Abstract: A kind of discrete Particle Swarm Optimization (PSO) algorithm named NDPSO was proposed for extending the classic PSO model to solve the discrete optimization problems with high effectiveness and stability. The concept of comparison with probability was also introduced based on NDPSO, and then the stochastic repairing operator was constructed for heuristic search to solve the Winner Determination Problem (WDP) in combinatory auction. The experimental results show that NDPSO has great advantages in both success rate and convergence speed compared with other discrete PSO algorithms and genetic algorithm.

Key words: combinatory auction, winner determination, discrete Particle Swarm Optimization (PSO), stochastic repairing operator, artificial life computation

摘要： 通过拓展标准粒子群优化算法模型，提出了一种用于解决离散最优化问题的NDPSO算法，使其仍然具备标准PSO算法相对于其他智能算法的高效性和稳定性。在NDPSO算法的基础上引入依概率随机比较的概念，并构造了进行启发式搜索的随机修补算子，实现对组合拍卖中的竞胜标确定问题（WDP）的求解。实验结果表明，该求解方案与基于其他离散化PSO算法或遗传算法的求解方案相比在达优率和收敛速度上都具有明显的优势。

关键词: 组合拍卖, 竞胜标确定, 离散粒子群算法, 随机修补算子, 人工生命计算