Круглов В.В., Борисов В.В. - Искусственные нейронные сети (ИНС) Теория и практика (778918), страница 22
Текст из файла (страница 22)
При этом благодаря передаче генетической информации (генетическому наследованию) потомки наспедуют от родителей основные их качества. Таким образом, потомки сильных особей также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков ипи сотен поколений средняя приспособпенность особей данного вида заметно возрастает Дадим краткую справку о том, как устроены механизмы генетического наследования.
В каждой клетке любого животного содержится вся генетическая информация данной особи Эта информация записана в виде набора молекул ДНК, каждая из кото- 135 Здесь выбраны функции принадлежности колоколообразного ~аида Например, рых представляет собой цепочку, состоящую из молекул нукпеотидов четырех типов, обозначаемых А, Т, С и О. Собственно информацию несет порядок следования нукпеотидов в ДНК. Таким образом, генетический код особи — это длинная строка, где ис пользуются всего 4 символа.
В животной клетке каждая молекула ДНК окружена оболочкой, такое образование называется хромосомой. Каждое врожденное качеСтво особи (цвет глаз, наследственные болезни, тип волос и т. д) кодируется определенной частью хромосомы, которая называется геном этого свойства Например, ген цвета глаз содержит информацию, кодирующую определенный цвет глаз Различные значения гена называются его аппепями. При размножении особей происходит слияние двух родительских половых клеток, и их ДНК взаимодействуют, образуя ДНК потомка.
Основной способ взаимодействия — кроссовер гсгоззоиег, скрещивание) При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками При наследовании возможны мутации, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде. При этом произойдет скачкообразное повышение приспособленности вида 3.6.2. Что такое генетический алгоритм Пусть дана некоторая сложная целевая функция, зависящая от нескольких переменных, и требуется решить задачу оптимизации, т. е найти такие значения переменных, при которых значение функции максимально или минимально.
Эту задачу можно решить, применяя известные биологические эволюционные подходы к оптимизации Будем рассматривать каждый вариант (набор значений переменных) как особь, а значение целевой функции для этого варианта — как приспособленность данной особи Тогда в процессе эволюции приспособленность особей будет возрастать, а значит, будут появляться все более к более оптимальные варианты. Остановив эволюцию в некоторьй момент и выбрав лучший вариант, можно получить достаточно хорошее решение задачи.
Генегпоческий алгоритм ~ГА) — это последовательность управляющих действий и операций, моделирующая эволюционные процессы на основе аналогов механизмов генетического наследс. 136 Рис 3 20 Вариант структуры гаматичаского апгоритма вания и естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. Хромосома — вектор (поспедоватепьность) из нулей и единиц, каждая позиция (бит) которого называется веном. Особь (индивидуум) = генетический код — набор хромосом = вариант решения задачи. Кроссовер — операция, при которой две хромосомы обмениваются своими частями. Муглеция — спучайное изменение одной ипи нескольких позиций в хромосоме.
Генетические алгоритмы представляют собой скорее подход, чем единые алгоритмы. Они требуют содержательного наполнения дпя решения каждой конкретной задачи. На рис. 3.20 показан один из вариантов структуры генетического апгоритма. Вначапе генерируется случайная попупяция— несколько особей со случайным набором хромосом (чисповых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания особей, мутации и смены поколений (отбора).
В течение жизненного цикла популяции, т е. в результате нескольких случайных скрещиваний (посредством кроссовера) и мутаций, к ней добавляется какое-то количество новых вариантов Далее происходит отбор, в результате которого из старой популяции формируется новая, после чего старая попупяция погибает Поспе отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее Отбор в генетическом алгоритме тесно связан с принципами естественного отбора следующим образом. ° приспособленность особи соответствует значению целевой функции на заданном варианте; 137 ° выживание наиболее приспособленных особей соответствует тому, что популяция следующего поколения вариантов формируется с учетом целевой функции.
Чем приспособленнее особь, тем больше вероятность ее участия в кроссовере, т. е в размножении Таким образом, модель отбора определяет, как следует строить популяцию следующего поколения. Как правило, вероятность участия особи в скрещивании берется пропорциональной ее приспособленности. Часто используется так называемая сгпрагпегия элитиэма, при которой несколько лучших особей переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе.
В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность особей перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучший из найденных вариантов. Математически, изложенное можно представить следующим образом. Пусть имеется некоторая целевая функция от многих переменных, у которой необходимо найти глобальный максимум или минимум: ,«„) Представим независимые переменные в виде хромосом.
Для этого выполним кодирование независимых переменных либо в двоичном формате, либо в формате с плавающей запятой. В случае двоичного кодирования используется л бит для каждого параметра, причем, и может быть различным Если параметр может изменяться между минимальным (пип) и максимальным (гпах) значениями, можно использовать следующие формулы для преобразования: д(гпах- в(п) (г — в(п) г= +пил, д= (2" — 1) (гпах- т(п)(2' — 1) где д — значение параметра в двоичном формате, г — значение параметра в формате с плавающей запятой. Хромосомы в формате с плавающей запятой задаются путем последовательного размещения закодированных параметров друг за другом.
Наиболее хорошие результаты дает вариант представления хромосом в двоичном формате (особенно, при использовании кодов Грея). Однако в этом случае необходимо постоянно осуществлять кодирование/декодирование параметров (генов) Рассмотрим работу генетического алгоритма более подробно. Заранее подбирается некоторое представление для рассмат- 138 риваемого решения, размер и структура популяции. В первом поколении случайным образом генерируется популяция хромосом. Обычно, размер популяции постоянен. Определяется «полезность» хромосом После чего генетический алгоритм может начинать генерировать новую популяцию. Далее осуществляется репродуцирование, состоящее из: ° селекции; ° и трех генетических операторов кроссовера, мутации и инверсии, порядок применения которых не важен.
Из трех генетических операторов кроссовер является наиболее важным. Он генерирует новую хромосому потомка, объединяя генетический материал двух родителей. Существует несколько вариантов кроссовера Наиболее простым является одноточечный, в котором берутся две хромосомы и «перерезаются» в случайно выбранной точке. Хромосома потомка получается из начала одной и конца другой родительских хромосом: ОО«ОО~О~ ~ ~ОО~О1НОО ОО1~ОО~ОМСОО~О(МООО ИО1О1 1ОНОГООО)ГГГОО Мутация представляет собой случайное изменение хромосомы (обычно простым изменением состояния одного из битов на противоположное). Данный оператор позволяет, во-первых, более быстро находить локальные экстремумы и, во-вторых, перескочить в другой локальный экстремум оонооюн~оонлгооо — оо«ооюн юо~ и~оез Инверсия изменяет порядок бит в хромосоме путем циклической перестановки (случайное количество раз).
Многие модификации ГА обходятся без данного генетического оператора; ПОООООМООЮГ ПООГЕ оопоо~онюо~оггооо По скорости определения оптимума целевой функции генетические алгоритмы на несколько порядков превосходят случайный поиск. Причина этому заключается в том, что большинство систем имеют довольно независимые подсистемы. Вследствие чего при обмене генетическим материалом от каждого из родителей берутся гены, соответствующие наиболее удачному варианту определенной подсистемы (неудачные варианты постепенно погибают).
Генетический алгоритм позволяет накапливать удачные Решения для таких систем в целом. 139 Генетические алгоритмы менее применимы для систем, ко. торые сложно разбить на подсистемы Кроме того, они могут давать сбои из-за неудачного порядка расположения генов (например, если рядом расположены параметры, относящиеся к различным подсистемам), при котором преимущества обмена генетическим материалом сводятся к нулю. Это замечание несколько сглаживается в системах с диплоидным (двойным) генетическим набором Данные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
