遺傳演算法人工智慧

A. 人工智慧之進化演算法

進化計算的三大分支包括：遺傳演算法(Genetic Algorithm ，簡稱GA)、進化規劃(Evolu-tionary Programming，簡稱EP)和進化策略(Evolution Strategies ，簡稱ES)。這三個分支在演算法實現方面具有一些細微的差別，但它們具有一個共同的特點，即都是藉助生物進化的思想和原理來解決實際問題。

遺傳演算法是一類通過模擬生物界自然選擇和自然遺傳機制的隨機化搜索演算法，由美國Holand J教授於1975年首次提出。它是利用某種編碼技術作用於稱為染色體的二進制數串，其基本思想是模擬由這些串組成的種群的進化過程，通過有組織的、然而是隨機的信息交換來重新組合那些適應性好的串。遺傳演算法對求解問題的本身一無所知，它所需要的僅是對演算法所產生的每個染色體進行評價，並根據適應性來選擇染色體，使適應性好的染色體比適應性差的染色體有更多的繁殖機會。遺傳演算法尤其適用於處理傳統搜索方法難於解決的復雜的非線性問題，可廣泛用於組合優化、機器學習、自適應控制、規劃設計和人工生命等領域，是21世紀有關智能計算中的關鍵技術之一。

1964年，由德國柏林工業大學的RechenbergI等人提出。在求解流體動力學柔性彎曲管的形狀優化問題時，用傳統的方法很難在優化設計中描述物體形狀的參數，然而利用生物變異的思想來隨機地改變參數值並獲得了較好效果。隨後，他們便對這種方法進行了深入的研究和發展，形成了進化計算的另一個分支——進化策略。

進化策略與遺傳演算法的不同之處在於：進化策略直接在解空間上進行操作，強調進化過程中從父體到後代行為的自適應性和多樣性，強調進化過程中搜索步長的自適應性調節;而遺傳演算法是將原問題的解空間映射到位串空間之中，然後再施行遺傳操作，它強調個體基因結構的變化對其適應度的影響。

進化策略主要用於求解數值優化問題。

進化規劃的方法最初是由美國人Fogel LJ等人在20世紀60年代提出的。他們在人工智慧的研究中發現，智能行為要具有能預測其所處環境的狀態，並按照給定的目標做出適當的響應的能力。在研究中，他們將模擬環境描述成是由有限字元集中符號組成的序列。

進化演算法與傳統的演算法具有很多不同之處，但其最主要的特點體現在下述兩個方面：

進化計算的智能性包括自組織、自適應和自學習性等。應用進化計算求解問題時，在確定了編碼方案、適應值函數及遺傳運算元以後，演算法將根據「適者生存、不適應者淘汰"的策略，利用進化過程中獲得的信息自行組織搜索，從而不斷地向最佳解方向逼近。自然選擇消除了傳統演算法設計過程中的-一個最大障礙：即需要事先描述問題的全部特點，並說明針對問題的不同特點演算法應採取的措施。於是，利用進化計算的方法可以解決那些結構尚無人能理解的復雜問題。

進化計算的本質並行性表現在兩個方面：

一是進化計算是內在並行的，即進化計算本身非常適合大規模並行。

二是進化計算的內含並行性，由於進化計算採用種群的方式組織搜索，從而它可以同時搜索解空間內的多個區域，並相互交流信息，這種搜索方式使得進化計算能以較少的計算獲得較大的收益。

B. 求助：人工智慧「遺傳演算法求解f(x)=xcosx+2的最大值」

為了方便我只求了-3.14到3.14之間的最大值，你可以自己改一下，不過范圍大了之後，種群也因該擴大，我的種群只有66個

結果：極值點（-3.141593，5.141593）

我又算了一下-100到100之間的極大值

結果：極值點（-97.399473,99.394504)

-1000到1000之間的極大值

結果：（999，1001）

-2000到2000之間的極大值

結果：（1998.053550，2000.053163）

以上結果我用matlab畫圖驗證了，沒問題。
希望再給加點分，呵呵

//中國電子科技集團公司

//第一研究室

//呼文韜

//[email protected]

