姓名：楊晶晶 學(xué)號：21011210420 學(xué)院：通信工程學(xué)院
轉(zhuǎn)載自：https://blog.csdn.net/ritterliu/article/details/54821300
【嵌牛導(dǎo)讀】遺傳算法哨坪，核心是達爾文優(yōu)勝劣汰適者生存的進化理論的思想贷掖。我們都知道一個種群蔑匣，通過長時間的繁衍谦趣，種群的基因會向著更適應(yīng)環(huán)境的趨勢進化畔况，優(yōu)良的基因會被保留之景，后代越來越多限佩，適應(yīng)能力低個體的基因被淘汰，后代越來越少塑悼。經(jīng)過幾代的繁衍進化劲适，留下來的少數(shù)個體，就是相對能力最強的個體了厢蒜。那么在解決一些問題的時候霞势，我們能不能學(xué)習(xí)這樣的思想。
【嵌牛鼻子】遺傳算法的基本概念斑鸦；遺傳算法代碼愕贡。
【嵌牛提問】什么是遺傳算法？利用C語言設(shè)計相關(guān)代碼進行驗證巷屿。
【嵌牛正文】
遺傳算法介紹
遺傳算法是一種模擬生命進化機制的搜索和優(yōu)化方法固以，是把自然遺傳學(xué)和計算機科學(xué)結(jié)合起來的優(yōu)化方程，有很強的解決問題的能力和廣泛的適應(yīng)性嘱巾。其假設(shè)常描述為二進制位串嘴纺，位串的含義依賴于具體應(yīng)用。搜索合適的假設(shè)從若干初始假設(shè)的群體集合開始浓冒。當(dāng)前種群成員通過模仿生物進化的方式來產(chǎn)生下一代群體，如隨機變異和交叉尖坤。每一步稳懒，根據(jù)給定的適應(yīng)度評估當(dāng)前群體的假設(shè)，而后使用概率方法選出適應(yīng)度最高的假設(shè)作為產(chǎn)生下一代的種子慢味。
遺傳算法的幾個基本概念
〕“稹（1）染色體（Chromosome）：在使用遺傳算法時，需要把問題的解編成一個適合的碼子纯路。這種具有固定結(jié)構(gòu)的符號串既是染色體或油，符號串的每一位代表一個基因。符號串的總位數(shù)成為染色體的長度驰唬，一個染色體就代表問題的一個解顶岸，每個染色體也被稱為一個個體腔彰。
（2）群體（Population）：每代所產(chǎn)生的染色體總數(shù)成為群體辖佣，一個群體包含了該問題在這一代的一些解的集合霹抛。
（3）適應(yīng)度（Fitness）：對群體中每個染色體進行編碼后卷谈，每個個體對應(yīng)一個具體問題的解杯拐，而每個解對應(yīng)于一個函數(shù)值。該函數(shù)值即適應(yīng)函數(shù)世蔗，就是衡量染色體對環(huán)境適應(yīng)度的指標(biāo)端逼，也是反映實際問題的目標(biāo)函數(shù)
基本的遺傳操作
（1）選擇（Select）：按一定的概率從上代群體中選擇M對個體作為雙親污淋，直接拷貝到下一代顶滩，染色體不發(fā)生變化。
≤搅ぁ（2）交叉（Crossover）：對于選中進行繁殖的兩個染色體X诲祸，Y，以X而昨，Y為雙親作交叉操作救氯，從而產(chǎn)生兩個后代X1，Y1.
「韬（3）變異（Mutation）：對于選中的群體中的個體（染色體）着憨，隨機選取某一位進行取反運算，即將該染色體碼翻轉(zhuǎn)务嫡。
用遺傳算法求解的過程是根據(jù)待解決問題的參數(shù)集進行編碼甲抖，隨機產(chǎn)生一個種群，計算適應(yīng)函數(shù)和選擇率心铃，進行選擇准谚、交叉、變異操作去扣。如果滿足收斂條件柱衔，此種群為最好個體，否則愉棱，對產(chǎn)生的新一代群體重新進行選擇唆铐、交叉、變異操作奔滑，循環(huán)往復(fù)直到滿足條件艾岂。
TSP問題
所謂TSP問題（旅行商問題）即最短路徑問題就是在給定的起始點S到終止點T的通路集合中，尋求距離最小的通路朋其，這樣的通路成為S點到T點的最短路徑王浴。在尋找最短路徑問題上脆炎，有時不僅要知道兩個指定頂點間的最短路徑，還需要知道某個頂點到其他任意頂點間的最短路徑叼耙。用遺傳算法解決這類問題腕窥，沒有太多的約束條件和有關(guān)解的限制，因而可以很快地求出任意兩點間的最短路徑以及一批次短路徑筛婉。
TSP問題的遺傳算法設(shè)計與實現(xiàn)
〈乇（１）編碼問題：由于這是一個離散型的問題，我們采用整數(shù)編碼的方式爽撒，用1－ｎ來表示n個城市入蛆，1－n的任意一個排列就構(gòu)成了問題的一個解∷段穑可以知道哨毁，對于n個城市的TSP問題，一共有n!種不同的路線源武。
《笸省（２）種群初始化：對于N個個體的種群，隨機給出N個問題的解（相當(dāng)于是染色體）作為初始種群粱栖。這里具體采用的方法是：1,2话浇，…,n作為第一個個體，然后2,3闹究，…n分別與1交換位置得到n-1個解幔崖，從2開始，3,4,…,n分別與2交換位置得到n-2個解渣淤，依次類推赏寇。（如果這樣還不夠初始種群的數(shù)量，可以再考慮n,n-1,…,1這個序列价认，然后再按照相同的方法生成嗅定，等等）
（３）適應(yīng)度函數(shù)：設(shè)一個解遍歷初始行走的總距離為D用踩，則適應(yīng)度fitness=1/D.即總距離越高露戒，適應(yīng)度越低，總距離越低（解越好）捶箱，適應(yīng)度越高。
《（４）選擇操作：個體被選中的概率與適應(yīng)度成正比丁屎，適應(yīng)度越高，個體被選中的概率越大旱眯。這里仍然采用輪盤賭法晨川。選擇作為交叉的雙親证九，是根據(jù)前代染色體的適應(yīng)函數(shù)值所確定的，質(zhì)量好的個體共虑，即從起點到終點路徑長度短的個體被選中的概率較大愧怜。交叉率不可選擇過小，否則妈拌，延緩獲得最優(yōu)解的過程拥坛，本程序選擇 =0.85。
〕痉帧（５）交叉操作：交叉操作是遺傳算法最重要的操作猜惋，是產(chǎn)生新個體的主要來源，直接關(guān)系到算法的全局尋優(yōu)能力培愁，這里采用部分映射交叉著摔。比如對于n = 10的情況，對于兩個路徑:
1 2 4 5 6 3 9 0 8 7
3 9 7 6 8 0 5 1 2 4
隨機產(chǎn)生兩個[1,10]之間的隨機數(shù)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ā)現(xiàn)可能交叉過來的基因與原來其他位置上的基因有重復(fù)港粱，容易直到，第一個個體重復(fù)基因的數(shù)目與第二個個體重復(fù)基因的數(shù)目是相同的（這里都是3個）旦签，只需要把第一個個體重復(fù)的基因與第二個個體重復(fù)的基因做交換查坪，即可以消除沖突。消除沖突之后的解如下:
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)的自學(xué)習(xí)過程，即在某位基因變異后.計算新產(chǎn)生的染色體的適應(yīng)函數(shù)值幽钢，若適應(yīng)函數(shù)值更小歉备，即獲得的路徑更短，則保留;否則匪燕，保持原來的解不變蕾羊。
個人觀點：
∩逃印（１）還是那句話笤昨，程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法赴邻，所以實現(xiàn)遺傳算法审胸，預(yù)先設(shè)計一個簡單有效的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要，一個好的數(shù)據(jù)結(jié)構(gòu)利凑，會讓我們在編碼過程當(dāng)中浆劲，更容易理解和處理程序流程。
〗夭辍（２）遺傳算法并沒有想象的那么復(fù)雜和困難梳侨，在完成編碼以后，深刻認(rèn)識到遺傳算法其實就是一種在大量數(shù)據(jù)中的搜索方法日丹，同時走哺，具有除去不理想狀態(tài)結(jié)點的功能，這無疑是遺傳算法的要害之處哲虾，極大的增加了程序的收斂性丙躏，通過無數(shù)次的迭代，不斷從一組數(shù)據(jù)當(dāng)中選出當(dāng)前組當(dāng)中最好的數(shù)據(jù)束凑，然后再形成一組數(shù)據(jù)晒旅，這些數(shù)據(jù)在經(jīng)過某些調(diào)整（選擇、交叉和變異）汪诉，有可能會產(chǎn)生更理想的數(shù)據(jù) 废恋。依照此法，不斷迭代生成新的數(shù)據(jù)扒寄，選出較為理想的數(shù)據(jù)鱼鼓，隨著迭代次數(shù)的增加，所產(chǎn)生的數(shù)據(jù)就會不斷靠近该编，甚至等于問題的最優(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 //城市數(shù)量（基因數(shù)量）（染色體長度）
#define popSize 10 //種群大小（尺寸）
#define croRate 0.85 ? ? //交叉概率
#define mutRate 0.1 //變異概率
#define MAX 999 //進化代數(shù)
//定義染色體的結(jié)構(gòu)
struct Chrom
{
int cityArr[cityNum]; //染色體的基因編碼
char name; //染色體的名稱
float adapt; //染色體的適應(yīng)度
int dis; //染色體的路徑長度
};
struct Chrom genes[popSize]; //定義基因庫（結(jié)構(gòu)體數(shù)組）
struct Chrom genesNew[popSize]; //重新建立一個新的種群
struct Chrom temp; //定義臨時公用結(jié)點
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));//初始化隨機種子,防止隨機數(shù)每次重復(fù)课竣，常常使用系統(tǒng)時間來初始化,當(dāng)srand()的參數(shù)值固定的時候嘉赎，rand()獲得的數(shù)也是固定的
for(i = 0; i < popSize; i ++)
{
//使用臨時結(jié)點開始賦值
? ? temp.name = names[i];
temp.adapt = 0.0f;
temp.dis = 0;
//產(chǎn)生10個不相同的數(shù)字
for(j = 0; j < cityNum;)
{
t = rand()%cityNum; //隨機產(chǎn)生0-9的數(shù)
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;//存入結(jié)構(gòu)體數(shù)組，產(chǎn)生一個個體
j++;
}
}
}
}
//計算種群所有染色體的個體適應(yīng)度
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īng)度)
}
}
//返回最優(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; // 概率數(shù)組
}
// 輪盤賭
? ? for(i = 0;i < popSize; i ++)
? ? {
? ? ? ? pick = (float)rand()/RAND_MAX; // 0到1之間的隨機數(shù)
? ? ? ? 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; // 當(dāng)前移動的位置
? ? while(move < popSize-1)
? ? {
? ? ? ? pick = (float)rand()/RAND_MAX; // 用于決定是否進行交叉操作
? ? ? ? if(pick > croRate) //兩條染色體是否相愛
? ? ? ? {
? ? ? ? ? ? move += 2;
? ? ? ? ? ? continue; // 本次不進行交叉
? ? ? ? }
? ? ? ? // 采用部分映射雜交
? ? ? ? choice1 = move; // 用于選取雜交的兩個父代
? ? ? ? choice2 = move+1; // 注意避免下標(biāo)越界
? ? ? ? pos1 = rand()%popSize;
? ? ? ? pos2 = rand()%popSize;
? ? ? ? while(pos1 > popSize -2 || pos1 < 1)//如果位置在開頭或結(jié)尾(因為全部交換無意義)
? ? ? ? {
? ? ? ? ? ? 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();//更新數(shù)據(jù)
//此步驟的作用在于檢查是否變異后得到的個體比變異前更優(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(); //更新數(shù)據(jù)
//輸出配置信息
printf("\n\t\t基因長度:%d",cityNum);
printf("\t種群大小:%d",popSize);
printf("\t交叉概率:%.2f",croRate);
printf("\t變異概率:%.2f",mutRate);
printf("\t進化代數(shù):%d",MAX);
printf("\t預(yù)設(shè)最優(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)解中：");
//通過不斷進化，直到達到定義的進化代數(shù)
for(i = 0; i < MAX; i ++)
{
select();
cross();
mutation();
popFitness();//更新數(shù)據(jù)
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;
}
