楊 剛，余 順

（安徽職業(yè)技術(shù)學(xué)院 信息工程系，合肥 安徽 230011）

融合模擬退火的遺傳算法研究與應(yīng)用
——以行程規(guī)劃問題為例

楊 剛，余 順

（安徽職業(yè)技術(shù)學(xué)院 信息工程系，合肥 安徽 230011）

遺傳算法具有較強(qiáng)的全局搜索能力，但容易陷入局部最優(yōu).把模擬退火算法的思想融入到遺傳算法中，在選擇、交叉和變異的過程中加入退火過程，并使用改進(jìn)后的算法求解行程規(guī)劃問題，實(shí)驗(yàn)結(jié)果證明設(shè)計(jì)的算法是有效的.

遺傳算法；模擬退火算法；行程規(guī)劃

0 引言

優(yōu)化算法的典型應(yīng)用場景是存在大量可能的解以至于無法對其進(jìn)行一一嘗試的情況.最簡單也是最低效的求解方法，莫過于去嘗試隨機(jī)猜測的上千個(gè)解，并從中找出最佳解來.而更有效的方法，則是以一種對題解可能有改進(jìn)的方式來對其進(jìn)行智能化修正.

近年常用于優(yōu)化問題的智能算法主要有遺傳算法與模擬退火算法兩種.這兩種智能算法有各自的優(yōu)缺點(diǎn).遺傳算法的全局搜索能力較強(qiáng)，由于其內(nèi)部具有并行性，因此可以方便地進(jìn)行分布式計(jì)算，從而得以快速地搜索出解空間中的全體解，而不會(huì)陷入局部最優(yōu)解的快速下降陷阱.但是遺傳算法的缺點(diǎn)也很明顯，即局部搜索能力較差，導(dǎo)致單純的遺傳算法比較費(fèi)時(shí)，在進(jìn)化后期搜索效率較低.在具體應(yīng)用中，如何在保留優(yōu)良個(gè)體的同時(shí)維持群體的多樣性，一直是遺傳算法中較難解決的問題[1].與遺傳算法相比，模擬退火算法的優(yōu)勢在于擺脫局部最優(yōu)解的能力，它能夠以隨機(jī)搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最優(yōu)解.但是，由于模擬退火算法對整個(gè)搜索空間的狀況了解不多，不便于使搜索過程進(jìn)入最有希望的搜索區(qū)域，使得模擬退火算法的運(yùn)算效率不高[2].本研究通過將模擬退火算法的思想融入遺傳算法中，并根據(jù)所要解決的問題對選擇算子、交叉算子和變異算子進(jìn)行了設(shè)計(jì)，增強(qiáng)了遺傳算法的全局收斂性.

1 問題描述

為來自不同地方去往同一地點(diǎn)的人們安排一次會(huì)面是一件極富挑戰(zhàn)性的事情.假設(shè)有一些畢業(yè)多年的同學(xué)想要來一次聚會(huì)，他們來自全國各地，并且他們希望在北京會(huì)面.他們將在同一天乘坐飛機(jī)到達(dá)并在機(jī)場集合.他們還將在同一天離開，而且他們將一同到達(dá)機(jī)場乘坐各自的航班.每天有許多航班從任何一個(gè)人所在的城市地飛往北京，每天也有許多航班從北京飛往任何一個(gè)人所在的城市.這些航班的價(jià)格和起飛時(shí)間也都不盡相同.現(xiàn)在需要幫助他們規(guī)劃他們?nèi)ズ突貢r(shí)的航班，使得總體成本最小.需要考慮兩個(gè)方面的成本，一是價(jià)格，一是等待時(shí)間.

設(shè)共有 n 個(gè)來自不同地方人 Pi(i=1，2，3，…，n)，用 Gi(i=1，2，3，…，n)表示每個(gè)人所在城市飛往北京的航班價(jià)格，用 Ci(i=1，2，3，…，n)表示從北京返回每個(gè)城市的航班價(jià)格，用 GTi(i=1，2，3，…，n)表示每個(gè)人到達(dá)北京的時(shí)間，用CTi(i=1，2，3，…，n)表示每個(gè)人離開時(shí)航班起飛的時(shí)間.為方便計(jì)算，GTi和CTi的值用某一個(gè)時(shí)間在當(dāng)天的分鐘數(shù)來表示.例如：早上的“00∶30”用30來表示，早上的“08∶30”用510來表示.同時(shí)把每1 min等同于1元錢.這樣就可把價(jià)格和時(shí)間聯(lián)系在一起.對問題分析后可得到以下公式：

