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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
' Z( U5 S& M) ~. M% n//
//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
#include"math.h"
+ i; \9 X7 a/ Y, T  K#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
) W" U; }, l4 N" ^2 s#endif
5 Q, O1 p* k) p; E9 ]* L/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
0 ~! k. h- ~  l9 ?' w- j, x* e// Construction/Destruction
' |/ w! K& `' v//////////////////////////////////////////////////////////////////////</P>
& n3 Q% K% C4 [( F; Q% T& J<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
8 l& _( r" S  w$ J; q1 P# e7 U8 C2 j0 ] pcross=0.9;//交叉概率
- D2 ]! W* S( P2 g9 M maxgen=5000;//最大进化代数
* N3 p: j( b4 ? iVarNo=0;//染色体数目
sumfitness=0.0;
# K6 \2 i+ a3 B0 R7 X gen=0;
  E% l6 \( W: T7 W8 Q" r IsSetScope=false;//还未设定个变量范围
IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
; j# ~$ T; Z  a dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;

% c" X5 M4 b3 r8 o3 j  o initM(MATCOM_VERSION);
}</P>
<>CGenetic::~CGenetic()
{exitM();
}</P>
& u9 R9 K" W% e) g<>int CGenetic::rselect()
. s) O$ c* }- {{double rand1,partsum;
int j=0;
! f9 Y" G) W, ^0 \ partsum=0;
rand1=rand()*sumfitness;
do{
2 L% R9 k& Y- ~9 O  partsum=partsum+newpop[j].fitness;
' [, o  K) A/ _, K! X! E: F  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
" f3 ^4 n& m" V0 E1 ^ return (j-1);
+ u9 S. G/ W  X) a5 {$ V}</P>
. M! L0 |5 L" f- z9 }<>void CGenetic::generation()
{int i,r1,r2;
+ _% `$ S8 @" X% x3 q CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
6 l$ c$ F3 o3 |3 a    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
1 e: `. C4 W0 \8 k$ w. o, E, |  r2=rselect();
5 {9 R/ A/ y4 v( s+ ?& m: }. O2 L  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
}
; r( ]+ j3 N* s( j& F7 L //从1到POPSIZE循环，对newpop进行变异
3 M  P% Q. S+ N6 ^8 A    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
<>bool CGenetic::begin()
{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
* u; `4 A* T0 T! Qfor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
2 i% W1 a6 ^% d* A  break;
2 _  l% N0 ?1 j! T9 Z if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
7 M/ j8 Q5 S+ L1 j% V  u return(false);
7 @( a+ `$ E6 M5 N1 C9 C. _ }
if(gen==0)
. S6 p' N! }6 {* u6 T2 a8 o  init();//如果刚开始运算，初始化
generation();
gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
3 X- p+ F. y$ p :ispatchMessage(&amp;msg);
/ Y( \! B: {& Z0 c8 m' e3 @/ f msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
<>return(true);
}</P>
, o5 W8 G& }$ A$ l, H& y<>
9 G5 k) d" [" z+ P8 z* {void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
( _5 f7 j) X, t- M int i=0;
3 g& E6 T: ]8 J5 J//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
1 s+ t  A: v+ ~) V' ~0 f! [ do{if(flip(pcross)){//交叉概率
c=rand();
    for(i=0;i&lt;iVarNo;i++){
oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
# m. @$ q9 f8 W8 _( e7 F oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
$ p5 r8 j1 `8 d0 B& e }
! l; }+ ?3 p+ o7 \6 O% D' Y else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
4 E4 S8 P! ~% j( n8 P/ a  oldpop[iPlace+1]=chrom2;
1 V1 j5 _! z% H2 o6 b }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
( A$ P6 o# E3 L! ]+ r3 \<>bool CGenetic::flip(double possibility)
0 J+ S4 E+ |8 Q; J: z{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
4 u, n  X/ O  l9 s1 y' s' z return (true);
" ^" f+ R3 {0 ^else
" g; O6 |( z4 g2 H return (false);
}</P>
7 l+ s9 e4 a0 P- i<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
8 ?4 ^9 w* |2 M) f: U  o int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
: k5 S; p6 [8 _  E& m8 Q  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
+ i( R4 O0 `1 g8 v; `9 N         for(i=0;i&lt;iVarNo;i++)
% I. N: A4 y- `2 V+ c! o; o9 u    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
; U: @- G1 b& T6 e% d# j          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
9 y7 s7 p8 o2 h" i7 X4 _) ?8 a     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
}
else{
/ r; U" C/ R+ Q) p. t  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
9 d1 V3 N9 F! d( D for(i=0;i&lt;iVarNo;i++)
8 j3 ^2 P" j. R$ Z1 _/ T  chrome-&gt;chrom=temp2.chrom;
2 o5 |  J0 W. v% I}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
* S* g2 e3 `( l sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
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))
  bestchrom[iBestNum++]=pop;
" D# S. o% R1 \ if(pop.fitness&gt;best.fitness)
" Q3 n: @, S- ]7 R0 v# r  i* `  best=pop;//纪录最佳染色体
}</P>
<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
# i7 S3 ]6 ~% L5 a& R0 G<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
- f- D& o4 X0 N' `9 k for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
1 K0 z2 I& v7 ^# _3 Q( ]' A/ P  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
6 x* p+ x5 l, m  n5 N3 E" r        oldpop.chrom[j]=newpop.chrom[j];
: Q- m- H& T) m% \9 n }
}
& B" \9 h& {; A. G) r$ l}
4 x) `: X, T6 p; S else
( y7 d( j! ?, ] {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
0 x3 p6 X4 R$ b$ Y }
/ S' T; S3 g# Z}</P>

& E" T+ f% `0 S% c: T<>double CGenetic::randxy(double x, double y)
" ]' Z7 P, Z% ?* e8 W/ ^4 j2 S* i{ return (x+(y-x)*rand());</P>
<>}</P>
- W1 \. u4 i# {+ P9 f( J) ?<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
( }; }: I& f6 N/ P& m. E{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
5 o$ p4 O6 `2 J: K2 |9 C int i;
for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
$ |% K4 c- X# F: X$ C mResult=bpnet-&gt;simulate(mData);
  U1 `# }) Z5 d* R& @ dblResult=mResult.r(1);
return(dblResult);
$ A/ J& n7 H% m* y& W) d" C}</P>
3 j; ^" J+ O& }5 A
<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
' `6 h4 B* ~5 _7 ?* M8 ^ for(i=0;i&lt;iVarNo;i++){
: ?0 B. D+ l. i7 U  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
3 T) l2 s- t8 ]! _( t- Y% f  {IsOk=false;
  break;}
+ N7 R8 h/ v8 M9 G3 b }
return (IsOk);
# `0 x$ y0 C+ U( p- X( ^9 x/ J5 z}</P>
0 d; X" [# U+ z9 x
<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
6 {, g3 J- w) {6 W  ~( K/ I" O int i;
for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
3 j- {5 J: ~8 s2 J! K0 \, e4 J  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
+ ?  \& @( e) _* y7 g+ c* _  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
- l7 W/ o0 ~! h! U  temp3+=dblTemp2*dblTemp2;
# s6 K$ T3 M  U; I* K) X }
" S/ @6 D0 i: {' B7 k! r/ [ temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
+ }  {! Y! O7 m* \5 C return (differ);
}</P>
6 T+ E9 l# \; {& x! G<P>bool CGenetic::IsNew(CHROM ch)
+ \/ ~/ }! [3 N1 Y* N, p{int i;
- d. N9 W5 [- _5 j# R/ x' ` bool IsDifferent;
! g+ p: W9 U0 C% t, @, E IsDifferent=true;
8 ~" v; [% V0 G/ h+ t- P4 `: @; ~ for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
& G7 C% U; B2 Q2 ~  C' w) ~  {IsDifferent=false;
      break;
  }
+ }9 Q4 [8 T5 ~; ?5 x0 T, }return (IsDifferent);</P>
<P>}</P>
+ i; u8 i; x. q<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
- ]2 _# F5 v. M" P% o+ U# z& D{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
. X0 R4 b% W, _ double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
' }" d/ H' p# v0 B  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
- x+ h& a5 h: k; `% J8 K  temp2+=dblTemp1*dblTemp1;
9 v' [% k, w% g& D( k- _8 e8 {4 \% v* ]  temp3+=dblTemp2*dblTemp2;
6 i9 O; U7 k$ B7 u& l }
) L; ~- @8 N! e; S+ c6 ] temp2=sqrt(temp2);
$ X( n/ R3 ]2 b  m, m temp3=sqrt(temp3);
% |' G- E6 F4 a$ h8 F4 Y" ?* O/ @ dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
angle=acos(dblCos);
: w( B5 p' @3 y angle=(angle/pi)*180.0;//转化为角度
* L4 J% ~) l  y+ Y3 ] return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
' F- Z0 X* s% I* @//////////////////////////////////////////////////////////////////////</P>
; |$ k  i% y& F2 V<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
$ N! d8 m6 O( b0 w# x( `$ ?. V3 I* ]<P>#if _MSC_VER &gt; 1000
1 I5 |% m! s7 ]+ e3 h#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
, P1 I9 Z5 Y$ q0 D( i( xdouble chrom[MAXVARNO];
, q3 v, s3 [% O/ Adouble fitness;//适应度
}CHROM;
#include "BpNet.h"
  i8 X0 c) G5 L1 U/ K////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
/ ]& d/ ^; j1 w$ N8 N' Wclass CGenetic  
9 A7 e; j) |' i{
- [  H- A# m/ J; m* u0 |2 ]( Xpublic:
  ?+ ~7 N8 w- ~. }) Q  ^! q bool IsStoped;
