基于離散粒子群的組合拍賣競(jìng)勝標(biāo)確定問(wèn)題研究.pdf

1、與其他多物品拍賣方式相比，組合拍賣通過(guò)允許競(jìng)標(biāo)組合從而能更精確地表達(dá)競(jìng)標(biāo)者對(duì)競(jìng)標(biāo)物品之間關(guān)聯(lián)價(jià)值的真實(shí)需求。由于競(jìng)標(biāo)組合的不可分割性，使得競(jìng)標(biāo)者避免了由于關(guān)聯(lián)價(jià)值物品的缺失而導(dǎo)致的競(jìng)標(biāo)風(fēng)險(xiǎn)。通過(guò)組合拍賣機(jī)制的運(yùn)用，極大地提高價(jià)值關(guān)聯(lián)性強(qiáng)的多物品分配行為的經(jīng)濟(jì)效率。組合拍賣的競(jìng)勝標(biāo)求解問(wèn)題(Winner Determination Problem，WDP)被證明是一個(gè)NP完全問(wèn)題，因此WDP問(wèn)題的高效求解被認(rèn)為是組合拍賣相關(guān)研究中關(guān)系到其

2、應(yīng)用前景與實(shí)用性的關(guān)鍵問(wèn)題。
　　 本文使用提出的基于位置映射的離散化粒子群算法(Position MappingDiscrete Particle Swarm Optimization，PM-DPSO)，結(jié)合基于領(lǐng)域知識(shí)構(gòu)造的啟發(fā)式隨機(jī)化修補(bǔ)算子(Heuristic Stochastic Repairing Operator，HSRO)分別求解了基于OR、XOR、以及OR-XOR混合標(biāo)集的WDP問(wèn)題。本文的主要貢獻(xiàn)包括：(1)

3、提出隨w的變化動(dòng)態(tài)調(diào)整c1和c2的DCF-PSO算法，其中根據(jù)帶約束因子PSO算法推導(dǎo)出社會(huì)因子c1和個(gè)人因子c2和慣性權(quán)重w之間應(yīng)滿足的關(guān)系；(2)提出了新的離散化PSO算法PM-DPSO，為了遵循原有粒子群算法(PSO)背后的仿生學(xué)意義，保持了連續(xù)版本PSO的速度與位置更新公式不變；(3)設(shè)計(jì)了啟發(fā)式隨機(jī)修補(bǔ)算子HSRO以及帶鄰域搜索的HSRO算子，目的在于解決求解約束最優(yōu)化問(wèn)題中常用的貪婪修補(bǔ)算法造成的有效解空間被遺漏的問(wèn)題；(4