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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
: T; C. B# C3 Q: h0 L<>#include "stdafx.h"</P>
<>#include "Genetic.h"
) l) M- l( q# \+ a#include"math.h"
#ifdef _DEBUG
7 E/ Z% F# d6 H. k9 `7 N#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
% y, o, t! d, X0 z- n, u7 x#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
+ |/ v  p5 E6 @2 h* K//////////////////////////////////////////////////////////////////////
  K. C  Y( b$ t5 ^  w* q# L, n4 S// Construction/Destruction
- y9 X+ L5 y/ l//////////////////////////////////////////////////////////////////////</P>
<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
  F! m: K6 E2 e# z pcross=0.9;//交叉概率
maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
gen=0;
& o: u) W7 O9 Y4 d5 ]8 G& y3 S" Q IsSetScope=false;//还未设定个变量范围
2 y; J& b+ R. O" J# ]- @ IsStoped=false;
0 H: Z5 P; L/ ~) a4 J; e$ v for(int i=0;i&lt;MAXBESTNUM;i++)
" q8 o! A  z# Q   bestchrom.fitness=0;
3 j* h! I1 X" V  }  X) J9 b! o iBestNum=0;
dblCre=0.0;
* ]: _" x: U( b; s2 J- u dblDifference=0.15;
best.fitness=0.0;

