Лекция: Генетический алгоритм и другие методы оптимизации

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

Для того чтобы подчеркнуть ограниченность возможностей полного перебора вариантов в сложных проблемах, рассмотрим задачу коммивояжера, которая формулируется так. Имеется n городов, расположенных на различном расстоянии друг от друга, и соединенных дорогами. Требуется обойти все города кратчайшим путем, побывав в каждом городе только однажды. На рис. 1.3 показан пример для 5 городов.

Когда рассматривается n городов, при построении маршрута существует n вариантов выбора первого города, n-1вариантов выбора второго города и т.д. Таким образом, количество вариантов путей в задаче для n городов оказывается равно n!

И если для n=5 получается 5!=120 вариантов, то для n=20 получается 20!»2.4*1018 вариантов. Несложные подсчеты показывают, что при скорости расчетов 500 млн. вариантов в секунду потребуется более 150 лет для полного перебора вариантов. Таким образом, решение задач перебором вариантов возможно далеко не всегда.

Рис. 1.3.Задача коммивояжера для 5 городов

Сделанное замечание позволяет утверждать, что ГА в среднем будет всегда эффективнее, чем перебор вариантов (рис. 1.4).

Рис. 1.4.Качественное сравнение различных методов оптимизации

Отличия ГА от других алгоритмов случайного поиска заключается в следующем:

1. В ГА используются коды параметров, а не сами параметры. Параметры кодируются в цепочки конечной длины, в процессе итераций эти цепочки тестируются и видоизменяются;

2. Поиск происходит не в точках пространства, а на основе популяции точек;

3. Генетический алгоритм использует знания о прошлых полученных решениях. Он обеспечивает концентрацию решений в наиболее эффективных областях пространства решений;

4. Генетический алгоритм использует только оценки решений, а не их производные или другие параметры.

В ГА не накладываются ограничения на свойства целевой функции в виде непрерывности, дифференцируемости и т.д. Она подразумевается как устройство типа «черного ящика», которое на вход получает параметры, а на выход выводит результат.

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

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

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

§ 1.2. Общие сведения о генетическом алгоритме