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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
5 u  `+ ]4 H2 ~//
! I2 Y' ]' g8 r1 W5 X2 _//////////////////////////////////////////////////////////////////////</P>
$ d/ {, \) y6 Q- [: i0 K6 [" n<>#include "stdafx.h"</P>
) f+ |0 c( s- m3 j<>#include "Genetic.h"
#include"math.h"
: @0 g' z" j- a7 Y  F#ifdef _DEBUG
#undef THIS_FILE
) s/ {) B- \1 q, Pstatic char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
' d6 U1 j/ P% `; A//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
7 m4 |% i; |' S7 X" i, r, ?; V pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
4 l% \1 T( T# P% i iVarNo=0;//染色体数目
sumfitness=0.0;
gen=0;
* w4 u* }4 V  e1 H IsSetScope=false;//还未设定个变量范围
IsStoped=false;
% T1 w# }7 a8 V! i/ ]1 e for(int i=0;i&lt;MAXBESTNUM;i++)
9 ^0 X+ `" V5 O) w- Z+ l   bestchrom.fitness=0;
iBestNum=0;
0 |" X' j% R, j: u7 y dblCre=0.0;
. y7 c9 u6 d& f+ H dblDifference=0.15;
; C. m2 P' L8 Z) U2 o  ?6 }4 k9 L: h best.fitness=0.0;
8 H8 U4 I+ o; ~0 b# t0 H
$ i. h, g! O7 o1 x initM(MATCOM_VERSION);
$ \7 R7 W- P1 J3 Z+ n7 w' |) U }</P>
<>CGenetic::~CGenetic()
{exitM();
}</P>
<>int CGenetic::rselect()
{double rand1,partsum;
int j=0;
partsum=0;
rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
8 h; N" ^$ h! S% j$ V; Q  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
# s3 k6 n6 w% R- A}</P>
<>void CGenetic::generation()
{int i,r1,r2;
CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
& E3 Q) w0 K' v( L) l. i //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
' j' \: _  }4 W) \9 y    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
: V/ d$ j8 F! K  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
$ y# z# W6 x7 I. t4 I; B for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
, @; M/ G. X' \6 H, C; J  oldpop=tempChrom;
0 f' v+ X  `: v7 B3 {6 j7 G, S }
//从1到POPSIZE循环，对newpop进行变异
7 l+ |' I! Y4 y* d% e    for(i=0;i&ltOPSIZE;i++)
8 V4 e# X: X; o$ q  _, u     mutation(&amp;newpop);
# y) X1 X8 }; m: n  c/ |}</P>
<>bool CGenetic::begin()
{MSG msg;
) m' z4 Y$ \: B9 y* Q' P5 u' O mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  w: M- c: }- t! V/ I: q  break;
if(bpnet-&gt;iOutput&gt;1){
5 g$ K* Q5 q' I* }; K ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
: X/ U+ D. m1 M4 p0 }6 r; S }
if(gen==0)
  init();//如果刚开始运算，初始化
