用遺傳算法求解TSP問題.doc

《用遺傳算法求解TSP問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、用遺傳算法求解TSP問題遺傳算法（GeneticAlgorithm——GA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型，它是由美國Michigan大學(xué)的J.Holland教授于1975年首先提出的。J.Holland教授和它的研究小組圍繞遺傳算法進(jìn)行研究的宗旨有兩個：抽取和解釋自然系統(tǒng)的自適應(yīng)過程以及設(shè)計具有自然系統(tǒng)機(jī)理的人工系統(tǒng)。遺傳算法的大致過程是這樣的：將每個可能的解看作是群體中的一個個體或染色體，并將每個個體編碼成字符串的形式，根據(jù)預(yù)定的目標(biāo)函數(shù)對每個個體進(jìn)行評價，即給出一個適應(yīng)度值。開始時，總是隨機(jī)

2、的產(chǎn)生一些個體，根據(jù)這些個體的適應(yīng)度，利用遺傳算子——選擇（Selection）、交叉（Crossover）、變異（Mutation）對它們重新組合，得到一群新的個體。這一群新的個體由于繼承了上一代的一些優(yōu)良特性，明顯優(yōu)于上一代，以逐步向著更優(yōu)解的方向進(jìn)化。遺傳算法主要的特點在于：簡單、通用、魯棒性強(qiáng)。經(jīng)過二十多年的發(fā)展，遺傳算法已經(jīng)在旅行商問題、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)等領(lǐng)域得到成功的應(yīng)用。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點：1、遺傳算法以決策變量的編碼作為運算

3、對象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概念，可以模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子。2、遺傳算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。3、遺傳算法使用多個點的搜索信息，具有隱含并行性。4、遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。遺傳算法是基于生物學(xué)的，理解或編程都不太難。下面是遺傳算法的一般算法步驟：1、創(chuàng)建一個隨機(jī)的初始狀態(tài)初始種群是從解中隨機(jī)選擇出來的，將這些解比喻為染色體或基因，該種

4、群被稱為第一代，這和符號人工智能系統(tǒng)的情況不一樣；在那里，問題的初始狀態(tài)已經(jīng)給定了。2、評估適應(yīng)度對每一個解(染色體)指定一個適應(yīng)度的值，根據(jù)問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特性。3、繁殖(包括子代突變)帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代(后代產(chǎn)生后也將發(fā)生突變)。后代是父母的產(chǎn)物，他們由來自父母的基因結(jié)合而成，這個過程被稱為“雜交”。4、下一代如果新的一代包含一個解，能產(chǎn)生一個充分接近或等于期望答案的

5、輸出，那么問題就已經(jīng)解決了。如果情況并非如此，新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程，一代一代地演化下去，直到達(dá)到期望的解為止。5、并行計算非常容易將遺傳算法用到并行計算和群集環(huán)境中。一種方法是直接把每個節(jié)點當(dāng)成一個并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個節(jié)點遷移到另一個節(jié)點。另一種方法是“農(nóng)場主/勞工”體系結(jié)構(gòu)，指定一個節(jié)點為“農(nóng)場主”節(jié)點，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點作為“勞工”節(jié)點，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評估。6、術(shù)語說明由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個算

6、法中會用到很多生物遺傳學(xué)知識，以下是我們將會涉及到的一些術(shù)語：①染色體(Chromosome)染色體又可以叫做基因型個體(individuals),一定數(shù)量的個體組成了群體(population),群體中個體的數(shù)量叫做群體大小。②基因(Gene)基因是串中的元素，基因用于表示個體的特征。例如有一個串S＝01234，則其中的1，0，2，3這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。①基因地點(Locus)基因地點在算法中表示一個基因在串中的位置稱為基因位置(GenePosition)，有時也簡稱基因位?；?/p>

7、位置由串的左向右計算，例如在串S＝12043中，0的基因位置是3。②基因特征值(GeneFeature)在用串表示整數(shù)時，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8?！贿^本程序的基因無特征值；③適應(yīng)度(Fitness)各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù).這個函數(shù)是計算個體在群體中被使用的概率。遺傳算法中，針對三種遺傳算子可進(jìn)行如下

8、的遺傳操作。一、選擇算子從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫做選擇。選擇算子又叫再生算子（ReproductionOperator）。選擇的目的是把優(yōu)化的解直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子