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

ilikenba

<DIV class=HtmlCode>
; h$ l* q- q7 Q5 [<>// Genetic.cpp: implementation of the CGenetic class.
//
0 v5 t7 q* `1 N0 [: Q: u: v//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
<>#include "Genetic.h"
#include"math.h"
, ?1 ]3 T5 V* r" }8 J#ifdef _DEBUG
9 F2 x* O4 P4 C$ h#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
7 t" y) S: T; V3 d' `: o0 n$ \#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
9 Z4 E6 u6 h/ L: Z2 B1 N( l// Construction/Destruction
//////////////////////////////////////////////////////////////////////</P>
3 U: V+ e/ J1 l3 @<>CGenetic::CGenetic()
{pmutation=0.01;//变异概率
% K" ?2 l8 ?8 {+ `8 [; A$ z) K' p pcross=0.9;//交叉概率
* M4 ]6 j  e- z maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
+ _" P. p1 Z" i6 r sumfitness=0.0;
2 n8 v, S, d  S* p3 ` gen=0;
, z. `5 d7 g/ b2 L/ a5 m) q* _ IsSetScope=false;//还未设定个变量范围
# T) z9 d9 \, @, f8 J2 L) B IsStoped=false;
# g0 p! |0 l* H, S7 K( B  a for(int i=0;i&lt;MAXBESTNUM;i++)
   bestchrom.fitness=0;
  m- ~; n0 p) Q iBestNum=0;
+ L+ o. o% G5 Y# ?+ N1 f% v3 q- t dblCre=0.0;
dblDifference=0.15;
6 w  k, ~' F- X0 v( C3 { best.fitness=0.0;

' {; B$ H: v/ x9 I7 T; U( Y- e' o initM(MATCOM_VERSION);
0 o; ?! J2 Z7 ^6 M2 o  F }</P>
<>CGenetic::~CGenetic()
{exitM();
6 O5 q, Z) P  `: n- N" ]}</P>
<>int CGenetic::rselect()
6 G$ {4 c/ j) `8 X{double rand1,partsum;
  m7 u# ]. u; w; x! [ int j=0;
0 f8 X4 s  ~1 H" ?+ P) z# P8 w partsum=0;
rand1=rand()*sumfitness;
: n' o: x6 N( ?" w) h& ` do{
  partsum=partsum+newpop[j].fitness;
; |4 W9 V& Y7 H' ^! c1 _" T  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
return (j-1);
}</P>
9 H1 U  N+ N1 A+ D) ~<>void CGenetic::generation()
  k; X# X4 O) B! M{int i,r1,r2;