//隨機初始種群
//編碼方式為格雷碼
//選擇方法為隨機遍歷
//採用了精英保存策略
//採用了自適應的交叉率和變異率
//採用了與模擬退火演算法相結合的尺度變換
//採用了均勻交叉法

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <windows.h>
#define IM1 2147483563
#define IM2 2147483399
#define AM (1.0/IM1)
#define IMM1 (IM1-1)
#define IA1 40014
#define IA2 40692
#define IQ1 53668
#define IQ2 52774
#define IR1 12211
#define IR2 3791
#define NTAB 32
#define NDIV (1+IMM1/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0-EPS)
#define zhenjuli 0.005
#define PI 3.14159265358
#define T0 100000//溫度要取得很高才行。
#define zhongqunshu1 200
#define zuobianjie -2000
#define youbianjie 2000
unsigned int seed=0; //seed 為種子，要設為全局變數
void mysrand(long int i) //初始化種子
{
seed = -i;
}
long a[1];
//double hunn;
//double c=4;
//設置全局變數
struct indivial
{
unsigned *chrom; //染色體；
double geti;//變數值
double shiying; //目標函數的值；
double fitness; //變換後的適應度值；
};
indivial *zuiyougeti;//精英保存策略
int zhongqunshu; //種群大小
indivial *nowpop;//當前代
indivial *newpop;//新一代
double sumfitness;//當代的總適應度fitness
double sumshiying;//當代的總適應度shiying
double maxfitness;//最大適應度
double avefitness;//平均適應度
double maxshiying;//最大適應度
double avgshiying;//平均適應度
float pc;//交叉概率
float pm;//變異概率
int lchrom;//染色體長度
int maxgen;//最大遺傳代數
int gen;//遺傳代數
//函數
int flipc(double ,double );//判斷是否交叉
int flipm(double );//判斷是否變異
int rnd(int low,int high);//產生low與high之間的任意數
void initialize();//遺傳演算法初始化
void preselectfitness(); //計算sumfiness,avefitness,maxfitness
void generation();
double suijibianli();//產生隨機遍歷指針
int fu(float );//選擇要復制的個體
void crossover(indivial ,indivial ,indivial &,indivial &);//交叉
void bianyi(indivial &);//變異
void mubiaohanshu(indivial &);//計算適應度
void chibianhuan(indivial &);//對shiying進行尺度變換賦給fitness
double ran1(long *);//隨機數初始
void bianma(double bianliang,unsigned *p);//編碼
double yima(unsigned *p);
void guanjiancanshujisuan();//計算shiying,根據shiying計算sumshiying,對shiying進行尺度變換變成fitness,根據fitness計算sumfitness，avefitness，maxfitness
void jingyingbaoliu();
void glp(int n,int s,int *,int (*)[1],float (*)[1]);//glp生成函數
BOOL Exist(int Val, int Num, int *Array);//判斷一個數在前面是否出現過
int cmpfitness(const void *p1,const void *p2)
{
float i=((indivial *)p1)->shiying;//現在是按照"適應度"排序，改成"個體"的話就是按照"個體"排序
float j=((indivial *)p2)->shiying;
return i<j ? -1:(i==j ? 0:1);//現在是按升序牌排列，將1和-1互換後就是按降序排列
}
void main()
{
initialize();
cout<<zuiyougeti->geti<<" "<<zuiyougeti->shiying<<endl;/////////////
for(gen=1;gen<maxgen;gen++)
{ generation();
}
jingyingbaoliu();
cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti<<" "<<setiosflags(ios::fixed)<<setprecision(6)<<(zuiyougeti->shiying)<<endl;////////////////
delete [] newpop;
delete [] nowpop;
delete [] zuiyougeti;
system("pause");
}
void initialize()
{
int q[zhongqunshu1][1],s=1;
float xx[zhongqunshu1][1];//生成的glp用x儲存
int h[1]={1};//生成向量
zuiyougeti=new indivial;//最優個體的生成
zhongqunshu=200;//種群數量
nowpop=new indivial[zhongqunshu1];//當代
newpop=new indivial[zhongqunshu1];//新一代
maxgen=150;//最大代數
gen=0;//起始代
lchrom=22;//基因數量的初始化
mysrand(time(0));//隨機數種子
a[0]=seed;//隨機數種子
//對最優個體的初始化
zuiyougeti->geti=0;
zuiyougeti->fitness=0;
zuiyougeti->shiying=0;
//
glp(zhongqunshu,s,h,q,xx);
//for(int i=0;i<zhongqunshu1;i++)//產生初始種群
//{
// for(int j=0;j<s;j++)
// {
// nowpop[i].geti=zuobianjie+(youbianjie-zuobianjie)*xx[i][j];
// }
//}
for(int i=0;i<zhongqunshu1;i++)//產生初始種群
{
nowpop[i].geti=zuobianjie+(youbianjie-(zuobianjie))*ran1(a);
}
//nowpop[0].geti=999;//////////////////////////
guanjiancanshujisuan();
jingyingbaoliu(); //精英保留的實現
guanjiancanshujisuan();//計算shiying,根據shiying計算sumshiying,對shiying進行尺度變換變成fitness,根據fitness計算sumfitness，avefitness，maxfitness
}
void jingyingbaoliu() //精英保留的實現
{
indivial *zuiyougetiguo;
zuiyougetiguo=new indivial[zhongqunshu1];//建立一個過渡數組
for(int i=0;i<zhongqunshu;i++)//將當代個體復制到過渡數組中
zuiyougetiguo[i]=nowpop[i];
qsort(zuiyougetiguo,zhongqunshu1,sizeof(indivial),&cmpfitness);//按fitness升序排序
// cout<<"zuiyougetiguo適應度:"<<zuiyougetiguo[zhongqunshu1-1].shiying<<endl;///////////
// cout<<"zuiyougeti適應度:"<<zuiyougeti->shiying<<endl;///////////////////
//system("pause");
if(zuiyougetiguo[zhongqunshu-1].shiying>zuiyougeti->shiying)
{
*zuiyougeti=zuiyougetiguo[zhongqunshu1-1];//如果最優個體的fitness比當代最大的fitness小則用當代的代替之
//cout<<"zuiyougetiguo個體:"<<zuiyougetiguo[zhongqunshu1-1].geti<<endl;/////////////
//cout<<"zuiyougeti個體:"<<zuiyougeti->geti<<endl;/////////////
}
else
nowpop[rnd(0,(zhongqunshu1-1))]=*zuiyougeti;//否則的話從當代中隨機挑選一個用最優個體代替之
delete [] zuiyougetiguo;//釋放過渡數組
}
void guanjiancanshujisuan()//計算shiying,根據shiying計算sumshiying,對shiying進行尺度變換變成fitness,根據fitness計算sumfitness，avefitness，maxfitness
{
for(int i=0;i<zhongqunshu;i++)//計算shiying
mubiaohanshu(nowpop[i]);
for(i=0;i<zhongqunshu;i++)//對shiying進行尺度變換變成fitness
chibianhuan(nowpop[i]);
preselectfitness();//根據fitness計算sumfitness，avefitness，maxfitness
}
void mubiaohanshu(indivial &bianliang)//計算shiying
{
bianliang.shiying=(bianliang.geti*cos(bianliang.geti)+2.0);//目標函數
}
void chibianhuan(indivial &bianliang)//對shiying進行尺度變換變成fitness
{
double T;//退火溫度
T=T0*(pow(0.99,(gen+1-1)));
double sum=0;
for(int j=0;j<zhongqunshu;j++)
sum+=exp(nowpop[j].shiying/T);
bianliang.fitness=exp(bianliang.shiying/T)/sum;//算出fitness
}
void preselectfitness()//根據fitness計算sumfitness，avefitness，maxfitness
{
int j;
sumfitness=0;
for(j=0;j<zhongqunshu;j++)
sumfitness+=nowpop[j].fitness;
indivial *guo;
guo=new indivial[zhongqunshu1];
for(j=0;j<zhongqunshu;j++)
guo[j]=nowpop[j];
qsort(guo,zhongqunshu1,sizeof(indivial),&cmpfitness);
maxfitness=guo[zhongqunshu1-1].fitness;
avefitness=sumfitness/zhongqunshu1;
delete [] guo;
}
void generation()
{
indivial fuqin1,fuqin2,*pipeiguo,*pipeichi;
int *peiishuzu;//用來存放產生的隨機配對
pipeiguo=new indivial[zhongqunshu1];
pipeichi=new indivial[zhongqunshu1];
peiishuzu=new int[zhongqunshu1];
int member1,member2,j=0,fujishu=0,i=0,temp=0,tt=0;
float zhen;
//隨機遍歷的實現
for(zhen=suijibianli();zhen<1;(zhen=zhen+zhenjuli))//設定指針1/66
{
pipeichi[fujishu]=nowpop[fu(zhen)];
fujishu++;
}

//交叉與變異的實現
//交叉
for(i=0;i<zhongqunshu1;i++)
{
peiishuzu[i]=-1;
}
for (i=0; i<zhongqunshu1; i++)
{
temp =rnd(0,zhongqunshu1-1); //產生值在0-zhongqunshu1-1的隨機數
while(Exist(temp, i, peiishuzu))//判斷產生的隨機數是否已經產生過，如果是，則再產生一個隨機數
{
temp =rnd(0,zhongqunshu1-1);
}
//如果沒有的話，則把產生的隨機數放在peiishuzu中
*(peiishuzu+i) = temp;
}
for(i=0;i<zhongqunshu1-1;i=i+2)
{
fuqin1=pipeichi[peiishuzu[i]];
fuqin2=pipeichi[peiishuzu[i+1]];
crossover(fuqin1,fuqin2,newpop[i],newpop[i+1]);
}
for(j=0;j<zhongqunshu1;j++)
{
//if(newpop[j].geti<-1000)
//cout<<"個體數值小於下界了";
nowpop[j].geti=newpop[j].geti;
}
//
guanjiancanshujisuan();
//變異的實現
for(j=0;j<zhongqunshu;j++)
{
bianyi(nowpop[j]);
}
//
guanjiancanshujisuan();
//精英保留的實現
jingyingbaoliu();
//
guanjiancanshujisuan();
delete [] peiishuzu;
delete [] pipeichi;
delete [] pipeiguo;
}
void crossover(indivial parent1,indivial parent2,indivial &child1,indivial &child2)//交叉
{
int j;
unsigned *panan;
panan=new unsigned[lchrom];
parent1.chrom=new unsigned[lchrom];
parent2.chrom=new unsigned[lchrom];
child1.chrom=new unsigned[lchrom];
child2.chrom=new unsigned[lchrom];
//cout<<"jiaocha"<<endl;///////////////////////
bianma(parent1.geti,parent1.chrom);
bianma(parent2.geti,parent2.chrom);
if(flipc(parent1.fitness,parent2.fitness))
{
for(j=0;j<lchrom;j++)
panan[j]=rnd(0,1);
//for(j=0;j<lchrom;j++)////////////////
// {
// cout<<panan[j];/////////////
// }
// cout<<endl;////////////////
// system("pause");////////////////
for(j=0;j<lchrom;j++)
{
if(panan[j]==1)
child1.chrom[j]=parent1.chrom[j];
else
child1.chrom[j]=parent2.chrom[j];
}
for(j=0;j<lchrom;j++)
{
if(panan[j]==0)
child2.chrom[j]=parent1.chrom[j];
else
child2.chrom[j]=parent2.chrom[j];
}
//for(j=0;j<lchrom;j++)////////////////
//{
// cout<<child1.chrom[j];/////////////
// }
//cout<<endl;////////////////
// system("pause");////////////////
child1.geti=yima(child1.chrom);
child2.geti=yima(child2.chrom);
delete [] child2.chrom;
delete [] child1.chrom;
delete [] parent2.chrom;
delete [] parent1.chrom;
delete [] panan;
}
else
{
for(j=0;j<lchrom;j++)
{
child1.chrom[j]=parent1.chrom[j];
child2.chrom[j]=parent2.chrom[j];
}
child1.geti=yima(child1.chrom);
child2.geti=yima(child2.chrom);
delete [] child2.chrom;
delete [] child1.chrom;
delete [] parent2.chrom;
delete [] parent1.chrom;
delete [] panan;
}
}
void bianyi(indivial &child)//變異
{
child.chrom=new unsigned[lchrom];
//cout<<"變異"<<endl;
bianma(child.geti,child.chrom);
for(int i=0;i<lchrom;i++)
if(flipm(child.fitness))
{
if(child.chrom[i]=0)
child.chrom[i]=1;
else
child.chrom[i]=0;
}
child.geti=yima(child.chrom);
delete [] child.chrom;
}
void bianma(double bianliang,unsigned *p)//編碼
{
unsigned *q;
unsigned *gray;
q=new unsigned[lchrom];
gray=new unsigned[lchrom];
int x=0;
int i=0,j=0;
if(bianliang<zuobianjie)///////////////////
{
cout<<"bianliang:"<<bianliang<<endl;/////////
system("pause");
}
//cout<<youbianjie-(zuobianjie)<<endl;
//system("pause");
x=(bianliang-(zuobianjie))*((pow(2,lchrom)-1)/(youbianjie-(zuobianjie)));
//cout<<x<<endl;///////////
if(x<0)
system("pause");///////////
for(i=0;i<lchrom;i++)
{
q[i]=0;
p[i]=0;
}
i=0;
while (x!=0&&(i!=lchrom))
{
q[i]=(unsigned)(x%2);
x=x/2;
i++;
}
// for(i=0;i<lchrom;i++)//////////////////
// cout<<q[i];///////////////
// cout<<endl;///////////
int w=lchrom-1;
if(q[w]!=0&&q[w]!=1)
system("pause");
for(j=0;j<lchrom&&w>0;j++)
{
p[j]=q[w];
w--;
}
//cout<<"yuanma"<<endl;
//for(j=0;j<lchrom;j++)///////////
// cout<<p[j];////////
//cout<<endl;////////////////////
gray[0]=p[0];
for(j=1;j<lchrom;j++)
{
if(p[j-1]==p[j])
gray[j]=0;
else if(p[j-1]!=p[j])
gray[j]=1;
}
for(j=0;j<lchrom;j++)
p[j]=gray[j];
//cout<<"geleima"<<endl;
//for(j=0;j<lchrom;j++)///////////
// cout<<p[j];////////
//cout<<endl;////////////////////
//system("pause");///////////

delete [] gray;
delete [] q;
}
double yima(unsigned *p) //解碼
{

int i=0;
// for(i=0;i<lchrom;i++)/////////
// {
// cout<<p[i];//////
// }
// cout<<endl;/////////
// system("pause");//////////
int x=0;
unsigned *q;
q=new unsigned[lchrom];
q[0]=p[0];
// cout<<q[0]<<endl;//////////////////
// system("pause");//////////

for(int j=1;j<lchrom;j++)
{
if(q[j-1]==p[j])
q[j]=0;
else if(q[j-1]!=p[j])
q[j]=1;
}
// for(i=0;i<lchrom;i++)//////
// {
// cout<<q[i];//////////
// if(q[i]!=0&&q[i]!=1)
// {
// cout<<q[i];
// system("pause");
// }
// }
// cout<<endl;////////
// system("pause");///////////////////
for(i=0;i<lchrom;i++)
x=x+q[i]*pow(2,(lchrom-i-1));
if(x<0)
{
cout<<"解碼出錯1"<<endl;
system("pause");
}
//cout<<"x:"<<x<<endl;
double bianliang;
//cout<<pow(2,22)<<endl;
//cout<<2000*x<<endl;
//cout<<(x*(2000/(pow(2,22)-1)))<<endl;
bianliang=(x*((youbianjie-(zuobianjie))/(pow(2,lchrom)-1)))+zuobianjie;
if(bianliang<zuobianjie)
{
cout<<"解碼出錯2"<<endl;
system("pause");
}
delete [] q;
return bianliang;
}
double ran1(long *im)
{
int j;
long k;
static long im2=123456789;
static long iy=0;
static long iv[NTAB];
float temp;
if (*im <= 0)
{
if (-(*im) < 1) *im=1;
else *im = -(*im);
im2=(*im);
for (j=NTAB+7;j>=0;j--)
{
k=(*im)/IQ1;
*im=IA1*(*im-k*IQ1)-k*IR1;
if (*im < 0) *im += IM1;
if (j < NTAB) iv[j] = *im;
}
iy=iv[0];
}
k=(*im)/IQ1;
*im=IA1*(*im-k*IQ1)-k*IR1;
if (*im < 0) *im += IM1;
k=im2/IQ2;
im2=IA2*(im2-k*IQ2)-k*IR2;
if (im2 < 0) im2 += IM2;
j=iy/NDIV;
iy=iv[j]-im2;
iv[j] = *im;
if (iy < 1) iy += IMM1;
if ((temp=AM*iy) > RNMX) return RNMX;
else return temp;
}
double suijibianli()//隨機遍歷
{
double i=ran1(a);
while(i>zhenjuli)
{
i=ran1(a);
}
//cout<<i<<endl;//////////////
return i;
}
int fu(float p)//復制
{
int i;
double sum=0;
if(sumfitness!=0)
{
for(i=0;(sum<p)&&(i<zhongqunshu);i++)
sum+=nowpop[i].fitness/sumfitness;
}
else
i=rnd(1,zhongqunshu1);
return(i-1);
}

