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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
9 t  E& y  q  E8 G  \, d//////////////////////////////////////////////////////////////////////</P>
' K- ?2 z% j& z( s2 P# W<>#include "stdafx.h"</P>
0 f# o: h/ w) |7 G" f<>#include "Genetic.h"
#include"math.h"
4 d# C, ]% _1 {. E/ z#ifdef _DEBUG
9 D* ^( E2 f" K7 C+ J5 t  ?+ N#undef THIS_FILE
+ Q: w2 @* U, A8 i& j8 p; Z3 tstatic char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
" o* Z5 V6 k/ Q$ v//////////////////////////////////////////////////////////////////////
" Y! Z! q3 r* F+ u! n# j' Y// Construction/Destruction
/ C, b+ @2 Y! [' i//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
5 d; z1 {8 W  o1 s{pmutation=0.01;//变异概率
' [$ _5 X& h( E# s/ I2 A pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
! k( w" x; Z# O0 }% J5 S$ C gen=0;
& E/ {; d( b- n  |( a2 u( ~ IsSetScope=false;//还未设定个变量范围
' d( r& s& M" Q& }) \: c1 } IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
1 W3 y! n' S5 t   bestchrom.fitness=0;
iBestNum=0;
dblCre=0.0;
4 x( Z/ B" K0 g dblDifference=0.15;
6 T- L( k' a  M" o2 E3 f+ W7 Q" H best.fitness=0.0;
. y2 q! \: U' ]( O( i
6 F( C7 ^# m* l  e9 q2 Z- X initM(MATCOM_VERSION);
2 `: X' V- A. n9 }% L4 o8 J }</P>
<>CGenetic::~CGenetic()
6 Y. m4 M5 O% A$ L0 d0 @$ L, E0 B{exitM();
}</P>
. S- A$ k( w4 p# J! s/ C<>int CGenetic::rselect()
+ c3 f% l. c( Y. }! A{double rand1,partsum;
! V2 j* U) G1 k3 V7 f int j=0;
partsum=0;
rand1=rand()*sumfitness;
do{
& p, h. P3 U5 P/ b' F  partsum=partsum+newpop[j].fitness;
  y9 v  O: |1 \/ T! f  j++;
3 ?" `* o2 k2 _7 k }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
: ?; D6 p3 i. e return (j-1);
}</P>
4 c% o- V. o: K9 P& M<>void CGenetic::generation()
8 |9 [( T* ~6 W+ I( ]# n{int i,r1,r2;
4 r; \) @0 ]  ^# w$ y/ m8 E$ @ CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
4 ]- X' w* f# Y0 i8 C  |    for(i=0;i&ltOPSIZE;i+=2){
3 S2 Y& {+ H- e  ^  r1=rselect();
  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
  M7 a/ l( f2 o( o4 ~  q, t- F for(i=0;i&ltOPSIZE;i++){
2 a1 p5 G* H. B& \% \  tempChrom=newpop;
) l+ p0 H" D5 g/ C1 e) k  newpop=oldpop;
+ D# ]4 F2 P+ C3 C) q* q  oldpop=tempChrom;
}
6 f! ~1 f' d. @$ O //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
# z( T, O  o: @: O+ Y9 s     mutation(&amp;newpop);
% C0 |% D% y( f: U- J8 ~1 V* y  S}</P>
2 k6 b" b7 s( Q7 Q& b* \: B. J8 C2 @& O<>bool CGenetic::begin()
{MSG msg;
! g; ~7 A. V9 E* N7 J mData=zeros(1,bpnet-&gt;iInput);
  G5 D- M7 T8 V/ V( s5 c mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
8 p5 X% p! V0 K/ B0 r{if(IsStoped)
9 B8 }3 u8 q$ J1 Y: i# Q  m& \  break;
' f9 v4 `- ~  }# p# J* d if(bpnet-&gt;iOutput&gt;1){
* f; H' j6 F9 M& G* ^* y ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
2 _" S! S2 G& i return(false);
  [4 n8 X1 E3 h }
! l5 D0 F5 Q0 l) G4 g8 S8 X if(gen==0)
  init();//如果刚开始运算，初始化
9 y; k" K" ]' g generation();
6 z" C3 U: j& |" p7 r; _+ ^3 r gen++;
//防止假死机
5 K* P0 T) e' O0 J' w% B1 Q; K9 [) h :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
4 w4 m/ A6 C: `& p; j( ^0 i :ispatchMessage(&amp;msg);
msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
, }4 z* f9 d; c3 ?+ T( u8 ?- e<>return(true);
}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
9 B" E( D0 Q0 ?7 k% `{double c;
int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
" x7 W' a6 n7 T0 J4 ?+ Y6 w//循环，直到产生合法的新染色体
! b( x7 G% x* U* D do{if(flip(pcross)){//交叉概率
* ]4 a! t( X7 V5 ^. | c=rand();
    for(i=0;i&lt;iVarNo;i++){
5 N. F% H# `: _3 F2 J# _% w oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
; Q1 {! J9 o5 y8 H oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
  |7 L5 u) _( H% _; v0 a) n7 o }
else//直接赋值，不再交叉
2 r* w  D, _& q' E; D {oldpop[iPlace]=chrom1;
3 i# C5 i: D$ |/ o% i  oldpop[iPlace+1]=chrom2;
& u* |( G, ~% p* w }
5 `4 Y0 g9 x) S' ]}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
return (true);
, G( W. Z9 ?& G  ~7 f$ t" k. ]else
return (false);
}</P>
  R% T) e1 l  c" Z: j% c4 ~; Q<>void CGenetic::mutation(CHROM *chrome)
& z/ y; k% ~' r% r{double m=10;
int i=0;
  a& L  S: l# X/ K  E/ \ CHROM temp1,temp2;
; T; [2 s9 w$ Y( F4 \ if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
. S2 ]3 e/ [, y8 x    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
6 }" Z! b2 b4 N( x6 f4 o    if(!identify(temp2))
- }. t9 D+ z' j# l/ R2 M6 v     m=(double)m/(double)(2.0);
) e, s( I- L4 f/ F! {' ^3 Y4 R  h  }while(!identify(temp2));
3 t; S7 ]6 ^& y# e }
else{
" |2 }5 m4 c0 D  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
7 A+ u" K- [1 U3 f }
for(i=0;i&lt;iVarNo;i++)
6 Y3 `' Q* O6 L  chrome-&gt;chrom=temp2.chrom;
}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
5 \' C4 ~% _# b: c3 P) S& v* e$ z for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
/ ^! @5 I: E" E6 H% X7 m if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
<>}</P>
" B# l5 d, h6 w3 C5 x<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
7 T- Z; a* f7 U4 F6 n3 ]; a for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
4 M& D+ W$ q5 y# s( l/ K }
, |. h6 }) a+ U+ W7 ^5 E2 j}
. o* `$ e" z$ k0 ~}
% P( r$ q/ I  d else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
' v4 B1 g  c& Z& u$ H0 P- |  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
+ V! @" V: v  Z5 W. ^+ F  M }
}</P>
! s! z; o9 V2 f5 d
<>double CGenetic::randxy(double x, double y)
# l! x" i! ^' G- u{ return (x+(y-x)*rand());</P>
  s, t& [8 p/ U0 J1 r# M<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
& {) R. T; T; C5 ~{int i;
  X5 ?5 A* l$ |1 `for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
& P* J4 P/ A' P! M' U/ j varminmax[1]=scope[1];//最大值
% u, ~: ~/ b- w}
IsSetScope=true; </P>
8 f. [) I. t' s$ w<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
0 S1 Z, S* ~# [* H7 I{ double dblResult;
int i;
for(i=0;i&lt;iVarNo;i++)
5 ?1 r% H# Q$ a9 S8 w# s# h7 v  mData.r(i+1)=chrome.chrom;
. D/ r& Q$ m' x, i$ \ mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
5 J$ x2 n6 f( T" p+ F return(dblResult);
. E5 X: e% W1 t& H; d5 T; i$ P# j}</P>

<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
' R1 U* @# w: A$ w0 I; e7 s bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
% P" _$ C/ g/ ~) ?5 T  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
% R; J+ l/ z: @$ }/ L  {IsOk=false;
  break;}
( i: b# n" x5 c, K0 C# K; { }
/ [. [' L* Q4 _7 L- _! b return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
$ ^% v% I0 t* u; `) r& N5 ] for(i=0;i&lt;iVarNo;i++){
- p+ d/ d  i6 T* I( @4 }8 Q  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
* J1 g" f. [% W+ r  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
* ^# `; L- K5 M( j- i" Q/ {  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
& _% k. R! V& b' N; o' [1 w     temp2+=dblTemp1*dblTemp1;
; a8 U" m5 [. ~% a2 {$ W  temp3+=dblTemp2*dblTemp2;
) T9 {" p3 ]- m6 z' z7 N }
7 J/ W' X% ~+ K3 Z* m" D) @ temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
return (differ);
+ ~4 z' y. T! L1 k$ X}</P>
! ~4 w: \! H- z( a& N, f  h' g9 [2 j<P>bool CGenetic::IsNew(CHROM ch)
( _& b3 T# p1 A4 l) V: Q3 U{int i;
  m. D5 R1 ]3 h+ b5 \% L6 d bool IsDifferent;
" ]9 e. p7 {2 X8 _/ S0 p IsDifferent=true;
) Z0 N" q7 z8 q. E for(i=0;i&lt;iBestNum;i++)
% Q9 O# _9 X& s0 R% ~  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
0 k4 w0 x0 ~# c* g4 p  {IsDifferent=false;
; R/ z/ U. W8 v7 y      break;
: F$ W, v; C% W# i" t% {  }
return (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
  J, U+ L9 ?3 k% c& Q2 m* D{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++)
1 n7 m$ C) W2 i8 F  a6 V {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
, H! o  i' S1 g& I  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
+ ?2 `- q  F6 g/ Z: n) i  temp2+=dblTemp1*dblTemp1;
5 T" N- L6 {4 Z6 i  temp3+=dblTemp2*dblTemp2;
3 H. Q1 K( y2 U$ r& y }
2 F2 w# X' N) w5 A2 S# s2 z temp2=sqrt(temp2);
temp3=sqrt(temp3);
) a9 H+ H% I* _3 _" G7 b dblCos=temp1/(temp2*temp3);
3 y$ V5 v0 |1 q* l6 X) d, v pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
) o) i  @5 L% N- z) |9 x; n. R<P>}</P></DIV>
5 U; T( D3 X: k9 A0 c& A<DIV class=HtmlCode>
1 H4 J( r5 R; G3 c6 D5 e9 T<P>// Genetic.h: interface for the CGenetic class.
//
8 l- _7 S4 V7 K0 q//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
- H* W- |& e- E3 j, D, H#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
#pragma once
$ p* t0 o" B1 C#endif // _MSC_VER &gt; 1000
#include"definition.h"
, _7 P6 L4 j6 B- m6 ]* W/ Ltypedef struct mychrom{
4 [2 W" j) E6 M+ C' fdouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
) m& @/ L* a3 O- H5 Lclass CGenetic  
{
% ]9 b, P) l; S! ?* ]public:
bool IsStoped;
double dblAngle;
; T9 Q/ b( O; }! N( M4 ]* } CHROM best;
, L  E; F' X4 B9 ^/ E, m Mm mData,mResult;
* s' P" `1 c8 @  c1 k: _# g* [ double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
( s( y& a! j7 }- |, Z" f/ n CBpNet * bpnet;
9 f+ l# S1 e. \. @. x //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
  F% J6 E# _) F4 Z' { long gen;//当前进化代数
+ [4 v9 Y: \5 z) e void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
- ]. j$ z, C# Z. O; Q4 { double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
- K( n/ y$ @/ w( S0 y5 \% {9 l bool begin();//主函数
void generation();//一次进化
# ~7 m0 ^# `* x; F! M: o int rselect();//轮盘赌选择
. G3 c* F: |0 B/ X CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
1 ^9 W; u5 u1 J- k double pcross;//交叉概率
long maxgen;//最大进化代数
  c7 ~* _& c) T1 p int iVarNo;//染色体数目
) s0 d! S) u" D! K+ k3 G double sumfitness;
; V0 _; D& F0 p7 U) } CGenetic();
4 E5 j0 a6 S& ^, X+ ? virtual ~CGenetic();</P>
<P>private:
. @% C& h1 A5 q0 z; Y, ?2 r2 N6 n double angle(CHROM ch1,CHROM ch2);
8 e! }. t/ R4 T0 l bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
4 n" h/ G3 Q0 `' g double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
/ R' O0 {7 s1 g* | double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
& v  S1 S8 w1 } bool flip(double possibility);//测试
1 X- l6 g# u9 X2 h. ] //交叉操作，iPlace指明新染色体位置
+ r9 }, s5 B- K1 w: V void cross(CHROM chrom1,CHROM chrom2,int iPlace);
" I; e  ^, y' b4 O bool IsSetScope;

};</P>
% `4 Y, W( x4 ^<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
, b/ E( w. P1 N* V$ s
</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>