CHROM tempChrom;
* v' x- h; Y8 g! W' B //进行统计，计算newpop单个染色体的适应度，选出最优染色体
3 i6 O( C. w0 {, [5 Q  B( \5 E0 ? statistic(newpop);
5 C6 m* n& N! R8 y$ ] //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
' n% @& y' d) U* Y; R+ Z  cross(newpop[r1],newpop[r2],i);
}</P>
, @  H$ B: a) y$ R9 s( ?5 b: K* O<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
  tempChrom=newpop;
  newpop=oldpop;
/ a. ?/ U0 u: ~% R$ d  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
0 {6 H7 N7 n  I+ I! ~# z    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
<>bool CGenetic::begin()
{MSG msg;
mData=zeros(1,bpnet-&gt;iInput);
: e! w, _8 r! N. M& K mResult=zeros(1,bpnet-&gt;iOutput);
5 B8 T2 A; v: F; P0 gfor(int i=gen;i&lt;maxgen;i++)
{if(IsStoped)
  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
+ T& @/ b/ L/ f return(false);
4 F  C% t# z' L+ U6 a0 x# b }
) g- e1 C$ \- |# e9 Q% G. j; W& f if(gen==0)
2 B5 \, C- B# ?! P  init();//如果刚开始运算，初始化
generation();
gen++;
//防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
/ e$ X" b. d5 E" q9 i :ispatchMessage(&amp;msg);
$ i# q- i& _9 N$ l% K4 I msg.message=-1;
:ispatchMessage(&amp;msg);//这样可以消除屏闪
}</P>
% f+ C+ [0 {5 N$ |<>return(true);
}</P>
$ X2 i0 s) c2 D: I<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
  Z! i) n" Q& \% C9 I{double c;
$ a# P; p9 H6 U4 K5 n2 a0 V int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
* P$ i6 Y0 G  R1 R4 r# w1 S- U do{if(flip(pcross)){//交叉概率
. g, q$ F8 }7 x- f" c c=rand();
    for(i=0;i&lt;iVarNo;i++){
/ _$ N( A3 H8 ^0 p; \, |& w5 I& ~4 Z oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
" d7 u7 n8 w+ i3 J4 K oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
! H/ Y' N5 D" d4 N# p. B5 h }
}
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  oldpop[iPlace+1]=chrom2;
+ t4 E1 k8 a6 q7 J  h }
1 e( C6 T4 @9 y6 o; T2 n1 C}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
7 A: R+ {9 m7 N/ Z' ~/ p3 e<>}</P>
<>bool CGenetic::flip(double possibility)
{double ppp;
6 c) T) ?3 c" n5 W" _: W+ y1 m7 Yppp=rand();
& B& U& y+ ^9 U3 R1 C, Sif(ppp&lt;=possibility)
0 h8 R! Y* n, z" n8 @; x return (true);
else
return (false);
}</P>
0 e$ z, X/ ^5 ~<>void CGenetic::mutation(CHROM *chrome)
{double m=10;
int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
0 A1 }- u& p1 `+ k  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;
- t) U) P  q$ q+ c) S    if(!identify(temp2))
     m=(double)m/(double)(2.0);
  }while(!identify(temp2));
( N9 ~' M# J& Q9 Y' p$ N, W }
else{
  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
9 O: F1 }2 ?+ h4 v* f6 z for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
3 f9 d7 B. \$ P2 d0 E& y}</P>
<>void CGenetic::statistic(CHROM pop[])
{int i;
3 M" G/ D2 U, K5 G sumfitness=0;
# A) G( Y1 X" |5 T5 O! \ //循环，计算单个染色体的适应度,以及sumfitness
for(i=0;i&ltOPSIZE;i++){
   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
: c0 S( G' m- d' ]" J9 Z# \4 C //选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
. A4 r, z9 L: @1 w! ~# Q  bestchrom[iBestNum++]=pop;
if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
( m+ [, V& V( [7 n}</P>
<>}</P>
- |: s4 i, c) c; _* i) J<>void CGenetic::init()
7 r! d  `7 \3 ?3 O$ }' \{//对种群进行随机初始化
int i,j;
srand( (unsigned)time( NULL ) );</P>
! e% x  B% p' t) N<>if(iVarNo!=0&amp;&amp;IsSetScope)
: X% ~1 k: F  k* K8 {! u+ d  q7 z" y{for(i=0;i&ltOPSIZE;i++){
# s( o" J& ?/ a6 U9 u$ s6 E9 B, G& U for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
9 ~4 D) k: ^/ x% b1 V5 n& K6 I }
7 O6 ?% P0 t" q8 r8 z2 B  \}
}
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)
{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
& \  x! T, a1 s+ F' H varminmax[1]=scope[1];//最大值
}
6 @' M! [  W6 r0 F7 `0 qIsSetScope=true; </P>
<>}</P>
/ B" N6 c% t( U3 b  n& `+ f- C<>double CGenetic::CalFitness(CHROM chrome)
5 I# p* ^) D4 X6 p& D; L: G( d8 x5 w{ double dblResult;
0 I8 e% U2 ~* e5 l' k/ J int i;
for(i=0;i&lt;iVarNo;i++)
6 H% L$ x3 b6 s3 f) Z. ^) J  mData.r(i+1)=chrome.chrom;
5 e+ T6 S$ I- Z$ F' A% B$ ]& ?7 p' i mResult=bpnet-&gt;simulate(mData);
dblResult=mResult.r(1);
return(dblResult);
}</P>

! T9 A! a- a* \* ~% P<P>bool CGenetic::identify(CHROM chrome)
' G# `' N3 O- [% _' X{int i=0;
! w  _. B. ~1 W! ^: O& z bool IsOk=true;;
  O# D/ G1 ~$ L& O6 R1 ]( t8 z for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
+ ?" b) ~- Q. g( ~4 s; l: G( }4 d  {IsOk=false;
  break;}
