2. С определенной вероятностью (вероятностью кроссовера) выбрать вторую особь из популяции и произвести оператор кроссовера;

3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации;

4. С определенной вероятностью (вероятностью инверсии) выполнить оператор инверсии;

5. Поместить полученную хромосому в новую популяцию;

6. Выполнить операции, начиная с пункта 3, k-раз;

7. Увеличить номер текущей эпохи t=t+1;

8. Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2;

Распишем более подробно следующие этапы:

1. Выбор родительской пары:

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

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

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

Другие два способа формирования родительской пары – инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров. В связи с этим различают генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга оказалось более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма. Наиболее полезно применение обоих представленных методов для многоэкстремальных задач. Однако два этих способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области. [10]

2. Механизм отбора:

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

В последние годы, реализовано много генетических алгоритмов и в большинстве случаев они мало похожи на алгоритм, представленный на рис.5. По этой причине в настоящее время под термином "генетические алгоритмы" скрывается не одна модель, а достаточно широкий класс алгоритмов.[2]

1.4 Вывод к Главе 1

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

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

Работа генетического алгоритма имитирует естественную жизнь, только сильно упрощенную.

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

ГЛАВА 2 ЗАДАЧИ ОПТИМИЗАЦИИ

2.1 Задачи, решаемые с помощью генетических алгоритмов

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

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

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

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

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

Генетические алгоритмы являются эффективной процедурой поиска, которая конкурирует с другими процедурами. Эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, операторов, настраивания параметров, отдельных критериев успеха. [1]

2.2 Математическая постановка задачи оптимизации

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

Нельзя отождествлять критерий (критерии) оптимальности и целевую функцию.

Целевая функция – это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.