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

ilikenba

<DIV class=HtmlCode>
6 X; Q9 x# W9 C, x. M# [<>// Genetic.cpp: implementation of the CGenetic class.
//
! h* {$ X+ |' \, L0 C: e# |//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
7 J( k1 D6 G5 m7 p" V<>#include "Genetic.h"
1 d1 K' R& r! t; X" s5 @, a#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
* T; l7 j) \: y* nstatic char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
3 ?: w  P; x2 K. f! S9 _% a//////////////////////////////////////////////////////////////////////
+ Q+ J" q5 \* |+ _$ ]+ R// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
( \* t8 T- N/ E5 r: ~ pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
. [  I/ b3 B$ A: c( y1 H0 N iVarNo=0;//染色体数目
: }8 n: ?0 O; g% ~- h  Y+ F6 { sumfitness=0.0;
. I# {! g7 M& E gen=0;
IsSetScope=false;//还未设定个变量范围
IsStoped=false;
# N8 a9 a1 v/ C for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
9 B4 D. W  ?: f/ v1 l  ~0 z0 M iBestNum=0;
dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;

6 g' J+ V0 v* _+ j initM(MATCOM_VERSION);
$ n" a7 @" R) f9 ] }</P>
<>CGenetic::~CGenetic()
$ [) a, {' o1 \0 x6 D. |{exitM();
}</P>
<>int CGenetic::rselect()
{double rand1,partsum;
5 B; X  n8 \& E" g- t; I int j=0;
partsum=0;
% E  \) a8 `1 u, Z/ Q  ~6 v: n rand1=rand()*sumfitness;
1 t4 A" r8 D% X6 Z; q  O do{
  partsum=partsum+newpop[j].fitness;
  j++;
' k, O/ T. a- D; q$ ` }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
% O( l& `) y4 [; Q% s5 T return (j-1);
: P; G* C  d# w* S}</P>
<>void CGenetic::generation()
{int i,r1,r2;
CHROM tempChrom;
7 T3 B5 Y- F& g+ V8 u //进行统计，计算newpop单个染色体的适应度，选出最优染色体
3 t* d& y% K1 t, \ statistic(newpop);
* u" x" I- J; ^; y2 r( O8 s& j //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
* h. y, _0 m, H  D  r1=rselect();
  r2=rselect();
6 ]# ~2 z- _3 G* O, \7 d0 J  cross(newpop[r1],newpop[r2],i);
}</P>
9 A% B& `7 g; w<> // oldpop,newpop进行调换
5 e( B, y5 b5 q4 C for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
6 M8 ~+ R6 O& b7 I  newpop=oldpop;
, j+ @* w" `4 d- \6 K  oldpop=tempChrom;
( h* q1 e  Z3 F8 ^/ @ }
. J5 m0 t- Y) X3 Y8 p //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
# h4 e4 Z' F: O6 B, T}</P>
<>bool CGenetic::begin()
{MSG msg;
) I9 t  s2 }% x9 n1 z8 [ mData=zeros(1,bpnet-&gt;iInput);
$ j4 R! \0 ?% `2 o9 _% q1 o  ` mResult=zeros(1,bpnet-&gt;iOutput);
8 v+ K0 x' I' j/ a, z) Yfor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
2 `! H$ _. Y+ V+ d3 c8 S! H4 U ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
  y& v/ T2 P$ S return(false);
}
8 m2 W0 W/ i/ y" @- N' s9 r if(gen==0)
  init();//如果刚开始运算，初始化
generation();
( M) y6 M! @# P8 ^" j1 P gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
' B4 N4 B) r4 f msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
1 p1 N2 H: u* n8 S  I- g}</P>
! h& m6 S3 _/ |, T) H<>return(true);
( {$ X6 t7 s9 E}</P>
<>
$ M6 m0 H4 I) ~7 W; }& t4 P# I5 M" Rvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
1 j  m8 K1 N2 p- w int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
3 I1 Y* Y  J' L2 U" i) _//循环，直到产生合法的新染色体
+ n8 s0 n$ }1 E4 b6 W8 T do{if(flip(pcross)){//交叉概率
c=rand();
    for(i=0;i&lt;iVarNo;i++){
; h- x, A0 ?6 x7 @; j1 ~* p! E7 ? oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
8 ]+ {  a  W6 ]2 ~7 L* B  o& D) ` oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
8 c; q' l' k. _+ _1 ^0 r }
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
2 A* h, g% J5 t( h3 x; M' h1 ? }
6 v. ^# z" _; z- O7 d) \}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
: C- \2 S) q3 [9 L& r7 R% |; N$ S<>bool CGenetic::flip(double possibility)
1 H5 c4 b' t1 v. ~" O3 ^  w1 ?- s{double ppp;
ppp=rand();
# P8 U. F9 `* ^7 j" M& M: u6 r+ rif(ppp&lt;=possibility)
. a; a5 ]  t: M2 Q. }1 x( [ return (true);
0 ?' @0 P: Q, i  oelse
return (false);
. `. L/ K* I/ U+ ^% k) U6 e}</P>
: q" D9 W8 H" v4 C: B3 E<>void CGenetic::mutation(CHROM *chrome)
/ E% J3 ?( L. |{double m=10;
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;
          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
1 m/ L2 _9 n7 _0 V8 V( `1 ]     m=(double)m/(double)(2.0);
- h6 h3 s) C' x8 q  }while(!identify(temp2));
4 g. x$ p% u5 `- ]' R }
3 @. ?) Q. L% l3 p) x) Y else{
& \% g7 k" N+ T: f" Q, O8 w% ]8 q, l  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
$ U7 _$ U5 _' X( e) P  chrome-&gt;chrom=temp2.chrom;
}</P>
  z- Y( z4 E7 v% a+ m<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
% G& e! p4 |7 y8 D4 o8 v) C //循环，计算单个染色体的适应度,以及sumfitness
7 r- n' C* Y4 o2 x! C8 K6 f for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
+ O% o6 w) s; i5 E/ | if(pop.fitness&gt;best.fitness)
9 N' B5 a" U" j  best=pop;//纪录最佳染色体
}</P>
' O# t# U. l; [6 H<>}</P>
<>void CGenetic::init()
0 N; s! a8 A  p% C{//对种群进行随机初始化
0 ~9 `0 O, J' U1 N; n- Uint i,j;
1 ?1 u0 |' z# Wsrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
1 [4 N" r, N% [) S/ L# s, I' L7 E for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
1 ?5 m) w% p, |  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
" Q$ ~5 t6 q3 K: F }
}
0 e& g) d( n* e( i* h! M}
1 s0 X, @( n4 |1 T" Y3 X' B- i else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
+ T" k# F7 t; `9 [% M$ I$ r' f }
3 U1 @% F% S' f0 S}</P>
  F9 P4 t9 d, n% I9 X! a
<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
3 X- w+ z' X( K  K3 G5 M5 g- i<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
" O& W- _+ m6 y7 L: V5 {- _, `IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
& A$ C* l; Y! g6 ?1 @0 Q int i;
/ ]  F' p" P; u1 W for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
( l. o* P6 y( `1 r9 }% c mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
return(dblResult);
! R7 w! X: `3 z( k3 p}</P>
3 e4 \  E( ~9 l! B9 s; m
6 Y9 A4 p8 B4 G<P>bool CGenetic::identify(CHROM chrome)
# c! I) w; }6 v- F7 \% S{int i=0;
7 `! o& ~# I4 u2 Q* v bool IsOk=true;;
+ p, k1 ]* m6 ], ~2 X5 ] for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
, C) ?5 E5 `) i, L: d1 z, e  {IsOk=false;
  break;}
6 ^6 C* S7 |. y* [, b }
return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
' L9 z/ G' ?' O7 U7 w$ y4 @& ]+ O int i;
# y7 N( L0 I- B6 B$ u6 D) F0 s5 M for(i=0;i&lt;iVarNo;i++){
9 b! v/ l- }7 S( R  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
5 D& c) ~$ P! d; ?  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
; c1 d% ^2 v+ G$ c4 z) c: Q! B  temp3+=dblTemp2*dblTemp2;
' B7 ~1 U- O( a }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
$ M0 ^  d2 b7 L differ=sqrt(temp1)/sqrt(temp2);
return (differ);
5 P  R! C# O# `}</P>
% B7 @, u: n' n/ ~& U<P>bool CGenetic::IsNew(CHROM ch)
+ Y. z1 z, ?- o$ [+ l{int i;
bool IsDifferent;
IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
+ z  V2 |* E# e& F  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
' V; n8 E: w% C2 S/ t9 L  {IsDifferent=false;
      break;
$ i: H4 v* z# T9 R  m' V  }
& d% n( S9 m% V: A1 Sreturn (IsDifferent);</P>
9 V% B( s1 I5 h<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
; P, l/ Y6 j& u$ D{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
; d+ v  [- g' g% V& E0 g+ b2 Y int i=0;
" ?2 g5 x9 U. j1 s( } double dblTemp1,dblTemp2;
1 F# x2 {, ]1 o3 p4 {( l 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;
# _1 W" x& j" d( e, ` }
9 ]" v- H$ k! a8 B+ z9 d2 {2 V temp2=sqrt(temp2);
6 K% }3 i6 h0 k1 q temp3=sqrt(temp3);
8 F" Y7 B7 u2 x& v# y dblCos=temp1/(temp2*temp3);
" H# ~/ K$ W2 S6 @4 W' o* z; y pi=acos(-1.0);
4 c* |5 u" m: o& ~ angle=acos(dblCos);
9 \- I  ^) G0 c angle=(angle/pi)*180.0;//转化为角度
5 G7 n6 R, j! b7 h* J  i return (angle);</P>
/ l$ [+ i. n+ n% j* g' z<P>}</P></DIV>
: L0 Z" r4 k% \; c. V<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
- s) E2 P: r& W! K! B//
//////////////////////////////////////////////////////////////////////</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
#pragma once
#endif // _MSC_VER &gt; 1000
#include"definition.h"
typedef struct mychrom{
( H0 i9 ?0 C  w9 L9 u; U# Pdouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
#include "BpNet.h"
, |, g7 `/ B. x- j7 M4 Y) f////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
public:
bool IsStoped;
double dblAngle;
CHROM best;
; c+ ]! L6 l+ B. q/ l' ?0 w' Y Mm mData,mResult;
$ s5 Y3 J2 E1 ]2 R. G) H$ t double dblDifference;//差异〉改值的染色体视为不同
0 J# d- g3 @* Y% k/ ?) Z/ Y double dblCre;//适应度&gt;改值的染色体符合条件
( }+ w, O3 y( z  Y8 D3 G# _ int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
//double (* obj_fun)();
: B/ E: {5 \( l double CalFitness(CHROM chrome);//计算适应度函数
2 L$ d, F$ t! e1 j! }& L long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
; t: }" X/ i& H3 ]; D; z% y bool begin();//主函数
5 n+ h8 [! O6 ^5 C3 J# u void generation();//一次进化
int rselect();//轮盘赌选择
* {) r! n' f! R4 p& p* s$ F8 I CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
3 u6 f, }8 t1 C3 ~ double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
; z% H/ R( F4 r% ~ double sumfitness;
+ ~& _5 U7 d! @- a1 L, Q/ m' C CGenetic();
virtual ~CGenetic();</P>
<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
/ T8 v" Q# d$ V$ Y- S double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
% z$ o* r" r% J9 ]  R3 T double varminmax[MAXVARNO][2];
. ~  U2 }8 v4 k7 ]7 N void init();//初始化，设置初始染色体
2 k3 ^1 i/ y  C4 Z1 @5 w( j void mutation(CHROM *chrome);//对新染色体进行变异
; r8 H( p9 |. p' @ bool flip(double possibility);//测试
0 Q7 l5 J$ d5 R) Y8 L7 N: q7 I //交叉操作，iPlace指明新染色体位置
4 ?3 V+ r) @0 y' u# E0 f* a8 ? void cross(CHROM chrom1,CHROM chrom2,int iPlace);
9 T& C2 j. |3 w* S bool IsSetScope;

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

$ ~4 _- N. F- V; G1 [/ l/ Y</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>