【摘要】：拍賣是一種競價的買賣方式。傳統(tǒng)的拍賣是將特定物品或財(cái)產(chǎn)權(quán)利轉(zhuǎn)讓給最高應(yīng)價者。組合拍賣與傳統(tǒng)拍賣不同,組合拍賣允許投標(biāo)人在多個拍賣品中自由組合,給出總價格作為出價進(jìn)行競標(biāo),而不對其中物品單獨(dú)給出價格。組合拍賣在電子商務(wù)、空間分配、云計(jì)算等領(lǐng)域均有應(yīng)用。而勝者決定問題又是組合拍賣領(lǐng)域的核心問題之一,有著重要的理論意義和實(shí)際應(yīng)用價值。然而,勝者決定問題已經(jīng)在理論上被證明是NP難問題,目前找不到多項(xiàng)式時間內(nèi)求解的精確算法。精確算法雖然能證明輸出解的最優(yōu)性,但隨著問題規(guī)模的擴(kuò)大,它需要的求解時間將呈指數(shù)型增長,難以在可接受的時間里應(yīng)對復(fù)雜的大規(guī)模實(shí)例。這類NP問題通常都需要依靠啟發(fā)式算法進(jìn)行近似求解,以達(dá)到可以在實(shí)際中應(yīng)用的目的。局部搜索作為一類重要的啟發(fā)式算法,具有簡潔和高效的特點(diǎn)。局部搜索算法在多種NP問題求解中都有極好的表現(xiàn)。盡管它無法像精確算法一樣給出最優(yōu)解并證明其最優(yōu)性,但在大規(guī)模實(shí)例上,局部搜索算法通�？梢栽诟虝r間內(nèi)給出高質(zhì)量的近似解。勝者決定問題在實(shí)際應(yīng)用中十分重要,受到了很多關(guān)注。本文將設(shè)計(jì)和實(shí)現(xiàn)一種求解勝者決定問題的局部搜索算法,用于在短時間內(nèi)求解較大規(guī)模的實(shí)例并使解質(zhì)量盡可能提高。本文中提出的算法名為WDPLS。WDPLS基于一種高效且簡明的局部搜索框架,并配有三種技術(shù),分別為格局檢測技術(shù)、自由出價技術(shù)和偽并列技術(shù)。格局檢測技術(shù)是一種十分高效的用于局部搜索算法的防回溯策略。針對勝者決定問題,我們?yōu)閃DPLS設(shè)計(jì)了適合該問題的格局定義,阻止算法貪婪搜索時發(fā)生回溯。在算法進(jìn)行搜索時,可能會出現(xiàn)自由出價。這是一種特殊的出價,WDPLS優(yōu)先選擇自由出價以快速提升解質(zhì)量。此外,在搜索過程中可能會遇到質(zhì)量(得分)非常相似的落敗出價。對于這些出價,偽并列技術(shù)阻止了算法過度貪婪地選擇最高得分出價,從而為其他高質(zhì)量出價提供了被選可能,進(jìn)一步增加了解的多樣性。在LG數(shù)據(jù)集上的大量實(shí)驗(yàn)表明,WDPLS在求解質(zhì)量和求解時間上均領(lǐng)先于已發(fā)表的先進(jìn)算法。特別地,盡管WDPLS在本文實(shí)驗(yàn)中被實(shí)現(xiàn)為單線程程序,但其在與多線程實(shí)現(xiàn)的算法CARA及商業(yè)求解器CPLEX相比時仍具有明顯優(yōu)勢。同時,實(shí)驗(yàn)也展示出,以上三種主要技術(shù)都對WDPLS的性能有正面影響,證明了它們的有效性。
[Abstract]:An auction is a form of bidding. The traditional auction is the transfer of specific goods or property rights to the highest bidder. Combinatorial auction is different from traditional auction. Combinatorial auction allows bidders to combine freely in multiple auction items and give the total price as a bid instead of giving the price of the items. Combinatorial auctions have applications in e-commerce, space allocation, cloud computing and so on. The decision of winner is one of the core problems in the field of combinatorial auction, which has important theoretical significance and practical application value. However, the winner decision problem has been proved to be a NP problem in theory, and no exact algorithm can be found to solve it in polynomial time. Although the exact algorithm can prove the optimality of the output solution, with the expansion of the scale of the problem, the solving time it needs will increase exponentially, so it is difficult to deal with complex large-scale examples in acceptable time. This kind of NP problem usually needs to be solved by heuristic algorithm, so that it can be applied in practice. As an important heuristic algorithm, local search is simple and efficient. Local search algorithms have excellent performance in solving various NP problems. Although it can not give the optimal solution and prove its optimality just like the exact algorithm, the local search algorithm can usually give a high quality approximate solution in a shorter time. The winner decision problem is very important in practical application and has received much attention. In this paper, we design and implement a local search algorithm to solve the winner decision problem, which is used to solve large scale examples in a short time and to improve the quality of the solution as much as possible. The proposed algorithm named WDPLS.WDPLS is based on an efficient and concise local search framework with three techniques: pattern detection free bid and pseudo-juxtaposition. Pattern detection is a very efficient backtracking strategy for local search algorithms. For the winner decision problem, we design a pattern definition for WDPLS to prevent the backtracking of greedy search algorithm. Free bids may appear when the algorithm searches. This is a special bid, WDPLS preferred free bid to quickly improve the quality of the solution. In addition, the search process may encounter quality (score) very similar defeat bid. For these bids, pseudo-juxtaposition prevents the algorithm from choosing the highest score bid too greedily, thus providing other high-quality bids with the possibility of being selected, further increasing the diversity of understanding. A large number of experiments on LG datasets show that WDPLS is ahead of the published advanced algorithms in solving quality and time. In particular, although WDPLS is implemented as a single-threaded program in our experiments, it still has a significant advantage over the multithreaded algorithm CARA and the commercial solver CPLEX. At the same time, the experiments also show that the above three main technologies have a positive effect on the performance of WDPLS, which proves their effectiveness.
【學(xué)位授予單位】：東北師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：F713.359;TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 梁小毅;唐屹;;k-匿名映射的一種局部搜索算法[J];計(jì)算機(jī)應(yīng)用與軟件;2009年12期

