發(fā)布時(shí)間：2019-11-11 10:06

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2559207