组合拍卖中求解最优竞胜标确定问题的部分搜索方法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 Combinatorial auctions摘要 本文研讨了随机部分搜索SLS和忌讳搜索TS用于处理组合拍卖中最优竞胜标确定问题WDP。所提的方法对各种规范问题进展评价，与混合模拟退火SAGII、密母算法MA和Casanova进展比较，结果显示SLS找到了质量更高的解。1 引见 拍卖是MAS中的市场协议，用于agent活动的协调和资源分配。组合拍卖CA是允许agents (bidders)对物品集合进展招标的机制。它允许招标人表达他们偏好的互补性和替代性。物品间的互补性意味着物品集合的价值大于各物品的价值总和。组合拍卖已运用于各个领域，如经济学，博弈论和MAS的义务分配等。 组合拍卖的最优竞胜者确定问题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)目的函数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. 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。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被接受，当其给出一个更好解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是不称心的。执行部分搜索时，选择不称心的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 实验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的影响。