https://blog.csdn.net/b2b160/article/details/4680853/

https://blog.csdn.net/ljp1919/article/details/42425281

1、遺傳算法，核心是達爾文優勝劣汰適者生存的進化理論的思想。一個種群，通過長時間的繁衍，種群的基因會向著更適應環境的趨勢進化，適應性強的個體基因被保留，后代越來越多，適應能力低個體的基因被淘汰，后代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。

那么在解決一些問題的時候，我們所學習的便是這樣的思想。比如先隨機創造很多很多的解，然后找一個靠譜的評價體系，去篩選適應性高的解，再用這些適應性高的解衍生出更好的解，然后再篩選，再衍生。反復迭代一定次數，可以得到近似最優解。

2、首先，我們先看看一個經典組合問題：“背包問題”

“背包問題（Knapsack problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。”

這個問題的衍生簡化問題“0-1背包問題” 增加了限制條件：每件物品只有一件，可以選擇放或者不放，更適合我們來舉例
這樣的問題如果數量少，當然最好選擇窮舉法
比如一共3件商品，用0表示不取，1表示取，那么就一共有
000 001 010?
011 100 101
110 111
這樣8種方案，然后讓計算機去累加和，與重量上限比較，留下來的解里取最大即可。
但如果商品數有300,3000,甚至3w種呢，計算量太大窮舉法可能就不適用了，這時如果遺傳算法使用得當，就能在較短的時間內幫我們找到近似的最優解，我們繼續往下看：
新的問題是12件商品的0-1背包問題
我們先讓計算機隨機產生1000個12位的二進制數。把總重量超過背包上限的解篩掉，剩下的兩兩一對隨機交換“基因片段”產生下一代
交換前：
0000 1100 1101
0011 0101 0101
交換后：
0000 0101 1101
0011 1100 0101
再篩選，再交配，如此反復幾代，留下的“基因型“差不多就是最好的了，如此這般與生物進化規律是一樣的。
同時，在生物繁殖過程中，新產生的基因是有一定幾率突變的，這是很多優良性狀的重要來源，遺傳算法中可也不能忽略它
比如：

變異前：

000101100101

變異后：

000101110101

產生突變的位置，就是一個概率問題。在設計算法的時候，會給每個基因位設置一個突變概率（當然是非常了）同樣的在基因交換階段交換哪些基因呢，也是一個算法設置問題。

3、總結一下，遺傳算法應該有

一個基本函數：適度函數f(x)
三個基本操作：選擇，交叉，變異

一.適度函數
適度函數其實就是指解的篩選標準，比如上文所說的把所有超過上限重量的解篩選掉，但是不是有更好的篩選標準呢？這將直接影響最后結果的接近程度以及求解所耗費的時間，所以設置一個好的適度函數很重要

二.選擇
在遺傳算法中選擇也是個概率問題，在解的范圍中適應度更高的基因型有更高的概率被選擇到。所以，在選擇一些解來產生下一代時，一種常用的選擇策略是“比例選擇”，也就是個體被選中的概率與其適應度函數值成正比。假設群體的個體總數是M，那么那么一個體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) )。常用的選擇方法――輪盤賭（Roulette Wheel Selection）選擇法。

三.交叉
在均等概率下基因位點的交叉，衍生出新的基因型。上述例子中是通過交換兩個基因型的部分”基因”，來構造兩個子代的基因型。

四.變異
在衍生子代的過程中，新產生的解中的“基因型”會以一定的概率出錯，稱為變異。變異發生的概率設置為Pm，記住該概率是很小的一個值。因為變異是小概率事件！

五.基本遺傳算法優化
為了防止進化過程中產生的最優解被變異和交叉所破壞。《遺傳算法原理及應用》介紹的最優保存策略是：即當前種群中適應度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經過交叉、變異等遺傳操作后所產生的適應度最低的個體。

遺傳算法的優點：

1、 與問題領域無關且快速隨機的全局搜索能力。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，復蓋面大，利于全局擇優。

2、 搜索從群體出發，具有潛在的并行性，可以進行多個個體的同時比較，魯棒性高！

3、 搜索使用評價函數啟發，過程簡單。

4、使用概率機制進行迭代，具有隨機性。遺傳算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。這說明遺傳算法是采用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。

5、具有可擴展性，容易與其他算法結合。遺傳算法求解時使用特定問題的信息極少，僅僅使用適應值這一信息進行搜索，并不需要問題導數等與問題直接相關的信息。遺傳算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題，容易形成通用算法程序。

6、具有極強的容錯能力。遺傳算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；并且是一個并行濾波機制。故而，遺傳算法有很高的容錯能力。

遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會陷入局部最優解的快速下降陷阱；并且利用它的內在并行性，可以方便地進行分布式計算，加快求解速度。

