- Koya Ihara ORCID:orcid.org/0000-0002-5473-086411,12 &
- Shohei Kato ORCID:orcid.org/0000-0003-4130-272911,12
Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 12576))
Included in the following conference series:
1470Accesses
Abstract
Some metaheuristic algorithms such as particle swarm optimization (PSO) are extended and have been shown to perform very well in a wide range of optimization domains though they are originally designed for continuous optimization. In discrete optimization, some extended algorithms handle continuous parameters of a probability distribution, which assumes variable values of a candidate solution instead of directly handling discrete variables. These distribution-based discrete PSOs (DDPSO) sample a variable value from a distribution for every variable to generate a candidate solution. This procedure can be considered as a kind of local search centered on anintended solution, which has the highest probability to be generated. Step length from the intended solution increases proportionally and the probability of producing an intended solution decreases exponentially in high-dimensional problems. We propose a novel sampling method to control the step size for DDPSO. In this paper, we describe our new sampling method to control the step size with Lévy distribution in a similar way to Lévy flight. The proposed method is applied to three representative methods of DDPSOs and performance is compared with original algorithms. In our discrete optimization experiments, we demonstrate that our algorithm increases DDPSO’s search performance and robustness to dimensionality.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 10295
- Price includes VAT (Japan)
- Softcover Book
- JPY 12869
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ardizzon, G., Cavazzini, G., Pavesi, G.: Adaptive acceleration coefficients for a new search diversification strategy in particle swarm optimization algorithms. Inf. Sci.299, 337–378 (2015)
Brown, C.T., Liebovitch, L.S., Glendon, R.: Lévy flights in Dobe Ju/’hoansi foraging patterns. Hum. Ecol.35(1), 129–138 (2007)
Chatterjee, S., Sarkar, S., Hore, S., Dey, N., Ashour, A.S., Balas, V.E.: Particle swarm optimization trained neural network for structural failure prediction of multistoried RC buildings. Neural Comput. Appl.28(8), 2005–2016 (2016).https://doi.org/10.1007/s00521-016-2190-2
Eberhart, R.C., Shi, Y.: Comparing inertia weights and constriction factors in particle swarm optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation (CEC), vol. 1, pp. 84–88. IEEE (2000)
Eberhart, R., Kennedy, J.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. Citeseer (1995)
Engelbrecht, A.P.: Fitness function evaluations: a fair stopping condition? In: Proceedings of 2014 IEEE Symposium on Swarm Intelligence (SIS), pp. 1–8. IEEE (2014)
Jensi, R., Jiji, G.W.: An enhanced particle swarm optimization with levy flight for global optimization. Appl. Soft Comput.43, 248–261 (2016)
Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, vol. 5, pp. 4104–4108. IEEE (1997)
Bengoetxea, E., Larrañaga, P., Bloch, I., Perchant, A.: Estimation of distribution algorithms: a new evolutionary computation approach for graph matching problems. In: Figueiredo, M., Zerubia, J., Jain, A.K. (eds.) EMMCVPR 2001. LNCS, vol. 2134, pp. 454–469. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-44745-8_30
Mantegna, R.N.: Fast, accurate algorithm for numerical simulation of levy stable stochastic processes. Phys. Rev. E49(5), 4677 (1994)
Reynolds, A.M., Frye, M.A.: Free-flight odor tracking in drosophila is consistent with an optimal intermittent scale-free search. PLoS ONE2(4), e354 (2007)
Shen, M., Zhan, Z.H., Chen, W.N., Gong, Y.J., Zhang, J., Li, Y.: Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks. IEEE Trans. Industr. Electron.61(12), 7141–7151 (2014)
Strasser, S., Goodman, R., Sheppard, J., Butcher, S.: A new discrete particle swarm optimization algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 53–60. ACM (2016)
Veeramachaneni, K., Osadciw, L., Kamath, G.: Probabilistically driven particle swarms for optimization of multi valued discrete problems: design and analysis. In: IEEE Swarm Intelligence Symposium, pp. 141–149. IEEE (2007)
Wang, Z.J., et al.: Dynamic group learning distributed particle swarm optimization for large-scale optimization and its application in cloud workflow scheduling. IEEE Trans. Cybern.50, 2715–2729 (2019)
Yang, X.S., Deb, S.: Cuckoo search via lévy flights. In: 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), pp. 210–214. IEEE (2009)
Yang, X.S., Deb, S.: Engineering optimisation by cuckoo search. Int. J. Math. Model. Numer. Optim.1(4), 330–343 (2010)
Acknowledgment
This work was supported in part by the Ministry of Education, Culture, Sports, Science and Technology-Japan, Grant–in–Aid for Scientific Research under grant #JP19H01137, #JP19H04025, and #JP20H04018.
Author information
Authors and Affiliations
Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya, 466-8555, Japan
Koya Ihara & Shohei Kato
Frontier Research Institute for Information Science, Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya, 466-8555, Japan
Koya Ihara & Shohei Kato
- Koya Ihara
You can also search for this author inPubMed Google Scholar
- Shohei Kato
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toShohei Kato.
Editor information
Editors and Affiliations
School of Information Technology and Electrical Engineering, University of Queensland, Brisbane, QLD, Australia
Marcus Gallagher
School of Engineering and Information Technology, University of New South Wales, Canberra, ACT, Australia
Nour Moustafa
School of Engineering and Information Technology, University of New South Wales, Canberra, ACT, Australia
Erandi Lakshika
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ihara, K., Kato, S. (2020). Improving Distribution-Based Discrete Particle Swarm Optimization Using Lévy Flight. In: Gallagher, M., Moustafa, N., Lakshika, E. (eds) AI 2020: Advances in Artificial Intelligence. AI 2020. Lecture Notes in Computer Science(), vol 12576. Springer, Cham. https://doi.org/10.1007/978-3-030-64984-5_15
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-64983-8
Online ISBN:978-3-030-64984-5
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative