Труды КНЦ (Технические науки вып. 7/2023(14))

Ограничение (7) создает связь между бинарной xbt и линейной переменной и гарантирует, что максимальное количество материала, добытого из блока, меньше или равно общему количеству, доступному в блоке. Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 92-101. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 92-101. Схема алгоритма имитации отжига Имитация отжига (SA) — это алгоритм стохастического поиска для решения задач комбинаторной оптимизации высокой размерности [3]. Алгоритм использует механизм случайного поиска путем возмущения текущего решения, начиная с исходного, для генерации нового решения S' в окрестности текущего. Если значение целевой функции f ( S ') улучшается, то шаг принимается, однако, если перемещение уменьшает целевое значение, то алгоритм SA переводит систему в это состояние с некоторой вероятностью p , известной как вероятность перехода, которая позволяет алгоритму отклониться от локального оптимума в поисках глобального оптимума. Вероятность p может быть получена с использованием критерия metropolis , приведенного ниже в уравнении (8): где AE = f(S') - f(S) — изменение значения целевой функции; а Т — температура. Процесс повторяется итеративно путем поддержания постоянной температуры в течение достаточного числа модификаций таким образом, чтобы при этой температуре было достигнуто равновесное состояние, и затем она снижается с помощью схемы охлаждения. Производительность SA зависит от управляющих параметров алшоритма, т. е. температуры (Г), схемы охлаждения, повторения возмущений при каждой температуре (N) и структуры окрестности. Модификация метода имитация отжига В статье рассматривается эвристический алгоритм ранжированного позиционного веса (RPW — Ranked Positional Weight), который был использован для генерации начального неоптимального входного решения для алгоритма SA [4]. Этот метод работает по логике, согласно которой, если есть какой-либо ценный блок, лежащий под блоком, то вышележащий блок должен получить больше очков, потому что его добыча приводит к получению ценных блоков, лежащих под ним. Первоначальное решение, сгенерированное RPW, затем передается в SA с возможностью накопления запасов для дальнейшей оптимизации. Алгоритм на основе SA 1. Генерация исходного неоптимального решения с использованием эвристического алгоритма ранжированного позиционного веса (RPW). 2. Выбор значения начальной температуры Т0 и общее количество итераций при каждой температуре (N). 3. Пока (текущее количество итераций меньше, чем максимальное количество итераций). 4. Найти блоки-кандидаты (т. е. изменение периода) для замены. 5. Создать новое решение, используя две возможности замены: a. перенести выбранные блоки на ранний период; b. перенести выбранные блоки на более поздний период. 6. Запустить эвристику накопления запасов для поиска нового решения. 7. Запустить жадную эвристику после заданного количества итераций. 8. Вычислить значение целевой функции для нового решения. © Шестаков А. В., Зуенко А. А., 2023 !Іа=іУыа ^ 4 b * 4 t t = 1,2...... Т. (7) (8) 95