趙恒昌（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

基于移民策略與優(yōu)勢(shì)基因的遺傳算法的改進(jìn)

趙恒昌
（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

遺傳算法是由美國(guó)的Holland教授與1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》[1]中首先提出的。遺傳算法是一種進(jìn)化算法。它的具體定義，很多文章給了不同的解釋[2]?？墒枪J(rèn)的，遺傳算法的基本原理，是相同的，它借鑒了自然進(jìn)化論中“物競(jìng)天演,適者生存,不適者淘汰”的思想 ,在諸多工程領(lǐng)域得到了實(shí)效性的應(yīng)用。旅行商問(wèn)題的時(shí)間復(fù)雜度為O（n!），遺傳算法面對(duì)這類問(wèn)題，一般可以得到較優(yōu)的解。但是，隨著n的增多，遺傳算法也暴露出了諸多不足，過(guò)早收斂于局部解（表現(xiàn)不好的局部解），或者收斂太慢。

1　遺傳算法概述

遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按問(wèn)題所要求的個(gè)性選出一部分個(gè)體，同時(shí)也淘汰一部分個(gè)體，利用選出來(lái)的個(gè)體進(jìn)行雜交、變異等演化，產(chǎn)生新一代的種群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。與傳統(tǒng)的啟發(fā)式優(yōu)化搜索算法相比，遺傳算法的主要本質(zhì)特征在于群體搜索策略和簡(jiǎn)單的遺傳算子。

遺傳算法中，雜交、變異、選擇，方式多種多樣。文章的實(shí)驗(yàn)均采用了較為常規(guī)的方法。文章重點(diǎn)放在了尋找優(yōu)勢(shì)基因，由優(yōu)勢(shì)基拼接出優(yōu)秀個(gè)體，在結(jié)合移民策略來(lái)改進(jìn)遺傳算法。

經(jīng)典遺傳算法流程圖如圖1。

圖1　

2　旅行商問(wèn)題

旅行商問(wèn)題 （Travelling Salesman Problem，TSP）是組合數(shù)學(xué)中一個(gè)古老而又困難的問(wèn)題，它易于描述但至今尚未徹底解決，現(xiàn)已歸入所謂的NP完全問(wèn)題。經(jīng)典提法為:有一貨物推銷員要去若干個(gè)城市推銷貨物，從某個(gè)城市出發(fā),經(jīng)其余各城市至少一次,然后回到那個(gè)城市,選擇怎樣的行走路線,才能使總行程最短（各城市間距離為已知）[3]。

TSP問(wèn)題可以采用如下數(shù)學(xué)描述：

城市集合C（C_1，C_2，C_3，…，CN）；距離矩陣Distance（N*N），Distance（i，j）表示城市i與城市j之間的距離；要求找到一條訪問(wèn)路徑T（T（1），T（2），…，T （n）），T（i）表示第i個(gè)訪問(wèn)城市的編號(hào)。令f（T）最小。

TSP問(wèn)題實(shí)際上是一個(gè)優(yōu)化問(wèn)題。

3　針對(duì)經(jīng)典遺傳算法的改進(jìn)

在經(jīng)典遺傳算法中，變異率是固定的。大多數(shù)情況下，種群經(jīng)過(guò)多代更新以后，種群的素質(zhì)趨于一致，特別是種群中保留的精英群體，幾乎完全一樣，造成了種群的“近親繁殖”[4]。近親繁殖不利于后代個(gè)體的繼續(xù)完善，導(dǎo)致種群多樣性下降，這樣很可能導(dǎo)致算法收斂于一個(gè)較差的局解。為了改善這種不足，本文提出了移民策略。

移民策略：在種群進(jìn)化過(guò)程中，保留一定的比例（一般只有百分之幾）給“移民”。“移民”是指不是有上一代種群“繁殖”（上一代種群經(jīng)過(guò)雜交、變異、自然選擇產(chǎn)生的新一代）而來(lái)，而是由外部遷移而來(lái)，在本文中“移民”有隨機(jī)算法生成，然后加入種群。

在遺傳算法中，評(píng)價(jià)系統(tǒng)是基于個(gè)體的。在針對(duì)TSP問(wèn)題時(shí)，評(píng)價(jià)系統(tǒng)即是：訪問(wèn)所有城市，距離最短的順序。這樣，雖然極好地適應(yīng)了問(wèn)題的要求與目的，但是城市數(shù)量較多時(shí)，問(wèn)題的候選解空間是巨大的，極大地增加了尋找最優(yōu)解的難度。

