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

ilikenba

<DIV class=HtmlCode>
<>// Genetic.cpp: implementation of the CGenetic class.
  K" i* T# f+ O. L/ i! _6 V# }5 \//
+ d( Q+ V% a' z1 ^$ _+ x//////////////////////////////////////////////////////////////////////</P>
<>#include "stdafx.h"</P>
8 \) a* v5 n/ |+ {5 t<>#include "Genetic.h"
6 D* v' W: H* a#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
5 s, z3 h2 y% H( \- J#define new DEBUG_NEW
#endif
/////张纯禹  2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
4 l' {/ X& H7 N+ H- m//////////////////////////////////////////////////////////////////////</P>
# i7 K& ]8 y! l: U+ O<>CGenetic::CGenetic()
4 h  M5 X! d; \{pmutation=0.01;//变异概率
) P$ k/ h& G; c# Y pcross=0.9;//交叉概率
% i7 N% a9 S. d8 o& s, q maxgen=5000;//最大进化代数
iVarNo=0;//染色体数目
sumfitness=0.0;
- y) i! b+ ^0 r. y gen=0;
# ?/ `) J- {" y8 P7 l+ b IsSetScope=false;//还未设定个变量范围
* l5 j( j' P9 T3 `$ W IsStoped=false;
* F' `9 K7 v" g8 E for(int i=0;i&lt;MAXBESTNUM;i++)
2 w" |1 z' V) a   bestchrom.fitness=0;
iBestNum=0;
  d3 d$ V& ~1 b) f; Z. B7 d dblCre=0.0;
0 k% r' e+ |5 S- U$ g dblDifference=0.15;
best.fitness=0.0;
% U* A: e% Y0 d8 H
5 v) A; \* z0 a initM(MATCOM_VERSION);
7 E( \) _# |& E8 D }</P>
% U+ O% T8 Q; k# \3 r  V+ n% K+ j<>CGenetic::~CGenetic()
) g5 f0 p' Q) o0 r; M5 w{exitM();
}</P>
! C, H" e: O# X8 T# B# a$ h<>int CGenetic::rselect()
5 P- D. \7 [, L" Y! G3 e{double rand1,partsum;
$ d# Q$ j5 G4 [; M6 B4 ] int j=0;
partsum=0;
rand1=rand()*sumfitness;
do{
) L# K$ Y. G+ D5 {* m  |! w  partsum=partsum+newpop[j].fitness;
  j++;
}while((partsum&lt;rand1)&amp;&amp;(j&ltOPSIZE));
) V) f" |; Q2 D8 |5 J! s& ?* p return (j-1);
}</P>
<>void CGenetic::generation()
- ^* ]/ [* W4 V- {$ h. v  T{int i,r1,r2;
CHROM tempChrom;
/ Q+ C# b; G/ n) W  Y! L$ R //进行统计，计算newpop单个染色体的适应度，选出最优染色体
statistic(newpop);
//从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
- R! U; m+ n6 R) R4 R    for(i=0;i&ltOPSIZE;i+=2){
  r1=rselect();
  r2=rselect();
; ?9 A; ]# m/ S/ X. [  cross(newpop[r1],newpop[r2],i);
}</P>
! d! W* f" Y5 X8 d) K<> // oldpop,newpop进行调换
for(i=0;i&ltOPSIZE;i++){
) n) Y4 C- D  d  tempChrom=newpop;
  newpop=oldpop;
( M  S% n% u2 D& P& o* A  oldpop=tempChrom;
}
//从1到POPSIZE循环，对newpop进行变异
    for(i=0;i&ltOPSIZE;i++)
     mutation(&amp;newpop);
}</P>
  B7 \2 @6 T: F7 |. p<>bool CGenetic::begin()