遺傳算法的缺點：

1、遺傳算法的編程實現比較復雜,首先需要對問題進行編碼,找到最優解之后還需要對問題進行解碼

2、三個算子的實現也有許多參數,如交叉率和變異率,并且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗

3、沒有能夠及時利用網絡的反饋信息,故算法的搜索速度比較慢，要得要較精確的解需要較多的訓練時間

4、算法對初始種群的選擇有一定的依賴性（下圖所示），能夠結合一些啟發算法進行改進

5、算法的并行機制的潛在能力沒有得到充分的利用，這也是當前遺傳算法的一個研究熱點方向。

同時，遺傳算法的局部搜索能力較差，導致單純的遺傳算法比較費時，在進化后期搜索效率較低。在實際應用中，遺傳算法容易產生過早收斂的問題。采用何種選擇方法既要使優良個體得以保留，又要維持群體的多樣性，一直是遺傳算法中較難解決的問題。
-------------------------我------是------分------割--------線------------------------------------------------------------

下面舉例來說明遺傳算法用以求函數最大值

函數為y = -x2+ 5的最大值，-32<=x<=31

一、編碼以及初始種群的產生

編碼采用二進制編碼，初始種群采用矩陣的形式，每一行表示一個染色體，每一個染色體由若干個基因位組成。關于染色體的長度（即基因位的個數）可根據具體情況而定。比如說根據要求極值的函數的情況，本文-32<=X<=31，該范圍內的整數有64個，所以可以取染色體長度為6，（26=64）。綜上所述，取染色體長度為6，前5個二進制構成該染色體的值（十進制），第6個表示該染色體的適應度值。若是所取得染色體長度越長，表示解空間搜索范圍越大，對應的是待搜索的X范圍越大。關于如何將二進制轉換為十進制，文后的C代碼中函數x即為轉換函數。

初始種群結構如下圖所示：

該初始種群共有4個染色體，第1列表示各個染色體的編號，第2列表示該染色體值的正負號，0表示正，1表示負。第3列到第7列為二進制編碼，第8列表示各個染色體的適應度值。第2列到第7列的0-1值都是隨機產生的。

二、適應度函數

一般情況下，染色體（也叫個體，或一個解）的適應度函數為目標函數的線性組合。本文直接以目標函數作為適應度函數。即每個染色體的適應度值就是它的目標函數值，f(x)=-x^2+ 5。

三、選擇算子

初始種群產生后，要從種群中選出若干個體進行交叉、變異，那么如何選擇這些個體呢？選擇方法就叫做選擇算子。一般有輪盤賭選擇法、錦標賽選擇法、排序法等。本文采用排序法來選擇，即每次選擇都選出適應度最高的兩個個體。那么執行一次選擇操作后，得到的新種群的一部分為下圖所示：

四、交叉算子

那么接下來就要對新種群中選出的兩個個體進行交叉操作，一般的交叉方法有單點交叉、兩點交叉、多點交叉、均勻交叉、融合交叉。方法不同，效果不同。本文采用最簡單的單點交叉。交叉點隨機產生。但是交叉操作要在一定的概率下進行，這個概率稱為交叉率，一般設置為0.5到0.95之間。通過交叉操作，衍生出子代，以補充被淘汰掉的個體。交叉后產生的新個體組成的新種群如下：

黑體字表示子代染色體繼承父代個體的基因。

五、變異

變異就是對染色體的基因進行變異，使其改變原來的結構（適應值也就改變），達到突變進化的目的。變異操作也要遵從一定的概率來進行，一般設置為0到0.5之間，即以小概率進行基因突變。這符合自然規律。本文的變異方法直接采取基因位反轉變異法，即0變為1，1變為0。要進行變異的基因位的選取也是隨機的。

六、終止規則

遺傳算法是要一代一代更替的，那么什么時候停止迭代呢？這個規則就叫終止規則。一般常用的終止規則有：若干代后終止，得到的解達到一定目標后終止，計算時間達到一定限度后終止等方法。本文采用迭代數來限制。