經(jīng)過(guò)分析，每一個(gè)個(gè)體都是由一個(gè)一個(gè)的“基因”鏈接而成的。“基因”即是構(gòu)成個(gè)體的小的組成部分。針對(duì)不多的問(wèn)題，解的個(gè)體“基因”的含義也是多種多樣的。在TSP問(wèn)題中，本文采用的“基因”定義如下：一個(gè)緊密連接的城市訪問(wèn)順序。舉例來(lái)講，六個(gè)城市（城市編號(hào)依次為1，2，3，…6）的訪問(wèn)順序多種多樣，假設(shè)一個(gè)個(gè)體解為6 2 3 1 4 5，它的基因即是 “62”，“23”，“31”，“14”，“45”“56”六個(gè)基因。舉例來(lái)講基因“62”，就是旅行商在訪問(wèn)所有城市中，由城市6直接到達(dá)城市2的簡(jiǎn)單路徑。當(dāng)然基因的具體定義，雖然問(wèn)題以及目的的不同，自然也是千差萬(wàn)別。為了便于研究，本文采用了這種相對(duì)簡(jiǎn)單的定義。

基因優(yōu)勢(shì)：每個(gè)基因各有各自的優(yōu)勢(shì)，但是優(yōu)勢(shì)的評(píng)估是基于個(gè)體的。如果大量含有特定基因的個(gè)體，表現(xiàn)良好，可以認(rèn)為該基因?yàn)閮?yōu)勢(shì)基因；反之，如果大量含有這一基因的個(gè)體，表現(xiàn)糟糕，可以認(rèn)為該基因?yàn)榱觿?shì)基因。為了便于描述本文的數(shù)學(xué)公式，文章采用下面符號(hào)。

GeneAdvantage（i，j）表示基因（i，j）的優(yōu)劣，具體含義是包含該基因的個(gè)體的平均表現(xiàn)，在TSP問(wèn)題中即是訪問(wèn)完所有城市的距離的平均值。該值越小，說(shuō)明該基因優(yōu)勢(shì)越大。

C（i，j）包含基因（i，j）的個(gè)體的集合。

Number_C（i，j）包含基因（i，j）的個(gè)體集合的大小

基因拼接，基于優(yōu)勢(shì)基因本文提出了基因拼接的技術(shù)（或者基因合成，但是拼接一詞，更貼切本文的描述）?；驹砣缦拢?/p>

①城市均以數(shù)字（1-n）編號(hào)。初始隊(duì)列T為空，T為旅行商的訪問(wèn)順序；L為數(shù)字1-n的集合，L為旅行商下一個(gè)要訪問(wèn)的城市的集合。

②任意選擇一個(gè)城市作i為旅行商的起點(diǎn)城市，加入隊(duì)列T，同時(shí)L中減去i。

③選出T中最后加入的城市i，然后選出i與L中城市形成最優(yōu)的基因（i，j）的城市j，然后將j加入隊(duì)列T，同時(shí)把j從L中去除。

④如果L為空，輸出T；否則繼續(xù)執(zhí)行③。

基因拼接方法可以較經(jīng)典遺傳算法，迅速地求得較好地解。我們以美國(guó)48個(gè)城市的旅行商問(wèn)題（數(shù)據(jù)來(lái)源于網(wǎng)站TSPLIB，壓縮包att48.tsp.gz），為實(shí)驗(yàn)數(shù)據(jù)，以MATLAB 2015a為平臺(tái)，來(lái)闡述實(shí)踐結(jié)果。

經(jīng)典遺傳算法：種群個(gè)數(shù)2000，繁殖1000代，計(jì)算兩百萬(wàn)個(gè)候選解，耗時(shí)254秒，得到的最優(yōu)解：45218，旅行商路徑如圖2。

基因拼接算法：分析二十萬(wàn)個(gè)候選解，再合成1000個(gè)解，耗時(shí)35秒，得到最優(yōu)解：35974，旅行商路徑如圖3。

事實(shí)上的最優(yōu)解為33524，旅行商路徑如圖4。該數(shù)據(jù)由網(wǎng)站TSPLIB提供。

圖2　

圖3　

