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

является тот факт, что резко снижается вероятность попадания в локальный оптимум, а за счёт распараллеливания может уменьшаться время выполнения. Пчелиный алгоритм, в отличие от ГА, имеет лишь один оператор и легко распределяется на несколько параллельных процессов, за счёт чего значительно увеличится его скорость. Стоит отметить, что пчелиный алгоритм основывается на социальном поведении роя, а генетический алгоритм имитирует процесс эволюции и отбора. За счёт этого есть возможность комбинирования этих методов. Табу-поиск Табу-поиск (Поиск с запретами, Tabu-search, TS) является «высоко­ уровневой» эвристической процедурой для решения проблем оптимизации, разработанной для того, чтобы помогать другим методам (или составляющим их процессам) избежать ловушки локального оптимума. Термин «Табу-поиск» был придуман F. Glover в [13]. Табу-поиск достиг оптимальных и близких к ним решений в широком спектре классических и практических проблем - от планирования в телекоммуникациях до распознавания символов в нейросетях. Метод использует специализированные структуры данных, условия для выхода поиска из локального оптимума, и различные виды памяти для различных промежутков времени для интенсификации и диверсификации поиска. Особенности памяти TS. Атрибуты ходов TS использует атрибутивную память для направляющих целей (т. е. для вычисления множества доступных ходов N*(x)). Вместо записи полного решения, атрибутивная память базируется на записи атрибутов. Этот тип памяти записывает информацию о свойствах решения (атрибутах), которые меняются при переходе от одного решения к другому (например, индексы изменённых при шаге поиска переменных). Наиболее распространёнными типами памяти являются основанная на новизне память и основанная на частоте память. Основанная на новизне память хранит атрибуты решений, изменившиеся при самых последних поисках. Основанная на частоте память хранит соотношения между общим числом итераций и числом итераций, на которых атрибут изменился или нет (в зависимости от того, является ли это частотой пребывания или частотой перехода). Основанная на новизне память (Recency-based memory) является наи­ более часто используемой структурой памяти в реализациях TS. Как и предполагает её название, она хранит атрибуты решения, которые изменились в недалеком прошлом. Для использования этой памяти, выбранные атрибуты недавно рассмотренного решения помечаются табу-статусом, и решения, которые содержат эти элементы (или частные комбинации этих элементов), становятся запрещенными для выбора. При этом сами решения исключаются из N*(x), что предотвращает их повторное посещение. Другие решения, куда входят атрибуты со статусом табу, также не посещаются. Стоит отметить, что в отличие от классификации, запрещающей ходить только в посещенные решения, плюс хранения таких атрибутов в том, что другие ходы, ведущие к подобным решениям, также часто становятся табу. 68