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

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

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

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

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

Неоднородная мутация.

Одним из способов организации самоадаптирующегося алгоритма является применение неоднородной мутации. Если мутирует ген , то новое значение случайно генерируется на отрезке [mini, maxi]:

где q случайным образом принимает значения 0 или 1; r - случайное число, принимающее значение из диапазона [0; 1]; t - номер поколения; Т - максимальное число поколений; b - некоторый параметр, обусловленный природой задачи; и - верхняя и нижняя границы для величины .

Инцест.

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

Заключение

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

Преимущества генетических алгоритмов:

· не требуют никакой информации о поведении функции (например, дифференцируемости и непрерывности);

· относительно стойки к попаданию в локальные оптимумы;

· пригодны для решения крупномасштабных задач оптимизации за счет эффективного распараллеливания;

· могут быть использованы для широкого класса задач;

· просты в реализации;

· могут быть использованы в задачах с изменяющейся средой.

В то же время существует ряд трудностей в практическом использовании генетических алгоритмов, а именно:

· очень сложно найти точный глобальный оптимум;

· генетические алгоритмы неэффективно применять в случае оптимизации функции, требующей большого времени на вычисление;

· сложно смоделировать для нахождения всех решений задачи;

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