A Small World Algorithm for Multi-Dimensional Knapsack Problems

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

您当前的位置：

首页 >

文章列表页 >

A Small World Algorithm for Multi-Dimensional Knapsack Problems

更新时间：2025-12-08

- A Small World Algorithm for Multi-Dimensional Knapsack Problems
- Vol. 43, Issue 2, Pages: 10-14(2009)
- 作者机构：
  
  西安交通大学管理学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP183
- Online First：10 February 2009，
  
  Published：2009
- 稿件说明：
移动端阅览
杜巍 1, 李树茁 2, 陈煜聪 3. A Small World Algorithm for Multi-Dimensional Knapsack Problems[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Small-World Algorithm with the Replacing and Tracking Characters

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

Related Author

陈煜聪 1

杨斌 1

杜海峰 1

邵頡 2

庄健 1

Related Institution

School of Mechanical Engineering, Xi'an Jiaotong University

⁰