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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
9 G+ Q7 F$ n% O8 V( m. ^<>#include "stdafx.h"</P>
6 R3 B, Q' c. E3 x0 n* `6 ]6 _' s<>#include "Genetic.h"
#include"math.h"
. g: [7 a' E% S7 t( D2 m#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
$ b. o9 s% o$ D- g6 F5 X#define new DEBUG_NEW
#endif
: i6 p  L5 S, _  d2 G) _% F/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
3 H5 i. C& f+ |// Construction/Destruction
) t9 g9 {( P5 c, C' X# [+ }6 Y) g//////////////////////////////////////////////////////////////////////</P>
+ [% g9 y  s  p2 D$ b$ h0 S. o. c0 y<>CGenetic::CGenetic()
, ^( {- B9 T. z9 f9 j{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
& S- W4 S# L% R. K maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
% \5 M0 R9 A, P4 A9 V6 s/ ^ gen=0;
IsSetScope=false;//还未设定个变量范围
IsStoped=false;
$ S$ r5 `2 h8 S  t for(int i=0;i&lt;MAXBESTNUM;i++)
5 v: Z0 f+ p7 l& O5 q; a& Q, O   bestchrom.fitness=0;
% g5 `/ k) ^: A  t" m iBestNum=0;
dblCre=0.0;
5 C" ^3 z; K( w& x2 ~ dblDifference=0.15;
9 g: p0 H7 d* u best.fitness=0.0;

7 X: B' ^% D5 X1 q% D' \  q initM(MATCOM_VERSION);
}</P>
<>CGenetic::~CGenetic()
2 F3 {/ i9 d6 |3 {, V) y" D" [; `{exitM();
! {9 ^. d0 z3 ]4 \8 e7 s2 ^' j}</P>
: b/ I0 T0 K9 s" G- Y<>int CGenetic::rselect()
{double rand1,partsum;
int j=0;
partsum=0;
rand1=rand()*sumfitness;
$ B3 J" o- u8 F, O2 M do{
# T0 @& x0 D& b: @& R  v  partsum=partsum+newpop[j].fitness;
; i5 K& F/ Y! w) c  j++;
; \; W& C9 B3 \( w }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
: C9 |! B' I% O return (j-1);
' P4 K  j& C; y+ s+ `# b}</P>
<>void CGenetic::generation()
{int i,r1,r2;
CHROM tempChrom;
& ^( j5 B$ B8 x' ~7 r" _ //进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
5 C7 B0 o. H3 D$ \6 \, d4 e, L  r1=rselect();
  r2=rselect();
: i; f1 j, e- f8 v+ X0 `  cross(newpop[r1],newpop[r2],i);
0 c. x% H: Q0 E$ M: D; }' Q }</P>
& |2 y, ^# j- f; N4 i* Q<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
6 \6 f$ Q/ G3 \* T/ Q/ B2 w  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
6 e2 Q3 @+ q6 _* H4 ]7 h$ R    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);
for(int i=gen;i&lt;maxgen;i++)
3 \$ A, P. J4 ?0 X/ Q$ g, p# c& k{if(IsStoped)
$ y7 `2 e# @* h# ~( ^1 q  break;
if(bpnet-&gt;iOutput&gt;1){
  }5 t/ g& O, s( ]3 x/ E0 c* T# \ ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
7 e1 b/ V1 J1 M3 `0 [ return(false);
5 G4 x: o+ W8 Z$ z6 a, q9 \9 U }
if(gen==0)
  init();//如果刚开始运算，初始化
generation();
' H4 \3 T+ b$ n$ O) F8 p3 F gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
( m5 @. i; i( V}</P>
& D  k& {' t/ a<>return(true);
9 {+ w  b5 z! [, a}</P>
& o2 Q  _; h/ ]& g- H<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
) H: Z8 }* x5 r% u' F2 ~/ A! u//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
2 u' q+ K. A! a8 T+ h5 b do{if(flip(pcross)){//交叉概率
c=rand();
    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;
, ]  V9 j" |: N: A2 C3 t6 s }
' @; y0 _( w* w( ?( h }
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
  ]+ B& }1 E+ |" N }
" r& ]6 e" K7 G' ]7 c5 c( T}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
, E) ~( `" v0 s( t' ?<>bool CGenetic::flip(double possibility)
{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
return (true);
else
return (false);
8 Y; b% S5 c& V+ ]}</P>
<>void CGenetic::mutation(CHROM *chrome)
) o: m6 d! w/ }$ O: C+ k{double m=10;
+ d; r  N* H- k int i=0;
* P* b1 j4 a$ w4 ~ CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
8 k* Z  B) Y# Z  do{ for(i=0;i&lt;iVarNo;i++)
/ ~& m. @6 x' v3 N     temp2.chrom=chrome-&gt;chrom;
) |5 w, {6 [6 O. v, y2 H( D$ Z( S         for(i=0;i&lt;iVarNo;i++)
& d/ K$ P- B  `* R/ ^8 O    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
- F$ @5 P9 }1 M  b/ p          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
* J+ Y! I/ i$ [* G, s     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
}
% h0 c" g: x4 J else{
5 F' Z9 W8 x: {& L1 L3 F  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
* L9 z! ^2 L6 V for(i=0;i&lt;iVarNo;i++)
: E% r1 v5 H' J" W) x  chrome-&gt;chrom=temp2.chrom;
/ D/ N, d* {$ m1 }! L$ C& p. Y}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
& p5 G8 w+ V6 U0 B //循环，计算单个染色体的适应度,以及sumfitness
: @% w- v+ o0 Z. a% C3 F( u# V for(i=0;i&ltOPSIZE;i++){
3 Z1 z: h' k( m( o' \   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
/ P% R( L8 Z: ]$ U //选出符合条件的染色体
, W/ _' s) n  `9 ^  V for(i=0;i&ltOPSIZE;i++){
4 r. s$ M* T8 C  S6 r/ B if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
3 E6 M( d& i  h0 o$ O2 a  ~}</P>
<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
/ R9 A- G8 z1 v0 x# `1 u5 Qsrand( (unsigned)time( NULL ) );</P>
6 E% I1 |/ H5 }<>if(iVarNo!=0&amp;&amp;IsSetScope)
9 U3 h; K0 t0 x{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
}
2 N! d1 b" Z6 u) w" s/ D}
else
1 x! e0 n. B) W# v1 D; u( O {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
& B+ `+ ]" e; n+ T2 f }
}</P>

<>double CGenetic::randxy(double x, double y)
( |% n; H9 b% Z0 A$ L, d{ return (x+(y-x)*rand());</P>
<>}</P>
7 _# }7 L. Q( m9 d3 B<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
) v  N+ U1 l  w$ `- c) B{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
8 Y- c( s$ q" w  V! q9 H! x1 y varminmax[1]=scope[1];//最大值
' V. ^5 f" B: G2 a: l}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
5 W& ?8 h) m  _: W2 s# X+ A for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
" U4 S  K1 Z6 e7 s mResult=bpnet-&gt;simulate(mData);
9 }% R5 p2 x. A1 b2 q# K1 G dblResult=mResult.r(1);
/ H; H# E5 k6 I return(dblResult);
2 w+ o7 v5 i6 y' Q& J% @6 O}</P>
* A/ m% j: V0 p& v
<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
2 h% ]% y6 o* A3 g. S. G" k/ f2 T! O1 K  {IsOk=false;
  break;}
7 C0 H, l4 j9 l! i, ~* f5 E9 Y }
return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
6 Y! Y9 n; f8 I. M: |1 `. r' R{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
8 K3 s& p2 c1 f! g& y$ a int i;
# D1 k+ R$ H/ d( P for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
! g8 J' z) |1 p* w( V; ]5 ~: E& o  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
7 C5 g  p+ `0 f6 e' ?' c2 Z" F( b     temp2+=dblTemp1*dblTemp1;
/ O4 S! w  }$ f# M  temp3+=dblTemp2*dblTemp2;
}
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
! S& a/ r3 B! q& b$ A( { differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
{int i;
2 z: r0 e( w% ]) @, M8 @0 G bool IsDifferent;
9 O" A/ L) b' Z! Z2 [* @ IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
+ G4 p0 ]+ {  g. X# Z5 u# ^, \/ [  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
  }
return (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
7 G# P! Y! D/ o2 C{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
  o0 [% z1 a1 e/ O- F. v. V int i=0;
double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
1 t/ {, y+ @* M# H1 R  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
8 V2 A: A% }$ _ }
3 e+ f2 T0 u" z$ `% ?$ [2 R temp2=sqrt(temp2);
4 d) S( |- _* p# Z2 x temp3=sqrt(temp3);
5 Q( d$ \6 p* L' D6 D dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
7 t! `) |( ~6 r: C( Q3 \ return (angle);</P>
<P>}</P></DIV>
$ p. b" W5 {8 h0 ]! t& M<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
: L& G0 `- }2 i9 }( ?//
//////////////////////////////////////////////////////////////////////</P>
, O* d: `8 ~8 D5 a, b' J<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
# o$ {# ^) \2 e/ g8 i* U5 G" }8 R<P>#if _MSC_VER &gt; 1000
/ @: B) X9 g6 c#pragma once
4 u4 O# N# s: l/ N8 n7 u, H+ R#endif // _MSC_VER &gt; 1000
6 I3 e' K: s+ U  {3 ?# j#include"definition.h"
, m2 |# D3 o8 mtypedef struct mychrom{
4 J1 j9 L% F! I& w# Xdouble chrom[MAXVARNO];
double fitness;//适应度
0 J2 W4 L5 M) G( Q: }}CHROM;
* V- _) B; o) l/ k4 l#include "BpNet.h"
& Q6 I2 m& b$ u( h5 b! F////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
$ E+ T2 Q2 C" x4 n7 o2 A* q  b% Gpublic:
2 J, v( p5 c' Z% I bool IsStoped;
- Z! c* W8 H& ?( ]! d double dblAngle;
CHROM best;
' I1 z! [- w4 f2 d0 X5 i Mm mData,mResult;
2 Z6 u. n7 i2 ]# M% v& n double dblDifference;//差异〉改值的染色体视为不同
3 T9 u4 I3 P1 } double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
0 u! d- a4 D" o/ X+ i CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
; P) o2 h& Z/ |9 c$ ? void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
4 R1 q9 }2 C9 l; I double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
9 `" k9 F$ K9 s void generation();//一次进化
int rselect();//轮盘赌选择
8 }6 a0 T9 |9 y. A, Z CHROM newpop[POPSIZE];//种群
- ?" K2 N. R3 G- ^ CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
double sumfitness;
CGenetic();
, D: A* d3 C4 V. O2 ^ virtual ~CGenetic();</P>
<P>private:
$ {2 z0 G" h# E: X2 ^9 S8 ` double angle(CHROM ch1,CHROM ch2);
8 B- L$ ?+ r) x  F* f4 M bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
: @7 ^" G. S7 q! r: ~ double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
8 G4 M6 L4 W$ m# T$ _  ]6 S) [ double varminmax[MAXVARNO][2];
" I# F3 u4 q4 l8 ?) T void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
6 W6 ?9 R( \+ k( I3 U, X //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
3 q' ^5 z. N8 P+ y# O6 _/ ^$ w1 U bool IsSetScope;
# x0 r( v  p7 y4 h/ V
};</P>
' \, s( l: z" n1 p' _- k<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>
<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>