资源描述：
《组合拍卖中求解最优竞胜标确定问题的局部搜索方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合拍卖中求解最优竞胜标确定问题的局部搜索方法LocalSearchMethodsfortheOptimalWinnerDeterminationProbleminCombinatorialAuctionsDalilaBoughaci·BelaïdBenhamou·HabibaDriasSpringer：JMathModelAlgor(2010)9:165–180Keywords：Stochasticlocalsearch·Tabusearch·Winnerdeterminationproblem·Casanova·SAGII·Meme
2、ticalgorithms·Combinatorialauctions摘要本文研究了随机局部搜索（SLS）和禁忌搜索（TS）用于解决组合拍卖中最优竞胜标确定问题（WDP）。所提的方法对各种标准问题进行评估，与混合模拟退火（SAGII）、密母算法（MA）和Casanova进行比较，结果显示SLS找到了质量更高的解。1介绍拍卖是MAS中的市场协议，用于agent活动的协调和资源分配。组合拍卖（CA）是允许agents(bidders)对物品集合进行投标的机制。它允许投标人表达他们偏好的互补性和替代性。物品间的互补性意味着物品集合的价值大于各
3、物品的价值总和。组合拍卖已应用于各个领域，如经济学，博弈论和MAS的任务分配等。组合拍卖的最优竞胜者确定问题（WDP)要决定哪个投标是可接受的。本文提出了两种局部搜索方法求解WDP，一个是随机的局部搜索方法，另一个是禁忌搜索方法。2问题模型拍卖物品的集合——M={1,2,...,m}投标集合——B={B1,B2,...,Bn}一个投标——Bj=(Sj,Pj),Sj是一个物品集合，Pj是Sj的物品的总体价格。矩阵Am×n——Aij=1，iff物品i属于Bj的Sj；否则Aij=0。决策变量——xj=1,iff投标Bj是可接受的（winnin
4、gbid）；否则xj=0（Bjisalosingbid）2问题模型WDP是在每个物品至多分配给一个投标人的约束下最大化拍卖人的收益，找到获胜投标的问题。WDP模型为下面的整数规划：(1)(2)目标函数（1）最大化拍卖者的收益，等于获胜标的价格之和。约束（2）表示每个物品至多分配给一个投标人。3本文贡献3.1解的表示变长的向量V，Vi接收获胜标。3.1.1TheRandomKeyEncoding1.产生4个随机数，如r={0.65,0.70,0.80,0.75}.2.highestordervalue(0.80)，Thefirstacce
5、ptedbidisB3，V={B3}.3.thesecondhighestordervalueisB4，conflictswiththebidB3inV，Itisdiscarded。4.thethirdhighestordervalueisB2，conflictswiththebidB3inV，Itisdiscarded。5.V={B3,B1}是WDP的一个解.3本文贡献3.2冲突图为了保证搜索过程中解的可行性，文中定义了一个冲突图，顶点是bids，边将不能被接受的bids相连。这个图用于发现冲突的bids。3.3评价函数theallo
6、cationV={B1,B2,...,BL}.(3)3本文贡献3.4随机的局部搜索（SLS）SLS利用RK编码机制产生一初始分配V，然后执行局部搜索，选择一bid加入V,移除所有冲突bids。maxiter=10000wp=0.33本文贡献3.5禁忌搜索（TS）forWDP禁忌搜索结合了集中搜索和分散搜索。集中搜索起始于RK编码产生的初始分配，然后选择最好的邻域分配，为此定义了两个move操作。-On-Bidmove:当bid是最好但不是tabu时执行状态空间定义为：不在当前分配中的不满意但可接受的bids集合。将当前状态空间中最好的b
7、id加入到当前分配V中，移除冲突的bids。最好的bid指加入分配后最大化总体价格。避免局部最优：bid加入分配后，接收一个tabu状态，其索引存入tubu列表，在给定的次迭代中不允许再次访问。特赦准则：一tabumove被接受，当其给出一个更好解3本文贡献3.5禁忌搜索（TS）forWDP-On-Itemmove:状态空间定义为：当前分配中没有被bids所覆盖的items集合。覆盖这些items的最好的bid加入到当前分配V中，移除冲突的bids。分散搜索：当集中搜索不再有改善时启动，为下一代选择一随机的邻域解，用于开发新的区域。选
8、择一个随机的不满意bid加入到当前分配，此过程连续执行n步（bids数目）。maxiter=25000=40d=404实验1）对比算法简介Cssanova:一种随机局部搜索方法，算法起始于空分配，所有物品