int rnd(int low, int high) /*在整數low和high之間產生一個隨機整數*/
{
int i;
if(low >= high)
i = low;
else
{
i =(int)((ran1(a) * (high - low + 1)) + low);
if(i > high) i = high;
}
return(i);
}
int flipc(double p,double q)//判斷是否交叉
{
double pc1=0.9,pc2=0.6;
if((p-q)>0)
{
if(p>=avefitness)
{
pc=pc1-(pc1-pc2)*(p-avefitness)/(maxfitness-avefitness);
}
else
pc=pc1;
}
else
{
if(q>=avefitness)
{
pc=pc1-(pc1-pc2)*(q-avefitness)/(maxfitness-avefitness);
}
else
pc=pc1;
}
if(ran1(a)<=pc)
return(1);
else
return(0);
}
int flipm(double p)//判斷是否變異
{
double pm1=0.001,pm2=0.0001;
if(p>=avefitness)
{
pm=(pm1-(pm1-pm2)*(maxfitness-p)/(maxfitness-avefitness));
}
else
pm=pm1;
if(ran1(a)<=pm)
return(1);
else
return(0);
}
void glp(int n,int s,int *h,int (*q)[1],float (*xx)[1])//glp
{
int i=0,j=0;
//求解q
for(i=0;i<n;i++)
{
for(j=0;j<s;j++)
{
*(*(q+i)+j)=((i+1)*(*(h+j)))%n;
}
}
i=n-1;
for(j=0;j<s;j++)
{
*(*(q+i)+j)=n;
}
//求解x
for(i=0;i<n;i++)
{
for(j=0;j<s;j++)
{
*(*(xx+i)+j)=(float)(2*(*(*(q+i)+j))-1)/(2*n);
}
}
}
BOOL Exist(int Val, int Num, int *Array)//判斷一個數是否在一個數組的前Num個數中
{
BOOL FLAG = FALSE;
int i;
for (i=0; i<Num; i++)
if (Val == *(Array + i))
{
FLAG = TRUE;
break;
}
return FLAG;
}

