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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
; q7 x, z1 E( G! P6 ~//
//////////////////////////////////////////////////////////////////////</P>
- Z5 r* u5 T5 n$ o<>#include "stdafx.h"</P>
<>#include "Genetic.h"
; n, w" X  i. Q; H#include"math.h"
$ _, A8 d* y  T5 m# `#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
% V& b/ T7 Y6 V% W#define new DEBUG_NEW
#endif
' F# i2 b# n! @) |9 K. ?( X/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
4 \2 z5 g6 W' n" M  y<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
9 I$ v" k$ s6 h- b' P# ^1 A maxgen=5000;//最大进化代数
+ Q3 F6 P, g) }) s iVarNo=0;//染色体数目
sumfitness=0.0;
* ?& X$ }, a! C$ n1 m gen=0;
IsSetScope=false;//还未设定个变量范围
: \" Q' _! \" w$ M IsStoped=false;
  F% ?0 u9 }& d& f3 f4 u4 Z for(int i=0;i&lt;MAXBESTNUM;i++)
( N9 l4 }8 ^5 ]   bestchrom.fitness=0;
" B* d; Q8 `7 g& n* w+ k. ^/ X iBestNum=0;
  R3 J2 m! R% z dblCre=0.0;
% V/ {5 ^6 x) v( q- P' H; ^/ m0 u dblDifference=0.15;
8 Y% h; c$ O/ D( R4 k+ e% b$ a best.fitness=0.0;
$ W3 i5 H  t) t- n
8 l; H$ u5 I5 P5 c% t initM(MATCOM_VERSION);
}</P>
7 Y$ q, G4 {( d6 g<>CGenetic::~CGenetic()
{exitM();
}</P>
. `- K. ~3 E/ S. n$ f<>int CGenetic::rselect()
{double rand1,partsum;
- H6 _7 D9 d- }1 A: Y/ Q- I/ G int j=0;
/ \- ?3 L4 V1 X  t! U+ [. M; d; \, A partsum=0;
9 l( @8 b  t. A( o rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
4 ]9 X1 S/ F2 a. Q  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
& P, M4 u# V- F) h" `2 H return (j-1);
}</P>
<>void CGenetic::generation()
, D$ G  U, X; L{int i,r1,r2;
# I; S; j3 F6 D4 d9 l. k& \ CHROM tempChrom;
* }9 _4 l: E/ b! w& ~ //进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
( X) D- o. d0 ?) N! K2 y //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
; @" J! k, D. t  ~) m    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
( \/ f) H. z, D* E5 y  r2=rselect();
- A( F2 Y; |0 {' S4 P7 Q1 B  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
! p' B( E& Z) w) I- |8 `  newpop=oldpop;
  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
* b" O# g. x: |8 U  q     mutation(&amp;newpop);
8 ^" O. b4 s1 B, @  K}</P>
<>bool CGenetic::begin()
{MSG msg;
! D! `0 \( `6 m mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
; s, D5 G1 E) N if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
+ L) ^2 v" T/ p+ v. c return(false);
}
8 I+ B) k8 m, j) m: Q if(gen==0)
  init();//如果刚开始运算，初始化
