遺傳算法的簡單應用，關于巡回旅行商(TSP)的求解問題，采用了C#語言實作的。
上篇我們用遺傳算法求解了方程，其中用到的編碼方式是二進制的編碼，實作起來相對簡單很多，
就連交配和變異等操作也是比較簡單，但是對于TSP問題，就稍微複雜一點，需要有一定的政策，
才能較好的實作。
這次的TSP問題的題目是：
随機産生10~30個城市，每個城市之間的距離也是随機産生，距離的範圍是[1,50]，求最優的路徑
==========================================================
下面就是具體的求解，由于我的政策是基于知網上的《一種改進的遺傳算法求解TSP問題》這篇文章，
是以把這篇文章先放上來。下面我簡單介紹一下這篇文章關于求解TSP問題的政策，然後附上參照這篇
文章寫的代碼。
政策簡述：
1、染色體編碼
為了充分利用城市間相鄰邊的資訊和距離的資訊，不采用二進制編碼而是采用整數編碼，即每個染
色體都是一個1到N的排列，表示周遊路線的城市間的先後順序序列。
/// <summary>
/// 初始化群體
/// </summary>
static void Initial_Group()
{
int count = 0;//已産生個體數
List<int> myRoad = new List<int>();
string road = string.Empty;//個體的表現型
for (int i = 0; i < city_count; i++)
{
myRoad.Add(i);
}
while (count < gruopCount)//20個個體
{
int tmp, index;
for (int i = 0; i < myRoad.Count; i++)//随機交換得到一組路徑(個體)
{
index = rd.Next(myRoad.Count);
tmp = myRoad[i];
myRoad[i] = myRoad[index];
myRoad[index] = tmp;
}
for (int i = 0; i < myRoad.Count; i++)//将個體轉化成路徑存到種群中
{
road += MyEncode(myRoad[i]);//自己編碼如果大于10,轉化成對應的符号
}
group.Add(road);
count++;
road = "";
}
//foreach (var item in group)
//{
// Console.WriteLine(item + " " + Ca(item));
//}
} View Code
2、選擇算子
這裡沒有采用輪盤賭算法，而是采用了錦标賽選擇，即每次從群體中随機抽 取出M個個體，然後選
擇其中适應值最好的進入下 一代，接着進行下一個錦标賽選擇直至選出種群數目個個體為止。錦标
賽選擇算子保證了更優的染色體能夠有更大的存活機會，當然，同一個優秀的個體被多次選中也是
允許的。這裡的M取2.
/// <summary>
/// 選擇(錦标賽)
/// 思路:1.産生兩個不同的随機數作為要參加錦标賽的兩個個體;2.判斷适應度大小,
/// 小的被選擇(最短路徑)
/// </summary>
/// <param name="list">适應度集合</param>
static void Selection(List<int> list)
{
int count = 0;//選擇的數量
List<string> result = new List<string>();//選擇的結果
while (count < gruopCount)
{
int test1 = rd.Next(0, gruopCount);//要參加錦标賽的的兩個個體
int test2 = rd.Next(0, gruopCount);
if (test1 != test2)
{
if (list[test1] >= list[test2])
{
result.Add(group[test2]);
}
else
{
result.Add(group[test1]);
}
}
count++;
}
//更新種群資訊
for (int i = 0; i < result.Count; i++)
{
group[i] = result[i];
}
} 3、交配算子
利用相鄰邊的資訊和距離的資訊作為啟發來設計一種基于頂點的候選表的交配算子(CandidateCrossover)
具體步驟如下：
①交配算子根據交配機率pc來選擇兩個父體進行交配。把這兩個父體看作是兩個循環隊列，然後産生一個
随機數k作為交配位。 交配位所對應的父體1中的城市作為目前的城市加入到子代1中；
②找到該城市在父體2中對應的位置，分别把該城市在父體1和 父體2中的左右鄰接城市(和這個城市相連接配接
的邊的另外兩個城市)加入到目前城市的候選表中，如果其左右鄰接城市已在子代中，則選擇其次鄰接城市，
依次類推直至所選取的城市不在子 代中，而最後一個城市的下一個城市是第一個城市；
③根據距離矩陣計算目前城市和候選表中的各個城市的距離，找出與目前城市距離最短的城市加入到子代中，
并且把這個距離最短的城市又當作當 前城市，找到此城市在父體1中的位置，傳回到第2 步繼續執行，
直到所有的城市加入到子代1中為止。
/// <summary>
/// 基于鄰接表的交叉實作
/// </summary>
/// <param name="str1">個體1的染色體</param>
/// <param name="str2">個體2的染色體</param>
/// <returns></returns>
static string Candidate_Crossover(string str1, string str2)
{
int k = rd.Next(city_count);
int j = 0;
List<int> list = new List<int>();//子代
List<int> tmp = new List<int>();//候選表
string result = string.Empty;
string son = str1[k].ToString();//第一個個體選的城市
int current = MyDecode(son);//目前城市
list.Add(MyDecode(son));
while (list.Count < city_count)
{
if (list.Count < city_count - 1)
{
for (int i = 0; i < str2.Length; i++)
{
if (MyDecode(str2[i].ToString()) == current)
{
j = i;
break;
}
}
string str = "";
//str1 左邊
for (int i = 0; i < str1.Length; i++)
{
str = str1[(k - i + city_count) % city_count].ToString();
if (!list.Contains(MyDecode(str)))
{
tmp.Add(MyDecode(str));
break;
}
}
//str1 右邊
for (int i = 0; i < str1.Length; i++)
{
str = str1[(k + i) % city_count].ToString();
if (!list.Contains(MyDecode(str)))
{
tmp.Add(MyDecode(str));
break;
}
}
//str2 左邊
for (int i = 0; i < str2.Length; i++)
{
str = str2[(j - i + city_count) % city_count].ToString();
if (!list.Contains(MyDecode(str)))
{
tmp.Add(MyDecode(str));
break;
}
}
//str2 右邊
for (int i = 0; i < str2.Length; i++)
{
str = str2[(j + i) % city_count].ToString();
if (!list.Contains(MyDecode(str)))
{
tmp.Add(MyDecode(str));
break;
}
}
Dictionary<int, int> dic = new Dictionary<int, int>();
foreach (var item in tmp)
{
if (!dic.ContainsKey(item))
{
dic.Add(item, distance[current, item]);
}
}
int minKey = dic.OrderBy(s => s.Value).Select(s => s.Key).FirstOrDefault();
for (int i = 0; i < str1.Length; i++)
{
if (minKey == MyDecode(str1[i].ToString()))
{
k = i;
current = minKey;
list.Add(minKey);
break;
}
}
tmp.Clear();
}
else if (list.Count == city_count - 1)
{
foreach (var a in str1)
{
if (!list.Contains(MyDecode(a.ToString())))
{
list.Add(MyDecode(a.ToString()));
}
}
}
}
foreach (var item in list)
{
result += MyEncode(item);
}
return result;
} 4、變異算子
變異操作發生在某個染色體的某個基因上，它将可變性引入群體中，增強了群體的多樣性，進而提供了從局部
最優中跳出來的一種手段。變異方法也是一個随機的、盲目的變異，是以需要使用比較小的變異機率（pm）
來控制以避免造成種群的破壞。這裡采用的是基于位置的變異也稱為插入式變異(InsertionMutation)，該算子
在染色體中随機産生兩個變異位，然後把第二個位置的基因插入到第一個位置的基因之前。
/// <summary>
/// 插入式變異(ISM)
/// 思路:1.産生兩個随機位置;2.将第二個位置的數放在第一個位置的數的前面
/// </summary>
/// <param name="str1">要變異的個體</param>
/// <returns>變異過後的個體</returns>
static string Opreation_Mutation(string str1)
{
int pos1 = rd.Next(1, city_count);//産生兩個位置
int pos2 = rd.Next(1, city_count);
if (pos1 < pos2)
{
string s = str1[pos2 - 1].ToString();
return str1.Insert(pos1 - 1, s).Remove(pos2, 1);
}
else if (pos1 > pos2)
{
string s = str1[pos1 - 1].ToString();
return str1.Insert(pos2 - 1, s).Remove(pos1, 1);
}
else//如果相等的兩個位置,則重新産生小範圍的随機數
{
int pos3 = rd.Next(1, city_count / 2);
int pos4 = rd.Next(city_count / 2, city_count);
string s = str1[pos2 - 1].ToString();
return str1.Insert(pos1 - 1, s).Remove(pos2, 1);
}
} 其中的方法，實作不唯一，時間比較敢，也沒有作一定的優化，隻是為了熟悉算法而寫的。
希望能幫到初學者，也歡迎各位提出修改意見。
完整代碼可在這下載下傳
https://github.com/hwqdt/Catcher.TSP
如果您認為這篇文章還不錯或者有所收獲，可以點選右下角的【推薦】按鈕，因為你的支援是我繼續寫作，分享的最大動力！
作者：Catcher Wong ( 黃文清 )
來源：http://catcher1994.cnblogs.com/
聲明：
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。如果您發現部落格中出現了錯誤，或者有更好的建議、想法，請及時與我聯系！！如果想找我私下交流，可以私信或者加我微信。