initM(MATCOM_VERSION);
}</P>
/ H$ c( N/ d. Q0 C# [; t7 D- ], J0 N<>CGenetic::~CGenetic()
! y7 G0 v5 I- H' u7 Z{exitM();
}</P>
! f4 E1 [! p* J<>int CGenetic::rselect()
{double rand1,partsum;
int j=0;
: [3 y$ E  i+ }6 O( Q$ ^+ | partsum=0;
, o$ w7 y1 U) J rand1=rand()*sumfitness;
do{
  partsum=partsum+newpop[j].fitness;
  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
9 B# a. F# u( W# F0 e return (j-1);
}</P>
<>void CGenetic::generation()
$ j5 C$ W, F' W6 {  Y{int i,r1,r2;
' W' [: y* D* W) N! l& V CHROM tempChrom;
//进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
; V5 c" j5 r) I5 E: Q //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
  cross(newpop[r1],newpop[r2],i);
. ~. [. E+ x" o# ^ }</P>
<> // oldpop,newpop进行调换
( T! \) m0 c) G for(i=0;i&ltOPSIZE;i++){
) F1 B. m% x9 P$ X3 z5 o" ^* V  tempChrom=newpop;
3 w  ]0 M) o8 P  newpop=oldpop;
0 F4 p/ y8 {( B+ Z1 a, C, v  oldpop=tempChrom;
}
6 Y* {. Q1 c$ O$ U7 M! V //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
- i# h& N6 Z7 g}</P>
<>bool CGenetic::begin()
, S5 n- j! k3 Z6 ]+ ?% y: U{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
. b6 m$ O. F* I0 u& B  j mResult=zeros(1,bpnet-&gt;iOutput);
+ K/ K# L( t$ ?; }' a( q; efor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
. {% f1 z/ Y6 P5 ]  break;
if(bpnet-&gt;iOutput&gt;1){
/ q8 [7 E( J$ w/ X8 R1 ` ::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
}
if(gen==0)
  init();//如果刚开始运算，初始化
generation();
gen++;
* S3 S) o1 |5 S' d* f( U //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
, {- E9 Y' x% _; e, Z: { msg.message=-1;
9 b/ ~* T  `' t+ g. {' x0 c, B0 d. O) R :ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
( A  J0 ]7 X0 [<>return(true);
9 \( V' p1 r. c0 b5 ^1 m7 b4 H}</P>
& u; a+ W6 E: g1 S* k4 r+ e8 o5 a<>
0 ?( F# b1 j4 I1 [+ @6 Hvoid CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
7 S; D0 ]$ Y! j: R5 t3 _' `) E//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
do{if(flip(pcross)){//交叉概率
c=rand();
  ~3 G/ o& f4 X    for(i=0;i&lt;iVarNo;i++){
oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
/ r# Y7 @3 J( b% S8 O- i oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
- h2 K! ]# L5 z }
8 D! G4 l! R9 @/ H( l# k1 ~, \" e, \ }
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
}
; {* G, ]( n( [+ O: P3 g}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
1 m4 }( W- R) C7 d. O<>}</P>
# b# Y2 O  n4 X3 U; @! y( v) |<>bool CGenetic::flip(double possibility)
2 f/ h5 n" q- G" H" j% |. s{double ppp;
ppp=rand();
if(ppp&lt;=possibility)
return (true);
; y- T6 a( d* }5 r  Qelse
return (false);
}</P>
, Z* Z6 J# D! X+ X2 R5 A+ c* u6 t<>void CGenetic::mutation(CHROM *chrome)
* z* l7 n/ Q! [0 A5 @1 E{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;
* |% h5 V! i3 q* o         for(i=0;i&lt;iVarNo;i++)
    temp1.chrom=randxy(varminmax[0]-varminmax[1],varminmax[1]-varminmax[0])/10;
: ]/ D' I' V8 [: F7 \* L3 D          for(i=0;i&lt;iVarNo;i++)
6 l, z7 M/ ^  P! k3 ~: M     temp2.chrom+=m*temp1.chrom;
5 p+ r8 E! t. G$ J' @- K    if(!identify(temp2))
4 R1 `, t6 y# @% Y4 @1 R     m=(double)m/(double)(2.0);
+ @5 z/ I% u4 W6 w$ d  }while(!identify(temp2));
$ U: Y3 v4 d& l- T  a3 [ }
& P+ R+ r3 y3 u- y' n5 |6 O& y9 L9 E5 y  } else{
  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
6 D+ q! F* l& v" K  H% d }
" S. o8 c6 k, k, [ for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
& J8 U0 ^# r0 h}</P>
  E) e- H8 \( W: A, m8 h; y<>void CGenetic::statistic(CHROM pop[])
& z8 E6 a' D, ]' m/ W! T{int i;
( P$ d$ z; R) }  B" W1 \ sumfitness=0;
" W- v8 v1 f  z: ^: a //循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
: t1 l* V5 z, X* q2 U# ?* b for(i=0;i&ltOPSIZE;i++){
, Y. v% ^9 r* R. y: b5 a0 y5 X0 w if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
9 a+ a- F# N9 H; O  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
8 r) z  F9 ^2 e" P8 g/ n9 b}</P>
<>}</P>
: r- r2 ]8 f5 m3 b6 V5 ^<>void CGenetic::init()
9 ~% x4 E6 _/ _0 y4 {3 {# Q5 N{//对种群进行随机初始化
( e3 A( c% X& n' Iint i,j;
$ R9 e! Z2 t, u6 O- A7 W# D) T% vsrand( (unsigned)time( NULL ) );</P>
<>if(iVarNo!=0&amp;&amp;IsSetScope)
2 ^* U1 z4 @8 r: m{for(i=0;i&ltOPSIZE;i++){
, s, k: ^. a) A# l: u: k. i for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
$ b3 N4 w7 z: f" g- Q) @ }
5 S0 s# H1 n* d% L! E; O}
}
! T- P0 I& o. Z+ J- A else
{if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
9 ]; C! `! n* \' q7 x5 ~) S+ n  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
}
}</P>
: `' b8 U% p& p, S8 d3 s
# H: U% C3 X# Y<>double CGenetic::randxy(double x, double y)
$ d' C) L. F( j4 g& I{ return (x+(y-x)*rand());</P>
/ ~8 _/ _2 k5 j6 F: \<>}</P>
<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
# j6 Z" N1 i4 f( @for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
varminmax[1]=scope[1];//最大值
7 P+ I, Q6 u% ^& r- g! b' C6 B}
& f0 V2 n: w3 Z; @8 ]) g1 aIsSetScope=true; </P>
) |# y7 V; r1 Y' E, ~# i! _3 z' H<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
int i;
for(i=0;i&lt;iVarNo;i++)
  mData.r(i+1)=chrome.chrom;
, r% s9 z' J2 }8 Z! p mResult=bpnet-&gt;simulate(mData);
7 Y( I. x3 E: Z; [% j( S dblResult=mResult.r(1);
return(dblResult);
+ g/ R8 l* E( A: k) I$ J6 x( F$ N}</P>

<P>bool CGenetic::identify(CHROM chrome)
% Z1 f7 q1 d# `: O9 d/ ~! D  m' x{int i=0;
: p6 F/ Z! ]2 \0 i) L( v& _- o7 t! ] bool IsOk=true;;
for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
: L$ _# f, H: z+ [1 Z% W  {IsOk=false;
( r  O; v* t$ r  break;}
% u# S- ^! b* U  l) D! P, O }
8 y+ O+ p. p% h/ p return (IsOk);
2 W3 }5 U! f9 y+ H& q0 F}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
2 _  r7 `" t* d  w) i int i;
5 C: t0 N, k. P for(i=0;i&lt;iVarNo;i++){
* X! A; N2 Y! h) f7 _. L3 g7 Y  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
* n$ {$ D( p( H( y  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
6 t0 h# V/ k7 ? temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
differ=sqrt(temp1)/sqrt(temp2);
: l) i! D, k6 G0 f7 L4 n' \6 W return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
% \) N" q9 ?) a, J{int i;
: L/ D; J6 k" E6 G$ s; t! P bool IsDifferent;
IsDifferent=true;
7 S2 I4 g" g# v) m$ @6 j+ ]9 i5 K for(i=0;i&lt;iBestNum;i++)
+ K: m# x, p8 T1 n  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
% e; b( f: h- y: O: t  {IsDifferent=false;
      break;
  }
return (IsDifferent);</P>
, |6 U5 I' n9 C1 @<P>}</P>
2 F' e. Y: k9 c7 l<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;
+ t3 v  Y0 m6 P* _" c0 t" W double dblTemp1,dblTemp2;
4 B) ]6 {8 t' u+ R" X. p+ J# X for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  H6 P) f$ o7 M3 @  temp1+=dblTemp1*dblTemp2;
+ M+ V% c5 _2 G6 z% ~2 c  temp2+=dblTemp1*dblTemp1;
$ g/ |( O( `9 q# u2 _- t) y  temp3+=dblTemp2*dblTemp2;
% W& f: N+ Q0 L0 T9 V6 `$ @4 W }
: d, d! c* `. q$ s temp2=sqrt(temp2);
2 J( z# B. \& p; C9 K temp3=sqrt(temp3);
& V7 P& I+ i* Q0 w& t2 Q2 Y dblCos=temp1/(temp2*temp3);
9 y; |. M8 m% z2 l0 l6 o8 R! D0 ^ pi=acos(-1.0);
) ^8 |; v, J, y$ w( @ angle=acos(dblCos);
* a. @( ?: N# W; ?( @+ X1 r2 G angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
/ h3 Z+ E7 \# K1 I- o9 ^! j#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
2 b( w& x. e! {6 P/ P#pragma once
; b" V9 Q2 }2 k" B( c#endif // _MSC_VER &gt; 1000
4 v; d) a0 K. w! ^* \#include"definition.h"
$ y9 r( i& L$ t1 K, v! S& Z4 j, dtypedef struct mychrom{
. {9 g4 Z* S0 _, jdouble chrom[MAXVARNO];
double fitness;//适应度
' @1 X# V5 [& G$ A, ]" j  Z}CHROM;
#include "BpNet.h"
7 z, w5 Q+ h# z- Q7 D8 `, _- D( \////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
" n) B! r9 v( H0 iclass CGenetic  
  ]; J5 u. d- T! v, F) \: B7 u{
public:
$ s, o: B+ I6 V bool IsStoped;
double dblAngle;
3 p& U$ z& S/ N2 r" t CHROM best;
2 Q& H# K  h. N( T, M Mm mData,mResult;
- G9 V( x0 Z) _8 g5 F double dblDifference;//差异〉改值的染色体视为不同
double dblCre;//适应度&gt;改值的染色体符合条件
& F6 ?0 ~2 a5 a* [! N$ s int iBestNum;//符合条件的染色体数目
CBpNet * bpnet;
//double (* obj_fun)();
' G! X* k& s/ O8 L3 m' J5 I double CalFitness(CHROM chrome);//计算适应度函数
3 Y$ V8 M6 [5 D long gen;//当前进化代数
" L+ [5 G( u* S! u; h void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
+ ]5 M0 ]7 y& T) w. M" Y0 Y void statistic(CHROM pop[]);
- [* c0 Y5 T8 x8 P3 [, e3 @) W CHROM bestchrom[MAXBESTNUM];//最优染色体
; V, w$ t2 O% A, ~! L bool begin();//主函数
# m: T+ `$ U- F8 S  [. f void generation();//一次进化
$ a) z6 M' ]8 S# y* | int rselect();//轮盘赌选择
  P9 z# d, H- O CHROM newpop[POPSIZE];//种群
2 ?6 O+ Q3 l* B' a$ E: y& I CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
+ n7 ~! m5 f* X; B2 \ double pcross;//交叉概率
long maxgen;//最大进化代数
. Q7 I- M, `; T" T8 K int iVarNo;//染色体数目
double sumfitness;
CGenetic();
, I+ O/ }% a7 Q* U7 l+ N virtual ~CGenetic();</P>
<P>private:
# }5 a; u: T4 c8 l' }8 b5 z7 T7 P9 E double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
4 W9 K. {8 D5 ~4 g 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);//测试
//交叉操作，iPlace指明新染色体位置
  S; f% ]) U3 S void cross(CHROM chrom1,CHROM chrom2,int iPlace);
bool IsSetScope;
3 u% d6 g/ @7 O
. X) u9 p( x' Q: [0 i0 R0 R};</P>
<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
: P* [1 y; i+ {; ?" ]) 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>
# _1 ~5 h8 o. a; Q<>QQ 20409589 EMAIL yiping8241@sohu.com</P>

txj66

<>好啊啊</P>

luotianj

<>谢谢</P>

john.liu

<>good</P>

bluewisher

<>还不会用</P>