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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
5 _0 _$ e$ S! Y& W5 z) D<>#include "stdafx.h"</P>
# Y+ W# w9 ~8 d* ]8 x! g, Y1 [<>#include "Genetic.h"
5 |; O/ e6 m2 I, J! W. M% Q#include"math.h"
#ifdef _DEBUG
* k; \$ q0 b( o: |) ]" h' u/ a) e#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
! o% _) K1 ^5 K4 a4 U5 O#endif
2 m9 q  |2 i) c: t3 g8 s/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
' o5 P7 P8 m( T" g//////////////////////////////////////////////////////////////////////
// Construction/Destruction
: j& W  D& j3 f9 k7 L0 C//////////////////////////////////////////////////////////////////////</P>
& }% G( H1 A* Q' r<>CGenetic::CGenetic()
/ \+ c" D$ G: ~{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
* S8 ?8 g) n6 I  S: f/ i. j" y8 [ maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
) d2 W  e4 c6 ? sumfitness=0.0;
gen=0;
5 k2 x! C% Y9 c IsSetScope=false;//还未设定个变量范围
IsStoped=false;
. P5 g6 ^( b* M- I  f for(int i=0;i&lt;MAXBESTNUM;i++)
; v' ~8 V9 O+ ^$ ?   bestchrom.fitness=0;
* d. T" e; Z9 M, {" Q iBestNum=0;
dblCre=0.0;
( Z* C! V) \) K* c( x$ @9 i dblDifference=0.15;
best.fitness=0.0;
9 }1 n2 d: Z2 ?" O3 k6 b9 t% S
initM(MATCOM_VERSION);
  }0 ^4 H6 f# G: _3 `9 y) n }</P>
<>CGenetic::~CGenetic()
{exitM();
( G) E/ R: M& s2 M}</P>
7 `* |- e! j2 l1 R$ S8 T( F: v<>int CGenetic::rselect()
{double rand1,partsum;
6 ^% d/ H9 b- N5 b' A int j=0;
partsum=0;
- a. J  g  e7 L: | rand1=rand()*sumfitness;
# Q. z, v- F$ q3 d/ ?- h; | do{
( M0 t$ T" ^5 `' v. N5 p% Y& M  partsum=partsum+newpop[j].fitness;
  j++;
! O! o) K% y6 J* S( y1 c+ n0 h }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
- A2 I- s1 ?& x: K( s$ E# d0 Z return (j-1);
7 q5 Y" V& Z  M3 P* U) d" q4 `# S1 b}</P>
# T2 H% n" f% v0 f, K8 e<>void CGenetic::generation()
{int i,r1,r2;
0 C& t5 X5 f8 ~: a CHROM tempChrom;
7 x( e$ i" L2 {, G //进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
- e$ N* `$ ^7 n. w& L  b; v //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
- N  n, W, y5 L. O9 P    for(i=0;i&ltOPSIZE;i+=2){
' ?6 p( g5 B9 v$ `4 ^  U: l. q; Y  r1=rselect();
  r2=rselect();
2 T2 o& u2 c" N/ E- v$ X  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
- K5 Y# c- G' y2 |# G' |" R: O  tempChrom=newpop;
, d, l4 U$ |) Q$ p2 ~: E  newpop=oldpop;
  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
, L1 j) W# L: C<>bool CGenetic::begin()
' x* B" J: L  x) E8 ]{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
' i" T, Y/ w; e: m8 }! Z" Hfor(int i=gen;i&lt;maxgen;i++)
; a( _. Y. V" ]2 H+ r{if(IsStoped)
# k" n+ ]7 Z$ Q% I2 j8 B  break;
- ~; K9 z' u, g1 c, G9 |$ m* R' z if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
}
; A. ?" ]) m! A if(gen==0)
' D( V; z* z. r; V  init();//如果刚开始运算，初始化
generation();
gen++;
6 c! z4 r4 Q, c //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
) W% U; L7 R4 k5 s, N+ G7 A :ispatchMessage(&amp;msg);
msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
( u: ?/ h  e. y5 h<>return(true);
}</P>
1 X2 u0 ?7 t, ~" J<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
) [3 R7 d( ?$ s/ \, d/ O/ a int i=0;
/ T$ H2 T5 U+ F, j: k5 c//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
) w$ ~$ S9 D: `3 M2 Y4 [ do{if(flip(pcross)){//交叉概率
c=rand();
! K1 C# m3 W4 T/ T& @    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;
& |2 i" H# B8 I0 W2 t }
}
else//直接赋值，不再交叉
& e# u* M4 T+ H$ l% u; Z {oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
- s6 I! W% d, G# d9 i2 D) j }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
; h) F# e  t0 c5 L* Y2 i. B; u. y<>}</P>
4 h: q7 ~6 v# J2 o4 H<>bool CGenetic::flip(double possibility)
: E# K' f1 w/ l6 ?{double ppp;
ppp=rand();
; o' D9 |4 Q! {+ L( j" A9 yif(ppp&lt;=possibility)
8 ?" b6 S6 s( x3 `# I return (true);
# B& v$ j& c/ O' d4 b/ y7 celse
return (false);
}</P>
<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
int i=0;
. Q! N# J( a2 q( Y CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
, I% s2 I2 A- J  @     temp2.chrom=chrome-&gt;chrom;
4 ^+ r$ M  s$ p- O" v, d         for(i=0;i&lt;iVarNo;i++)
    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
