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

摘要：

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

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

所属期刊栏目：43

分类号：TP183(自动化基础理论)

资助基金：国家自然科学基金资助项目70671083;教育部新世纪优秀人才支持计划资助项目NCET-07-0668;长江学者奖励计划;美国Santa Fe Institute国际基金;斯坦福大学联合资助项目;西安交通大学"985工程"二期重点资助项目07200701

在线出版日期：2009-04-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：10-14