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

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

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

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