Optimizasyon problemlerinin çözümü için yapay arı kolonisi algoritması tabanlı yeni yaklaşımlar

Abstract

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. 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.

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, 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.