北京工商大學(xué)畢業(yè)論文（設(shè)計(jì)）開(kāi)題報(bào)告

1、北京工商大學(xué)畢業(yè)論文(設(shè)計(jì))開(kāi)題報(bào)告,姓名：姚啟迪 班級(jí)：微機(jī)011學(xué)號(hào)：01042111指導(dǎo)教師：劉杰同組學(xué)生姓名：無(wú)畢業(yè)論文（設(shè)計(jì)）題目：遺傳算法在TSP問(wèn)題中的應(yīng)用,選題的目的和意義,遺傳算法是適應(yīng)性的啟發(fā)式搜索算法，研究歷史比較短，由美國(guó)Michigan大學(xué)John Holland等人于20世紀(jì)60年代末首先提出，它以自然選擇和遺傳機(jī)制的進(jìn)化思想為前提，體現(xiàn)著“適者生存”的競(jìng)爭(zhēng)機(jī)制，以模擬生物進(jìn)化的機(jī)制來(lái)構(gòu)造人

2、工系統(tǒng)的模型。隨后的20余年的發(fā)展，取得了很大的進(jìn)展，特別是近年來(lái)世界范圍形成的進(jìn)化計(jì)算熱潮，計(jì)算智能已作為人工智能研究的一個(gè)重要方向，以及后來(lái)的人工生命研究興起，使遺傳算法受到廣泛的關(guān)注。遺傳算法的一些主要應(yīng)用領(lǐng)域有：函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問(wèn)題、自動(dòng)控制、機(jī)器人智能控制、圖像處理和模式識(shí)別、人工生命、機(jī)器學(xué)習(xí)以及社會(huì)經(jīng)濟(jì)領(lǐng)域。,組合優(yōu)化問(wèn)題中一個(gè)典型問(wèn)題就是巡回旅行商問(wèn)題，也稱為貨郎擔(dān)問(wèn)題，簡(jiǎn)稱為T(mén)SP問(wèn)題，是一個(gè)容易描述但難以

3、處理的典型的NP難題。幾十年來(lái)，針對(duì)此問(wèn)題，出現(xiàn)了很多近似優(yōu)化算法，如鄰近法、貪心算法、最近插入法、最遠(yuǎn)插入法、雙極小生成樹(shù)法等等。由于遺傳算法的強(qiáng)大搜索能力，所以用遺傳算法求解TSP問(wèn)題是求得滿意解的最佳方法，也是繼續(xù)研究和發(fā)展該問(wèn)題得出更好解決方案的最有潛力的方向。,本題的研究現(xiàn)狀及開(kāi)題前的準(zhǔn)備工作,遺傳算法是一種有效的強(qiáng)大的隨機(jī)搜索方法，其性能主要取決于編碼方法及選擇、交叉、變異所采用的方法。以往曾對(duì)此課題做過(guò)研究和探討，所采用

4、的方案如下： 袁華 初始種群的生成 加入了均勻設(shè)計(jì)表 (局限于20個(gè)城市) 選擇：排序及輪盤(pán)賭交叉：順序交叉（OX）變異：逆轉(zhuǎn)變異吳穎 初始種群的生成 加入了均勻設(shè)計(jì)表 (局限于20個(gè)城市) 選擇：聯(lián)賽交叉：邊重組變異：對(duì)換朱英：初始種群的生成 加入了均勻設(shè)計(jì)表 (編程實(shí)現(xiàn)了任意個(gè)城市) 選擇：輪盤(pán)賭方法 輪盤(pán)賭與期望值結(jié)合的方法交叉：部分匹配交叉(PMX)變異：插入變異,查閱相

5、關(guān)的文獻(xiàn)資料，理解遺傳算法和TSP問(wèn)題的基本概念與基本思想，對(duì)課題的背景、應(yīng)用和發(fā)展現(xiàn)狀有一定的了解與認(rèn)識(shí)，并對(duì)前人的方案進(jìn)行比較，了解編碼、選擇、交叉、變異操作的各種方法，比較其優(yōu)劣，以尋求更優(yōu)方案。,畢業(yè)論文的進(jìn)度安排,第１—２周：查閱課題相關(guān)的文獻(xiàn)資料，對(duì)遺傳算法與TSP問(wèn)題的研究方法和研究現(xiàn)狀有一定的認(rèn)識(shí)；比較和研究前人方案，總結(jié)和規(guī)劃出一個(gè)更優(yōu)方案第３—5周：根據(jù)算法特點(diǎn)，按模塊編寫(xiě)程序，并在每個(gè)階段對(duì)程序進(jìn)行測(cè)試，以驗(yàn)證與

6、以往方案相比，本論文所采取的方案是否更加優(yōu)化。第６―８周：對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析與探討，并得出結(jié)論。第９—１０周：根據(jù)周志、參考資料等，概括和總結(jié)本次設(shè)計(jì)的成果、存在的問(wèn)題及改進(jìn)，在此基礎(chǔ)上，撰寫(xiě)畢業(yè)論文，完成畢業(yè)設(shè)計(jì)。,畢業(yè)論文（設(shè)計(jì)）的主要內(nèi)容,遺傳算法流程圖如下：,在用遺傳算法解決TSP問(wèn)題過(guò)程中，參照以往的研究成果所得出的經(jīng)驗(yàn)教訓(xùn)，對(duì)流程圖中編碼及生成初始種群、適應(yīng)度函數(shù)、選擇操作、交叉操作等環(huán)節(jié)所采用的方法進(jìn)行研究改進(jìn)，同時(shí)參