Apa itu Hyper-heuristics?

Saya ingin tahu apa perbedaan antara hiper-heuristik dan meta-heuristik, dan apa aplikasi utama mereka. Masalah apa yang cocok untuk dipecahkan oleh Hyper-heuristik?

TL: DR : Hiper-heuristik adalah metaheuristik, cocok untuk memecahkan masalah optimasi yang sama, tetapi (pada prinsipnya) memberikan pendekatan "prototyping cepat" untuk praktisi non-ahli. Dalam praktiknya, ada masalah dengan pendekatan yang berlaku, memotivasi perspektif yang muncul tentang hiper-heuristik 'whitebox' .

Lebih detail:

Metaheuristik adalah metode untuk mencari ruang besar solusi yang memungkinkan untuk menemukan solusi 'berkualitas tinggi'. Metaheuristik populer termasuk Simulasi Annealing, Pencarian Tabu, Algoritma Genetika dll.

Perbedaan mendasar antara metaheuristik dan hiper-heuristik adalah penambahan tingkat tipuan pencarian: secara informal, hiper-heuristik dapat digambarkan sebagai 'heuristik untuk mencari ruang heuristik'. Karena itu, seseorang dapat menggunakan metaheuristik apa pun sebagai hiper-heuristik, dengan memberikan sifat 'ruang heuristik' yang akan dicari didefinisikan dengan tepat.

Oleh karena itu, area aplikasi untuk hiper-heuristik sama dengan metaheuristik. Penerapan mereka (relatif terhadap metaheuristik) adalah sebagai 'alat prototyping cepat': motivasi asli adalah untuk memungkinkan praktisi non-ahli untuk menerapkan metaheuristik untuk masalah pengoptimalan spesifik mereka (misalnya "Traveling-Salesman (TSP) plus time-windows plus bin- packing ") tanpa memerlukan keahlian dalam domain masalah yang sangat spesifik. Idenya adalah bahwa ini dapat dilakukan oleh:

1. Mengizinkan para praktisi menerapkan heuristik yang sangat sederhana (efektif, acak) untuk mengubah solusi potensial. Misalnya, untuk TSP: "tukar dua kota acak" daripada (katakanlah) heuristik Lin-Kernighan yang lebih kompleks .
2. Dapatkan hasil yang efektif (walaupun menggunakan heuristik sederhana ini) dengan menggabungkan / mengurutkannya dengan cara yang cerdas, biasanya dengan menggunakan beberapa bentuk mekanisme pembelajaran.

Hiper-heuristik dapat digambarkan sebagai 'selektif' atau 'generatif' tergantung pada apakah heuristik (masing-masing) diurutkan atau digabungkan. Hyper-heuristik generatif dengan demikian sering menggunakan metode seperti Pemrograman Genetik untuk menggabungkan heuristik primitif dan oleh karena itu biasanya disesuaikan oleh praktisi untuk menyelesaikan masalah tertentu. Sebagai contoh, makalah asli tentang hiper-heuristik generatif menggunakan Sistem Pembelajaran Klasifikasi untuk menggabungkan heuristik untuk bin-packing. Karena pendekatan generatif spesifik masalah, komentar di bawah ini tidak berlaku untuk mereka.

Sebaliknya, motivator asli untuk hiper-heuristik selektif adalah bahwa para peneliti akan dapat membuat pemecah hiper-heuristik yang kemudian akan bekerja dengan baik dalam domain masalah yang tidak terlihat, hanya menggunakan heuristik acak sederhana.

Cara ini secara tradisional telah diterapkan adalah melalui pengenalan 'penghalang domain hiper-heuristik' (lihat gambar, di bawah), di mana secara umum seluruh domain masalah diklaim dapat dicapai dengan mencegah pemecah memiliki pengetahuan tentang domain di mana itu beroperasi. Sebaliknya, itu akan menyelesaikan masalah dengan beroperasi hanya pada indeks integer buram ke daftar heuristik yang tersedia (misalnya dengan cara 'Masalah Bandit Multi-bersenjata' ).

Dalam praktiknya, pendekatan 'domain blind' ini tidak menghasilkan solusi dengan kualitas yang memadai. Untuk mencapai hasil di mana saja sebanding dengan metaheuristik khusus masalah, peneliti hiper-heuristik harus menerapkan heuristik khusus masalah yang kompleks, sehingga gagal dalam tujuan pembuatan prototipe cepat.

Pada prinsipnya masih mungkin untuk membuat pemecah hiper-heuristik selektif yang mampu menggeneralisasi ke domain masalah baru, tetapi ini telah menjadi lebih sulit karena gagasan penghalang domain di atas berarti bahwa hanya set fitur yang sangat terbatas yang tersedia untuk lintas -domain belajar (misalnya seperti yang dicontohkan oleh kerangka kerja hiper-heuristik populer ).

Perspektif penelitian yang lebih baru terhadap hyper-heuristics 'whitebox' menganjurkan pendekatan deklaratif, kaya fitur untuk menggambarkan domain masalah. Pendekatan ini memiliki sejumlah keunggulan yang diklaim:

1. Praktisi sekarang tidak perlu lagi menerapkan heuristik, tetapi cukup menentukan domain masalah.
2. Ini menghilangkan domain-barrier, menempatkan hyper-heuristics pada status 'informasi' yang sama tentang masalah sebagai metaheuristik khusus masalah.
3. Dengan deskripsi masalah whitebox, teorema 'No Free Lunch' yang terkenal (yang pada dasarnya menyatakan bahwa, mempertimbangkan ruang semua masalah kotak hitam , Simulasi Annealing dengan jadwal anil yang tak terbatas, rata-rata, sebaik pendekatan lainnya) tidak berlaku lagi.

PENOLAKAN: Saya bekerja di bidang penelitian ini, dan karena itu tidak mungkin untuk menghapus semua bias pribadi dari jawabannya.