* r; P3 ?: J7 N{MSG msg;
8 ^9 ^% W$ c% f9 ?' l  h' H9 { mData=zeros(1,bpnet-&gt;iInput);
1 i/ \6 Z/ ^$ J6 z$ T mResult=zeros(1,bpnet-&gt;iOutput);
# @, t6 a9 Y5 e; lfor(int i=gen;i&lt;maxgen;i++)
' f9 h; f& a* m+ I{if(IsStoped)
* T$ o# `# Q1 ^9 W$ Q; E  break;
if(bpnet-&gt;iOutput&gt;1){
::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
return(false);
}
/ V0 w) c. n: H/ R% ? if(gen==0)
) ^) P$ M  `" Z4 p. j/ P" n. V5 R  init();//如果刚开始运算，初始化
: h' H2 z# Z0 Y% ~  Q2 i generation();
0 y% L4 V2 m9 |$ L gen++;
+ S# n6 w3 |- ]7 F4 A8 C8 [ //防止假死机
:eekMessage(&amp;msg,NULL,0,0,PM_REMOVE);
:ispatchMessage(&amp;msg);
msg.message=-1;
% K) m' Z! m3 ?5 B* q :ispatchMessage(&amp;msg);//这样可以消除屏闪
: @: p, y( U( D3 Z! a( `}</P>
<>return(true);
" X5 l+ b6 X! `. E}</P>
<>
void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
" n" B' V! e; K$ _ do{if(flip(pcross)){//交叉概率
. C/ C, p* G7 V! r9 w, B c=rand();
1 B) A" J: f; l& P( t9 n    for(i=0;i&lt;iVarNo;i++){
oldpop[iPlace].chrom=c*chrom1.chrom+(1-c)*chrom2.chrom;
, {  U0 d8 ~& }: [ oldpop[iPlace+1].chrom=(1-c)*chrom1.chrom+c*chrom2.chrom;
}
1 m& u* {2 M! s$ k2 O$ G' a! [ }
else//直接赋值，不再交叉
{oldpop[iPlace]=chrom1;
  {; e- P* {8 A( Q9 Y/ @, t  oldpop[iPlace+1]=chrom2;
0 w; K0 x) @) g9 C' y2 u6 W* U7 x/ L }
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));</P>
<>}</P>
9 Z  r6 e& Q% o  g<>bool CGenetic::flip(double possibility)
{double ppp;
3 ^: L& z' w2 R; Q% [" Cppp=rand();
& Z+ o- S8 f) G( i  N; I" T: \if(ppp&lt;=possibility)
  H6 r1 s+ K& @, m! k& \( B; S$ |4 n return (true);
8 _8 ]5 l5 b# W, }5 F5 o2 ?7 @  |2 P1 ]8 delse
0 i7 R1 I. x' G return (false);
}</P>
<>void CGenetic::mutation(CHROM *chrome)
5 q$ B: x' y  o: K! g/ s{double m=10;
int i=0;
CHROM temp1,temp2;
if(flip(pmutation)){ //以变异概率进行变异
% d" w) j* n' T* j/ o  do{ for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
1 r4 n2 Z) W8 M! }         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++)
: L+ n9 b) Z4 Z4 M# [0 |: n. |0 r8 m( T' S; w     temp2.chrom+=m*temp1.chrom;
, K7 F) C* b$ r+ r! X0 e0 e    if(!identify(temp2))
     m=(double)m/(double)(2.0);
