? 遺傳算法（Genetic Algorithm）又叫基因進化算法味咳，或進化算法家夺。屬于啟發(fā)式搜索算法一種，這個算法比較有趣佣蓉，并且弄明白后很簡單，寫個100-200行代碼就可以實現(xiàn)亲雪。在某些場合下簡單有效勇凭。本文就花一些篇幅，盡量白話方式講解一下义辕。
? ? 首先說一下問題虾标。在我們學校數(shù)據(jù)結構這門功課的時候，時常會有一些比較經典的問題（而且比較復雜問題）作為學習素材灌砖，如八皇后璧函，背包問題，染色問題等等基显。上面列出的幾個問題都可以通過遺傳算法去解決蘸吓。本文列舉的問題是TSP(Traveling Salesman Problem)類的問題。
? ? ? TSP問題實際上是”哈密頓回路問題”中的”哈密頓最短回路問題”.如下圖撩幽，就是要把下面8個城市不重復的全部走一遍库继。有點像小時候玩的畫筆畫游戲，一筆到底不能重復窜醉。TSP不光是要求全部走一遍宪萄，并且是要求路徑最短。就是有可能全部走一遍有很多走法榨惰，要找出其中總路程最短的走法拜英。
和這個問題有點相似的是歐拉回路（下圖）問題，它不是要求把每個點都走一遍琅催，而是要求把每個邊都不重復走一遍(點可以重復)居凶，當然歐拉回路不是本算法研究的范疇。
本文會從TSP引申出下面系列問題
1恢暖、 TSP問題：要求每個點都遍歷到排监，而且要求每個點只被遍歷一次，并且總路程最短杰捂。
2舆床、 最短路徑問題：要求從城市1 到城市8，找一條最短路徑。
3挨队、 遍歷m個點谷暮，要求找出其距離最短的路線。(如果m=N總數(shù)盛垦，其實就是問題1了湿弦，所以問題1可以看成是問題3的特例 )。
遺傳算法的理論是根據(jù)達爾文進化論而設計出來的算法: 人類是朝著好的方向（最優(yōu)解）進化腾夯，進化過程中颊埃，會自動選擇優(yōu)良基因，淘汰劣等基因蝶俱。
在上面tsp問題中班利，一個城市節(jié)點可以看成是一個基因，一個最優(yōu)解就是一條路徑榨呆，包含若干個點罗标。就類似一條染色體有若干基因組成一樣。所以求最短路徑問題积蜻，可以抽象成求最優(yōu)染色體的問題闯割。
遺傳算法很簡單，沒有什么分支判斷竿拆，只有兩個大循環(huán)宙拉，流程大概如下
? 流程中有幾個關鍵元素：
1、 適度值評估函數(shù)丙笋。這個函數(shù)是算法的關鍵鼓黔，就是對這個繁衍出來的后代進行評估打分，是優(yōu)秀不见，還是一般，還是很差的畸形兒崔步。用這個函數(shù)進行量化稳吮。在tsp中，路徑越短井濒，分數(shù)越高灶似。函數(shù)可以可以這樣 fitness = 1/total_distance. 或者 fitness = MAX_DISTANCE – total_distance. 不同的計算方法會影響算法的收斂速度，直接影響結果和性能瑞你。
2酪惭、 選擇運算規(guī)則: 又稱選擇算子。對應著達爾文理論中適者生存者甲，也有地方叫著精英主義原則春感，意思就是只有優(yōu)秀的人才有更大的幾率存活下來，擁有交配權。有權利擁有更多后代鲫懒，傳承下自己血脈基因嫩实。和現(xiàn)實中很相像，皇帝權臣遺留下來的子孫后代比較多窥岩。選擇方法比較多甲献。最常見的是round robin selection 算法，即輪盤賭算法, 這個算法比較簡單有效颂翼。選擇算法目前已有的有10來種之多晃洒。各種不同業(yè)務可以按需選擇。
? 選擇公式如下:
//選擇運算---輪盤賭,此算法要求不能有負數(shù).
? ? int32_t Genetic::Selection(Genome & selGenome)
? ? {
? ? ? ? //生成一個隨機浮點數(shù)
? ? ? ? //本算法在輪盤賭算法上加上了選擇概率朦乏，提高最大可行解入圍概率
? ? ? ? double ftmp = (((random())%100001)/(100000 + 0.0000001));
? ? ? ? if( ftmp > 0.9 )
? ? ? ? {
? ? ? ? ? ? GetBestGenome(selGenome);
? ? ? ? ? ? return ESUCCESS;
? ? ? ? }
? ? ? ? //生成一個【0球及， m_dTotalFitness】之間的隨機浮點數(shù)
? ? ? ? double dRange? ? = (((random()+ random())%100001)/(100000 + 0.0000001)) * m_dTotalFitness;
? ? ? ? double dCursor? ? = 0.0;
? ? ? ? size_t i? ? ? ? = 0;
? ? ? ? for(i = 0; i < m_vGenome.size(); ++i)
? ? ? ? {
? ? ? ? ? ? dCursor += m_vGenome[i].dFitness;
? ? ? ? ? ? if (dCursor > dRange)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? selGenome = m_vGenome[i];
? ? ? ? return ESUCCESS;
? ? }
3、 交叉運算規(guī)則：又稱交配規(guī)則集歇，交叉算子桶略。對應遺傳學中的精子和卵子產生的受精卵含有精子的部分基因，也含有卵子的部分基因的現(xiàn)象诲宇。就像孩子有點像父親际歼，又有點像母親的規(guī)律。交叉運算算法更多姑蓝。作者可以天馬行空的自己去想象鹅心。只要達到交叉結果中含有父母的基因就可以。最常見的是k-opt 交換纺荧。其中k可以是 1,2,3….等等旭愧。簡稱單點交換，兩點交換宙暇，3點交換等等:
單點交換
其中修復重復基因根據(jù)業(yè)務需要看是否需要输枯。
兩點交換
4、 變異運算規(guī)則：又叫變異算子占贫。在人類遺傳進化過程中桃熄。會發(fā)生一些基因突變。這些突變有可能是好的突變型奥，有可能是壞的突變瞳收。像癌細胞就是壞的突變。愛因斯坦的大腦估計是好的突變厢汹。突變方法也是可以天馬行空的自己去發(fā)揮創(chuàng)造螟深。
這里討論一下，為什么要有突變這道流程呢烫葬。從人類進化角度來說界弧。人類基因有數(shù)十萬種凡蜻，在遠古交流比較少的年代。都是部落內部通婚夹纫，但是整個部落內部居民可能都缺少某種好的基因咽瓷，這樣無論他們怎么交配，都不會產生好的基因舰讹，那么他們需要引入好的基因茅姜，于是和其他部落通婚。引入其他自己沒有的基因月匣，其實對于這個種群來說這就是一次基因變異钻洒。如果是好的變異，那么這個后代就很優(yōu)秀锄开，結果就是會產生更多子孫素标，把這個好的變異基因傳承下去，如果不是好的變異基因萍悴，自然而然會在前面選擇算子下淘汰头遭，就是現(xiàn)實生活中的所謂的年幼夭折，癡呆無后癣诱，或先天畸形被淘汰计维，不會傳承下去。
從計算機算法角度看：所有的啟發(fā)式算法無外乎2種手段結合撕予。局域搜索和全域搜索鲫惶。局域搜索是在鄰域范圍內找出最優(yōu)解。對應的是選擇算子和交叉算子实抡。在自己部落里面找最優(yōu)秀的人欠母。如果只有局域搜索的話，就容易陷入局域最優(yōu)解吆寨。算法結果肯定是要找出全域最優(yōu)解赏淌。這就要求跳出局域搜索。我們稱之為“創(chuàng)新”啄清。創(chuàng)新就是一次打破常規(guī)的突破——就是我們的“變異”算子猜敢。
這里拿最短路徑路徑舉例子，求點1到點8之間的最短路徑盒延，初始解是1——2——3——6——8
內變異：所謂內變異就是在自己內部發(fā)生變異。嚴格來說其實不是一種變異鼠冕。但是它又是一種比較有效的手段添寺。
外變異：外變異是引入創(chuàng)新，突破傳統(tǒng)的質的飛躍, 也是啟發(fā)算法中所謂的全域搜索懈费。下面是充當前基因中引入外部基因（當前集合的補集）计露。
結尾：遺傳算法除了上述這些幾個主要算子之外，還有一些細節(jié)。如交叉概率pc票罐，變異概率pm叉趣，這些雖然都是輔助手段，但是有時候對整個算法結果和性能帶來截然不同的效果该押。這也是啟發(fā)式算法的一個缺點疗杉。參數(shù)需要不停的在實踐中摸索，沒有萬能的推薦參數(shù)蚕礼。
還有細心的讀者可能發(fā)現(xiàn)幾個疑問烟具，就是最短路徑中變異或交叉結果可能產生無效解，如前面最短路徑 1——6——3——2——8.? 其中1和6之間根本沒有通路奠蹬。碰到這種情況朝聋，可以拋棄這條非法解，重新生成一條隨機新解（其實這也是一次變異創(chuàng)新）囤躁〖胶郏或者自己修復成可行解。反正框框在那里狸演。具體手段可以自己天馬行空發(fā)揮言蛇。
另一個比較實際的問題是：在最短路徑中并不知道染色體長度是多少，不錯严沥。大部分人還是用定長染色體去解決問題猜极，這樣性能低下。算法不直觀消玄。這時候可以使用變長染色體來解決跟伏。其實我建議不管何種情況，都設計變長染色體模式翩瓜。因為定長也是變長的一種特例受扳。使用變長可以解決任何問題。不管是tsp還是最短路徑問題兔跌。
還有一個編解碼問題勘高，就是把現(xiàn)實問題轉換成基因，這些問題都比較容易解決坟桅，最簡單的就是直接用數(shù)組下標表示华望。
