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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
9 C1 l" J7 {4 u/ X3 B/ U//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
0 w; ~$ B+ u/ W. e#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
- ?4 Z- @" o: p1 Y/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
  |( p# w. {9 F! @  w! `) r) n//////////////////////////////////////////////////////////////////////
' i" k/ O( @7 l3 `# B+ ]0 ?5 [4 _// Construction/Destruction
/ I5 Q& y/ O3 a. [( x& p//////////////////////////////////////////////////////////////////////</P>
$ O& N- c0 l0 O1 n. ^' m. d<>CGenetic::CGenetic()
# ^# g0 o9 y  F* ?) v/ k/ M" n6 n4 r{pmutation=0.01;//变异概率
0 I, [. ~6 Z# b$ g3 j1 G; O9 B/ ?) B pcross=0.9;//交叉概率
( Q7 k$ Y8 N% Z9 ~. z) c maxgen=5000;//最大进化代数
3 c% g9 \/ ~1 Y& o) W6 ` iVarNo=0;//染色体数目
sumfitness=0.0;
gen=0;
IsSetScope=false;//还未设定个变量范围
IsStoped=false;
3 U/ ?- u& {0 M5 q( G- ?, b9 G for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
( `2 x! Z3 S' x, m" o dblCre=0.0;
dblDifference=0.15;
7 ~' q( `  U8 W5 r$ A% L best.fitness=0.0;

initM(MATCOM_VERSION);
9 E; g: E8 h( I7 {# ` }</P>
<>CGenetic::~CGenetic()
{exitM();
}</P>
9 b4 V" R3 V: Z* Z) {<>int CGenetic::rselect()
( k$ U: v; q. X. d{double rand1,partsum;
3 L5 b& ?6 C/ e# w5 @1 A. _ int j=0;
, }& E8 G: D( B- R$ R partsum=0;
rand1=rand()*sumfitness;
do{
  ?# m0 s' d# v  P6 ~- B. F  partsum=partsum+newpop[j].fitness;
$ c0 Z2 j/ p7 b; Q  j++;
; u$ \0 c+ s8 j }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
! ^' Q0 b% c6 k) z5 U return (j-1);
}</P>
<>void CGenetic::generation()
{int i,r1,r2;
1 U; Z* r/ _, l2 E: J$ p- Y% e CHROM tempChrom;
& R! h. b" `6 ]' p/ {9 R$ _ //进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
* E; T5 ]; R0 w //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
6 {4 b4 U, D0 E- V2 K! U  r2=rselect();
. p9 l/ W* ?+ T/ O( i% P  cross(newpop[r1],newpop[r2],i);
}</P>
+ W: i7 S9 _. u$ {3 g4 J- b: p<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
4 U! \" Q" P" G, f" a' L7 `  newpop=oldpop;
  oldpop=tempChrom;
}
) A/ r4 j* Z0 Q( B //从1到POPSIZE循环，对newpop进行变异
+ x  p  E- N! Q    for(i=0;i&ltOPSIZE;i++)
$ V  o8 k: F0 _, Y     mutation(&amp;newpop);
7 ~7 E  N& @7 _. E$ w}</P>
7 l( x. ^1 d( J' m<>bool CGenetic::begin()
{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
/ R- |) L( K7 v! f( Afor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
3 |$ ~8 @8 s$ h0 L0 S) U9 h( s2 I return(false);
: h3 H& T  O  S! u }
* L) }/ r6 ]" o  _$ e) I if(gen==0)
2 j5 I3 O7 b  H  init();//如果刚开始运算，初始化
generation();
9 R4 y( Y# g" e: |  [; U gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
$ v3 s3 B* Q/ T  G: c: z9 O2 W) J1 J :ispatchMessage(&amp;msg);
/ F: Q" \* p& D. B; ~1 z, w msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
$ R: [' K9 l8 h: g6 P3 o6 A- D! f}</P>
1 i; o7 j/ u" [- z<>return(true);
}</P>
3 `; K% R* K; L& `6 C' M<>
# T5 E3 s2 n0 S* H: Xvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
2 _, e! Y3 X5 C8 g3 m2 H* s+ O8 O' f; o{double c;
int i=0;
% R* r: c* p& Q* n& H/ @//以交叉概率进行交叉，并对交叉后的新染色体进行判别
; a) G& ~5 m  K//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
) R3 ]' [2 c% h$ Q c=rand();
1 I# ~. I- }* r! u/ J    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;
}
}
( m8 o1 L. T6 R) V else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
' Z! N" Z6 J' Z }
& O( z* R/ ?' O0 z+ S}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
6 w/ d( C7 C0 F3 {; V; @2 e# N<>bool CGenetic::flip(double possibility)
" r& j. e( j( o& O- Z/ @4 s{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
return (true);
+ O1 J$ K. ?+ ^* `! \" C1 ^else
return (false);
: ^7 C* }! M' U( O}</P>
: N; v& m  V- Z* h( Z+ R<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
int i=0;
CHROM temp1,temp2;
* u: i8 H- E$ Z9 r if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
6 P( H) I, l1 Q4 `    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
7 H& `- m) @+ Z     temp2.chrom+=m*temp1.chrom;
7 A( b" U4 S" t/ b2 b    if(!identify(temp2))
     m=(double)m/(double)(2.0);
+ K% J' g* |! f: Y1 t+ b  l. B  }while(!identify(temp2));
' z$ Z8 k  S. M- m* ?6 \: L }
. }7 k8 i# e, s& M& g, u else{
4 h0 w3 O9 ~' k. q0 O  for(i=0;i&lt;iVarNo;i++)
' e0 d) f$ S& y1 D1 [* x     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
" G6 ^0 F4 P# v  chrome-&gt;chrom=temp2.chrom;
}</P>
<>void CGenetic::statistic(CHROM pop[])
8 k$ |+ z8 R$ F6 M+ F3 a{int i;
# }! |/ f1 l5 \, k sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
' s% ^8 f3 H" l( S 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))
3 B; `5 |3 I4 j, [5 z* r  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
& o2 y, d  B; ]: U7 t}</P>
; N' H7 `1 X+ j- @' K2 r<>}</P>
% m+ v  {; d3 j5 M<>void CGenetic::init()
{//对种群进行随机初始化
5 P5 P1 E+ b6 Cint i,j;
$ q, I0 V" N3 {6 j' ^8 x# csrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
9 l- |: U( _; o4 O  E{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
* Q* C. l, {. n/ D }
}
/ O0 J9 y) v! y: t7 K7 M4 n1 S: l7 [}
else
# S5 d( j! Z* |$ e {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
& A0 n7 w' B, P; n }
& N& T. f* B0 G4 b* e}</P>
+ N& ]* A$ x2 x- U4 U2 e8 p- v
<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
( E) i# y, m% \: k. ~( g6 t<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
, R! I& t( L; I* U! @for(i=0;i&lt;iNo;i++)
8 R  o, s3 `$ h& q& B{varminmax[0]=scope[0];//最小值
( D% `' G9 O' r0 U7 j% B varminmax[1]=scope[1];//最大值
& }8 w% z6 u+ M$ k! ~- v8 u}
  R6 a  V/ W8 _! \IsSetScope=true; </P>
