Geri Dön

Kuadratik atama problemlerinin çözümünde ayrık birey-koloni optimizasyonu modeli

Discrete particle swarm optimization algorithm for the quadratic assignment problem

  1. Tez No: 232304
  2. Yazar: METİN ŞATIR
  3. Danışmanlar: PROF. DR. EKREM MANİSALI
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2008
  8. Dil: Türkçe
  9. Üniversite: İstanbul Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. MÜJDE GÜZELKAYA

  2. Inverse optimal control for nonlinear systems

    Doğrusal olmayan sistemler için ters optimal kontrol

    MOAYED ALMOBAIED

    Doktora

    İngilizce

    İngilizce

    2017

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. İBRAHİM EKSİN

    PROF. DR. MÜJDE GÜZELKAYA

  3. 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

    İngilizce

    2021

    Mekatronik Mühendisliğiİstanbul Teknik Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. VOLKAN SEZER

  4. 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

    İngilizce

    2024

    Matematikİstanbul Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BURHANEDDİN İZGİ

  5. 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

    Türkçe

    2019

    Endüstri ve Endüstri MühendisliğiPamukkale Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CAN BERK KALAYCI