【摘要】：在實(shí)際生活和工程中,二次分配問題(Quadratic assignment problem,QAP)有著非常多的應(yīng)用,例如:工廠地址的位置選擇、集成電路的線路布局、打字機(jī)鍵盤設(shè)計、作業(yè)調(diào)度等。二次分配問題是一種離散型的組合優(yōu)化問題,具有NP-hard屬性,很難在多項式時間內(nèi)被求解。因此,自1957年Koopmans和Beckmann提出二次分配問題以來,許多學(xué)者一直關(guān)注并研究了該問題,并提出了3類有效的算法:經(jīng)典的數(shù)學(xué)方法、啟發(fā)式和演化方法。但前一類只適應(yīng)于小規(guī)模QAP問題的求解,后兩類仍然有研究的空間。如何探索高性能的求解方法一直是開放性的課題。人工魚群算法不需要對初始參數(shù)有過多的要求,差異演化算法的收斂速度快,局部搜索能力強(qiáng)。因此,本文在湖南省高�？萍汲晒a(chǎn)業(yè)化培育項目基金(編號2015CY010)的資助下,對求解QAP的差異與魚群混合的演化方法進(jìn)行研究,主要工作和創(chuàng)新點(diǎn)歸納如下:1.提出一種求解QAP問題的改進(jìn)的魚群優(yōu)化方法。(1)給出了一種步長為1的窮舉搜索覓食行為,提高了覓食效率;(2)改進(jìn)的隨機(jī)行為中,個體魚的新狀態(tài)繼承了一部分最優(yōu)魚的狀態(tài)分量,以避免隨機(jī)行為的盲目性;(3)通過隨機(jī)選取可視域大小,以保持魚群的多樣性。實(shí)驗表明:提出的改進(jìn)的魚群算法的求解精度優(yōu)于基本的人工魚群算法。2.提出一種求解QAP問題的改進(jìn)差異魚群優(yōu)化方法。定義了QAP問題中的差異演化的變異、交叉以及選擇算子。與改進(jìn)的魚群算法相結(jié)合,提高整體的局部尋優(yōu)能力和收斂速度。數(shù)值實(shí)驗表明:改進(jìn)差異魚群優(yōu)化方法的收斂速度和求解精度明顯優(yōu)于目前已有的其它算法。本文討論了QAP問題的基本魚群算法的改進(jìn),并與局部搜索能力強(qiáng)的差異演化算法結(jié)合。提出的改進(jìn)差異魚群優(yōu)化算法具有比較強(qiáng)的收斂能力,且求解精度高。二次分配基準(zhǔn)問題庫(QAPLIB)中的算例驗證了本文方法的良好性能。最后,希望本文算法能夠推廣到其他組合優(yōu)化問題中,能夠有助于對這些問題的求解。
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王麗;蘆彩林;宮建平;;一種求解路徑優(yōu)化問題的新型人工魚群算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;2016年20期

2 張惠珍;李倩;Cesar Beltran-Royo;;求解二次分配問題的拉格朗日松弛新方法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;2016年18期

3 馬憲民;劉妮;;自適應(yīng)視野的人工魚群算法求解最短路徑問題[J];通信學(xué)報;2014年01期

4 徐鵬;劉文穎;趙子蘭;李波;汪寧渤;;基于改進(jìn)人工魚群算法的含大規(guī)模風(fēng)電電網(wǎng)無功優(yōu)化[J];中國電力;2013年11期

5 王培崇;;人工魚群算法研究綜述[J];中國民航飛行學(xué)院學(xué)報;2013年04期

6 汪照;李有明;陳斌;鄒婷;;基于魚群算法的OFDMA自適應(yīng)資源分配[J];物理學(xué)報;2013年12期

7 楊淑霞;韓奇;徐琳茜;劉達(dá);路石俊;;魚群算法與神經(jīng)網(wǎng)絡(luò)結(jié)合的節(jié)能減排效果評價[J];中南大學(xué)學(xué)報(自然科學(xué)版);2012年04期

8 朱命昊;厙向陽;;求解旅行商問題的改進(jìn)人工魚群算法[J];計算機(jī)應(yīng)用研究;2010年10期

9 曲良東;何登旭;;一種混沌人工魚群優(yōu)化算法[J];計算機(jī)工程與應(yīng)用;2010年22期

10 張惠珍;馬良;;基于線性化技術(shù)的二次分配問題求解新方法[J];系統(tǒng)工程理論與實(shí)踐;2010年03期

相關(guān)博士學(xué)位論文 前2條

1 武志峰;差異演化算法及其應(yīng)用研究[D];北京交通大學(xué);2009年

2 李曉磊;一種新型的智能優(yōu)化方法-人工魚群算法[D];浙江大學(xué);2003年

相關(guān)碩士學(xué)位論文 前1條

1 楊藝;求解二次分配問題的魚群算法研究[D];湘潭大學(xué);2014年

，

本文編號：2559207