Проектная часть. 
Генетические алгоритмы и традиционные способы оптимизации

Применение генетического алгоритма для решения задачи коммивояжера

Постановка задачи безусловной оптимизации

Практически всегда оптимизируемая функция обладает каким-либо свойством (свойствами): алгоритмическое задание, сложная конфигурация допустимой области, наличие нескольких типов переменных. Это приводит к необходимости применения специализированных методов, к которым и относятся эволюционные и генетические алгоритмы, хорошо зарекомендовавшие себя в ситуациях, когда применение стандартных методов оптимизации крайне затруднено.

Ограничения при реализации генетических алгоритмов

Суть использования генетических алгоритмов держится на трех принципах:

кодирование, оценивание и воспроизводство, но с практической точки зрения имеют смысл иные качества, которые, однако, нисколько не отменяют основные параллели с эволюционными механизмами.

Под кодированием понимается способ представления данных в генетическом виде.

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

Оценивание является еще одним важным принципом. Смысл оценивания заключается в том, чтобы различать особей в зависимости от того, насколько «успешны» соответствующие им закодированные решения. При этом не должно возникать коллизий, когда две практически равноценные особи имеют существенно различные значения приспособленностей, и, наоборот, когда качественно разные особи оцениваются одинаково.

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

В ряде случаев это условие требует использования «нестандартных» генетических операторов и/или специфичного кодирования. К примеру при решении задачи коммивояжера в маршруте не должна два раза и чаще встречаться одна и та же вершина, что часто получается в результате применения традиционно используемых операторов однои двухточечного и однородного кроссинговера. Поэтому для данной проблемы разработаны специальные операторы скрещивания и мутации.

Так же важным параметром генетических алгоритмов является размер популяции.

При практической реализации возможны две крайности:

• — слишком малый размер популяции (<10). Данный выбор в большинстве случаев годится только для очень простых задач. В противном случае будет наблюдаться быстрое вырождение популяции;
• — слишком большой размер популяции (>1000). Как и полагается, решение скорее всего, будет найдено за меньшее число поколений, однако часто ценой лишних вычислительных затрат. В некоторых случаях, когда просто надо найти решение, это не критично. Однако бывает так, что необходимо продемонстрировать преимущества (если есть) генетического подхода для решения выбранной проблемы перед уже методами и алгоритмами.

Исходя из данных рекомендаций, оптимальным размером популяции является 20−30 особей, однако в некоторых задачах требуется 50−100 особей. Исследования показывают, что размер популяции во многом зависит от размера хромосом. Так, для алгоритма с 32-битовыми хромосомами размер популяции будет больше, чем для алгоритма с 16-битовыми. [7].

Так как у генетических алгоритмов есть не оцениваемая численно характеристика, описывающая их поисковые способности, они зависят от всего, но в большей степени от стратегий селекции и генетических операторов. Отсюда:

• — использование более агрессивных вариантов отбора вкупе с достаточно большой вероятностью мутации во многих случаях позволяет добиться более хороших результатов, по сравнению с каноническим генетическим алгоритмом. Агрессивными стратегиями отбора можно считать отбор усечением с достаточно большим порогом (т.е. когда к воспроизводству допускается меньшее количество особей), а также турнирный отбор с размером турнира 4 и больше;
• — популяция большего размера работает стабильнее и зачастую лучше. Если же необходимо уложиться в некоторое количество вычислений целевой функции, то лучше поискать оптимальный размер, при котором и решение может быть найдено, и вычислительные затраты вполне приемлемые;
• — двухточечный и однородный операторы кроссинговера, как правило, работают лучше, чем одноточечный;
• — планомерное выслеживание и ликвидация диверсионных элементов в лице дубликатов в популяции повышают качество результатов и полезно против преждевременной сходимости;
• — применение стратегии элитарности — позволяет гарантированно оставить в популяции наилучших особей;
• — большая вероятность мутации в некоторых случаях способна улучшить работу алгоритма (особенно для малых популяций), но нежелательна, в силу внесения большой хаотичности в эволюционный процесс, что может отрицательно сказаться на стабильности работы алгоритма. [3]