: ~8 [6 v' }3 Q3 _9 u }
$ s# h) G/ L- ^; q# p2 k2 } return (IsOk);
% u" ^9 R  b- r3 C0 p! z}</P>

7 v0 f3 a" E9 {! Y! L- @+ [<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
for(i=0;i&lt;iVarNo;i++){
  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
$ ?: ]" T1 `7 g( }  L2 g  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
}
1 }% E- ^" q; @ temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
! [6 j# o: P# ` differ=sqrt(temp1)/sqrt(temp2);
return (differ);
}</P>
<P>bool CGenetic::IsNew(CHROM ch)
- I; p# o6 T3 `. X{int i;
! Y6 V: B/ ]" \3 v' a' F bool IsDifferent;
IsDifferent=true;
0 d) o8 t4 \& U0 o for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
5 \7 h8 j; r* s* R/ _  {IsDifferent=false;
      break;
" L3 L+ O+ s% g- ^6 S. H% G" t" U  }
5 [/ d  \- K8 c8 Ereturn (IsDifferent);</P>
, b6 k- T5 j* j) k+ `5 Q3 D<P>}</P>
<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
7 L+ {  O8 B! J{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
1 A9 k6 _# u+ b* K8 y int i=0;
double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
{dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
  temp1+=dblTemp1*dblTemp2;
; k, L, [$ S2 ^, I! {  temp2+=dblTemp1*dblTemp1;
$ {5 n1 b. S  P$ O5 R" c  temp3+=dblTemp2*dblTemp2;
9 I) m& z7 b( K' T. y }
2 ?) x& U- E8 H3 k2 L! R temp2=sqrt(temp2);
2 Q% h# \% h; {. o% c& o temp3=sqrt(temp3);
dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
angle=acos(dblCos);
angle=(angle/pi)*180.0;//转化为角度
* Z  p$ f8 O5 W return (angle);</P>
<P>}</P></DIV>
<DIV class=HtmlCode>
$ D  }0 b; u5 X' V( F<P>// Genetic.h: interface for the CGenetic class.
2 r4 S: V. e! I# M' w' @//
//////////////////////////////////////////////////////////////////////</P>
8 }2 E2 A0 {4 E" o<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
. r6 Z0 R$ ~8 U( {# R& n#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
; I. p0 V, {4 k8 y; ?2 R8 A) `#pragma once
4 b. [' A3 J% L1 D#endif // _MSC_VER &gt; 1000
( d( }3 p$ k+ R$ n3 {5 G/ G#include"definition.h"
, |, _) \# w2 B" X, T, ?0 @9 Z- atypedef struct mychrom{
7 s( K# f1 R$ T: Hdouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
/ K7 ?& S6 x8 L$ O9 ?' K+ D#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
; X: V& M5 s$ |class CGenetic  
7 D  }) p; q& i5 U' ]+ [9 N{
, h# B0 N' N! {public:
* H- s0 c; ]* l4 L4 p bool IsStoped;
double dblAngle;
CHROM best;
Mm mData,mResult;
double dblDifference;//差异〉改值的染色体视为不同
1 x9 J: ~  \0 f9 ~! y/ w double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
* U) W0 V$ U+ u# e# k6 K: L CBpNet * bpnet;
7 O0 u, U& L/ w8 F: e& e2 |; Z6 } //double (* obj_fun)();
3 @* ~; b# g1 @! a! _/ x double CalFitness(CHROM chrome);//计算适应度函数
5 a# L1 t+ i/ ~$ G! n* v long gen;//当前进化代数
0 ^5 Y* m2 n0 e1 @ void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
double randxy(double x,double y);//产生x,y之间的随机数
- C6 K) H  V& [! ^+ e" S+ N void statistic(CHROM pop[]);
CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
  Z$ M& _. L6 K0 i+ T1 L: z void generation();//一次进化
( O& _* e' c# [5 T8 C$ ]0 o7 i4 b7 K int rselect();//轮盘赌选择
CHROM newpop[POPSIZE];//种群
4 w$ u9 I2 o# z5 }+ i CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
5 B  H/ |4 q" Q5 H" p5 l long maxgen;//最大进化代数
int iVarNo;//染色体数目
, x/ S3 c/ z6 f double sumfitness;
) A& _" q) `, n- S CGenetic();
- h! a6 w% l, [% D virtual ~CGenetic();</P>
5 F! M) c3 U8 [) d$ L<P>private:
6 V- o- t1 G- A0 n  s9 E& C4 u, y 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();//初始化，设置初始染色体
. k$ [' L5 ~0 u/ o void mutation(CHROM *chrome);//对新染色体进行变异
& F+ E. b) f3 u7 B) w: o! a" O. y bool flip(double possibility);//测试
$ ~& B  e8 {: C$ s7 d //交叉操作，iPlace指明新染色体位置
void cross(CHROM chrom1,CHROM chrom2,int iPlace);
. g) N; R6 J* l9 T" w bool IsSetScope;
& y: Y! S+ x8 y- `
};</P>
! y5 e! v/ v) y# X<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

</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>