生產(chǎn)生活中的一些實(shí)際問題可建模成背包問題進(jìn)行求解,比如決策投資、資源分配、預(yù)算控制等。其中0-1背包問題是最基礎(chǔ)的一類背包問題,許多的背包問題都可以轉(zhuǎn)化為0-1背包問題進(jìn)行求解。求解0-1背包問題的關(guān)鍵是在滿足約束條件的情況下使得最終裝入背包的物品價(jià)值總和最大。背包問題是一類離散化問題,利用群智能算法進(jìn)行求解時(shí),第一個(gè)需要解決的問題即是選擇編碼方式將算法離散化。群智能算法計(jì)算時(shí)會(huì)產(chǎn)生大量不可行解,如果對(duì)不可行解直接舍棄的話,會(huì)破壞種群多樣性,所以此時(shí)需要修復(fù)算法將不可行解可行化,保證種群多樣性。本文提出兩種改進(jìn)算法對(duì)0-1背包問題進(jìn)行求解。第一種是自適應(yīng)螢火蟲算法。對(duì)螢火蟲的位置賦予自適應(yīng)權(quán)重,在算法前期減小權(quán)重弱化螢火蟲自身位置,增加全局搜索能力,算法后期增加權(quán)重,為了使算法具有更強(qiáng)的局部搜索能力。根據(jù)權(quán)重可以使算法在快速有效的接近理論最優(yōu)值,最后對(duì)每一代更新后個(gè)體根據(jù)變異概率進(jìn)行變異操作。第二種是基于模擬退火的改進(jìn)螢火蟲算法。利用螢火蟲算法對(duì)個(gè)體進(jìn)行位置更新,模擬退火操作對(duì)更新后個(gè)體取舍,在一定程度上保證種群多樣性。根據(jù)種群的擁擠程度設(shè)置變異概率,當(dāng)種群較擁擠時(shí),增加變異概率,增強(qiáng)... 

【文章來源】：西華師范大學(xué)四川省

【文章頁數(shù)】：49 頁

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

【部分圖文】：

FA求解0-1背包問題的算法流程圖

第3章螢火蟲算法求解0-1背包問題12200247295284.3360-1KP250100200FA10249001018955.90209031024965.43852999947.700-1KP350100200FA3103271229042795.80502731288328090275629162833.100-1KP450100200FA5183327838353524.7080339738693617.40319139533669.900-1KP550100200FA26559193482136120170.10100197152197020445.20198852145120553.60通過表3-2知FA在求解規(guī)模較小的0-1背包問題可以在較小迭代次數(shù)下尋到最優(yōu)值，當(dāng)物品規(guī)模超過20個(gè)，即使增加迭代次數(shù)至200代也不能尋得理論最優(yōu)值，且隨著物品個(gè)數(shù)的增多，算法對(duì)于問題的尋優(yōu)結(jié)果越來越不理想，與理論最優(yōu)值之間的差距越來越大。為了進(jìn)一步了解螢火蟲算法的求解效果，下面綜合30次運(yùn)算結(jié)果的迭代平均值作出螢火蟲算法求解0-1背包問題的迭代效果圖：圖3-3FA求解0-1KP1的收斂效果圖3-4FA求解0-1KP2的收斂效果Fig.3-3FAConvergenceEffectfor0-1KP1Fig.3-4FAConvergenceEffectfor0-1KP2

第3章螢火蟲算法求解0-1背包問題12200247295284.3360-1KP250100200FA10249001018955.90209031024965.43852999947.700-1KP350100200FA3103271229042795.80502731288328090275629162833.100-1KP450100200FA5183327838353524.7080339738693617.40319139533669.900-1KP550100200FA26559193482136120170.10100197152197020445.20198852145120553.60通過表3-2知FA在求解規(guī)模較小的0-1背包問題可以在較小迭代次數(shù)下尋到最優(yōu)值，當(dāng)物品規(guī)模超過20個(gè)，即使增加迭代次數(shù)至200代也不能尋得理論最優(yōu)值，且隨著物品個(gè)數(shù)的增多，算法對(duì)于問題的尋優(yōu)結(jié)果越來越不理想，與理論最優(yōu)值之間的差距越來越大。為了進(jìn)一步了解螢火蟲算法的求解效果，下面綜合30次運(yùn)算結(jié)果的迭代平均值作出螢火蟲算法求解0-1背包問題的迭代效果圖：圖3-3FA求解0-1KP1的收斂效果圖3-4FA求解0-1KP2的收斂效果Fig.3-3FAConvergenceEffectfor0-1KP1Fig.3-4FAConvergenceEffectfor0-1KP2


本文編號(hào)：2963824