: j# q0 A5 B) s/ ]. C0 a double dblAngle;
CHROM best;
/ c/ B! t# h" p' n5 G1 _. ^, J9 U Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
% S2 E7 f6 }3 M, E# y1 `: t* D CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
* Y1 U& o% q& h5 v void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
. N5 m( O3 F! @% n' j: A! v double randxy(double x,double y);//产生x,y之间的随机数
6 h& d% P  `3 E5 q( ? void statistic(CHROM pop[]);
1 B7 j. p% n5 o( K# e# c0 Y2 \" b CHROM bestchrom[MAXBESTNUM];//最优染色体
$ i& S( _% w6 _  B bool begin();//主函数
7 Z1 x9 e: \; D; j" x5 ~ void generation();//一次进化
int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
$ U. g! S% h. |$ P double pmutation;//变异概率
6 I! m- b& A) ]5 x double pcross;//交叉概率
5 b, M; G2 D2 I+ ?3 D long maxgen;//最大进化代数
int iVarNo;//染色体数目
& N7 ^5 {* l2 E% O% f double sumfitness;
& I# ~0 m0 O' e& p CGenetic();
3 B/ s& @7 Q/ t: R: G virtual ~CGenetic();</P>
  ^, V* G) ^  l$ u2 s<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
9 E6 {% s) }1 O# s* D2 v double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
2 c: ?0 N5 _) w6 m- }7 G$ a' Z double varminmax[MAXVARNO][2];
6 }9 ~1 M0 @- A void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
! N: R4 w- O# L+ x- G/ U5 e6 n //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
( D  d- ^5 l& i+ ]5 g7 D- u2 U0 \ bool IsSetScope;

};</P>
<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>
. Q# q# K' |% L<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>