DISCRETE PARTICLE SWARM OPTIMIZATION ALGORITHM BASED ON INFORMATION SHARING MECHANISM
Keywords:
Information sharing mechanisms, Pheromone persistence, Discrete particle swarm optimization, Knapsack problems, Cargo dispensingAbstract
To better solve NP-complete problems, this paper proposes a Discrete Particle Swarm Optimization algorithm based on an Information Sharing Mechanism (ISM-DPSO). The algorithm uses a mechanism of sharing the pheromone of the ant colony algorithm to update particles; the particle swarm threshold function application is initialized. At the same time, to enhance the algorithm's global search ability, a particle swarm is initialized at a certain probability, and on this basis, using a nonlinear dynamic adjusting pheromone persistent rate strategy to guide the information memory. The proposed algorithm is applied to the knapsack problem with single constraints and the vehicle cargo loading problem with multiple constraints, and the optimization results are compared with the basic discrete particle swarm optimization algorithm (DPSO). The experimental results show that the ISM-DPSO algorithm outperforms the DPSO algorithm in terms of both the optimal value and the algorithm's fitted value, and the search results are superior to those of the DPSO algorithm.
References
Kennedy J, Eberhart R. A discrete binary version of the particle swarm algorithm. Proceedings of the 1997 Conference on System, Man, and Cybernetics; 1997 Oct 12-15; Orlando, USA. Piscataway, USA: IEEE; 1997. p.4104-8.
Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks; 1995 Nov 27-Dec 1; Perth, Australia. Piscataway, USA: IEEE; 1995. p. 1942-8.
Zhang G, Jiang J, Xia N, Su Z. Solutions of complicated coalition generation based on discrete particle swarm optimization. Acta Electronica Sinica 2007;35(2):323-7.
Lin Z, Gao W, Wu C, Li Y. Data center network flow scheduling based on DPSO algorithm. Acta Electronica Sinica 2016;44(9):2197-202.
Xu Z, Yang W, Zhang W, Chen S. Multi-objective distribution network reconfiguration based on chain loops and improved binary particle swarm optimization. Power System Protection and Control 2021;49(6):114-23. (In Chinese)
Liu G, Huang Y, Wang X, Guo W, Chen G. Hybrid discrete particle swarm algorithm for X-architecture steiner minimal tree construction with slew constraints. Chinese Journal of Computers 2021; 4(12):2542-59. (In Chinese)
Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Francisco, USA: W. H. Freeman and Company;1979.
Bas E. A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model. Expert Systems with Applications 2011;38(10):12415-22.
Han D, Huang W, Yan Z. Virtual Bidding Strategy in Electricity Market Based on Deep Reinforcement Learning. Proceedings of the CSEE 2022;42(4):1443-54. (In Chinese)
Shih W. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society 1979;30(4):369-78.
Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 1997;11(4): 341-59.
He Y, Wang J, Zhang X, Li H, Liu X. Encoding transformation-based differential evolution algorithm for solving knapsack problem with single continuous variable. Swarm and Evolutionary Computation 2019;50: 981-92.
Jiang H, Guo T, Yang Z. Research progress of vehicle routing problem. Acta Electronica Sinica 2022;50(2):480-92.
He Y, Wang X, Li W, Zhang X, Chen Y. Research on genetic algorithms for the discounted {0-1} knapsack problem. Chinese Journal of Computers 2016; 39(12):2614-30. (In Chinese)
Ren Z, Zhao S, Huang S, Liang Y. Hybrid optimization algorithm of ant colony optimization and Lagrangian relaxation for solving multidimensional knapsack problem. Control and Decision 2016; 31(7):1178-84. (In Chinese)
Li Y, Zhang J, Liu Q, Zhang W. Advanced artificial fish swarm algorithm for large scale multiple knapsack problem. Systems Engineering and Electronics 2018; 40(3):710-6.
Liu Y, Ma L. Solving 0-1 knapsack problem by fuzzy particle swarm optimization. Application Research of Computers 2011;28(11):4026-31. (In Chinese)
Geng Y, Wu F S. Research on knapsack problem based on the hybrid algorithm of particle swarm optimization and simulated annealing. Control Engineering of China 2019;26(5):991-6. (In Chinese)
Xu Q, Wu T, Wang W. Nonlinear dissipative particle swarm algorithm and its applications. IEEE ACCESS 2021;(9):158862-71.
Xu Q, Amdee N, Sangsongfa A. Design study of high-power PV grid-connected inverter system based on the particle swarm algorithm. Primera Scientific Engineering 2024;5(3):16-38.
Xiao J, Yu X, Zhou G, Sun K, Zhou Z. An improved ant colony algorithm for indoor AGV path planning. Chinese Journal of Scientific Instrument 2022;43(3):277-85. (In Chinese)
Ma H, Qiu X. A heuristic algorithm for the ordinary scattered cargoes’ container-loading question. In: Liu R, Zhang J, Guan C, editors. Logistics: The Emerging Frontiers of Transportation and Development in China. Reston, USA: ASCE; 2009. p. 4790-95.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Kasem Bundit University
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
*Copyright
The article has been published in Kasem Bundit Engineering Journal (KBEJ) is the copyright of the Kasem Bundit University. Do not bring all of the messages or republished except permission from the university.
* Responsibility
If the article is published as an article that infringes the copyright or has the wrong content the author of article must be responsible.
