組合拍賣問題及其智能優(yōu)化算法的研究.pdf

1、組合拍賣是解決各種資源分配問題的有效機制，隨著電子商務的發(fā)展，組合拍賣機制發(fā)展成為一種新的多方交互與決策的電子談判模式，是當前電子商務的一個重要應用領域。組合拍賣問題是組合拍賣理論的研究核心之一，是NP難題。該問題的優(yōu)化與求解直接影響到整個組合拍賣機制的有效性與實用性，有著極高的理論研究價值和廣泛的應用前景。 本文主要研究基于組合標集的單數(shù)量組合拍賣問題和多數(shù)量組合拍賣問題，目前，國內(nèi)外文獻對整合了組合標集的組合拍賣問題尚未見有

2、較深入的優(yōu)化求解。為此，本文對這兩種基于組合標集的組合拍賣問題進行研究，對問題的優(yōu)化求解開展了以下工作： 1、對組合拍賣問題原型進行了研究，分析了組合拍賣問題與多維背包問題的關系，揭示了兩種基于組合標集的組合拍賣問題模型均派生于多維背包問題模型。 2、對基于組合標集的單數(shù)量組合拍賣問題建立了0-1整數(shù)規(guī)劃模型。分析了單數(shù)量組合拍賣下的組合標集特性，提出多項啟發(fā)式規(guī)則并設計相應的預處理方法對問題進行優(yōu)化，有效地縮減求解空間

3、。 3、針對單數(shù)量組合拍賣的特性，設計新的評價策略和評價函數(shù)，更準確評估標進入最優(yōu)解的可能性。提出單親算子與免疫算子相結合的啟發(fā)式算法對問題進行求解，免疫算子利用評價函數(shù)將問題的特征知識引入到算法求解中，減少了冗余搜索，提高算法搜索效率。仿真測試表明該算法能夠有效地解決大規(guī)模問題，而且表現(xiàn)出良好的求解性能。 4、對基于組合標集的多數(shù)量組合拍賣問題建立了0-1整數(shù)規(guī)劃模型。分析了多數(shù)量組合拍賣下的組合標集特性，提出多項啟發(fā)