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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
' u  B6 J* N+ r, L  `4 r7 c2 T+ k//
" G, N$ c) [& _4 M) \9 H6 T3 Z" x//////////////////////////////////////////////////////////////////////</P>
* n$ K2 \% m" }3 `: F$ V1 m1 ]1 q<>#include "stdafx.h"</P>
, l9 @  _" L/ }& A<>#include "Genetic.h"
6 i- N0 O, R% J2 ]) g4 x#include"math.h"
#ifdef _DEBUG
$ G; {" |0 ?# K. y3 ~) x7 ~#undef THIS_FILE
5 h; b3 [+ o/ U9 F5 C2 Qstatic char THIS_FILE[]=__FILE__;
+ x" I& Q5 w" I' G- N, R#define new DEBUG_NEW
#endif
- W1 d, `/ b" j1 a; f9 X- p/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
6 U6 h# @8 U% k( z//////////////////////////////////////////////////////////////////////
// Construction/Destruction
6 u+ P$ J" c% B  Q9 z" @" \: }+ x+ ^//////////////////////////////////////////////////////////////////////</P>
: ?: u' D. o+ e0 _<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
9 k) n! h2 Q1 K7 `2 } pcross=0.9;//交叉概率
0 ?+ R! w8 V- _2 `. e; M maxgen=5000;//最大进化代数
" ?! ~; U6 _6 M' u3 n0 L iVarNo=0;//染色体数目
# b% z3 ]9 z" s7 b2 I$ Y" Q sumfitness=0.0;
. s/ a1 i! P: |% {. j gen=0;
IsSetScope=false;//还未设定个变量范围
* u/ K  C; ]  P0 i IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
3 J% E1 v( V7 u, _, t- I6 f' k+ B: q   bestchrom.fitness=0;
+ T) [8 D6 K6 b# T0 _6 Q iBestNum=0;
dblCre=0.0;
dblDifference=0.15;
; T1 y: a" ]( q$ v' [. x7 S best.fitness=0.0;
0 g$ q6 Y" o2 V: ?" y2 h! J& I
# g) o0 W, }! c/ G! ~1 z) j initM(MATCOM_VERSION);
" k! O" L' n, c! b! j }</P>
<>CGenetic::~CGenetic()
{exitM();
7 ~& L5 w! W9 T3 f4 k$ I/ b}</P>
. |2 d" }0 b% k& X  p, u/ _<>int CGenetic::rselect()
{double rand1,partsum;
) ]1 _9 S' x  u+ W3 y3 |0 D: A int j=0;
partsum=0;
rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
- \* h2 ?8 \  m5 z6 q" E% M return (j-1);
}</P>
- x+ g4 _8 m4 d<>void CGenetic::generation()
; [% ~1 B/ g" G. i- x{int i,r1,r2;
1 z$ Q6 q1 ?3 h. z; f CHROM tempChrom;
# u5 p0 A/ c: H8 s //进行统计，计算newpop单个染色体的适应度，选出最优染色体
2 M9 S) y% M9 V statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
" b* S" @2 \4 J3 a    for(i=0;i&ltOPSIZE;i+=2){
7 b* U$ x! |3 y* q1 d: Z3 R  r1=rselect();
8 X3 Z+ @# h% d0 U  c/ L7 k: V  r2=rselect();
; m% Y! g! P1 m/ P1 W  cross(newpop[r1],newpop[r2],i);
* J: n' D- ?+ O% [. @8 {: r }</P>
2 J* s: n$ d2 b( k. r" \: p' e<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
}
  S9 u! z) m* O' c3 x4 n/ L //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
. N! e) q6 H* o: Z' _: a8 w3 H}</P>
. Z5 A" x& T: B) n4 \  H4 H9 Y<>bool CGenetic::begin()
3 _% A2 N+ [# |" k{MSG msg;
# l3 \3 O) X) B0 c2 y2 _8 B: O mData=zeros(1,bpnet-&gt;iInput);
, `9 u+ p. I: B9 t8 l* N5 Y mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
& x' ^3 Y3 V% b! D, e9 u  n5 B return(false);
}
' ~8 h7 P) u1 c1 Z* d9 _2 e8 W if(gen==0)
2 ^5 G, L8 x) }; O* Q$ i$ y  init();//如果刚开始运算，初始化
generation();
gen++;
//防止假死机
; J  m0 j7 ?  c& Z4 _6 U$ e( e :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
- d. k5 `/ A7 H" `, z; _$ G :ispatchMessage(&amp;msg);
msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
<>return(true);
4 ~4 }, a0 ^2 E; Z}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
6 E6 m* c# B/ F& x6 D{double c;
3 s4 y6 }4 u. S  n% v" b* g int i=0;
& P! G5 a  j6 w//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
: u' K* K8 F9 r" j; x! e3 U do{if(flip(pcross)){//交叉概率
; ^5 c# x- B9 q2 N) D c=rand();
    for(i=0;i&lt;iVarNo;i++){
# z0 s' q" x2 J/ _, N8 I# I# w oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
}
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
5 I2 v! n8 e: J( m% B }
* a3 b0 p! Q3 [' _7 e& n9 o. F}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
4 w: k# N/ N5 N0 a/ |* S<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
5 x+ f; t; L0 i- kppp=rand();
if(ppp&lt;=possibility)
: G1 \5 q% h( \/ o5 I- U return (true);
else
0 L- l8 b/ l) e6 a return (false);
}</P>
<>void CGenetic::mutation(CHROM *chrome)
0 R* F8 O6 n3 ?0 _; J$ p{double m=10;
int i=0;
* Y/ ~" i9 J3 G2 J$ p CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
6 ?+ [! Z3 ?3 p9 {" K6 S, H  do{ for(i=0;i&lt;iVarNo;i++)
8 g/ x3 X7 _' Q. `     temp2.chrom=chrome-&gt;chrom;
% B. B' y# W/ l$ r. g( h/ s: c         for(i=0;i&lt;iVarNo;i++)
* W; X# Y4 g; g$ D4 F: R# l3 }    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
8 ~( B  L, m5 m! u+ a9 d9 G8 C' b1 W     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
( Z& c# D: w, Z- k8 A" f% n+ a$ B }
else{
  for(i=0;i&lt;iVarNo;i++)
7 b' T) m; H; |1 j5 z% I     temp2.chrom=chrome-&gt;chrom;
}
5 I* x" Q5 |1 E, u5 r7 Y for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
* C& d- S3 b$ N; W8 ^<>void CGenetic::statistic(CHROM pop[])
0 m9 a( w/ K8 K7 _3 d{int i;
sumfitness=0;
( k2 e. D( H; ? //循环，计算单个染色体的适应度,以及sumfitness
8 Y4 Z+ w! X, K' z7 K! @* I+ ? for(i=0;i&ltOPSIZE;i++){
6 w/ ^7 M2 z9 {8 q: I6 t   pop.fitness=CalFitness(pop);
4 f: g0 o7 S. {# i: @1 |7 H9 `   sumfitness+=pop.fitness;}
0 D% v* @% q) u* J/ a% | //选出符合条件的染色体
- ~- i" ?9 M  v. t! p! R' i6 L for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
% C' G' B: c, E! e! i  bestchrom[iBestNum++]=pop;
3 [" E4 ~! s! c6 A$ M if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
6 u/ e* A9 P' c3 E' S* u}</P>
" }" e, v7 i( O5 z$ n7 }<>}</P>
/ Z7 @# z* [) l. W0 |+ @! ?<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
6 _7 a. n% x& C) O: [5 U2 Esrand( (unsigned)time( NULL ) );</P>
- P1 v- C. B9 g7 K<>if(iVarNo!=0&amp;&amp;IsSetScope)
$ V- v$ ?/ d) N/ S- h4 g{for(i=0;i&ltOPSIZE;i++){
# _* L, J6 f! S5 M for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
1 G2 F2 k, C& Q: {  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
}
}
else
" s5 W: J9 _3 V# d {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
( m" f3 [8 h' y- N  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
; p. r1 r7 u7 ? }
}</P>
. s0 x7 z+ @: V" z9 s* y6 u0 l
<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
$ Z2 I" u# p: T) h<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
: `. [) u/ I: Y9 Z4 v2 M- b{int i;
( F. \$ y- ?* W( V9 r8 k+ Yfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
6 H- \8 f  o! x varminmax[1]=scope[1];//最大值
}
2 T0 Q: z! q; f3 _4 t( ^) CIsSetScope=true; </P>
<>}</P>
* I! a( f; y# k8 ~: C7 e8 h1 v<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
for(i=0;i&lt;iVarNo;i++)
9 V4 ~5 j5 T* i, I9 _+ C, ?  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
  C4 n/ |2 V6 i; W9 _& O# y dblResult=mResult.r(1);
% Z; O2 O( L: v% s, J5 j  O return(dblResult);
, t9 T) |" y  s1 V}</P>

<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
) g' N% O- H. @/ d& }0 _ for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
( [/ ~: k( j" c5 w2 H. k3 R  break;}
}
return (IsOk);
}</P>

9 U8 w8 N. z4 D6 D<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
for(i=0;i&lt;iVarNo;i++){
* Y7 J3 R2 T. |- v9 ]  |  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
# H- M8 G* u/ y3 v$ Z( l  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
+ H% O4 E+ o# ]$ P7 h1 P  L     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
* M7 D- B: Q; e( M0 B; J$ S* D) g- a }
, x1 g5 e; x/ L6 O/ w5 F6 B4 D+ o temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
7 V% c) t- c# @6 J' t differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
1 q! I" Z: s$ Q& Z, Z<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
/ W* r  O- e7 I7 u! j IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
% i4 t- x8 X7 n9 E  {IsDifferent=false;
3 b6 t; p. F* [+ ^      break;
  }
return (IsDifferent);</P>
<P>}</P>
9 m! a) Z) [$ }1 R<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
0 Y7 V8 p4 r. p' @& Y  ^8 f; q{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
4 t& Q: e) _7 d* Y- h; i double dblTemp1,dblTemp2;
4 V4 F  B; o$ A$ Q% @! M for(i=0;i&lt;iVarNo;i++)
) Z2 O" a' G  \& L% G; ? {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
/ |! b8 E0 `; `' \& y, b  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
$ ?- H1 t+ S  f0 l, x  temp1+=dblTemp1*dblTemp2;
: ]* s' [) j7 T6 p" q/ \  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
/ s- [. @3 o  ` temp2=sqrt(temp2);
' f! {) ~  |3 Z. N- s3 x temp3=sqrt(temp3);
# K" F+ ?) w/ N& T: u dblCos=temp1/(temp2*temp3);
% Y0 F% s* P0 p& B5 Q( H pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
9 f3 V; j4 G* c; ?6 W8 U" F<P>// Genetic.h: interface for the CGenetic class.
9 a/ c8 A& Q1 i8 o/ u6 D% ~//
//////////////////////////////////////////////////////////////////////</P>
/ M! N' W; X. R1 d" T<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
# W9 k# `5 D$ |% K4 X8 `- {  x2 I<P>#if _MSC_VER &gt; 1000
3 A- f0 `, [$ T! [# {0 P#pragma once
8 Z% {. U4 M, ~/ J9 T3 P. _#endif // _MSC_VER &gt; 1000
1 D1 E* ?6 u! {4 ?- h" E9 ]: b# @$ I#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
#include "BpNet.h"
4 K( ]1 k& D, f" r////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
2 D  d* W" R! Rclass CGenetic  
% k' w% {  Q* [6 Y' g{
public:
bool IsStoped;
double dblAngle;
  G; t7 ^# x0 j. a CHROM best;
! R1 `# k' G/ A Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
1 k, h7 T+ Z  `2 E; e CBpNet * bpnet;
1 X' |* U- i! }/ e //double (* obj_fun)();
5 [# H1 U- k: o" j6 Y double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
7 P- k; z* C- e' h4 ^% [& ?( F0 E void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
" ^, o. R% s* s. `! e2 T; X$ H" Q double randxy(double x,double y);//产生x,y之间的随机数
/ P& f% _9 d/ S9 ], P void statistic(CHROM pop[]);
3 b$ J) @% j/ E% b+ ]4 D CHROM bestchrom[MAXBESTNUM];//最优染色体
! Z  ]7 p) z) A. j bool begin();//主函数
void generation();//一次进化
5 X0 r* F& m2 g int rselect();//轮盘赌选择
8 M0 p( c/ ]. i* ~& T) A CHROM newpop[POPSIZE];//种群
: g# q. ?) c4 A% @! M2 @ CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
. k1 H+ m5 g+ F long maxgen;//最大进化代数
" Q) f1 n) A; Q8 k. t* v$ F$ U5 d int iVarNo;//染色体数目
) @2 s. s( u7 h3 p0 r" N4 x$ i! c  w double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
$ @) m( I) y, I/ G! e! g  H6 U<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
0 ~6 F1 U/ x8 \( j double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
) {* p2 Z1 l- z/ F/ }<P> bool identify(CHROM chrome);//验证是否为合法的染色体
0 O; W2 A" i3 T. k double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
6 g9 m! v, p  P# y" T //交叉操作，iPlace指明新染色体位置
1 ^1 T. L: I, G, G. y7 q; u void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;

};</P>
1 M# I# E% V' |9 U+ l/ x<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

</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>
# x- s7 p2 r# G<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>