0 ]) }1 b& g" P5 Q  a, T5 M generation();
gen++;
2 t# B/ F; F- K' A+ F3 a //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
- q* `3 B; J/ ]( u0 j$ n :ispatchMessage(&amp;msg);//这样可以消除屏闪
/ \! u  e9 t- }- J$ s, U( o}</P>
<>return(true);
9 A: M) a1 \6 Z$ F}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
9 W3 H9 f% f8 m$ `//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
* _$ w# O; N0 M% n% s do{if(flip(pcross)){//交叉概率
) D* [% n4 s0 j$ Z7 {! W0 a* y c=rand();
. A& T7 K$ x( D  S3 v4 j" p8 B    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;
}
}
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
) U2 u+ H( ]9 E' @ }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
* L# \  V" m% B$ O$ w# w<>}</P>
<>bool CGenetic::flip(double possibility)
* G& G$ e* C2 Q  R{double ppp;
! t& j& P4 s' X2 o; kppp=rand();
6 A6 M& {; C: ?if(ppp&lt;=possibility)
7 n* f* P5 r( H+ r( m; D, M8 r return (true);
" ]  a( _6 o! T& Gelse
' R) R& m0 }' y return (false);
}</P>
6 B, B8 M& t( p, [<>void CGenetic::mutation(CHROM *chrome)
) m( H1 P0 Q' X  q8 ~{double m=10;
int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
' Q) v: P8 p, X5 p  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
) P4 f! f9 ]- n+ R% K2 R         for(i=0;i&lt;iVarNo;i++)
    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
) s$ n3 J5 \+ @4 U8 ^4 r* W     temp2.chrom+=m*temp1.chrom;
8 l; {  m( M$ l1 f+ y- `    if(!identify(temp2))
+ ?  Q- r1 J: D# S3 G( H     m=(double)m/(double)(2.0);
+ S' a4 \/ z0 o: {9 y( s$ T  o  }while(!identify(temp2));
' N$ |& J! _0 c2 h }
. Y! I2 ~; i6 q* P else{
  for(i=0;i&lt;iVarNo;i++)
* s  H  e$ y$ x     temp2.chrom=chrome-&gt;chrom;
: r/ C/ y5 V9 G- d5 t: Q( b }
, T% j9 @' s. e# e5 N for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
  t( b, u+ X; ]* T1 b( r% K<>void CGenetic::statistic(CHROM pop[])
) r+ z7 S3 g/ K* r; b7 r- p{int i;
$ ^: ^5 F7 @( J  F. p( K) W sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
, V- `9 z5 I8 Z, k; \, I7 Q for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
5 T* A$ o. P, e% D% r$ [' V) A   sumfitness+=pop.fitness;}
//选出符合条件的染色体
% j! o& l" E( n6 f" d for(i=0;i&ltOPSIZE;i++){
2 a( U, a( G) ?5 n% z: e8 l if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
) R7 ~+ T1 ], q. Y7 q+ U  bestchrom[iBestNum++]=pop;
' D8 r- }/ Y: W( ], W4 }. T if(pop.fitness&gt;best.fitness)
6 F! Z  `  a: z- t0 @% f  best=pop;//纪录最佳染色体
( e: t% b  j6 h' d9 V8 L+ Y}</P>
<>}</P>
2 Q9 U. z. s0 T7 y! b<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
* S6 N' Q0 H! bsrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
+ i$ d0 A$ I( [, U3 ^  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
( {; ]  Z: N* n. v$ @        oldpop.chrom[j]=newpop.chrom[j];
) L: V3 T$ w% L8 m: g5 A }
. z/ x4 Y& f. U/ r}
}
else
! t" P+ u( L3 d+ i6 l. P {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
& @6 r) f8 d3 H8 P  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>
5 }0 N2 f. @: {3 z# ^. F4 ]+ |
' U2 W* m$ q, F. M! `<>double CGenetic::randxy(double x, double y)
! R" L& Y; e6 l, F, @" l{ return (x+(y-x)*rand());</P>
<>}</P>
* h* g2 n1 d- n6 p9 O5 ^2 O* N% G! F<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
' W: M* A' i. `; U( l1 i: a" L& S{int i;
for(i=0;i&lt;iNo;i++)
: c0 j$ T7 Y( N0 P) o6 e{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
& E  C" F6 h) [$ b6 k5 A}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
) a/ e( m' k; I' y1 n4 C5 U, ~{ double dblResult;
5 @% M# I, C: Z. h5 J int i;
for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
4 j8 B8 k3 `3 ~7 c  i& a. @ dblResult=mResult.r(1);
- s( C7 o( j1 K% b* S& B9 e return(dblResult);
, x+ |4 L% e  ^4 v" f. ]0 q}</P>
% o5 W5 i, ^" h& u
<P>bool CGenetic::identify(CHROM chrome)
* D# F( A7 i- z{int i=0;
bool IsOk=true;;
0 s. ?  O& |, }3 u4 V0 E for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
4 J9 |# m2 f& x3 r  break;}
}
8 m$ b  K, L2 K; o2 u# ?" _ return (IsOk);
}</P>

4 u( h. S* F( [! l9 C* V2 j$ b<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
( q, s3 }5 d% S2 q" _ int i;
for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
# k+ Z# _; W. U% T; Q5 W  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
2 m3 m3 d" ^9 n     temp2+=dblTemp1*dblTemp1;
0 z' a( J" p1 {1 b/ t' }  temp3+=dblTemp2*dblTemp2;
}
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
3 X% z" z9 n  y5 w2 n differ=sqrt(temp1)/sqrt(temp2);
return (differ);
9 R4 L& S+ d& \}</P>
5 s& e9 u0 f5 m' c) E* u& W" Q<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
1 t& V  e% C% X4 H6 c% m IsDifferent=true;
& Q, B! G) K! Z3 P3 a for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
  }
1 `6 G  S+ `$ s2 nreturn (IsDifferent);</P>
/ N% e7 M8 l5 `+ [6 k' B* O  R& A<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
6 g  H4 e2 j4 I  [$ f7 ^{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
double dblTemp1,dblTemp2;
/ G  ~; w/ S/ D" ~4 y( T4 i for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
4 V, f* A* x$ r+ b' t* N  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
: R, `( L+ P% C1 H) i9 r  temp3+=dblTemp2*dblTemp2;
+ I" W3 K4 \2 _1 Y( f5 ] }
temp2=sqrt(temp2);
temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
' W3 ~  J) m; C' l$ N+ i pi=acos(-1.0);
- [1 k# g0 P: u3 M! a( K$ _ angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
/ t% {! x; Z. r0 u) M return (angle);</P>
, x: }* \" v% ~% E- }<P>}</P></DIV>
! D3 l( ?8 L7 Y5 g$ q3 l: \<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
. q$ Q2 G! c) l3 s$ r( Z0 u* C8 a//
# i! \- @$ B& r3 Y; A% O" B9 k//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
0 _  N: q: m) f2 b7 b- l+ y$ {#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
) q! k- ~- U" L2 i<P>#if _MSC_VER &gt; 1000
6 R* C; p6 J, Z# E4 |$ U) C. v#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
double fitness;//适应度
9 {* q0 m7 M" e& J9 I}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
8 x+ d$ Y. z' I; `class CGenetic  
) q; v' P1 G4 ^9 N{
0 i3 C! V8 v4 e1 O7 ~2 Mpublic:
bool IsStoped;
/ v' s' }5 r9 U2 ^! Z; p& n double dblAngle;
CHROM best;
# s) J" C/ d; B3 O' r Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
4 L7 G" b( _% B5 ] double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
5 B7 d+ F5 d* a- M2 F% j CBpNet * bpnet;
; f  f9 h# ]( N8 i( w/ m/ r //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
/ A, r" x! r" @& R+ x( Z long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
. p  [" b/ R1 a. w% ^9 }1 m8 c5 V# \ double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
4 s4 i  C- d0 a' X; W/ X bool begin();//主函数
void generation();//一次进化
int rselect();//轮盘赌选择
7 W7 t' p, }; p  `7 ?6 P* K" I. W CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
* w- Y2 M8 Y+ d9 y* b" c7 m1 l double sumfitness;
/ ^  J: Y9 T) k. q7 N CGenetic();
virtual ~CGenetic();</P>
<P>private:
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];
void init();//初始化，设置初始染色体
2 |: A/ x" |# j8 S2 e# x void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
4 e5 D; h# W% c& V* d: i7 R, w/ p //交叉操作，iPlace指明新染色体位置
0 c" y# _8 e4 P- H void cross(CHROM chrom1,CHROM chrom2,int iPlace);
0 a5 P4 o( o5 K3 y bool IsSetScope;
: F% g) @3 P4 C7 X
};</P>
<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
% e. P6 z3 K$ u" V. B; ~# ?
</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>
) N7 u# I4 d/ z/ L  x* c. E. b/ S<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>