популяции.

• Целевая функция для оценки приспособленности решений. [11]

   1.2 Основные генетические операторы

 

     Стандартные операторы для всех типов генетических алгоритмов это: скрещивание, мутация и селекция.

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

     Действует он следующим образом:

1. Из популяции выбираются две особи, которые будут родителями;
2. Определяется (обычно случайным образом) точка разрыва;
3. Потомок определяется как конкатенация части первого и второго родителя.

 

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

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

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

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

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

     Оператор  селекции осуществляет отбор хромосом в соответствии со значениями их функции приспособленности.

     Наиболее эффективные  два механизма отбора – элитный отбор и отбор с вытеснением.

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

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

     Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно  поддерживается достаточное генетическое разнообразие. [8]

    1.3 Работа генетического алгоритма

 

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

    Схематичное описание функционирования генетического  алгоритма (Рисунок 1): 

    

    Рисунок 1 Алгоритм работы классического генетического алгоритма 

     Функционирование  генетического алгоритма можно  описать следующими шагами:

     Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k-особей.

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

1. Выбрать особь из популяции;
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 Математическая постановка задачи оптимизации

 

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