[分享]遗传算法(C++)

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
* L/ O: \( E- [, `+ l3 R4 g//
//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
4 ?" {# y1 }4 F, G5 h<>#include "Genetic.h"
#include"math.h"
#ifdef _DEBUG
) c5 l5 D2 |& d#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
$ H; `; s- e* A) M#define new DEBUG_NEW
. ~/ c; @2 P0 _  ?: T#endif
  S* U- q  m9 Z4 X" k/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
& `0 Q1 A8 W& G+ w9 l* C* R( F//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
# t# s" @8 n% k# d<>CGenetic::CGenetic()
8 V- [( T6 T! I* D, C/ ?{pmutation=0.01;//变异概率
- G  q( {, {* y# R% _ pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
4 B2 c! e! N$ w gen=0;
IsSetScope=false;//还未设定个变量范围
IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
dblCre=0.0;
dblDifference=0.15;
/ S! ~, F  ?& Q2 x" T9 p: r best.fitness=0.0;
; p  Q* f- H6 w8 r
initM(MATCOM_VERSION);
: r/ i) I& h: [4 E$ c! q }</P>
<>CGenetic::~CGenetic()
{exitM();
4 p9 [- u, V, u8 v4 ?# W}</P>
9 A) V# Q( H4 b<>int CGenetic::rselect()
{double rand1,partsum;
- ^5 [9 U9 v( R; x int j=0;
partsum=0;
rand1=rand()*sumfitness;
, k( L# l, V  ~' V% X$ J, w3 p4 b do{
  partsum=partsum+newpop[j].fitness;
2 d5 S# b' J; `/ t- X* e; N9 F  j++;
. i/ d& J1 Y% A3 B- h }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
2 C8 c. Y9 f9 N/ T1 q$ R0 h6 i}</P>
<>void CGenetic::generation()
% j( o* n  e: Y* l% ]{int i,r1,r2;
CHROM tempChrom;
( n: \" W7 p1 K* r& o* p# y2 b5 n //进行统计，计算newpop单个染色体的适应度，选出最优染色体
# c9 y" k9 P% |& x5 O! c' Q statistic(newpop);
% R7 c4 u8 T9 j4 S7 h! A/ d //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
, u3 S/ G* b( a9 D% b1 W  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
/ e6 \. t- a: E6 h1 u: s* e }</P>
% x$ u7 S% c3 h0 E! D& t<> // oldpop,newpop进行调换
0 s' [6 K, A" @- V6 d) w for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
2 d' u6 k- P  \+ y6 Z8 W  oldpop=tempChrom;
}
0 {: U5 \" }" c9 | //从1到POPSIZE循环，对newpop进行变异
5 P3 Y5 P5 S) \4 I$ E/ z' A    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
<>bool CGenetic::begin()
% q3 f. q, `( D% d* t, B{MSG msg;
) F: e. Q4 {/ Y mData=zeros(1,bpnet-&gt;iInput);
/ B4 H. W  w# v- ~' `# _ mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
, u1 ^- J* d7 H  D  break;
( L5 ?; \6 J% G if(bpnet-&gt;iOutput&gt;1){
* ]' O, Y; S/ q* | ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
  b1 a6 {( P& X( f5 U return(false);
}
8 M, k( \$ X9 u, o% Z5 Z if(gen==0)
* c/ ^6 z0 }5 o0 b3 y  init();//如果刚开始运算，初始化
generation();
  q" s  Y4 X3 {1 m; S gen++;
" _/ J2 e  h7 n: \3 G( i- t //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
1 t9 x3 S1 q1 q% j6 M msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
2 X) u4 c: ^# Q# D5 ^& s, \}</P>
<>return(true);
  X* T: x% v# ?3 ?3 t# E; E}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
  z  g6 K# R1 w) R2 G% D9 ~{double c;
3 \1 q! N% u2 V1 H" D# c int i=0;
/ N9 {* B9 I0 q  B2 o! {//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
% J+ B8 J- c/ R& B do{if(flip(pcross)){//交叉概率
c=rand();
    for(i=0;i&lt;iVarNo;i++){
7 N; C4 S  ]3 x, Z! b' L oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
}
" s) @  r1 d( f; M# l! ` else//直接赋值，不再交叉
+ O1 p3 Z& A6 Q {oldpop[iPlace]=chrom1;
1 A0 m- P2 p, K  oldpop[iPlace+1]=chrom2;
* d6 {- f. X$ Y5 w }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
7 S$ `7 J4 X5 Z9 q<>}</P>
% M; r  v! E% P6 T; r<>bool CGenetic::flip(double possibility)
+ L; i4 Q7 I9 q1 I& c{double ppp;
# O' `" {( q- i9 Xppp=rand();
* R% {2 x! o7 q# v; @if(ppp&lt;=possibility)
+ B9 }& k/ X$ F0 }* X return (true);
9 W( @- p, g3 s' Zelse
+ z$ C9 R5 y! I return (false);
% I# R0 k* b8 _+ B7 T5 j1 D2 V}</P>
<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
1 O  m8 S% {- D/ [$ ~ int i=0;
/ ]2 \7 Y* P: W" r9 m CHROM temp1,temp2;
  k6 p4 s, \  j% g3 `9 B6 k- { if(flip(pmutation)){ //以变异概率进行变异
& x' B# s6 }* h( a( r  do{ for(i=0;i&lt;iVarNo;i++)
# {1 E' @+ s+ l4 T3 M/ O  D! `     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
. E' c1 A  E! g  J( Z- q    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
& h/ g# V. L* M% @  }while(!identify(temp2));
}
* h; M: X& o9 Z9 v2 g+ d else{
9 e" W  z! I5 J, @" j8 a  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
8 v& T/ t  @$ W }
- G2 P; T3 Z0 v3 R4 ^' t' S for(i=0;i&lt;iVarNo;i++)
; b9 X) X) A! d% u" b( y  chrome-&gt;chrom=temp2.chrom;
* p& M; L; F0 v( _; h" ^}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
5 Q/ s/ W3 O# {- ~5 W5 u) q sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
4 z: q) J& B( l( C, r9 ^( w; L* Q if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
" R' Z' t  p+ [1 v# a) L}</P>
<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
, |. ~1 \: X; F: e/ o$ H* K. Oint i,j;
* w+ h6 A1 c8 x% k( Csrand( (unsigned)time( NULL ) );</P>
# D6 C, D/ O5 C3 N- o+ V# Y) z# |<>if(iVarNo!=0&amp;&amp;IsSetScope)
/ `' M& _  A8 ]$ R( O) a- ^, h. p{for(i=0;i&ltOPSIZE;i++){
! Z! v; }! V$ H: p6 H" n for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
. i6 b. e8 s2 l4 r1 d* S        oldpop.chrom[j]=newpop.chrom[j];
}
$ T' n+ a$ W; `% z0 g}
: E  p$ l; Y/ C: ]: p}
else
- E: w; A8 K$ b4 v {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
$ N0 h% z6 b' J9 E9 I! j) H, _  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>

# Z6 l+ T% X& i. S3 E8 m<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
0 H- n! `6 O! [; R. G8 c<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
  {/ Y* v1 Q7 Y" Y/ I& Efor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
2 M& c* C# b0 p5 V9 j varminmax[1]=scope[1];//最大值
$ O8 H5 P6 l+ u/ s4 Q4 C}
IsSetScope=true; </P>
<>}</P>
9 {& W+ X) z: x6 i<>double CGenetic::CalFitness(CHROM chrome)
! h6 V8 X  h1 H4 Q6 Z5 m{ double dblResult;
3 B3 g- c+ T2 ^) V int i;
* C  S+ S6 I/ L for(i=0;i&lt;iVarNo;i++)
5 W0 Y2 m, Q$ _( }  P4 T0 m  mData.r(i+1)=chrome.chrom;
* b) x! `9 z' A6 |5 O mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
# }+ `1 ]& `% s2 h. | return(dblResult);
}</P>

<P>bool CGenetic::identify(CHROM chrome)
4 |& c1 ?& {- x2 q. @{int i=0;
bool IsOk=true;;
! l% B/ F2 j+ M6 F1 m# | for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
% m$ T6 Q8 Y: k7 P3 b/ _9 c! O7 w  break;}
; Z* p$ t: R' ^* x- K2 X  c* g- D8 S2 } }
return (IsOk);
' J/ ^7 ]+ Z1 {; Y; E& _}</P>

$ N# h' K+ a  a2 [- T<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
1 n& w; ^+ E# t0 g4 [' ^{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
) U- f+ {" e6 h) b1 S7 n for(i=0;i&lt;iVarNo;i++){
+ ], Z( _/ l2 @( y! m  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  w* Z0 [) J" l4 U6 ]  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
( c: m/ g8 @3 u6 s& y8 N }
( b; w6 c/ W+ w( E0 A temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
1 v  C/ n; ^  `9 @; h- \6 o: r return (differ);
# Q# ?8 t, O* D: M" W}</P>
<P>bool CGenetic::IsNew(CHROM ch)
9 W9 p: R( I9 d8 C{int i;
9 H  O* j" B$ b: i1 C7 i bool IsDifferent;
IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
: a% h9 t! L# f0 J. a' S" r  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
  }
return (IsDifferent);</P>
3 s8 A) n0 y/ j$ Q) P% |<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
: F( R# y6 P- F7 @3 e2 z$ g* t{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
double dblTemp1,dblTemp2;
( `; k; V3 W5 |; K* a for(i=0;i&lt;iVarNo;i++)
8 K# Q- K9 {% [; M {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
. a) z$ B4 Y( `9 Z% P) J, }1 P  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
9 w( ^7 P! I* H$ B2 ?5 n) B8 q  temp1+=dblTemp1*dblTemp2;
5 c6 e# J5 L3 U' h) _9 [- k  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
temp2=sqrt(temp2);
! d  ?- F6 Z/ I( e$ V temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
% e1 a+ i% B, c6 D pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
# ~8 Y4 Y' ?8 [  r- ~3 m0 z3 x# V<P>}</P></DIV>
+ z& g6 l3 \1 Y- ~( V<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
0 b! N8 B5 k& X+ a1 c0 X#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
#pragma once
' U, a2 U  Y; p1 x7 J: r: f#endif // _MSC_VER &gt; 1000
  t8 F1 g5 S( u( O#include"definition.h"
typedef struct mychrom{
4 K2 W3 H7 j6 ], B9 Edouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
6 `7 |' Q* O) j8 c5 ^: R#include "BpNet.h"
/ k" p) ?7 d) `2 Z, I////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
0 o. j7 s) s! R$ }- R7 M9 Q{
public:
$ ^% R& J. N7 b: k% i; A8 m: ]6 f bool IsStoped;
. I% m$ T/ d) |( }& g double dblAngle;
9 V6 G6 H: M8 B, b0 V# y: D* ^ CHROM best;
Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
) Y/ I, w" H' |% t6 i2 t/ t double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
% K3 q* t* \- P7 S CBpNet * bpnet;
//double (* obj_fun)();
( N$ y' E/ S+ b0 v1 h1 o/ ?' U9 E double CalFitness(CHROM chrome);//计算适应度函数
% x3 c( O+ r8 e; U( {8 p/ j+ j# T long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
* ]# e4 F2 g$ m( N+ M" X void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
: ^  K4 {3 k7 o' C/ A4 C bool begin();//主函数
void generation();//一次进化
! [5 r9 w$ _) W$ ?! \ int rselect();//轮盘赌选择
6 c. b' s; H) P' h+ z) N CHROM newpop[POPSIZE];//种群
: b) Z5 I. u+ q4 H CHROM oldpop[POPSIZE];//种群
9 q6 N4 Q7 s) K$ V: Q double pmutation;//变异概率
double pcross;//交叉概率
. L$ G# e* p. W6 T( k# B# h; m) s( @ long maxgen;//最大进化代数
! {8 g* P, z3 |7 H7 ? int iVarNo;//染色体数目
/ F/ M1 M( f! d6 I2 p! n double sumfitness;
  Y# i1 b3 F9 B& B9 v1 D0 i' ] CGenetic();
virtual ~CGenetic();</P>
<P>private:
double angle(CHROM ch1,CHROM ch2);
% F' A' l* d) E2 ^& c/ @ bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
5 g/ y  U! Q, q9 c<P> bool identify(CHROM chrome);//验证是否为合法的染色体
& b6 V2 v% o( B% T  b3 s2 T double varminmax[MAXVARNO][2];
7 g- L0 B; ~5 g, y void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
* x$ e6 ^& E& q& E- @+ u bool flip(double possibility);//测试
" T+ r' Z' \* \8 Y5 P$ L //交叉操作，iPlace指明新染色体位置
) i% k% A7 O9 i, X void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;
: E% e; f" W9 `( E. @
};</P>
6 i& U8 j" y, @% _<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

/ t; I3 h% f4 m6 S, Z. \</P></DIV>

bogolyx

细细，谢谢了，请问有神经网络的vc++程序码？

edewo

你好，你发的程序我也看了，不过请问一下在Genetic.h头文件中，头文件definition.h和变量MAXVARNO在哪里可以找到，多谢了，你用这个类了吗，效果怎么样

hawkltl

<>能不能发份你的这部分程序给我啊？(包含Genetic.h头文件)</P><>谢谢！</P><><a href="mailthawkltl@eyou.com" target="_blank" >hawkltl@eyou.com</A></P><>QQ:297478832</P>

canglang

不错,支持

yiping_fly

<>有量子遗传算法解背包问题的程序么，谢谢斑竹</P>
' j% f$ c3 Z& p4 h  r# l- H<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>