Kombinatoryal optimizasyon problemlerinde arı sistemi yaklaşımı
Bee system approach for combinatorial optimization problems
Yazar: PINAR ZARİF TAPKAN
Danışman: YRD. DOÇ. DR. LALE ÖZBAKIR
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2010
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Birçok gerçek hayat probleminin kombinatoryal optimizasyon problemi olarak modellenebilmesi ve klâsik optimizasyon tekniklerinin bu tür problemleri çözmedeki çeşitli yetersizlikleri, kombinatoryal optimizasyon problemlerinin çözümünde hızlı ve etkin olarak kullanılacak araçların geliştirilmesi ihtiyacını doğurmuştur. Bu amaçla problemden ve modelden bağımsız bir yapıya sahip olan doğadan esinlenmiş sezgisel optimizasyon algoritmaları, son yıllarda artan bir hızla zor kombinatoryal optimizasyon problemlerinin çözümünde kullanılmaktadır. Bu tekniklerin bir dalı olan sürü zekâsı algoritmaları ise böceklerin problem çözme becerilerini taklit eden metasezgisel yöntemler geliştirebilmek için böcek davranışlarına odaklanmıştır.Arıların yiyecek arama davranışları, öğrenme, hatırlama ve bilgi paylaşma özellikleri sürü zekâsının en ilgi çekici araştırma alanlarından birisidir. Birbiriyle etkileşen bireyler sistemi olarak ele alınan arı kolonisinde kolektif zekâ, sinerjik bilgi değişimine dayanmaktadır. Temel olarak, bulunan yiyecek kaynaklarının kalitesi hakkında bilgi paylaşımının gerçekleştirildiği arı kolonisinde amaç, farklı ve kaliteli yiyecek kaynaklarına ulaşabilmek için kolonideki diğer arıların da iyi bölgelere çekilmesine dayanmaktadır. Arılar arasındaki bu etkileşim, zor kombinatoryal optimizasyon problemlerine kaliteli ve uygun çözümlerin daha hızlı bulunmasını sağlamaktadır.Bu tez çalışmasının amacı zor kombinatoryal optimizasyon problemlerine iyi çözümler üreten ve arı davranışlarını modelleyen yapay sistemler geliştirmektir. Bu doğrultuda zor kombinatoryal optimizasyon problemleri sınıfında yer alan Genelleştirilmiş Atama Problemi ve Çift Taraflı Montaj Hattı Dengeleme Problemi'ne etkin bir çözüm yaklaşımı geliştirmek amacıyla son yıllarda önerilen Arı Algoritması ve Yapay Arı Kolonisi Algoritması'ndan faydalanılmış ve oldukça başarılı sonuçlar elde edilmiştir.

Abstract:
Due to the fact that most of real life problems can be modelled as a combinatorial optimization problem and presence of various insufficiencies on solving these problems by classical optimization techniques, it has required developing rapid and effective tools to solve combinatorial optimization problems. For this purpose, problem and model independent nature inspired heuristic optimization algorithms have been utilized for solving hard combinatorial optimization problems with an increasing trend. Such a branch of nature inspired algorithms which are known as swarm intelligence focuses on insect behavior in order to develop some meta-heuristics which can mimic insect?s problem solution abilities.The foraging behaviour, learning, memorizing and information sharing characteristics of bees have recently been one of the most interesting research areas in swarm intelligence. The collective intelligence of interacting bee colony is based on synergic information exchange. Basically, the aim of the bee colony depends on attracting other bees to productive locations to collect different and qualified food sources by sharing information about quality of food sources. This interaction among bees provides finding qualified and feasible solutions to hard combinatorial optimization problems much more quickly.This thesis is focused on developing artificial systems that generate good solutions to hard combinatorial optimization problems by utilizing bee behaviours. Accordingly, with the aim of developing an effective solution approach for Generalized Assignment Problem and Two-Sided Assembly Line Balancing Problem that can be classified as hard combinatorial optimization problems, recently proposed Bees Algorithm and Artificial Bee Colony Algorithm are utilized and considerably effective results are obtained.