A heuristic solution algorithm to quadratic assignment problem
Kareli atama problemleri için sezgisel yaklaşım
- Tez No: 275871
- Danışmanlar: YRD. DOÇ. DR. SEROL BULKAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Kareli Atama Problemleri, matematikteki tesis yerleşimi problemleri kategorisinden eniyileme veya yöneylem araştırması dalı içinde kombinatoryal eniyileme problemlerinden biridir. Tesis içi planı ve yerleşim çalışmalarında çoğunlukla görülen atama probleminin özel bir halidir. Kareli Atama Problemleri'nin klasik atama problemlerinden farkı doğrusal olmayan amaç fonksiyonunu esas alan atama çiftleri arasında bir etkileşim olmasıdır. Tesis yerleşim tasarımı problemleri, çeşitli akış ilişkilerinin de değerlendirilmesini gerektiren problemlerdir ve literatürde Kareli Atama Problemleri olarak çözümlendirilmesi yoluna sıkça gidilmiştir. Kareli Atama Problemi NP-zor sınıfında olan en zor problemlerden biridir. Kareli Atama Problemi olarak modellenen problemler için yeniden çözme tekniklerinden yola çıkılarak, en iyi sonuç elde edilenden sezgisel yaklaşıma ve yarı sezgisel yaklaşıma kadar farklı birçok metot mevcuttur. En iyi sonuç elde edilen metotlarla problemleri çözmek çok uzun zaman gerektirmektedir. Bu çalışmada, literatürde Kareli Atama Problemleri için en iyi sonuç elde edilen metotlar, en iyi sonucu bulunamayan problemler için geliştirilen sezgisel, yarı sezgisel birçok metot ve bunların Kareli Atama Problemi örnekleri üzerinde çözülebilirliği ve yeni geliştirilen yöntemler incelenmiştir. Bu çalışma, Kareli Atama problemlerinin sezgisel bir optimizasyon tekniği olan genetik algoritma ve komşuluk yaklaşımı ile çözümünü içermektedir. Çalışmada, geliştirilen genetik algoritma yaklaşımının Kareli Atama Problemi örnekleri üzerinde çözülebilirliği incelenmiştir.
Özet (Çeviri)
The quadratic assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. The quadratic assignment problem is a special kind of assignment problem frequently seen in layout and location studies. The main difference between this problem and the classic assignment problem is that in this problem there are interactions between assignment pairs, leading to a non-linear objective function. Facility layout problems are problems that are needed the assessment of various flow relationship and in the literature Quadratic Assignment Problem is frequently used for solving these problems. This problem is one of the most difficult problems in the NP-hard class, which implies that finding a polynomial time algorithm to solve it is unlikely. In regards to the resolution techniques modeled as quadratic assignment problem, there are different methods ranging from exact to heuristic and meta-heuristic ones. It takes a long time to have an optimum solution with exact algorithms, so several heuristics have been proposed for handling near optimum solutions. In this thesis, a genetic algorithm as a heuristic optimization technique and neighborhood approximation is developed. This new algorithm?s solvability in benchmark problem instances is tested and results are listed.
Benzer Tezler
- A stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture
Çok çekirdekli bir mimari üzerinde karesel atama problemi için iş birliği yapan durgunluk bilinçli yerel arama kaçış algoritması
YAĞMUR AKSAN
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
- A hybrid algorithm based on whale optimization algorithm and simulated annealing and its applications for quadratic assignment problem
Benzetilmiş tavlamalı hibrit balina optimizasyon algoritmasının karesel atama problemine uygulanması
ADEM BÜYÜKÖZER
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ EMRULLAH SONUÇ
- Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms
Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma
MELİKE ÖZTÜRK
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
PROF. DR. ÇİĞDEM ALABAŞ USLU
- Kuadratik atama problemlerinin çözümünde ayrık birey-koloni optimizasyonu modeli
Discrete particle swarm optimization algorithm for the quadratic assignment problem
METİN ŞATIR
Doktora
Türkçe
2008
Endüstri ve Endüstri Mühendisliğiİstanbul ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. EKREM MANİSALI
- Birleşi eniyileme problemleri için oto-kontrollü yerel arama yöntemi
Self-controlled local search method for combinatorial optimization problems
ÇİĞDEM ALABAŞ
Doktora
Türkçe
2004
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. BERNA DENGİZ