A continuous and a discrete particle swarm optimization algorithm for uncapacitated facility location problem

Abstract

Bu tezde bir sürekli ve bir kesikli parçacık sürü optimizasyonu (PSO) algoritmasıiyi bilinen bir kesikli problem olan kapasitesiz tesis yerleştirme (UFL) problemleri içinönerilmiştir.PSO, Eberhart ve Kennedy tarafından önerilen ve evrimsel algoritmalara dayananyeni bir sezgisel yöntemdir. Kuş ve balık sürülerinin sosyal iletişimi sırasında oluşanhareketlerinden esinlenilmiş ve şu ana kadar çok çeşitli problemleri çözmek içinbaşvurulmuştur. Diğer taraftan, UFL son kırk yıldır araştırmacılar tarafından çözümyöntemleri önerilen bir konudur. Bu yüzden UFL problemleri için PSO algoritmalarıönerilmiştir. Çözüm kalitesini artırmak için ayrıca bu PSO algoritmalarına birer yerelarama algoritması eklenmiştir. Güvenilir karşılaştırmalar yapabilmek için önerilen PSOalgoritmaları yöneylem araştırmaları kütüphanesindeki karşılaştırma problemlerineuygulanmıştır. Sonuçlar ortaya konulmuş ve literatürdeki optimum değerler ilekarşılaştırılmıştır. Sonuç olarak önerilen PSO algoritmaları optimum sonuçları kabuledilebilir işlem zamanı içinde elde etmiştir.Anahtar Kelimeler: Parçacık Sürü Optimizasyonu, Kapasitesiz Tesis YerleştirmeProblemi, Sürekli PSO, Kesikli PSO

In this paper, a Continuous and a Discrete version of Particle Swarm Optimization(PSO) algorithms proposed for a well known discrete problem, Uncapacitated FacilityLocation (UFL) problem.PSO is one of the recent metaheuristics based on evolutionary algorithms inventedby Eberhart and Kennedy based on the metaphor of social interaction andcommunication such as bird flocking and fish schooling. It has been successfullyapplied to a wide range of applications. On the other hand, developing solution methodsfor the UFL problem has been a hot topic of research for the last 40 years. Thus PSOalgorithms are proposed to solve UFL problems. In order to improve the solutionquality local searches are embedded in the PSO algorithms. To make a confidentialcomparison the proposed PSO algorithms are applied to the benchmark suites collectedfrom OR library. The results are presented and compared with the optimum results inthe literature. It is concluded that the proposed PSO algorithms have found optimumresults in a reosanable CPU time.Keywords: Particle Swarm Optimization, Uncapacitated Facility LocationProblem, Continuous PSO, Discrete PSO