摘 要：遺傳算法最初被研究的出發(fā)點不是為專門解決最優(yōu)化問題而設(shè)計的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。遺傳算法中的TSP問題即旅行商問題，又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。

關(guān)鍵詞：遺傳算法；TSP；人工智能

一、背景和國內(nèi)外發(fā)展現(xiàn)狀

遺傳算法被提出之后立即受到了各國學(xué)者的廣泛關(guān)注，有關(guān)遺傳算法的研究成果不斷涌現(xiàn)。從20世紀(jì)80年代中期起，遺傳算法和進(jìn)化計算到達(dá)一個研究高潮，以遺傳算法和進(jìn)化計算為主題的國際學(xué)術(shù)會議在世界各地定期召開。此外，進(jìn)化規(guī)劃年會（annual conference on Evolutionary programming， ACEP）每隔兩年召開一屆，它具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計算和建模方法的研究漸趨成熟。其他類型的各種會議，如以遺傳編程、進(jìn)化策略或進(jìn)化編程為主題的研討會也很頻繁。

二、算法原理

遺傳算法把問題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。

典型的遺傳算法CGA（Canonical Genetic Algorithm）通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：考慮對于一群長度為L的二進(jìn)制編碼bi，i=1，2，3，4，n；有bi{0，1}L（3-84）給定目標(biāo)函數(shù)f，有f（bi），并且f（bi）f（bi+1）求滿足下式max{f（bi）|bi{0，1}L}的bi。很明顯，遺傳算法是一種最優(yōu)化方法，它通過進(jìn)化和遺傳機理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個特定的串bi處，即求出最優(yōu)解。

長度為L的n個二進(jìn)制串bi（i=1，2，…，n）組成了遺傳算法的初解群，也稱為初始群體。在每個串中，每個二進(jìn)制位就是個體染色體的基因。根據(jù)進(jìn)化術(shù)語，對群體執(zhí)行的操作有三種：

選擇（Selection）這是從群體中選擇出較適應(yīng)環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也稱這一操作為再生（Reproduction）。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時也稱為非均勻再生（differential reproduction）。

交叉（Crossover）這是在選中用于繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個體。

變異（Mutation）這是在選中的個體中，對個體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因為1，產(chǎn)生變異時就是把它變成0，同理反之。

三、算法實現(xiàn)及分析

使用遺傳算法第一件事情就是確定染色編碼方式，它根據(jù)不同的問題模型使用不同編碼方式，有二進(jìn)制編碼也有整數(shù)編碼和浮點數(shù)編碼，面對TSP問題，我肯定選用整數(shù)編碼，因為很簡單，對于每個城市用一個整數(shù)來編號，例如有48個城市，就用0到47來標(biāo)識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為48，如：0，1，2，3，4…47就是一個染色體，它表達(dá)的意思就是旅行者從0號城市出發(fā)，依次訪問1，2，…47號城市再回到0號城市；遺傳算法的第二個要點就是評價函數(shù)，TSP的評價函數(shù)很簡單，就是染色體編碼表達(dá)的路徑總長度；最后很簡單，其實在這個模型中就是將0到47這48個數(shù)進(jìn)行全排列，從中找出最短的一條路徑（想想48個數(shù)全排列，然后比較）清楚了解了這些，就可以按照上面的遺傳算法框架來進(jìn)行編程了。

我們使用TSP問題依然來自于tsplib上的數(shù)據(jù)att48，這是一個對稱TSP問題，城市規(guī)模為48，其距離計算方法如下所示：

xd=x[i]-x[j]；

yd=y[i]-y[j]；

rij=sqrt[（xd*xd+yd*yd）/10.0]；

tij=nint（rij）；

if（tijelse dij=tij

遺傳算法還具有以下幾方面的特點：

（1）遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。

（2）遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。

（3）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應(yīng)用范圍大大擴展。

（4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。

（5）具有自組織，自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時，適應(yīng)度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

（6）此外，算法本身也可以采用動態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中自動調(diào)整算法控制參數(shù)和編碼精度，比如使用模糊自適應(yīng)法。

基本的遺傳算法是有很多不足的，如容易選入局部收斂，全局搜索能力不夠強，但是有很多可以改進(jìn)的地方，如交叉算子的設(shè)計、變異算子的設(shè)計、選擇策略等等，有關(guān)遺傳算法個人覺得作為一種智能啟發(fā)式搜索算法它甚至比別的普通算法（如動態(tài)規(guī)劃）理解起來還容易，而且它特別容易與別的算法相結(jié)合，設(shè)計新的混合算法。

參考文獻(xiàn)：

[1]鄭寒冰.基于混合遺傳算法的導(dǎo)頻優(yōu)化[J].電信科學(xué).2016（9）.

[2]趙禮峰.求解最短路徑問題的混合遺傳算法[J].計算機技術(shù)與發(fā)展.2016（9）.

作者簡介：

唐友（1979.05—），男，教授，高級工程師，碩士。

（作者單位：黑龍江財經(jīng)學(xué)院）