Kuadratik atama problemlerinin çözümünde ayrık birey-koloni optimizasyonu modeli
Discrete particle swarm optimization algorithm for the quadratic assignment problem
Yazar: METİN ŞATIR
Danışman: PROF. DR. EKREM MANİSALI
İstanbul Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2008
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Bu tezde, zor atama problemlerinden olan kuadratik atama problemlerinin çözümünde yeni bir yaklaşım ele alınmıştır. Çözüm yöntemi olarak, son yıllarda hızla gelişen koloni temelli sezgisel yöntemlerden biri olan ayrık birey-koloni optimizasyonu kullanılmıştır.Koloni temelli bir meta sezgisel yaklaşım olan ayrık birey-koloni optimizasyonu yöntemi, kuş, balık ve böcek kolonilerinin sosyal davranışlarından esinlenerek geliştirilmiş ve optimizasyon problemlerinin çözümüne uyarlanmıştır. Ayrık birey-koloni optimizasyonunda aday çözüm, birey olarak nitelendirilir ve koloni içerisindeki bir kuş, bir balık veya bir böcek olarak düşünülebilir. Koloni ise, çözüm uzayını keşfetmek için beraberce hareket eder. Her bir bireyin bir amaç fonksiyon değeri vardır ve hız vektörü yardımıyla en iyi çözümü bulmaya çalışır. Bireyler ise, problem uzayında birbirleriyle bilgi paylaşımında bulunarak dolaşırlar. Bu yöntemde, her bir bireyin başlangıç değerleri rastgele oluşturulur ve her bir iterasyon için güncellenir.Kuadratik atama probleminde, birbiri arasındaki iş akışları tanımlanmış n işlem merkezinin, aralarındaki mesafeleri tanımlanmış n yerleşme noktasına atanması işlemi olarak tanımlanabilir. Amaç, iş akışı ve mesafe parametrelerini kullanarak, katedilen toplam mesafeyi minimum yapacak şekilde, işlem merkezlerinin uygun yerleşme noktalarına atanmasıdır.Bu tezde, ilk olarak kuadratik atama problemleri için ayrık birey-koloni optimizasyonu, sürekli birey-koloni optimizasyonu ve genetik algoritma yöntemleri ile çözüm algoritmaları tasarlanmış ve ?toplam mesafe? başarım ölçütüne göre literatürde yer alan test problemleri üzerindeki performansları incelenmiştir. İkinci olarak, ayrık birey-koloni optimizasyonu, sürekli birey-koloni optimizasyonu ve genetik algoritma modellerinin toplam mesafe başarım ölçütüne göre elde edilen sonuçları % 5, % 1 ve ? 5, ? 1 anlamlılık düzeylerinde istatistiksel olarak karşılaştırılıp incelenmiştir. Üçüncü olarak, ayrık birey-koloni optimizasyonu, sürekli birey-koloni optimizasyonu ve genetik algoritma modelleri ?çalışma zamanı? başarım ölçütüne göre literatürde yer alan test problemleri üzerindeki performansları incelenmiştir. Sonuçta, ayrık birey-koloni optimizasyonunun diğer yöntemlerden daha iyi performans gösterdiği sonucuna ulaşılmıştır.

Abstract:
In this dissertation, a new meta-heuristic technique called Discrete Particle Swarm Optimization (DPSO) is applied to Quadratic Assignment problem (QAP), which is one of the hardest combinatorial optimization problems.Discrete Particle Swarm Optimization (DPSO) is one of the population based optimization technique inspired by social behavior of bird flocking, insect flocking and fish schooling. DPSO inventers were inspired of such natural process based scenarios to solve the optimization problems. In DPSO, each single solution, called a particle, is considered as a bird, the group becomes a swarm (population) and the search space is the area to explore. Each particle has a fitness value calculated by a fitness function, and a velocity of flying towards the optimum. All particles fly across the problem space following the particle nearest to the optimum. DPSO starts with initial population of solutions, which is updated iteration-by-iteration.The quadratic assignment problem (QAP) is concerned with assigning a set of facilities to a set locations with given distances between the locations and the flows between the facilities. The objective is to find a placement of the facilities on locations to minimize the sum of the products between flows and distances.First of all, a DPSO, a CPSO) and a genetic algorithm (GA) model for the QAP are developed and applied to the well-known benchmark suites in the literature with the ?total distance criterion?. Secondly, DPSO, CPSO and GA model results are compared statistically at 5 %, 1 %, 5 ? and 1 ? significant levels. Thirdly, a DPSO, a CPSO and a GA model for the quadratic assignment problem(QAP) are developed and applied to the well-known benchmark suites in the literature with the? CPU time criterion?.It is concluded that, DPSO results are better than CPSO and GA results over the 130 benchmark problems.