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

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

Набор операторов - для генерации новых решений из предыдущей популяции; Целевая функция - для оценки приспособленности решений.

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

Недостатки генетических алгоритмов: время исполнения функции оценки велико, необходимо найти все решения задачи, а не одно из них, а также сложная конфигурация (сложное кодирование решения).

Решение задач оптимизации. Оптимизирование некоторой функции F(X1,X2,..,Xn). Поиск глобального максимума. Каждая особь состоит из массива X и значения функции F на переменных этого массива. Суть ГА:

1. Генерация начальной популяции - заполнение популяции особями, в которых элементы массива X (биты) заполнены случайным образом.

2. Отбор - используем элитный отбор, то есть берем особей с максимальными значениями функции F и составим из них все возможные пары.

3. Скрещивание – используем одноточечное скрещивание. Возьмем случайную точку на массиве X и произведем обмен между полученными частями для каждой хромосомы. Новые особи с некоторой вероятностью мутируют - инвертируется случайный бит массива X этой особи.

4. Полученные особи-потомки добавляются в популяцию после переоценки, т.е. новые особи добавляют взамен старых, при условии, что значение функции на новых особях выше, чем на старых.

5. Если самое лучшее решение в популяции нас не удовлетворяет, то переход на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются бесконечно.

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