C. 遺傳演算法原理簡介

遺傳演算法（Genetic Algorithm, GA）是一種進化計算（Evolutionary Computing）演算法，屬於人工智慧技術的一部分。遺傳演算法最早是由John Holland和他的學生發明並改進的，源於對達芬奇物種進化理論的模仿。在物種進化過程中，為了適應環境，好的基因得到保留，不好的基因被淘汰，這樣經過很多代基因的變化，物種的基因就是當前自然環境下適應度最好的基因。該演算法被廣泛應用於優化和搜索中，用於尋求最優解（或最優解的近似），其最主要的步驟包括交叉（crossover）和突變（mutation）。

所有的生物體都由細胞組成，每個細胞中都包含了同樣的染色體（chromosome）。染色體由一串DNA組成，我們可以簡單地把一個生物個體表示為一條染色體。每條染色體上都包含著基因，而基因又是由多個DNA組成的。每個基因都控制著個體某個性狀的表達，例如眼睛的顏色、眼皮的單雙等。在物種繁衍的過程中，首先發生交叉，來自於父母的染色體經過分裂和重組，形成後代的染色體。之後，後代有一定概率發生基因突變，即染色體上某個位置處的基因以一定概率發生變化。之後，對每一代都重復進行交叉和突變兩個步驟。對於每一個後代，我們可以通過一定的方式測量其適應度。適應度越好的個體，在下一次交叉中被選中的概率越大，它的基因越容易傳給下一代。這樣，後代的適應度就會越來越好，直到收斂到一個穩定值。