( ]! z, k' e! p- H  }while(!identify(temp2));
$ K0 h6 j5 Y8 Y5 C4 J0 ]' H }
else{
  for(i=0;i&lt;iVarNo;i++)
     temp2.chrom=chrome-&gt;chrom;
}
for(i=0;i&lt;iVarNo;i++)
  chrome-&gt;chrom=temp2.chrom;
}</P>
- L# k. ?9 Z  @# u' g<>void CGenetic::statistic(CHROM pop[])
{int i;
: G! d; f# Z" I% Z" X sumfitness=0;
//循环，计算单个染色体的适应度,以及sumfitness
0 V; D9 d  r/ K* H' t7 @, G for(i=0;i&ltOPSIZE;i++){
; C8 r5 p+ F- I, M1 Z( j   pop.fitness=CalFitness(pop);
   sumfitness+=pop.fitness;}
//选出符合条件的染色体
for(i=0;i&ltOPSIZE;i++){
! k: l9 O! T# t$ g4 i if(pop.fitness&gt;=dblCre&amp;&amp;IsNew(pop))
  bestchrom[iBestNum++]=pop;
+ C; z' i0 l, }* O+ f( m4 w/ z+ C8 y if(pop.fitness&gt;best.fitness)
  best=pop;//纪录最佳染色体
7 r1 N) Y2 c* d}</P>
<>}</P>
<>void CGenetic::init()
{//对种群进行随机初始化
$ ?, ?7 U. q5 Sint i,j;
srand( (unsigned)time( NULL ) );</P>
: W' l$ X5 z0 k8 K/ N4 R2 Y) N<>if(iVarNo!=0&amp;&amp;IsSetScope)
{for(i=0;i&ltOPSIZE;i++){
for(j=0;j&lt;iVarNo;j++){//在最值间随机赋值
: q, m; J" b: _; R+ e/ P  newpop.chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop.chrom[j]=newpop.chrom[j];
}
. J5 Y* g: q: ~8 y8 o# j' c/ X5 _0 P( T: x}
# F+ g2 P5 Y/ |8 v}
8 n: G6 o6 x* m4 W7 a% B  r else
0 z, n# g) \+ o {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
6 W9 z7 H* I5 A% {6 P, W$ s }
}</P>

<>double CGenetic::randxy(double x, double y)
. ], L* A2 E9 F5 p0 a: O3 ]; l{ return (x+(y-x)*rand());</P>
6 f1 g# f+ l. ]4 e  a; t<>}</P>
- a5 v% G; ^! t" K/ K<>void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i&lt;iNo;i++)
{varminmax[0]=scope[0];//最小值
$ C1 H( K) [' r. B; o varminmax[1]=scope[1];//最大值
5 L) N3 W: o3 w6 m/ A, `}
IsSetScope=true; </P>
<>}</P>
<>double CGenetic::CalFitness(CHROM chrome)
  ]  A: x; j$ K4 e{ double dblResult;
int i;
& k& d& F; e, h; A9 x for(i=0;i&lt;iVarNo;i++)
, Q4 M1 y' y3 F/ ^* i1 M  mData.r(i+1)=chrome.chrom;
mResult=bpnet-&gt;simulate(mData);
. G) l* d5 R3 K* F. h& t0 R dblResult=mResult.r(1);
return(dblResult);
! E8 D$ y6 ?! c& |% Y# }# d}</P>

& y0 ?( U2 X1 u2 m! a% x# f% A- E<P>bool CGenetic::identify(CHROM chrome)
" K/ ~7 Z; }% l& V2 k{int i=0;
0 |. h: S7 p+ o bool IsOk=true;;
' [9 I: c2 c) x* P& z; ^+ N for(i=0;i&lt;iVarNo;i++){
  if(chrome.chrom&gt;varminmax[1]||chrome.chrom&lt;varminmax[0])
. Y8 r# a# q' ^9 }0 M+ S% S3 A  {IsOk=false;
  break;}
}
return (IsOk);
}</P>

<P>double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
int i;
7 y) [0 S, B% U, S% ? for(i=0;i&lt;iVarNo;i++){
% v" a1 a+ r! m7 r; C( p9 v9 H  dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
; o. g" U4 K1 c) k, Y1 q& D: y( P3 [4 p  temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
8 n1 T5 n! n. }: H6 X$ e5 {     temp2+=dblTemp1*dblTemp1;
+ n' G8 z! o  U; u1 C5 h1 R2 {  temp3+=dblTemp2*dblTemp2;
- O* Y# G& v1 m! z }
temp2=(temp2&gt;temp3)?temp2:temp3;//取较大者
# v" P) @; C0 U1 b/ A' b3 y8 j differ=sqrt(temp1)/sqrt(temp2);
& C6 n; g/ U3 u' ?( s2 }% P return (differ);
) r9 N8 C) u$ [0 b2 h3 Z0 G}</P>
. R1 d) V2 Y0 s: p- V<P>bool CGenetic::IsNew(CHROM ch)
7 R: c8 e( I5 D' N6 d2 Z# R' |: s{int i;
bool IsDifferent;
IsDifferent=true;
for(i=0;i&lt;iBestNum;i++)
  if((difference(ch,bestchrom)&lt;dblDifference)&amp;&amp;(angle(ch,bestchrom)&lt;dblAngle))
  {IsDifferent=false;
6 s: R5 A) o. U$ Z5 }* I4 m" ^      break;
  }
/ H& U+ _. d3 Q. @  d8 Freturn (IsDifferent);</P>
<P>}</P>
" n3 q( I( z8 {$ J8 Y+ v, @9 p1 }- J<P>double CGenetic::angle(CHROM ch1, CHROM ch2)
0 B- R) `6 O% ?# u6 m! n{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
1 I' I6 Z  d9 g( q  h int i=0;
# V1 R" V1 P7 k8 l* x3 S double dblTemp1,dblTemp2;
for(i=0;i&lt;iVarNo;i++)
  h% }9 x, M" N* D% e! Z; `, m  k {dblTemp1=ch1.chrom/(varminmax[1]-varminmax[0]);
  dblTemp2=ch2.chrom/(varminmax[1]-varminmax[0]);
& U; W/ V. F' r& U& R  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
: x; x; e3 b$ u0 W" }  temp3+=dblTemp2*dblTemp2;
}
temp2=sqrt(temp2);
temp3=sqrt(temp3);
! L; m. x4 G, V5 I: [) D dblCos=temp1/(temp2*temp3);
pi=acos(-1.0);
+ ?# Q& ^* f2 N. M7 X/ x( V& d angle=acos(dblCos);
6 M- E5 Q. n" [, n( }7 g+ q5 ]# e angle=(angle/pi)*180.0;//转化为角度
return (angle);</P>
- a( t. L, o, Y5 t<P>}</P></DIV>
2 J1 |0 |* b& H" w! G# s  g<DIV class=HtmlCode>
0 J2 g$ E# T/ x6 l" S; b! b<P>// Genetic.h: interface for the CGenetic class.
//
//////////////////////////////////////////////////////////////////////</P>
( u' f7 c& c+ y! F# l<P>#if !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)
& q7 a- [% s- q' }0 R#define AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_</P>
<P>#if _MSC_VER &gt; 1000
' t% @/ N4 J0 w#pragma once
$ l" u. b) ?! B$ m- O" h#endif // _MSC_VER &gt; 1000
2 z; c5 j2 ~! M9 G0 u#include"definition.h"
typedef struct mychrom{
4 ?& ^/ t$ H5 pdouble chrom[MAXVARNO];
double fitness;//适应度
}CHROM;
#include "BpNet.h"
////////张纯禹 2001年   <a href="mailtchunyu79@hotmail.com" target="_blank" >chunyu79@hotmail.com</A>
class CGenetic  
& g- K* `! {, W5 _{
  s" m, Q2 _4 F2 p$ R" s) _- `public:
3 t' Z! D8 i. B- k- ?) p; z1 M bool IsStoped;
2 `' t. y4 G7 U7 [) R! C8 K double dblAngle;
% z; [5 z2 I7 k; D, d CHROM best;
Mm mData,mResult;
# p0 J% {$ P& B; r double dblDifference;//差异〉改值的染色体视为不同
, E+ l2 H7 D8 ~& a; d4 M double dblCre;//适应度&gt;改值的染色体符合条件
int iBestNum;//符合条件的染色体数目
) V% o1 d, m3 w' J1 t1 ^5 J; K3 f- Q CBpNet * bpnet;
//double (* obj_fun)();
/ e$ f) H" h1 I; Q' y& ?5 c2 B double CalFitness(CHROM chrome);//计算适应度函数
1 r/ y4 Q) O3 w6 e8 ~  M long gen;//当前进化代数
, ~  F9 T9 j4 P/ U& T; K3 f% n void setscope(double scope[MAXVARNO][2],int iNo);//设置染色体取值范围
4 ?+ ?  Y- e  x double randxy(double x,double y);//产生x,y之间的随机数
7 ]0 @( [& U$ |$ `+ O8 A void statistic(CHROM pop[]);
1 ~; c. k% z9 E6 {/ x5 w  r CHROM bestchrom[MAXBESTNUM];//最优染色体
bool begin();//主函数
void generation();//一次进化
1 ^1 A% R2 g+ _) P int rselect();//轮盘赌选择
+ _) T* Q$ G0 ? CHROM newpop[POPSIZE];//种群
CHROM oldpop[POPSIZE];//种群
double pmutation;//变异概率
double pcross;//交叉概率
long maxgen;//最大进化代数
int iVarNo;//染色体数目
& t& X5 I' p8 g double sumfitness;
CGenetic();
virtual ~CGenetic();</P>
0 k) {: G. L. `<P>private:
double angle(CHROM ch1,CHROM ch2);
bool IsNew(CHROM ch);//判断是否为符合条件的新染色体
double difference(CHROM ch1,CHROM ch2);//量个染色体之间的差异,用以区别</P>
<P> bool identify(CHROM chrome);//验证是否为合法的染色体
; K& j0 \( W/ g; m. F9 Q double varminmax[MAXVARNO][2];
# @% u" l7 n: ~$ g" v$ C1 Q void init();//初始化，设置初始染色体
# H" e. z" y  Y+ \ void mutation(CHROM *chrome);//对新染色体进行变异
, s. G/ R5 [9 }4 @6 j bool flip(double possibility);//测试
//交叉操作，iPlace指明新染色体位置
/ W+ }# V8 u2 R2 E$ k void cross(CHROM chrom1,CHROM chrom2,int iPlace);
/ j! ?& l* K( V. T, I4 @0 a9 h" T2 M4 v bool IsSetScope;
) |5 Q7 G( I+ S3 H2 d7 G
9 {2 _1 P' j0 G& ^/ y};</P>
9 a3 j- @: b( {) ^; D  I5 M<P>#endif // !defined(AFX_GENETIC_H__72C36058_C073_487F_BD99_D8BD4A59EFF0__INCLUDED_)

: f1 G$ ~4 a) W# |/ R</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>