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
- Sınır koşulunda özdeğer parametresi içeren regüler Sturm-Liouville problemlerinin asimptotik çözümleri ve Green fonksiyonları
Asymptotic solutions of eigenfunctions and Green's functions for regular Sturm-Liouville problems having eigenvalue parameter in the boundary condition
AYŞE KABATAŞ
Doktora
İngilizce
2015
MatematikKaradeniz Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. HASKIZ COŞKUN
- Buğday kabuğu biyosilikasından nanogözenekli silika malzeme üretimi ve sulu çözeltilerden kurşun gideriminde kullanılması
Removal of lead from aqueous solutions by using nanoporous silica materials obtained from wheat husk biosilica
PINAR TERZİOĞLU
Doktora
İngilizce
2015
BiyomühendislikYıldız Teknik ÜniversitesiBiyomühendislik Ana Bilim Dalı
PROF. DR. SEVİL YÜCEL
DOÇ. DR. MEHMET ÖZTÜRK
- Genetik algoritma kullanarak hisse senedi portföy optimizasyonu: BİST - 30'da bir uygulama
Portfolio optimzation using genetic algorithm: An application in BIST - 30
AHMET ÇANKAL
Yüksek Lisans
Türkçe
2015
EkonomiOsmaniye Korkut Ata ÜniversitesiYönetim Bilişim Sistemleri Ana Bilim Dalı
YRD. DOÇ. DR. EMRE YAKUT
- Modeling and active steering control of articulated vehicles with multi-axle semi-trailers
Çekici ve çok akslı yarı treyler kombinasyonlarının modellenmesi ve aktif yönlendirme kontrolü
MECİD UĞUR DİLBEROĞLU
Yüksek Lisans
İngilizce
2015
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. YAVUZ SAMİM ÜNLÜSOY
- Modeling, simulation, and active control of tractor-semitrailer combinations
Çekici-yarıtreyler kombinasyonlarının modellenmesi, simülasyonu ve aktif kontrolü
SİNA ALAMDARİ MİLANİ
Yüksek Lisans
İngilizce
2015
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. YAVUZ SAMİM ÜNLÜSOY