在優化問題中，可行解總是有很多個，我們希望尋找一個最優解，它相對於其他可行解來說具有更好的適應度（即目標函數值更大或更小）。每個可行解就是一個「生物個體」，可以表示為狀態空間中的一個點和適應度。每個解都是一個經過編碼的序列，已二進制編碼為例，每個解都是一個二進制序列。這樣每個染色體就是一個二進制序列。遺傳演算法從從一組可行解開始，稱為population，從population中隨機選擇染色體進行交叉產生下一代。這一做法的基於下一代的適應度會好於上一代。遺傳演算法的過程如下：

終止條件可以是達到了最大迭代次數，或者是前後連續幾代的最優染色體的適應度差值小於一個閾值。以上演算法描述也許還不夠直觀，我們舉例說明。假設解可以用二進制編碼表示，則每個染色體都是一個二進制序列。假設序列長度為16，則每個染色體都是一個16位的二進制序列：

首先，我們隨機生成一個population，假設population size為20，則有20個長度為16的二進制序列。計算每個染色體的適應度，然後選取兩個染色體進行交叉，如下圖所示。下圖在第6為上將染色體斷開再重組，斷開的位置是可以隨機選擇的。當然，斷裂位置也可以不止一個。可以根據具體問題選擇具體的交叉方式來提升演算法性能。

之後，隨機選取後代染色體上某個基因發生基因突變，突變的位置是隨機選取的。並且，基因突變並不是在每個後代上都會發生，只是有一定的概率。對於二進制編碼，基因突變的方式是按位取反：

上述例子是關於二進制編碼的，像求解一元函數在某個區間內的最大最小值就可以使用二進制編碼。例如，求解函數f(x)=x+sin(3x)+cos(3x)在區間[0,6]內的最小值。假設我們需要最小值點x保留4位小數，那麼求解區間被離散成60000個數。因為2 {15}<60000<2 {16}，所以，需要16位二進制數來表示這60000個可能的解。其中0x0000表示0，0x0001表示0.0001，以此類推。針對這個例子，文末給出了demo code．

然而，在排序問題中無法使用二進制編碼，應該採用排列編碼（permutation encoding）。例如有下面兩個染色體：

交叉：隨機選取一個交叉點，從該出將兩個染色體斷開。染色體A的前部分組成後代1的前部分，然後掃描染色體B，如果出現了後代1中不包含的基因，則將其順序加入後代1中。同理，染色體B的前部分組成了後代2的前部分，掃描染色體A獲得後代2的後部分。注意，交叉的方式多種多樣，此處只是舉出其中一種方式。

( 1 5 3 2 6 | 4 7 9 8) + ( 8 5 6 7 2 | 3 1 4 9) => ( 1 5 3 2 6 8 7 4 9) + ( 8 5 6 7 2 1 3 4 9)

突變：對於一個染色體，隨機選中兩個基因互換位置。例如第3個基因和倒數第2個基因互換：

(1 5 3 2 6 8 7 4 9) => (1 5 4 2 6 8 7 3 9)

此外還有值編碼（value encoding）和樹編碼（tree encoding）等，具體例子可以參考這個鏈接： http://obitko.com/tutorials/genetic-algorithms/encoding.php

