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

ilikenba

<DIV class=HtmlCode>
' S' s' k' |6 n" q<>// Genetic.cpp: implementation of the CGenetic class.
0 l3 O! R7 b( @! N//
//////////////////////////////////////////////////////////////////////</P>
+ B% n0 V" t  q0 _& h6 L+ \<>#include "stdafx.h"</P>
<>#include "Genetic.h"
$ c9 [( v( X% R5 n2 p#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
1 j5 w1 p' C8 R! r#endif
+ e% e# {( J$ d9 T/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
1 m! W$ C6 S! E- f$ I<>CGenetic::CGenetic()
, o+ i0 Q; ]" V* i: P! r3 v{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
" @3 \* Y& T7 A  z$ [ iVarNo=0;//染色体数目
- h3 E' N: u; ]! }2 M sumfitness=0.0;
gen=0;
9 F% {6 R+ |3 o- B1 V( s IsSetScope=false;//还未设定个变量范围
3 q) M. Y' I4 `3 m& x! V, A IsStoped=false;
' E9 j" }( D* ^% x0 p6 Q for(int i=0;i&lt;MAXBESTNUM;i++)
: }+ K  L6 q8 \' C& ]) Q1 z. F   bestchrom.fitness=0;
+ p* u! H+ T! v( ] iBestNum=0;
" K9 p" I7 n1 [  y4 Q7 U. \8 S4 C dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;
7 P3 \/ z; p0 R1 t9 y6 d. H
initM(MATCOM_VERSION);
1 h9 E' }; g0 g }</P>
& a* v( B" s2 j3 ^<>CGenetic::~CGenetic()
{exitM();
  @7 Z, u5 N% ~. T- w  a& s( W, e7 z}</P>
<>int CGenetic::rselect()
: \  K8 P3 ^9 C9 E{double rand1,partsum;
- w" ~' }" ^; b9 Z5 b int j=0;
partsum=0;
rand1=rand()*sumfitness;
4 Z8 {8 s8 C( |; E do{
  partsum=partsum+newpop[j].fitness;
) {8 t- F+ ~  F2 K4 ?; j2 T  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
7 y; u0 q# i- `2 p5 [! i return (j-1);
}</P>
2 V3 r2 {, \0 l<>void CGenetic::generation()
$ {3 @* W6 F$ C{int i,r1,r2;
CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
. N0 w# v/ D, W- | //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
( X  [# S- W9 P  H    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
9 {$ q- n  ?' T' i( d4 q7 f  cross(newpop[r1],newpop[r2],i);
}</P>
5 r4 C9 J. L" w: F! }- i<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
% B3 O/ T6 a& D+ h$ h8 U  tempChrom=newpop;
  newpop=oldpop;
* }4 A# ~) i( \  oldpop=tempChrom;
! w: n% ^' u4 { }
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
  n% K, o$ x9 L9 t/ I+ ^     mutation(&amp;newpop);
}</P>
+ b( ~; C, f. U4 [: M) V<>bool CGenetic::begin()
! }: j" F  t& F  m7 m7 |{MSG msg;
" v. A: E7 Y* ^( b" F mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
0 F1 K. |/ X8 {6 b2 l0 [for(int i=gen;i&lt;maxgen;i++)
3 I2 f& ]6 r& j& m' K* a{if(IsStoped)
  break;
5 `/ @" |  S% y$ ^2 c if(bpnet-&gt;iOutput&gt;1){
7 {) i* v* P& m( u ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
% c  @' l  {* F9 G8 U return(false);
}
if(gen==0)
+ q5 I7 C5 K& b* A8 @, P; m  init();//如果刚开始运算，初始化
generation();
gen++;
//防止假死机
# y' Y8 m; C  ] :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
2 L/ C9 n3 {- L( Y  T :ispatchMessage(&amp;msg);
8 |4 u9 c' x* W1 e6 B6 C msg.message=-1;
% P4 k- f9 d8 n" S) ?0 { :ispatchMessage(&amp;msg);//这样可以消除屏闪
- `. G" ~; N3 M- ^5 W$ J- L' t}</P>
<>return(true);
8 a4 u( x' w5 t1 k1 d* m4 b: _}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
, h; ^. E( K! [3 j8 m( Q//循环，直到产生合法的新染色体
$ U: O, p; N+ O; q9 C do{if(flip(pcross)){//交叉概率
2 |4 @+ t7 n1 e' R. v2 Z% n c=rand();
# Z  I+ l1 r) v( d! k; \- z$ f6 P' h    for(i=0;i&lt;iVarNo;i++){
oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
- E5 R/ M2 O" V5 d) W' P }
7 Y/ d9 m0 `$ y else//直接赋值，不再交叉
( o- A: f2 h; r* x" k {oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
& g! D, h6 b# b }
9 x( g2 X" n! _, a" V1 {}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
' k. F; ?+ g# @7 @: N' R<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
: ]% f% m! k( ?3 @* y8 N; oppp=rand();
% ?+ m/ ^( Q& Qif(ppp&lt;=possibility)
* `# m4 x/ Y+ s; e8 C% i return (true);
/ z& ]7 i; W2 u: T, ^) jelse
return (false);
. O! f/ q# L2 Q( @/ D}</P>
<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
int i=0;
6 f- y. u: V  J1 S CHROM temp1,temp2;
$ ]% K# l3 z* E) v) |- j if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
, `5 H: c6 T. t( B& q     temp2.chrom=chrome-&gt;chrom;
3 ~) V' l: e9 U         for(i=0;i&lt;iVarNo;i++)
+ p& T& y5 I/ s: g5 r    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
' e9 z0 _, Z# i! ]: l! H  R. H/ z9 |. ~    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
7 X) M7 c; F( b: c7 s7 x. E }
else{
* p0 p/ D& V& _1 x1 T" w, ~  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
3 x/ K5 u, O: y, r }
for(i=0;i&lt;iVarNo;i++)
  k  L8 \6 o1 b. f8 F1 T* P  chrome-&gt;chrom=temp2.chrom;
/ x# U7 T7 m6 r. k& s# x0 ~6 }}</P>
<>void CGenetic::statistic(CHROM pop[])
: w1 [! G: C" y( q8 u{int i;
% t8 a% g7 {4 v; u sumfitness=0;
8 Q: y, I& J. a* `# j2 U //循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
0 p5 R- C: h; w1 B+ I   sumfitness+=pop.fitness;}
//选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
: D7 {+ }" {/ r" h  bestchrom[iBestNum++]=pop;
! c3 M" L2 p7 C+ D7 E if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
2 `& y/ x! _/ r: s5 |* I' s}</P>
9 h- y" D2 C  E! @<>}</P>
& J, v  M5 Z1 @1 ]<>void CGenetic::init()
{//对种群进行随机初始化
6 _8 P- c; R# g) G  F8 I4 Sint i,j;
srand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
, @4 U* v( M+ a4 V4 C4 j8 R{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
- w8 C  M/ k+ |  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
) ^, P; g; W6 D7 T9 E# o& ^+ |1 p        oldpop.chrom[j]=newpop.chrom[j];
}
}
4 N: M* k  v- R0 Q}
' H! A7 N9 s- W+ f; k: ~; w7 ` else
2 b' Y$ S+ g& _9 }- A  O7 v0 V {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
  Q- I8 N* p. c7 S( O }
1 D1 y0 j4 R) m/ h0 n3 f}</P>

<>double CGenetic::randxy(double x, double y)
6 E5 o2 o0 j- [# A, d4 d{ return (x+(y-x)*rand());</P>
<>}</P>
1 U$ ~, U6 o2 y$ z4 ]<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
. S$ m$ u  ?2 C) \, X- a{int i;
9 G5 }; _0 F; R4 l2 Cfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
3 ~, t8 J( v& h0 U# i}
$ k9 i% j( Q& B, u* e4 wIsSetScope=true; </P>
( M7 O0 C1 W" j1 m+ h<>}</P>
/ K0 S. t+ z" e/ m  B/ G% Q<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
for(i=0;i&lt;iVarNo;i++)
; V7 R( i" g: E! o  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
. M0 p5 A2 f1 A$ M2 Q: ^ return(dblResult);
$ `0 Z4 o  F6 H& Z0 ^# a5 Q/ Z}</P>

, F/ b+ q8 B' p0 N# ^<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
( s  G( T3 h: `+ } bool IsOk=true;;
- I/ P9 ?& R, @/ j4 V+ m" | for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
  break;}
3 A. k2 o% W# Z; q) C }
0 Q0 C; _8 C  ?# }  U4 D return (IsOk);
}</P>
; G+ @0 N3 [& v; `) \7 \( s6 t! S
$ h4 C7 C( i: ]8 K. f0 A( S<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++){
) I: s: m2 |6 g8 D  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
1 G' k- k: k2 _7 H  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
+ y! B$ F5 X, v; K2 j     temp2+=dblTemp1*dblTemp1;
2 |( \4 ^- z* d! \: Q$ m  A  temp3+=dblTemp2*dblTemp2;
}
) L5 r7 f* M/ Y1 `9 j temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
2 ?& q$ O- \$ u; ?) S& I, ] differ=sqrt(temp1)/sqrt(temp2);
4 `) T0 s$ e/ n5 v return (differ);
$ b0 _3 }3 M7 v}</P>
<P>bool CGenetic::IsNew(CHROM ch)
" i7 t' O1 A( L& E# M# @) u2 [{int i;
3 b1 m1 R9 C  |7 |% w bool IsDifferent;
IsDifferent=true;
! D3 d+ m) J& m2 x0 q for(i=0;i&lt;iBestNum;i++)
+ U0 T# ?) `7 e( s# T& r  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
$ s& a8 \# I; c  {IsDifferent=false;
) u3 n; W& P: Y9 h      break;
  }
return (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
) P( ~& I! P4 q- C8 `4 c int i=0;
double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
  j1 E) P8 H, Y- | {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
4 ?2 Y* f& A# }$ j5 s  L+ ^ }
2 D& Y* ^( Z  Z! d/ w1 G" u temp2=sqrt(temp2);
temp3=sqrt(temp3);
9 E* ?: N% T+ y' j7 J/ Q dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
/ d+ U8 a4 U2 i<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
/ g3 h0 m+ M/ p% ?' s! c4 j+ t# c6 F#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
6 B% P9 C5 V! q8 |double chrom[MAXVARNO];
( p& o, W' N+ |  y+ Pdouble fitness;//适应度
  t1 @" |( R3 z}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
. n5 H$ C+ o% a8 L) xpublic:
bool IsStoped;
double dblAngle;
2 r, p# `1 }- ]5 f- q1 w# | CHROM best;
Mm mData,mResult;
" t' x* ~4 K/ u: G double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
% \! T) b' W+ v, A9 u  v5 H2 G! q1 t int iBestNum;//符合条件的染色体数目
* n3 o: J5 g4 i$ U  a CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
* o+ O/ ~; k2 o5 l- g7 n: ^ void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
  z- A2 ~* v! c8 w. H8 ` void statistic(CHROM pop[]);
5 \; y/ f& f# Y9 p% N2 r CHROM bestchrom[MAXBESTNUM];//最优染色体
: h# ^' m5 H5 s$ Z% g bool begin();//主函数
void generation();//一次进化
int rselect();//轮盘赌选择
: p  ^( z" W: X8 ~  N/ [& P& F CHROM newpop[POPSIZE];//种群
$ g% L' v' V' ^7 n; R* u, o! _ CHROM oldpop[POPSIZE];//种群
1 p$ @4 d+ b6 m' `7 D double pmutation;//变异概率
- t0 @: Y1 z, g! `6 _! D double pcross;//交叉概率
* U0 P& K# e/ s long maxgen;//最大进化代数
int iVarNo;//染色体数目
4 [- K( t- Q: M4 b+ S: e double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
$ C' G* ^; L6 D) n* [, |" P* b; C<P>private:
6 i9 {% u+ Z$ g& e3 _. C double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
  w" f  r, k9 f void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
0 O- e: e3 v7 q5 _+ x) f4 J5 x# R; S! A bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;
9 v8 m% a6 W4 P" v; Z0 i; S/ q
};</P>
8 r/ b+ C% B7 ]/ h<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

7 D6 D) Q, w) j0 U</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>
/ B: n2 @( F* u) k4 E" J( R/ ]+ v* F% U<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>