遺傳算法
算法思想
遺傳算法（Genetic Algorithm, GA）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。
其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，不需要確定的規則就能自動獲取和指導優化的搜索空間，自適應地調整搜索方向。
遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心內容。
設計思路
遺傳算法是從代表問題可能潛在的解集的一個種群開始的，一個種群由基因編碼的一定數量的個體組成。每個個體實際上是染色體帶有特征的實體。
初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。
這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。
遺傳算法應用步驟：
????1）確定決策變量及各種約束條件，即個體的表現型X和問題的解空間；
????2）建立優化模型 （目標函數最大OR 最小） 數學描述形式 量化方法；
????3）染色體編碼方法；
????4）解碼方法；
????5）個體適應度的量化評價方法 F(x)
????6）設計遺傳算子；
????7）確定有關運行參數。
程序代碼（使用遺傳算法解決01背包問題）
#include <windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>#define S 5 //種群的規模
#define Pc 0.8 //交叉概率
#define Pm 0.05 //突變概率
#define KW 1000 //背包最大載重1000
#define N 50 //物體總數
#define T 800 //最大換代數
#define ALIKE 0.05 //判定相似度
int stop=0; //初始化函數中初始化為所有價值之和
int t=0; //目前的代數
int value[]={
220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1};
int weight[]={
80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1};struct individual //個體結構體
{bool chromsome[N]; //染色體編碼double fitness; //適應度//即本問題中的個體所得價值double weight; //總重量
};
int best=0;
int same=0;
individual X[S],Y[S],bestindividual;/************************************************************************/
int comp(individual bestindividual,individual temp); //比較函數
void checkalike(void); //檢查相似度函數
void GenerateInitialPopulation(void); //初始種群
void CalculateFitnessValue(void); //適應度
void SelectionOperator(void); //選擇
void CrossoverOperator(void); //交叉
void MutationOperator(void); //變異
void FindBestandWorstIndividual(void); //尋找最優解
void srand(unsigned int seed); //隨機生成
/************************************************************************/int comp(individual bestindividual,individual temp)//比較函數
{int fit=0,w=0;//第一種不變:操作后不滿足重量函數，第二種:操作后適應度小于操作前for(int i=0;i<N;i++){fit+=temp.chromsome[i]*value[i];w+=temp.chromsome[i]*weight[i];}if(w>KW)return -1;return (bestindividual.fitness>fit?-1:1);//如果小于原來值或者不滿足重量函數，則返回-1
}/************************************************************************/
void Checkalike(void)
{int i=0,j=0;for( i=0;i<S;i++)//相似度校驗{for(j=0;j<N;j++){bool temp=X[i].chromsome[j];for(int k=1;k<S;k++){if(temp!=X[k].chromsome[j])break;}}if(j==N)same++;}if(same>N*ALIKE)//大于ALIKE作為判定為早熟{int minindex=0;for(int n=0;n<S;n++)if(X[n].fitness<X[minindex].fitness)minindex=n;//確定最小for (j=0; j<N;j++)//重新生成{bool m=(rand()%10<5)?0:1;X[minindex].chromsome[j]=m;X[minindex].weight+=m*weight[j];//個體的總重量X[minindex].fitness+=m*value[j]; //個體的總價值}}
}/************************************************************************/
void GenerateInitialPopulation(void)//初始種群,保證每個值都在符合條件的解
{int i=0,j=0; bool k;for(i=0;i<N;i++)stop+=value[i];//設置理論最優值for (i=0; i<S; i++){int w=0,v=0;for (j=0; j<N;j++){k=(rand()%10<5)?0:1;X[i].chromsome[j]=k;w+=k*weight[j];//個體的總重量v+=k*value[j]; //個體的總價值}if(w>KW) i--; //如果不是解，重新生成else{X[i].fitness=v;X[i].weight=w;if(v==stop){bestindividual=X[i];return;}//這種情況一般不會發生}}
}
/************************************************************************/void CalculateFitnessValue()
{int i=0,j=0;for (i=0; i<S; i++){int w=0,v=0;for (j=0; j<N;j++){w+=X[i].chromsome[j]*weight[j];//個體的總重量v+=X[i].chromsome[j]*value[j]; //個體的總價值}X[i].fitness=v;X[i].weight=w;if(v==stop){bestindividual=X[i];return;}//符合條件情況下最優解這種情況一般不會發生if(w>KW) X[i]=bestindividual;//如果不是解，找最好的一個解代之}
}
/************************************************************************/void SelectionOperator(void)
{int i, index;double p, sum=0.0;double cfitness[S];//選擇、累積概率individual newX[S];for (i=0;i<S;i++)sum+=X[i].fitness;//適應度求和for (i=0;i<S; i++)cfitness[i]=X[i].fitness/sum; //選擇概率for (i=1;i<S; i++)cfitness[i]=cfitness[i-1]+cfitness[i];//累積概率for (i=0;i<S;i++){p=(rand()%1001)/1000.0;//產生一個[0,1]之間的隨機數index=0;while(p>cfitness[index])//輪盤賭進行選擇{index++;}newX[i]=X[index];}for (i=0; i<S; i++)X[i]=newX[i];//新的種群
}/************************************************************************/
void CrossoverOperator(void)//交叉操作
{int i=0, j=0,k=0;individual temp;for(i=0; i<S; i++){int p=0,q=0;do{p=rand()%S;//產生兩個[0，S]的隨機數q=rand()%S;}while(p==q);int w=1+rand()%N;//[1,N]表示交換的位數double r=(rand()%1001)/1000.0;//[0,1]if(r<=Pc){for(j=0;j<w;j++){temp.chromsome[j]=X[p].chromsome[j];//將要交換的位先放入臨時空間X[p].chromsome[j]=X[q].chromsome[j];X[q].chromsome[j]=temp.chromsome[j];}}if(p==best)if(-1==comp(bestindividual,X[p]))//如果變異后適應度變小X[p]=bestindividual;if(q==best)if(-1==comp(bestindividual,X[q]))//如果變異后適應度變小X[q]=bestindividual;}
}
/************************************************************************/void MutationOperator(void)
{int i=0, j=0,k=0,q=0;double p=0;for (i=0; i<S; i++){for (j=0; j<N; j++){p=(rand()%1001)/1000.0;if (p<Pm)//對每一位都要考慮{if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;else X[i].chromsome[j]=1;}}if(i==best)if(-1==comp(bestindividual,X[i]))//如果變異后適應度變小X[i]=bestindividual;}
}
/************************************************************************/void FindBestandWorstIndividual(void)
{int i;bestindividual=X[0];for (i=1;i<S; i++){if (X[i].fitness>bestindividual.fitness){bestindividual=X[i];best=i;}}
}/*主函數*****************************************************************/
int main()
{t=0;GenerateInitialPopulation(); //初始群體包括產生個體和計算個體的初始值while (t<=T){FindBestandWorstIndividual(); //保存當前最優解SelectionOperator(); //選擇CrossoverOperator(); //交叉MutationOperator(); //變異Checkalike(); //檢查相似度CalculateFitnessValue(); //計算新種群適應度t++;}FindBestandWorstIndividual(); //找到最優解printf(" 物品價值：");for(int k=0;k<N;k++){printf(" %d ",value[k]);}printf("\n");printf(" 物品重量:");for(int k=0;k<N;k++){printf(" %d ",weight[k]);}printf("\n");printf("背包容量 %d\n",1000); //輸出最優值printf("-----------------------------\n");printf("最優值 %f\n",bestindividual.fitness); //輸出最優值printf("對應重量 %f\n",bestindividual.weight); //對應重量printf("線性解：");for(int k=0;k<N;k++){if(bestindividual.chromsome[k]==1){ //輸出最優解printf(" %d ",1);}else{printf(" %d ",0);}}printf("\n");printf("\n");return 0;
}
/*結束***********************************************************************/測試例
物品價值：
220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 56 50 30 20 15 10 8 5 3 1
物品重量：
80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 25 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1
運行結果
最優值 3078.000000
對應重量 1000.000000
線性解： 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1
分析
試驗中用到的物品的重量和價值分別存儲于以下兩個數組之中。
int value[]={
220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1};
int weight[]={
80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1};
遺傳算法有許多不足，算法對新空間的探索能力是有限的，也容易收斂到局部最優解。涉及到大量個體的計算，當問題復雜時，計算時間很長。
但是他也有很多優點：
- 與問題領域無關切快速隨機的搜索能力。
- 搜索從群體出發，具有潛在的并行性，可以進行多個個體的同時比較，robust.
- 搜索使用評價函數啟發，過程簡單
- 使用概率機制進行迭代，具有隨機性。
- 具有可擴展性，容易與其他算法結合。
參考：
短短的路走走停停被搶注啦
鶴鶴有明
wangqiuyun
