Ayrık optimizasyon problemlerinin çözümünde göçmen kuşlar optimizasyon (MBO) algoritmasının iyileştirilmesi

Abstract

Göçmen kuşlar optimizasyon (MBO) algoritması sürü zekasına dayanan meta-sezgisel bir optimziasyon algoritmasıdır. MBO algoritması tek sürüden oluşan bir popülasyona sahiptir. Popülasyon içerisindeki bireyler fayda mekanizması olarak adlandırılan bir iletişime sahiptir. Bu iletişim sayesinde sürüdeki bireyler en iyi sonuca sahip bireye benzemeye çalışırlar. Ancak bu durum algoritmanın yerel optimum noktalara takılmasına sebep olabilmektedir. Bu tez çalışmasında ayrık problemlerin çözümü için tasarlanan MBO algoritması iyileştirilmiştir. Ayrıca farklı türden problemlerin çözümünde kullanılabilmesi için MBO'nun temel yapısını bozmadan yeni algoritmalar geliştirilmiştir. Yerel optimumlara takılmasını önlemek için MBO algoritmasına birden çok sürü dahil edilerek çok sürülü MBO (ÇS-MBO) algoritması geliştirilmiştir. Geliştirilen bu ÇS-MBO algoritmasında, her sürü birbirinden bağımsız olarak arama işlemi yaptırılmıştır. Global aramayı kuvvetlendirmek için ÇS-MBO algoritması yine bir optimizasyon algoritması olan parçacık sürü optimizasyon (PSO) algoritması ile birlikte kullanılarak melez bir ÇS-MBO (PSO-ÇS-MBO) algoritması geliştirilmiştir. Bu melez algoritma, ÇS-MBO'daki sürülerin PSO yardımıyla etkileşimde bulunmasını sağlamıştır. Bunun yanında ikili (binary) problemlerin çözümünde kullanılmak üzere MBO algoritmasının temel yapısı kullanarak ikili MBO (BMBO) algoritması geliştirilmiştir. BMBO algoritmasının performansını artırmak için çok sürülü BMBO (ÇS-BMBO) algoritması geliştirilmiştir. Tüm iyileştirilen ve geliştirilen algoritmaların performansları literatürde bulunan problemler üzerinde test edilmiştir. Ayrık kombinatoryal problemlerden olan Gezgin satıcı problemi (GSP), çok boyutlu iki yönlü sayı bölümle problemi (ÇBİYSBP), graf boyama problemi (GBP) ve tek boyutlu kesim problemi (TBKP) MBO, ÇS-MBO ve PSO-ÇS-MBO algoritmaları ile çözülmüş ve performansları kıyaslanmıştır. Ayrıca ayrık ikili problemlerden olan ikili sırt çantası problemi (İSÇP) ve çok boyutlu ikili sırt çantası problemi (ÇBİSÇP) BMBO ve ÇS-BMBO algoritmaları ile çözülmüş ve sonuçları kıyaslanmıştır. Elde edilen sonuçlar, iyileştirilen ÇS-MBO ve PSO-ÇS-MBO algoritmalarının MBO algoritmasından daha başarılı olduğunu göstermiştir. Ayrıca geliştirilen BMBO ve ÇS-BMBO algoritmalarından elde edilen sonuçlara göre ÇS-BMBO algoritmasının BMBO algoritmasına göre daha başarılı olduğu görülmüştür.

The migrating birds optimizaton (MBO) algorithm is a meta-heuristic algorithm based on swarm intelligence. The MBO algorithm has a population which consists of one swarm. Individuals in the population has a communication method called benefit mechanism. Owing to this communication method, individuals in the swarm try to converge to the individual which has the best solution. However, this may cause the algorithm to be stacked at local optimum. In this thesis study, the MBO algorithm, which was developed to solve the discrete problems, was improved. Besides, without changing the fundamental structure of MBO, new algorithms were developed to be used in the solution of different types of problems. Multi flock MBO (MF-MBO) was developed by including more than one flock to the algorithm to avoid stacking of MBO at local optimum. In this developed MF-MBO, it was had the each flock searched individually. By using MF-MBO and Particle Swarm Optimization (PSO) together, a hybrid PSO-MF-MBO algorithm was developed to strengthen the global search. This hybrid algorithm provided that flocks in the MF-MBO interact with each other with the help of PSO. In addition, binary MBO algorithm (BMBO) was developed by using fundamental structure of MBO for the solution of binary problems. In order to improve the performance of the BMBO algorithm, a multi flock BMBO (MF-BMBO) algorithm was developed. The performances of all the algorithms developed and enhanced were tested with the problems existing in the literature. Some discrete combinatorial problems such as Traveling Salesman Problem, Multi-Dimensional Two-Way Number Partitioning Problem, Graf Coloring Problem, One-Dimensional Cuting Problem were solved and their performances were compared by using the algorithms of MBO, MF-MBO and PSO-MF-MBO. Additionally, binary problems such as Binary Knapsack Problem and Multi-Dimensional Knapsack Problem were solved and compared with the algorithms of BMBO and MF-BMBO. The results showed that the enhanced MF-MBO and PSO-MF-MBO algorithms were much more successful than that of MBO. Besides, according to results obtained by the algorithm of the enhanced BMBO and MF-BMBO, it was observed that MF-BMBO was more successful than that of BMBO.