|
|||||
|
|
| 一种求解多维背包问题的小世界算法 | |
| 引用本文： | 杜巍,李树茁,陈煜聪.一种求解多维背包问题的小世界算法[J].西安交通大学学报,2009,43(2). |
| 作者姓名： | 杜巍 李树茁 陈煜聪 |
| 作者单位： | 1. 西安交通大学管理学院,710049,西安 2. 西安交通大学人口与发展研究所,710049,西安 3. 西安交通大学机械工程学院,710049,西安 |
| 基金项目： | 国家自然科学基金，教育部新世纪优秀人才支持计划，长江学者奖励计划，美国Santa Fe Institute国际基金，斯坦福大学联合资助项目，西安交通大学面向21世纪教育振兴行动计划（985计划） |
| 摘 要： | 针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题,提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理,采用类似遗传变异操作的局部搜索,而非遗传算法中的交叉操作.针对多维背包问题的多约束性,BSWA算法还按照价值资源比大小对不可行解进行贪婪修正,以保证求解的正确性.与遗传算法相比,BSWA可以在一定程度上克服早熟收敛,在保持种群多样性和求解精度方面均体现出较大的优势,具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验,结果表明,BSWA算法对于其中72.73%的问题可以次次获得最优解,对于其他不能次次求解到最优解的问题,也可以获得非常接近全局最优解的满意解. |
| 关 键 词： | 小世界算法 多维背包问题 贪婪修正算子 |
A Small World Algorithm for Multi-Dimensional Knapsack Problems |
|
| DU Wei,LI Shuzhuo,CHEN Yucong.A Small World Algorithm for Multi-Dimensional Knapsack Problems[J].Journal of Xi'an Jiaotong University,2009,43(2). | |
| Authors: | DU Wei LI Shuzhuo CHEN Yucong |
| Abstract: | |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ | |
