Yeni Bir Parçacık Sürü Optimizasyon Algoritması

Abstract

Parçacık Sürü Optimizasyonu (Particle Swarm Optimization) (PSO) 1995’te Dr. Eberhart ve Dr. Kennedy tarafından geliştirilmiş popülasyon temelli sezgisel bir optimizasyon tekniğidir. Bu tekniğin bilinen dezavantajı, gerçek optimumu bulmadan önce erken yakınsama sergilenmesidir. Bu çalışmada, literatürde geleneksel hale gelen ve yeni parçacıkları popülasyona yeniden enjekte etmeyi öneren yöntemlere karşın, parçacıkları harici belleklerden alınan bilgilere göre yönlendiren yeni bir parçacık sürü optimizasyon algoritmasını sunmaktadır. Bunun için, parçacığın harici bellekteki parçacıklar arasından, parçacığa en yakın olan en iyi ve en kötü parçacığa uzaklığı hesaplanıp bir katsayi üretilmektedir. Sonra her parçacık için hız bileşenini hesaplarken bu katsayı belli bir olasılıkla mevcut hıza eklenmektedir. Ayrıca randomize bir üst ve alt sınır inertia için tanınmaktadır. Algoritmada inertia bileşeni üst sınırden başlayıp ve her parçacığı değerlendirdikten sonra küçük bir değerle non-linear bir şekilde azaltılmaktadır. Inertia bileşeni randomize alt sınıra ulaştığı zaman, bu bileşenin değeri randomize üst sınırın değeriyle sıfırlamaktadır. Çıkan PSO evrensel optima’yi orijinal PSO’den daha hızlı bulmaktadır. Bu algoritma en güncel PSO’ların arasında olan CLPSO algoritmasından daha hızlı olduğunu ve daha kaliteli çözümler ürettiğini ortaya çıkarılmıştır. Ayrıca literatürde en iyi ve güncel optimizasyon algoritmaların arasında olan CMA-ES algoritması de kıyaslamak amacıyla seçilmiştir. Deneylerin sonucunda, CMA-ES’in genelde PSO’den daha iyi olmasına rağmen, bazi durumlarda, sunulan yöntemin daha üstün bir performans sergilediği ortaya çıkarılmıştır. Evrensel optima’yı gösteren evrensel bir topolojinin eksik olduğu veya havzasının çeker hacmı küçük olan problemlerde, sunulan algoritma daha hızlı davrandığı gösterilmiştir. Deneyler, standart kriter olan fonksyonlar ve simülatör ortamındaki Aldebaran NAO robotun kick hareketi için uygulamaktadır.

Particle Swarm Optimization (PSO) (Kennedy and Eberhart, 1995), which is a population-based global search method is known to suffer from premature convergence prior to discovering the true global minimizer. In this thesis, a novel memory-based method is proposed which aims to guide the particles through the information deduced from the external memory contents rather than to re-inject them into the population. This is done by calculating a coefficient, based on the distance of the current particle to the closest best and closest worst particles in the external memory at each iteration. Later, when updating the velocity component, this coefficient is added to the current velocity of the particle with a certain probability. Also randomized upper bound and lower bound values have been defined for the inertia component. The algorithm starts with the upper bound value of the inertia. At each particle evaluation the inertia is decreased non-linearly with a small value and when its value reaches the lower bound, the inertia value is reset to its upper bound. The resulting PSO finds the global optima much faster than the original PSO and it have been shown that it also performs better compared with a recent improvement of PSO, CLSPO namely. A state-of-the-art algorithm, CMA-ES (Covariance Matrix Adaptation Evolutionary Strategy), has also been chosen for comparison purposes. It has been shown by experiments that although the CMA-ES shows a better performance than that of our algorithm, in some cases where the overall topology pointing to the global optimum is missing and the attractor volume of global optimum is small, our algorithm performs better and finds the desired optimum value of the function in lesser evaluation counts. The tests have been consucted on standard benchmark functions as well as a simulation of the Aldebaran NAO robot for developing a kick action.