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

ilikenba

<DIV class=HtmlCode>
; C. v4 j) x8 ~* A' N2 w<>// Genetic.cpp: implementation of the CGenetic class.
' m8 S9 O1 V9 Y' I//
& O7 z) l' E" a8 D4 q4 n# f//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
#include"math.h"
#ifdef _DEBUG
! w" [7 c: M+ ], E4 ?$ I/ l#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
1 P: v& j0 p3 f! u" ^& y#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
- D( k1 N  p! {$ P1 y: X- f//////////////////////////////////////////////////////////////////////
* e( a/ g. V* _2 U) G. ^// Construction/Destruction
( @: N: D: p4 }//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
* ]0 Q0 x7 m' _4 R& j- [8 W( X" o{pmutation=0.01;//变异概率
( C( B9 O% o4 p. A$ F  G9 ]$ M. X! V# K pcross=0.9;//交叉概率
' v9 `5 |9 E+ l; d/ F maxgen=5000;//最大进化代数
7 u5 E1 ~; N, G6 v  Y iVarNo=0;//染色体数目
sumfitness=0.0;
4 N# x& U. S/ E gen=0;
IsSetScope=false;//还未设定个变量范围
4 R) Y+ A- j% g" A  g1 H IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
* g' A! d; C* ^1 F( m5 \   bestchrom.fitness=0;
4 b: Q. ^( [) g( X' Z9 ] iBestNum=0;
dblCre=0.0;
8 a& r+ d; l/ [3 ~  g* [; _- g7 b dblDifference=0.15;
best.fitness=0.0;

initM(MATCOM_VERSION);
4 P0 r- e( D# Q  q2 @ }</P>
. v- L& l$ i% }* N+ H$ p1 D<>CGenetic::~CGenetic()
{exitM();
}</P>
1 e/ ^; Y+ U" D7 i) C7 ?<>int CGenetic::rselect()
{double rand1,partsum;
int j=0;
partsum=0;
8 r6 e4 v' }) \: z# M rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
  j++;
1 d6 T; P% ]+ b" ^) z9 x- } }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
) f0 m( U  `( f0 ]$ ^( I% G return (j-1);
- V. [+ G, `# t$ {5 z9 y& C}</P>
: n# _, Y7 M, h6 F<>void CGenetic::generation()
5 R1 U# l, S$ [  C, S5 {{int i,r1,r2;
* r/ q6 L; [3 s6 Z0 z CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
2 r+ F' K  p6 D6 n5 U/ W& p7 F statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
" @% i- H0 K" I    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
+ I6 p# a1 k" V5 L( v  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
}</P>
9 }( W+ F9 I0 S5 l<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
; ]5 M, C5 e* D0 P$ j' w' b% P  newpop=oldpop;
3 Y8 E; j* q, p9 d7 t' {+ B1 I. N  oldpop=tempChrom;
}
3 E; Z( k' y: \9 u+ G8 s& a //从1到POPSIZE循环，对newpop进行变异
2 Q9 \3 P. {3 ~- W3 J) [* r5 [    for(i=0;i&ltOPSIZE;i++)
' g$ e, M& T2 \     mutation(&amp;newpop);
}</P>
. ?4 |' q6 k3 L- U- ]<>bool CGenetic::begin()
2 ~* x  c; V0 J2 J* w6 I{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
* Q4 R* E7 [4 _) {1 ffor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
! H* m+ \+ w! y1 @, r+ |  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
  F- \# N: v0 Q+ R1 R return(false);
}
if(gen==0)
  init();//如果刚开始运算，初始化
% C8 p; B- j$ v% T7 P generation();
gen++;
//防止假死机
8 [% \2 \% O! c; n :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
, I$ [$ E- a6 r9 k :ispatchMessage(&amp;msg);
% y* W& p; C) f2 y& j5 ~) S" i* S msg.message=-1;
% R$ j( w& D* S: ]8 @, ?+ ~  H :ispatchMessage(&amp;msg);//这样可以消除屏闪
, k! A( ]; {/ n2 b}</P>
<>return(true);
0 f8 s; R# S* E) h% ~$ E. |}</P>
" v' B6 V  v- c$ G<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
/ F' W) {0 {# G9 b, {' W int i=0;
! |$ T4 X+ F, j4 x2 I//以交叉概率进行交叉，并对交叉后的新染色体进行判别
) y% Q& z# O  O. t//循环，直到产生合法的新染色体
+ `+ O; O$ _5 K3 k# ]9 h do{if(flip(pcross)){//交叉概率
. W/ |5 ^" A  c( M6 B6 ^# h/ [ 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;
}
% G( \/ X# g( [ }
( |/ Y; l9 t' ^, Y" d  x: |  H else//直接赋值，不再交叉
/ D# V9 ]7 v, l+ f" f {oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
3 _, Y) B  G% M" z+ ]! J7 n }
) l2 f0 k" \3 O" \}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
4 O5 C( L( |8 Q( ?8 t# Z<>bool CGenetic::flip(double possibility)
- x, E) i( y* U( }% v' S  U{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
) x$ B% V& u" o5 `  d" x3 s return (true);
else
- D( C9 |: V, _: v9 V return (false);
! [# D! I' F3 l  o5 g( L}</P>
6 N9 |8 Q' D+ a* k) b* z# }<>void CGenetic::mutation(CHROM *chrome)
6 Q! s% H( q: [0 \{double m=10;
$ u! _) \- h. K/ H int i=0;
" ^( [9 n- a: o5 a 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++)
8 f' U2 y4 n2 M, ?$ U9 A" \    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
" o  P9 t" C) l  N; W1 m6 j          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
* n2 A. b, |) H  {8 Q  a' F1 H: `" i    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
}
else{
  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
* n0 Q' u5 \9 s$ p8 v  chrome-&gt;chrom=temp2.chrom;
( R) q7 ~& s) m" E8 I1 z& \}</P>
<>void CGenetic::statistic(CHROM pop[])
: F) F" e& \( n; s1 Y0 V9 X{int i;
, B; P' T0 V# l: \1 g5 e/ U. A sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
4 L6 ?6 u! f7 y8 n6 S6 C6 C0 L for(i=0;i&ltOPSIZE;i++){
" l7 C& L* A6 H2 F/ I2 Q   pop.fitness=CalFitness(pop);
* Z8 y) e1 u* T4 w6 T1 d   sumfitness+=pop.fitness;}
. j: Z) D) @2 J* r //选出符合条件的染色体
6 }. i3 F- e+ g& \; n9 }+ _4 {1 ^ for(i=0;i&ltOPSIZE;i++){
3 W1 ^. h  ^+ Q if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
- l# w5 [5 ^! F7 l0 P# l  q' ` if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
<>}</P>
" y* R- }7 ]2 J5 h; p3 \8 [<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
. Z) A+ Q/ m, E<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
4 g1 X, ?+ ~3 @: q* z+ g% w- K for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
: }7 l: I. w+ W3 ^$ ~0 G* Z  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
6 N0 X7 m4 {0 L2 K, J7 o        oldpop.chrom[j]=newpop.chrom[j];
}
}
}
. w4 ~) ^( M+ y else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
' i" o$ ?& t8 _0 u9 M  R0 X  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
& a* L' Q% ~" \- Z }
3 y8 O9 N5 ]( h0 m. X6 Z8 m}</P>

) ]' L5 K0 ^- I) g9 |, r5 Q# h<>double CGenetic::randxy(double x, double y)
0 J; y, K$ x  X) J7 t. w" d{ return (x+(y-x)*rand());</P>
  ~* `, _% e: M& w1 ^, U0 Q<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
0 u5 Z# x! C) @3 Z, f{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
: c" A$ G# b$ \7 l- N}
1 T% k) g  f  C; M/ K+ N) eIsSetScope=true; </P>
<>}</P>
# m' A5 J5 G& f" z<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
- w, U( i1 Z2 @. W0 H6 C5 H1 S int i;
& e  L' u( N1 v: ]# v for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
9 l( f2 d+ ]1 K mResult=bpnet-&gt;simulate(mData);
8 k/ _' y6 T8 E2 L4 b, @ dblResult=mResult.r(1);
return(dblResult);
}</P>
& Y8 E: ~, R, z1 H
/ W0 m& Q7 k, p8 A! G) r, a5 d<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
+ z# `! v, X1 x$ T0 A" x4 |  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
2 ~  a! y" k3 Y6 s- l  {IsOk=false;
  break;}
