T.C. SELÇUK ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ OPTİMİZASYON PROBLEMLERİNİN ÇÖZÜMÜ İÇİN YAPAY ARI KOLONİSİ ALGORİTMASI TABANLI YENİ YAKLAŞIMLAR MUSTAFA SERVET KIRAN DOKTORA TEZİ Bilgisayar Mühendisliği Anabilim Dalını MAYIS-2014 KONYA Her Hakkı Saklıdır TEZ BİLDİRİMİ Bu tezdeki bütün bilgilerin etik davranış ve akademik kurallar çerçevesinde elde edildiğini ve tez yazım kurallarına uygun olarak hazırlanan bu çalışmada bana ait olmayan her türlü ifade ve bilginin kaynağına eksiksiz atıf yapıldığını bildiririm. DECLARATION PAGE I hereby declare that all information in this document has been obtained and presented in accordance with academic rules and ethical conduct. I also declare that, as required by these rules and conduct, I have fully cited and referenced all materials and results that are not original to this work. Mustafa Servet KIRAN 20.05.2014 ÖZET DOKTORA TEZİ OPTİMİZASYON PROBLEMLERİNİN ÇÖZÜMÜ İÇİN YAPAY ARI KOLONİSİ ALGORİTMASI TABANLI YENİ YAKLAŞIMLAR Mustafa Servet KIRAN Selçuk Üniversitesi Fen Bilimleri Enstitüsü Bilgisayar Mühendisliği Anabilim Dalı Danışman: Yrd.Doç.Dr. Mesut GÜNDÜZ 2014, 129 Sayfa Jüri Danışman: Yrd.Doç.Dr. Mesut GÜNDÜZ Prof.Dr. Şirzat KAHRAMANLI Prof.Dr. Ahmet ARSLAN Doç.Dr. Mehmet ÇUNKAŞ Yrd.Doç.Dr. İsmail BABAOĞLU Optimizasyon problemlerinin çözümü için kullanılan klasik optimizasyon teknikleri genellikle önerildikleri problemler için etkin sonuçlar üretmesine rağmen birçok farklı yapıda optimizasyon problemi olmasından dolayı bazı optimizasyon problemlerinin çözümünde yetersiz kalabilmektedir. Sürü zekâsına dayanan pozisyon güncelleme ile optimal ya da yakın optimal bir çözüm elde etme çabasında olan parçacık sürü optimizasyonu (PSO), karınca kolonisi optimizasyonu (ACO) ve yapay arı kolonisi algoritması (ABC) sadece bir probleme özel olmamakla birlikte birçok farklı optimizasyon probleminin çözümünde başarılı şekilde kullanılmaktadır. Doğadaki sürülerin davranışlarından esinlenilerek oluşturulmuş olan bu teknikler, popülasyon tabanlıdırlar, birden fazla noktadan çözüm uzayını araştırmaya başlarlar ve popülasyonun bireyleri olan yapay ajanlar arasında sıkı bir işbirliği ve etkileşim bulunmaktadır. PSO kuş veya balık sürülerinin yiyecek kaynağına doğru yaptıkları hareketi taklit ederek, ACO karıncaların yuva ile yiyecek kaynağı arasındaki davranışlarını simüle ederek ve ABC gerçek bal arıları kolonilerindeki yiyecek araştırma ve bilgi paylaşımı davranışlarını kullanarak optimizasyon problemi için optimal veya yakın optimal çözüm elde etmeye çalışır. Problemlerin yapılarına göre her yöntem farklı çözüm uzayında hareket edecek şekilde yapılandırılabilir. ACO ayrık çözüm uzayında hareket edebilecek yapıda tasarlanmıştır, ABC ve PSO yöntemlerindeki ajanlar ise sürekli çözüm uzayında araştırma yapma kabiliyetine sahiptirler. Çeşitli problemlerin yapısına uygun olarak bu yöntemlerin geliştirilmesi mümkündür ve ayrık problemler için önerilmiş olan ACO sürekli uzayda hareket edebilecek bir yapıya büründürülürken, ABC ve PSO ise ayrık uzayda çalışacak şekilde modifiye edilmişlerdir. Fakat hâlâ bu yöntemlerin araştırma yeteneklerinin dengelenmesine, yeni araştırma stratejileri ile global ve/veya yerel araştırma kabiliyetlerinin arttırılmasına ve farklı problemler için modifiye edilmelerine ihtiyaç duyulmaktadır. Bu tez çalışması bu yöntemlerden biri olan ABC algoritmasının sürekli ve ayrık versiyonlarını geliştirmek, iyileştirmek veya güncellemek üzerine kurulmuştur. Geliştirilen yöntemler literatürde sıklıkla kullanılan ayrık ve/veya sürekli kıyas problemlerinin çözümü için uygulanmış ve elde edilen sonuçlar bilinen diğer yöntemler ile kıyaslanmıştır. Her problem türü için farklı sayıda çalışmalar yapılmıştır. iv Sürekli problemleri çözmek için ABC algoritması ilk olarak çaprazlama operatörleri ile yerel araştırması ve yakınsama yeteneği arttırılmaya çalışılmıştır. Elde edilen sonuçlar temel ABC algoritması ile kıyaslanmış ve sonuçlar raporlanmıştır. İkinci çalışmada ABC algoritması ve modifiye edilmiş versiyonları Türkiye’nin elektrik enerjisi tahmini için uyarlanmış ve elde edilen sonuçlar PSO ve ACO ile kıyaslanmıştır. Üçüncü çalışmada araştırma kabiliyetlerini arttırmak ve daha iyi sonuçlar elde etmek amacıyla ABC ve PSO yöntemleri hibritleştirilmiştir. Elde edilen sonuçlar ABC ve PSO yöntemlerine dayanan diğer hibrit yöntemler ile karşılaştırılmıştır. Sürekli problemlerin çözümü için önerilen son çalışmada ise farklı güncelleme kuralları bir seçim mekanizması ile birleştirilerek ABC algoritmasında kullanılmış ve literatürde popüler diğer ABC varyantları ve diğer popülasyon tabanlı optimizasyon teknikleri ile karşılaştırılmıştır. Ayrık problemlerin çözümü için komşuluk operatörleri ile ayrıklaştırılmış ABC algoritmasının performans analizi gezgin satıcı problemi üzerinde yapılmış ve diğerlerine göre iyi olan komşuluk operatörü belirlenmiştir. Bu belirlemeden elde edilen sonuçlara dayanarak ACO yöntemi ile elde edilen en iyi sonuç ABC algoritması ile iyileştirilmeye çalışılmış ve hiyerarşik bir yöntem olarak sunulmuştur. Ayrık problemlerin çözümü için yapılan son çalışmada ise ABC algoritması lojik XOR operatörü kullanılarak ikili optimizasyon problemlerini çözebilecek şekilde değiştirilmiştir ve ABC ajanları ikili uzayda hareket edebilecek bir yeteneğe kavuşturulmuştur. Önerilen yöntem bir ikili optimizasyon problemi olan kapasitesiz tesis yerleşim problemi üzerinde test edilmiş ve ikili PSO, iyileştirilmiş ikili PSO ve DisABC yöntemleri ile kıyaslanmıştır. Yapılan tüm çalışmalardan görülmüştür ki yerel araştırma, global araştırma, durağanlaşma ile mücadele ve yerel araştırmaya karşın global araştırmanın veya tersinin dengelenmesi sürü zekâsına dayanan teknikler ve özellik ABC algoritması için başarılı sonuçlar elde etmenin vazgeçilmez şartlarıdır. ABC algoritmasında küçük değişiklikler yapılarak ABC algoritmasının ayrık optimization problemlerinin çözümü için de uygulanabileceği bu tez çalışmasında ayrıca görülmüştür. Anahtar Kelimeler: ayrık optimizasyon, ikili optimizasyon, karınca kolonisi optimizasyonu, parçacık sürü optimizasyonu, sürekli optimizasyon, sürü zekâsı yöntemleri, yapay arı kolonisi algoritması. v ABSTRACT Ph.D THESIS NOVEL APPROACHES BASED ON ARTICIAL BEE COLONY ALGORITHM TO SOLVE OPTIMIZATION PRONLEMS Mustafa Servet KIRAN THE GRADUATE SCHOOL OF NATURAL AND APPLIED SCIENCE OF SELÇUK UNIVERSITY THE DOCTOR OF PHILOSOPHY IN COMPUTER ENGINEERING Advisor: Assist.Prof.Dr. Mesut Gündüz 2014, 129 Pages Jury Advisor: Yrd.Doç.Dr. Mesut GÜNDÜZ Prof.Dr. Şirzat KAHRAMANLI Prof.Dr. Ahmet ARSLAN Doç.Dr. Mehmet ÇUNKAŞ Yrd.Doç.Dr. İsmail BABAOĞLU The classic optimization techniques which are proposed for solving the optimization problems generally produce the effective results for a specific optimization problem, but due to the fact that there are many types of the optimization problems, they cannot be applied to solve optimization problems with different characteristics. Swarm intelligence-based algorithms such as particle swarm optimization (PSO), ant colony optimization (ACO) and artificial bee colony (ABC) algorithm are not specific for an optimization problem, and they are used for solving many types of optimization problems. Being inspired the natural and intelligent behaviors of the swarms, these methods are population-based, start multiple points to search solution space, and there is vigorous collaboration and interaction among artificial agents which are members of population. PSO simulates the movements of fish or bird swarms towards food sources, ACO imitates the behaviors of real ants between nest and food source and ABC models the intelligent behaviors of real honey bee colony, such as information sharing and searching food source. Being simulated these behaviors of swarms, these methods try to obtain optimal or near optimal solution for the optimization problems. The basic version of each method can do search on the search spaces with different structures. While artificial agents of ACO can search discrete solution space, the agents of PSO or ABC can search continuous solution space. But, ACO has been modified for solving the optimization problems with continuous solution space, and PSO and ABC have been modified for solving optimization problems with discrete solution space. Briefly, each method can be modified for solving the optimization problems with different solution spaces. In order to obtain optimal or near optimal solution for the optimization problem and more robust methods, new search strategies for the methods and modification for applying to the many optimization problems are required for these methods. This thesis is based on improvement, modification or updating of the ABC algorithm, which is one of the prominent members of swarm intelligence, for solving discrete or continuous optimization problems. Newly proposed approaches in this thesis are applied to the discrete or continuous optimization problems and obtained results are compared with the state-of-the-art methods. Both three studies have been completed for solving continuous optimization and three studies have been completed for solving discrete optimization problems. The first study is proposed for solving continuous optimization problems, vi and it is based on ABC and crossover operators. The convergence speed and information sharing in the artificial hive are tried to improve by using crossover operators in the ABC algorithm. Obtained results are compared with the basic version of ABC algorithm and reported in the experimental results section. In the second study, the ABC algorithm and its variants proposed in this thesis are modified for applying estimation of electricity energy demand of Turkey. Obtained results are compared with the results of PSO and ACO. In order to improve search capabilities of the methods, ABC and PSO is hybridized in the last study for solving continuous optimization problems. The proposed hybrid method is compared with the basic ABC and PSO, and the other hybrid methods proposed in the literature. In the first study proposed for solving discrete optimization problems, the discrete ABC algorithm with neighborhood operator is analyzed on solving the travelling salesman problem. Basic or combined nine neighborhood operators are used in discrete ABC, and which neighborhood operator is better than the others is determined. After this determination, the second study is hierarchically established on ACO and ABC algorithms. In the hierarchic approach, the best solution obtained by ACO is given to bee population in ABC algorithm to improve it. When the solution space of the problem is binary structured, the ABC algorithm should be modified for solving this class of optimization problems. In the last study for solving discrete optimization problems in this thesis, the ABC algorithm is modified by using XOR logic operator for solving binary optimization problems. Obtained results are compared with the state-of-art methods in the literature, such as binary PSO, discrete ABC (DisABC). As seen from the studies done for this thesis, improvement or balancing of local search and/or global search, prevention of stagnation of the population are necessary conditions for obtaining optimal or near optimal solutions for the optimization problems by swarm intelligence-based methods, especially ABC algorithm. This thesis also shows that the ABC algorithm can be easly applied to optimization problems with discrete solution space with a bit modification in the algorithm. Keywords: ant colony optimization, artificial bee colony algorithm, binary optimization, continuous optimization, discrete optimization, particle swarm optimization, swarm intelligence-based methods vii ÖNSÖZ VE TEŞEKKÜR Yaşanılan dünyada bilim ve teknolojideki hızlı ilerlemeler sayesinde son zamanlarda çözümsüzlük çok az problem için vardır ve birçok problem için ise birden fazla çözümün varlığı karşımıza çıkmaktadır. Bu noktada ise birden fazla çözüm içerisinden en avajtajlı olanın seçilmesi gerekmektedir. Birden fazla çözümden hangisinin diğerlerine göre zaman, maliyet vb. açılardan daha avantajlı olduğunun belirlenmesi karar vericiler için uzun ve yorucu bir süreç teşkil edebilmektedir. Doğal olarak bu da bizi bir tercihe yöneltmektedir. Birden fazla çözüm içerisinden en iyisine tercih etme optimizasyonun çekirdeğini oluşturur. Bu tez çalışması kapsamında da zeki optimizasyon tekniklerinden biri olan yapay arı kolonisi algoritması için yeni yaklaşımlar önerilmekte ve elde edilen çözümlerin kalitesi tespit edilmeye çalışılmıştır. Ayrıca önerilen yöntemlerin var olan diğer yöntemler ile kıyaslamaları yapılarak önerilen metotların deneysel doğrulaması yapılmaya çalışılmaktadır. Tezin dil düzeltmesi için tez, konuya hâkim olan ve olmayan araştırmacılar tarafından okunmuş ve gerekli düzeltmeler yapılmıştır fakat yine de bazı imlâ hatalarına rastlanabilir. Okuyuculara bu gibi hatalar için şimdiden özürlerimi sunarım. Araştırdığı konu itibariyle son yıllarda gündemde olan bu teknikler üzerine yapılmış olan bu tez çalışmasının araştırmacı ve uygulayıcılar için faydalı olmasını temenni ederim. Yaklaşık 4 yıldır yoğun bir zaman ve emek sarfederek ortaya koyduğumuz bu çalışmada yardımlarını ve rehberliğini eksik etmeyen Danışman Hocam Sayın Yrd.Doç.Dr. Mesut Gündüz Bey’e teşekkür eder ve saygılarımı sunarım. Ayrıca tez izleme komitesinde yer alan Sayın Prof.Dr. Ahmet Arslan ve Doç.Dr. Mehmet Çunkaş Bey’lere önerileri ve eleştirileri için, doktora tez savunmam da yer alan jüri üyeleri Prof.Dr. Şirzat Kahramanlı ve Yrd.Doç.Dr. İsmail Babaoğlu Bey’lere de incelemeleri, tespitleri, eleştirileri ve düzeltmeleri için teşekkür ederim. Bu yola çıkmamı sağlayan ve her zaman ve her koşulda bana destek olan rahmetli babam Mehmet Kıran’a ve dualarını benden esirgemeyen annem Meziyet Kıran’a teşekkürlerimi, sevgilerimi ve saygılarımı sunmadan bu tezin benim için tamamlanmış olmayacağının da bilinmesini isterim. Maddi ve manevi desteklerini esirgemeyen ve beni sürekli kollayan kardeşlerim Murat ve Ferhat Kıran’a da ayrıca minnettarım. Elbette her zaman yanımda olan ve zor zamanlarımda desteğini esirgemeyen sevgili eşim Zehra Kıran’a, evde çalışırken en umutsuz ve yorgun zamanlarımda viii gülümsemeleri, neşeleri ve sevgileri ile beni yeniden çalışmaya sevkeden oğullarım Mehmet Kıran ve Eren Kıran’a sonsuz sevgilerimi sunarım. Beraber çalışma yaptığımız Doç.Dr. Harun Uğuz, Doç.Dr. Turan Paksoy, Yrd.Doç.Dr. Ömer Kaan Baykan, Arş.Gör. Eren Özceylan ve Arş.Gör. Hüseyin Haklı hocalarıma da çalışarak geçirdiğimiz zamanlar için teşekkür ederim. Bu çalışmada bana doğrudan veya dolaylı yardımcı olan mesai arkadaşlarıma ve huzurlu bir çalışma ortamı sağladıkları için Bölüm ve Anabilim Dalı Başkanlarımıza teşekkür etmeyi bir borç bilirim. Ayrıca tezimi hazırlamam süresince 2211-C Öncelikli Alanlar kapsamında burs imkânı sağlayan Türkiye Bilimsel ve Teknolojik Araştırma Kurumu (TÜBİTAK)’a maddî desteğinden dolayı ve tüm soru ve sorunlarımızı çözmede yardımcı olan değerli personeline teşekkür ederim. Ayrıca TÜBİTAK’ın gelecek yıllarda daha fazla araştırmacıya daha fazla destek sağlamasını da temenni ederim. Mustafa Servet Kıran KONYA – 2014 ix İÇİNDEKİLER TEZ BİLDİRİMİ ......................................................................................................... iii ÖZET .......................................................................................................................... iv ABSTRACT ................................................................................................................ vi ÖNSÖZ VE TEŞEKKÜR .......................................................................................... viii İÇİNDEKİLER .............................................................................................................x KISALTMALAR ...................................................................................................... xiii 1.GİRİŞ .........................................................................................................................1 1.1. Optimizasyon ..................................................................................................3 1.1.1. Karar Seti .....................................................................................................5 1.1.2. Amaç (Objective) ve uygunluk (Fitness) fonksiyonu .....................................6 1.1.3. Sınırlamalar ..................................................................................................7 1.2. Optimizasyon yöntemleri ....................................................................................8 1.2.1. Klasik yöntemler ..........................................................................................9 1.2.2. Evrimsel hesaplama teknikleri .................................................................... 10 1.2.3. Sürü zekâsına dayalı yöntemler ................................................................... 10 1.2.3.1. Çözümün gösterimi .................................................................. 11 1.2.3.2. Çözümün uygunluğu ................................................................ 11 1.2.3.3. Popülasyon .............................................................................. 11 1.2.3.4. Seçim mekanizmaları ............................................................... 12 1.2.3.5. Yeni çözümün üretilmesi ......................................................... 12 1.2.3.6. İlklendirme .............................................................................. 12 1.2.3.7. Sonlandırma ............................................................................. 13 1.2.4. Performans değerlendirme kıstasları ........................................................... 13 1.2.4.1. Çözüm kalitesi ......................................................................... 14 1.2.4.2. Gürbüzlük ................................................................................ 14 2. KAYNAK ARAŞTIRMASI-LİTERATÜR ÖZETİ ................................................. 16 2.1. Karınca Kolonisi Optimizasyonu Kaynak Araştırması ....................................... 18 2.2. Parçacık Sürü Optimizasyonu Kaynak Özeti ..................................................... 22 2.3. Yapay Arı Kolonisi Literatür Araştırması .......................................................... 28 x