在實際的遺傳演算法中，往往會保留上一代中的少數幾個精英（elite），即將上一代population中適應度最好的幾個染色體加入到後代的poulation中，同時去除後代population中適應度最差的幾個染色體。通過這個策略，如果在某次迭代中產生了最優解，則最優解能夠一直保留到迭代結束。

用GA求函數最小值的demo code： https://github.com/JiaxYau/GA_test

參考資料 ：

[1] Introction to Genetic Algorithm, http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems

D. 遺傳演算法--GA

        遺傳演算法（GA）屬於 人工智慧啟發式演算法 ，啟發式演算法的目標就是 尋找原始問題的最優解 ，該演算法的定義為

         人類通過直觀常識和生活經驗，設計出一種以搜索最優解為目的，通過模擬大自然規律的演算法，該演算法在可以在接受的花銷（計算時間和存儲空間）范圍內找到問題實例的一個可行解，且該可行解和真實最優解的誤差一般不可以被估計

        當下主要有的啟發式演算法包括 遺傳演算法、退火法，蟻群演算法、人工神經網路等 ，這篇文章主要介紹遺傳演算法

        遺傳演算法的基本原理是模擬達爾文進化論 "物競天擇，適者生存" 的自然法則，其核心思想為

（1）將原始問題的參數，抽象為基因編碼

（2）將原始問題的可行解，抽象為基因排列的染色體組合

（3）將原始問題的解集規模，抽象為一定數量染色體組成的種群

（4）尋找可行解的過程，抽象為種群的進化過程（染色體選擇、交叉、變異等）

（5）比較可行解的優劣，抽象為量化比較不同種群對當前環境的適應程度

（6）逼近最優解的過程，抽象為淘汰適應度差的種群，保留適應度高的種群進行下一次進化

（7）問題的最優解，抽象為經過多次進化後，最終生存下來的精英種群

        理論上，通過有限次種群進化，生存下來的種群都是 精英染色體 ，是最適合當前環境條件的種群，也就可以無限逼近原始問題的最優解

相關生物學術語：

    為了大家更好了解遺傳演算法，在此之前先簡單介紹一下相關生物學術語，大家了解一下即可。

基因型(genotype)：性狀染色體的內部表現；

表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；

進化(evolution)：種群逐漸適應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。

適應度(fitness)：度量某個物種對於生存環境的適應程度。

選擇(selection)：以一定的概率從種群中選擇若干個個體。一般，選擇過程是一種基於適應度的優勝劣汰的過程。

復制(reproction)：細胞分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因。

交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前後兩串分別交叉組合形成兩個新的染色體。也稱基因重組或雜交；

變異(mutation)：復制時可能（很小的概率）產生某些復制差錯，變異產生新的染色體，表現出新的性狀。

編碼(coding)：DNA中遺傳信息在一個長鏈上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。

解碼(decoding)：基因型到表現型的映射。

個體（indivial）：指染色體帶有特徵的實體；

種群（population）：個體的集合，該集合內個體數稱為種群

大體實現過程

遺傳演算法中每一條染色體，對應著遺傳演算法的一個解決方案，一般我們用適應性函數（fitness function）來衡量這個解決方案的優劣。所以從一個基因組到其解的適應度形成一個映射。 遺傳演算法的實現過程實際上就像自然界的進化過程那樣。

基本遺傳演算法概述

    1.[開始]生成n個染色體的隨機群體（適合該問題的解決方案）

    2.[適應度]評估群體中每個染色體x的適應度f（x）

    3.[新種群]通過重復以下來創建新種群直到新種群完成的步驟

        3.1 [選擇]根據種群的適合度選擇兩個親本染色體（更好的適應性，更大的選擇機會）

        3.2 [交叉]以交叉概率跨越父母形成新的後代（兒童） ）。如果沒有進行交叉，後代就是父母的確切副本。

        3.3 [突變]突變概率突變每個基因座（染色體中的位置）的新後代。

    4.[接受]在新種群中放置新後代[替換]使用新生成的種群進一步運行演算法

    5.[測試]如果滿足結束條件，則停止並返回當前種群中的最佳解

    6。[循環]轉到步驟2

影響GA的因素

    從遺傳演算法概述可以看出，交叉和變異是遺傳演算法中最重要的部分。性能主要受這兩個因素的影響。在我們解釋有關交叉和變異的更多信息之前，我們將給出一些有關染色體的信息。

染色體編碼

染色體應該以某種方式包含它所代表的解決方案的信息。最常用的編碼方式是二進制字元串。然後染色體看起來像這樣：

每個染色體由二進制字元串表示。字元串中的每個位都可以表示解決方案的一些特徵。另一種可能性是整個字元串可以表示一個數字 - 這已在基本的GA小程序中使用。當然，還有許多其他的編碼方式。編碼主要取決於解決的問題。例如，可以直接編碼整數或實數，有時對某些排列等進行編碼很有用。

染色體交叉

