Hybrid metaheuristics for selected optimization problems

Abstract

Meta-sezgisel yöntemler, kombinatoryal optimizasyon problemleri için yaygın olarak kullanılan çözüm teknikleridir. Meta-sezgiseller, büyük problem örneklerinde optimum çözümler arandığında kesin çözüm algoritmalarına tercih edilirler. Ancak, yüksek karmaşıklık veya büyük ölçekli problem örnekleri için, tatmin edici sonuçlar elde etmek için sezgisel yöntemler veya meta-sezgisel yöntemler yeterli olmayabilir. Bu nedenle, özellikle son otuz yıldır araştırmacılar daha iyi performans sağlayan yeni teknikler bulmaya çalışmaktadır. Araştırmacıların yönlendiği alanlardan biri meta-sezgisel yöntemlerin hibritleştirilmesidir. Hibrit meta-sezgisel yöntemler genellikle iki veya daha fazla meta-sezgiselin gücünün birleştirilmesi veya bir yerel arama yönteminin bir meta-sezgisel yöntem içine yerleştirilmesiyle elde edilir. Bu tezde açıklanan problemler için iyi performans gösteren yöntemleri geliştirmek hala çalışılan bir konudur ve daha iyi sonuçlar elde etmek için mevcut yöntemlerin hibritleştirilmesi yaygın olarak uygulanan bir yöntemdir. Bu nedenle, bu tezde farklı alanlardaki problemler için hibrit tekniklerin geliştirilmesi üzerine çalışılmıştır. Bu tez, hem ayrık hem de sürekli ortamlardan seçilen dört probleme odaklanmaktadır; özellik seçimi problemi, engel etkisizleştirme problemi, ikinci dereceden atama problemi ve sürekli fonksiyonlar. Göç eden kuşların optimizasyonunu; benzetimli tavlama, eş zamanlı pertürbasyon rassal yaklaşım algoritmaları ve pekiştirmeli öğrenme tekniği birleştirilerek üç yeni hibrit teknik geliştirilmiştir. Bu üç hibrit teknik ve birkaç son teknoloji meta-sezgisel yöntem dört probleme başarıyla uygulandı ve performansları problem örnekleri üzerinde karşılaştırıldı. Hesaplama sonuçları geliştirilen hibrit tekniklerin başarılı olduğunu göstermektedir.

Meta-heuristics are commonly used solution techniques for combinatorial optimization problems. They are preferred to exact algorithms when optimum solutions are sought on large problem instances. However, for instances of high complexity or large-scale problems, heuristics or meta-heuristics may not be sufficient to achieve satisfactory results. For this reason, especially during the last three decades, researchers have been trying to find new techniques that provide better performance. One of the fields that researchers are focusing on is hybridizing meta-heuristics. Hybrid meta-heuristics are generally obtained by combining the power of two or more meta-heuristics or by placing a local search heuristic within a meta-heuristic. Developing well-performing methods for problems described in this thesis is still an open issue and hybridization of existing methods to obtain better results is a widely applied method. Therefore, in this thesis, developing hybrid techniques for problems in different domains is studied. This thesis focuses on four problems from both discrete and continuous domains; feature selection problem, obstacle neutralization problem, quadratic assignment problem and continuous functions. We proposed three new hybrid techniques by combining migrating birds optimization with simulated annealing, simultaneous perturbation stochastic approximation algorithms and reinforcement learning technique. These three hybrid techniques and several state-of-the-art meta-heuristics are successfully applied to the four problems and their performances are compared on the problem instances. Computational experiment results are presented to show effectiveness of the developed hybrid techniques for each problem.