" V) }$ s# ^& X  }& M, E9 y6 Z }
return (IsOk);
, v# s+ p$ n4 M}</P>
) X: c! j2 H! u# b: Y9 C+ x' Y2 @
<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
4 w$ a+ M1 d( O2 T9 X- \! K9 ~' r8 q{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
) G" Z- g- k7 N' N int i;
for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
, X5 }, U5 v6 x' A2 T  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
+ l! j, O. T- z8 b }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
8 T( B, z* t9 z<P>bool CGenetic::IsNew(CHROM ch)
' o8 I9 e7 {0 C. O0 w3 w) \; ]{int i;
% i0 W& K* C/ X1 a bool IsDifferent;
IsDifferent=true;
- N& i" I. R1 W  a, W for(i=0;i&lt;iBestNum;i++)
4 W$ o: \( k; R* w  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
3 ]0 D4 J3 a! t  ]* }/ l7 H9 B  {IsDifferent=false;
* R2 A2 b( l" g3 `' G      break;
  }
return (IsDifferent);</P>
8 }8 O! Q  A! V/ `3 H<P>}</P>
3 ^: g9 T3 Y* |$ k: y& o<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
* A0 ~' ]  D7 c8 s4 S{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++)
7 Y4 F( V* G+ e/ e5 M {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
: `0 O# H6 H2 b" T1 y0 v( t  temp3+=dblTemp2*dblTemp2;
, x, U9 u) {! _9 O: n# }7 i+ o) z }
( U# {# w3 f5 D# s0 a temp2=sqrt(temp2);
temp3=sqrt(temp3);
# A! ^1 t0 G! V; k0 X; J dblCos=temp1/(temp2*temp3);
# A, F9 Z9 T) p/ T! F pi=acos(-1.0);
# y3 k, y% W4 H0 |0 a' A- x angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
& v1 G! u$ L" j4 \+ o<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
5 q( ]3 {6 ^$ {# ^#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
#pragma once
2 M3 p+ _& y9 W$ R2 r% ]9 i/ @#endif // _MSC_VER &gt; 1000
/ p/ V& Z( y% R  d. G#include"definition.h"
typedef struct mychrom{
. ?$ N& u( Q- n. S9 `double chrom[MAXVARNO];
double fitness;//适应度
. ~6 {# N1 o- }! ], q}CHROM;
: Q( r! N4 \1 m#include "BpNet.h"
. H4 I8 f* u) U0 E3 ?' P& e  W, P////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
9 ]0 f" t' k$ `" cclass CGenetic  
{
public:
bool IsStoped;
2 \# [& A6 y" j5 F double dblAngle;
CHROM best;
, i3 N: s' L3 A Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
& @& Q9 f5 ]1 X, b  m6 Q int iBestNum;//符合条件的染色体数目
' I( [8 Z! ]8 c CBpNet * bpnet;
9 o8 [) A* ~" B, F7 Z4 W //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
/ S" n! |! k3 D2 r( r, b* h; w void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
/ u; a. i: A: w7 C' t, D& ]5 }, r double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
8 k: ]/ u6 F- x% o  {, C bool begin();//主函数
% Q7 H" R- ]5 |/ `& f" H+ Q  R! j void generation();//一次进化
int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
& w' w8 `4 X7 {1 {7 K# K) Q CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
% g3 `0 q, @/ }" d double pcross;//交叉概率
long maxgen;//最大进化代数
2 M1 m" ~; P. ~" X int iVarNo;//染色体数目
1 W9 J2 k9 {2 a8 ]) O double sumfitness;
0 u) ~9 @8 X6 l CGenetic();
" Y4 p7 Z7 ]+ J( ?& | virtual ~CGenetic();</P>
: s2 o, ?: Q" O<P>private:
  a3 d3 [2 L( D7 q- Y+ q double angle(CHROM ch1,CHROM ch2);
$ D: h+ s2 `5 ~0 c9 [ bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
6 Z5 h: z( K, P7 w double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
. i! i9 J1 S' Q7 g  [" l8 g double varminmax[MAXVARNO][2];
4 E$ q' y& d/ h, P* w8 b5 W: c2 K void init();//初始化，设置初始染色体
; i  c' Y# ^9 U1 o$ s9 s0 ? void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
% ~, C- h; j( `/ w* g( q6 } bool IsSetScope;

};</P>
7 ]. n1 T& j$ y/ l* D$ d$ W<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
4 G; l1 N7 d- q5 a( V% k8 ]; A: I$ M
* {8 M$ H. n# r. N</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>
, s# J8 J% X3 R+ t9 Y4 Y<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>