本文關(guān)鍵詞：問(wèn)題和解共同進(jìn)化的優(yōu)化方法的試探

  更多相關(guān)文章： 進(jìn)化算法 遺傳算法 問(wèn)題和解共同進(jìn)化 旅行商問(wèn)題 局部最優(yōu)問(wèn)題

【摘要】：隨著生物學(xué)與進(jìn)化算法不斷的研究與完善,研究人員研究總結(jié)發(fā)現(xiàn),自然界種群個(gè)體或物種之間,不但有著個(gè)體或物種之間為自然環(huán)境生存的競(jìng)爭(zhēng)關(guān)系,它們之間還有著很常見(jiàn)明顯的相互作用協(xié)作式一起共同進(jìn)化的規(guī)律。協(xié)同進(jìn)化,最早由Ehrlich和Raven提出,協(xié)同進(jìn)化是指各個(gè)種群間通過(guò)相互作用建立關(guān)聯(lián),并提高種群的性能的優(yōu)化。其實(shí),協(xié)同進(jìn)化也有兩種:協(xié)作型協(xié)同進(jìn)化和競(jìng)爭(zhēng)型共同進(jìn)化。在此基礎(chǔ)上,我們可以理解為物種的最終的進(jìn)化成的結(jié)果,其實(shí)是最終環(huán)境的演變過(guò)程中物種進(jìn)化的結(jié)果。環(huán)境不停的演變,最終演變成我們現(xiàn)在的環(huán)境,而現(xiàn)在的物種就是經(jīng)歷環(huán)境不斷的演變并自身在不斷進(jìn)化已經(jīng)適應(yīng)演變之后最終的當(dāng)前環(huán)境的結(jié)果。本文的問(wèn)題和解共同進(jìn)化算法,就是描述的就是這樣的一個(gè)方法。我們的問(wèn)題和解共同進(jìn)化算法里的問(wèn)題的進(jìn)化嚴(yán)格來(lái)講不是進(jìn)化而是演變,它類似于環(huán)境的演變,在這種環(huán)境變化的情況下,物種如何變化就是解的進(jìn)化,最終的解就是在最終的環(huán)境下的解,即環(huán)境演變伴隨著物種自身進(jìn)化最終的種群。在這里我們可以設(shè)置,使問(wèn)題演化并最終演化成我們希望的問(wèn)題,這就是問(wèn)題和解共同進(jìn)化。該方法在農(nóng)業(yè)應(yīng)用方面也有借鑒作用。當(dāng)前,遺傳算法很多的改進(jìn)都在致力于改進(jìn)它的收斂速度慢和早熟的問(wèn)題。而在遺傳算法局部最優(yōu)的這個(gè)問(wèn)題上,很多改善只是試圖提高算法的全局收索能力,從而使之減少陷入局部最優(yōu)的可能性。而本文的問(wèn)題和解共同進(jìn)化算法,旨在探討跳出遺傳算法局部最優(yōu)的問(wèn)題。在本文中,僅以旅行商問(wèn)題(Traveling Salesman Problem,TSP)來(lái)試探本文的問(wèn)題和解共同進(jìn)化算法。在傳統(tǒng)遺傳算法解決TSP問(wèn)題的基礎(chǔ)上,設(shè)計(jì)我們問(wèn)題和解共同進(jìn)化算法在TSP問(wèn)題上對(duì)遺傳算法局部最優(yōu)問(wèn)題的影響。本文的TSP問(wèn)題的設(shè)計(jì)是讓它從一個(gè)三維空間的TSP問(wèn)題逐漸演變成傳統(tǒng)的二維平面的TSP問(wèn)題,即在這里我們問(wèn)題的關(guān)鍵就是第三維坐標(biāo)Z的初始化與它在進(jìn)化過(guò)程中的變化規(guī)律的設(shè)置,使之以一種合理的方式逐漸演變成二維平面的TSP問(wèn)題的求解,這是本文的研究重點(diǎn),。本文問(wèn)題和解共同進(jìn)化算法將從三個(gè)方向探討問(wèn)題和解共同進(jìn)化算法對(duì)于跳出遺傳算法局部最優(yōu)問(wèn)題的影響:首先,是讓問(wèn)題演化規(guī)則相同即Z初始值和變化規(guī)律相同的情況下,從不同的數(shù)據(jù)量的經(jīng)典的已經(jīng)得到解決的TSP問(wèn)題探討,這里選取了四個(gè)TSPLIB里經(jīng)典的TSP問(wèn)題kroA100、att532、pr1002、pr2392進(jìn)行探討;其次,是從Z初始值不同,變化規(guī)律相同來(lái)探討對(duì)遺傳算法局部最優(yōu)問(wèn)題的影響;最后是從Z初始值相同,變化規(guī)律不同來(lái)探討對(duì)遺傳算法局部最優(yōu)問(wèn)題的影響。改進(jìn)后的算法得到的結(jié)果如果能比傳統(tǒng)的遺傳算法更優(yōu)的解、相似的解或者是比它稍差的解,總的來(lái)說(shuō)就是得到不一樣的跳動(dòng)很大的和傳統(tǒng)的不相同的解,因此問(wèn)題和解共同進(jìn)化算法可以使遺傳算法的解有所跳動(dòng)而不再是總處于一個(gè)相對(duì)來(lái)說(shuō)平穩(wěn)的局部解,即跳出遺傳算法局部最優(yōu)的問(wèn)題。
【關(guān)鍵詞】：進(jìn)化算法 遺傳算法 問(wèn)題和解共同進(jìn)化 旅行商問(wèn)題 局部最優(yōu)問(wèn)題
【學(xué)位授予單位】：南昌大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要3-5
• ABSTRACT5-9
• 引言9-11
• 第1章 進(jìn)化算法概述11-18
• 1.1 進(jìn)化規(guī)劃12-13
• 1.2 進(jìn)化策略13-14
• 1.3 遺傳算法14-18
• 1.3.1 遺傳算法的概念14-15
• 1.3.2 遺傳算法的特點(diǎn)15
• 1.3.3 遺傳算法的基本原理15-16
• 1.3.4 遺傳算法的步驟16-17
• 1.3.5 參數(shù)控制17
• 1.3.6 算法結(jié)束條件17-18
• 第2章 共同進(jìn)化算法18-24
• 2.1 協(xié)同進(jìn)化算法18-21
• 2.1.1 競(jìng)爭(zhēng)協(xié)同進(jìn)化19-20
• 2.1.2 協(xié)作共同進(jìn)化20-21
• 2.2 問(wèn)題和解共同進(jìn)化算法21-24
• 第3章 旅行商問(wèn)題24-29
• 3.1 旅行商推銷員問(wèn)題描述24
• 3.2 TSP的應(yīng)用24-25
• 3.3 TSP的進(jìn)展25
• 3.4 現(xiàn)有的TSP計(jì)算方法25-29
• 3.4.1 完全算法26-27
• 3.4.2 不完全算法27-29
• 第4章 問(wèn)題和解共同進(jìn)化遺傳算法在TSP問(wèn)題上的試探29-38
• 4.1 傳統(tǒng)遺傳算法解決TSP問(wèn)題主要思想29-34
• 4.1.1 編碼及適應(yīng)度函數(shù)29-30
• 4.1.2 選擇機(jī)制30
• 4.1.3 交叉策略30-33
• 4.1.4 變異技術(shù)33-34
• 4.2 問(wèn)題和解共同進(jìn)化遺傳算法在TSP問(wèn)題上的試探的主要思想34-38
• 4.2.1 TSP問(wèn)題的演變（或者是“進(jìn)化”）35-36
• 4.2.2 Z坐標(biāo)的初始值設(shè)置與變化函數(shù)設(shè)置36-37
• 4.2.3 編碼及適應(yīng)度函數(shù)37
• 4.2.4 選擇機(jī)制37
• 4.2.5 交叉策略37
• 4.2.6 變異技術(shù)37-38
• 第5章 實(shí)驗(yàn)結(jié)果及分析38-58
• 5.1 參照TSPLIB不同城市，改進(jìn)的方法與傳統(tǒng)的方法比較39-50
• 5.1.1 kroA100TSP問(wèn)題實(shí)驗(yàn)結(jié)果39-41
• 5.1.2 att532TSP問(wèn)題實(shí)驗(yàn)結(jié)果41-44
• 5.1.3 pr1002TSP問(wèn)題實(shí)驗(yàn)結(jié)果44-47
• 5.1.4 pr2392TSP問(wèn)題實(shí)驗(yàn)結(jié)果47-50
• 5.2 Z初始值不同，改進(jìn)的方法與傳統(tǒng)的方法比較50-54
• 5.3 Z如何趨近于零，，改進(jìn)的方法與傳統(tǒng)的方法比較54-58
• 第6章 結(jié)論與展望58-60
• 6.1 結(jié)論58-59
• 6.2 進(jìn)一步工作的方向59-60
• 致謝60-61
• 參考文獻(xiàn)61-64

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前6條

1 尤文堅(jiān);葉雪英;;粒子群和遺傳算法在農(nóng)業(yè)工程中的應(yīng)用[J];農(nóng)機(jī)化研究;2013年01期

2 呂躍進(jìn);劉南星;陳磊;;一種基于并行遺傳算法的粗糙集屬性約簡(jiǎn)[J];計(jì)算機(jī)科學(xué);2008年03期

3 羅彪;鄭金華;楊平;;基于定向爬山的遺傳算法[J];計(jì)算機(jī)工程與應(yīng)用;2008年06期

4 王德利,高瑩;競(jìng)爭(zhēng)進(jìn)化與協(xié)同進(jìn)化[J];生態(tài)學(xué)雜志;2005年10期

5 曹先彬,羅文堅(jiān),王煦法;基于生態(tài)種群競(jìng)爭(zhēng)模型的協(xié)同進(jìn)化[J];軟件學(xué)報(bào);2001年04期

6 馬良;旅行推銷員問(wèn)題的算法綜述[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2000年02期

本文編號(hào)：897600