获胜者确定问题的启发规则与改进蚁群算法

摘要

组合拍卖竞胜标的确定问题是一个NP完全问题.本文提出基于启发规则的改进蚁群算法BRIAA(Improved ACO Algorithm based heuristic rule)对问题进行求解,其基本思想是首先提出了可行性竞标启发规则,采用启发规则淘汰不可能入选最优解的竞标,缩减竞标规模;然后采用禁忌表和可行性竞标启岌规则相结合的改进蚁群算法,减小蚂蚁搜索过程中选择可行性竞标的范围,提高可行性解的质量.仿真结果表明,与同类的近似求解算法相比,本算法在求解规模和求解效率上都能够获得更好的效果.