在我們確定了將使用的編碼之後，我們可以繼續進行交叉操作。 Crossover對來自親本染色體的選定基因進行操作並產生新的後代。最簡單的方法是隨機選擇一些交叉點，並在此點之前從第一個父項復制所有內容，然後在交叉點之後復制另一個父交叉點之後的所有內容。交叉可以說明如下:( |是交叉點）：

還有其他方法可以進行交叉，例如我們可以選擇更多的交叉點。交叉可能非常復雜，主要取決於染色體的編碼。針對特定問題進行的特定交叉可以改善遺傳演算法的性能。

4.染色體突變

在執行交叉之後，發生突變。突變旨在防止群體中的所有解決方案落入解決問題的局部最優中。突變操作隨機改變由交叉引起的後代。在二進制編碼的情況下，我們可以將一些隨機選擇的位從1切換到0或從0切換到1.突變可以如下所示：

突變（以及交叉）技術主要取決於染色體的編碼。例如，當我們編碼排列時，可以將突變作為兩個基因的交換來進行。

GA的參數

    1.交叉和突變概率

    GA有兩個基本參數 - 交叉概率和變異概率。

     交叉概率 ：交叉的頻率。如果沒有交叉，後代就是父母的精確副本。如果存在交叉，則後代由父母染色體的部分組成。如果交叉概率為100％，那麼所有後代都是由交叉產生的。如果它是0％，那麼全新一代都是從舊種群的染色體的精確拷貝製成的（但這並不意味著新一代是相同的！）。交叉是希望新染色體將包含舊染色體的良好部分，因此新染色體將更好。但是，將舊人口的一部分留給下一代是好的。

     突變概率 ：染色體部分突變的頻率。如果沒有突變，則在交叉（或直接復制）後立即生成後代而不進行任何更改。如果進行突變，則改變染色體的一個或多個部分。如果突變概率為100％，則整個染色體發生變化，如果是0％，則沒有變化。突變通常會阻止GA陷入局部極端。突變不應該經常發生，因為GA實際上會改變為隨機搜索。

    2.其他參數

     種群規模 ：種群中有多少染色體（一代）。如果染色體太少，GA幾乎沒有可能進行交叉，只探索了一小部分搜索空間。另一方面，如果染色體太多，GA會減慢。研究表明，經過一定的限制（主要取決於編碼和問題），使用非常大的種群是沒有用的，因為它不能比中等規模的種群更快地解決問題。

     3      選擇

正如您從GA概述中已經知道的那樣，從群體中選擇染色體作為交叉的父母。問題是如何選擇這些染色體。根據達爾文的進化論，最好的進化能夠創造出新的後代。選擇最佳染色體的方法有很多種。例如輪盤賭選擇，Boltzman選擇，錦標賽選擇，等級選擇，穩態選擇和其他一些選擇。

1.輪盤賭選擇

父母根據他們的健康狀況選擇。染色體越好，它們被選擇的機會就越多。想像一下輪盤賭輪，人口中的所有染色體都放在那裡。輪盤中截面的大小與每條染色體的適應度函數的值成比例 - 值越大，截面越大。有關示例，請參見下圖。

輪盤賭中放入一塊大理石，並選擇停止的染色體。顯然，具有較大適應值的染色體將被選擇更多次。

該過程可以通過以下演算法來描述。

[Sum]計算總體中所有染色體擬合度的總和 - 總和S.

[Select]從區間（0，S）-r生成隨機數。

[循環]遍歷總體並從0 - 總和中求和。當總和s大於r時，停止並返回您所在的染色體。當然，對於每個群體，步驟1僅執行一次。

2.排名選擇

當健身值之間存在很大差異時，先前的選擇類型會出現問題。例如，如果最佳染色體適應度是所有擬合度總和的90％，那麼其他染色體將很少被選擇的機會。等級選擇首先對群體進行排序，然後每個染色體接收由該等級確定的適合度值。最差的將是健身1，第二個最差的2等等，最好的將具有適應度N（人口中的染色體數量）。您可以在下面的圖片中看到，在更改適應性與排名確定的數字後情況如何變化。

排名前的情況（適合度圖）

排名後的情況（訂單號圖）

現在所有染色體都有機會被選中。然而，這種方法會導致收斂速度變慢，因為最好的染色體與其他染色體的差別不大。

3.穩態選擇

這不是選擇父母的特定方法。這種選擇新種群的主要思想是染色體的很大一部分可以存活到下一代。穩態選擇GA以下列方式工作。在每一代中，選擇一些好的（具有更高適應性）染色體來創建新的後代。然後去除一些不好的（具有較低適合度）染色體並將新的後代放置在它們的位置。其餘人口倖存下來。

4.精英

精英主義的想法已經被引入。當通過交叉和變異創建新的種群時，我們有很大的機會，我們將失去最好的染色體。精英主義是首先將最佳染色體（或少數最佳染色體）復制到新種群的方法的名稱。其餘人口以上述方式構建。精英主義可以迅速提高GA的性能，因為它可以防止丟失最佳找到的解決方案。

交叉(Crossover)和突變 (Mutation)

交叉和變異是GA的兩個基本運算符。 GA的表現非常依賴於它們。運算符的類型和實現取決於編碼以及問題。有多種方法可以執行交叉和變異。在本章中，我們將簡要介紹一些如何執行多個編碼的示例和建議。

1.二進制編碼

交叉

單點交叉 - 選擇一個交叉點，從第一個父項復制從染色體開始到交叉點的二進制字元串，其餘從另一個父項復制

選擇兩點交叉 - 兩個交叉點，從第一個父節點復制從染色體開始到第一個交叉點的二進制字元串，從第一個父節點復制從第一個交叉點到第二個交叉點的部分，其餘的是再次從第一個父級復制

均勻交叉 - 從第一個父項或第二個父項中隨機復制位

算術交叉 - 執行一些算術運算以產生新的後代

突變

位反轉 - 選擇的位被反轉

2.置換編碼

交叉

單點交叉 - 選擇一個交叉點，將排列從第一個父項復制到交叉點，然後掃描另一個父項，如果該數字還沒有在後代中，則添加它注意：還有更多方法如何在交叉點之後產生休息

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

變異

順序更改 - 選擇並交換兩個數字

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

3.值編碼

交叉

可以使用來自二進制編碼的所有交叉

變異

添加一個小數字（用於實數值編碼） - 將一個小數字添加到（或減去）所選值

（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）

4.樹編碼

交叉

樹交叉 - 在父母雙方中選擇一個交叉點，父母在該點被分割，交換點下面的部分被交換以產生新的後代

變異

更改運算符，數字 - 選定節點已更改

補充:

疑惑點：

初始種群是啥：

利用二進制（一般）表示最終解

例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}