代碼如下所示：
?

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>typedef struct Chrom                           // 結構體類型，為單個染色體的結構；
{short int bit[6];//一共6bit來對染色體進行編碼，其中1位為符號位。取值范圍-64~+64int fit ;//適應值double rfit;//相對的fit值，即所占的百分比double cfit;//積累概率
}chrom;                                       
//定義將會用到的幾個函數；
void *evpop (chrom popcurrent[4]);//進行種群的初始化
int x (chrom popcurrent);
int y (int x);
void *pickchroms (chrom popcurrent[4]);//選擇操作
void *pickchroms_new (chrom popcurrent[4]); // 基于概率分布
void *crossover (chrom popnext[4]);//交叉操作
void *mutation (chrom popnext[4]);//突變
double r8_uniform_ab ( double a, double b, int &seed );//生成a~b之間均勻分布的數字
chrom popcurrent [4];                        // 初始種群規模為；
chrom popnext [4];                           // 更新后種群規模仍為；
void main ()                                    // 主函數；
{int num ;                                    // 迭代次數；int i ,j, l,Max ,k;Max=0;                                      // 函數最大值printf("\nWelcome to the Genetic Algorithm！\n");  // printf("The Algorithm is based on the function y = -x^2 + 5 to find the maximum value of the function.\n");enter:printf ("\nPlease enter the no. of iterations\n請輸入您要設定的迭代數 : ");scanf("%d" ,&num);                           // 輸入迭代次數，傳送給參數 num；if(num <1)                                  goto enter ;                                 // 判斷輸入的迭代次數是否為負或零，是的話重新輸入；//不同的隨機數可能結果不同？？那是當所設置的迭代次數過少時，染色體的基因型過早地陷入局部最優srand(time(0));  evpop(popcurrent );    // 隨機產生初始種群；//是否需要指定x的取值范圍呢？6bit來表示數字，第一位為符號位，5bit表示數字大小。所以，取值范圍為-32~+31Max = popcurrent[0].fit;//對Max值進行初始化for(i =0;i< num;i ++)                          // 開始迭代；{printf("\ni = %d\n" ,i);                 // 輸出當前迭代次數；for(j =0;j<4; j++){popnext[j ]=popcurrent[ j];           // 更新種群；}pickchroms(popnext );                    // 挑選優秀個體；crossover(popnext );                     // 交叉得到新個體；mutation(popnext );                      // 變異得到新個體；for(j =0;j<4; j++) {popcurrent[j ]=popnext[ j];              // 種群更替；}}  // 等待迭代終止；
//對于真正隨機數是需要注意取較大的迭代次數for(l =0;l<3; l++){if(popcurrent [l]. fit > Max ){Max=popcurrent [l]. fit;k=x(popcurrent [l]);//此時的value即為所求的x值}}printf("\n 當x等于 %d時，函數得到最大值為： %d ",k ,Max);printf("\nPress any key to end ! " );flushall();                                 // 清除所有緩沖區；getche();                                   // 從控制臺取字符，不以回車為結束；}                                             void *evpop (chrom popcurrent[4])   // 函數：隨機生成初始種群；
{int i ,j, value1;int random ;double sum=0;for(j =0;j<4; j++)                            // 從種群中的第1個染色體到第4個染色體{for(i =0;i<6; i++)                       // 從染色體的第1個基因位到第6個基因位{random=rand ();                     // 產生一個隨機值random=(random %2);                 // 隨機產生0或者1popcurrent[j ].bit[ i]=random ;       // 隨機產生染色體上每一個基因位的值，或；}  value1=x (popcurrent[ j]);                // 將二進制換算為十進制，得到一個整數值；popcurrent[j ].fit= y(value1); // 計算染色體的適應度值sum = sum + popcurrent[j ].fit;printf("\n popcurrent[%d]=%d%d%d%d%d%d  value=%d  fitness = %d",j, popcurrent[j ].bit[5], popcurrent[j ].bit[4], popcurrent[j ].bit[3], popcurrent[j ].bit[2], popcurrent[j ].bit[1], popcurrent[j ].bit[0], value1,popcurrent [j]. fit); // 輸出整條染色體的編碼情況，}//計算適應值得百分比，該參數是在用輪盤賭選擇法時需要用到的for (j = 0; j < 4; j++){popcurrent[j].rfit = popcurrent[j].fit/sum;popcurrent[j].cfit = 0;//將其初始化為0}return(0);                
}                                       int x (chrom popcurrent)  // 函數：將二進制換算為十進制；
{//此處的染色體長度為，其中個表示符號位int z ;z=(popcurrent .bit[0]*1)+( popcurrent.bit [1]*2)+(popcurrent. bit[2]*4)+(popcurrent .bit[3]*8)+( popcurrent.bit [4]*16);if(popcurrent .bit[5]==1)  // 考慮到符號；{z=z *(-1);                             }return(z );                           
}                                     
//需要能能夠從外部直接傳輸函數，加強魯棒性
int y (int x)// 函數：求個體的適應度；
{int y ;y=-(x *x)+5;                                // 目標函數：y= - ( x^ 2 ) +5；return(y );             
} 
//基于輪盤賭選擇方法，進行基因型的選擇
void *pickchroms_new (chrom popnext[4])//計算概率
{int men;int i;int j;double p;double sum=0.0;//find the total fitness of the populationfor (men = 0; men < 4; men++ ){sum = sum + popnext[men].fit;}//calculate the relative fitness of each memberfor (men = 0; men < 4; men++ ){popnext[men].rfit = popnext[men].fit / sum;}//calculate the cumulative fitness,即計算積累概率popcurrent[0].cfit = popcurrent[0].rfit;for ( men = 1; men < 4; men++){popnext[men].cfit = popnext[men-1].cfit + popnext[men].rfit;}for ( i = 0; i < 4; i++ ){//產生0~1之間的隨機數//p = r8_uniform_ab ( 0, 1, seed );//通過函數生成0~1之間均勻分布的數字p =rand()%10;//p = p/10;if ( p < popnext[0].cfit ){popcurrent[i] = popnext[0];      }else{for ( j = 0; j < 4; j++ ){ if ( popnext[j].cfit <= p && p < popnext[j+1].cfit ){popcurrent[i] = popcurrent[j+1];}}}}//  Overwrite the old population with the new one.//for ( i = 0; i < 4; i++ ){popnext[i] = popcurrent[i]; }return(0);
}
void *pickchroms (chrom popnext[4])          // 函數：選擇個體；
{int i ,j;chrom temp ;                                // 中間變量//因此此處設計的是個個體，所以參數是for(i =0;i<3; i++)                           // 根據個體適應度來排序；（冒泡法）{for(j =0;j<3-i; j++){if(popnext [j+1]. fit>popnext [j]. fit){temp=popnext [j+1];popnext[j +1]=popnext[ j];popnext[j ]=temp;}  }               }for(i =0;i<4; i++){printf("\nSorting:popnext[%d] fitness=%d" ,i, popnext[i ].fit);printf("\n" );                     }flushall();/* 清除所有緩沖區 */                      return(0);
}   
double r8_uniform_ab( double a, double b, int &seed )
{{int i4_huge = 2147483647;int k;double value;if ( seed == 0 ){std::cerr << "\n";std::cerr << "R8_UNIFORM_AB - Fatal error!\n";std::cerr << "  Input value of SEED = 0.\n";exit ( 1 );}k = seed / 127773;seed = 16807 * ( seed - k * 127773 ) - k * 2836;if ( seed < 0 ){seed = seed + i4_huge;}value = ( double ) ( seed ) * 4.656612875E-10;value = a + ( b - a ) * value;return value;}
}
void *crossover (chrom popnext[4])              // 函數：交叉操作；
{int random ;int i ;//srand(time(0)); random=rand ();                             // 隨機產生交叉點；random=((random %5)+1);                     // 交叉點控制在0到5之間；for(i =0;i< random;i ++)                   {popnext[2].bit [i]= popnext[0].bit [i];   // child 1 cross overpopnext[3].bit [i]= popnext[1].bit [i];   // child 2 cross over}for(i =random; i<6;i ++)                      // crossing the bits beyond the cross point index{popnext[2].bit [i]= popnext[1].bit [i];    // child 1 cross overpopnext[3].bit [i]= popnext[0].bit [i];    // chlid 2 cross over}  for(i =0;i<4; i++){popnext[i ].fit= y(x (popnext[ i]));        // 為新個體計算適應度值；}for(i =0;i<4; i++){printf("\nCrossOver popnext[%d]=%d%d%d%d%d%d    value=%d    fitness = %d",i, popnext[i ].bit[5], popnext[i ].bit[4], popnext[i ].bit[3], popnext[i ].bit[2], popnext[i ].bit[1], popnext[i ].bit[0], x(popnext [i]), popnext[i ].fit); // 輸出新個體；}return(0);
}                                          void *mutation (chrom popnext[4])               // 函數：變異操作；
{int random ;int row ,col, value;//srand(time(0)); random=rand ()%50;  // 隨機產生到之間的數；//變異操作也要遵從一定的概率來進行，一般設置為0到0.5之間//if(random ==25)                              // random==25的概率只有2%，即變異率為，所以是以小概率進行變異！！{col=rand ()%6;                            // 隨機產生要變異的基因位號；row=rand ()%4;                            // 隨機產生要變異的染色體號；if(popnext [row]. bit[col ]==0)             // 1變為；{popnext[row ].bit[ col]=1 ;}else if (popnext[ row].bit [col]==1)        // 0變為；{popnext[row ].bit[ col]=0;}popnext[row ].fit= y(x (popnext[ row]));     // 計算變異后的適應度值；value=x (popnext[ row]);printf("\nMutation occured in popnext[%d] bit[%d]:=%d%d%d%d%d%d    value=%d   fitness=%d", row,col ,popnext[ row].bit [5],popnext[ row].bit [4],popnext[ row].bit [3],popnext[ row].bit [2],popnext[ row].bit [1],popnext[ row].bit [0],value, popnext[row ].fit);// 輸出變異后的新個體；}                                          return(0);
}   

?

總結

以上是生活随笔為你收集整理的遗传算法与C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。