Performance analysis of hyperheuristics and their use with hill-climbers

Abstract

Yardımlı buluşsal algoritmalar buluşsalüstü algoritmalara göre daha yüksek seviyedebir soyutlama olacak şekilde önerilen döngüsel yaklaşımlardır. Yardımlı buluşsal yöntemlerproblem çözümü için bir buluşsallar kümesini yönetir. Tipik bir yardımlı buluşsal döngüsü ikiaşamadan oluşur: buluşsal seçme yöntemi ve hareket kabul etme. Uygun bir buluşsalseçildikten ve tek çözüm adayına uygulandıktan sonra yeni çözüm adayının kabul edilipedilmeyeceği kararı alınır. Bu karar sadece probleme özgü olmayan, uygunluk değeri,buluşsal işletim süresi gibi veriler kullanılarak alınır. Bu tezde geleneksel yardımlı buluşsalçerçeve modeli geliştirilmiş ve tepe tırmanıcıları daha iyi kullanmak için üç yeni çerçevemodel önerilmiştir. Bu çerçeve modeller ve çeşitli buluşsal seçme yöntemi ve kabul kriteriçiftleri derinlemesine çözümlenmiştir. Bunların başarımları iyi bilinen matematiksel denektaşıfonksiyonlarında ölçülmüştür. Yardımlı Buluşsalların başarım varyansları ayrıca denektaşısınav zaman çizelgeleme problem örnekleri üzerinde araştırılmıştır.

Hyperheuristics are iterative approaches that are proposed as a higher level abstractionas compared to the metaheuristics. Hyperheuristic methods manage a set of heuristics forsolving a problem. A typical iteration in a hyperheuristic framework consists of two phases:heuristic selection and move acceptance. After the selection and application of an appropriateheuristic to a single candidate solution at hand, a decision is made whether to keep the newcandidate solution, or not. This decision is based on only nonproblem-specific data, such as,fitness change or heuristic execution time. In this thesis, the traditional framework is extendedand three new frameworks are proposed in order to make better use of hill-climbers. Theseframeworks and several heuristic selection method and acceptance criterion combinations areanalyzed in depth. Their performances are evaluated on well-known benchmark functions.The performance variances of the hyperheuristics are further investigated on the examinationtimetabling benchmark problem instances.