组合拍卖中求解最优竞胜标确定问题的局部搜索方法.ppt

1、组合拍卖中求解最优竞胜标确定问题的局部搜索方法,Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions,Dalila Boughaci Belad Benhamou Habiba Drias,Springer：J Math Model Algor (2010) 9:165180,Keywords： Stochastic local search Tabu search Winner determination problem Casanova SAGII Memeti

2、c algorithms Combinatorial auctions,摘要,本文研究了随机局部搜索（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的物品的总体价格。 矩阵AmnAij=1，iff物品i属于Bj的Sj；否则Aij=0。 决策变量xj=1,iff投标Bj是可接受的（winning bid）；否则xj=0（Bj is a losing bid）,2 问题模型,WDP是在每个物品至多分配给一个投标人的约束

4、下最大化拍卖人的收益，找到获胜投标的问题。WDP模型为下面的整数规划：,(1),(2),目标函数（1）最大化拍卖者的收益，等于获胜标的价格之和。约束（2）表示每个物品至多分配给一个投标人。,3 本文贡献,3.1 解的表示 变长的向量V，Vi接收获胜标。 3.1.1 The Random Key Encoding,1. 产生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 i

5、s 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

6、.4 随机的局部搜索（SLS） SLS利用RK编码机制产生一初始分配V，然后执行局部搜索，选择一bid加入V,移除所有冲突bids。,maxiter=10000 wp=0.3,3 本文贡献,3.5 禁忌搜索（TS）for WDP 禁忌搜索结合了集中搜索和分散搜索。 集中搜索起始于RK编码产生的初始分配，然后选择最好的邻域分配，为此定义了两个move操作。 - On-Bid move:当bid是最好但不是tabu时执行 状态空间定义为：不在当前分配中的不满意但可接受的bids集合。将当前状态空间中最好的bid加入到当前分配V中，移除冲突的bids。最好的bid指加入分配后最大化总体价格。 避免局

7、部最优：bid加入分配后，接收一个tabu状态，其索引存入tubu列表，在给定的次迭代中不允许再次访问。 特赦准则：一tabu move被接受，当其给出一个更好解,3 本文贡献,3.5 禁忌搜索（TS）for WDP - On-Item move: 状态空间定义为：当前分配中没有被bids所覆盖的items集合。覆盖这些items的最好的bid加入到当前分配V中，移除冲突的bids。 分散搜索：当集中搜索不再有改善时启动，为下一代选择一随机的邻域解，用于开发新的区域。选择一个随机的不满意bid加入到当前分配，此过程连续执行n步（bids数目）。,maxiter=25000 =40 d=40,4

8、 实验,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 exchange Memetic算法 RK Encoding c

9、onflict graph new select strategy according to fitness and diversial quality crossover operator,4 实验,2）Benchmarks problems 3）对比实验：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）对比实验,4 实验,3）对比实验 c. SLS vs. MA MA获得的解质量稍好于SLS，但SLS速度更快。,5 结论,组合拍卖是一种存在替代品和互补品情况下，将多种物品分配给竞拍人的拍卖。本文提出了两种局部搜索方法解决组合拍卖中的竞胜标确定问题。第一种方法是随机局部搜索（SLS），第二种