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

杜巍 1; 李树茁 2; 陈煜聪 3

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-12-08

- 一种求解多维背包问题的小世界算法
- A Small World Algorithm for Multi-Dimensional Knapsack Problems
- 西安交通大学学报 2009年43卷第2期页码：10-14
- 作者机构：
  
  西安交通大学管理学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2008-06-20. 作者简介: 杜巍(1979-),男,博士生;李树茁(联系人),男,教授,博士生导师. 基金项目: 国家自然科学基金资助项目(70671083);教育部新世纪优秀人才支持计划资助项目(NCET-07-0668);长江学者奖励计划;美国Santa Fe Institute国际基金资助项目;斯坦福大学联合资助项目;西安交通大学“985工程”二期重点资助项目(07200701)
- DOI：
  中图分类号： TP183
- 网络首发：2009-02-10，
  
  纸质出版：2009
- 稿件说明：
移动端阅览
杜巍 1, 李树茁 2, 陈煜聪 3. 一种求解多维背包问题的小世界算法[J]. 西安交通大学学报, 2009,43(2):10-14.

杜巍 1, 李树茁 2, 陈煜聪 3. A Small World Algorithm for Multi-Dimensional Knapsack Problems[J]. 2009, 43(2): 10-14.
杜巍 1, 李树茁 2, 陈煜聪 3. 一种求解多维背包问题的小世界算法[J]. 西安交通大学学报, 2009,43(2):10-14. DOI：

杜巍 1, 李树茁 2, 陈煜聪 3. A Small World Algorithm for Multi-Dimensional Knapsack Problems[J]. 2009, 43(2): 10-14. DOI：

摘要

针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题

提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理

采用类似遗传变异操作的局部搜索

而非遗传算法中的交叉操作.针对多维背包问题的多约束性

BSWA算法还按照价值资源比大小对不可行解进行贪婪修正

以保证求解的正确性.与遗传算法相比

BSWA可以在一定程度上克服早熟收敛

在保持种群多样性和求解精度方面均体现出较大的优势

具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验

结果表明

BSWA算法对于其中72.73%的问题可以次次获得最优解

对于其他不能次次求解到最优解的问题

也可以获得非常接近全局最优解的满意解.

Abstract

In order to overcome the shortcomings of genetic algorithms(GA)

an optimization algorithm called the binary-coding small world algorithm(BSWA)is proposed. The GA always loses diversity in the set of the candidate solutions and prematurely converges when it is used to solve complex combinatorial optimization problems. The BSWA is based on the searching mechanisms in social networks

and emphasizes local(as mutation in GA)rather than global search(as crossover in GA)to find solutions for optimization problems. Compared with the GA

the BSWA is capable of preserving diversity and avoiding premature convergence

and converges faster. These properties suggest that the BSWA is a useful method for solving complicated optimization problems. Simulation results show that the best known solutions of 72.73% of the 55 standard 0-1 knapsack problems can be found by the BSWA in each of the 50 independent runs

and the final solutions found by the BSWA for the other problems are very close to the best known ones.

关键词

Keywords

references

玄光男,程润伟.遗传算法与工程优化 [M].于歆杰,周根贵, 译.北京:清华大学出版社,2004:55-60.

MARTELLO S, PISINGER D, TOTH P. New trends in exact algorithms for the 0-1 knapsack problem[J]. European Journal of Operational Research, 2000,123(2):325-332.

AKCAY Y, LI Haijun, XU S H.Greedy algorithm for the general multidimensional knapsack problem [J]. Annals of Operations Research, 2007,150(1):17-29.

CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics, 1998, 4(1):63-86.

杜海峰, 庄健, 张进华,等.用于函数优化的小世界优化算法[J]. 西安交通大学学报, 2005, 39(9):1011-1015.

DU Haifeng, ZHUANG Jian, ZHANG Jinhua, et al. Small-world phenomenon for function optimization [J]. Journal of Xi'an Jiaotong University, 2005, 39(9):1011-1015.

MICHALEWICZ Z. Genetic algorithms+data structures=evolution programs [M]. 2nd ed. Berlin,Grermany: Spring-Verlag, 1994.

BEASLEY J E. OR-library: distribution test problems by electronic mail [J]. Journal of Operational Research Society, 1990, 41(11): 1069-1072.

KHURI S, BÄCK T, HEITKÖTTER J. The zero/one multiple knapsack problem and genetic algorithms[C]∥Proceedings of the 1994 ACM Symposium on Applied Computing. New York, USA: ACM Press, 1994: 88-193.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种具有跟踪替代特征的小世界算法

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

冷库水平空气幕热湿阻隔性能数值模拟研究