遺傳算法簡(jiǎn)單通用，具有很強(qiáng)的全局搜索能力。正因?yàn)榇?，遺傳算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。而大量數(shù)據(jù)表明遺傳算法局部搜索能力差，容易陷入早熟收斂：進(jìn)化中群體多樣性迅速下降，個(gè)體間的競(jìng)爭(zhēng)力度急劇下降，進(jìn)化能力基本喪失[5]。相關(guān)種群?jiǎn)栴}的研究，1989年Whitley提出，GA（Genetic Algorithm，即遺傳算法）最重要的兩個(gè)因素就是“種群多樣性”和選擇壓力[6]，本文主要從種群多樣性的角度出發(fā)，研究遺傳算法的改進(jìn)。本文實(shí)驗(yàn)數(shù)據(jù)，表明了基因拼接方法的優(yōu)勢(shì)，基因拼接方法是基于優(yōu)勢(shì)基因，而優(yōu)勢(shì)基因的獲得，需要在候選解空間中充分抽樣個(gè)體，統(tǒng)計(jì)后獲得。基于以上討論，本文對(duì)遺傳算法做了如下改進(jìn)，如圖5。

改進(jìn)后的算法：種群個(gè)數(shù)1000，繁殖300代；因?yàn)橐泼癫呗裕~外評(píng)估30萬(wàn)個(gè)個(gè)體?？偣灿?jì)算了110萬(wàn)個(gè)候選解，耗時(shí)175秒，得到最優(yōu)解：34374（與事實(shí)上的最優(yōu)解，有2%的誤差）。旅行商路徑如圖6。

4　結(jié)語(yǔ)

基因拼接的方法，可以在短時(shí)間內(nèi)拼接處較為優(yōu)秀的個(gè)體。把這些個(gè)體加入遺傳算法的種群中，極大地加速了遺傳算法的收斂速度，并且同時(shí)增大了種群的多樣性。本文中，遺傳算法的變異、雜交、選擇，都是采用了較為常規(guī)的方法。至于本文重點(diǎn)研究的優(yōu)勢(shì) “基因”，它們的合成與拼接，本文采用較為簡(jiǎn)單的方法，但這種方法有很多不足，諸如在拼接過(guò)程中，很可能舍棄了更具優(yōu)勢(shì)的基因。

圖4　

圖5　

圖6?。ㄗ顑?yōu)路線）

[1]HOLLAND J H.Adaptation in Natural and Artificial Systems:an Introductory Analysis with Applications to Biology，Control，and Artificial Intelligence[M].2nd.Cambridge:MIT Press[M]，1992.

[2]Jeff Heaton.Artificial Intelligence for Humans，Volume 2:Nature-Inspired Algorithms.Heaton Research，Inc[M]，May 28，2014.

[3]黃厚生.求解旅行商問(wèn)題的新方法研究[D]，2005，1.

[4]李軍.基于最優(yōu)基因的遺傳算法研究[D]，2007，4.

[5]崔珊珊.遺傳算法的一些改進(jìn)及其應(yīng)用[D]，2010，5.

[6]Darrell Whitley.The GENITOR Algorithm and Selection Pressure:Why Rank-Based Allocation of Reproductive Trials is Best.1989[J]

Genetic Algorithm;Immigration Policy;Gene Advantage;TSP;Permutations Optimization

Genetic Algorithm Improvement Based on Immigration and Better Genes

ZHAO Heng-chang
（College of Computer Science，Sichuan University，Chengdu，610065）

1007-1423（2016）07-0036-04

10.3969/j.issn.1007-1423.2016.07.008

趙恒昌（1988-），男，，山東新泰人，碩士，研究方向?yàn)槿斯ぶ悄?、最?yōu)化理論、算法設(shè)計(jì)與分析

2016-01-26

2016-02-26

遺傳算法在解決候選解空間巨大的問(wèn)題時(shí)，可以比較有效地找到最優(yōu)解或者次優(yōu)解。但是遺傳算法也存在諸多不足，例如收斂速度慢，早熟收斂?；谔囟ɑ虻膬?yōu)勢(shì)，構(gòu)想出基因拼接的方法；同時(shí)為了拓展算法的搜索空間和增加種群多樣性，改進(jìn)算法引入移民策略。以旅行商問(wèn)題（TSP）為例，實(shí)踐驗(yàn)證所提出的算法思想。

遺傳算法；移民策略；基因優(yōu)勢(shì)；旅行商問(wèn)題；排列優(yōu)化

Genetic algorithms dealing with problem with huge solution space of the candidate,can be more effective in finding an optimal solution or suboptimal solutions.But there are also many defects,such as slow convergence,premature convergence.Based on the advantages of spe-cific genes,creates gene-joint technique.In order to expand the search space and increase the diversity of the population,the improved algorithm introduced immigration policy.Takes the traveling salesman problem(TSP)as an example,to practice the algorithm thought.