用gaaa求解tsp問題設(shè)計(jì)畢業(yè)論文(編輯修改稿)
2025-07-21 04:30 本頁面
【文章內(nèi)容簡介】 可以按一次或多次ESC鍵來選擇窗體。3 算法綜述GAAA算法是指遺傳算法(GA)和螞蟻算法(AA),但當(dāng)求解到一定程度時(shí),往往做大量的冗余迭代,對(duì)于系統(tǒng)中的反饋信息利用不夠,求解效率降低。而螞蟻算法由于初期數(shù)據(jù)對(duì)象隨機(jī)散布,螞蟻“拾起”、“放下”對(duì)象隨機(jī)運(yùn)動(dòng),形成有效聚類的時(shí)間很長,[6]。遺傳算法在搜索的初期(t0ta時(shí)間段)具有較高收斂速度,但達(dá)到ta之后效率降低。而螞蟻算法在搜索的初期(t0ta時(shí)間段)由于數(shù)據(jù)及自身運(yùn)動(dòng)的隨機(jī)性,使得搜索速度緩慢,但當(dāng)運(yùn)動(dòng)到一定時(shí)間后,效果顯著提升。遺傳算法和螞蟻算法融合(genetic algorithmant algorithm, GAAA)的基本思想是：基于遺傳算法的快速全局搜索能力和螞蟻算法的正反饋收斂機(jī)制，初期采用遺傳算法過程生成數(shù)據(jù)對(duì)象的初始聚類中心，后期利用螞蟻算法正反饋性能，優(yōu)勢(shì)互補(bǔ)。速度GAAAdVaatd0tbtatcte時(shí)間 遺傳算法和螞蟻算法的速度－時(shí)間曲線 遺傳算法綜述自然界始終是人類靈感的重要來源。仿生學(xué)直接模仿生物界的現(xiàn)象和原理，而另外一些研究方向則起源于對(duì)自然現(xiàn)象或過程的模擬，如控制論，人工神經(jīng)網(wǎng)絡(luò)，模擬退火算法，元胞自動(dòng)機(jī)等。遺傳算法（genetic algorithms）也是其中之一。早在20世紀(jì)50年代就有將進(jìn)化原理應(yīng)用于計(jì)算機(jī)科學(xué)的努力，但缺乏一種普遍的編碼方法，只能依賴于變異而非交配產(chǎn)生新的基因結(jié)構(gòu)。50年代末到60年代初，受一些生物學(xué)家用計(jì)算機(jī)對(duì)生物系統(tǒng)進(jìn)行模擬的啟發(fā)，Holland開始應(yīng)用模擬遺傳算子研究適應(yīng)性。在Bagley1967年關(guān)于自適應(yīng)下棋程序的論文中，他應(yīng)用遺傳算法搜索下棋游戲評(píng)價(jià)函數(shù)的參數(shù)集，并首次提出了遺傳算法這一術(shù)語。1975年Holland出版了遺傳算法歷史上的經(jīng)典著作《自然和人工系統(tǒng)中的適應(yīng)性》，系統(tǒng)闡述了遺傳算法的基本理論和方法，并提出了模式定理（schemata theorem），證明在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級(jí)增長，這里的模式是某一類字符串，其某些位置有相似性。同年，DeJong完成了他的博士論文《遺傳自適應(yīng)系統(tǒng)的行為分析》，將Holland的模式理論與他的計(jì)算試驗(yàn)結(jié)合起來，進(jìn)一步完善了選擇、交叉和變異操作，提出了一些新的遺傳操作技術(shù)。 遺傳算法的原理遺傳算法已有了許多發(fā)展，但一般來說，其基本過程是：首先采用某種編碼方式將解空間映射到編碼空間（可以是位串、實(shí)數(shù)、有序串、樹或圖，Holland最初的遺傳算法是基于二進(jìn)制串的，類似于生物染色體結(jié)構(gòu)，易于用生物遺傳理論解釋，各種遺傳操作也易于實(shí)現(xiàn)。另外，可以證明，采用二進(jìn)制編碼式，算法處理的模式最多。但是，在具體問題中，直接采用解空間的形式進(jìn)行編碼，可以直接在解的表現(xiàn)型上進(jìn)行遺傳操作，從而易于引入特定領(lǐng)域的啟發(fā)式信息，可以取得比二進(jìn)制編碼更高的效率。實(shí)數(shù)編碼一般用于數(shù)值優(yōu)化，有序串編碼一般用于組合優(yōu)化。），每個(gè)編碼對(duì)應(yīng)問題的一個(gè)解，稱為染色體或個(gè)體。一般通過隨機(jī)方法確定起始的一群個(gè)體，稱為種群，在種群中根據(jù)適應(yīng)值或某種競(jìng)爭(zhēng)機(jī)制選擇個(gè)體（適應(yīng)值就是解的滿意程度，可以由外部顯式適應(yīng)度函數(shù)計(jì)算，也可以由系統(tǒng)本身產(chǎn)生，如由協(xié)同演化時(shí)不同對(duì)策的博奕確定，或者由個(gè)體在群體中的存活量和繁殖量確定。），使用各種遺傳操作算子（包括雜交，變異，倒位等等）產(chǎn)生下一代（下一代可以完全替代原種群，即非重疊種群；也可以部分替代原種群中一些較差的個(gè)體，即重疊種群），如此進(jìn)化下去，直到滿足期望的終止條件。從上面的原理可以看出，從搜索角度，遺傳算法具有許多獨(dú)特的優(yōu)點(diǎn)：（l） 不必非常明確描述問題的全部特征，通用性和魯棒性強(qiáng)，能很快適應(yīng)問題和環(huán)境的變化；對(duì)領(lǐng)域知識(shí)依賴程度低，不受搜索空間限制性假設(shè)的約束，不必要求連續(xù)性、可導(dǎo)或單峰等。（2） 從多點(diǎn)進(jìn)行搜索，如同在搜索空間上覆蓋的一張網(wǎng)，搜索的全局性強(qiáng)，不易陷入局部最優(yōu)；具有隱并行性，非常適合于并行計(jì)算。 遺傳算法流程圖受自然免疫機(jī)制的啟發(fā),人們將遺傳算法應(yīng)用于各種優(yōu)化問題。一般來說,遺傳算法對(duì)待求解的優(yōu)化問題沒有特殊要求,目標(biāo)函數(shù)可以不連續(xù)、非可微、只要求問題是可計(jì)算的。算法中的抗原、抗體、抗體對(duì)抗原的親和力分別對(duì)應(yīng)于待求解問題的目標(biāo)函數(shù)、候選解、候選解對(duì)目標(biāo)函數(shù)的匹配程度。算法中抗體群體的進(jìn)化學(xué)習(xí),識(shí)別抗原的過程就待求解問題的優(yōu)化過程。初 始 種 群個(gè) 體 適 應(yīng) 評(píng) 價(jià)個(gè) 體 選 擇 運(yùn) 算染色體 交叉 運(yùn)算染色體 變異 運(yùn)算進(jìn)化結(jié)束?算 法 結(jié) 束YN 遺傳算法的程序流程圖 遺傳算法步驟由于遺傳算法的特性,使得其成為解決TSP問題的重要方法,其中,抗原對(duì)應(yīng)遍歷各城市的最短路徑,即TSP的最優(yōu)解?？贵w對(duì)應(yīng)為TSP的一條遍歷路徑。親和力對(duì)應(yīng)為抗體所決定的路徑與抗原的最短路徑的匹配程度。算法的基本步驟[7]:Step 1:隨機(jī)生成一個(gè)規(guī)模為N的初始群體Abs1。Step 2:計(jì)算抗體群體Abs1中的每個(gè)抗體對(duì)抗原的親和力。Step 3:選擇親和力較高的抗體形成群體Abs1。Step 4:計(jì)算Abs1中各個(gè)抗體的濃度。Step 5:依據(jù)親和力和濃度對(duì)Abs1中各個(gè)抗體的進(jìn)行克隆增擴(kuò),得到克隆抗體群體Abs2。親和力
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1