Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Основанная на частоте память (Frequency-based memory). Как и новизна, частота часто имеет весовые значения или раскладывается на подклассы. Кроме того, информация о частоте может быть объединена с информацией о новизне с целью обеспечения композитной структуры для создания штрафов и стимулов, изменяющих оценку хода. Определение лучшего кандидата Определение лучшего кандидата для хода - критически важный шаг алгоритма. Сначала каждый из ходов в списке кандидатов оценивается на данной итерации поиска (вопросы касательно создания, обработки и модификации списка кандидатов, обсуждены в [14]). Во многих конфигурациях, оценка хода может базироваться изначально на изменениях, произведенных в целевой функции (то есть различие между значениями целевой функции до и после совершения хода). В иных случаях, когда ветвления не так легко определяются или не всем переменным назначены значения, оценка может базироваться на создании приблизительных решений, или просто использовать локальные критерии привлекательности. Впрочем, по мере продвижения поиска форма оценки может становиться более адаптивной, объединяя в себе улучшения, связанные с интенсификацией и диверсификацией. Так как число ходов, запрещенных согласно табу-критерию, будет в основном малым относительно числа доступных, предполагая, что оценка в ходе не слишком вычислительно затратная, обычно предпочтительно оценивать перед проверкой статуса табу, имеет ли данный ход оценку выше, чем у его приемлемых предшественников. Проверка статуса табу - первый шаг в отборе допустимых ходов. Если ход не является табу, он немедленно принимается как допустимый; в противном случае, для преодоления статуса табу используется критерий аспирации, обеспечивая ходу второй шанс для принятия его как приемлемого. Критерий аспирации - некоторое условие, при выполнении которого ход может быть сделан, даже если он содержит табу-атрибуты. К таким условиям может относиться, например, отсутствие не-табу ходов в списке возможных на данной итерации. Также если ход приводит к решению, которое лучше любого ранее достигнутого, он тоже часто удовлетворяет данному критерию. Стратегии поиска Использование основанной на новизне и частоте памяти в TS обычно исполняет функцию предотвращения циклов в процессах поиска, т. е. предотвращения бесконечного повторения одной и той же последовательности ходов. Ключевой проблемой при использовании адаптивной памяти в TS является соблюдение баланса между интенсификацией и диверсификацией. Интенсификационные стратегии базируются на модификации правил выбора для поощрения комбинаций ходов и особенностей решений, показавших положительные свойства. Также они могут инициировать возврат к привле­ кательным регионам для более тщательного их обследования. 69