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

ilikenba

<DIV class=HtmlCode>
0 Y) ^9 V, c  U% K, P7 M" Z7 ^. o<>// Genetic.cpp: implementation of the CGenetic class.
7 l+ D4 i2 Q3 z' H//
//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
* G  ?$ b# U9 P6 T4 z" A4 ?<>#include "Genetic.h"
% S/ r* E/ G2 O$ }#include"math.h"
7 {# N4 U/ H; t9 c( \  V" `#ifdef _DEBUG
# I, Z; I6 \( o" P# `#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
2 W) H9 H& Y2 ?/ P2 V#endif
" z* r- J. Q3 S/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
; j9 I& {8 H0 k" L+ T//////////////////////////////////////////////////////////////////////
/ D/ X& Z! V  j8 E2 G9 s// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
3 j$ I- x6 \4 y' R- i$ {/ ?; F& O<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
- V/ u6 J4 _) A* {, ` pcross=0.9;//交叉概率
+ e0 b( ?3 }, h1 P( H4 h: K maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
gen=0;
IsSetScope=false;//还未设定个变量范围
IsStoped=false;
! B& }9 U  i' M for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
9 [% v2 v# H1 y/ @+ K# n4 ] dblCre=0.0;
dblDifference=0.15;
& @4 B) W" _9 k best.fitness=0.0;

initM(MATCOM_VERSION);
}</P>
, b3 e2 U/ ?- a" m( X( W: I<>CGenetic::~CGenetic()
: }+ X' A5 [9 {# q% y; x3 O/ l{exitM();
7 N2 T' G6 }6 o- y7 i}</P>
" y2 Y; c; K6 Q, P5 G, U) m5 H2 ]<>int CGenetic::rselect()
{double rand1,partsum;
" k& b8 O1 O7 F# h9 I int j=0;
partsum=0;
rand1=rand()*sumfitness;
do{
, N7 p" {2 F3 E) F: i  partsum=partsum+newpop[j].fitness;
1 q& c/ S' R4 y. V  j++;
4 x. d6 }' w; j }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
4 V/ Y8 b- H8 `; ~( |$ i}</P>
<>void CGenetic::generation()
- }1 l9 P" C6 O& q2 E4 V) Q{int i,r1,r2;
! V) D+ Z2 M3 n6 Q4 e& c CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
$ m* c* J/ n, g //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
" G9 l3 X& S2 w" `+ s: m% o- Q: x    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
7 I2 o* O" ^9 a: j9 X  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
: \0 A- H& e; X* E* s/ m }</P>
) {+ g( x% M! \2 Y, t9 l<> // oldpop,newpop进行调换
9 b: s# U! S! `% ^3 q4 Z0 H for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
( D5 r- L+ _# d% C, f# Q }
//从1到POPSIZE循环，对newpop进行变异
! a& p% J, M0 m4 D7 O0 w    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
( @" ?) t# w) o+ a* o: o0 }5 D<>bool CGenetic::begin()
, \# \! B/ D  {) A2 y2 \{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
/ N9 Z1 G+ O" G" F mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
}
: Q7 f3 W5 W7 y, i, I if(gen==0)
  init();//如果刚开始运算，初始化
generation();
5 i+ s) }. n, r gen++;
& r5 t  h# p& B& x, C$ a //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
: a+ f' N" L6 y1 W+ K$ S+ c* Y2 g :ispatchMessage(&amp;msg);
msg.message=-1;
. s( B( K9 T" |- a! B3 M$ n :ispatchMessage(&amp;msg);//这样可以消除屏闪
; f  R$ r: E. c& ^; f}</P>
<>return(true);
; s) m! `' e+ M6 m}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
( q$ t9 L$ ~- P. [: ^" ^ int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
" N* d1 T5 A8 z1 W, Z% w/ [& |+ m c=rand();
% ~& `9 K) t* f4 N; g  D% q) N+ y' H    for(i=0;i&lt;iVarNo;i++){
" A& C2 G! {1 U+ W3 D1 T! Q! ? oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
- I; ~: Q9 ~, x# g2 R# L0 d# w oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
# K" g( ^( t: w  e1 M1 ]  l: c3 J }
% S1 e# |: q% S3 ] else//直接赋值，不再交叉
! S1 K# u3 G2 [  T {oldpop[iPlace]=chrom1;
( l0 |" @( m# d# n- X, r( g4 P  oldpop[iPlace+1]=chrom2;
}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
" \$ n6 F7 T  k+ h, O* t. ~ return (true);
else
5 i4 ^( o, a' {6 @* R5 o8 B return (false);
}</P>
<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
* l) Q" q9 \4 ~0 Z int i=0;
3 X! Q& Y  L( w  o$ U CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
$ {7 z+ m, V. P! ?9 G  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
) ^& h; f! {9 R! g' d         for(i=0;i&lt;iVarNo;i++)
  _  e' A* G7 D0 c    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
$ ~0 V- p0 B5 e' F) {          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
$ @7 z  _8 v$ F" j, W. z+ W  j0 z: J     m=(double)m/(double)(2.0);
5 T5 E' H. T. J1 ^  }while(!identify(temp2));
}
& h( e2 {  `! X0 l% G else{
. R* w6 |3 ~8 e* l  ^2 t  for(i=0;i&lt;iVarNo;i++)
4 b" Y+ J. {3 h# K4 B     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
<>void CGenetic::statistic(CHROM pop[])
0 P# u8 ?' ]# [1 P) W3 }{int i;
sumfitness=0;
( E" o2 ^" C( ]1 H- K //循环，计算单个染色体的适应度,以及sumfitness
$ x6 r) p+ j1 w4 ~! [# M3 l for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
* w: U3 O8 Z7 a) J8 R& T: o   sumfitness+=pop.fitness;}
3 b+ S7 H+ L5 V9 L //选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
0 P6 n0 `) I* H, Y+ b if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
}</P>
<>}</P>
& o" D: z. [$ U  a<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
: k$ y2 C) l* B7 r5 G  B3 I. v<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
6 x9 a* Z& c: Y/ I; `  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
}
}
else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
4 w: t2 J- j+ r0 T) v& i: b }
}</P>
, N# }7 i; d% L" y% F6 x
<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
8 G* Q& y  K( ^1 ]* S<>}</P>
' k0 N: p; A  A<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
$ p8 {/ ?6 V2 u- {: O1 N7 t! c, `{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
% c& [8 a) O  X- E0 c) dIsSetScope=true; </P>
9 A2 z6 X% P. s0 a<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
8 ]! a5 Z+ \* Y{ double dblResult;
* c- R4 K% R. O  D; [ int i;
for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
& E/ q0 I  H5 O- Y( a  o' U: [ mResult=bpnet-&gt;simulate(mData);
1 j; o7 [- b" l4 u" z# B+ ` dblResult=mResult.r(1);
: g2 g  Q( m, h2 e3 B# K- C; y4 ] return(dblResult);
}</P>

<P>bool CGenetic::identify(CHROM chrome)
: u! ^0 T! Y) p{int i=0;
bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
; u& D# Y3 X+ R  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
8 f# N9 d- }' ^) J; d  {IsOk=false;
  break;}
+ _- J  r$ F' W5 M }
return (IsOk);
}</P>

; q/ Q3 o, b  S+ `) P# C; ^<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
+ \+ m- j% M, Z0 a$ P5 R- n4 U: l{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
1 B- q1 o% u0 U for(i=0;i&lt;iVarNo;i++){
4 h. @& i, j& L& R8 _+ _  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
! P! A9 `6 Q* K/ p4 h  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
, G& M1 r0 a- ~* ]( l# J6 `* e( L  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
6 K. s/ Z8 g1 \; w# |0 h. i1 N# l  temp3+=dblTemp2*dblTemp2;
}
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
1 O8 [( Z/ F5 K+ _2 b* J; _ differ=sqrt(temp1)/sqrt(temp2);
return (differ);
/ t0 C& N' S0 z1 ~% d+ K) Y}</P>
<P>bool CGenetic::IsNew(CHROM ch)
0 M% Z% n9 p. f' l3 a{int i;
bool IsDifferent;
! I( I' d) T  W IsDifferent=true;
4 ]9 x7 q) s6 P9 v for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
& i7 H& K6 s, o- l5 w$ z  J      break;
  }
8 ~( l: i4 Z+ Z8 E2 B' ^return (IsDifferent);</P>
<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
/ k! Z- e3 ]9 O2 ~7 E3 Y4 | 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;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
) L; E9 w1 Z1 K( u7 g, R; G; l temp2=sqrt(temp2);
. p1 g4 L) B  C( U  [* X+ c* ? temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
( {& [& [  U& ~3 Q5 j/ U pi=acos(-1.0);
5 s( L$ p! ]/ f% v angle=acos(dblCos);
* f1 p6 p5 S. @7 f& ]0 l( P angle=(angle/pi)*180.0;//转化为角度
# E, t( M) N& y. b( \  S return (angle);</P>
<P>}</P></DIV>
7 t! z9 B" ?+ C: H<DIV class=HtmlCode>
% X3 T) }4 f; m4 }<P>// Genetic.h: interface for the CGenetic class.
/ h" g2 W3 C, G. v/ B//
4 [2 |, D9 N9 a9 F8 X2 }//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
. T* j& p7 h$ L7 R" X. _5 g#pragma once
# G8 C5 s/ i" T) _# Y% H#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
6 b+ I* p& }# \9 d4 ldouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
5 j0 F6 n: F! E! {* A, H3 l, C#include "BpNet.h"
: v% l7 V; `4 K( r' o////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
. g7 I3 T. Z* \$ [& bclass CGenetic  
{
public:
1 K* z7 G9 ^* S5 B* T  f bool IsStoped;
$ X$ |5 _; y: E1 z6 d# Z double dblAngle;
( ]3 v4 O4 {7 Z( q7 I* f! F CHROM best;
Mm mData,mResult;
8 G/ }: s. \( J9 U& ]1 v; ^& c double dblDifference;//差异〉改值的染色体视为不同
  e+ W' a( ~8 y1 x  Z" B9 y double dblCre;//适应度&gt;改值的染色体符合条件
5 I+ M" @; E0 O int iBestNum;//符合条件的染色体数目
( I& O1 J/ B1 P CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
* l6 `  U5 w! y- A( P void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
5 i/ `' {. c# D% |! ? double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
void generation();//一次进化
int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
4 j! `( J, y7 ^( \ double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
double sumfitness;
, Y% j$ @4 c& G4 m: ^ CGenetic();
virtual ~CGenetic();</P>
6 W6 k, X% X2 v1 `( n. B/ `<P>private:
double angle(CHROM ch1,CHROM ch2);
. j! X4 ^* y3 g bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
( J- N# C" n% x! r' g% j void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
( x( u; j$ C) d  U# S- M# u bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
( [8 E2 c. N' [2 h9 w void cross(CHROM chrom1,CHROM chrom2,int iPlace);
$ o! U; Z- H4 l% A3 |: Z& Q* I bool IsSetScope;

};</P>
<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

) @" H, N- n: Y' d</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>