基于遺傳算法原理優(yōu)化數(shù)據(jù)研究

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

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

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

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

二、算法原理

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

典型的遺傳算法CGA（Canonical Genetic Algorithm）通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題：考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(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)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串bi處，即求出最優(yōu)解。

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

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

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

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

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

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

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

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

遺傳算法還具有以下幾方面的特點(diǎn)：

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

作者簡(jiǎn)介：

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

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