A Comprehensive Analysis on the Iterated Greedy Algorithm

Abstract

Generally, optimization is the achievement of the best result under certain constraints. Basically, the approaches developed for the solution of optimization problems are examined under two groups as exact solution methods and approximate solution methods. Exact solution methods guarantee the optimum, but they cannot produce solutions in an acceptable time for large-scale real-life problems of NP-Hard. Therefore, the researchers draw great attention to the meta-heuristic methods, which are one of the approximate solution methods, because they can provide quality solutions at an acceptable time. In this study, a detailed analysis of the iterative greedy algorithm, which is an easy-to-apply and effective meta-heuristic, was conducted. In the relevant meta-heuristic, each operator is discussed under subheadings. Iterative greedy algorithm approaches developed for various problems are presented to the reader with their advantages and disadvantages. In summary, in this study, it is aimed to contribute to the Turkish literature about the iterative greedy algorithm, which has many aspects in common with various meta-heuristics such as taboo, annealing simulation, and iterative local search.Genel olarak optimizasyon, belirli kısıtlar altında en iyi sonucun elde edilmesi için yapılan çalışmaların bütünüdür. Temel olarak optimizasyon problemlerinin çözümü için geliştirilen yaklaşımlar kesin çözüm yöntemleri ve yaklaşık çözüm yöntemleri olmak üzere iki grup altında incelenir. Kesin çözüm yöntemleri optimumu garanti ederler ancak NP-Zor yapıdaki büyük boyutlu gerçek hayat problemleri için kabul edilebilir bir zamanda çözüm üretemezler. Bu yüzden araştırmacılar, kabul edilebilir zamanda, kaliteli çözümler verebilmeleri nedeni ile yaklaşık çözüm yöntemlerinden metasezgisel yöntemlere büyük ilgi göstermektedir. Bu çalışmada uygulaması kolay ve etkili bir metasezgisel olan tekrarlı açgözlü algoritmaya yönelik detaylı bir analiz çalışması yapılmıştır. İlgili metasezgisele ait her bir operatör alt başlıklar halinde ele alınmıştır. Çeşitli problemler için geliştirilen tekrarlı açgözlü algoritma yaklaşımları avantaj ve dezavantajlarıyla okuyucuya sunulmuştur. Özetle bu çalışmada tabu, tavlama benzetimi, tekrarlı yerel arama gibi çeşitli meta-sezgiseller ile ortak birçok yönü bulunan tekrarlı açgözlü algoritma hakkında Türkçe literatüre katkıda bulunmak amaçlanmıştır.