A modified choice function hyper-heuristic with Boltzmann function

Abstract

Гіпер-евристика — це підклас методів дослідження високого рівня, які функціонують у просторі евристичних досліджень низького рівня. Їхня мета — покращити рівень загальності для розв’язування задач комбінаторної оптимізації за допомогою двох основних компонентів: методології евристичного вибору та критерію прийнятності ходу для забезпечення інтенсифікації та диверсифікації [1]. Таким чином, замість того, щоб безпосередньо працювати над розв’язками задачі та обирати один з них, щоб перейти до наступного кроку на кожному етапі, гіпер-евристика діє у просторі евристичного дослідження низького рівня. Функція вибору є однією з гіпер-евристик, які довели свою ефективність у розв’язанні задач комбінаторної оптимізації [2–4]. На кожній ітерації вибір евристики залежить від оцінки, обчисленої шляхом поєднання трьох різних показників, щоб гарантувати як інтенсифікацію, так і диверсифікацію процесу вибору евристики. Тому для розв’язуванн задачі вибирається евристика з найвищим балом. Отже, ключем до успіху в виборі функції є вибір правильних вагових параметрів для трьох її мір. У цій роботі виконано сучасне гіперевристичне дослідження та запропоновано новий метод, який автоматично керує цими ваговими параметрами на основі функції Больцмана. Проведено порівняння результатів, отриманих внаслідок його застосування до п’яти предметних областей, з результатами методу стандартної модифікованої функції вибору, які запропоновані Дрейком та ін. [2, 3].

Hyper-heuristics are a subclass of high-level research methods that function in a low-level heuristic research space. Their aim objective is to improve the level of generality for solving combinatorial optimization problems using two main components: a methodology for the heuristic selection and a move acceptance criterion, to ensure intensification and diversification [1]. Thus, rather than working directly on the problem’s solutions and selecting one of them to proceed to the next step at each stage, hyper-heuristics operates on a low-level heuristic research space. The choice function is one of the hyper-heuristics that have proven their efficiency in solving combinatorial optimization problems [2–4]. At each iteration, the selection of heuristics is dependent on a score calculated by combining three different measures to guarantee both intensification and diversification for the heuristics choice process. The heuristic with the highest score is therefore chosen to be applied to the problem. Therefore, the key to the success of the choice function is to choose the correct weight parameters of its three measures. In this study, we make a state of the art in hyper-heuristic research and propose a new method that automatically controls these weight parameters based on the Boltzmann function. The results obtained from its application on five problem domains are compared with those of the standard, modified choice function proposed by Drake et al. [2, 3].