0 E0 L. V$ ^$ d' f! L5 ]' m+ T<>}</P>
& u. y# V: |: x1 X6 F) T& g<>double CGenetic::CalFitness(CHROM chrome)
$ w" d  ?* S! s' [5 A{ double dblResult;
1 g, j6 L. d2 S! @; ` int i;
for(i=0;i&lt;iVarNo;i++)
3 G. A" u% I, l5 B  mData.r(i+1)=chrome.chrom;
/ e7 V, g1 M  g: k* d6 } mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
return(dblResult);
}</P>

! u2 y( {8 Q& p+ u; [, s<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
) u8 C0 G7 b: y) y! u4 S& b: v bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
9 H, U' V% M0 U% k- m/ ?2 w  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
  break;}
}
5 L1 T+ D/ X- C9 \8 q return (IsOk);
+ q! `8 r+ ~9 Z5 Y/ s}</P>
: k) g$ w: ?: W) F- Y
<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
  m8 c( J% R/ o- l* B. s4 O for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
/ q% |. E% p: c: B  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
8 ]9 o. o1 F& [; N  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
. C3 D0 g. P+ p. j* J' `" H7 ^  k  temp3+=dblTemp2*dblTemp2;
}
* n7 [. N- v# R" p( o8 l temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
, p( G5 h$ |4 K+ F0 v! | differ=sqrt(temp1)/sqrt(temp2);
7 F$ j: B% O/ V! ]7 l& j( _1 z return (differ);
}</P>
& \3 g3 U( V9 T! N5 D' Q<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
1 J8 G: @- F% p IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
! E; {/ d' Z: U  {IsDifferent=false;
' ^, j9 U2 U9 e+ g' K9 @. b$ ~8 O      break;
* r9 N1 H8 r8 s$ _4 f  }
' n7 @8 ^" t. k# H& V9 zreturn (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
- U; f& N/ F. h! e{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
# F1 N$ ?5 @2 g6 L$ f" |) d double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
) m% h" Y, Q2 w' y7 `/ A {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
4 O& s+ O$ r$ R" _/ T  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
temp2=sqrt(temp2);
7 C5 B. j+ W; ? temp3=sqrt(temp3);
8 K" z- N8 d. {6 y3 g/ j. ?: { dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
1 @2 Y& C$ g7 K3 p7 v angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
& J0 Y8 g% H% W0 M  K  K. H return (angle);</P>
<P>}</P></DIV>
* `' ?( e+ a: T; b" X* d<DIV class=HtmlCode>
7 v$ s( r! k  J" ~0 s# R) m* k<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
$ S+ T  C" J4 u3 X  o6 Z) O<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
#pragma once
6 W7 v3 j& ~* w1 H# e7 m- x! E5 J#endif // _MSC_VER &gt; 1000
! U2 W0 T8 w, G  T#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
5 b7 `! j' y" Ndouble fitness;//适应度
: O" b5 C1 a  v1 {) F+ x}CHROM;
#include "BpNet.h"
  F; X' D' M7 l% K9 E2 r////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
# W3 K" v& o9 ^" u8 nclass CGenetic  
{
public:
+ V0 Y+ G% ], y+ q; z bool IsStoped;
double dblAngle;
CHROM best;
Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
% m3 L0 z6 O6 }5 g/ o) K double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
! a/ D3 v7 b* O5 c4 Q8 _ void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
1 A" g3 }& P7 K1 u  l4 _3 w double randxy(double x,double y);//产生x,y之间的随机数
; H0 g$ [9 ?; o( l) G( V void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
void generation();//一次进化
* t+ B2 D: p" R4 {' y% ~ int rselect();//轮盘赌选择
! O' P! T5 f5 x! f CHROM newpop[POPSIZE];//种群
) j6 G6 p; T) d$ H4 i CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
7 z% y8 b' H7 v# ^; q3 B0 S& x long maxgen;//最大进化代数
! E1 `( j1 L# F int iVarNo;//染色体数目
double sumfitness;
CGenetic();
4 C( ]+ \5 z3 S* n3 a virtual ~CGenetic();</P>
<P>private:
double angle(CHROM ch1,CHROM ch2);
+ d0 ?% P* j. M bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
- p( U$ Q2 {" H9 u" ^' \* c void init();//初始化，设置初始染色体
, s5 W; X* J) p& k+ K$ y& D void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
* A: w* k- N6 g; \: G5 y0 k //交叉操作，iPlace指明新染色体位置
* v! p1 O- g$ t- J void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;

6 p$ D) w" C  I; _};</P>
<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

. x7 _* j: V: e  C; P2 I</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>
<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>