Bacteria Foraging Optimization with Genetic Operators for QAP and mQAP

DSpace Home
→
02 Faculty of Engineering
→
Department of Computer Engineering
→
Theses (Master's and Ph.D) – Computer Engineering
→
View Item

dc.contributor.advisor	Ünveren, Ahmet
dc.contributor.author	Parvandeh, Saeid
dc.date.accessioned	2017-05-16T11:39:46Z
dc.date.available	2017-05-16T11:39:46Z
dc.date.issued	2013-07
dc.date.submitted	2013
dc.identifier.citation	Parvandeh, Saeid. (2013). Bacteria Foraging Optimization with Genetic Operators for QAP and mQAP. Thesis (M.S.), Eastern Mediterranean University, Institute of Graduate Studies and Research, Dept. of Computer Engineering, Famagusta: North Cyprus.	en_US
dc.identifier.uri	http://hdl.handle.net/11129/3254
dc.description	Master of Science in Computer Engineering. Thesis (M.S.)--Eastern Mediterranean University, Faculty of Engineering, Dept. of Computer Engineering, 2013. Supervisor: Assist. Prof. Dr. Ahmet Ünveren.	en_US
dc.description.tableofcontents	The Bacterial Foraging Optimization Algorithm (BFOA) is one of the metaheuristics algorithms which is widely used in Optimization processes. It is also related to other optimization algorithms such as Ant Colony and Particle Swarm Optimization. So far, many of the metaheuristics algorithms such as genetic algorithm, particle swarm optimization, and tabu search have been used to hybridize this algorithm. The BFOA is imitated by behavior of the foraging bacteria group such as E.coli. Basically, the main aim of the algorithm is to eliminate those bacteria which have weak foraging methods and following up those bacteria which have strong foraging methods. In this extent, each bacterium contacts to other bacteria by sending signals such that bacterium change the position to the next step if prior factors have been satisfied. In fact, the process of algorithm allows bacteria to follow up the nutrients toward the optimal. BFO algorithm has three steps: 1) 'Chemo-tactic', 2) 'Reproduction', and 3) 'Elimination-dispersal'. In this thesis, Bacteria Foraging Optimization Algorithm (BFOA) is used for the solution of Quadratic Assignment Problems (QAP), and Multi-objective QAP (mQAP). Since, QAP is NP-hard problem and finding a reasonable solution is a non-polynomially time-consuming process, then one of the combinatorial algorithms should be used to find the solution in reasonable time. The BFO is one of the combinatorial optimization algorithms which apply to optimize the cost of such problems. The BFO algorithm takes a population of permutation (locations), and in several iterations of a generation, it can find a reasonable solution for QAP or mQAP. Furthermore, in order to improve the algorithm, some genetic updating operators such as crossover and mutation have been used in the second part of BFOA algorithm (chemo-tactic) in every generation of this step. Additionally, robust tabu search has been used in the third part (elimination-dispersal) to improve the best solution found so far.	en_US
dc.description.tableofcontents	ÖZ: Bakteriyel besin arama algoritması (BBAA), bakteri eniyleme optimizyasyon ve sürü en iyileme algoritmaları alanına ait olup daha geniş alanlar olan hesaplara dayalı zeka ve sezgisel Algoritma alanları altında kullanılan noktadır. BBAA algoritması parçası sürü eniyileme ve karınca kolonisi en iyileme algoritmaları ilede benzerlik göstermektedir. Ayrıca BBAA, diğer en iyileme algoritmaları ile birleştirilerek de kullanılmaktadır. Örneğin BBAA ve Genetik algoritma, veya parçacık sürü en iyileme algoritması veya Tabu arama algoritmaları. BBAA, E.coli bakterisinin beslenme davranışından esinlenerek geliştirilmiş bir iyileme yöntemidir. E.coli bakterisi besin maddesine ulaştığında diğer bakterileri uyarıcı etkiye sahip kimyasal bir madde salgılamaktadır. Bu madde diğer E.coli bakterilerinin besini bulan bakterinin bulunduğu yere doğru hareket etmesini sağlamaktadır. BBAA en iyileme algoritması tüm hücrelerin en iyiye doğru grup halinde hareketini sağlama stratejisi gütmektedir. En iyiye ulaşmak için BBAA sırasıyla üç önemli işlemi sürü halindeki tüm hücrelere uygular; 1) “Kemotaktik”, 2) “Üreme”, 3) “Eliminasyon-dağıtım”. Bu tezde bakteriyel besin arama algoritması (BBAA) kullanılarak karesel atama problemleri(KAP) ve çok amaçlı karesel atama problemleri (MKAP) çözülmüştür. KAP, bir dizi aracı, bir dizi lokasyona, verilen lokasyonlar arası uzaklıklar ve araçlar arası akış bilgileri kullanarak atama yapma problemi olarak tanımlıya biliriz. KAP problemi bir NP-ZOR problem olduğundan iyi çözümlere ulaşmak uzun zaman almaktadır. BBAA algoritması tümleşik algoritmalardan biri olup NP-ZOR problemlerini çözmek için kullanılır. BBAA algoritması en iyileme döngüsü ile KAP ve MKAP problemlerine çözüm bulmaya çalışır. BBAA algoritmasında KAP ve MKAP problemleri çözümü esnasında farklı çaprazlama ve mutasyon metodları kullanılarak mevcut problemler iyileştirilmeye çalışılmıştır. Ayrıca Tabu arama algoritması bulunan en iyi çözümlere uygulanmış ve mevcut en iyi çözümlere ulaşılmıştır.	en_US
dc.language.iso	eng	en_US
dc.publisher	Eastern Mediterranean University (EMU) - Doğu Akdeniz Üniversitesi (DAÜ)	en_US
dc.rights	info:eu-repo/semantics/openAccess	en_US
dc.subject	Computer Engineering	en_US
dc.subject	BFOA	en_US
dc.subject	Tabu Search	en_US
dc.subject	Quadratic Assignment Problem	en_US
dc.subject	Multiobjective Quadratic Assignment Problem	en_US
dc.title	Bacteria Foraging Optimization with Genetic Operators for QAP and mQAP	en_US
dc.type	masterThesis	en_US
dc.contributor.department	Eastern Mediterranean University, Faculty of Engineering, Dept. of Computer Engineering	en_US