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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
- z7 b' O% r- v! o2 J) F% y3 z3 w: g//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
, U; C# ^; ^$ {1 ]$ U: w<>#include "Genetic.h"
#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
( l2 j- e8 v0 `, c- ]#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
) C6 r3 p2 p, c' x/ y//////////////////////////////////////////////////////////////////////
1 e  a7 ~3 A& y) B  x! `// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
3 G7 s0 S/ ?& e8 H4 i. o0 o$ a<>CGenetic::CGenetic()
! U8 ]2 _2 V, L{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
* }( ]' I# _& b. I% D, }' q' ? maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
gen=0;
* {+ K8 t7 _$ o' Y IsSetScope=false;//还未设定个变量范围
IsStoped=false;
9 R; j; ~: O- D% C# I for(int i=0;i&lt;MAXBESTNUM;i++)
7 B# g/ X# g2 S# c; x; }- `- a7 d   bestchrom.fitness=0;
iBestNum=0;
dblCre=0.0;
* M2 [9 b( h- X; G; b1 j dblDifference=0.15;
best.fitness=0.0;

1 A* |9 [' m; e4 i initM(MATCOM_VERSION);
}</P>
<>CGenetic::~CGenetic()
# n0 k5 w- b  i' \{exitM();
}</P>
: _" e1 F+ Q" F/ x* [& [6 J1 @" {<>int CGenetic::rselect()
{double rand1,partsum;
int j=0;
0 ?6 I0 }- b0 ?: t partsum=0;
0 y0 S/ ~: J; H- b" C# f rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
( g* m% r- z7 S# G2 S return (j-1);
}</P>
2 Q/ _  P* U  x1 P( [+ a<>void CGenetic::generation()
{int i,r1,r2;
: i5 E8 x7 r1 |9 Z3 l+ Q, ` CHROM tempChrom;
( V4 H) n2 z1 A //进行统计，计算newpop单个染色体的适应度，选出最优染色体
' E/ k" _( l, F' H statistic(newpop);
  n9 X" `- N5 l$ y  Q* T' N //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
- D/ w! y, N4 C" ^0 r% K    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
/ Z0 }  ~5 m' O0 Y. d- U  r2=rselect();
6 }, T, x. i8 K8 [% x/ y) |" D  cross(newpop[r1],newpop[r2],i);
% z- `$ e$ R" Q8 Q! Z }</P>
<> // oldpop,newpop进行调换
+ F0 v7 [2 s, Q" y  \ for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
3 \; y0 A) g$ L# k/ F1 {& {; b0 p  newpop=oldpop;
  oldpop=tempChrom;
6 H6 \& o9 R/ g" h- x$ C  R }
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
& G1 c: E* |, T+ p6 a5 i     mutation(&amp;newpop);
}</P>
- Q: p6 t5 v6 w<>bool CGenetic::begin()
4 [+ h2 ?3 n% y, `" \: G{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
' }. {. @+ W$ ]) z, x" {* W1 Q{if(IsStoped)
' s# ^4 ~' n( y! v3 @4 @; Y  break;
; x' X; p. F- ^8 K" C if(bpnet-&gt;iOutput&gt;1){
7 b, T# @" k. M9 }- A0 a ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
$ t" Q3 Y: y1 A) o: v; y/ Y9 T }
if(gen==0)
  init();//如果刚开始运算，初始化
" ]4 X" b% U6 B  M; ^4 j generation();
gen++;
//防止假死机
& B8 _# ~) n/ Y :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
% g. [. O8 G* {: i. A2 `) g :ispatchMessage(&amp;msg);
! F3 j1 \6 T! J0 K msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
<>return(true);
# R# g+ l) ]' O! ^( m8 O6 u% B}</P>
<>
2 _1 |7 e7 B5 n, a, ]( ]" Lvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
2 C. ^4 C! O2 H  C6 ~{double c;
int i=0;
' b0 N' t2 A$ b. p" l//以交叉概率进行交叉，并对交叉后的新染色体进行判别
3 G( f4 S' Z& r. n7 r$ N//循环，直到产生合法的新染色体
1 Z, f9 L4 k' i- k3 ]# T9 y3 V do{if(flip(pcross)){//交叉概率
6 p6 }" `4 n$ H* p& Z' \/ S; { c=rand();
    for(i=0;i&lt;iVarNo;i++){
0 V# r4 A5 y2 R. z2 Z+ X oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
% b2 L4 p6 @! F oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
* d& v, @0 F8 E0 J }
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
$ y6 U$ _* \" P9 j7 J  oldpop[iPlace+1]=chrom2;
& m- P' K9 s* ~ }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
, Z% O& x3 n+ @: I; r' r* g2 A8 G<>bool CGenetic::flip(double possibility)
{double ppp;
5 t- R$ [$ v  z4 |4 H6 a5 Hppp=rand();
if(ppp&lt;=possibility)
return (true);
else
) O& w, V; R4 U/ j' _1 d7 C4 k/ @ return (false);
}</P>
<>void CGenetic::mutation(CHROM *chrome)
' ]" P6 P( `. Y8 Z{double m=10;
int i=0;
) n; B" k. p8 b% J0 W CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
0 h. _7 ^& n, M8 n$ T% H# q  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;
9 S; R+ t+ |$ ?  J# _8 V" W          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
/ ]7 @4 i+ |9 n" ] }
else{
) n% A. N: c. V# j  for(i=0;i&lt;iVarNo;i++)
0 T1 S' |# `: f% m. n$ h$ {     temp2.chrom=chrome-&gt;chrom;
. G" X0 Q1 w, u5 S }
for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
* _4 Z. L: {% L  Z}</P>
4 B4 A: R+ r. q( S/ \5 q# ]<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
0 u$ Z# _  U9 G) B6 n8 z //循环，计算单个染色体的适应度,以及sumfitness
9 C9 ?) z& L, j% P+ N' e for(i=0;i&ltOPSIZE;i++){
& q) O, D* J2 u/ i. j9 r2 T   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
2 K1 ?' K0 z, X; ^) K, C# ?. _9 x for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
4 j! n  \$ h9 b% e  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
) T8 M9 A& n9 ?1 x1 X5 c6 b  best=pop;//纪录最佳染色体
+ [( `$ x6 C6 s, X}</P>
<>}</P>
$ o) l. Q' R/ F$ [<>void CGenetic::init()
{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
2 l! c+ s$ [2 q{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];
+ l. T$ y* V* ], o( m* P5 g. ?4 [ }
}
}
else
3 s- F$ ?& K  q: ] {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
" g7 P9 i# f1 B0 A7 `5 v# f: j  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
: k/ n. A- e4 A$ E }
}</P>

<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
+ z5 |; C" P! K* p9 k0 U- d4 Y<>}</P>
" W& l6 u& f5 _# [: x<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
8 i; _. |( f0 ~8 Wfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
$ J. H9 G# g& \0 e: n4 q5 W/ _- o}
! }( [7 d$ N' a$ `  h1 R5 t3 v$ ~IsSetScope=true; </P>
<>}</P>
) _" H& h& `9 p5 @) ~. H<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
! o; t6 D6 {# `4 {5 O( A int i;
; A+ h; k/ E" e, H) p, D for(i=0;i&lt;iVarNo;i++)
; D6 W: ?1 B9 p1 k/ q% I  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
, ^" h3 b0 P/ d3 r8 c$ x dblResult=mResult.r(1);
return(dblResult);
}</P>

" `8 r  ]% d! G  N  z<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
% F- l5 b+ Y" |  P2 X, G for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
6 s9 K4 C' y! k/ c' @  {IsOk=false;
  break;}
}
0 n1 l& M- e% y5 t+ P/ Z) n2 d return (IsOk);
}</P>
! E. b& T: A' @" _! N: i
<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
7 @) o) N. T) \* v8 F: x8 R7 N{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
  d) h6 Z+ l  D' X8 C+ y int i;
