遺傳算法
遺傳算法介紹
遺傳算法是一種模拟生命進化機制的搜尋和優化方法，是把自然遺傳學和計算機科學結合起來的優化方程，有很強的解決問題的能力和廣泛的适應性。其假設常描述為二進制位串，位串的含義依賴于具體應用。搜尋合适的假設從若幹初始假設的群體集合開始。目前種群成員通過模仿生物進化的方式來産生下一代群體，如随機變異和交叉。每一步，根據給定的适應度評估目前群體的假設，而後使用機率方法選出适應度最高的假設作為産生下一代的種子。
遺傳算法的幾個基本概念
（1）染色體（Chromosome）：在使用遺傳算法時，需要把問題的解編成一個适合的碼子。這種具有固定結構的符号串既是染色體，符号串的每一位代表一個基因。符号串的總位數成為染色體的長度，一個染色體就代表問題的一個解，每個染色體也被稱為一個個體。
（2）群體（Population）：每代所産生的染色體總數成為群體，一個群體包含了該問題在這一代的一些解的集合。
（3）适應度（Fitness）：對群體中每個染色體進行編碼後，每個個體對應一個具體問題的解，而每個解對應于一個函數值。該函數值即适應函數，就是衡量染色體對環境适應度的名額，也是反映實際問題的目标函數
基本的遺傳操作
（1）選擇（Select）：按一定的機率從上代群體中選擇M對個體作為雙親，直接拷貝到下一代，染色體不發生變化。
（2）交叉（Crossover）：對于選中進行繁殖的兩個染色體X，Y，以X，Y為雙親作交叉操作，進而産生兩個後代X1，Y1.
（3）變異（Mutation）：對于選中的群體中的個體（染色體），随機選取某一位進行取反運算，即将該染色體碼翻轉。
用遺傳算法求解的過程是根據待解決問題的參數集進行編碼，随機産生一個種群，計算适應函數和選擇率，進行選擇、交叉、變異操作。如果滿足收斂條件，此種群為最好個體，否則，對産生的新一代群體重新進行選擇、交叉、變異操作，循環往複直到滿足條件。
TSP問題
所謂TSP問題（旅行商問題）即最短路徑問題就是在給定的起始點S到終止點T的通路集合中，尋求距離最小的通路，這樣的通路成為S點到T點的最短路徑。在尋找最短路徑問題上，有時不僅要知道兩個指定頂點間的最短路徑，還需要知道某個頂點到其他任意頂點間的最短路徑。用遺傳算法解決這類問題，沒有太多的限制條件和有關解的限制，因而可以很快地求出任意兩點間的最短路徑以及一批次短路徑。
TSP問題的遺傳算法設計與實作
（１）編碼問題：由于這是一個離散型的問題，我們采用整數編碼的方式，用1－ｎ來表示n個城市，1－n的任意一個排列就構成了問題的一個解。可以知道，對于n個城市的TSP問題，一共有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.即總距離越高，适應度越低，總距離越低（解越好），适應度越高。
（４）選擇操作：個體被選中的機率與适應度成正比，适應度越高，個體被選中的機率越大。這裡仍然采用輪盤賭法。選擇作為交叉的雙親，是根據前代染色體的适應函數值所确定的，品質好的個體，即從起點到終點路徑長度短的個體被選中的機率較大。交叉率不可選擇過小，否則，延緩獲得最優解的過程，本程式選擇 =0.85。
（５）交叉操作：交叉操作是遺傳算法最重要的操作，是産生新個體的主要來源，直接關系到算法的全局尋優能力，這裡采用部分映射交叉。比如對于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之間的基因交換，交換之後變為:
1 9 7 6 6 3 9 0 8 7
3 2 4 5 8 0 5 1 2 4
劃線部分表示交叉過來的基因，這個時候會發現可能交叉過來的基因與原來其他位置上的基因有重複，容易直到，第一個個體重複基因的數目與第二個個體重複基因的數目是相同的（這裡都是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
變異率的選擇對規模大的優化問題影響很大，本程式選 0.1。為了使算法盡可能快地獲得更好的解，改善遺傳算法的收斂性。在變異操作時，增加了個體求優的自學習過程，即在某位基因變異後.計算新産生的染色體的适應函數值，若适應函數值更小，即獲得的路徑更短，則保留;否則，保持原來的解不變。
流程圖：
效果圖：
//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 }}; //最優解為18
void initGroup()
{
//初始化基因庫
int i,j,k;
int t = 0;
int flag = 0;
srand(time(NULL));//初始化随機種子,防止随機數每次重複，常常使用系統時間來初始化,當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; //每條染色體的路徑總和(個體适應度)
}
}
//傳回最優秀的一條染色體
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();//更新資料
//此步驟的作用在于檢查是否變異後得到的個體比變異前更優秀了，如若往壞的方向變化了，那還不如不變異了
//（強制傳回，雖然有點違背事物的客觀發展規律，但為了增強程式的收斂性，該操作還是有必要的）（偷笑）
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預設最優解：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尋求最優解中：");
//通過不斷進化，直到達到定義的進化代數
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最優路徑：");
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;
}