generation();
& O! O+ @3 |+ c+ j# \1 k; M) P7 F gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
5 d9 M3 R) u; E :ispatchMessage(&amp;msg);//这样可以消除屏闪
. M: E, B$ [; t" h" y& H' B}</P>
<>return(true);
}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
. G. O. W$ ?+ H7 a* t{double c;
' Y' j/ t, v9 M: x int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
( z1 r# T( u2 m& O- b% w! D//循环，直到产生合法的新染色体
! F  K  Y9 M2 [( D2 U( j% Q; @7 J do{if(flip(pcross)){//交叉概率
2 L+ D) ^+ V8 h3 p; P c=rand();
    for(i=0;i&lt;iVarNo;i++){
4 m/ I/ H$ f' U1 |+ V oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
# s& \% v8 B7 T oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
$ k; d' F6 i6 M2 m( e2 B }
2 o$ N& @" U  S" C0 B. R }
! q/ W& \! e- u, M3 _( z0 | else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
2 h4 P, k, J# q: Y  oldpop[iPlace+1]=chrom2;
}
: x' a3 C3 B$ q1 j4 T( T}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
3 e+ l2 k, _1 H<>}</P>
<>bool CGenetic::flip(double possibility)
  C  X' B3 x' Q0 e+ u+ x5 M6 Z' A{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
. U1 R/ {7 f! B' v9 v7 u return (true);
else
return (false);
}</P>
) Q8 Z4 ~3 [) F7 ]$ g% P' ?<>void CGenetic::mutation(CHROM *chrome)
# b7 q+ Q; Y# y4 t% |{double m=10;
int i=0;
8 L: v5 H6 l4 K  F5 r" M  c CHROM temp1,temp2;
% }0 N$ v& I& E- m4 _5 v+ F2 p+ p if(flip(pmutation)){ //以变异概率进行变异
  do{ for(i=0;i&lt;iVarNo;i++)
5 D% t/ T5 z5 O5 w     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
" s1 ]# L+ ^6 q% \) P: \) x    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
) |  W1 ~' f2 z3 s6 {; u  {- J          for(i=0;i&lt;iVarNo;i++)
& b/ i) B; r3 m1 n     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
1 T7 U( N: C4 @& R  }while(!identify(temp2));
}
else{
9 J( v6 ]/ \4 R. G  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
% a7 |! ^- r: q/ J" h, M8 B }
7 W4 z  n6 Y- U6 Z$ s* T. @ for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
<>void CGenetic::statistic(CHROM pop[])
, @; c; M* I+ X, Q8 f: Y. j{int i;
sumfitness=0;
1 Q  R6 A; j& Z) G' \ //循环，计算单个染色体的适应度,以及sumfitness
: C- W# u+ r: |5 K0 d9 \ for(i=0;i&ltOPSIZE;i++){
2 ~( j  }% Z$ P/ e   pop.fitness=CalFitness(pop);
5 g% a& ~: f( @6 o2 @   sumfitness+=pop.fitness;}
4 K( l& V4 y( i0 ?$ P //选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
! ]8 m5 j4 {3 K6 j0 g* B" y2 f if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
9 I8 M; o! W8 B8 A& x if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
<>}</P>
<>void CGenetic::init()
/ t6 G4 f3 X; \' K1 B4 I{//对种群进行随机初始化
) h5 ~4 @/ R9 y' ]% \/ \! A- V6 Kint i,j;
2 ^+ ?# U' M+ C  Osrand( (unsigned)time( NULL ) );</P>
( s  z  {5 Y5 U9 v  n<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
/ g% _9 |4 t* _  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
8 w- k+ X- F5 \5 z        oldpop.chrom[j]=newpop.chrom[j];
}
}
% n9 F, i4 ]8 T, W7 @" I- P" Q% `}
3 N$ v. f6 M. W: C8 C6 D( I6 n else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
/ V' u5 T: h& ]( a! V7 u  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
: Z' H: S+ c1 z8 ] }
}</P>
2 P* g) |! ^0 ]1 x
  j, W' O0 }" G+ @<>double CGenetic::randxy(double x, double y)
  ]7 C* ?" K* x- h' X{ return (x+(y-x)*rand());</P>
, L) x0 s* }5 H$ s  ?<>}</P>
% u- L; l. C, w- l7 u7 ]" D<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
* ^0 ~* B7 P- _7 \ int i;
for(i=0;i&lt;iVarNo;i++)
. @$ `/ i& {2 y& {$ C, p1 w3 r  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
% R. H" M0 h4 p7 h dblResult=mResult.r(1);
return(dblResult);
, q: E/ s' L0 e* Y6 c6 H' v: ^}</P>

<P>bool CGenetic::identify(CHROM chrome)
3 J6 S8 m' U% Z2 y- j$ f  M; r{int i=0;
4 |& B6 f+ l- e- ^& [( A  b6 y bool IsOk=true;;
" k- N& v! i) s' c8 h for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
. C" }4 U8 @: r4 s' W  break;}
}
7 P  w* w$ b5 R, R8 _1 f; ^ return (IsOk);
; q1 H5 v- b3 d! v; W}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
/ _* j7 b& W2 [9 d* w- q int i;
for(i=0;i&lt;iVarNo;i++){
& Y5 \4 z, B7 {- f2 I( F  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
- j* u( q3 G+ A- g: \0 ~  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
- f3 L, |- p" Z: Z+ v, ]     temp2+=dblTemp1*dblTemp1;
- l; l7 d0 a1 s2 B% i  temp3+=dblTemp2*dblTemp2;
}
! b" q+ T$ r! P- K; \  l" Y2 e temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
: _$ ?3 }* X' J' K9 g( \) H) r differ=sqrt(temp1)/sqrt(temp2);
return (differ);
: S7 D& ~3 K8 ^% K, j}</P>
+ Z% `& M/ J  c/ C2 p+ j& g2 p<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
IsDifferent=true;
+ y% i( `* P' S) @2 S; t0 T8 Q8 H for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
/ x6 Y6 B! n' W0 k  }
return (IsDifferent);</P>
<P>}</P>
) H4 d: J4 j, w$ ]3 x; s<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
4 `( K$ p+ T6 N2 T3 C7 O{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
( K7 J0 H: U8 H' t double dblTemp1,dblTemp2;
* Y- k  S6 h1 Q1 f7 l for(i=0;i&lt;iVarNo;i++)
& C2 t3 O; {/ T" e {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
1 c. @4 B! \& n, p  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
0 M4 L( V9 B% n) k$ \  temp3+=dblTemp2*dblTemp2;
}
$ q) t0 e$ f; H0 t$ \3 h  w4 ] temp2=sqrt(temp2);
temp3=sqrt(temp3);
1 f9 Z( I$ s7 v1 u dblCos=temp1/(temp2*temp3);
( p- E3 \; {; x7 C* D. b pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
( e1 C; D  n1 H2 b! Y6 K1 Y<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
+ V! b3 s% @. c7 s! K! ^<P>#if _MSC_VER &gt; 1000
#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
% {" l9 Q; R& L& Q5 L; ?7 _& _typedef struct mychrom{
7 r/ p1 n& G- J" f; Xdouble chrom[MAXVARNO];
- D/ ]+ N, q( g  @, W# adouble fitness;//适应度
# w- S0 W8 x/ T- \! z# C( Q}CHROM;
, z; ^$ S/ K) ?. d$ c#include "BpNet.h"
1 H3 K. X( s/ d0 |$ Q1 c; Y////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
public:
bool IsStoped;
5 L# [) h/ w" J1 ` double dblAngle;
. Q. P$ o' a0 @2 b CHROM best;
( z5 E* n0 o! G) W4 w0 H7 ?- @ Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
( F% }6 Y/ z7 e& [$ ~ double dblCre;//适应度&gt;改值的染色体符合条件
( e) G7 _1 l1 y* Y# g int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
1 h' H6 D# C$ a* o" p void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
. r" f1 h8 N7 ^1 W4 M! P double randxy(double x,double y);//产生x,y之间的随机数
3 x" Z3 z- T* P# [1 Q void statistic(CHROM pop[]);
# b2 \1 B4 T) J( n  w CHROM bestchrom[MAXBESTNUM];//最优染色体
6 B2 R+ O1 Y- j1 ]9 y bool begin();//主函数
void generation();//一次进化
9 L! ]& I9 V( v# Y# n int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
, g! N  q5 L% u* G CHROM oldpop[POPSIZE];//种群
' V$ f4 n2 _! t7 D$ a double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
; F9 C5 u) B8 e5 X- t int iVarNo;//染色体数目
5 d" c* m# k+ v/ L double sumfitness;
CGenetic();
$ ]2 V% g& k+ ~5 n5 v6 H virtual ~CGenetic();</P>
4 c' E' w, B* o<P>private:
$ N$ i/ M, @4 {1 l3 M' i& J double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
9 U; T; b3 d" c% n; s<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
+ v' x. D- `' N) @ void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
0 C" l/ d6 b* m bool flip(double possibility);//测试
0 d' E" l3 [8 ]- r9 p //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
4 t) V7 F( J' X9 o% b bool IsSetScope;
1 i: }% y) ~6 ^- Y7 ]4 m
};</P>
7 P/ b+ O: `( |& w$ w# @6 n, q<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
4 X  E: H6 T1 D
' R3 H# l  c% w' T( g. q2 G</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>
. U4 F1 I3 g% A2 p; c$ {* N9 y1 |( e( ]<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>