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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
: S9 r" s8 t% z<>#include "Genetic.h"
2 F1 T/ \4 V: k#include"math.h"
- p- ~+ z$ ^! b, _- q$ W#ifdef _DEBUG
4 V9 a1 K: B( \2 N& i' O% k#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
5 M8 u  U+ J, S( o0 U#define new DEBUG_NEW
9 r) ?" N3 \1 _/ y& l#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
* w! {/ V- K8 p6 w3 e- B//////////////////////////////////////////////////////////////////////
// Construction/Destruction
' I" N& s/ v, ?$ ?, d" X! A//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
7 Y3 ]# R. m; V) o. T+ x pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
0 j* [* E1 S; J1 [9 b# b  | gen=0;
: M  e# {4 S1 z; Y2 i9 S$ R: c' E+ u IsSetScope=false;//还未设定个变量范围
IsStoped=false;
+ }: W! @+ g% C% j8 s for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
% G2 Z! v. ?# W  K+ Q iBestNum=0;
dblCre=0.0;
dblDifference=0.15;
best.fitness=0.0;

0 m3 |1 s& z6 T. n% i+ P* l; Z initM(MATCOM_VERSION);
}</P>
9 v9 b6 Q% L3 N/ a<>CGenetic::~CGenetic()
{exitM();
, F! S0 U2 \, x8 R) W}</P>
) G- m" z% M; @" h* _9 ]<>int CGenetic::rselect()
{double rand1,partsum;
! ]: O7 D# v; C# Y int j=0;
partsum=0;
rand1=rand()*sumfitness;
7 \) v! c8 o) [& d, c7 j" R2 G6 ?9 h8 L do{
  partsum=partsum+newpop[j].fitness;
  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
& E. }6 S3 I$ a0 v" T* G+ R3 u return (j-1);
}</P>
<>void CGenetic::generation()
{int i,r1,r2;
CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
( k, p0 X1 y8 I* O" D* ]* h2 `    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
4 n' t& }5 H( X/ p; S' i  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
  m1 h! x* U) m1 {4 _ for(i=0;i&ltOPSIZE;i++){
6 z$ V, ^( X4 J# Y0 z  tempChrom=newpop;
( B; P2 B1 z" S, }1 ^+ F  newpop=oldpop;
  oldpop=tempChrom;
  {! h! E3 j. |2 L3 N }
% K0 \8 H: _+ B( @! v //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
/ B/ |+ ^/ U" P' W0 t}</P>
<>bool CGenetic::begin()
" M3 ^; o" l4 ^5 ~- q0 s$ Q1 h8 i{MSG msg;
8 {3 ]4 i: }# M1 A% k* o" e  W1 ] mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
for(int i=gen;i&lt;maxgen;i++)
' Q; s$ q9 G5 G1 h5 }- k! W7 a+ @$ f{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
7 i/ o+ Z- |9 f, t+ y6 w ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
5 F5 ]+ h. P! c7 x" ]* u9 C, K* w return(false);
}
if(gen==0)
  init();//如果刚开始运算，初始化
( n2 N  W- B6 |6 f generation();
3 W% d* U# n+ n2 z7 K gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
<>return(true);
}</P>
; B* s0 o$ O  o: V7 b; f<>
( ^- f4 d9 }9 D: u+ z7 rvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
& l5 T; t/ i% c int i=0;
# H/ b3 L7 Y  Y5 j3 K6 ^//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
9 b( [1 X3 r7 s6 p; X" K do{if(flip(pcross)){//交叉概率
c=rand();
    for(i=0;i&lt;iVarNo;i++){
/ j0 q- A3 e% E4 R, @# O$ [! X oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
* _- T( F' d! p" c  c+ M. N oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
2 r4 X1 `) e, @$ s }
}
' O, Z( b! {' g/ K else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
3 W7 M$ J1 u! r7 h; l+ S: h  oldpop[iPlace+1]=chrom2;
}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
) q4 D4 h5 b; H" s* x& K<>bool CGenetic::flip(double possibility)
{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
" |" J* A( I- h9 l( @ return (true);
, z$ C# F; t  @: ?: \; I5 ]else
, V9 `9 Z: Q1 O9 B# W, b) Z return (false);
* m7 k1 ~' \: o, [( y+ ?}</P>
<>void CGenetic::mutation(CHROM *chrome)
1 i0 V; [! R7 \  A. g' `{double m=10;
: P/ a9 X" d; `+ a( Q1 N/ b int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
- P4 l! Q- a% q. p" w- H8 ?  do{ for(i=0;i&lt;iVarNo;i++)
- `+ \! B' q5 G     temp2.chrom=chrome-&gt;chrom;
: x7 }" i( r& A- C- o         for(i=0;i&lt;iVarNo;i++)
% j- ~4 ^# n, `* e3 Z    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
! Q2 M, N  V. q& L          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
3 ~! {) v- F6 p5 l" O     m=(double)m/(double)(2.0);
8 _' q* @7 [; T9 Q- t  }while(!identify(temp2));
& o* [2 m( B# [ }
; N0 O* S" g3 S& c& l  ~7 O$ [ else{
9 I$ N) Q9 _. L9 t5 b3 X+ a4 i  for(i=0;i&lt;iVarNo;i++)
8 Q2 W/ D5 L" g5 v' G6 \! Q1 `% c     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
1 Z2 Y8 P. ]9 v4 y/ Z4 M}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
# Y, z( ~* T4 k   pop.fitness=CalFitness(pop);
4 I' [8 G* h3 J* j   sumfitness+=pop.fitness;}
//选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
1 O" l1 u6 F6 b. E# L  bestchrom[iBestNum++]=pop;
* g7 q0 v. y+ N" c3 _  x if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
# F4 _0 {# g# I9 S}</P>
* S3 W; J5 D: e4 x<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
7 e$ `4 h9 k, }- E5 n8 Tint i,j;
; r# ]1 n2 J1 V; _" G1 W3 hsrand( (unsigned)time( NULL ) );</P>
, `2 n- G$ L: L( {6 X- a2 t<>if(iVarNo!=0&amp;&amp;IsSetScope)
' e( E3 v2 C: `- r' X. r8 |{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];
/ [, t8 M8 L5 }/ I! k* M }
}
- U: i# m; R8 h- ^}
else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
+ R) n4 ~* V: q1 s- K% p  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>
- v' H, P- T7 N9 ], U, b, n. V
3 R8 g/ Z' B: a  v6 ?5 H* M<>double CGenetic::randxy(double x, double y)
0 J) A, t4 o4 \* `+ s% W{ return (x+(y-x)*rand());</P>
$ w8 k( j/ y+ c! c% A) e) l<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
9 Q1 j! f+ N3 ]. ^% ^6 s: D{int i;
for(i=0;i&lt;iNo;i++)
! h3 j7 a* G' M2 Y9 l- J{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
IsSetScope=true; </P>
3 q; z3 W7 x5 z6 {8 g<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
  Q, S* O3 S3 [- ` for(i=0;i&lt;iVarNo;i++)
: i8 L( ^1 R6 T- ]. D: W- v  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
: ~7 |$ {9 }( {( y) l( G" J' W dblResult=mResult.r(1);
return(dblResult);
}</P>

<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
: z0 h0 i/ L0 D( o5 L3 [& y) P' n- \ bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
% z' f, _6 Y6 [  break;}
}
return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
4 ?$ G; V4 @$ H2 `% c2 F0 s# }{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
# I. j: }% d) B0 |) a7 ]& I4 d9 H for(i=0;i&lt;iVarNo;i++){
6 H6 V3 h! D. F  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
1 k  F6 b, T; E  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
5 V0 L( {. G& K9 y" d  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
+ O! t& c" c+ B* o  temp3+=dblTemp2*dblTemp2;
}
2 H3 P. }/ x: z* l+ }( X( P! O temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
2 c& R* }+ |/ P3 P6 [& R+ ` return (differ);
! ~3 P2 X0 R+ J1 o8 c* J6 i}</P>
<P>bool CGenetic::IsNew(CHROM ch)
: Z# O# R; {$ S3 `0 F' n{int i;
bool IsDifferent;
' n" c% _) [' @ IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
- s: i0 k5 K6 S  {IsDifferent=false;
      break;
  }
3 f- E& p4 A, M: y( g3 [return (IsDifferent);</P>
<P>}</P>
+ N( A% E7 ]+ A) L* y7 D& o+ B<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
( {  T6 `  ]5 v2 g) `{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
! s5 C9 ]" P" v' Y: T2 k3 T int i=0;
double dblTemp1,dblTemp2;
" v$ O& B- b; E" B1 Q2 J for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
1 V4 t" t$ I. w4 V# e  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
5 O; ~# n7 W% |- G& B$ X$ k! K  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
/ C2 |* ?% t6 C5 e" `* ]. M }
" T* Z( q" h$ q% B3 T( c# I6 _ temp2=sqrt(temp2);
temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
angle=acos(dblCos);
3 s  @; V. w% R0 p2 V4 g angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
( d$ _' z- A- }9 ?" r: _3 p<P>}</P></DIV>
% f7 b1 i" B9 Z7 ?6 B<DIV class=HtmlCode>
0 x  O, j0 F" _. i: D4 b<P>// Genetic.h: interface for the CGenetic class.
//
: n0 t4 D9 p1 J/ {# {+ g1 W5 g//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
" D5 M" I; I" e0 ^# [! M<P>#if _MSC_VER &gt; 1000
#pragma once
! Q4 h- a/ w5 ?8 Q, `( h0 K#endif // _MSC_VER &gt; 1000
#include"definition.h"
1 Z. P* A3 v5 J- N1 |  ttypedef struct mychrom{
9 X& A$ m8 ~$ M1 v' f& `double chrom[MAXVARNO];
# {9 ]  d4 s% F+ r6 s" {" Odouble fitness;//适应度
% L3 H+ A) S4 l- t}CHROM;
- t$ O! a8 P+ F#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
  u; Z0 _4 s0 P# n# D- jclass CGenetic  
{
public:
bool IsStoped;
double dblAngle;
CHROM best;
Mm mData,mResult;
$ }  Q+ {- Z# _* | double dblDifference;//差异〉改值的染色体视为不同
6 c" K, U* L" N2 L7 E, S. O double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
3 h$ t1 V; s" J, o* A CBpNet * bpnet;
//double (* obj_fun)();
( M2 E. C& `# I double CalFitness(CHROM chrome);//计算适应度函数
1 q7 U" R) D+ G! g5 { long gen;//当前进化代数
: A7 [4 q4 |& t7 S  @ void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
$ K' u$ a) D! S* A. x6 z1 Z$ o: |. b double randxy(double x,double y);//产生x,y之间的随机数
6 C! x/ ^% `9 ]$ J# ^+ `! Q+ C0 X8 Y( X void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
- Z; q+ Y, @3 ~( A7 [ bool begin();//主函数
void generation();//一次进化
int rselect();//轮盘赌选择
/ Z: t  B# Z) r, y2 J CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
<P>private:
double angle(CHROM ch1,CHROM ch2);
! X- o4 ?  ~5 j) ` bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
0 z( m. g$ G6 E& V6 @. f# p# s- } double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
! ]; V2 f0 u' E: T$ Z% E$ H double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
. m; o' f8 H" g, Y4 B9 {3 {) u //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;

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

3 M, W% W: i/ @</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>
0 Z; I' ^: ~. R; {<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>