获胜者确定问题的建模与启发式算法

获胜者确定问题是组合拍卖机制的核心问题．因此，对基于OR与XOR标集的获胜者确定问题建立了0-1规划模型，并且提出了免疫算子与单亲算子相结合的启发式算法．提出多个启发式规则以扩大标比较范围，并应用在预处理中缩减解空间．设计了多个评价函数评估标的优劣，从而将特征知识引入到免疫算子中．仿真实验表明，对大规模问题的求解具有良好的寻优效率和求解质量，免疫算子对达优率和收敛速度都有着明显的提升作用．

Modeling and Heuristic for Winner Determination in Combinatorial Auctions

Combinatorial auctions are efficient mechanisms for allocating resource in complex marketplace. The combination auction with XOR-bids and OR-bids allows bidders expressing their general preference more exactly. Winner determination, which is NP-complete, is the core problem in combinatorial auctions. In this paper, a zero-one programming model and a heuristic algorithm are proposed for solving the winner determination problem with XOR-bids and OR-bids. For searching the non-competitive bids in XOR-bids and OR-bids, new heuristic rules and methods are designed in the preprocessing. The heuristic algorithm is a partheno-genetic algorithm combined with the immune operator. In the immune operator, new heuristics are designed for evaluating the bids and applied in the procedure of vaccines selection and vaccination. Simulation results show that the algorithm achieves good performance in large size problems and the immune operator can improve the searching ability and increase the converging speed greatly.