Учебник_Final

5.3.4. Достоинства и недостатки генетических алгоритмов

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

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

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

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

К недостаткам ГА следует отнести следующее:

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

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

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

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

пакет Evolver 4.0 разработки компании Palisade Corp., представляющий собой дополнение к табличному процессору MS Exсel;
пакет Gene Hunter 1.0 компании Ward System Group;
пакет Genetic Training Option (GTO) компании California Scientific Software, созданный специально для обучения нейронных сетей и являющийся приложением пакета Brain Maker.

Содержание