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

ilikenba

<DIV class=HtmlCode>
" |% w; A3 K+ @) C6 j& J6 F6 d: O<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
0 r8 o" K; B) a( G4 A- |1 s<>#include "Genetic.h"
#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
5 K- T, R' X, }* j1 z: J! p#define new DEBUG_NEW
4 X; P; c& y8 D6 b! `$ m#endif
& J- f! G4 e4 |1 E" e/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
  N; V+ t3 H( N, h4 V//////////////////////////////////////////////////////////////////////
( Q* S4 C% b0 v7 v5 d// Construction/Destruction
& s5 ~* P3 O+ J' z- T//////////////////////////////////////////////////////////////////////</P>
" x4 k; R$ |1 F9 w% {" G5 U<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
+ w: O6 i: X0 n# m' b) ? sumfitness=0.0;
5 \4 C$ l4 p* H. Q: G gen=0;
  Z# `' a( G: _* S: s& }% M6 U8 M+ B% D IsSetScope=false;//还未设定个变量范围
" f$ Y* s/ A3 a) y5 g) C( P IsStoped=false;
2 d4 N2 g6 G. ^/ p$ @0 W' W, G for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
dblCre=0.0;
/ n/ B  A8 h! i  x' i  S/ O: Y dblDifference=0.15;
  p/ o5 W& e$ g best.fitness=0.0;
! |5 U! O+ R4 V7 ?* N0 m
initM(MATCOM_VERSION);
}</P>
<>CGenetic::~CGenetic()
: R0 P) T% ]( a3 V+ o. u2 K/ H{exitM();
}</P>
# _. d  n% J  X4 g8 @' {. `& C5 _' C<>int CGenetic::rselect()
& k0 @. t6 w# m0 T$ o' ~1 J3 l{double rand1,partsum;
int j=0;
partsum=0;
# j3 Z# D( j+ v' p/ n3 T rand1=rand()*sumfitness;
! l. g: G) J/ p1 t; l+ z do{
  partsum=partsum+newpop[j].fitness;
- H- L% c# l" {. D, S% C" _2 a9 \  j++;
# Z1 N' `! o& Z# Z' [3 G }while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
4 o+ j; c& O+ a; p}</P>
( ~3 k  g9 l1 W$ [) j<>void CGenetic::generation()
{int i,r1,r2;
" ~3 U. E7 z- I7 M" m7 Q CHROM tempChrom;
' a; v* m! d* G: t. O2 I3 U //进行统计，计算newpop单个染色体的适应度，选出最优染色体
3 O* S2 T. ~" G1 m# _ statistic(newpop);
* z" o, T  X5 j( K2 q //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
}</P>
<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
2 W4 ^0 @" e: S) ~% e# ] }
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
( D! l  @! k( P0 H     mutation(&amp;newpop);
# b3 l+ Z% ?, I- {}</P>
<>bool CGenetic::begin()
4 C7 J9 `: \3 \9 {7 `8 b- @$ b{MSG msg;
/ I3 Y$ d, l/ s. M mData=zeros(1,bpnet-&gt;iInput);
8 o+ r6 z0 u5 \9 c. R# u mResult=zeros(1,bpnet-&gt;iOutput);
# K8 h1 G9 _: [* ^" q& H% z  Lfor(int i=gen;i&lt;maxgen;i++)
2 B" j7 C2 Q& J1 v2 e4 c{if(IsStoped)
  break;
! w% W; |0 C. H  H if(bpnet-&gt;iOutput&gt;1){
5 ^. B( K1 c) o2 |1 m6 N ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
. w& Y: C( t  ]; M& G return(false);
}
if(gen==0)
  init();//如果刚开始运算，初始化
generation();
gen++;
8 h, C! e6 F7 f //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
7 C" F/ _. S9 h" E: F3 \2 d msg.message=-1;
/ ]. W+ N+ [2 V6 R9 m; I7 B3 c :ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
+ Q9 u# w/ M# C9 D& J<>return(true);
: \/ b1 L* p8 w: R}</P>
<>
" S- b; C" a9 }1 ivoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
8 m; x+ R0 X: L) n1 @4 e int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
  \! y2 ~0 q, [* F0 O+ T# @//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
' w* T2 V4 @( X4 `6 U c=rand();
    for(i=0;i&lt;iVarNo;i++){
" |' `0 q- J3 `# h5 y, f1 g oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
+ w+ D- G( e$ O oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
( O4 Z9 S& Y9 p }
}
$ u8 L  I5 f- T. I/ ?1 N else//直接赋值，不再交叉
1 V8 g: }/ z7 U) n {oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
6 N! g8 }/ y7 t5 F& n<>bool CGenetic::flip(double possibility)
{double ppp;
4 q) I+ Y' J& i0 P, |3 F: xppp=rand();
( `" T/ G1 L& g" C8 I! |2 M3 {if(ppp&lt;=possibility)
$ T2 f& {6 ^2 ]4 _/ @" v return (true);
. {, B5 n* |2 a( m2 V* P' w8 j0 t9 {else
3 Q  h2 R6 {8 r9 C$ {8 N return (false);
}</P>
6 m8 c4 G* A/ d& O3 M<>void CGenetic::mutation(CHROM *chrome)
# W& l6 i' O, ]) z2 c5 G, E# Z2 Y{double m=10;
int i=0;
CHROM temp1,temp2;
: Z, G4 O& B" W if(flip(pmutation)){ //以变异概率进行变异
0 l) D  _+ m4 l* l$ K2 |$ s  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++)
, O; Q& x$ i$ F' x8 A2 [4 K4 I& }     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
. O; S. V& `9 [  }while(!identify(temp2));
; w5 {7 C) X( S( X; }3 V }
else{
  for(i=0;i&lt;iVarNo;i++)
% ?  @: ?: {3 W) t8 J0 f     temp2.chrom=chrome-&gt;chrom;
  @% J* X7 p" E: f7 |# y) X0 [% I }
0 ~) d2 o% J0 h) {# {% T4 f  e for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
2 ]/ ?% d  f4 S3 ?}</P>
" q: v7 P) n( Y* \: d, g<>void CGenetic::statistic(CHROM pop[])
; w% j- x# ^1 C4 O7 A{int i;
sumfitness=0;
8 I6 k. ^  b, W; o //循环，计算单个染色体的适应度,以及sumfitness
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;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
. U: |+ w" |6 F; X2 x}</P>
<>}</P>
7 X, [& t2 _2 q' I+ R<>void CGenetic::init()
- F; S5 L4 Y$ z& t! q) i5 s2 h{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
( m; w( I3 M1 R6 Q: A6 z<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
0 P+ {4 B0 c# X9 R6 i1 | for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
8 Y# Z3 b( ?! t4 n. R  v5 T        oldpop.chrom[j]=newpop.chrom[j];
}
, `6 l5 E3 i" Z" G& d. }2 P- g}
: c+ G2 n! c3 L, O' Z  N- L( U: F}
5 h/ A7 v& U, _9 ]* q9 u else
# v  Z* A7 f& U4 u {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
9 L' D' e2 C; m. L+ ~ }
9 O# ]9 G- g1 M' b% I}</P>

7 f5 Q% w7 y* L9 ?<>double CGenetic::randxy(double x, double y)
  }5 t. X9 E7 }  c' s+ e3 K# v' o{ return (x+(y-x)*rand());</P>
<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
7 p- ]1 F. h! H! A8 Z{int i;
for(i=0;i&lt;iNo;i++)
- ?4 ?( z% |, ~{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
IsSetScope=true; </P>
<>}</P>
* q& T2 d9 B7 l1 A' W<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
for(i=0;i&lt;iVarNo;i++)
, ?- c2 [4 G, ]) l% `  mData.r(i+1)=chrome.chrom;
# L0 V( f% H; Z" \$ V' m mResult=bpnet-&gt;simulate(mData);
0 @# H7 W9 O% e. \& l& ? dblResult=mResult.r(1);
2 o2 I. a' `1 K' M" `: k, X return(dblResult);
}</P>
% \7 Z7 \! F3 `/ I3 n1 W% D. e. m
! k7 H) T6 ?. |# w<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
4 ~3 r7 p. u2 t4 a* S bool IsOk=true;;
( @. C& r5 k1 B- t for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
  {IsOk=false;
% N4 b: p" d+ t$ i  break;}
}
. F5 _" ~1 u: ?: p  z! Z+ e return (IsOk);
( \7 y8 p& ~% y$ a/ J9 m6 l}</P>

* M% ~0 c0 D: b* ~& W! F<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
$ x' ]- g$ N" C  i/ T{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
8 U) {+ }. ~3 x  {0 @, q+ d* h int i;
for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
% e  d' U& \# C4 d& a2 O5 @5 |  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
. H' {$ ^# B6 l* i  y; s' q5 { }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
9 H: Y4 C( r, K* e6 y' r/ d return (differ);
0 J/ q% ?" o6 a& r- Q( O8 x}</P>
$ G! K! z, j# R# y. {: _- q<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
0 S' v; d6 x$ B- W" z6 g IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  L9 s+ P( Q" h1 y9 o2 @# [' ]5 Y  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
      break;
  }
return (IsDifferent);</P>
0 d( p1 d. O# D+ P/ j<P>}</P>
+ h9 t  w* C0 Q& }# g% W: I<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
/ p0 h, I+ Q# _0 ~! f8 J{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
# ^( @$ C# ~9 n- r int i=0;
( e& G8 B: d  m! V& p double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
2 O" n  j& e" H6 D5 r  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
0 i" x( R  |7 r: U0 q  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
: ?$ f) H( D4 `% w" N temp2=sqrt(temp2);
temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
/ y, L' Y, T+ w angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
6 o2 H! ~( X& L return (angle);</P>
; J, e- h7 O! @7 x# Y2 |; e<P>}</P></DIV>
: I9 j6 h* Q" n3 D' q7 c( E<DIV class=HtmlCode>
( T' L3 D" G8 T, m& k<P>// Genetic.h: interface for the CGenetic class.
' K/ I7 j2 F" G7 W4 m2 |$ i; M+ L//
//////////////////////////////////////////////////////////////////////</P>
& I" p- D' |$ d) I  N  ~$ o2 j8 r<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
2 ^) |8 o8 K' A' k. ?#include"definition.h"
typedef struct mychrom{
* U% J3 ^# |3 o. a: k* w0 k6 E' ^double chrom[MAXVARNO];
double fitness;//适应度
2 R( ~3 w: h' ?8 v9 }2 A$ ~}CHROM;
#include "BpNet.h"
' O. b0 }# `7 v////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
{
' T4 A" U( r3 `3 |- G7 |public:
. m% \8 @' l- ?& } bool IsStoped;
0 ]/ ^2 d/ U4 X+ F# q7 k double dblAngle;
$ n# `4 i: v( ]  O; D CHROM best;
Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
9 s/ X! t# ~; g# u double dblCre;//适应度&gt;改值的染色体符合条件
' U! H1 I* z1 Q7 J int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
//double (* obj_fun)();
double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
6 W. b# x( S: w+ P8 N" K5 } double randxy(double x,double y);//产生x,y之间的随机数
# V9 g% y3 H4 p% u% \ void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
# s1 I7 Q' ?* m bool begin();//主函数
- y4 P0 |9 c9 D void generation();//一次进化
0 f* I9 v% k! g% p1 ^2 S; @ int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
; v8 E4 I: U# q: G* u, W: x) P double pmutation;//变异概率
. n! x0 C8 X1 @0 ^ double pcross;//交叉概率
4 |3 B9 G. d) I, L" Q long maxgen;//最大进化代数
int iVarNo;//染色体数目
: `9 \9 o  E2 d6 R$ Q) @9 q double sumfitness;
CGenetic();
  F. z; O. V" o; R; ^ virtual ~CGenetic();</P>
7 V6 T9 D* r3 }4 I( }: {. h. O; L<P>private:
! Q2 K/ Q, ~* D double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
void mutation(CHROM *chrome);//对新染色体进行变异
bool flip(double possibility);//测试
4 ^; u& t2 ~! ^) K4 P2 e //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
6 g" l4 R1 |: H" X# } bool IsSetScope;
: z. E$ A2 }% ^7 h7 L# Q& w
};</P>
3 |& E8 ]9 I9 Y1 x' T7 \<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
' |/ M& X4 J: C" A" v0 S
</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>
5 E# L9 w  \& t( c$ ]<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>