基于移民策略與優勢基因的遺傳算法的改進

趙恒昌（四川大學計算機學院，成都　610065）

基于移民策略與優勢基因的遺傳算法的改進

趙恒昌
（四川大學計算機學院，成都610065）

0　引言

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

1　遺傳算法概述

遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法。遺傳算法模擬自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按問題所要求的個性選出一部分個體，同時也淘汰一部分個體，利用選出來的個體進行雜交、變異等演化，產生新一代的種群，重復此過程，直到滿足某種收斂指標為止。與傳統的啟發式優化搜索算法相比，遺傳算法的主要本質特征在于群體搜索策略和簡單的遺傳算子。

遺傳算法中，雜交、變異、選擇，方式多種多樣。文章的實驗均采用了較為常規的方法。文章重點放在了尋找優勢基因，由優勢基拼接出優秀個體，在結合移民策略來改進遺傳算法。

經典遺傳算法流程圖如圖1。

圖1　

2　旅行商問題

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

TSP問題可以采用如下數學描述：

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

TSP問題實際上是一個優化問題。

3　針對經典遺傳算法的改進

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

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

在遺傳算法中，評價系統是基于個體的。在針對TSP問題時，評價系統即是：訪問所有城市，距離最短的順序。這樣，雖然極好地適應了問題的要求與目的，但是城市數量較多時，問題的候選解空間是巨大的，極大地增加了尋找最優解的難度。

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

基因優勢：每個基因各有各自的優勢，但是優勢的評估是基于個體的。如果大量含有特定基因的個體，表現良好，可以認為該基因為優勢基因；反之，如果大量含有這一基因的個體，表現糟糕，可以認為該基因為劣勢基因。為了便于描述本文的數學公式，文章采用下面符號。

GeneAdvantage（i，j）表示基因（i，j）的優劣，具體含義是包含該基因的個體的平均表現，在TSP問題中即是訪問完所有城市的距離的平均值。該值越小，說明該基因優勢越大。

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

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

基因拼接，基于優勢基因本文提出了基因拼接的技術（或者基因合成，但是拼接一詞，更貼切本文的描述）。基本原理如下：

①城市均以數字（1-n）編號。初始隊列T為空，T為旅行商的訪問順序；L為數字1-n的集合，L為旅行商下一個要訪問的城市的集合。

②任意選擇一個城市作i為旅行商的起點城市，加入隊列T，同時L中減去i。

③選出T中最后加入的城市i，然后選出i與L中城市形成最優的基因（i，j）的城市j，然后將j加入隊列T，同時把j從L中去除。

④如果L為空，輸出T；否則繼續執行③。

基因拼接方法可以較經典遺傳算法，迅速地求得較好地解。我們以美國48個城市的旅行商問題（數據來源于網站TSPLIB，壓縮包att48.tsp.gz），為實驗數據，以MATLAB 2015a為平臺，來闡述實踐結果。

經典遺傳算法：種群個數2000，繁殖1000代，計算兩百萬個候選解，耗時254秒，得到的最優解：45218，旅行商路徑如圖2。

基因拼接算法：分析二十萬個候選解，再合成1000個解，耗時35秒，得到最優解：35974，旅行商路徑如圖3。

事實上的最優解為33524，旅行商路徑如圖4。該數據由網站TSPLIB提供。

圖2　

圖3　

遺傳算法簡單通用，具有很強的全局搜索能力。正因為此，遺傳算法在各個領域得到了廣泛的應用。而大量數據表明遺傳算法局部搜索能力差，容易陷入早熟收斂：進化中群體多樣性迅速下降，個體間的競爭力度急劇下降，進化能力基本喪失[5]。相關種群問題的研究，1989年Whitley提出，GA（Genetic Algorithm，即遺傳算法）最重要的兩個因素就是“種群多樣性”和選擇壓力[6]，本文主要從種群多樣性的角度出發，研究遺傳算法的改進。本文實驗數據，表明了基因拼接方法的優勢，基因拼接方法是基于優勢基因，而優勢基因的獲得，需要在候選解空間中充分抽樣個體，統計后獲得。基于以上討論，本文對遺傳算法做了如下改進，如圖5。

改進后的算法：種群個數1000，繁殖300代；因為移民策略，要額外評估30萬個個體。總共計算了110萬個候選解，耗時175秒，得到最優解：34374（與事實上的最優解，有2%的誤差）。旅行商路徑如圖6。

4　結語

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

圖4　

圖5　

圖6　（最優路線）

[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]黃厚生.求解旅行商問題的新方法研究[D]，2005，1.

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

[5]崔珊珊.遺傳算法的一些改進及其應用[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-），男，，山東新泰人，碩士，研究方向為人工智能、最優化理論、算法設計與分析

2016-01-26

2016-02-26

遺傳算法在解決候選解空間巨大的問題時，可以比較有效地找到最優解或者次優解。但是遺傳算法也存在諸多不足，例如收斂速度慢，早熟收斂。基于特定基因的優勢，構想出基因拼接的方法；同時為了拓展算法的搜索空間和增加種群多樣性，改進算法引入移民策略。以旅行商問題（TSP）為例，實踐驗證所提出的算法思想。

遺傳算法；移民策略；基因優勢；旅行商問題；排列優化

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.