2 張雁;黃永宣;魏明海;;一種求解最大團(tuán)問題的自適應(yīng)過濾局部搜索算法[J];信息與控制;2011年04期

3 肖進(jìn)杰,朱大銘,馬紹漢,潘銳;多服務(wù)中心設(shè)置問題局部搜索算法的分析與實(shí)驗(yàn)[J];計(jì)算機(jī)工程;2005年12期

4 謝嘯虎;黃樟燦;焉炳艷;;多目標(biāo)遺傳局部搜索算法的研究進(jìn)展[J];武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版);2006年12期

5 潘銳;朱大銘;董林光;董穎;;求解k中間點(diǎn)問題的新局部搜索算法[J];計(jì)算機(jī)工程與應(yīng)用;2008年04期

6 詹青青;;啟發(fā)式局部搜索算法在電路劃分中的應(yīng)用[J];福建電腦;2010年04期

7 韋煒;藤村茂;席裕庚;;求解旅行錦標(biāo)賽問題的改進(jìn)混合局部搜索算法[J];計(jì)算機(jī)仿真;2012年10期

8 吳貴芳,徐科,徐金梧;邊界局部搜索算法與應(yīng)用[J];計(jì)算機(jī)應(yīng)用;2005年02期

9 肖進(jìn)杰;謝青松;牛翠霞;;設(shè)備定位問題局部搜索算法的實(shí)驗(yàn)[J];計(jì)算機(jī)工程與應(yīng)用;2010年02期

10 陳萍;黃厚寬;董興業(yè);;基于多鄰域的車輛路徑優(yōu)化迭代局部搜索算法[J];北京交通大學(xué)學(xué)報(bào);2009年02期

相關(guān)會議論文 前4條

1 錢巍;馮玉強(qiáng);呼大永;;基于關(guān)聯(lián)函數(shù)確定組合拍賣商品的可行組合空間[A];第十三屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2011年

2 齊潔;鄭珉楠;;采用極值優(yōu)化算法求解動態(tài)組合拍賣問題[A];2009年中國智能自動化會議論文集（第七分冊）[南京理工大學(xué)學(xué)報(bào)（增刊）][C];2009年

3 王雅娟;王先甲;;關(guān)聯(lián)價值下最優(yōu)在線組合拍賣機(jī)制[A];中國系統(tǒng)工程學(xué)會第十八屆學(xué)術(shù)年會論文集——A01系統(tǒng)工程[C];2014年

4 劉心報(bào);葉強(qiáng);;基于模塊設(shè)計(jì)的蟻群算法研究綜述[A];'2008系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2008年

相關(guān)博士學(xué)位論文 前3條

1 李睿智;基于局部搜索策略的若干組合優(yōu)化問題求解算法研究[D];東北師范大學(xué);2017年

2 錢巍;組合拍賣中競勝標(biāo)自動確定問題研究[D];哈爾濱工業(yè)大學(xué);2012年

3 祁寧;網(wǎng)絡(luò)采購的逆向組合拍賣模型與優(yōu)化方法研究[D];東北大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 張皓辰;一種求解組合拍賣勝者決定問題的局部搜索算法[D];東北師范大學(xué);2017年

2 吳越鐘;改進(jìn)的Lin-Kernighan局部搜索算法和雜交算法在旅行商問題中的應(yīng)用[D];中國科學(xué)技術(shù)大學(xué);2016年

3 張崢華;SAT求解局部搜索行為分析與概率控制策略[D];華中科技大學(xué);2014年

4 徐斌;基于索引調(diào)制的寬帶MIMO-OFDM無線傳輸技術(shù)研究[D];電子科技大學(xué);2016年

5 李雙星;改進(jìn)迭代局部搜索算法求解需求拆分的校車路徑問題[D];河南大學(xué);2016年

6 劉偉臣;改進(jìn)的Ejection Chain局部搜索算法與混合算法求解旅行商問題[D];中國科學(xué)技術(shù)大學(xué);2017年

7 咸愛勇;合取范式最大不全滿足與最大可滿足問題的局部搜索算法研究[D];山東大學(xué);2012年

8 高超;隨機(jī)局部搜索算法及其應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2015年

9 殷茜;基于局部搜索的最小可滿足問題求解算法研究[D];東北師范大學(xué);2015年

10 趙軒;求解RCPSP問題的迭代局部搜索算法研究[D];北京交通大學(xué);2016年

，

本文編號：2299017