& P1 K. @0 t( V# T" ?8 i for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
" w& @+ c! q0 a9 t3 E! K- s  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
5 `, s& `( F& q- N. i  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  O2 D- g, |" k2 j  temp3+=dblTemp2*dblTemp2;
2 ~  ?+ Y  j8 d# e! U }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
) v+ x5 i9 L0 q% q: N differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
{int i;
6 n) e- ^2 T9 a! i$ U9 w bool IsDifferent;
' y5 q& n) ]# i1 f' R& ^% h IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
0 K3 W' g6 D6 C8 o' F7 g! V  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
: T# N  U5 B+ N" {+ O. v      break;
$ E6 H; A7 P  F! Y/ o  }
return (IsDifferent);</P>
8 f) T, R# J! o<P>}</P>
3 [5 x& u2 W# v: b9 p  H% o7 i<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;
double dblTemp1,dblTemp2;
% \! a" y& }8 @ for(i=0;i&lt;iVarNo;i++)
& N0 m0 ^! P4 d+ M+ r0 ?; F" a {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  z) Y! ^$ M* T, j9 f. E' o  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
3 U% a- u4 x$ K3 T; `$ F  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
temp2=sqrt(temp2);
temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
3 {3 z7 i+ k* p3 h; _" ` angle=acos(dblCos);
- g. Q% X( D$ e8 t angle=(angle/pi)*180.0;//转化为角度
$ X# H- B" N' d! L return (angle);</P>
<P>}</P></DIV>
  x8 j" u: [# q) {5 J% ?7 m- M<DIV class=HtmlCode>
; }$ p+ N; V, n! @7 ~1 V, `0 L  C<P>// Genetic.h: interface for the CGenetic class.
//
- @3 i! o4 `9 w' ?//////////////////////////////////////////////////////////////////////</P>
% l( i' |* H7 m6 o9 z( @  Z8 m: M<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
9 C7 K; c- v- h+ b2 L* n#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
+ j/ V3 d4 |& \1 i: ^; d#pragma once
) w7 K/ I9 s- n" u7 |1 Y( C#endif // _MSC_VER &gt; 1000
4 N/ n5 `% }/ A- \1 T& v/ x- ~1 g#include"definition.h"
4 Q3 M0 Q, c4 {& e, n  k: K; f4 Ktypedef struct mychrom{
6 `" d5 h' L3 J- t$ ^" C: Pdouble chrom[MAXVARNO];
2 j  r% O! V% r/ Q5 c2 odouble fitness;//适应度
6 r2 z/ R9 P3 Q# D/ o& f6 B8 O}CHROM;
9 s# z0 m3 F) F$ q#include "BpNet.h"
, k) T% ^+ H" v$ J////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
& ?4 K1 e  f0 x{
public:
" a& _. C" A1 L# \9 H) X6 l bool IsStoped;
- ^5 R/ g/ j2 K- O+ r" m double dblAngle;
( `- y6 y+ o% ~1 Q, n8 u- | CHROM best;
Mm mData,mResult;
7 y% Y  W8 k- G' E! n5 a. S double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
# z# O6 I) X" [5 S: A9 F: } int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
5 U7 q- e) Q9 C& y4 h0 a5 w //double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
" a4 [' W# F8 e2 U* s long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
1 S$ _2 P! P% T void statistic(CHROM pop[]);
" G1 a* i/ k7 O0 o$ b4 G CHROM bestchrom[MAXBESTNUM];//最优染色体
2 N( |1 _  B* w' Y5 D5 P bool begin();//主函数
void generation();//一次进化
int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
- W. V$ g* E  [: z; \, C CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
0 R: F0 j4 \1 f8 J double pcross;//交叉概率
6 c  Y; Z2 T$ H* B% | long maxgen;//最大进化代数
int iVarNo;//染色体数目
double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
<P>private:
% I: P( [0 O, h6 f double angle(CHROM ch1,CHROM ch2);
* {3 f+ x, G6 k. k/ H bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
8 g2 h* O+ _& e8 m* } double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
# ^+ h& i1 ~- l<P> bool identify(CHROM chrome);//验证是否为合法的染色体
" H, z: n7 X$ E; Y1 f double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
2 ~. B8 z! \" M* f; W bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
7 e9 H; x$ a" u& g) r$ y$ S5 w void cross(CHROM chrom1,CHROM chrom2,int iPlace);
4 D# ^. v  _) q bool IsSetScope;

: i* k! C0 G$ }4 E) ]2 G};</P>
# C3 D, x( B( }- |+ U# ?<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

, _8 {! d# ?: t& Y  Z" }</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>