Когда использовать Табу Поиск с генетическими алгоритмами, а когда нет?

Question

Tabu Search может использовать на Genetic Algorithms.

Генетическим алгоритмам может потребоваться много поколений, чтобы добиться успеха, поэтому для них важно работать с высокой производительностью. Tabu Search - это усовершенствование, позволяющее избежать локальных максимумов и хорошо работающее с механизмом памяти, чтобы добиться большего успеха через итерации. Однако поиск Tabu делает алгоритм более медленным, как обычно, помимо его преимуществ.

Мой вопрос:

Есть ли какие-либо исследования о том, когда использовать Табу Поиск с генетическими алгоритмами, а когда нет?

Answer 1

Вообще говоря, ГА тратят много времени на выборочные точки, которые являются тривиально субоптимальными.Предположим, вы оптимизируете функцию, которая выглядит как пара верблюжьих горбов.Изначально ГА будут сбрасывать точки повсюду и медленно сходятся к точкам, находящимся на вершине горбов.Однако даже очень простой алгоритм локального поиска может взять точку, которую GA генерирует на склоне горба, и сразу же вытолкнуть ее прямо на вершину горба.Если вы позволите каждой точке, сгенерированной GA, пройти эту простую локальную оптимизацию, то вы получите GA, ищущий только пространство локальных оптимумов, что в целом значительно повысит ваши шансы на поиск лучших решений.Проблема в том, что, когда вы начинаете с реальных проблем вместо горбов верблюдов, простые локальные алгоритмы поиска часто недостаточно мощны, чтобы найти действительно хорошие локальные оптимумы, но вместо них можно использовать что-то вроде поиска табу.

Есть два недостатка.Во-первых, каждое поколение ГА идет намного медленнее (но обычно вам нужно гораздо меньше поколений).Во-вторых, вы теряете некоторое разнообразие, что может привести к тому, что вы будете чаще сходиться к неоптимальному решению.

На практике я бы всегда включал бы какую-либо форму локального поиска внутри GA всякий раз, когда это возможно.«Свободный обед» не говорит нам о том, что иногда вы все ухудшите, но через десять лет или около того, профессионально занимаясь поисковыми системами и исследованиями в области локального поиска, я почти всегда выставляю новый 100-долларовый счет, в котором говорится, что локальный поиск улучшит ситуациюдля большинства случаев вы действительно заботитесь.Это не должен быть поиск табу;Вы можете использовать имитацию отжига, VDS или просто восхождение на гору следующего подъема.

Answer 2

Когда вы объединяете несколько эвристик вместе, вы получаете то, что называется гибридной эвристикой.

В последнее десятилетие или около того была тенденция исследовать преимущества и недостатки гибридной эвристики в оптимизации "толпы".

Есть буквально сотни статей по этой теме, и многие из них довольно хороши. Я видел работы, в которых для каждого потомства в каждом поколении ГА используется локальный поиск (восхождение на гору, а не табу), чтобы направить каждого потомка к локальному оптимуму. Авторы сообщают о хороших результатах. Я также видел работы, в которых используется GA для оптимизации графика охлаждения алгоритма имитации отжига как для конкретного случая проблемы, так и для общего случая, и которые дают хорошие результаты. Я также читал статью, в которой добавлен список табу к алгоритму имитации отжига, чтобы он не позволял пересматривать решения, которые он видел за последние n итераций, если не выполняется какая-либо функция аспирации.

Если вы работаете над составлением расписания (как предлагает ваш другой комментарий), я предлагаю вам прочитать некоторые статьи из PATAT (практика и теория в области автоматического составления расписаний), особенно от EKBurke и P.Brucker, которые очень активны и хорошо известный в данной области. Многие материалы PATAT находятся в свободном доступе.

Попробуйте поиск в Академии так:

http://scholar.google.com/scholar?q=%22hybrid+heuristics%22+%22combinatorial+optimization%22+OR+timetabling+OR+scheduling&btnG=&hl=en&as_sdt=0%2C5&as_ylo=2006

Очень трудно математически доказать сходимость этих видов эвристики. Я видел марковское цепное представление имитированного отжига, которое показывает верхнюю и нижнюю границы сходимости и существует нечто подобное для GA. Часто вы можете использовать много разных эвристик для одной задачи, и только экспериментальные результаты покажут, что лучше. Возможно, вам придется провести вычислительные эксперименты, чтобы увидеть, можно ли улучшить вашу GA с помощью TS или более общего локального поиска, но в целом гибридная эвристика, похоже, сейчас подходит.

Answer 3

Я еще не комбинировал поиск по табу с генетическими алгоритмами , но я комбинировал его с имитированным отжигом . На самом деле это не поиск по табу , это больше , улучшающий другой алгоритм с помощью tabu .

Исходя из моего опыта, проверка, является ли что-то табу, не требует высокой производительности .