多維背包問(wèn)題（Multidimensional knapsack problem,MKP）作為0-1背包問(wèn)題的拓展,是一種典型的NP難問(wèn)題,在日常生活中有著大量的應(yīng)用場(chǎng)景,比如貨物裝載,資源分配,投資決策等等。因此,無(wú)論是理論上,還是實(shí)際應(yīng)用中,對(duì)多維背包問(wèn)題進(jìn)行求解都具有重要意義。隨著問(wèn)題規(guī)模的逐漸增大,傳統(tǒng)的精確求解算法和啟發(fā)式算法逐漸顯得力不從心,而群智能算法的發(fā)展,為這類問(wèn)題的求解開辟了新的道路。群智能算法是通過(guò)模擬生物種群之間的信息交流以達(dá)到求解目的的一類新型算法。煙花算法是通過(guò)模擬夜空中煙花爆炸的過(guò)程而實(shí)現(xiàn)的。作為群智能算法的一種,煙花算法具有參數(shù)較少、執(zhí)行過(guò)程簡(jiǎn)單、實(shí)現(xiàn)容易,魯棒性強(qiáng)等特點(diǎn),在解決大型復(fù)雜優(yōu)化問(wèn)題上具有一定優(yōu)勢(shì),目前已經(jīng)得到了學(xué)術(shù)界的廣泛關(guān)注。本文介紹了用于求解多維背包問(wèn)題的各類精確求解算法,啟發(fā)式算法和群智能算法,深入分析了多維背包問(wèn)題及煙花算法的特點(diǎn),針對(duì)多維背包問(wèn)題中,物品選擇策略表現(xiàn)為二進(jìn)制字符串的特點(diǎn),以及煙花算法前期搜索速度快,后期收斂速度慢的優(yōu)劣性,引入了二進(jìn)制煙花算法和精英反向?qū)W習(xí)機(jī)制,設(shè)計(jì)了二進(jìn)制精英反向?qū)W習(xí)煙花算法（Binary Eli... 

【文章來(lái)源】：吉林大學(xué)吉林省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：60 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

遺傳算法流程圖

第2章背包問(wèn)題及優(yōu)化算法相關(guān)理論基礎(chǔ)16圖2.2煙花算法流程圖2.4.2煙花算法實(shí)現(xiàn)過(guò)程1.爆炸算子煙花算法在運(yùn)行過(guò)程中通過(guò)爆炸算子操作來(lái)生成下一代火花，爆炸算子通常包括爆炸強(qiáng)度，爆炸幅度，位移操作三個(gè)部分。爆炸算子是煙花算法中的核心操作，極其重要。

第3章二進(jìn)制精英反向?qū)W習(xí)煙花算法25)))(()((1maxmaxmiiiixffxffmceilA··························(3-7)其中，ceil為向上取整函數(shù)；cN為一個(gè)和親代煙花數(shù)量相關(guān)的系數(shù)，用于控制產(chǎn)生火花的數(shù)量；m為二進(jìn)制維數(shù)；maxf為計(jì)算過(guò)程中已知的最優(yōu)適應(yīng)度值，minf為計(jì)算過(guò)程中已知的最差適應(yīng)度值；610，保證分母不為0。煙花ix爆炸后在iA半徑內(nèi)產(chǎn)生iN個(gè)火花，其中第p個(gè)火花的生成規(guī)則為),,(0EiipirSxx····································(3-8)其中，},,2,1{0mS為全部m個(gè)二進(jìn)制編碼構(gòu)成的集合；Eir為爆炸步長(zhǎng)，二進(jìn)制轉(zhuǎn)換算子),,(0EiixrS表示以元素ix為基礎(chǔ)字符串，從轉(zhuǎn)換集0S中隨機(jī)選出Eir個(gè)字符進(jìn)行0-1轉(zhuǎn)置。爆炸步長(zhǎng)采用隨機(jī)生成方式獲得，隨機(jī)數(shù)產(chǎn)生范圍為0到爆炸半徑。ceilrrandA)(ipi·································(3-9)爆炸算子運(yùn)行過(guò)程示例如下：設(shè)選定煙花0,0,0,0,1,1,1,11x，8,7,6,5,4,3,2,10S，1pir，產(chǎn)生的火花個(gè)體數(shù)量21N，則爆炸算子結(jié)果如下圖圖3.1爆炸算子示意圖最終產(chǎn)生的火花個(gè)體將會(huì)在全部8種可能的情況中隨機(jī)選擇2種。2.變異算子


本文編號(hào)：2900104