Alt küme bulma tabanlı ayrık optimizasyon problemleri için ayrık parçacık sürü optimizasyonu modelleri

Abstract

Parçacık sürü optimizasyonu (PSO) sürekli optimizasyon problemleri için geliştirilmiş bir metasezgiseldir. PSO, daha sonra bazı ayrık optimizasyon problemleri için de uygulanmıştır. Yaptığımız araştırmalarda PSO'nun alt küme tabanlı ayrık optimizasyon problemlerine uygulandığına rastlanmamıştır. Bu çalışmada PSO'nun bu tip problemlere etkin bir şekilde uygulanabilirliği araştırılmıştır.Çalışma kapsamında alt küme tabanlı ayrık optimizasyon problemlerinin çoğunu kapsayan büyüme ve küçülme amaçlayan alt küme problemleri tanımlanmış ve bu problemlere uygulanabilecek bir PSO modeli önerilmiştir. Geliştirilen model uygulanılarak üç problem için çözüm üreten algoritmalar sunulmuştur. Bu problemler maksimum klik problemi(MKP), çok boyutlu sırt çantası problemi(ÇSP) ve kenar kapsama problemidir (KKP).Karşılaştırma problemleri ile yapılan testler sonucunda modelin MKP ve KKP üzerinde başarı ile çalıştığı gözlemlenmiştir. Bu problemler için geliştirilen algoritmalar çözüm kalitesi açısından diğer metasezgisellerden daha iyi sonuçlar vermiştir. ÇSP için ise iyi sonuçlar alınamamıştır. Modelin ilk iki problem için başarı ile çalışırken son problem için başarılı olmamasının nedenleri sorgulanmıştır.

Particle Swarm Optimization (PSO) is a metaheuristic intended for continuous optimization problems. Later, PSO is applied to some discrete optimization problems as well. Application of PSO to any subset selection based problem is not observed during our research. In this work, a PSO model applicable to such problems is introduced.In this work, ?aiming increase and decrease? subset problems which cover most of the subset selection problems are defined and a PSO model is proposed for these problems. This model is applied to three such problems. These problems are maximum clique, multi-dimensional knapsack, and vertex cover problems.It has been observed that the model is applicable successfully on maximum clique and vertex cover problems. The algorithms developed for these problems have given better results than other metaheuristics in terms of solution quality. For multi-dimensional knapsack problem, good results could not been attained. The reason why the model is applicable for the first two problems and why it is not for the last one was questionized.