所有人的航班的總價(jià)格：

所有人的等待時(shí)間：

因此，成本函數(shù)為：

F的值越小，則成本越低.

2 遺傳算法簡介

遺傳算法是受自然科學(xué)啟發(fā)的一種智能算法[1，2].遺傳算法的運(yùn)行過程是先隨機(jī)產(chǎn)生一組被成為初始種群的解，然后對種群中的所有個(gè)體進(jìn)行評價(jià)以及遺傳操作，生成下一代種群，然后繼續(xù)對種群中個(gè)體進(jìn)行評價(jià)，這個(gè)過程將不斷被重復(fù)，直到滿足結(jié)束條件為止.

在種群進(jìn)化的過程中，最重要的操作是選擇，選擇方法有很多，但都會(huì)有一個(gè)核心的思想，選擇適應(yīng)度值較高的個(gè)體.因此新的種群可以被稱為較優(yōu)解.新種群中的余下部分可通過修改種群中的個(gè)體產(chǎn)生.修改的方法主要有兩種.一種方法被稱為交叉.這種方法是從種群中隨機(jī)選取個(gè)體a和b，然后將他們按照某種方式進(jìn)行結(jié)合，形成一個(gè)新的個(gè)體c，或者a和b按照某種方式互換基因，形成兩個(gè)新的個(gè)體a'和b'.另外一種是較為簡單的方法，被稱為變異，通常的做法是隨機(jī)的選擇個(gè)體a，然后對a進(jìn)行微小的隨機(jī)改變以產(chǎn)生一個(gè)新的個(gè)體a'.

通過對較優(yōu)解進(jìn)行隨機(jī)的變異和交叉處理，將會(huì)構(gòu)造出一個(gè)新的種群，它的規(guī)模通常與初始種群相同.這一過程會(huì)一直重復(fù)進(jìn)行，直到到達(dá)指定的迭代次數(shù)，或者連續(xù)經(jīng)過數(shù)代后，個(gè)體的適應(yīng)度值變化很小或者不再改變，整個(gè)過程就結(jié)束了.

3 模擬退火算法簡介

模擬退火算法也是受自然科學(xué)啟發(fā)的智能算法[2，3].退火是指當(dāng)合金停止加熱后，溫度開始慢慢降低，一直到溫度不再改變的過程.在模擬退火算法開始時(shí)，需要設(shè)定兩個(gè)變量，一個(gè)用于表示溫度的變量，該變量的值非常大，一個(gè)用于表示解的變量，該變量的值是問題的一個(gè)隨機(jī)解.在算法的整個(gè)迭代過程中，每迭代一次，溫度就會(huì)以一定的系數(shù)逐漸變小，同時(shí)算法會(huì)隨機(jī)選中解中的某個(gè)位置，然后隨機(jī)變化.

在模擬退火算法的迭代過程中，如果新的解比當(dāng)前解更優(yōu)秀，則新的解成為當(dāng)前的解.不過如果新的解沒有當(dāng)前解優(yōu)秀的話，新的解也可能成為當(dāng)前解.這是為了避免陷入局部最優(yōu)的一種嘗試.在某些情況下，在能夠得到一個(gè)更優(yōu)的解之前轉(zhuǎn)向一個(gè)更差的解是很有必要的.模擬退火算法之所以管用，不僅僅因?yàn)樗偸墙邮芤粋€(gè)更優(yōu)的解，而且還因?yàn)樗谕嘶疬^程中的開始階段會(huì)接受表現(xiàn)較差的解.隨著迭代次數(shù)的增加，算法越來越不可能接收較差的解，因?yàn)榻邮茌^差解的概率越來越小，最后它將接受更優(yōu)的解.算法運(yùn)行過程中接受更差解的概率由下列公式給出：

式中，temperature表示溫度，highcost表示較優(yōu)的解，lowcost表示較差的解.因?yàn)閠emperature開始非常之高，指數(shù)將總是接近于0，所以概率幾乎為1.隨著temperature的遞減，較優(yōu)解和差解之間的差異越來越重要——差異越大，概率越低，因此該算法只傾向于稍差的解而不會(huì)是非常差的解.

4 混合遺傳算法與模擬退火算法求解行程規(guī)劃問題

