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

ilikenba

<DIV class=HtmlCode>
$ j, n0 {+ _; E- [3 {! |( O+ w' X<>// Genetic.cpp: implementation of the CGenetic class.
//
: K/ {. i! E7 j5 v. g/ E//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
9 x; f3 Q8 g, q( h$ j#include"math.h"
#ifdef _DEBUG
6 r7 ]! k) `# J) I* A1 H#undef THIS_FILE
" j/ ]2 K: C5 u: w5 f: T/ Cstatic char THIS_FILE[]=__FILE__;
- J) T% n# e/ l. I1 y#define new DEBUG_NEW
6 \8 W+ c; l. K( |7 F) K#endif
" _# q. P/ b- z5 h4 Q9 T, |' `/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
6 u' u/ f; j  ~, k6 f//////////////////////////////////////////////////////////////////////
& l+ `9 n6 T' e+ ]9 p! q6 _* ]// Construction/Destruction
* x3 W, w9 k# O  q7 b, |/ G//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
1 k: y9 m/ Z, }% o+ K5 l iVarNo=0;//染色体数目
' e/ }( b2 \" k3 r5 q: s sumfitness=0.0;
# r* D: J, G5 I+ V' q4 M  t gen=0;
IsSetScope=false;//还未设定个变量范围
+ R* s1 E) }# L# m$ x' a; h IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
+ m4 A6 y' n+ [; o) K   bestchrom.fitness=0;
iBestNum=0;
- r8 r" S% z% S$ R) N3 R3 M dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;
/ Q' u6 \7 ?' O0 X9 n% D1 e. b/ i
" {8 N( M. U* L* j" ` initM(MATCOM_VERSION);
}</P>
) T  O7 N$ U2 j+ s/ g, T3 r<>CGenetic::~CGenetic()
* j  E7 j, ~  E& V, }$ ~9 i; Y- l7 }{exitM();
+ {6 M9 e/ F7 {$ @& q& e}</P>
0 }6 {4 n( C' v- u4 b: |<>int CGenetic::rselect()
{double rand1,partsum;
& b8 p" f: e4 |& W8 V0 s int j=0;
( g8 P* U8 |; F& t2 d8 F partsum=0;
* c/ I+ U5 |7 M4 m' } rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
& E! `6 H  A/ \2 M' {. x* g  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
* x3 }  h: H) s}</P>
, ^; B4 f% U& \2 \& k; p8 n<>void CGenetic::generation()
7 T: K* l2 f5 F  G1 E{int i,r1,r2;
* i; B& G2 K) a& c0 f CHROM tempChrom;
* [; s, B$ r. p6 W# j* l) O //进行统计，计算newpop单个染色体的适应度，选出最优染色体
2 C  l$ L6 A/ C9 \9 x8 Y$ X statistic(newpop);
" ^' E: V6 g2 R* {& M //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
% ]7 Q9 d8 l3 B4 u2 u  r1=rselect();
) y  M: G6 a7 A" @  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
: U' M/ \* L8 c$ E, M }</P>
<> // oldpop,newpop进行调换
( E* {' t  J, v: g) g for(i=0;i&ltOPSIZE;i++){
3 h" L  P: m+ T/ {% A/ @  tempChrom=newpop;
9 u( L0 m: ?6 \  newpop=oldpop;
  oldpop=tempChrom;
}
2 c) y  P) Q; V: g. n //从1到POPSIZE循环，对newpop进行变异
! S0 f0 z) q+ F+ r' H( I4 Q    for(i=0;i&ltOPSIZE;i++)
: U# A+ V0 @( p2 r5 L, }     mutation(&amp;newpop);
; @2 d# y( @4 j# \) R; |# M9 G; m}</P>
<>bool CGenetic::begin()
{MSG msg;
) U( B, B( U" V/ M# X mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
2 F; `) W8 ]1 L' R) E- a* [8 c{if(IsStoped)
2 o4 d0 ~$ M1 H  O0 k! r- j% C% K& N  break;
if(bpnet-&gt;iOutput&gt;1){
  ]/ w+ e! q5 i5 h3 }( z, a ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
# P) r# P/ f1 a. }1 p return(false);
: w+ U4 B5 `9 H8 g% }" } }
if(gen==0)
  init();//如果刚开始运算，初始化
8 |8 f! `8 Q6 [1 L% E generation();
9 ?) j: o# E: C  W. e6 j gen++;
2 I- T) u5 u/ \0 ^ //防止假死机
& e( M9 R, J4 S1 v :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
+ H/ |$ {& z$ J, i9 c, ]' U+ I :ispatchMessage(&amp;msg);
- R* \/ e7 {. o! l8 k- ? msg.message=-1;
7 |' W& t/ j3 o! P1 W$ e; T :ispatchMessage(&amp;msg);//这样可以消除屏闪
. ]! s1 t( m0 W) @* T}</P>
<>return(true);
" O) H& y9 r# B2 @' I}</P>
7 d" n& ~7 T4 Y/ j) w: `6 P1 \<>
  I) V: ?' ~5 ?1 S! d) @. e2 T& j! Gvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
9 N# _6 E+ u/ C( d4 Y  O{double c;
) c; Y8 u; B6 b# z: x int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
0 m  r/ s# ]/ \5 v8 m c=rand();
! u1 Z) ~) c  v( J, Z* x: D    for(i=0;i&lt;iVarNo;i++){
' h3 R5 o8 c& x/ W( ]5 H% G8 _ oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
! b) j$ b# ]3 d, O0 g }
else//直接赋值，不再交叉
2 N- i  Y- E/ w  H5 ]% c) Q {oldpop[iPlace]=chrom1;
0 P" C% p5 i7 K, X8 M; t5 K  oldpop[iPlace+1]=chrom2;
}
# i+ l* Y8 F( J3 N}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
. y/ q: q) A3 D4 A<>bool CGenetic::flip(double possibility)
{double ppp;
: A4 X+ U3 H1 a/ `" C/ hppp=rand();
- f" l" D+ [1 q/ Bif(ppp&lt;=possibility)
- J7 R; [8 h0 t2 W return (true);
else
" a) W3 Z- ^1 j+ `& s, x! U return (false);
+ i0 L' j# r! p$ P* P- }$ V& ]}</P>
1 \# C+ {% ?! O$ u8 B, z, ]* _<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
9 F+ S. v1 R) V5 T6 x; F3 V, L9 h  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
$ C) R! y& C6 @) T4 [$ j* a' |3 s, s         for(i=0;i&lt;iVarNo;i++)
: [7 q8 K% U' I% N    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
3 d0 R- X3 X6 k# h2 D          for(i=0;i&lt;iVarNo;i++)
" F' ^1 \- t4 s' S+ m) X# f# f     temp2.chrom+=m*temp1.chrom;
/ o/ o1 C1 \6 \  }+ ?    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  k% z2 i+ F9 D' H  }while(!identify(temp2));
2 b9 f9 D0 o. N( j  Z6 l }
else{
  for(i=0;i&lt;iVarNo;i++)
" ~3 q( c! Y& c) K" m( u7 ?% W% D6 j3 |     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
% D& v) t# R  X. _& c) v  chrome-&gt;chrom=temp2.chrom;
}</P>
: h4 ]' ]2 L0 B$ v1 [: ^+ f, K<>void CGenetic::statistic(CHROM pop[])
{int i;
9 q9 ?0 `, t* T3 T: T/ L sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
* F/ n# G6 r& N  P0 y- _   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
4 r$ }! Z' c- p0 Y9 j for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
9 D* r( y( J- A; ~7 j+ P  best=pop;//纪录最佳染色体
) f6 ^" x# M7 m! k2 ]) F}</P>
5 h+ G; W' G; T3 T* x8 q7 {<>}</P>
/ _' P1 T' \4 S! f8 T<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
0 H4 W" F. |1 t7 q+ k# _, Zsrand( (unsigned)time( NULL ) );</P>
7 R4 c* X* L) n1 g) P<>if(iVarNo!=0&amp;&amp;IsSetScope)
& ^: Z- B& {5 F! B6 ]+ {  \  d{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
" j3 S3 X0 ]( M- U  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
- P/ a! _9 ]5 C/ @5 e5 G        oldpop.chrom[j]=newpop.chrom[j];
}
}
}
4 }& B* A  D* R$ B, x# x else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
6 {* H* d& p0 [% ~, x}</P>

% K9 F' P2 ?/ p8 M. \( U<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
/ G5 e, L( k+ c$ d{varminmax[0]=scope[0];//最小值
/ D1 w+ V9 ^/ V: I( m) j varminmax[1]=scope[1];//最大值
}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
/ W, e5 Q) Q3 q7 n* ?) H; K- R{ double dblResult;
5 ^% Q9 c/ i1 Y6 f  j int i;
for(i=0;i&lt;iVarNo;i++)
7 B6 h' ?& ?; {9 d+ p+ f; f  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
- |5 f9 P( f) p dblResult=mResult.r(1);
return(dblResult);
6 ?  i" s$ j% W3 C6 F; p}</P>

<P>bool CGenetic::identify(CHROM chrome)
3 Y: \( T* W/ N& S: l" {{int i=0;
  J5 j) U; R$ f) f/ `0 a8 d3 r% X) M  W bool IsOk=true;;
