T.C. SELÇUK ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ ARI KOLONİSİ İLE ŞOFÖR-HAT-ZAMAN OPTİMİZASYONU MUSTAFA SERVET KIRAN YÜKSEK LİSANS TEZİ BİLGİSAYAR MÜHENDİSLİĞİ ANABİLİM DALI KONYA-2010 ii ÖZET Yüksek Lisans Tezi ARI KOLONİSİ İLE ŞOFÖR-HAT-ZAMAN OPTİMİZASYONU 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 2010, 99 Sayfa Jüri : Prof.Dr. Ahmet ARSLAN Yrd.Doç.Dr. Adem Alparslan ALTUN Yrd.Doç.Dr. Mesut GÜNDÜZ Sezgisel optimizasyon teknikleri doğadan esinlenilerek geliştirilmiştir. Bu tekniklere karınca kolonisi optimizasyon, kısmi sürü optimizasyon ve arı sistemi optimizasyon algoritmaları örnek olarak verilebilir. Son yıllarda arı sistemi üzerine yapılan çalışmalar ivme kazanarak artmış ve arı sistemi bir çok optimizasyon probleminin çözümünde kullanılmıştır. Bu tez çalışmasında arı kolonisi optimizasyon algoritması şoför-hat-zaman çizelgelemede optimum görev dağılımının bulunması için kullanılmıştır. Konya Cumhuriyet Otobüs Durağına ait yolcular için hazırlanmış olan araç kalkış saatleri bir problem olarak ele alınmış ve hatlara ait seferlerin şoförlere dağıtılması amaçlanmıştır. Arı sisteminin bir metodu olan arı kolonisi optimizasyonu tez problemindeki şoförlerin belirli saat çalışması kaydıyla optimum görev dağılımını oldukça başarılı şekilde gerçekleştirmiştir. Elde edilen uygulama sonuçlarına göre, şoförlerin dinlenme süreleri, mola saatleri ve sayılarında dikkate değer iyileştirmeler yapılmıştır. Anahtar Kelimeler: Arı Sistemi, Arı Kolonisi Optimizasyonu, Sürü Zekâsı, Şoför-Hat-Zaman Çizelgeleme iii ABSTRACT MS Thesis BEE COLONY BASED DRIVER-LINE-TIME OPIMIZATION Mustafa Servet KIRAN Selçuk University Graduate School of Natural Applied Sciences Department of Computer Engineering Supervisor : Assist. Prof. Dr. Mesut GÜNDÜZ 2010, 99 Pages Jury: Prof.Dr. Ahmet ARSLAN Yrd.Doç.Dr. Adem Alparslan ALTUN Yrd.Doç.Dr. Mesut GÜNDÜZ Heuristic optimization methods have been developed by being inspired from nature. Ant colony optimization, particle swarm optimization and bee system optimization algorithms are given as examples to these methods. In recent years, studies on bee system are increasing by growing popularity and bee system is commonly used in solution of various optimization problems. In this thesis, bee colony optimization algorithm is used so as to find the optimal distribution of tasks in driver line-time scheduling. Konya Cumhuriyet Bus Station departure time of vehicles which is prepared for travelers is considered as an optimization problem and it is aimed that travels of lines are distributed to drivers. Optimal task distribution is successfully implemented by bee colony optimization which is one of the sub-method in the bee system concept providing that each driver is to work certain hours. According to application results obtained, remarkable improvements are performed in rest periods, break time and number of drivers. Keywords: Bee System, Bee Colony Optimization, Swarm Intelligence, Driver-Line-Time Scheduling iv TEŞEKKÜR Bu çalışmamda bana yol gösteren danışman hocam Yrd.Doç.Dr. Mesut GÜNDÜZ Bey’e, tezim hakkında çokça tartıştığımız Arş.Gör. Oğuz FINDIK Bey’e ve problemle ilgili yardımcı olan Konya Büyükşehir Belediyesi Cumhuriyet Durağı Baş Şoförü Sayın Mükremin Yiğit Bey’e teşekkürlerimi bir borç bilirim. Her durumda maddi manevi yardımlarını esirgemeyen aileme sonsuz teşekkürlerimi sunarım. v İÇİNDEKİLER ÖZET......................................................................................................................ii ABSTRACT...........................................................................................................iii TEŞEKKÜR........................................................................................................... iv İÇİNDEKİLER.........................................................................................................v TABLO VE ŞEKİL LİSTESİ.................................................................................vii 1. GİRİŞ.................................................................................................................. 1 1.1. Amaç ............................................................................................................ 2 1.2. Kaynak Araştırması....................................................................................... 3 1.3. Materyal ve Metot......................................................................................... 4 2. OPTİMİZASYON KAVRAMLARI..................................................................... 5 2.1. Optimizasyon ve Optimizasyon Problemleri.................................................. 5 2.2. Optimizasyon Probleminin Temel Bileşenleri................................................ 6 2.3. Optimizasyon Problemlerinin Sınıflandırılması............................................. 7 2.4. Optimizasyon Metotları ve Sınıflandırılması................................................. 7 2.5. Sürü Zekâsı Temelli Optimizasyon Algoritmaları.........................................10 2.5.1. Karınca kolonisi optimizasyonu.............................................................10 2.5.2. Parçacık sürü optimizasyonu.................................................................11 2.5.3. Arı kolonisi optimizasyonu....................................................................11 3. SÜRÜ ZEKÂSI VE DOĞADAKİ ARILAR.......................................................12 3.1. Kovandaki Arı Çeşitleri................................................................................13 3.1.1. Erkek arılar............................................................................................13 3.1.2. Kraliçe arı..............................................................................................13 3.1.3. İşçi arılar...............................................................................................14 3.2. Arı Kolonisinde Görev Paylaşımı.................................................................14 3.3. Arıların Yem Arama Davranışı ve Sallanım Dansı........................................15 4. ARI KOLONİSİ OPTİMİZASYONU.................................................................17 4.1. Biyolojik Esinlenme ve Yaklaşım.................................................................17 4.2. Arı Kolonisi Optimizasyon Algoritması.......................................................19 vi 5. ŞOFÖR-HAT-ZAMAN PROBLEMİ..................................................................24 5.1. Problemin Tanımı.........................................................................................25 5.2. Kısıtlar ve Şartlar.........................................................................................27 5.3. Önişlemler....................................................................................................28 5.4. Problem Matrisi............................................................................................29 6. ARI KOLONİSİ İLE ŞOFÖR-HAT-ZAMAN OPTİMİZASYONU....................30 6.1. Algoritmanın Uyarlanması...........................................................................30 6.2. Elde Edilen Sonuçlar....................................................................................35 7. SONUÇ VE ÖNERİLER....................................................................................37 8. KAYNAKLAR...................................................................................................39 EK-A. Yolcular İçin Hazırlanan Sefer Listesi..........................................................42 EK-B. HALİHAZIRDA ŞOFÖRLER TARAFINDAN KULLANILAN ÇİZELGE43 EK-C. HAT MATRİSİ............................................................................................51 EK-D. SEFER MATRİSİ........................................................................................61 EK-E. MATLAB KODLARI..................................................................................71 EK-F. ÜRETİLEN ÇÖZÜMLERDEN RASTGELE BİRİSİ...................................81 EK-G. UYGULAMA SONUÇLARI.......................................................................90 vii TABLO VE ŞEKİL LİSTESİ Şekil 2-1. Yerel Minimum-Maksimum ve Global Minimum-Maksimum................. 6 Şekil-2.4.1 Optimizasyon Yöntemlerinin Sınıflandırılması (Akay 2009).................. 9 Şekil-3.2.1. Arılarda Görev Paylaşımı ve Yaşam Evreleri (Akay 2009)...................15 Şekil-4.1.1. Arıların Yem Arama/Getirme Davranışı...............................................18 Şekil-4.2.1. Yapay Arıların İleri Geçişi...................................................................19 Şekil-4.2.3. Yapay Arıların Haberleşme Sonrası Bireysel İleri Geçişi......................20 Şekil-5.1.1 İşleyiciler ve Durumları........................................................................25 Şekil-5.1.1. Hatta ait bilgiler...................................................................................26 Tablo-5.3.1. Önişlemden çıkan örnek matris...........................................................28 Tablo-5.4.1. Üzerinde çalışılan matris.....................................................................29 Şekil-6.1.1. Şoför-Hat-Zaman Optimizasyonu İçin Arı Kolonisi Optimizasyon Algo- ritmasının Akış Diyagramı......................................................................................34 1 1. GİRİŞ Dünyada birçok problem insan hayatını doğrudan veya dolaylı şekilde etkilemektedir. Bu problemlerin hızlı ve kesin çözümleri için geliştirilen bilgisayarlar insan hayatını oldukça kolaylaştırır. Matematiksel olarak kesin çözümü olan problemlerin çözümü bilgisayarların gelişmesiyle birkaç saniyede ortaya konmaktadır. Bazı problemlerin çözümü ise çözüm uzayının büyüklüğü nedeniyle matematiksel olarak modellenememekte veya modellense bile kesin çözümün bulunması çok uzun zaman almaktadır. Çözümü uzun süren problemler için ortaya atılan sezgisel (heuristic) algoritmalar en iyi çözümü garanti edememesine karşın en iyi çözüme yakın iyi bir çözümü garanti edebilmektedirler. Optimizasyon genel anlamda en iyiyi yapma veya bulma anlamına gelmesine karşın Akay’a (2009) göre bilgisayar bilimleri, yapay zekâ ve ilgili araştırma alanlarında belirli bir zaman sınırı olan optimizasyon problemine getirilen olası çözümlerden kabul edilebilir bölge içerisinde en iyi olanı (amaç fonksiyonunu minimum ya da maksimum yapan) bulma sürecidir. Optimizasyon problemlerinin çözümünde optimizasyon teknikleri kullanılmaktadır. Klasik optimizasyon teknikleri problemin boyutunun büyük olması, lineer olmaması, çözüm uzayının geniş olması gibi nedenlerden dolayı yetersiz kalmaktadır. Bu problemlerin çözümü için ortaya atılan sezgisel algoritmalar en iyi çözümü (optimum çözüm) kesin olarak garanti edememesine karşın kabul edilebilir iyi bir çözüm sunarlar. Doğada sürüler halinde yaşayan canlılarda genellikle bir iş bölümü söz konusudur ve aynı işi yapan bireyler arasında bilgi değişimi bulunmaktadır. Örneğin karıncaların yuva ile yiyecek kaynağı arasında en kısa yolu bulmaları için geçtikleri yollara kimyasal bir madde bırakmaları ve kendilerinden sonraki toplayıcı bireylerin bu maddeyi takip etmeleri karıncalar arasındaki bilgi değişiminin nasıl gerçekleştiğini açıklamaktadır. Karıncaların yem arama davranışı Dorigo (1991) 2 tarafından Karınca Kolonisi Optimizasyon Algoritması olarak modellenmiş ve en kısa yol bulma probleminin çözümünde kullanılmıştır. Arı sürülerin yem aramadaki zeki davranışlarından esinlenilerek ortaya konulan Arı Sistemi üzerine de yapılan araştırmalar literatürde bulunmaktadır. Yapay Arı Kolonisi Algoritması (Artificial Bee Colony – ABC) (Karaboğa 2005), Arı Kolonisi Optimizasyon Algoritması (Bee Colony Optimization - BCO) (Lucic ve Teodorovic 2001, 2002,2003a, 2003b) ve Bal Arısı Kolonileri (Honey Bees) (Nakrani ve Tovey 2004) birçok optimizasyon probleminin çözümünde kullanılmıştır. Arı Kolonisi Optimizasyon Algoritması (Bee Colony Optimization Algorithm- BCO) bir problemin herhangi bir çözümünden başlamak üzere en iyi çözümü bulmaya çalışan sezgisel bir algoritmadır. BCO algoritması farklı problemlerin çözümü için farklı alanlarda uygulanmış ve iyi çözümler elde edilmiştir. Üretim işlerinin çizelgelenmesinde (Chong ve ark. 2006), gezgin satıcı probleminin çözülmesinde (Wong ve ark. 2008), veri gruplamasında (Pham ve ark. 2007), dinamik sunucu yerleşimi (Nakrani ve Tovey 2004) için arı sistemi kullanılmış ve iyi sonuçlar elde edilmiştir. Tez organizasyonu aşağıdaki şekildedir; Birinci bölümde tezin girişi, ikinci bölümde optimizasyon teknikleri, üçüncü bölümde doğadaki arıların davranışları ve yem arama/toplama süreçleri, dördüncü bölümde arı kolonisi optimizasyon algoritması, beşinci bölümde şoför-hat-zaman çizelgeleme problemi, altıncı bölümde arı kolonisi ile çizelgeleme yer almakta ve son olarak da sonuç ve öneriler sunulmaktadır. 1.1. Amaç Otobüs istasyonlarında birden fazla otobüs/şoför sürekli olarak belirlenmiş hatlarda ve saatlerde yolcu taşıma işinde çalışmaktadırlar. Belirli hatlar için kalkış saatleri sadece yolcular düşünülerek oluşturulan bir liste halinde bulundurulmakta ve