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

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

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

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

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