0-1 problem uzayları için kuantum tabanlı yerel arama ile güçlendirilmiş parçacık sürüsü optimizasyonu

Öz

Parçacık Sürü Optimizasyonu (PSO), problem çözmede balık veya kuş sürülerinin hareketlerini taklit eden, oldukça bilinen sürü zekâsı tabanlı bir algoritmadır. İlk olarak kısıtsız global optimizasyon problemlerini çözmek için önerilse de, çeşitli problem tiplerini içeren çok sayıda PSO çalışması mevcuttur. Fakat bununla birlikte, ilgili bilimsel yazından görülebileceği gibi, diğer uygulama türleriyle karşılaştırıldığında, kesikli ve 0-1 yapıdaki PSO uygulamaları görece daha az sayıdadır. Bu bağlamda, mevcut araştırmada, kuantum tabanlı yerel arama yordamı ile güçlendirilmiş bir 0-1 PSO modifikasyonu getirilmiştir. Bahsedilen kuantum tabanlı prosedür, algoritma tarafından bulunan eniyi çözüm etrafında üretilen bir küre içinde konumlanan ve kuantum parçacıkları olarak adlandırılan rastgele dağıtılmış parçacıklar üretir. Ardından bu parçacıklar, bulunan eniyi çözüm üzerinde olası iyileştirmeler sağlayabilmek için yerel arama amacıyla kullanılır. Önerilen yaklaşımın performansı, bu alanda sıkça kullanılan Bir-Enb, Aldatıcı, Plato ve Kral Yolu fonksiyonlarından oluşan bir 0-1 problem seti kullanılarak test edilmiştir. Deneysel çalışma, önerilen yaklaşımın 0-1 problemlerdeki etkinliğini göstermektedir.

Anahtar Kelimeler

• Metasezgiseller,Parçacık Sürüsü Optimizasyonu,0-1 optimizasyon,Kuantum parçacıkları

A quantum based local search enhanced particle swarm optimization for binary spaces

Abstract

Particle Swarm Optimization (PSO) is a well-known swarm intelligence-based algorithm that simulates the movements of school or bird flocks in problem solving. Although it is first introduced to solve unconstrained global optimization problems, there are numerous reported publications of PSO involving various types of problems. However, as one can see from the related literature, compared to other types of implementations, discrete and binary PSO applications are relatively fewer in number. In this context, in the present work, a 0-1 PSO modification enhanced with a quantum-based local search procedure is developed. The mentioned quantum-based procedure generates randomly scattered particles referred to as quantum particles located within a sphere that is generated around the best-found solution by the algorithm. Next, these particles are used for local search to achieve possible improvements on the best-found solution. The performance of the proposed approach is tested by using a 0-1 problem suite consisting of the commonly used One-Max, Deceptive, Plateau and Royal Road functions. Experimental study shows the effectiveness of the proposed approach in 0-1 problems.

Keywords

• Metaheuristics,Particle swarm optimization,Binary optimization,Quantum particles

References

1. Goldberg DE. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, Massachusetts, USA, Addison-Wesley, 1989.
2. Storn R, Price K. “Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization Over Continuous Spaces”. International Computer Science Institute, Muenchen, Germany, Scientific Report TR-95-012, ICSI, 1995.
3. Eberhart RC, Kennedy J. “A new optimizer using particle swarm theory”. IEEE 1995 International Symposium on Micro Machine and Human Science, Nagoya, Japan, 4-6 October 1995.
4. Karaboga D, Basturk B. “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”. Journal of Global Optimization, 39(3), 459-471, 2007.
5. Yang XS. Firefly Algorithms for Multimodal Optimization. Editors: Watanabe O, Zeugmann T. Lecture Notes in Computer Sciences. 169-178, Berlin, Germany, Springer Heidelberg, 2009.
6. Krishnanand KN, Ghose D. “Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions”. Swarm Intelligence, 3(2), 87-124, 2009.
7. Yang XS. A New Metaheuristic Bat-Inspired Algorithm. Editors: González JR, Pelta DA, Cruz C, Terrazas G, Krasnogor N. Studies in Computational Intelligence. 65-74, Berlin, Germany, Springer Heidelberg, 2010.
8. Yang X-S. Flower Pollination Algorithm for Global Optimization. Editors: Durand-Lose J, Jonoska N. Lecture Notes in Computer Science. 240-249, Berlin, Germany, Springer Heidelberg, 2012.

