一种求解多维背包问题的小世界算法

杜　巍　李树茁　陈煜聪

摘要：针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题，提出了一种解决多维背包问题的二进制编码小世界算法(BSWA)。BSWA算法依据社会学中的小世界现象搜索机理，采用类似遗传变异操作的局部搜索，而非遗传算法中的交叉操作。针对多维背包问题的多约束性，BSWA算法还按照价值资源比大小对不可行解进行贪婪修正，以保证求解的正确性。与遗传算法相比，BSWA可以在一定程度上克服早熟收敛，在保持种群多样性和求解精度方面均体现出较大的优势，具有解决复杂组合优化问题的潜力。对55个标准的多约束0-1背包问题进行了50次随机实验，结果表明，BSWA算法对于其中72.73％的问题可以次次获得最优解，对于其他不能次次求解到最优解的问题，也可以获得非常接近全局最优解的满意解。

关键词：小世界算法；多维背包问题；贪婪修正算子

中图分类号：TP183文献标志码：A文章编号：0253—987X(2009)02—010—05