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

Чтобы избежать цикличности, используется краткосрочный список табу (TL — Tabu List), который запрещает изменять последние смены. Если выполнен переход от х к х ® (i, t ), то алгоритм добавит блок і на Х[ (сдвиг (і, Xj)) в список табу, и в течение следующих Ѳ итераций данный блок при планировании рассматриваться не будет, Ѳ — случайное целое число, выбранное за [Ѳт іп, Ѳтах] . Также может быть применен сдвиг табу, если это приводит к решению, лучшему, чем те, что найдены на данный момент, и обозначаемому xbest. Изменение целевой функции Ax( i , t ) = f ( x ® (i,t)') - f ( x ) , связанное с соседним решением х 0 (i, t), легко оценить, поскольку сдвиг (i, t) влияет только на периоды Х[ и t. Может существовать несколько сдвигов с одинаковым значением наилучшей модификации. Чтобы осуществить из них выбор, используются вторичный критерий выбора, основанный на частотной памяти. В работе вводят F = [F;t ] матрицу частот размерности N х (Т + 1). Каждая запись , связанная с парой блоков i и периодом t , представляет количество раз, когда i было запланировано на t с начала процесса решения. Эта частотная матрица обновляется всякий раз, когда применяется сдвиг (i, t) путем увеличения значения элемента Fit на 1. Чтобы разорвать связи, выбирается наилучшее возможное решение х 0 (i, t) с наименьшим значением частоты F ^ . Этот вторичный критерий отбора можно рассматривать как стратегию диверсификации, используемую для продвижения поиска в менее исследованные регионы пространства поиска. Наконец, процедура поиска с запретами завершается, когда число последовательных итераций без улучшения достигает заданного значения. Пусть х* — текущее наилучшее решение, сгенерированное с помощью табу-поиска. Если х* лучше, чем решение xbest, сгенерированное в предыдущих приложениях поиска (лучшее решение, найденное на данный момент), то xbest заменяется на х*. В статье было проведено численное сравнение двух различных стратегий диверсификации — Long-term memory (LTM) и Variable neighborhood (VN). Первая стратегия использует долговременную память истории поиска, в то время как вторая основана на методе поиска по переменной окрестности. Если прошедшее время меньше, чем timemax , эти стратегии могут быть использованы для создания нового начального решения х° для повторной инициализации процедуры табу-поиска. Заключение В статье рассмотрены два наиболее часто применяемых подхода к локальному поиску для планирования открытых горных работ: подход, основанный на имитации отжига, и подход на основе поиска с запретами. В работе [2] авторы предложили подход, основанный на имитации отжига с эвристикой «жадного» поиска. Применение данной эвристики в алгоритме имитации отжига, как показано в работе, позволило значительно повысить его эффективность. В статье [5] предложен метаэвристический метод, основанный на процедуре поиска с запретами. Описаны два варианта метода решения TS-LTM и TS-VN, полученные путем объединения процедуры поиска по табу с двумя стратегиями диверсификации LTM и VN, далее было проведено сравнение методов, которое продемонстрировало, что для задач относительно небольших размеров TS-VN выдает решения не хуже, чем TS-LTM. Однако он не конкурирует с TS-LTM в решении более масштабных задач. Анализ работ показал, что предложенные методы имеют потенциал для улучшения планирования открытых горных работ. Сравнение данных методов на различных задачах позволяет судить о том, что размерность решаемых с их помощью задач выше, чем размерность задач, которые способны решить методы смешанного целочисленного программирования. Таким образом, для решения реальных задач, возникающих на производстве, больше подходят методы, развиваемые в рамках искусственного интеллекта. Хотя они и не гарантируют получение оптимального решения, но позволяют получить достточно неплохую его аппроксимацию. Список источников 1. Espinoza D., Goycoolea M., Moreno E., Newman A. MineLib: a library o f open pit mining problems // Ann. Oper. Res. 2013. Vol. 206(1). P. 93-114. 2. Danish A., Khan A., Khan M., Waqas A., Salman S. A simulated annealing based approach for open pit mine production scheduling with stockpiling option // Resources Policy. 2021. Vol. 71. p. 102016. Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 92-101. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 92-101. © Шестаков А. В., Зуенко А. А., 2023 100