遺傳算法的優(yōu)點(diǎn)是把握總體的能力較強(qiáng)，但它也有很明顯的缺點(diǎn)：局部搜索能力較差以及容易發(fā)生“早熟”現(xiàn)象.所以應(yīng)用遺傳算法求解行程規(guī)劃問題時(shí)，實(shí)驗(yàn)的結(jié)果并不能令人完全滿意.為達(dá)到較好的效果，本研究利用對遺傳算法進(jìn)行改進(jìn)，把模擬退火算法的思想融入進(jìn)來.具體求解過程如下：

1）編碼方式、適應(yīng)度函數(shù)和種群的初始化

①編碼方式

應(yīng)用遺傳算法求解問題時(shí)，首先要將問題的解映射成染色體，本研究采用實(shí)數(shù)編碼方式[4].用數(shù)字表示某個(gè)城市到北京（或北京到某個(gè)城市）的第幾號航班，如0表示某個(gè)城市到北京當(dāng)天的第1個(gè)航班，1表示第2個(gè)航班，依次類推.因?yàn)槊總€(gè)人都需要返航，所以染色體的長度是人數(shù)的兩倍.假設(shè)有5個(gè)來自不同城市的人，則一個(gè)解映射成一個(gè)染色體，表示為：1，4，3，3，7，5，6，1，0，9.

②適應(yīng)度函數(shù)

遺傳算法在對問題求解的過程中，考察個(gè)體的唯一指標(biāo)就是適應(yīng)度值.一般而言，適應(yīng)度值高，則說明個(gè)體好，反之說明個(gè)體壞，容易被淘汰.所以適應(yīng)度函數(shù)的選取是十分關(guān)鍵的，要能把個(gè)體的好壞區(qū)分開來.

在生成初始種群后，可以使用目標(biāo)函數(shù)式（3）求解每個(gè)染色體的成本.因?yàn)槌杀驹降驮胶?，但個(gè)體的適應(yīng)度值越高表示該個(gè)體越好.因此適應(yīng)度函數(shù)可由目標(biāo)函數(shù)做如下變換得到：

式中，C為一個(gè)較大的整數(shù).

③種群的初始化

隨機(jī)產(chǎn)生種群規(guī)模為PopSize的初始種群，為保證種群中個(gè)體的多樣性，種群中的個(gè)體不盡相同.

2）選擇退火算子

生成初始種群后，算法進(jìn)入迭代過程，首先是對初始種群中的個(gè)體進(jìn)行選擇，選擇的方法有多種，但不管采用什么方法，目的都是選出適應(yīng)度值較大的個(gè)體，從進(jìn)化的角度來說，適應(yīng)度值大的個(gè)體更容易生存.本研究設(shè)計(jì)的選擇過程如下：

①從種群中隨機(jī)選擇個(gè)體Zi和Zj，然后分別計(jì)算它們的適應(yīng)度值f（Zi）和f（Zj）；

②如果f（Zi）＜f（Zj），則個(gè)體Zi遺傳到下一代；否則，個(gè)體Zj以概率m遺傳到下一代；

③重復(fù)①，②操作直到選出TopSize個(gè)個(gè)體.TopSize小于PopSize.

3）交叉退火算子

經(jīng)過選擇操作，種群的規(guī)模由PopSize降為TopSize，現(xiàn)在需要對個(gè)體進(jìn)行修改以產(chǎn)生新的個(gè)體來擴(kuò)大種群規(guī)模.首先進(jìn)行的是交叉操作，本研究設(shè)計(jì)的交叉過程如下：

①隨機(jī)選取個(gè)體Zi和個(gè)體Zj；

②將個(gè)體Zi和Zj進(jìn)行交叉，生成新的個(gè)體Z'，計(jì)算個(gè)體適應(yīng)度f（Zi），f（Zj），f（Z'）；

③進(jìn)行退火操作，如果max[f（Zi），f（Zj）]＜f（Z'），則把個(gè)體Z'加入種群，否則，以概率m把個(gè)體Z'加入種群；

④循環(huán)步驟①，②，③，直到種群的規(guī)模達(dá)到PopSize.

4）變異退火算子

交叉操作之后是變異操作.本研究設(shè)計(jì)的變異過程如下：

①在種群中隨機(jī)選擇個(gè)體Z；

②在Z中隨機(jī)選擇3個(gè)位置，然后在該位置隨機(jī)選擇方向進(jìn)行改變以產(chǎn)生一個(gè)新個(gè)體Z'；

③計(jì)算個(gè)體適應(yīng)度值f（Z）和f（Z'）.如果f（Z'）＜f（Z），則用Z'代替Z；否則，以概率m接受Z'；

④隨機(jī)重復(fù)步驟①、②、③n次，n是一個(gè)比較小的整數(shù).

