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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
: w" [" j% u8 A; V" y+ Y$ b//
//////////////////////////////////////////////////////////////////////</P>
  R; I* U% ~9 O1 z- D! Y* W1 q, _* o6 h% Q<>#include "stdafx.h"</P>
4 \. A6 f% K: O6 c7 y<>#include "Genetic.h"
/ e8 P* N0 r3 C/ \7 M+ P* e3 b#include"math.h"
. ~9 j* k! M1 N, K#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
. T, X% S; H# V' H$ ^! L3 z#define new DEBUG_NEW
#endif
1 e( ]4 D. Q; c, h/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
9 Z& p) E, {/ D9 U  x0 i2 N/ g//////////////////////////////////////////////////////////////////////
+ I4 p, V9 w; V/ q) d// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
$ E& C! |4 k; [1 R. D<>CGenetic::CGenetic()
# `+ @8 @5 }! r{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
+ y* V$ |# ]5 v: w, \5 ~ maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
+ n. v4 F1 l' |9 P8 C: _$ T sumfitness=0.0;
gen=0;
6 |2 P' V/ s6 r# \* P IsSetScope=false;//还未设定个变量范围
IsStoped=false;
for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
* ~  B$ @6 n# O, G dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;
( i6 K/ j8 Y4 u4 P" q* W/ S3 K% J$ i
initM(MATCOM_VERSION);
}</P>
<>CGenetic::~CGenetic()
" V, B4 W( D0 H# O! Y6 p. ]( @{exitM();
}</P>
<>int CGenetic::rselect()
. p7 Z' {& I3 w2 X7 {{double rand1,partsum;
6 s* U8 j5 \- j' D int j=0;
& T! Y6 q+ p; U+ Q  |  ^/ L0 ~ partsum=0;
! J6 P* m9 `; \  F6 J rand1=rand()*sumfitness;
6 X7 z8 X: M5 t- T/ P do{
  partsum=partsum+newpop[j].fitness;
! K; N& Q6 L+ ~, p5 D0 G: f0 Z  j++;
: y" A- p0 i# L' p8 \7 {$ y6 }9 s }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
' m3 e. ~+ }# Z$ U( B}</P>
8 @% B6 ^8 X0 i9 d<>void CGenetic::generation()
{int i,r1,r2;
* l3 X, v, B8 X% V+ U CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
$ j' r: g& T; M% r5 c- F* S5 G& k, n //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
( `' p$ r3 Z; S; g3 s2 H2 M3 D: X  r1=rselect();
2 f" ]# K2 S8 f# M9 `$ j) g# T' K  r2=rselect();
2 }( T( a( n1 t9 O0 S  cross(newpop[r1],newpop[r2],i);
# M7 \1 i$ d9 K! @7 N, Q8 L }</P>
8 l7 v; O1 }+ X0 ^/ G  _' ~6 l<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
8 Y: Z+ I& v2 |, e! H8 d3 m  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
! ~+ O5 b5 q+ k0 i     mutation(&amp;newpop);
! X. |9 q! p7 v3 V}</P>
<>bool CGenetic::begin()
{MSG msg;
" ]7 ~7 z  m/ m# ], z mData=zeros(1,bpnet-&gt;iInput);
/ m4 Q& j* ]) k3 }! ?( M2 h mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
( @: }- v0 n  \5 R# `. |{if(IsStoped)
  break;
8 H3 b$ q' U8 I) b8 [" \; G if(bpnet-&gt;iOutput&gt;1){
( V$ h, ^' c) ^ ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
# h7 D: s4 h/ c3 U return(false);
+ j9 W8 s$ n4 |" T/ r6 U* ]+ p- t }
if(gen==0)
  init();//如果刚开始运算，初始化
5 a! N4 k9 @& \; x* D generation();
gen++;
# S& |2 L& W: A/ S1 n //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
- U7 @" g' Z. z5 t- u8 I :ispatchMessage(&amp;msg);
$ B, E3 r/ H6 m+ z/ O/ Z3 m5 R msg.message=-1;
: m' m2 D- n5 q: D :ispatchMessage(&amp;msg);//这样可以消除屏闪
& L, H# i& L$ o}</P>
' d5 p) f3 x7 V/ ~2 m$ l1 i<>return(true);
}</P>
2 }. {# N8 s% K- V+ p/ J1 ?  S3 r<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
- D  F# [9 r( H4 C{double c;
9 w5 y* X* _/ B; M9 r# z7 T int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
& q1 r7 A- B% }, b" \: z do{if(flip(pcross)){//交叉概率
/ `) x- P. ^! C c=rand();
    for(i=0;i&lt;iVarNo;i++){
: X! ?# Y+ w! i6 d: x: e oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
, N" Y  t, ]" E) U2 H oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
}
else//直接赋值，不再交叉
- u" E3 H% d0 x {oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
& j; h, z  w, v<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
2 U- Y9 w% d1 G7 W3 H# y* T6 jppp=rand();
if(ppp&lt;=possibility)
return (true);
else
+ ?2 x* T  j' F. Q6 }6 a return (false);
4 |: t( w/ p) l7 H/ f4 [, B9 H}</P>
+ U) r( {( r) U" v) w( Z<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
. [& T) K& g  ?; n8 J int i=0;
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++)
    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
1 X0 |! w7 @: C4 d          for(i=0;i&lt;iVarNo;i++)
" G1 r0 i* z+ u3 [' E     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
, C; _) {4 K& I3 W3 M1 d' f     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
}
4 k. [1 c; S. { else{
6 F! a( ~3 |; g) f  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
5 y4 d! v" x! o. p" b& X8 X }
2 u# J: k5 N" N/ |3 u+ l- [ for(i=0;i&lt;iVarNo;i++)
5 B# }2 C5 e4 R9 T! C  chrome-&gt;chrom=temp2.chrom;
/ h# ^$ S4 M* Z! Z$ a/ Q8 j}</P>
$ ~) x( F+ p9 g8 d* ?<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
" }% Z: a- M4 c$ M) \% H //循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
% J1 S; K/ s4 _   pop.fitness=CalFitness(pop);
: z7 C) j' h/ p1 T4 f2 D/ F   sumfitness+=pop.fitness;}
% a7 e7 S- e9 q+ ^ //选出符合条件的染色体
6 f8 ?: F, _3 I for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
% K" h8 k7 s& h4 q* Q  bestchrom[iBestNum++]=pop;
" p2 @9 ?7 s/ Y if(pop.fitness&gt;best.fitness)
6 W" p6 C1 b) |, [  best=pop;//纪录最佳染色体
) n. P; |4 _0 u4 q9 V6 C}</P>
<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
9 N" d9 u* |) X) mint i,j;
srand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
, i% i) r! \* q' e* R3 m{for(i=0;i&ltOPSIZE;i++){
9 h" q. k/ U8 ~& n5 x for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
}
0 C+ y4 \4 ^4 N}
else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
3 s7 Z3 d6 D) w  I. ? }
}</P>

<>double CGenetic::randxy(double x, double y)
/ w3 j6 _9 ]2 t8 H! y' X' N{ return (x+(y-x)*rand());</P>
4 b* a$ u1 M& A6 w8 J& d<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
- C, b' D3 d' s. ?{int i;
' w7 t/ G0 E9 E* R/ Xfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
, K, U& I- K) Z- [# r varminmax[1]=scope[1];//最大值
# N' `6 H5 @( H1 ^}
8 r9 {' J8 m! @: JIsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
( p$ B' @& W: A1 X  R0 B{ double dblResult;
& |. g# M+ _5 Q' D* V& m6 M int i;
7 r+ r% `( J7 T6 P! i2 @) X for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
  ^: p" y+ A2 o# {& I  r( Y% ? mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
7 ?& w1 D8 H7 _; m3 B return(dblResult);
4 l- i7 A* d  t) [' @5 y}</P>
  r/ u, A5 k  {8 `
" i% M, i4 C% l3 C" l/ Z7 U  O9 h<P>bool CGenetic::identify(CHROM chrome)
+ V6 j/ _; m9 |5 t; w4 B{int i=0;
$ L3 {  h) D* M bool IsOk=true;;
0 H6 l0 n' |  u/ m# ^3 k for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
$ D; W7 W$ V2 C, c+ w  break;}
6 ?! x/ o: m. P- ~# b/ D+ a }
. s1 I# G5 W* |: s return (IsOk);
% t- A; o3 Z6 h9 r}</P>
& A9 N0 c1 p6 _, w4 \1 e$ b
8 M/ F! K* S. E$ W$ i<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
for(i=0;i&lt;iVarNo;i++){
7 f' a9 J% R% i! s- U  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
$ @" H* C9 d+ I$ q- n. f temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
. A4 E- C  T9 F8 Z8 _ differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
/ X7 V2 E! t- L6 }7 G0 ]{int i;
+ w. Y' |3 V% k+ P% a) ~ bool IsDifferent;
+ {% l3 q2 T8 Y" ~, y% N. E IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  S) S" m2 r( q9 P  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
, Y* k- M5 I% v, G& \  }
6 Q* N3 Q: M+ ~+ Vreturn (IsDifferent);</P>
" a$ P7 D/ {  h" A/ V<P>}</P>
% k6 l4 M) x6 t1 h  `3 j<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
$ O3 H- t1 C5 X7 B  D; i2 _ int i=0;
double dblTemp1,dblTemp2;
# w4 j6 M6 O1 b) [0 G for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
! f0 U) z- E8 h! p4 J+ C' ]2 Y  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
; s# i$ [1 F7 d* ], W7 f, z  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
& U, ^0 Z+ ~" k$ N5 O temp2=sqrt(temp2);
. T0 i, {$ X7 E: ^: K temp3=sqrt(temp3);
2 e) F' H" D8 n$ B8 V; n7 V4 Q& A! A; D dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
! }; _4 Q5 R2 X- V2 I0 r7 A# M- ` angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
& v. O8 D( J8 P% _# I- p return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
: |& R3 |7 l6 M- }. X* k% Z2 G9 m//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
, @5 H* ?4 T: O2 X+ K4 ]+ P% w2 D; i#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
* i2 _) `& p0 R  ^( Z<P>#if _MSC_VER &gt; 1000
#pragma once
#endif // _MSC_VER &gt; 1000
$ O# a+ z1 v$ @: C- V: v. E& ^#include"definition.h"
typedef struct mychrom{
double chrom[MAXVARNO];
( `; M7 H/ x5 p6 w, ]double fitness;//适应度
2 h4 w2 x" m  {% Y& T+ f) B3 g}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
: Y# c% N3 d; ^4 P/ e8 a{
$ Q( e0 p% B$ j5 P& h% npublic:
bool IsStoped;
6 S8 w1 m$ x: W1 w; u: Q+ E double dblAngle;
8 ?( s7 L- [* A CHROM best;
Mm mData,mResult;
- r3 }& L$ m% r  H4 y1 k! p double dblDifference;//差异〉改值的染色体视为不同
) O3 f3 z' V8 W" u double dblCre;//适应度&gt;改值的染色体符合条件
4 ]8 Z, L; W+ O( o: H4 ~ int iBestNum;//符合条件的染色体数目
9 d* H# \# O  H& {+ |- G CBpNet * bpnet;
//double (* obj_fun)();
; b+ b6 B) i% B6 |* {. i double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
3 |" e( x) A/ I' t' z. p% { void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
# F6 V6 N5 g* @* j; T* h+ | double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
. x1 w" v4 y" F& d: Q5 J' l CHROM bestchrom[MAXBESTNUM];//最优染色体
$ [( _+ l; O* [* ^! ^( r bool begin();//主函数
' d6 `2 x7 m) q6 b void generation();//一次进化
. v# v" g% N. O3 O+ V7 ?5 d- p! ? int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
( k5 z: a) x. w5 T double pcross;//交叉概率
long maxgen;//最大进化代数
* O" f% v3 w5 g6 |+ x int iVarNo;//染色体数目
double sumfitness;
CGenetic();
' M' x  s% B# @; F  m) R1 ^ virtual ~CGenetic();</P>
<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
) O; d/ k3 _3 h8 J# M- ^+ C) b double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
4 `5 A* T, a" I4 h4 G) X# Q void init();//初始化，设置初始染色体
& r+ n4 q) x: D, X1 r1 N% ^ void mutation(CHROM *chrome);//对新染色体进行变异
4 }3 H  w7 V* V/ k( @+ F# Q9 ^+ W! ~ bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
; U2 R2 x: [$ Z/ t void cross(CHROM chrom1,CHROM chrom2,int iPlace);
& z; l4 ?8 ]% k- D3 o1 N bool IsSetScope;

};</P>
( w2 f( [. K+ a3 s# G5 q<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>
1 M6 s5 i! M$ K1 g0 M( r<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>