An immune-based response particle swarm optimizer for knapsack problems in dynamic environments
- PDF / 1,637,605 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 56 Downloads / 170 Views
METHODOLOGIES AND APPLICATION
An immune-based response particle swarm optimizer for knapsack problems in dynamic environments Huihong Wu1 · Shuqu Qian1 · Yanmin Liu2 · Dong Wang1 · Benhua Guo1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper proposes a novel binary particle swarm optimization algorithm (called IRBPSO) to address high-dimensional knapsack problems in dynamic environments (DKPs). The IRBPSO integrates an immune-based response strategy into the basic binary particle swarm optimization algorithm for improving the quantity of evolutional particles in high-dimensional decision space. In order to enhance the convergence speed of the IRBPSO in the current environment, the particles with high fitness values are cloned and mutated. In addition, an external archive is designed to store the elite from the current generation. To maintain the diversity of elites in the external archive, the elite of current generation will replace the worst one in the external archive if and only if it differs from any of the existing particles in the external archive based on the Hamming distance measurement when the archive is due to update. In this way, the external archive can store diversiform elites for previous environments as much as possible, and so as to the stored elites are utilized to transfer historical information to new environment for assisting to solve the new optimization problem. Moreover, the environmental reaction scheme is also investigated in order to improve the ability of adapting to different kinds of dynamic environments. Experimental results on a series of DKPs with different randomly generated data sets indicate that the IRBPSO can faster track the changing environments and manifest superior statistical performance, when compared with peer optimization algorithms. Keywords Dynamic knapsack problems · Particle swarm optimization · Immune response · External archive · Environmental reaction
1 Introduction Most real-world optimization problems are not static. Their objective function, decision variables, or environmental parameters may change over time, such as vehicle routing problems (Baker and Ayechew 2003), dynamic knapsack problems (Calderín et al. 2015), portfolio optimization (Mendes et al. 2016), shortest path problems (Baykasoˇglu and Ozsoydan 2016), and dynamic scheduling problem in manufacturing system (Baykasoˇglu 2018; Baykasoˇglu and Communicated by V. Loia.
B
Huihong Wu [email protected] Shuqu Qian [email protected]
1
School of Sciences, Anshun University, Anshun 561000, China
2
School of Mathematics and Computer Science, Zunyi Normal College, Zunyi 563002, China
Ozsoydan 2018b). These problems are often subject to dynamic environments, where the fitness landscape and/or the parameters may change over time. These types of problems, called dynamic optimization problems or optimization problems in dynamic environments (DOPs), have attracted considerable attention and research interest for the community of evolution algorithms (EAs). Compared with the
Data Loading...
