《组合拍卖中求解最优竞胜标确定问题的局部搜索方法ppt课件》由会员分享，可在线阅读，更多相关《组合拍卖中求解最优竞胜标确定问题的局部搜索方法ppt课件（18页珍藏版）》请在金锄头文库上搜索。
1、组合拍卖中求解最优竞胜标确定问题的部分搜索方法LocalSearchMethodsfortheOptimalWinnerDeterminationProbleminCombinatorialAuctionsDalila Boughaci Belad Benhamou Habiba DriasSpringer：J Math Model Algor (2019) 9:165180Keywords： Stochastic local search Tabu search Winner determination problem Casanova SAGII Memetic algorithms Co
2、mbinatorial auctions摘要 本文研讨了随机部分搜索SLS和忌讳搜索TS用于处理组合拍卖中最优竞胜标确定问题WDP。所提的方法对各种规范问题进展评价，与混合模拟退火SAGII、密母算法MA和Casanova进展比较，结果显示SLS找到了质量更高的解。1 引见 拍卖是MAS中的市场协议，用于agent活动的协调和资源分配。组合拍卖CA是允许agents (bidders)对物品集合进展招标的机制。它允许招标人表达他们偏好的互补性和替代性。物品间的互补性意味着物品集合的价值大于各物品的价值总和。组合拍卖已运用于各个领域，如经济学，博弈论和MAS的义务分配等。 组合拍卖的最优竞胜者确
3、定问题WDP)要决议哪个招标是可接受的。本文提出了两种部分搜索方法求解WDP，一个是随机的部分搜索方法，另一个是忌讳搜索方法。2 问题模型拍卖物品的集合M=1,2,.,m招标集合B=B1,B2,.,Bn一个招标Bj=(Sj,Pj),Sj是一个物品集合，Pj是Sj的物品的总体价钱。矩阵AmnAij=1，iff物品i属于Bj的Sj；否那么Aij=0。决策变量xj=1,iff招标Bj是可接受的winning bid；否那么xj=0Bj is a losing bid2 问题模型WDP是在每个物品至多分配给一个招标人的约束下最大化拍卖人的收益，找到获胜招标的问题。WDP模型为下面的整数规划：(1)(2
4、)目的函数1最大化拍卖者的收益，等于获胜标的价钱之和。约束2表示每个物品至多分配给一个招标人。3 本文奉献3.1 解的表示变长的向量V，Vi接纳获胜标。3.1.1 The Random Key Encoding1. 产生4个随机数，如 r = 0.65, 0.70, 0.80, 0.75.2. highest order value (0.80)，The first accepted bid is B3，V = B3.3. the second highest order value is B4，conflicts with the bid B3 in V，It is discarded。4.
5、 the third highest order value is B2，conflicts with the bid B3 in V，It is discarded。5. V=B3,B1是WDP的一个解.3 本文奉献3.2 冲突图为了保证搜索过程中解的可行性，文中定义了一个冲突图，顶点是bids，边将不能被接受的bids相连。这个图用于发现冲突的bids。3.3 评价函数 the allocation V = B1, B2, . . . , BL.(3)3 本文奉献3.4 随机的部分搜索SLS SLS利用RK编码机制产生一初始分配V，然后执行部分搜索，选择一bid参与V,移除一切冲突bids
6、。maxiter=10000wp=0.33 本文奉献3.5 忌讳搜索TSfor WDP 忌讳搜索结合了集中搜索和分散搜索。 集中搜索起始于RK编码产生的初始分配，然后选择最好的邻域分配，为此定义了两个move操作。- On-Bid move:当bid是最好但不是tabu时执行形状空间定义为：不在当前分配中的不称心但可接受的bids集合。将当前形状空间中最好的bid参与到当前分配V中，移除冲突的bids。最好的bid指参与分配后最大化总体价钱。防止部分最优：bid参与分配后，接纳一个tabu形状，其索引存入tubu列表，在给定的次迭代中不允许再次访问。特赦准那么：一tabu move被接受，当其
7、给出一个更好解3 本文奉献3.5 忌讳搜索TSfor WDP- On-Item move:形状空间定义为：当前分配中没有被bids所覆盖的items集合。覆盖这些items的最好的bid参与到当前分配V中，移除冲突的bids。 分散搜索：当集中搜索不再有改善时启动，为下一代选择一随机的邻域解，用于开发新的区域。选择一个随机的不称心bid参与到当前分配，此过程延续执行n步bids数目。maxiter=25000=40d=404 实验1对比算法简介Cssanova:一种随机部分搜索方法，算法起始于空分配，一切物品设置到dummy bid并且一切real bids是不称心的。执行部分搜索时，选择不称
8、心的bids参与当前分配并移除冲突的bids。选择时，以概率wp随机选一bid；以1-wp贪婪地选一bid将一切bids按profit/number of items降序陈列。B1或B2参与分配。模拟退火SAGII：利用预处置和三个部分moves预处置排除部分最优解Branch-and-Bound,greedy local search,1-2 exchangeMemetic算法RK Encodingconflict graphnew select strategy according to fitness and diversial qualitycrossover operator4 实验
9、2Benchmarks problems3对比实验：SLS总体绩效好于其他算法 a. SLS vs. TS:实验结果显示，SLS优于TS, SLS可以在更短的CPU时间内找到更好的解。 b. SLS,Casanova,Tabu Search and SAGII :算术平均 ， time:平均时间，: SLS比Casanova提高了28%-42%；SLS稍好于TS，对于REL5001000，TS好于SLS； SLS稍好于SAGII。SLS所用的时间最短。4 实验3对比实验4 实验3对比实验4 实验3对比实验5 结论 组合拍卖是一种存在替代品和互补品情况下，将多种物品分配给竞拍人的拍卖。本文提出了两种部分搜索方法处理组合拍卖中的竞胜标确定问题。第一种方法是随机部分搜索SLS，第二种是一种忌讳搜索元启发式方法(TS)。TS和SLS都在多种规范问题上进展测试，并与SGAII,MA和Casanova对比，SLS显示了更有竞争力的结果。 未来任务思索为SLS添加预处置过程，以使SLS更高效并防止堕入部分最优。还将研讨SLS对分枝定界算法Branch-and-Bound的影响。