用六位二進制數表示由x，y組成的解，例如：001100 表示x=1，y=4

001100 稱為一條基因序列，表示的是該問題的一種解決 方案

種群是包含多個基因序列（解決方案/個體）的集合

適應度函數是啥，有什麼作用：

適應度函數可以理解成「 游戲 規則」，如果問題較為復雜，需要自定義適應度函數，說明如何區分優秀與不優秀的個體; 如果問題比較簡單，例如上述求最大值的問題，則直接用此函數式作為適應度函數即可。作用：評定個體的優劣程度，從而決定其遺傳機會的大小。

怎麼選擇：

定義「適者生存不適者淘汰」的規則，例如：定義適應度高的被選擇的概率更大

怎麼交叉：

利用循環，遍歷種群中的每個個體，挑選另一個體進行交叉。例如，通過遍歷為基因序列A挑選出B配對，則取A的前半部分，B的後半部分，組合成新的個體（基因序列）C

如何變異：

隨機挑選基因序列上的某一位置，進行0-1互換

建議 GA的參數

如果您決定實施遺傳演算法，本章應該為您提供一些基本建議。這些建議非常籠統。您可能希望嘗試使用自己的GA來解決特定問題，因為沒有一般理論可以幫助您針對任何問題調整GA參數。

建議通常是對GA的經驗研究的結果，這些研究通常僅在二進制編碼上進行。

交叉率

交叉率一般應高，約為80％-95％。 （但是有些結果表明，對於某些問題，交叉率約為60％是最好的。）

突變率

另一方面，突變率應該非常低。最佳利率似乎約為0.5％-1％。

人口規模

可能令人驚訝的是，非常大的人口規模通常不會改善GA的性能（從找到解決方案的速度的意義上說）。良好的人口規模約為20-30，但有時大小為50-100是最好的。一些研究還表明，最佳種群規模取決於編碼字元串（染色體）的大小。這意味著如果你有32位染色體，那麼人口應該高於16位染色體。

選擇

可以使用基本的輪盤賭選擇，但有時排名選擇可以更好。查看有關選擇優缺點的章節。還有一些更復雜的方法可以在GA運行期間更改選擇參數。基本上，這些表現類似於模擬退火。如果您不使用其他方法來保存最佳找到的解決方案，則應確保使用精英主義。您也可以嘗試穩態選擇。

編碼

編碼取決於問題以及問題實例的大小。查看有關編碼的章節以獲取一些建議或查看其他資源。

交叉和變異

運算符取決於所選的編碼和問題。查看有關操作員的章節以獲取一些建議。您還可以查看其他網站。

搜索空間

    如果我們正在解決問題，我們通常會尋找一些最好的解決方案。所有可行解決方案的空間（所需解決方案所在的解決方案集）稱為搜索空間（也稱為狀態空間）。搜索空間中的每個點代表一種可能的解決方案。每個可能的解決方案可以通過其對問題的值（或適應度）進行「標記」。通過GA，我們在眾多可能的解決方案中尋找最佳解決方案 - 以搜索空間中的一個點為代表。然後尋找解決方案等於在搜索空間中尋找一些極值（最小值或最大值）。有時可以很好地定義搜索空間，但通常我們只知道搜索空間中的幾個點。在使用遺傳演算法的過程中，隨著進化的進行，尋找解決方案的過程會產生其他點（可能的解決方案）。

    問題是搜索可能非常復雜。人們可能不知道在哪裡尋找解決方案或從哪裡開始。有許多方法可用於尋找合適的解決方案，但這些方法不一定能提供最佳解決方案。這些方法中的一些是爬山，禁忌搜索，模擬退火和遺傳演算法。通過這些方法找到的解決方案通常被認為是很好的解決方案，因為通常不可能證明最佳方案。

NP-hard Problems

NP問題是一類無法用「傳統」方式解決的問題。我們可以快速應用許多任務（多項式）演算法。還存在一些無法通過演算法解決的問題。有很多重要問題很難找到解決方案，但是一旦有了解決方案，就很容易檢查解決方案。這一事實導致了NP完全問題。 NP代表非確定性多項式，它意味著可以「猜測」解決方案（通過一些非確定性演算法），然後檢查它。如果我們有一台猜測機器，我們或許可以在合理的時間內找到解決方案。為簡單起見，研究NP完全問題僅限於答案可以是或否的問題。由於存在輸出復雜的任務，因此引入了一類稱為NP難問題的問題。這個類並不像NP完全問題那樣受限。 NP問題的一個特徵是，可以使用一個簡單的演算法，可能是第一眼看到的，可用於找到可用的解決方案。但是這種方法通常提供了許多可能的解決方案 - 只是嘗試所有可能的解決方案是非常緩慢的過程（例如O（2 ^ n））。對於這些類型問題的更大的實例，這種方法根本不可用。今天沒有人知道是否存在一些更快的演算法來提供NP問題的確切答案。對於研究人員來說，發現這樣的演算法仍然是一項重大任務（也許你！:-)）。今天許多人認為這種演算法不存在，因此他們正在尋找替代方法。替代方法的一個例子是遺傳演算法。 NP問題的例子是可滿足性問題，旅行商問題或背包問題。可以獲得NP問題匯編。

參考：

         https://www.jianshu.com/p/ae5157c26af9

        https://www.jianshu.com/p/b36b520bd187

E. 神經網路和遺傳演算法有什麼關系

遺傳演算法是一種智能優化演算法，神經網路是人工智慧演算法的一種。
可以將遺傳演算法用於神經網路的參數優化中。