一種改進(jìn)遺傳算法及其在TSP問(wèn)題中的應(yīng)用

1、遺傳算法1,2是由教授于年首先提出John H.Holland 1975來(lái)的。這種算法是受達(dá)爾文的生物進(jìn)化論啟發(fā)而創(chuàng)建的,是基于生物進(jìn)化中自然選擇、適者生存和物種遺傳思想的搜索算法。它是一種非數(shù)值并行優(yōu)化算法。近年來(lái),遺傳算法在解決連續(xù)變量的函數(shù)最優(yōu)化問(wèn)題和離散變量的組合最優(yōu)化問(wèn)題時(shí)所表現(xiàn)出的魯棒性、全局最優(yōu)性、隱含并行性和自適應(yīng)性而使其成為目前應(yīng)用較為廣泛的一種智能優(yōu)化方法1,2。但在傳統(tǒng)的遺傳算法中1,算法的收斂速度與問(wèn)題解的質(zhì)量是影響算法尋優(yōu)性能的一對(duì)主要矛盾。針對(duì)上述矛盾,我們提出了一種改進(jìn)現(xiàn)有尋優(yōu)性能的綜合控制策略:GA (1雜交、變異的并行處理;基于適應(yīng)值密度的變異操作;(2 自調(diào)

2、整父代遷移策略與父代與子代競(jìng)爭(zhēng)策略。并通過(guò)求(3解問(wèn)題驗(yàn)證了算法的有效性。TSP 遺傳算法簡(jiǎn)介1 設(shè)待優(yōu)化的函數(shù)為,是一個(gè)向量,它是所有的可能f(xx 的取值構(gòu)成的該優(yōu)化問(wèn)題的變量空間。首先,由構(gòu)造出f(x一個(gè)適應(yīng)值函數(shù),該適應(yīng)值函數(shù)必須滿足其下面g(x=Ff(x兩個(gè)條件:的值域g(xV R + (R +表示全體非負(fù)實(shí)數(shù)的集合;在取得最優(yōu)值的點(diǎn)時(shí)取得最大值。g(x遺傳算法的實(shí)現(xiàn)步驟如下1,2:確定遺傳算法的參數(shù):種群大小,交叉概(1 POPSIZE 率P c ,變異概率 P m 。初始化:隨機(jī)產(chǎn)生一個(gè)規(guī)模為的初始種(2 POPSIZE 群,其中每個(gè)個(gè)體為二進(jìn)制位串的形式。并計(jì)算每個(gè)個(gè)體的適應(yīng)值

3、 Gi 。雜交:從種群中隨機(jī)選擇兩個(gè)染色體,按一定的雜(3 交概率P c 進(jìn)行基因交換,交換的位置隨機(jī)產(chǎn)生。變異:從種群中隨機(jī)選擇一個(gè)染色體,按一定的變(4 異概率 Pm 進(jìn)行基因變異。繁殖:計(jì)算當(dāng)前代每個(gè)個(gè)體的適應(yīng)值;根據(jù)其相對(duì)(5 適應(yīng)值,計(jì)算每個(gè)個(gè)體(也即染色體的再生次數(shù),并進(jìn)行繁殖操作。繁殖后保持種群個(gè)數(shù)不變。POPSIZE 如果滿足停止規(guī)則,則返回當(dāng)前代適應(yīng)值最高的個(gè)(6 體所對(duì)應(yīng)的變量空間的點(diǎn),作為優(yōu)化的結(jié)果;否則,回到x 繼續(xù)繁衍下去。(3遺傳算法研究的主要目標(biāo)是既要使算法的質(zhì)量提高,又要求算法具有高的計(jì)算效率。一方面,由于遺傳算法是一種隨機(jī)搜索,所以好的解往往需要大的計(jì)算量;另

4、一方面,收斂速度高的算法通常導(dǎo)致早熟,使解的質(zhì)量降低。在傳統(tǒng)的中,主要通過(guò)變異率來(lái)調(diào)節(jié)收斂速度和解的質(zhì)量之間的GA 矛盾3。變異率太小,則算法容易陷入局部最優(yōu)值,導(dǎo)致早熟,使解的質(zhì)量降低;反之,變異率太大,則遺傳算法退化為隨機(jī)搜索法。因此,我們針對(duì)遺傳算法的演化步驟,從多方面入手,提出了一種改進(jìn)遺傳算法的綜合控制策略。改進(jìn)遺傳算法的控制策略2 好的算法使計(jì)算效率和解的質(zhì)量之間的平衡。可以從遺傳算法的選擇操作來(lái)理解收斂速度與解的質(zhì)量間的關(guān)系。從個(gè)體選擇方面來(lái)講,高的收斂速度通常通過(guò)采用高選擇壓力,即給予當(dāng)前代中的具有較高適應(yīng)值的個(gè)體較高的再生概率來(lái)實(shí)現(xiàn)。另一方面,由于群體規(guī)模不變,使得當(dāng)前代中的

5、具有較低適應(yīng)值的個(gè)體降低了群體中個(gè)體的信息含量,使算法搜索新解區(qū)域的能力降低,即降低了算法搜索全局最優(yōu)解的能力。因此,容易導(dǎo)致早熟收斂。既要使算法有較快的收斂速度,又要獲得令人滿意的解。我們提出的改進(jìn)遺傳算法從以下幾方面對(duì)傳統(tǒng)進(jìn)行了改進(jìn)。GA 雜交、變異的并行處理2.1 傳統(tǒng)的計(jì)算結(jié)構(gòu)模擬生物的遺傳進(jìn)化過(guò)程,即采用 GA 一種改進(jìn)遺傳算法及其在問(wèn)題中的應(yīng)用TSP 陳斌,徐華中(武漢理工大學(xué)自動(dòng)化學(xué)院,武漢430070摘要: 傳統(tǒng)遺傳算法的收斂速度與問(wèn)題解的質(zhì)量是影響算法尋優(yōu)性能的一對(duì)主要矛盾。文章針對(duì)上述矛盾,提出了改進(jìn)遺傳算法的控制策略雜交、變異的并行處理、基于適應(yīng)值密度的變異操作、自調(diào)整父

6、代遷移策略和父代與子代競(jìng)爭(zhēng)策略。并應(yīng)用于問(wèn)題中,驗(yàn)證了算法TSP 的有效性。關(guān)鍵詞:遺傳算法;改進(jìn)遺傳算法;控制策略;旅行商問(wèn)題An Improved Genetic Algorithm and Its Application in TSP,CHEN Bin XU Huazhong,(School of Automation ,Wuhan University of Technology Wuhan 430070【】Abstract The convergence speed of genetic algorithm and the quality of problem result are

7、the main inconsistency which affects the performance of GA.The paper proposes the control strategies of improved GA,which are parallel operation of crossover and mutation, mutation based on the density of fitness, the adaptive migration of father generation and competition of father generation and f

8、ilial generation. Furthermore, its efficiency is shown by an application in TSP.【】Key words Genetic algorithm; Improved genetic algorithm; Control strategy; Traveling salesmam problem第28卷第9期Vol.28 9計(jì)算機(jī)工程Computer Engineering2002年9月 September 2002人工智能及識(shí)別技術(shù) 中圖分類號(hào): TP301.6文章編號(hào):10003428(200209 009003文獻(xiàn)標(biāo)識(shí)

9、碼:A90 串行處理結(jié)構(gòu)雜交、變異再進(jìn)行選擇。這種串行算子操作方式存在弊端:對(duì)雜交后的個(gè)體進(jìn)行變異計(jì)算,有可能破壞經(jīng)雜交后所產(chǎn)生的較優(yōu)個(gè)體,從而影響收斂速度。雖然目前大多數(shù)改進(jìn)的遺傳算法都是采用自調(diào)整雜交率和變異率來(lái)解決交叉與變異算子的協(xié)調(diào)問(wèn)題,但是串行結(jié)構(gòu)使交叉和變異具有較強(qiáng)的耦合性,因此有時(shí)用此種控制策略所達(dá)到的效果并不十分理想。要提高的尋優(yōu)性能,就要改變傳統(tǒng)的GA GA 計(jì)算結(jié)構(gòu)。將傳統(tǒng)的的串行處理結(jié)構(gòu)改為雜交、變異算GA 子分別對(duì)父代進(jìn)行操作。這樣,既可以充分保留父代個(gè)體的好基因模式、保持雜交尋優(yōu)的速度,又可降低變異算子的破壞力,同時(shí)保證種群的多樣性,從而提高的尋優(yōu)性能。GA 基于適應(yīng)

10、值密度的變異操作2.2 眾所周知,存在早熟的問(wèn)題,主要原因是由于一種GA 被稱為超級(jí)個(gè)體的現(xiàn)象存在""4,即當(dāng)種群進(jìn)化到某一代時(shí),在種群中某個(gè)個(gè)體的適應(yīng)值遠(yuǎn)遠(yuǎn)大于其他任何個(gè)體的適應(yīng)值,因?yàn)閭€(gè)體被選中復(fù)制的概率與其適應(yīng)值有關(guān),這樣就會(huì)造成子代中許多個(gè)體來(lái)自于同一祖先,從而彼此在基因模式上近似,中的雜交和選擇操作失效。為了算法跳出早GA 熟,當(dāng)某代中所有的個(gè)體集中在一起時(shí),取基因突變的位數(shù)為普通基因突變位數(shù)通常為或位的倍。這樣,就能(1234隨機(jī)、獨(dú)立地產(chǎn)生許多新個(gè)體,從而使整個(gè)種群脫離早熟。為判斷某代中所有個(gè)體的集中程度,采用基于適應(yīng)值密度的方法。首先,對(duì)適應(yīng)值密度下個(gè)定義。

11、適應(yīng)值密度。D= 其中參數(shù)的范圍為,通常取值為。010.8當(dāng)適應(yīng)值密度小于預(yù)先設(shè)定的閾值因子時(shí),說(shuō)明該代中個(gè)體不是很集中,則采用普通基因突變位數(shù)進(jìn)行突變。反之,當(dāng)適應(yīng)值密度大于預(yù)先設(shè)定的閾值因子時(shí),說(shuō)明該代中個(gè)體很集中,則采用多位基因突變,以產(chǎn)生許多獨(dú)立、隨機(jī)的新個(gè)體,增加解空間的搜索范圍。自調(diào)整父代遷移策略與父代與子代競(jìng)爭(zhēng)策略2.3 遺傳算法的遷移策略也將影響到個(gè)體的多樣性。遺傳算法的個(gè)體遷移操作方式體現(xiàn)了自然界父代與子代之間的繼承與相互競(jìng)爭(zhēng)的關(guān)系。這種普遍的生物現(xiàn)象,在物種的進(jìn)化過(guò)程中產(chǎn)生了具有廣泛適應(yīng)性的魯棒性結(jié)構(gòu)。由的算法可GA 以看出,個(gè)體的遷移策略是算法必需的一個(gè)重要環(huán)節(jié)5。遺傳算

12、法的性能在很大程度上依賴于個(gè)體遷移策略,也就是依賴于如何在每一代中選擇被替換的個(gè)體來(lái)提高算法的尋優(yōu)性能。其實(shí)質(zhì)是怎樣既要保留進(jìn)化過(guò)程中父代個(gè)體具有的好基因模式,又要用子代中產(chǎn)生的個(gè)體所具有的更有效的新基因模式來(lái)替換父代中已不再有生命力個(gè)體中的舊基因模式。改進(jìn)遺傳算法的算法流程如圖所示,由圖可以看出,11由于采用并行的雜交操作和變異操作,使得如何確定父代的遷移策略以及父代與子代的競(jìng)爭(zhēng)策略顯得尤為重要。如果在父代遷移策略中采用遷移固定數(shù)量的父代,然后與子代進(jìn)行競(jìng)爭(zhēng)。實(shí)際上采用這種策略忽略了遺傳算法優(yōu)化的動(dòng)態(tài)性,也就是說(shuō),遺傳算法每一代對(duì)解的優(yōu)化程度是不一樣的。與父代相比,具有有效基因模式的個(gè)體數(shù)量

13、也是隨著進(jìn)化的過(guò)程不斷變化。遷移固定數(shù)量的父代,導(dǎo)致?lián)碛休^多好的基因模式的群體中,有些個(gè)體擁有的好的基因模式的信息被淘汰掉,降低了算法的尋優(yōu)性能。自調(diào)整父代遷移策略具體分為兩步分別求出雜交子:(1代和變異子代平均適應(yīng)值C rossFitness avg 和MutateFitness avg ;取兩者中的較大值并乘以閾值因子一般取(2(0.90-1.10,得到自調(diào)整適應(yīng)值的閾值×AdaptFitness=Max( C rossFitness avg , MutateFitness avg 選擇大于自調(diào)整適應(yīng)值的父代進(jìn)入父代較優(yōu)染AdaptFitness 色體庫(kù)中,以準(zhǔn)備與雜交子代和變異

14、子代共同競(jìng)爭(zhēng)進(jìn)入新一代子代。與遷移固定數(shù)量的父代策略相比,自調(diào)整父代遷移策略遷移的父代的數(shù)目隨著種群的進(jìn)化而動(dòng)態(tài)變化。如果子代的平均適應(yīng)值通過(guò)雜交或變異提高得很多,那么父代染色體庫(kù)中保留較少父代。相反,如果子代的平均適應(yīng)值通過(guò)雜交或變異提高得較少,那么父代染色體庫(kù)中保留較多父代。這樣,此策略增強(qiáng)了算法的尋優(yōu)性能。由改進(jìn)遺傳算法的算法流程看出,新的子代是由父代較優(yōu)染色體庫(kù)中的全部個(gè)體、雜交子代個(gè)體和變異子代個(gè)體組成。因此,新的子代中保留父代中具有有效模式的優(yōu)秀個(gè)體,又產(chǎn)生了經(jīng)過(guò)雜交和變異后產(chǎn)生的具有有效模式的優(yōu)秀個(gè)體。但是,由于雜交概率和變異概率不等于,則雜交子1代和變異子代中一定有父代中沒(méi)有參

15、加雜交和變異的較優(yōu)個(gè)體,為了保證新的子代在進(jìn)行賭輪盤選擇后群體的多樣性,增大解的搜索空間,避免早熟,則一定要限制父代中較好個(gè)體在新的子代中出現(xiàn)的次數(shù),因此我們采用父代與子代競(jìng)爭(zhēng)策略。父代與子代競(jìng)爭(zhēng)策略具體分為兩步:比較雜交子代(1的個(gè)體與父代較優(yōu)染色體庫(kù)中的個(gè)體,與父代較優(yōu)染色體庫(kù)中相同的雜交子代的個(gè)體不進(jìn)入新的子代;同樣的策(2 略,與父代較優(yōu)染色體庫(kù)中相同的變異子代的個(gè)體也不進(jìn)入新的子代。所以,新的子代是由父代較優(yōu)染色體庫(kù)中的全部個(gè)體,雜交子代的部分個(gè)體和變異子代的部分個(gè)體所組成。91POPSIZEMaxfitnessFitness Maxfitness m種群大小*(µ圖1 改

16、進(jìn)遺傳算法的算法流程圖用改進(jìn)遺傳算法求解旅行商問(wèn)題3 (TSP問(wèn)題描述3.1 TSP 問(wèn)題也稱旅行商問(wèn)題、貨郎擔(dān)問(wèn)題TSP 6。該問(wèn)題是尋找一條最短的遍歷個(gè)城市的路徑,也就是說(shuō)搜索城市集合n 中的元素代表對(duì)個(gè)城市的編C= (C n 號(hào)的一個(gè)排列,使得W 取最小值,式中d (W i ,W i+1代表城市 W i 到W i+1的距離。這是 一個(gè)典型的優(yōu)化組合問(wèn)題,已被證明屬于 NP(nondetermini-完全問(wèn)題,即沒(méi)有確定的算法能在多項(xiàng)式時(shí)stic polynomial間內(nèi)得到問(wèn)題的解。對(duì)個(gè)城市而言,可能的路徑總數(shù)為n。隨著數(shù)的增加,路徑數(shù)將按數(shù)率急劇增長(zhǎng),即所謂n!/2 n n 的指數(shù)爆炸

17、。以為例,即使用每秒一億次的計(jì)算機(jī)按""n=20窮舉搜索法求解,也需年。因此,任何能使求解此問(wèn)題350簡(jiǎn)化的方法,在學(xué)術(shù)界均予以高度的重視。它是一個(gè)經(jīng)典的人工智能問(wèn)題。目前比較好的求解方法有反饋神經(jīng)網(wǎng)絡(luò)法和遺傳算法。用改進(jìn)遺傳算法的綜合控制策略求解問(wèn)題。TSP 算法描述3.2 我們以中國(guó)旅行商問(wèn)題(CTSP6為所需解決的問(wèn)題,按以下步驟進(jìn)行。編碼:直接采用城市在路徑中的相當(dāng)位置來(lái)表示。(1 例如,染色體,它表示從城市出發(fā),先到達(dá)R=0538*城市,再到城市,再到城市,最后從城市返回。5314對(duì)應(yīng)于中國(guó)旅行商問(wèn)題,編碼從開始,到結(jié)束。整個(gè)染030色體長(zhǎng)度為。31確定適應(yīng)值函數(shù)

18、:取每條旅行路線的總行程的倒(2 g(x數(shù)為適應(yīng)值,則適應(yīng)值越小,方案越優(yōu)。確定初始化群體:設(shè)群體規(guī)模為。我們?nèi)?3 POPSIZE 個(gè)。先用貪婪法確定個(gè)個(gè)體,這個(gè)個(gè)體的起點(diǎn)城市分603131別是,。經(jīng)過(guò)貪婪法產(chǎn)生的個(gè)體在一定程0122930度上使得初始群體具有有效的基因模式,有利于算法提高尋優(yōu)能力,剩余的個(gè)體則隨機(jī)產(chǎn)生。雜交算子:我們采用由提出的算子(4 Davis OX 7通過(guò)從一個(gè)親體中挑選一個(gè)子序列旅行并保存另一個(gè)親體的城市相對(duì)次序來(lái)構(gòu)造后代。變異算子:對(duì)于基本的變異算子有倒置、插(5 TSP 入、移位、互換等。我們采用互換變異算子。即在染色體中隨機(jī)產(chǎn)生兩個(gè)位置,將這兩個(gè)位置上的基因互

19、換即可,也即互換基因所對(duì)應(yīng)的城市。在小于適應(yīng)值密度的閾值時(shí),每個(gè)染色體進(jìn)行次基因互換操作。在大于適應(yīng)值密度的閾值2時(shí),每個(gè)染色體進(jìn)行次基因互換操作。6參數(shù)選擇:雜交概率(6 P c 取,變異概率0.9P m 取。一0.8般而言,P m 取值范圍。但是由于改進(jìn)的遺傳算法0.0050.01雜交和變異采用并行處理,這樣一來(lái),突變不再破壞遺傳和雜交的尋優(yōu)結(jié)果,因此變異率可取很大,使算法可以覆蓋廣泛的解空間。適應(yīng)值密度閾值因子取。自調(diào)整適應(yīng)值0.7閾值因子取。0.8仿真結(jié)果3.3 我們用對(duì)中國(guó)旅行商問(wèn)題采用改進(jìn)遺傳算法和VC+6.0遺傳算法分別進(jìn)行了仿真。仿真實(shí)驗(yàn)分為組,每組都獨(dú)立4執(zhí)行次,每組所迭代的

20、次數(shù)分別為次,次,5100020003000次,次。5000首先定義衡量算法的標(biāo)準(zhǔn)為:相對(duì)距離(本次進(jìn)化的=最優(yōu)解-已知最優(yōu)解/已知最優(yōu)解為。每組的相15404km 對(duì)距離為獨(dú)立執(zhí)行次所得到的平均值。5仿真實(shí)驗(yàn)的結(jié)果如表所示。1表仿真實(shí)驗(yàn)結(jié)果1 第1組第2組第3組第4組簡(jiǎn)單遺傳算法0.25660.24030.23970.2397改進(jìn)遺傳算法0.08210.03240.00820.0006從實(shí)驗(yàn)結(jié)果可以看到,采用了改進(jìn)遺傳算法的綜合控制策略較簡(jiǎn)單的遺傳算法在收斂速度上有明顯的提高,使解空間很好地脫離早熟,并且得到了已知的最優(yōu)解。因此,基于改進(jìn)的遺傳算法對(duì)解決復(fù)雜的非線性規(guī)劃問(wèn)題具有較好的穩(wěn)定性、

21、收斂性和精確性。結(jié)論4 本文分析了傳統(tǒng)在解決問(wèn)題時(shí)存在的不足,即傳統(tǒng)GA 的收斂速度和對(duì)問(wèn)題解空間覆蓋能力之間存在相互制約GA 的關(guān)系。這種制約關(guān)系使傳統(tǒng)在處理復(fù)雜非線性規(guī)劃問(wèn)GA 題時(shí),難以取得優(yōu)良的性能。針對(duì)這一矛盾,本文提出的改進(jìn)遺傳算法的綜合控制策略不僅提高了遺傳算法的收斂速度,而且使得求解質(zhì)量顯著提高。參考文獻(xiàn)1 Michalewicz Z. Genetic Algorihms+Data Structures=Evolution Progr- ams.Beijing: Science Publishing House,20002 Liu Yong, Tang Lishan, Chen

22、 Yuping. Non-digital Parallel Algorithms. Beijing: Science Publishing House,19973 Bhandart D, Muthy C A. Genetic Algorithm with Elitist Model and Its Convergence. International Journal of Pattern Recognition and Artificial Intelligence,1996, 10(64 Potts J C, Gkddens T D, Yadav S B. The Development and Eva