姓名：楊晶晶 學號：21011210420 學院：通信工程學院
轉載自：https://blog.csdn.net/ritterliu/article/details/54821300
【嵌牛導讀】遺傳算法，核心是達爾文優(yōu)勝劣汰適者生存的進化理論的思想。我們都知道一個種群，通過長時間的繁衍，種群的基因會向著更適應環(huán)境的趨勢進化，優(yōu)良的基因會被保留，后代越來越多，適應能力低個體的基因被淘汰，后代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。那么在解決一些問題的時候，我們能不能學習這樣的思想。
【嵌牛鼻子】遺傳算法的基本概念；遺傳算法代碼。
【嵌牛提問】什么是遺傳算法？利用C語言設計相關代碼進行驗證。
【嵌牛正文】
遺傳算法介紹
遺傳算法是一種模擬生命進化機制的搜索和優(yōu)化方法，是把自然遺傳學和計算機科學結合起來的優(yōu)化方程，有很強的解決問題的能力和廣泛的適應性。其假設常描述為二進制位串，位串的含義依賴于具體應用。搜索合適的假設從若干初始假設的群體集合開始。當前種群成員通過模仿生物進化的方式來產生下一代群體，如隨機變異和交叉。每一步，根據給定的適應度評估當前群體的假設，而后使用概率方法選出適應度最高的假設作為產生下一代的種子。
遺傳算法的幾個基本概念
?。?）染色體（Chromosome）：在使用遺傳算法時，需要把問題的解編成一個適合的碼子。這種具有固定結構的符號串既是染色體，符號串的每一位代表一個基因。符號串的總位數成為染色體的長度，一個染色體就代表問題的一個解，每個染色體也被稱為一個個體。
?。?）群體（Population）：每代所產生的染色體總數成為群體，一個群體包含了該問題在這一代的一些解的集合。
?。?）適應度（Fitness）：對群體中每個染色體進行編碼后，每個個體對應一個具體問題的解，而每個解對應于一個函數值。該函數值即適應函數，就是衡量染色體對環(huán)境適應度的指標，也是反映實際問題的目標函數
基本的遺傳操作
?。?）選擇（Select）：按一定的概率從上代群體中選擇M對個體作為雙親，直接拷貝到下一代，染色體不發(fā)生變化。
?。?）交叉（Crossover）：對于選中進行繁殖的兩個染色體X，Y，以X，Y為雙親作交叉操作，從而產生兩個后代X1，Y1.
（3）變異（Mutation）：對于選中的群體中的個體（染色體），隨機選取某一位進行取反運算，即將該染色體碼翻轉。
用遺傳算法求解的過程是根據待解決問題的參數集進行編碼，隨機產生一個種群，計算適應函數和選擇率，進行選擇、交叉、變異操作。如果滿足收斂條件，此種群為最好個體，否則，對產生的新一代群體重新進行選擇、交叉、變異操作，循環(huán)往復直到滿足條件。
TSP問題
所謂TSP問題（旅行商問題）即最短路徑問題就是在給定的起始點S到終止點T的通路集合中，尋求距離最小的通路，這樣的通路成為S點到T點的最短路徑。在尋找最短路徑問題上，有時不僅要知道兩個指定頂點間的最短路徑，還需要知道某個頂點到其他任意頂點間的最短路徑。用遺傳算法解決這類問題，沒有太多的約束條件和有關解的限制，因而可以很快地求出任意兩點間的最短路徑以及一批次短路徑。
TSP問題的遺傳算法設計與實現
?。ǎ保┚幋a問題：由于這是一個離散型的問題，我們采用整數編碼的方式，用1－ｎ來表示n個城市，1－n的任意一個排列就構成了問題的一個解。可以知道，對于n個城市的TSP問題，一共有n!種不同的路線。
?。ǎ玻┓N群初始化：對于N個個體的種群，隨機給出N個問題的解（相當于是染色體）作為初始種群。這里具體采用的方法是：1,2，…,n作為第一個個體，然后2,3，…n分別與1交換位置得到n-1個解，從2開始，3,4,…,n分別與2交換位置得到n-2個解，依次類推。（如果這樣還不夠初始種群的數量，可以再考慮n,n-1,…,1這個序列，然后再按照相同的方法生成，等等）
（３）適應度函數：設一個解遍歷初始行走的總距離為D，則適應度fitness=1/D.即總距離越高，適應度越低，總距離越低（解越好），適應度越高。
?。ǎ矗┻x擇操作：個體被選中的概率與適應度成正比，適應度越高，個體被選中的概率越大。這里仍然采用輪盤賭法。選擇作為交叉的雙親，是根據前代染色體的適應函數值所確定的，質量好的個體，即從起點到終點路徑長度短的個體被選中的概率較大。交叉率不可選擇過小，否則，延緩獲得最優(yōu)解的過程，本程序選擇 =0.85。
?。ǎ担┙徊娌僮鳎航徊娌僮魇沁z傳算法最重要的操作，是產生新個體的主要來源，直接關系到算法的全局尋優(yōu)能力，這里采用部分映射交叉。比如對于n = 10的情況，對于兩個路徑:
1 2 4 5 6 3 9 0 8 7
3 9 7 6 8 0 5 1 2 4
隨機產生兩個[1,10]之間的隨機數r1，r2，代表選擇交叉的位置，比如r1 = 2，r2 = 4,如上圖劃線的位置，將第一個個體r1到r2之間的基因(即城市序號)與第二個個體r1到r2之間的基因交換，交換之后變?yōu)?
1 9 7 6 6 3 9 0 8 7
3 2 4 5 8 0 5 1 2 4
劃線部分表示交叉過來的基因，這個時候會發(fā)現可能交叉過來的基因與原來其他位置上的基因有重復，容易直到，第一個個體重復基因的數目與第二個個體重復基因的數目是相同的（這里都是3個），只需要把第一個個體重復的基因與第二個個體重復的基因做交換，即可以消除沖突。消除沖突之后的解如下:
1 9 7 6 5 3 2 0 8 4
3 2 4 5 8 0 6 1 9 7
?。ǎ叮┳儺惒僮?變異操作采取對于一個染色體(即個體)隨機選取兩個基因進行交換的策略。比如對于染色體:
2 4 6 0 3 1 9 7 8 5
隨機選取了兩個位置p1=3,p2=8,交換這兩個位置的基因，得到新的染色體為:
2 4 7 0 3 1 9 6 8 5
變異率的選擇對規(guī)模大的優(yōu)化問題影響很大，本程序選 0.1。為了使算法盡可能快地獲得更好的解，改善遺傳算法的收斂性。在變異操作時，增加了個體求優(yōu)的自學習過程，即在某位基因變異后.計算新產生的染色體的適應函數值，若適應函數值更小，即獲得的路徑更短，則保留;否則，保持原來的解不變。
個人觀點：
?。ǎ保┻€是那句話，程序 = 數據結構 + 算法，所以實現遺傳算法，預先設計一個簡單有效的數據結構至關重要，一個好的數據結構，會讓我們在編碼過程當中，更容易理解和處理程序流程。
?。ǎ玻┻z傳算法并沒有想象的那么復雜和困難，在完成編碼以后，深刻認識到遺傳算法其實就是一種在大量數據中的搜索方法，同時，具有除去不理想狀態(tài)結點的功能，這無疑是遺傳算法的要害之處，極大的增加了程序的收斂性，通過無數次的迭代，不斷從一組數據當中選出當前組當中最好的數據，然后再形成一組數據，這些數據在經過某些調整（選擇、交叉和變異），有可能會產生更理想的數據 。依照此法，不斷迭代生成新的數據，選出較為理想的數據，隨著迭代次數的增加，所產生的數據就會不斷靠近，甚至等于問題的最優(yōu)解。
完整源代碼：
//population 種群
//Chromosome 染色體
//survival? 存活
//crossover rate 交叉率
//mutation rate 突變率
//probability 概率
#include "stdio.h"
#include "stdlib.h"
#include "windows.h"
#include "time.h"
#define cityNum 10 //城市數量（基因數量）（染色體長度）
#define popSize 10 //種群大小（尺寸）
#define croRate 0.85 ? ? //交叉概率
#define mutRate 0.1 //變異概率
#define MAX 999 //進化代數
//定義染色體的結構
struct Chrom
{
int cityArr[cityNum]; //染色體的基因編碼
char name; //染色體的名稱
float adapt; //染色體的適應度
int dis; //染色體的路徑長度
};
struct Chrom genes[popSize]; //定義基因庫（結構體數組）
struct Chrom genesNew[popSize]; //重新建立一個新的種群
struct Chrom temp; //定義臨時公用結點
char names[cityNum] = {'A','B','C','D','E','F','G','H','I','J'}; //城市名稱
int distance[cityNum][cityNum] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9? }, ? ? //城市距離矩陣
{? 1, 0, 1, 2, 3, 4, 5, 6, 7, 8? },
{? 2, 1, 0, 1, 2, 3, 4, 5, 6, 7? },
{? 3, 2, 1, 0, 1, 2, 3, 4, 5, 6? },
{? 4, 3, 2, 1, 0, 1, 2, 3, 4, 5? },
{? 5, 4, 3, 2, 1, 0, 1, 2, 3, 4? },
{? 6, 5, 4, 3, 2, 1, 0, 1, 2, 3? },
{? 7, 6, 5, 4, 3, 2, 1, 0, 1, 2? },
{? 8, 7, 6, 5, 4, 3, 2, 1, 0, 1? },
{? 9, 8, 7, 6, 5, 4, 3, 2, 1, 0? }}; //最優(yōu)解為18
void initGroup()
{
//初始化基因庫
int i,j,k;
int t = 0;
int flag = 0;
srand(time(NULL));//初始化隨機種子,防止隨機數每次重復，常常使用系統(tǒng)時間來初始化,當srand()的參數值固定的時候，rand()獲得的數也是固定的
for(i = 0; i < popSize; i ++)
{
//使用臨時結點開始賦值
? ? temp.name = names[i];
temp.adapt = 0.0f;
temp.dis = 0;
//產生10個不相同的數字
for(j = 0; j < cityNum;)
{
t = rand()%cityNum; //隨機產生0-9的數
flag = 1;
for(k = 0; k < j; k ++)
{
if(genes[i].cityArr[k] == t)
{
flag = 0;
break;
}
}
if(flag)
{
temp.cityArr[j] = t;
genes[i] = temp;//存入結構體數組，產生一個個體
j++;
}
}
}
}
//計算種群所有染色體的個體適應度
void popFitness()
{
int i,n1,n2;
for(i = 0; i < popSize; i ++)
{
genes[i].dis = 0;
for(int j = 1;j < cityNum; j ++)
{
n1 = genes[i].cityArr[j-1];
n2 = genes[i].cityArr[j];
genes[i].dis += distance[n1][n2];
}
genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum-1]];
genes[i].adapt = (float)1/genes[i].dis; //每條染色體的路徑總和(個體適應度)
}
}
//返回最優(yōu)秀的一條染色體
int chooseBest()
{
int choose = 0;
float best = 0.0f;
best = genes[0].adapt;
for(int i = 0; i < popSize; i ++)
{
if(genes[i].adapt < best)
{
best = genes[i].adapt;
choose = i;
}
}
return choose;
}
// 選擇操作
void select()
{
float biggestSum = 0.0f;
float adapt_pro[popSize];
float pick = 0.0f;
int i;
for(i = 0; i < popSize; i ++)
{
biggestSum += genes[i].adapt; // 總概率
}
for(i = 0; i < popSize; i ++)
{
adapt_pro[i] = genes[i].adapt / biggestSum; // 概率數組
}
// 輪盤賭
? ? for(i = 0;i < popSize; i ++)
? ? {
? ? ? ? pick = (float)rand()/RAND_MAX; // 0到1之間的隨機數
? ? ? ? for(int j = 0; j < popSize; j ++)
? ? ? ? {
? ? ? ? ? ? pick = pick - adapt_pro[j];
? ? ? ? ? ? if(pick <= 0)
? ? ? ? ? ? {
genesNew[i] = genes[j];
? ? ? ? ? ? ? break;? ?
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? for(i = 0;i < popSize; i++)
? ? {? ? ?
genes[i] = genesNew[i];
? ? }
}
// 交叉操作
void cross()
{
? ? float pick;
? ? int choice1,choice2;
? ? int pos1,pos2;
? ? int temp;
? ? int conflict1[popSize]; // 沖突位置
? ? int conflict2[popSize];
? ? int num1;
? ? int num2;
? ? int index1,index2;
? ? int move = 0; // 當前移動的位置
? ? while(move < popSize-1)
? ? {
? ? ? ? pick = (float)rand()/RAND_MAX; // 用于決定是否進行交叉操作
? ? ? ? if(pick > croRate) //兩條染色體是否相愛
? ? ? ? {
? ? ? ? ? ? move += 2;
? ? ? ? ? ? continue; // 本次不進行交叉
? ? ? ? }
? ? ? ? // 采用部分映射雜交
? ? ? ? choice1 = move; // 用于選取雜交的兩個父代
? ? ? ? choice2 = move+1; // 注意避免下標越界
? ? ? ? pos1 = rand()%popSize;
? ? ? ? pos2 = rand()%popSize;
? ? ? ? while(pos1 > popSize -2 || pos1 < 1)//如果位置在開頭或結尾(因為全部交換無意義)
? ? ? ? {
? ? ? ? ? ? pos1 = rand()%popSize;? ? ?
? ? ? ? }
? ? ? ? while(pos2 > popSize -2 || pos2 < 1)
? ? ? ? {
? ? ? ? ? ? pos2 = rand()%popSize;
? ? ? ? }
? ? ? ? if(pos1 > pos2)
? ? ? ? {
? ? ? ? ? ? temp = pos1;
? ? ? ? ? ? pos1 = pos2;
? ? ? ? ? ? pos2 = temp; // 交換pos1和pos2的位置
? ? ? ? }
? ? ? ? for(int j = pos1;j <= pos2; j++)// 逐個交換順序
? ? ? ? {
? ? ? ? ? ? temp = genes[choice1].cityArr[j];
? ? ? ? ? ? genes[choice1].cityArr[j] = genes[choice2].cityArr[j];
? ? ? ? ? ? genes[choice2].cityArr[j] = temp;
? ? ? ? }
? ? ? ? num1 = 0;
? ? ? ? num2 = 0;
? ? ? ? if(pos1 > 0 && pos2 < popSize - 1)//分三段
? ? ? ? {
? ? ? ? ? ? for(int j =0;j < pos1;j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for(int k = pos1; k <= pos2; k++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? conflict1[num1] = j;
? ? ? ? ? ? ? ? ? ? ? ? num1 ++;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? conflict2[num2] = j;
? ? ? ? ? ? ? ? ? ? ? ? num2 ++;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? ? for(j = pos2 + 1;j < popSize;j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for(int k = pos1; k <= pos2; k ++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? conflict1[num1] = j;
num1 ++;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? conflict2[num2] = j;
num2 ++;? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if((num1 == num2) && num1 > 0)
? ? ? ? {
? ? ? ? ? ? for(int j = 0;j < num1; j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? index1 = conflict1[j];
? ? ? ? ? ? ? ? index2 = conflict2[j];
? ? ? ? ? ? ? ? temp = genes[choice1].cityArr[index1]; // 交換沖突的位置
? ? ? ? ? ? ? ? genes[choice1].cityArr[index1] = genes[choice2].cityArr[index2];
? ? ? ? ? ? ? ? genes[choice2].cityArr[index2] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? move += 2;
? ? }
}
//變異操作
void mutation()
{
double pick;
? ? int pos1,pos2,temp;
? ? for(int i = 0;i < popSize; i ++)
? ? {
? ? ? ? pick = (float)rand()/RAND_MAX; // 用于判斷是否進行變異操作
? ? ? ? if(pick > mutRate)
{
? ? ? ? ? ? continue;
}
? ? ? ? pos1 = rand()%popSize;
? ? ? ? pos2 = rand()%popSize;
? ? ? ? while(pos1 > popSize - 1)
? ? ? ? {
? ? ? ? ? pos1 = rand()%popSize; ?
? ? ? ? }
? ? ? ? while(pos2 > popSize - 1)
? ? ? ? {
? ? ? ? ? pos2 = rand()%popSize;
? ? ? ? }
? int a = genes[i].dis;
? ? ? ? temp = genes[i].cityArr[pos1];
? ? ? ? genes[i].cityArr[pos1] = genes[i].cityArr[pos2];
? ? ? ? genes[i].cityArr[pos2] = temp;
popFitness();//更新數據
//此步驟的作用在于檢查是否變異后得到的個體比變異前更優(yōu)秀了，如若往壞的方向變化了，那還不如不變異了
//（強制返回，雖然有點違背事物的客觀發(fā)展規(guī)律，但為了增強程序的收斂性，該操作還是有必要的）（偷笑）
if(genes[i].dis > a)
{
temp = genes[i].cityArr[pos1];
genes[i].cityArr[pos1] = genes[i].cityArr[pos2];
genes[i].cityArr[pos2] = temp;
}
? ? }
}
int main()
{
char c = 0;
printf("\n\t\t******************************** 遺傳算法求解TSP(旅行商)問題 *********************************\n");
initGroup(); //初始化
popFitness(); //更新數據
//輸出配置信息
printf("\n\t\t基因長度:%d",cityNum);
printf("\t種群大小:%d",popSize);
printf("\t交叉概率:%.2f",croRate);
printf("\t變異概率:%.2f",mutRate);
printf("\t進化代數:%d",MAX);
printf("\t預設最優(yōu)解：18");
printf("\n\n\t\t**********************************************************************************************\n");
//輸出距離矩陣
printf("\n\t\t--------- 城市距離矩陣 ---------\n");
printf("\t\t");
int i,j;
for(i = 0; i < cityNum; i ++)
{
for(j = 0;j < cityNum; j ++)
{
printf("? %d",distance[i][j]);
}
printf("\n\t\t");
}
printf("--------------------------------");
//輸出路徑信息
printf("\n\t\t-------- 初始種群基因庫 --------\n");
printf("\t\t ");
for(i = 0; i < cityNum; i ++)
{
printf("? %c",genes[i].name);
}
printf("\n\t\t");
for(i = 0;i < cityNum; i ++)
{
printf("%c",genes[i].name);
for(j = 0; j < cityNum; j ++)
{
printf("? %d",genes[i].cityArr[j]);
}
printf("\n\t\t");
}
printf("--------------------------------\n");
do
{
printf("\n\t\t尋求最優(yōu)解中：");
//通過不斷進化，直到達到定義的進化代數
for(i = 0; i < MAX; i ++)
{
select();
cross();
mutation();
popFitness();//更新數據
int temp = (int)MAX/20;
if( i % temp == 0)
{
printf("▊");
Sleep(200);
}
}
printf("完成");
printf("\n\n\t\t最優(yōu)路徑：");
for(i = 0; i < cityNum ; i++)
{
printf("%d-->",genes[chooseBest()].cityArr[i]);
}
printf("%d",genes[chooseBest()].cityArr[0]);
printf("\n\n\t\t路徑長度:%d",genes[chooseBest()].dis);
printf("\n\n\t\t是否再試一次?(Y/y) 是/(N/n) 否：");
? ? fflush(stdin);
? ? c = getchar();
? ? fflush(stdin);
if(c=='N'||c=='n')
{
break;
}
}while(1);
printf("\n\t\t");
return 0;
}
