Improved genetic algorithm to 0-1 knapsack problem

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (34): 44-46.

• 研究、探讨 • Previous Articles Next Articles

Improved genetic algorithm to 0-1 knapsack problem

LV Xiaofeng1，ZHANG Yongliang2，MA Ling2

1.Department of Armament Science and Technology，Naval Aeronautical and Astronautical University，Yantai，Shangdong 264001，China
2.Brigade of Graduate Student，Naval Aeronautical and Astronautical University，Yantai，Shangdong 264001，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-12-01 Published:2011-12-01

一种求解0-1背包问题的改进遗传算法

吕晓峰1，张勇亮2，马羚2

1.海军航空工程学院兵器科学与技术系，山东烟台 264001
2.海军航空工程学院研究生管理大队，山东烟台 264001

Abstract

Abstract: An improved Genetic Algorithm（GA） is proposed to solve 0-1 Knapsack Problem（KP） considering the deficiency of the Simple GA（SGA） that being easy to “precocity”.A new way to decode is designed to ensure solutions workable according to the way of dual-structure coding，and to revise individuals without corresponding solutions in the population at the same time.And SGA is improved by the Simulated Annealing（SA） algorithm and improved elite selection operator.The advantage of the improved GA in the evolution efficiency and the ability to search the best solution is proved by the simulation results.

Key words: Genetic Algorithm（GA）, Knapsack Problem（KP）, decode way, Simulated Annealing（SA）, elite selection

摘要： 针对传统遗传算法（SGA）容易“早熟”的不足，提出一种求解0-1背包问题（KP）的改进遗传算法。借鉴二重结构编码的解码处理方法设计了一种新解码方法，在保证解可行性的同时修正种群中无对应可行解的个体;采用模拟退火算法和改进的精英选择算子改进SGA。实例仿真结果验证了改进遗传算法在进化效率和最优解搜索能力上的优越性。

关键词: 遗传算法, 背包问题, 解码, 模拟退火, 精英选择

LV Xiaofeng1，ZHANG Yongliang2，MA Ling2. Improved genetic algorithm to 0-1 knapsack problem[J]. Computer Engineering and Applications, 2011, 47(34): 44-46.

吕晓峰1，张勇亮2，马羚2. 一种求解0-1背包问题的改进遗传算法[J]. 计算机工程与应用, 2011, 47(34): 44-46.

[1]	WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2020, 56(7): 57-66.
[2]	QIN Qin, LIANG Chengji. Optimization of Equipment Coordination Scheduling with Considering Buffer Space in Automated Container Terminal [J]. Computer Engineering and Applications, 2020, 56(6): 262-270.
[3]	LIANG Chengji, YU Jian. Research on Dispatching of Container Terminals Quay Crane Scheduling with Interference Constraints [J]. Computer Engineering and Applications, 2020, 56(10): 273-278.
[4]	DONG Hao1, ZHANG Haiping2, LI Zhongjin1, LIU Hui1. Computation Offloading for Service Workflow in Mobile Edge Computing [J]. Computer Engineering and Applications, 2019, 55(2): 36-43.
[5]	XUE Meng, JIANG Shujuan, WANG Rongcun. Systematic review of test data generation based on intelligent optimization algorithm [J]. Computer Engineering and Applications, 2018, 54(17): 16-23.
[6]	LOU Gaoxiang, CAI Zongyan, LIU Qingtao. Application of new hybrid algorithm in mixed model assembly scheduling [J]. Computer Engineering and Applications, 2018, 54(16): 254-259.
[7]	WANG Xinyue, GUO Jianquan. Subsidy strategy model of multi-period closed-loop hybrid system under carbon tax [J]. Computer Engineering and Applications, 2018, 54(14): 236-240.
[8]	LUO Xianglong1，2, ZHANG Shengrui1, NIU Liyao2. Short-term traffic flow prediction based on detector optimal selection [J]. Computer Engineering and Applications, 2017, 53(8): 199-202.
[9]	LIANG Chengji, WU Yu. Simultaneous berth and quay crane scheduling under uncertainty environments in container terminals [J]. Computer Engineering and Applications, 2017, 53(7): 212-219.
[10]	CAO Xiaoning, XUE Han, WANG Yongming. Optimization for control strategy of serial production system with machine breakdowns [J]. Computer Engineering and Applications, 2017, 53(16): 199-204.
[11]	CUI Yongfeng, ZHOU Dingding. Analysis of optimal scheduling model in variable speed environment at night [J]. Computer Engineering and Applications, 2016, 52(9): 239-242.
[12]	XU Xian1，2, LU Xianling1，2, WANG Hongbin1，2. Accelerometer data feature selection for activity recognition based on GA optimization [J]. Computer Engineering and Applications, 2016, 52(6): 139-143.
[13]	LU Yan1, HUI Qiaojuan2. Improved framework for 3D face feature points extraction method based on statistic deformable model [J]. Computer Engineering and Applications, 2016, 52(24): 166-170.
[14]	YAN Han, LIU Juan, ZHOU Xuanyu. Optimal proportion of training data for Chinese coreference resolution [J]. Computer Engineering and Applications, 2016, 52(17): 140-145.
[15]	WANG Lucai, CAO Pengxia, JIANG Xiaolong. Improved method for speech endpoint detection with noise [J]. Computer Engineering and Applications, 2016, 52(15): 162-167.

Improved genetic algorithm to 0-1 knapsack problem

一种求解0-1背包问题的改进遗传算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles 0

Metrics