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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
& m1 F. V5 L; u- u//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
#include"math.h"
9 b- k( s, ]: H3 r! c4 L) d- S#ifdef _DEBUG
$ V) S: h) X, e( T#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
3 e! f, W0 b% B#define new DEBUG_NEW
, o6 _. ?: {$ f8 r7 [& Y#endif
5 P3 i1 e" i9 O9 C+ S1 N+ V# n/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
6 N; i# A* h- V//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
- ?& m  L. V3 V+ n" i3 C pcross=0.9;//交叉概率
! _. q+ W7 b+ |+ Y; \3 g) r$ k: f maxgen=5000;//最大进化代数
, g  z3 I! i' ?; s7 F! g0 l9 A iVarNo=0;//染色体数目
7 n/ H& c5 r4 u6 y sumfitness=0.0;
gen=0;
0 Z1 o, R- S( `. \ IsSetScope=false;//还未设定个变量范围
IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
: ~# ~5 p+ K8 p6 J dblCre=0.0;
' B5 A. Y* j# L0 d, ?+ t dblDifference=0.15;
best.fitness=0.0;
: f  ?& d% M& n' H. `+ k
( m  c# M2 q& c3 a* g+ Q7 L( ^ initM(MATCOM_VERSION);
4 X5 y2 i0 A( L) c }</P>
- v( D/ V: s3 @5 {- j4 T<>CGenetic::~CGenetic()
( l; M% v6 Y: I! w0 j2 U{exitM();
}</P>
" T1 l  `% n& m; h$ O) g3 {: ^<>int CGenetic::rselect()
) C# H* p. q4 Y{double rand1,partsum;
int j=0;
partsum=0;
2 K+ \6 S. Q2 a4 `7 l* B. b9 _ rand1=rand()*sumfitness;
9 q6 c( c7 R0 X( \5 y+ E1 Q do{
) ^% s$ |2 ?& ~' R  partsum=partsum+newpop[j].fitness;
  j++;
, [$ S& p, a3 l }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
8 C4 x9 {: D( F' E' G0 P return (j-1);
' B) H5 `  Q! f; i6 t}</P>
<>void CGenetic::generation()
! p! S' \+ k3 s; k* c: ]! y: g{int i,r1,r2;
+ r5 V6 b: F* x. m% v, [" `" w: P CHROM tempChrom;
  L$ x, i5 D) T, D //进行统计，计算newpop单个染色体的适应度，选出最优染色体
" |) e4 I0 g# d4 ]* I" f statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
8 {' C4 G$ s- A2 w  r2=rselect();
4 i+ `9 j5 [. K4 t; O  cross(newpop[r1],newpop[r2],i);
}</P>
* [( b1 Z7 B. {/ a( B8 s<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
1 v& ], r$ n8 F- l  tempChrom=newpop;
1 H/ m7 [( r3 Z3 x5 W6 r  newpop=oldpop;
- k6 C$ @. m( d  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
: I. {8 g: P5 _+ m$ x}</P>
<>bool CGenetic::begin()
; [' }8 |* P9 G' g8 A{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
/ v; ^  {; V: O2 T$ vfor(int i=gen;i&lt;maxgen;i++)
; C" L* H5 d8 d{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
}
: [" j* E' l# _, U4 O if(gen==0)
  init();//如果刚开始运算，初始化
. q: ]) M! c- M' ] generation();
gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
0 W7 e5 ?3 ~/ u :ispatchMessage(&amp;msg);
& {' l- b7 \8 S msg.message=-1;
. x$ D5 R9 t+ s# e9 x9 O  A8 I! J :ispatchMessage(&amp;msg);//这样可以消除屏闪
! ]' D8 d( I' g}</P>
& |% p' I6 H5 Y<>return(true);
}</P>
3 D! _3 t2 W5 G$ y2 f  F<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
, R2 T" k# z1 t3 @( D! D+ m0 ]//循环，直到产生合法的新染色体
! i# P$ A5 |! E: t; H+ V do{if(flip(pcross)){//交叉概率
c=rand();
9 c( Q: X. H8 V, @    for(i=0;i&lt;iVarNo;i++){
/ B* T5 e; H  K, O8 m! f oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
% y0 E  [/ c, d7 Z. ]$ F! D oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
}
( a  O+ ^4 r& O+ U) Z else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
}
) L# f/ Q2 [/ V% n}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
8 E3 ~9 T. l, ?3 X' x# X<>}</P>
<>bool CGenetic::flip(double possibility)
  q9 T) m8 x  F. ?2 p{double ppp;
! T) ?5 ^( y$ @9 tppp=rand();
if(ppp&lt;=possibility)
! u" B( |0 k8 m, f; t return (true);
else
return (false);
. G( B! k+ E% o}</P>
$ G$ ~+ V9 `! I<>void CGenetic::mutation(CHROM *chrome)
2 b3 \; T3 ?" J{double m=10;
  n3 P7 E5 X6 C" O int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
! K& f3 o+ `/ q6 ^' X! J8 g6 D  F          for(i=0;i&lt;iVarNo;i++)
8 ?* o0 t# i% m& j6 ~     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
: q  Y2 g4 ~4 j( \  @; _0 I  }while(!identify(temp2));
3 J$ R& L2 y6 ^+ } }
  J6 W$ |. L5 ^- t+ B9 M else{
  for(i=0;i&lt;iVarNo;i++)
! Z7 I$ Y9 y/ A2 l- c6 |     temp2.chrom=chrome-&gt;chrom;
}
+ @0 L5 w; a) u. R0 B. G8 _ for(i=0;i&lt;iVarNo;i++)
" }8 L. w7 J$ l* I$ R2 v  chrome-&gt;chrom=temp2.chrom;
}</P>
7 b$ T, G- `# C/ N- H<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
' b- }4 |3 [7 b% u: o6 s0 W% X1 B //循环，计算单个染色体的适应度,以及sumfitness
) c" Q2 O/ v) D/ q- i for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
% h4 w4 D( ~0 j- _, D: {   sumfitness+=pop.fitness;}
7 N' c, e4 m/ V //选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
% k1 `6 {) ?2 P; p9 K& r/ I<>}</P>
0 W4 l* I  Q1 }/ J6 v% H% c<>void CGenetic::init()
5 w  ]) b6 S( |{//对种群进行随机初始化
  H. Z  C! _( c  i# e$ Nint i,j;
srand( (unsigned)time( NULL ) );</P>
+ u( K9 i1 Q+ [; G# j/ W<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
4 D) g7 [4 B3 n6 d5 B' [* m for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
2 v. S+ @) p! Z  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
0 H* l' e$ F' b; \. _& k" ^        oldpop.chrom[j]=newpop.chrom[j];
5 ?  f- u; i" P. P- t9 i }
}
! o: D6 ~4 z' z}
; K+ ]: ?! Y+ _/ i" `" j else
- V+ F. D: Y9 j! _$ C8 E {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>
& E0 Z3 P( J, ~1 I$ A. i7 M' u
<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
3 U9 y- N1 ^0 l: `& S2 o# l" V; d<>}</P>
6 \' @* h& f0 q3 b- D<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
4 c1 C& q: E5 Z6 f, Rfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
* u$ P: v5 z/ q6 B* H  m: yIsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
6 |# d+ ^! y0 W5 S int i;
for(i=0;i&lt;iVarNo;i++)
5 N0 e' {5 Z3 a7 `$ F5 }3 `- t  mData.r(i+1)=chrome.chrom;
; D# |% f& J1 r- o mResult=bpnet-&gt;simulate(mData);
5 s7 i; `, t  G% j dblResult=mResult.r(1);
* {- z3 L/ b! _ return(dblResult);
}</P>
0 U; O* [0 S  \. @' c
<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
. m8 k( e: o4 Y  Z% H( T bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
  break;}
+ h& B; l+ a& r2 o' ]+ ^ }
+ S9 B, I5 x; a' f1 A, C1 `: x return (IsOk);
}</P>

% b+ p, m/ T5 w# s# M) P& Z<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
, I* y4 a( C& r% u0 M  C  D int i;
4 {. G9 T! H! e/ I2 Z5 n for(i=0;i&lt;iVarNo;i++){
* }& X5 h6 V5 _& v7 Q; H  I0 B  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
3 d3 v, a4 M1 D/ v  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
9 I" d4 M* F$ z8 d/ k  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
5 k: Q( Y  U! f- d temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
, P2 g. [5 C) e( N# g$ f+ C differ=sqrt(temp1)/sqrt(temp2);
return (differ);
# O; ^$ Y8 D# s+ h- ^}</P>
' {9 ?2 ^  P* z6 ?<P>bool CGenetic::IsNew(CHROM ch)
{int i;
+ y/ p& q9 j9 _1 L/ K) z% N bool IsDifferent;
; U+ V- m: I7 V+ @, ^5 j0 Z; j IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
  }
4 j, @. V' J$ A3 Kreturn (IsDifferent);</P>
# L9 o  u( O" W* g<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;
int i=0;
double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
$ Y' U6 I% A. w {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
2 B7 I$ W) W$ R% l8 n5 ^2 j5 n  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
+ {% |5 `6 N% |' Z  temp2+=dblTemp1*dblTemp1;
) A! J4 Y; p1 z  temp3+=dblTemp2*dblTemp2;
+ F8 C3 v+ K$ d2 f3 j }
temp2=sqrt(temp2);
temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
" z8 J7 T+ f, n' j/ i+ L' e% Q" N angle=acos(dblCos);
3 @" a5 E. _3 p% y angle=(angle/pi)*180.0;//转化为角度
( o5 W5 t; ^' c1 A return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
2 {6 W+ D+ Q5 e/ k5 O7 \<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>
% A3 X) W, Y& h7 L" X! `) p: X! H<P>#if _MSC_VER &gt; 1000
#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
double fitness;//适应度
' v. k5 Q+ v$ }' T! a7 H}CHROM;
#include "BpNet.h"
9 L  Z, V6 G( G& a9 e( V////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
+ O5 y0 L/ s9 F4 Q4 v{
public:
' y- m# f' N' d bool IsStoped;
double dblAngle;
CHROM best;
Mm mData,mResult;
4 \( E; l5 J; ~/ \ double dblDifference;//差异〉改值的染色体视为不同
, p* L4 J8 B( b4 d3 ~: O- a9 u double dblCre;//适应度&gt;改值的染色体符合条件
" p0 f1 v0 J$ t. P int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
" P% ^0 `* n5 C0 R //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
" G9 Z2 L$ K' v. S' w! P5 T long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
6 [* p! J. f  e+ I/ P- P- a* K double randxy(double x,double y);//产生x,y之间的随机数
8 U' x3 r. w  | void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
void generation();//一次进化
* W% ?/ N' l$ `: L) G2 r int rselect();//轮盘赌选择
! d- r1 X/ e/ i# P  ?6 p. i5 _ CHROM newpop[POPSIZE];//种群
5 M4 u/ q6 i) v CHROM oldpop[POPSIZE];//种群
  ?$ ~& h* `& \' T5 U double pmutation;//变异概率
double pcross;//交叉概率
& I; |! c! B1 q" [2 _ long maxgen;//最大进化代数
int iVarNo;//染色体数目
7 _' Q# k) ?! q* q+ | double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
2 K/ D) l, z- Y- ], k/ Q<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
3 o, u8 F, _# u# t! D) C! Q2 | double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
& R/ P. G! y. I* U3 Z3 \ void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
  h1 R( S: ^; D8 Y! b bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;

( O# N0 N7 d/ m2 |# `0 t};</P>
( J; j$ R4 G  i3 J7 y8 S  x0 @* l<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
# S! u- b9 m' j+ |$ ~
</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>