5）更新群體

選擇、交叉和變異產(chǎn)生了下一代種群，該種群將重復(fù)選擇、交叉和變異的過程.

6）結(jié)束條件

設(shè)定了以下兩個(gè)結(jié)束條件，當(dāng)滿足任意條件之一時(shí)，算法運(yùn)行結(jié)束.

①群體進(jìn)化的代數(shù)已經(jīng)達(dá)到設(shè)定的最大值；

②隨著種群的不斷進(jìn)化，最優(yōu)的適應(yīng)度值不再發(fā)生變化時(shí).

5 實(shí)驗(yàn)和結(jié)果

為了能夠驗(yàn)證混合算法的有效性和穩(wěn)定性，本研究通過數(shù)據(jù)實(shí)驗(yàn)對改進(jìn)的混合算法與傳統(tǒng)的遺傳算法進(jìn)行對比. 實(shí)驗(yàn)環(huán)境：CPU-INTER（R）Pentium（R）2 Dual CPU@2.4 GHz，內(nèi)存 3 GB；操作系統(tǒng)為 Windows 7（32位）；開發(fā)程序python 3.5.實(shí)驗(yàn)中假定有6個(gè)來自不同城市的人，每個(gè)城市和北京之間的航班數(shù)據(jù)如表1所示.

表1 航班時(shí)刻表

對算法的參數(shù)做如下設(shè)置：初始種群規(guī)模：40；初始溫度：500 000；降溫系數(shù)：0.985；退火終止溫度：0.1；最大進(jìn)化代數(shù)：500；變異概率：0.2.分別用基本遺傳算法和本研究提出的改進(jìn)算法進(jìn)行計(jì)算500次，結(jié)果如表2所示.從表2可以看出，本研究設(shè)計(jì)的遺傳退火算法與基本遺傳算法相比，可以更快速地尋找到最優(yōu)解，同時(shí)，所得到的解也比基本遺傳算法的解更優(yōu).

表2 基本遺傳算法與遺傳退火算法的運(yùn)行結(jié)果

6 結(jié)束語

遺傳算法是同時(shí)對問題的多個(gè)可能解進(jìn)行評價(jià)，因此運(yùn)行速度快，但容易陷入局部極優(yōu)，而且不容易跳出局部極優(yōu)，所以本研究把模擬退火算法的思想融入到遺傳算法中，幫助遺傳算法克服了傳統(tǒng)遺傳算法的早熟收斂問題，具有更強(qiáng)的通用性、穩(wěn)健性和精確性.實(shí)驗(yàn)結(jié)果表明，將遺傳退火算法應(yīng)用于行程規(guī)劃問題，能夠得到更優(yōu)的解，為這類問題提供了一種新的有效方法.

[1]楊元峰.基于模擬退火遺傳算法的多車場車輛調(diào)度問題的研究與應(yīng)用[D].蘇州：蘇州大學(xué)，2006.

[2]朱文堅(jiān)，陳東，劉建素.遺傳算法在多目標(biāo)優(yōu)化設(shè)計(jì)中的應(yīng)用研究[J].機(jī)械工程師，2001，（12）：7-9.

[3]申巍.基于模擬退火的混合遺傳算法在變電站選址中的應(yīng)用[D].保定：華北電力大學(xué)，2007.

[4]張晉，李冬黎，李平.遺傳算法編碼機(jī)制的比較研究[J].中國礦業(yè)大學(xué)學(xué)報(bào)，2002，31（6）：637-640.

The Application of Genetic Algorithm Fusing Simulated Annealing in Itinerary Planning Problem

YANG Gang,YU Shun
(Department of Information Engineering,Anhui Vocational College,Hefei,Anhui 230011,China)

Genetic algorithm has strong global search ability,but easy to fall into local optimum.In this paper,the simulated annealing algorithm thinking is incorporated into the genetic algorithm,and the annealing process joins the selection,crossover and mutation.The improved algorithm is used to solve the itinerary planning problem.The experimental results show that the algorithm is effective.

genetic algorithm;simulated annealing algorithm;itinerary planning

TP391

A

1673-1972（2017）06-0040-05

2017-10-17

2014年度安徽省質(zhì)量工程項(xiàng)目；計(jì)算機(jī)多媒體教學(xué)團(tuán)隊(duì)項(xiàng)目（2014jxtd076）

楊剛（1982-），男，安徽五河人，副教授，主要從事算法分析與設(shè)計(jì)和軟件工程研究.

（責(zé)任編輯 王穎莉）