2 X0 X' J; A+ W$ r1 m* [          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
: A* R3 c  a0 C9 W& y$ k    if(!identify(temp2))
4 V$ E" L; B  I% n0 G3 |. Y     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
}
7 K1 Q. E, L; L/ P8 j$ F- H else{
  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
1 m7 a( d4 P8 C6 V6 E$ C4 e }
4 o5 v9 ~# e: Q/ \ for(i=0;i&lt;iVarNo;i++)
  e# p) |' y0 J3 H: k5 Y  chrome-&gt;chrom=temp2.chrom;
" Y/ L& U& l' P}</P>
  j/ y2 z% l4 @) O1 Y<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
# Y9 ~  P( Z# |( m for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
& {! R5 y  h) U: G& J   sumfitness+=pop.fitness;}
6 i+ t0 G, m6 J. C; w //选出符合条件的染色体
) s( H% T: E6 B9 x for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
( F# N5 A" P$ W# O$ y8 Q if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
  j" t/ c$ E* Y/ R+ {9 x<>}</P>
8 l  A7 @( o$ m! T1 J7 F) Z* i<>void CGenetic::init()
{//对种群进行随机初始化
+ Y+ r' E; Q, F3 f, [( qint i,j;
9 [. x8 N# ]" Y' m) Esrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
& H6 T: G$ g( u{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
* a% |. O. v8 Z' f/ o        oldpop.chrom[j]=newpop.chrom[j];
}
/ W+ I& g( K5 g  j( ?. N( K$ {% H9 }}
! y  F# I" Z- _}
else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
# u0 k" A8 H2 {3 f  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
, h0 H& ~* f  p7 s$ u+ { }
* D) c  }0 f3 P2 D5 Y}</P>

<>double CGenetic::randxy(double x, double y)
9 ~7 L" ~$ U; i+ s! V/ J$ v! ~{ return (x+(y-x)*rand());</P>
<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
8 R) Y" }' b$ P0 W2 Q8 v, A{int i;
9 E" O/ ~# W: \! {/ m0 T' y" y1 {/ Pfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
. {9 B3 y( J# H: p! G+ I}
' B$ x8 A' [  e7 e* j' BIsSetScope=true; </P>
( y# ~0 R3 l* |4 J$ z: N3 W' W2 @2 X<>}</P>
5 v/ r& x. `: c- C8 R4 v<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
; s. F1 z" `# l7 X- } for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
3 v& F& ~2 T& a% [& D mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
return(dblResult);
}</P>
  r5 P7 Y2 f( J8 h, V
; F. |0 G/ c3 |<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
* S( @* _' g4 |7 Z2 r) i1 o  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
  break;}
}
return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
; |0 _# `6 r9 m1 p# R int i;
* x$ J# A5 V/ }5 T; p for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
2 R7 h: {" w: n# ]  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
  i& G( I, K! |+ ]     temp2+=dblTemp1*dblTemp1;
0 @. t! r& q( i7 W) }1 ~  temp3+=dblTemp2*dblTemp2;
- ~7 p3 g3 c5 H! F# C2 m }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
return (differ);
$ I. w5 W$ T) N4 u; [1 q) Q( b}</P>
6 C; T) f2 R! t/ K; j<P>bool CGenetic::IsNew(CHROM ch)
{int i;
1 }' w" O" _3 h. d: k bool IsDifferent;
IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
! V6 z, U- H5 M' K% x  {IsDifferent=false;
- g7 o' E. I' r9 G( S' Z1 ?1 L. k      break;
  }
return (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
5 `# R( f* V  H{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
* T! r! M1 |+ }3 G. o+ x: S double dblTemp1,dblTemp2;
. h7 I8 ^/ h2 M8 L( i# D for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
# u7 R; T/ L0 v7 s" a5 Q6 F }
temp2=sqrt(temp2);
6 m! W! E0 {6 a- R temp3=sqrt(temp3);
, o" m! o3 _& P/ Y# L dblCos=temp1/(temp2*temp3);
: N3 Z, E* E3 J+ Z( E6 | pi=acos(-1.0);
  D# r2 {- M5 W7 o angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
9 |& W8 F, R' A* l<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
; _8 F/ Q2 G) p: Q( r' D//////////////////////////////////////////////////////////////////////</P>
6 ^3 r2 C* R+ q; M<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
% I  @3 G2 e4 ^' h. p9 c# t#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
% i3 {5 U$ _+ D, `7 ~- p#pragma once
: V: q- P/ O3 B' U) ]#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
double fitness;//适应度
- A, w- t- ?5 |5 h$ q3 ?% t}CHROM;
% V4 G/ }3 |: c" r% p#include "BpNet.h"
6 e0 T5 h$ G: |# e5 H* B& r4 z////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
0 t9 l# D* i+ t" |class CGenetic  
{
public:
bool IsStoped;
double dblAngle;
& G- _  O- W5 ?, `; Q' N CHROM best;
, `. M& v; t6 ]: v/ b5 q$ I3 U Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
; \& R) w2 t( ` int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
) @/ M+ N# n% G5 Y3 g2 _8 B //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
; {3 r/ f; t1 F9 t. ~- i5 m) Y void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
, d1 p3 @* S- B$ X. w- j" I, ^) ]9 s void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
2 M8 W2 e7 [+ K; s; |) E bool begin();//主函数
void generation();//一次进化
' n' E( @9 m+ W int rselect();//轮盘赌选择
0 S: d- t, e9 ?& c+ R CHROM newpop[POPSIZE];//种群
, w7 @9 m. f: F# h  T$ @1 Z, L CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
0 t) _! k  J4 Q1 t  ` double pcross;//交叉概率
: ]4 }' L1 J8 d. s# _4 _6 w long maxgen;//最大进化代数
$ H$ K5 T. s/ k! N! Y int iVarNo;//染色体数目
double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
<P>private:
: i. S+ _' `8 u- {- D% O double angle(CHROM ch1,CHROM ch2);
6 W5 W( D5 _/ L8 E8 p* C5 x bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
* n$ t3 q" Q' ^; g2 T1 l8 P, M void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
: G9 E. P6 d/ q bool flip(double possibility);//测试
% u( C2 t0 a, g, Y: e //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
& x8 J: I, h# y  H) U( c$ c3 u% r4 S 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>
6 P- }9 H" B7 D0 |<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>