Kuadratik atama problemlerinin çözümünde ayrık birey-koloni optimizasyonu modeli
Discrete particle swarm optimization algorithm for the quadratic assignment problem
- Tez No: 232304
- Danışmanlar: PROF. DR. EKREM MANİSALI
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: Türkçe
- Üniversite: İstanbul Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 209
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Tracking control methodologies for a quadrotor UAV
Dört rotorlu bir İHA için yol takibi kontrol yöntemleri
BORA BAYRAKTAROĞLU
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJDE GÜZELKAYA
- Inverse optimal control for nonlinear systems
Doğrusal olmayan sistemler için ters optimal kontrol
MOAYED ALMOBAIED
Doktora
İngilizce
2017
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM EKSİN
PROF. DR. MÜJDE GÜZELKAYA
- Energy-efficient velocity trajectory optimization using dynamic programming for electric vehicles
Elektrikli araçlar için dinamik programlama kullanılarak enerji verimli hız yörünge optimizasyonu
ABDULLAH KIZIL
Yüksek Lisans
İngilizce
2021
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. VOLKAN SEZER
- Matrix norm based-solution methods and machine learning: Stochastic games and their applications
Matris norm tabanlı çözüm yöntemleri ve makine öğrenmesi: Stokastik oyunlar ve uygulamaları
MURAT ÖZKAYA
Doktora
İngilizce
2024
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DOÇ. DR. BURHANEDDİN İZGİ
- Eleman sayısı kısıtlı portföy optimizasyonu için değişken komşuluk arama algoritması temelli bir çözüm yaklaşımı
A variable neighborhood search based solution approach for cardinality constraint portfolio optimization
MEHMET ANIL AKBAY
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiPamukkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. CAN BERK KALAYCI