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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
/ S: _7 f2 s8 ]' w6 v<>#include "stdafx.h"</P>
! F+ Y% U; p* Y4 O# {1 s$ Z: o<>#include "Genetic.h"
, f7 A# m  Q* o" G: e; K9 \#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
% Q3 U2 N& [; s3 k5 lstatic char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
4 d* B8 |9 e; O#endif
4 w2 T3 R4 p) n$ o( I# K" }/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
3 m5 ~# L+ [% k% T  D//////////////////////////////////////////////////////////////////////
+ _$ b' V4 c- j: K$ {/ v// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
2 A& _3 }- R. s- S  q pcross=0.9;//交叉概率
6 o8 e, s! C& \ maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
$ C. P+ t0 Z( S) q sumfitness=0.0;
gen=0;
( N0 n1 }' z7 y5 o8 U IsSetScope=false;//还未设定个变量范围
3 I, Y5 x# @: s. W9 L- D  {8 L IsStoped=false;
: E+ P# R- G5 p4 x" t0 _ for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
iBestNum=0;
/ Q- N* p( P* g& A8 h dblCre=0.0;
; b5 ^- j+ j8 \8 R9 r dblDifference=0.15;
best.fitness=0.0;

# o$ C* Q7 y3 v initM(MATCOM_VERSION);
+ O- J) E: {/ M }</P>
9 K; t9 ~3 g8 s1 |7 x<>CGenetic::~CGenetic()
{exitM();
8 k6 L) v. r) G" h: @}</P>
<>int CGenetic::rselect()
$ k( {9 y, _- m$ e3 H" Q{double rand1,partsum;
+ i% P, m7 [0 E! X. u int j=0;
partsum=0;
. J' Q6 l' N( [$ J; R3 O rand1=rand()*sumfitness;
do{
6 S8 d$ {. l+ L8 f- M  partsum=partsum+newpop[j].fitness;
3 J( B' ?: X2 y  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
" X; ?% M% s. n4 c return (j-1);
% c9 }9 h# x+ e1 t}</P>
4 {* i# D) ^) g- a$ G$ v( x5 n. t<>void CGenetic::generation()
{int i,r1,r2;
* m8 ?/ p' t1 X: n CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
# [" m) Z6 p+ a' {: G, w7 M3 { statistic(newpop);
4 D) a( Y# l2 M; k6 R+ \- K( } //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
0 u4 a/ [4 {) \    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
. r  j4 p. D+ s  {7 d/ l( Q  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
}</P>
% e4 U9 y2 _- U* j<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
5 E6 p* {8 c2 Q# R$ q- F; a# I, g  tempChrom=newpop;
  newpop=oldpop;
  oldpop=tempChrom;
}
9 N) F' N6 l+ n, r1 g' x3 {# S //从1到POPSIZE循环，对newpop进行变异
6 T/ P- V$ o, H! N. H( e    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
! i) f* D2 N, \) M( x7 }' `}</P>
4 J& ~0 W* o7 D% D( n<>bool CGenetic::begin()
9 p2 ^& v2 d- c! ]' t* e( c% w+ h9 {( O{MSG msg;
  s/ [7 I' I4 I( o! U* i mData=zeros(1,bpnet-&gt;iInput);
mResult=zeros(1,bpnet-&gt;iOutput);
, Q. ~3 B5 b  f3 f; T0 y  Qfor(int i=gen;i&lt;maxgen;i++)
- q6 p- T& M) w  s- Z# J# {{if(IsStoped)
  f9 g: [. d5 M$ D$ `  break;
" C# j4 J$ F' W9 P! f. K2 y" D if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
% M# r8 c  k, t- v- I1 y% T9 J return(false);
6 J& B8 n- z" l }
if(gen==0)
  init();//如果刚开始运算，初始化
generation();
gen++;
) ~" a! }# g* F //防止假死机
8 G, q  }2 r0 d1 s/ Z :eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
& |4 d9 |  r0 x) f6 b2 n. ^ :ispatchMessage(&amp;msg);//这样可以消除屏闪
9 O5 C0 j0 G5 v' e8 Z" y}</P>
<>return(true);
3 J" z# N' Q  r5 \% J0 j}</P>
6 P/ l: \  g, T6 B<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
. P8 C( d) V2 K! F; h int i=0;
- D4 ~: m+ m; k, s; {//以交叉概率进行交叉，并对交叉后的新染色体进行判别
+ F# Q+ M, F/ Y+ m& f//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
; N! Y! T1 S: }# `( [* L% g% t c=rand();
    for(i=0;i&lt;iVarNo;i++){
oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
9 [. S+ b9 S' \% p5 T6 }0 F/ [$ L }
. d: M2 t' b8 w8 A& I7 t: i: K }
else//直接赋值，不再交叉
& ~9 v% K  G) q  n2 |" r {oldpop[iPlace]=chrom1;
, c- B# z% u# A* @  oldpop[iPlace+1]=chrom2;
}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
  y9 T% [0 w5 V, Z<>}</P>
) @+ b1 M# l$ ?, B+ `<>bool CGenetic::flip(double possibility)
* ~2 P! F' k( r/ G4 Y3 x. z. s{double ppp;
; }( t* W$ r! X3 w& U; f- j! A( b' n5 bppp=rand();
if(ppp&lt;=possibility)
5 B9 A7 Q- P" A3 N return (true);
else
return (false);
}</P>
9 X4 j7 j" j) d<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
8 M) [4 Y4 E+ U* M1 T( L int i=0;
; e5 a4 m- s9 g  `0 ]4 `' a CHROM temp1,temp2;
4 [9 r" Q0 m; p, E( q* o if(flip(pmutation)){ //以变异概率进行变异
2 Z. L  w* H, z& b& B  do{ for(i=0;i&lt;iVarNo;i++)
+ a9 h: L  f+ P1 n& [     temp2.chrom=chrome-&gt;chrom;
         for(i=0;i&lt;iVarNo;i++)
: r8 D3 J' A. s; c1 ~3 K    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
% h7 @7 I+ \8 E          for(i=0;i&lt;iVarNo;i++)
     temp2.chrom+=m*temp1.chrom;
    if(!identify(temp2))
     m=(double)m/(double)(2.0);
0 X' ^1 H( _- k. O  Z  }while(!identify(temp2));
}
else{
  for(i=0;i&lt;iVarNo;i++)
0 E% X, S% e8 E     temp2.chrom=chrome-&gt;chrom;
}
4 A5 U8 }8 [* I  \: [- t$ l& ] for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
<>void CGenetic::statistic(CHROM pop[])
; f- X1 Z4 O; |. {9 Z, J: K8 S{int i;
% [; C, L8 |) Q3 j. @* \5 l  f sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
! T1 c: Y- D' W. @ for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
5 z* g& @* _) A+ o# p* }5 N if(pop.fitness&gt;best.fitness)
  h$ c0 p3 a+ j& H  best=pop;//纪录最佳染色体
* g6 ~' w8 [3 f}</P>
<>}</P>
6 |1 @0 Z  l8 K9 a. J7 S2 `<>void CGenetic::init()
9 H' z/ \1 l! @, P0 E" D$ N{//对种群进行随机初始化
( \* o. p- H# W/ ]$ Nint i,j;
) \( Q4 l3 R( A  C$ c0 hsrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
: B8 w  T: y  U$ v for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
+ @6 X8 G6 i5 q7 A+ g  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
+ x6 L) e4 ?6 W! G9 ]}
. k& O4 g- \2 ]/ I- t}
& z1 s+ ~+ S# L0 ` else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>

<>double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());</P>
<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
' j  \( P8 M. N' L# h2 t{int i;
- Y0 e( S& K. z9 `8 hfor(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
}
5 {6 R% ^5 B* Y' }' O- B# _IsSetScope=true; </P>
% L7 F7 ^3 z, q9 J) E3 m<>}</P>
, l+ y% @2 f" W/ k2 O8 n7 Y$ U: C<>double CGenetic::CalFitness(CHROM chrome)
1 w0 \1 x. A1 N: w- f1 t' _- ?3 q2 g{ double dblResult;
  v+ h- ^! W& V: y: u. I4 ^ int i;
8 A8 S' O# x/ w$ l0 r for(i=0;i&lt;iVarNo;i++)
* e3 k  N% X! |* e5 F  mData.r(i+1)=chrome.chrom;
3 Q. C. y3 I% i: ]8 Q- V8 X+ N mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
return(dblResult);
}</P>

<P>bool CGenetic::identify(CHROM chrome)
{int i=0;
bool IsOk=true;;
% e8 s2 y& y- w/ @, J& `1 { for(i=0;i&lt;iVarNo;i++){
( O: n* D9 w1 q6 d3 ?/ B  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
& \, A: K" q6 T/ x  {IsOk=false;
  break;}
1 ^5 [- q8 F  ^- Q  d0 T" s1 _2 E7 k }
return (IsOk);
}</P>

- B* a% X1 g8 P& j+ B<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
  Z* Z, |/ c6 W; w# K for(i=0;i&lt;iVarNo;i++){
0 Y5 p3 H4 N9 {" v  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
6 `7 c! x7 j) ]  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
* y/ K6 Q& F% G5 n7 x3 A- J; s  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
, h4 ?4 v  I; @2 u# m+ ~8 u& }) g# W  temp3+=dblTemp2*dblTemp2;
! |& z( l8 ]( K' |9 V }
' P, l) y- a4 a8 o0 i& I( k temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
1 j: y. K( {. [: }5 Y differ=sqrt(temp1)/sqrt(temp2);
' h, I) x8 N- s' U return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
{int i;
bool IsDifferent;
8 S2 V% W7 O7 M/ i IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
# B7 e" N) w( ~2 U  a  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
/ g( F) J8 T$ m# I, Z3 ]' F* e      break;
  }
* ]' {: m- K6 [9 Rreturn (IsDifferent);</P>
5 c" P5 U$ B5 C6 r* V<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
9 G; \/ W- H* ^% W# `) o{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
int i=0;
double dblTemp1,dblTemp2;
) n: t! a" m1 l# O- n2 N* I5 Q for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
* ]8 r/ b; ?0 F. _) G8 T. L  V  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
( J3 g- G+ m  ^# \  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
2 i6 y, e0 v2 p. l0 s1 J  temp3+=dblTemp2*dblTemp2;
6 R6 v# c/ l- h: t: b3 v% O4 n }
temp2=sqrt(temp2);
temp3=sqrt(temp3);
4 a  R' t5 |* \/ k' C$ _6 a3 A/ ~ dblCos=temp1/(temp2*temp3);
0 D& u8 L' M" |* X0 w5 b  N# q pi=acos(-1.0);
angle=acos(dblCos);
5 V! l8 J. p) Q0 V% L6 Z* Q  o angle=(angle/pi)*180.0;//转化为角度
: E3 [0 E6 w/ |0 ~; c4 V. I5 \ return (angle);</P>
% u5 M* B! }4 \5 C<P>}</P></DIV>
, r* \+ ^0 k% {" ~7 M3 m1 G# z<DIV class=HtmlCode>
, `) ~' I# f- J: S5 k<P>// Genetic.h: interface for the CGenetic class.
//
$ k; e  E% p. v6 P8 @" H, `//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
+ ?9 Z" Y# @7 p, q  o# V#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
3 h+ W# t9 U* e) E: Y<P>#if _MSC_VER &gt; 1000
#pragma once
; q. a# Q, S. U4 y#endif // _MSC_VER &gt; 1000
6 A& K5 Q8 w  t: `0 v#include"definition.h"
typedef struct mychrom{
& Q) H3 ~. |& Zdouble chrom[MAXVARNO];
) @/ z: ]+ J8 O8 ndouble fitness;//适应度
0 B9 ?' S9 _: c/ w7 Y3 N) z}CHROM;
) f8 |" D/ w, ]# A1 V8 y! C#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
7 i* l$ v5 f- P. ^1 V6 K; p{
public:
+ t- {( V( P; q3 ^; _8 M bool IsStoped;
/ I4 x) M$ A, D1 s, m% N double dblAngle;
CHROM best;
& z3 n/ D* j+ ~9 U+ ` Mm mData,mResult;
6 d$ X& V' Q3 a; e5 j6 n) E8 ^ double dblDifference;//差异〉改值的染色体视为不同
8 }' _5 X6 y, ], b+ }, \  q double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
% ~' }4 I' Z( J: J CBpNet * bpnet;
& h; n( @3 y; ~/ T //double (* obj_fun)();
1 u) ~8 C! d& o" N% I9 |7 }4 g double CalFitness(CHROM chrome);//计算适应度函数
long gen;//当前进化代数
' o# y) |6 m- O% H void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
7 W, @- e9 c8 M, y0 h7 F; Z void statistic(CHROM pop[]);
3 _: f/ E& ^1 D  Z9 t5 f- u& E CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
void generation();//一次进化
, A8 r, a$ E( W  X. p8 n int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
# @4 V$ t) A& C( J* ` CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
double sumfitness;
% l8 e, \, ^7 ~& y$ R$ c* C* m CGenetic();
1 z; K. z1 U$ Y( E1 D" ~- V virtual ~CGenetic();</P>
- t8 i* y! N9 U' y<P>private:
) t6 C$ ~/ V: U3 h7 K double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
: L" w5 Z; Z# ^. C. [ double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
  s. H9 f, N' ^ double varminmax[MAXVARNO][2];
void init();//初始化，设置初始染色体
( W1 ], L) }6 Z void mutation(CHROM *chrome);//对新染色体进行变异
+ O* A) A$ A0 g* g bool flip(double possibility);//测试
7 `% s0 O: ^, J9 [2 H- O1 R //交叉操作，iPlace指明新染色体位置
" E, c8 O+ `5 @6 Z void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;
) @, v' O' }0 o2 I3 [
};</P>
, C) u& O1 G) R" |<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
; Z3 d, r) }# |9 z) c: J
</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>
8 N! z1 v6 ~  Y% p) W% d! A; A" o<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>