Evolutionary algorithms for solving DEC-POMDP problems
MO-KGMKS problemlerinin çözümünde evrimsel algoritmalar
- Tez No: 312062
- Danışmanlar: PROF. DR. HÜSEYİN LEVENT AKIN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 131
Özet
Merkezi Olmayan Kısmen Gözlemlenebilir Markov Karar Süreci (MO-KGMKS)modeli, kısmen gözlemlenebilir ortamlarda çoklu etmen planlama problemini adreslemektedir.Modelin NEXP-complete kompleksliğe sahip olmasından dolayı, sadece küçük boyutluproblemler optimal bir şekilde çözülebilir. Bu sebepten dolayı, birçok araştırmacıdaha büyük boyutlu problemler için en iyiye yakın çözüm üretebilecek yaklaşık çözümyordamları üzerine yoğunlaşmıştır. Bununla birlikte, şimdiye kadar geliştirilen yaklaşıkçözüm yordamları bile büyük boyutlu problemleri ancak az sayıda adım için çözebilmektedir.Bunun bir nedeni etmen stratejilerini temsil ederken ve strateji uzayını tararkenkiüssel hafıza gereksinimidir. Bu tezde sonlu adımlı MO-KGMKS problemlerini yaklaşıkolarak çözmek için dört yeni yaklaşım sunuyoruz. ?Ilk yaklaşım, MAP, MO-KGMKS problemleriniKGMKS problemi olarak modelleme ve daha sonrasında verimli bir KGMKSçözümcüsü ile çözme temellidir. Diğer yaklaşımların hepsi, yani ES-BV, ES-OH ve GAFSC,evrimsel yordamların uygulanması temeline dayanmaktadır. ES-BV, MAP yöntemindeolduğu gibi inanç vektörlerini kullanır ve strateji vektörlerini evrimsel stratejileri (ES)kullanarak bulmaya çalışır. ES-OH yaklaşımı gözlem tarihçesini kullanmayı, karar vermekiçin bunu bir sinir ağına girdi yapmayı ve sinir ağlarını eğitmek için ES kullanmayıönerir. GA-FSC yordamı ise stratejileri temsil etmek için sonlu durum kontrolcülerinikullanır ve genetik yordamları kullanarak en iyi stratejiyi arar. Bütün yordamlar en bilinenMO-KGMKS problemlerinde test edilmiştir. Sonuçlarımızı bu konudaki en ileritekniklerle ve birbirleriyle karşılaştırdık. MAP haricinde bu çalışmadan geliştirilen yordamlarınvarolan en iyi yordamlarla karşılaştırılabilir bir performansa sahip olduğunu veGA-FSC kullanılması durumunda problemler için çözüm adım sayısının artırıldığını gösterdik.
Özet (Çeviri)
The Decentralized Partially Observable Markov Decision Process (DEC-POMDP)model addresses the multiagent planning problem in partially observable environments.Due to its NEXP-complete complexity, only small size problems can be solved exactly.For this reason, many researchers concentrate on approximate solution algorithms that canhandle more complex cases and produce near optimal solutions. However, even the approximatesolution techniques developed so far can handle large size problems only for smallhorizons. One reason for this is the exponential memory requirements while representingthe agent policies and searching the policy space. In this thesis, we propose four newapproaches to solve finite horizon DEC-POMDP problems approximately. The first approach,called MAP, is based on modeling DEC-POMDP problems as a POMDP problemand then solving using an efficient POMDP solver. The other approaches, namely ES-BV,ES-OH and GA-FSC, are all based on the application of evolutionary algorithms. The ESBVmakes use of belief vectors as in the case of MAP and tries to find policy vectors usingevolution strategies (ES). The ES-OH proposes to use the observation history and input itinto a neural network to make a decision and it uses ES to train the neural networks. TheGA-FSC algorithm makes use of finite state controllers for representing the policies andsearch for the optimal policy using genetic algorithms (GA). All algorithms were tested onthe major well-known DEC-POMDP problems. We compared our results with the currentstate of the art methods and we also compared our algorithms with each other. We showedthat all the algorithms developed in this study, except MAP, have comparable performanceto that of the existing top algorithms and in the case of the GA-FSC, the solution horizonfor the problems are extended at least an order of magnitude.
Benzer Tezler
- Evolutionary algorithms for solving a multi-objective green vehicle routing problem
Çok amaçlı bir yeşil araç rotalama probleminin çözümü için evrimsel algoritmalar
KAZIM ERDOĞDU
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYaşar ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KORHAN KARABULUT
- Hybrid evolutionary algorithms for solving the register allocation problem
Yazmaç özgüleme problemi için evrimsel karma algoritmalar
BETÜL DEMİRÖZ
Yüksek Lisans
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ.DR. HALUK TOPÇUOĞLU
- Heuristic algorithms for solving chemical shift assignment problem in protein structure determination
Sezgisel algoritmalar ile protein yapı belirlemesindeki kimyasal kayma atama probleminin çözümü
EMEL MADEN YILMAZ
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR
PROF. DR. PETER GÜNTERT
- Nature-inspired evolutionary algorithms and a model proposal
Doğadan esinlenen evrimsel algoritmalar ve bir model önerisi
GÜLİN ZEYNEP ÖZTAŞ
Doktora
İngilizce
2021
İşletmeDokuz Eylül Üniversitesiİşletme (İngilizce) Ana Bilim Dalı
PROF. DR. SABRİ ERDEM
- Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar
Multiploid evolutionary algorithms with statistical methods for dynamic environments
EMRULLAH GAZİOĞLU
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR