LİG ŞAMPİYONASI ALGORİTMASI İLE GEZGİN TURNUVA PROBLEMİNİN ÇÖZÜMÜ

Abstract

Klasik optimizasyon algoritmaları, büyük ölçekli kombinasyonal ve doğrusal olmayan problemlerde yetersiz kaldığında sezgisel optimizasyon algoritmaları önerilmektedir. Genel amaçlı sezgisel yöntemler; biyoloji tabanlı, fizik tabanlı, sürü tabanlı, sosyal tabanlı, müzik tabanlı, kimya tabanlı, spor tabanlı, matematik tabanlı ve bunların birleşimi olan melez yöntemler olmak üzere dokuz farklı grupta değerlendirilmektedir. 2009 yılında spor tabanlı bir arama ve optimizasyon algoritması olan Lig Şampiyonası Algoritması (LŞA) Ali Husseinzadeh Kashan tarafından önerilmiştir. LŞA, genel optimizasyon için birkaç haftalık yapay bir ligde oynayan yapay takımlar içerisindeki bir şampiyonayı taklit eden popülasyon tabanlı meta sezgisel optimizasyon yöntemidir. Bu algoritmada, lig programına göre haftalık olarak mücadele edecek takım çiftlerine numara verilir ve oyunun sonucu kazanan veya kaybeden olarak belirlenir. Bir takımın oyunu kazanıp veya kaybetmesi Oyun Gücü ile yakından ilişkilidir. Takımlar ileri haftalarda gerçekleşecek olan oyunları kazanabilmek için mevcut takım oluşumlarını tüm sezonlar boyunca geliştirmeyi amaçlarlar. Optimizasyon algoritmalarının hızlı yakınsaması ve yüksek doğruluk oranını artırmak için kaotik haritalar birçok algoritmada kullanılmıştır. LŞA'nın kaosla global yakınsama özelliğinin arttırılması ve lokal çözümde takılıp kalmasının önlenmesi, ilk kez bu tez ile sunulmuştur. Bu tez çalışmasında LŞA detaylı olarak incelenmiş ve kaotik LŞA önerilmiştir. Kalite testi fonksiyonlarındaki performansı karşılaştırmalı olarak sunulmuştur. Ayrıca, güncel spor problemlerinden, taşınma ve takımların toplam hareketliliğinin minimize edilmesini amaçlayan gezgin turnuva probleminin çözümü için LŞA ilk kez bu çalışmada kullanılmıştır. Bu problem yine güncel optimizasyon yöntemlerinden olan Optik İlham Optimizasyon (OİO) ile de ilk kez çözülmüş ve elde edilen sonuçlar karşılaştırmalı olarak ilk kez bu tezde sunulmuştur. Anahtar Kelimeler: Optimizasyon, Metasezgisel Algoritmalar, Lig Şampiyonası Algoritması, Kaotik Harita, Gezgin Turnuva Problemi

Solution of Travelling Tournament Problem with League Championship Algorithm Classical optimization algorithms are insufficient in large scale combinatorial problems and in nonlinear problems. Hence, heuristic optimization algorithms have been proposed. General purpose heuristic methods are evaluated in nine different groups: biology-based, physics-based, social-based, music-based, chemical-based, sport-based, mathematics-based and hybrid methods which are combinations of these. Recently, a sports-based search and optimization algorithm entitled as League Championship Algorithm (LCA) has been proposed by Ali Husseinzadeh Kashan in 2009. LCA is a population-based, meta-heuristic optimization algorithm that simulates a Championship for a general optimization with artificial teams and artificial league for several weeks. In this algorithm, according to the league program, a number is given to the couple of teams that will match and the result of match is determined as loser or winner. Winning or losing the game is closely related to power of teams. Teams are intended to improve the formation of the current team throughout the season to win the game in the coming weeks. Chaotic maps have been used in many algorithms, to improve the convergence speed of optimization algorithms with high accuracy. Increasing global convergence speed and prevention of stuck on local solutions of LCA with chaos have been proposed for the first time in this thesis. In this thesis, LCA has been introduced and Chaotic LCAs have been proposed. Comparative performance has examined in benchmark functions. Furthermore, LCA has been firstly utilized in this thesis for travelling tournament problem which is one of the current sports problems and aids to minimize transportation and total movement of teams. Furthermore, this problem has been firstly solved by Optics Inspired Optimization (OIO) algorithm and obtained results have been firstly compared in this thesis. Keywords: Optimization, Metaheuristic Algorithms, League Championship Algorithm, Chaotic Map, Travelling Tournament Problem