" X9 G! @/ ^6 h; f. ~" E for(i=0;i&lt;iVarNo;i++){
# j. }* i$ n; \* X8 d- x, C% R  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
1 y+ Y1 p" t# h) k# I7 y( k: X  {IsOk=false;
, T) U* G  [. x9 @5 e+ i  break;}
}
return (IsOk);
1 c4 A1 Z" S+ V- a7 u3 u}</P>
- [& V$ O: Z1 O: `
6 }' K7 H/ H% Y' R% x4 O<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
% B* K2 v+ a8 x, Q{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
. Z0 U* e& U4 v2 V int i;
5 c9 s7 c# T/ d7 {# s2 l for(i=0;i&lt;iVarNo;i++){
" d; l6 b  u7 h) p+ F7 e! s  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  j$ t- M3 F& Z5 G  n7 A4 O9 i+ E  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
8 T& N8 m* I5 T; w     temp2+=dblTemp1*dblTemp1;
) {$ c* g' L7 {- y: B4 _+ x% Z  Y  temp3+=dblTemp2*dblTemp2;
}
" }7 w6 o  Z$ u3 Q temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
return (differ);
5 e4 n3 v. u# x2 H& J}</P>
5 `+ r. U1 g- r<P>bool CGenetic::IsNew(CHROM ch)
{int i;
7 Y0 n$ u8 I* |% K- [ bool IsDifferent;
IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
% W$ S4 X2 W" @; t  }
4 o# p" D, Y; l3 H. rreturn (IsDifferent);</P>
+ t2 l! V7 J7 h" @! G+ a<P>}</P>
& _( h0 f/ A1 ~8 f9 m) h, c$ W: L<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
( D1 c2 ], r, M{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
/ `! B2 s7 I! {/ u4 y& O5 c double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
) H( Q( u' Y4 M6 X {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
% h# b2 T, A- F1 I }
% h; H; D, E0 X7 w! ^ temp2=sqrt(temp2);
temp3=sqrt(temp3);
* y. G. M3 j9 X5 { dblCos=temp1/(temp2*temp3);
; o: K; J1 C* p$ M3 G5 k pi=acos(-1.0);
( h9 R2 |4 F/ u1 q/ p angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
, `5 T! @! {1 e' A3 q/ j return (angle);</P>
& x% u1 N3 k% j<P>}</P></DIV>
9 Z% \% j# ?' q<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
+ R* M& X  p5 m/ m#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
1 G6 K6 n7 G; u<P>#if _MSC_VER &gt; 1000
#pragma once
3 g. {! k# E* C' L7 f#endif // _MSC_VER &gt; 1000
7 r* c* `  e6 I) e( E1 P# Z#include"definition.h"
- a6 K  U( C$ [7 K& Y/ f: e/ {typedef struct mychrom{
double chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
public:
( k) ?: p; m, a$ F bool IsStoped;
/ g* S$ C+ ~% q3 p; \ double dblAngle;
CHROM best;
Mm mData,mResult;
8 C0 Z2 X% [: [3 i3 L- q/ W. G6 j double dblDifference;//差异〉改值的染色体视为不同
* ?0 J* |- N6 @1 k. {, \- b double dblCre;//适应度&gt;改值的染色体符合条件
: b5 ~0 X5 p6 D$ s int iBestNum;//符合条件的染色体数目
3 L7 k8 C* f; M7 a& o$ L CBpNet * bpnet;
1 ?6 U  p0 c' s) E% ] //double (* obj_fun)();
! P, O; x% `! P. T3 t double CalFitness(CHROM chrome);//计算适应度函数
  ?, K0 f8 E6 k: H long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
3 u( }$ G1 {0 b void generation();//一次进化
int rselect();//轮盘赌选择
' w2 y% ~. ?& [ CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
7 m; E" ^/ L/ l double pmutation;//变异概率
" a0 m' U6 O# k3 o' W double pcross;//交叉概率
) t3 W7 z2 @( x1 C$ S7 }( l long maxgen;//最大进化代数
6 |1 W5 ^$ Q9 S8 W6 w7 E int iVarNo;//染色体数目
double sumfitness;
CGenetic();
/ p& G% _1 G+ u7 O# N5 B4 n virtual ~CGenetic();</P>
  g* U% d! ]2 X& A, W# C/ W1 ?# g" h5 c<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
( W" Z! S! H0 _6 P, V( U3 {: D<P> bool identify(CHROM chrome);//验证是否为合法的染色体
4 Q% G/ K3 h$ Y! F/ ?  b double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
9 t9 k1 ~& W- \, n* H; }" I void mutation(CHROM *chrome);//对新染色体进行变异
$ _! e  y9 ]" p2 C bool flip(double possibility);//测试
" `+ E- }1 x+ `9 p+ d! H0 Y" y //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
3 D8 x. W( e1 y9 |3 D, v bool IsSetScope;
) Z4 X2 X6 W7 y- A
};</P>
( N! Z* ^6 y+ b0 Q$ C* w3 ^<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
3 g4 X$ }9 [' Z  l" T8 T
</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>
) M2 J6 v% G- z2 w3 d% K: k* s<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>