二次多背包問題及其擴(kuò)展問題的啟發(fā)式算法研究.pdf

1、二次多背包問題是經(jīng)典0-1背包問題的一個(gè)擴(kuò)展，在實(shí)際生活著中有著廣泛的應(yīng)用，例如當(dāng)不同工人相互合作時(shí)有不同效率的情況下將工人分配到不同的任務(wù)、有預(yù)算約束下通信衛(wèi)星的地球站選址問題以及鐵路站點(diǎn)、貨物運(yùn)輸終端、機(jī)場的選址問題等。與之相關(guān)的組成醫(yī)療小組問題來源于意大利米蘭的某個(gè)醫(yī)療服務(wù)中心，該問題與二次多背包問題有著相似的結(jié)構(gòu)，可以看成二次多背包問題的變種問題。這兩個(gè)問題除了廣泛的實(shí)際應(yīng)用背景，也是一類十分復(fù)雜的組合優(yōu)化問題，對于設(shè)計(jì)啟發(fā)式算

2、法求解十分有挑戰(zhàn)。鑒于其實(shí)用性和理論挑戰(zhàn)性，已經(jīng)吸引了大批學(xué)者的目光，在文獻(xiàn)中提出了各類求解這兩個(gè)問題的啟發(fā)式算法，但是仍然存在不足之處，還需要進(jìn)一步的深入研究。本文擬在在已有的研究求解二次多背包問題以及組成醫(yī)療小組問題文獻(xiàn)的基礎(chǔ)上，提出更為高效的啟發(fā)式算法并提升現(xiàn)有文獻(xiàn)中的最好解，為求解這類問題提供更多的選擇。
　　首先，研究了使用混合了可行與不可行局部搜索的禁忌搜索算法求解二次多背包問題。該算法引入了不可行解搜索階段，允許算法

3、在搜索過程中搜索不可行解，能夠?yàn)樗惴◣砀嗟淖杂啥?。然后，我們在算例上進(jìn)行了大量的實(shí)驗(yàn)來證明該算法的有效性并分析了算法各個(gè)重要組成部分的關(guān)鍵作用。
　　其次，本文根據(jù)二次多背包問題的分組特性，提出了一種基于backbone交叉算子混合算法求解該問題，該算子能夠保留父代中的物品分配信息并遺傳到子代，產(chǎn)生高質(zhì)量的解。我們將該混合算法在不同時(shí)間限制下的計(jì)算結(jié)果與文獻(xiàn)中求解QMKP最好的幾種算法進(jìn)行了對比，證明了該算法優(yōu)異性并給出了小結(jié)

4、。
　　第三，研究了由二次多背包問題變種而來的組成醫(yī)療小組問題，結(jié)合該問題的特點(diǎn)，提出了一種求解組成醫(yī)療小組問題的二階段禁忌搜索算法。該算法中的二階段局部搜索過程可以很好的處理目標(biāo)函數(shù)和約束之間相互影響的關(guān)系，能夠防止算法過早地陷入局部最優(yōu)。我們通過實(shí)驗(yàn)將該算法與文獻(xiàn)中的最好算法進(jìn)行了對比，并分析了二階段搜索過程對算法性能的影響，最后給出了小結(jié)。
　　第四，延續(xù)了第五章所研究的組成醫(yī)療小組問題，根據(jù)該問題的分組特性，將求解二