基于均勻設(shè)計(jì)的遺傳算法求解旅行商問題【文獻(xiàn)綜述】

《基于均勻設(shè)計(jì)的遺傳算法求解旅行商問題【文獻(xiàn)綜述】》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、畢業(yè)論文文獻(xiàn)綜述計(jì)算機(jī)科學(xué)與技術(shù)基于均勻設(shè)計(jì)的遺傳算法求解旅行商問題引言：遺傳算法(Geneticalgorithms:GA)是由美國Michigan大學(xué)的JohnHolland教授在60年代提出的，它是一種自然適應(yīng)優(yōu)化方法，該算法是基于自然遺傳和自然優(yōu)選機(jī)理的尋優(yōu)方法[1]。所謂自然遺傳和自然優(yōu)選來自于達(dá)爾文的進(jìn)化論學(xué)說，該學(xué)說認(rèn)為在生物進(jìn)化過程中，任一動(dòng)植物經(jīng)過若干代的遺傳和變異，使之能夠適應(yīng)新的環(huán)境，是優(yōu)勝劣汰的結(jié)果，這種自然遺傳思想也適用于求解優(yōu)化問題。遺傳算法具有十分頑強(qiáng)的魯棒性，這是因?yàn)楸绕鹌胀ǖ膬?yōu)化搜索方法，它采用了許多

2、獨(dú)特的方法和技術(shù)，其中最為重要的是許多傳統(tǒng)的搜索方法都是單點(diǎn)搜索算法，即通過一些變動(dòng)規(guī)則，使問題的解從搜索空間中的當(dāng)前解(點(diǎn))移動(dòng)到另一解(點(diǎn))[1]。這種點(diǎn)對(duì)點(diǎn)的搜索方法，對(duì)于多峰分布的搜索空間常常會(huì)陷入局部的某個(gè)峰的優(yōu)解[1]。與此相反，遺傳算法是采用同時(shí)理群體中多個(gè)個(gè)體的方法，即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，更形象的說，遺傳算法是并行爬多個(gè)峰，這一特點(diǎn)使遺傳算法具有較好的全局搜索性能，減少了陷于局部優(yōu)解的風(fēng)險(xiǎn)[1]。因此遺傳算法的初始分布，即開始搜索前選擇的解空間的多個(gè)個(gè)體，對(duì)于算法收斂將是十分重要的[1]。如果初始分布過于

3、集中，就很可能使算法陷入局部最優(yōu)，因此初始種群的多樣性對(duì)算法的影響是很大的[1]。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)[1]：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果[1]。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算上用枚舉法很難求出最優(yōu)解。對(duì)這類復(fù)雜的問題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求滿

4、意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。670年代，我國在進(jìn)行航空試驗(yàn)的時(shí)候提出要用較少的試驗(yàn)次數(shù)來完成參數(shù)水平較多的試驗(yàn)，如何來解決這個(gè)問題，是當(dāng)時(shí)專家們的一個(gè)重要課題。通過對(duì)傳統(tǒng)試驗(yàn)的研究和鑒于別過提出的創(chuàng)新理論之后，王開泰教授和王元教授提出了均勻設(shè)計(jì)這個(gè)方法[2]。均勻設(shè)計(jì)能很好得解決在經(jīng)典遺傳算法中對(duì)參數(shù)設(shè)定的問題。首先，遺傳算法中需要確定的參數(shù)數(shù)目比較多，一般在3～5個(gè)左右，為

5、了測試出最佳的參數(shù)組合，往往需要在確定參數(shù)的取值范圍后，再劃分參數(shù)水平，若假定需要確定的參數(shù)有3個(gè)，參數(shù)水平有10個(gè)，那么，需要做的試驗(yàn)次數(shù)為3的10次方次，這個(gè)數(shù)目是非常驚人的，往往令人望而生畏。假如運(yùn)用均勻設(shè)計(jì)的方法來設(shè)計(jì)試驗(yàn)，一般只需要做10次左右，這將大大地減少了試驗(yàn)的次數(shù)，為試驗(yàn)節(jié)約了可觀的人力物力。目前均勻設(shè)計(jì)已經(jīng)在各大領(lǐng)域中得到了運(yùn)用，經(jīng)過不斷得發(fā)展和完善，將會(huì)取得更大的成就。1旅行商問題旅行商（TravelingSalesmanProblem，TSP）是指一名推銷員要到N個(gè)城市推銷貨物，從任意一個(gè)城市出發(fā)，經(jīng)過其余各城

6、市一次且僅僅一次，然后回到出發(fā)點(diǎn)，求其最短行程。該問題是組合數(shù)學(xué)與圖論中的一個(gè)古老而有名的NPComplete問題。旅行商(TSP)問題的數(shù)學(xué)語言描述如下:給出一個(gè)圖G=(V，E)，任意邊e∈E上有非負(fù)權(quán)值w(e)，尋找G的哈密頓回路C，使得回路的總權(quán)值w(c)=Σw(e)（e∈E(c)）最小。2均勻設(shè)計(jì)簡介20世紀(jì)70年代，計(jì)算機(jī)仿真試驗(yàn)設(shè)計(jì)（Designofcomputerexperiments）在那時(shí)是一個(gè)最有挑戰(zhàn)的課題[2]。雖然很多的傳統(tǒng)試驗(yàn)方法已經(jīng)獲得了很好應(yīng)用效果，但是沒有任何實(shí)驗(yàn)都適用的實(shí)驗(yàn)設(shè)計(jì)方法。特別是在一些復(fù)雜的

7、優(yōu)化問題中，需要考察得因素較多且變化范圍較大，從而要求每個(gè)因素有較多的水平，這類問題若用現(xiàn)在流行的試驗(yàn)設(shè)計(jì)方法（包括優(yōu)選法和正交設(shè)計(jì)），則需要做較多的試驗(yàn)，常使使用者望而生畏[2]。“均勻設(shè)計(jì)”是80年代由中國科學(xué)院數(shù)學(xué)所王元和方開泰教授將數(shù)論和多元統(tǒng)計(jì)分析相結(jié)合創(chuàng)立的一種新穎的試驗(yàn)方法，它是單純從均勻性原則出發(fā)的試驗(yàn)設(shè)計(jì)[3]。均勻設(shè)計(jì)的主要目的是從給定的樣本中采樣一些點(diǎn)，而這些點(diǎn)能夠均勻地分布，它是一種能適應(yīng)多因數(shù)、多水平實(shí)驗(yàn)的實(shí)驗(yàn)方法，它比以前的實(shí)驗(yàn)方法計(jì)算次數(shù)大大減少，提高了算法速度；其他的實(shí)驗(yàn)算法就是在實(shí)驗(yàn)范圍內(nèi)挑選出代表性

8、的實(shí)驗(yàn)點(diǎn)，從而導(dǎo)致搜索進(jìn)入某一集中區(qū)域得不到優(yōu)良的解，但均勻設(shè)計(jì)可以做到實(shí)驗(yàn)點(diǎn)在實(shí)驗(yàn)范圍內(nèi)均勻分布，6這樣使搜索范圍有很大提高[2]。均勻設(shè)計(jì)常用一個(gè)均勻矩陣U[D][M](D個(gè)水平即權(quán)值矢量，M個(gè)因素即目標(biāo)函數(shù))來實(shí)現(xiàn)