9. Mirjalili S, Mirjalili SM, Lewis A. “Grey wolf optimizer”. Advances in Engineering Software, 69, 46-61, 2014.
10. Wang GG, Deb S, Cui Z. “Monarch butterfly optimization”. Neural Computing and Applications, in press, 2015.
11. Sun J, Feng B, Xu W. “Particle swarm optimization with particles having quantum behavior”. IEEE Congress on Evolutionary Computation, Portland, OR, USA, 19-23 June, 2004.
12. Sun J, Xu W, Feng B. “A global search strategy of quantum-behaved particle swarm optimization”. IEEE Conference on Cybernetics and Intelligent Systems, Singapore, Singapore, 1-3 December 2004.
13. Xi, M, Sun J, Xu W. “An improved quantum-behaved particle swarm optimization algorithm with weighted mean best position”. Applied Mathematics and Computation, 205(2), 751-759, 2008.
14. Dong H, Yang X, Teng X, Sha Y. “A diversity reserved quantum particle swarm optimization algorithm for MMKP”. International Conference on Computer and Information Science, Okayama, Japan, 26-29 June, 2016.
15. Banks A, Vincent J, Anyakoha C. “A review of particle swarm optimization. Part I: background and development”. Natural Computing, 6(4), 467-484, 2007.
16. Banks A, Vincent J, Anyakoha C. “A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications”. Natural Computing, 7(1), 109-124, 2008.
17. Kennedy J, Eberhart RC. “A discrete binary version of the particle swarm algorithm”. IEEE 1997 International Conference on Systems, Man, and Cybernetics, Orlando, FL, USA, 12-15 October 1997.
18. Ozsoydan FB, Sipahioglu A. “Heuristic solution approaches for the cumulative capacitated vehicle routing problem”. Optimization, 62(10), 1321-1340, 2013.
19. Pan QK, Tasgetiren MF, Liang YC. “A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem”. Computers & Operations Research, 35(9), 2807-2839, 2008.
20. Park JB, Jeong YW, Shin JR, Lee KY, Kim JH. “A hybrid particle swarm optimization employing crossover operation for economic dispatch problems with valve-point effects”. IEEE 2007 International Conference on Intelligent Systems Applications to Power Systems, Toki Messe, Niigata, Japan, 5-8 November 2007.
21. Tseng CT, Liao CJ. “A discrete particle swarm optimization for lot-streaming flowshop scheduling problem”. European Journal of Operational Research, 191(2), 360-373, 2008.
22. Marinakis Y, Marinaki M, Dounias G. “A hybrid particle swarm optimization algorithm for the vehicle routing problem”. Engineering Applications of Artificial Intelligence, 23(4), 463-472, 2010.
23. Marinakis Y, Marinaki M. “A hybrid genetic-particle swarm optimization algorithm for the vehicle routing problem”. Expert Systems with Applications, 37(2), 1446-1455, 2010.
24. Lian Z, Gu X, Jiao B. “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan”. Applied Mathematics and Computation, 175(1), 773-785, 2006.
25. Zhang G, Dou M, Wang S. “Hybrid genetic algorithm with particle swarm optimization technique”. IEEE 2009 International Conference on Computational Intelligence and Security, Beijing, China, 11-14 December 2009.
26. Su D, Xu W, Sun J. “Quantum-behaved particle swarm optimization with crossover operator”. IEEE 2009 International Conference on Wireless Networks and Information Systems, Shanghai, China, 28-29 December 2009.
27. Kennedy J. Particle Swarm Optimization. Editors: Sammut C, Webb GI. Encyclopedia of Machine Learning. 760-766, US, Springer, 2011.
28. Blackwell TM, Bentley PJ. “Dynamic search with charged swarms”. GECCO 2002 Genetic and Evolutionary Computation Conference, New York, USA, 9-13 July, 2002.
29. Blackwell T, Branke J. Multi-Swarm Optimization in Dynamic Environments. Editors: Raidl G, Cagnoni S, Branke J, Corne D, Drechsler R, Jin Y, Johnson C, Machado P, Marchiori E, Rothlauf F, Smith G, Squillero G. Applications of Evolutionary Computing. 489-500, Heidelberg, Berlin, Germany, Springer, 2004.
30. Blackwell T, Branke J, Li X. Particle swarms for dynamic optimization problems. Editors: Blum C, Merkle D. Swarm Intelligence. 193-217, Heidelberg, Berlin, Germany, Springer, 2008.
31. Wang H, Wang D, Yang S. “A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems.” Soft Computing, 13(8-9), 763-780, 2009.
32. Calderín JF, Masegosa AD, Pelta DA. “Algorithm portfolio based scheme for dynamic optimization problems”. International Journal of Computational Intelligence Systems, 8(4), 667-689, 2015.