JSW 2014 Vol.9(1): 104-110 ISSN: 1796-217X
doi: 10.4304/jsw.9.1.104-110
doi: 10.4304/jsw.9.1.104-110
Estimation of Distribution Algorithms for Knapsack Problem
Shang Gao1, Ling Qiu2, Cungen Cao3
1School of Computer Science and Technology, Jiangsu University of Science and Technology, Zhenjiang 212003, China
2Artificial Intelligence of Key Laboratory of Sichuan Province, Sichuan University of Science and Engineering, Zigong 643000,China
3Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China
Abstract—Estimation of distribution algorithms ( EDAs ) is a new kind of evolution algorithm. In EDAs , through the statistics of the information of selected individuals in current group, the probability of the individual distribution in next generation is given and the next generation of group is formed by random sampling. A wide range of mathematical model of the knapsack problem are proposed. In this paper, the EDAs is applied to solve the knapsack problem. The influence of several strategies, such as numbers of population and better population selection proportions are analyzed. Simulation results show that the EDAs is reliable and effective for solving the knapsack problem. The Maltab code is given also. It can easily be modified for any combinatorial problem for which we have no good specialized algorithm.
Index Terms—estimation distribution algorithm, knapsack problem, genetic algorithm
2Artificial Intelligence of Key Laboratory of Sichuan Province, Sichuan University of Science and Engineering, Zigong 643000,China
3Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China
Abstract—Estimation of distribution algorithms ( EDAs ) is a new kind of evolution algorithm. In EDAs , through the statistics of the information of selected individuals in current group, the probability of the individual distribution in next generation is given and the next generation of group is formed by random sampling. A wide range of mathematical model of the knapsack problem are proposed. In this paper, the EDAs is applied to solve the knapsack problem. The influence of several strategies, such as numbers of population and better population selection proportions are analyzed. Simulation results show that the EDAs is reliable and effective for solving the knapsack problem. The Maltab code is given also. It can easily be modified for any combinatorial problem for which we have no good specialized algorithm.
Index Terms—estimation distribution algorithm, knapsack problem, genetic algorithm
Cite: Shang Gao, Ling Qiu, Cungen Cao, "Estimation of Distribution Algorithms for Knapsack Problem," Journal of Software vol. 9, no. 1, pp. 104-110, 2014.
PREVIOUS PAPER
A Public-Key Cryptosystem Based On Stochastic Petri Net
General Information
ISSN: 1796-217X (Online)
Frequency: Monthly (2006-2019); Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
-
Dec 06, 2019 News!
Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec) [Click]
-
Jun 22, 2020 News!
Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP [Click]
-
Feb 19, 2021 News!
Vol 16, No 3 has been published with online version [Click]
-
Jan 28, 2021 News!
[CFP] 2021 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 21-23, 2021 [Click]
-
Feb 19, 2021 News!
The papers published in Vol 16, No 3 have all received dois from Crossref [Click]