Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Генетический алгоритм




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

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

f(x1, x2, x3, …, xN). (5.31)

Для того чтобы заработал ГА, необходимо представить независимые переменные в виде хромосом. Первым шагом является преобразование независимых переменных в хромосомы, которые будут содержать всю необходимую информацию о каждой создаваемой особи. Имеется два варианта кодирования параметров:

в двоичном формате;

в формате с плавающей запятой.

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

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

селекции и трех генетических операторов (порядок применения не важен);

кроссовера;

мутации;

инверсии.

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

001100101110010|11000     ®   001100101110010 11100
110101101101000|11100

 

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

00110010111001011000 ® 00110010111001111000

 

Инверсия инвертирует (изменяет) порядок битов в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации ГА обходятся без данного генетического оператора.

00110010111001011000 ® 11000001100101110010

 

Очень важно понять, за счет чего ГА на несколько порядков превосходит по быстроте случайный поиск во многих задачах. Дело, видимо, в том, что большинство систем имеют довольно независимые подсистемы. Вследствие этого, при обмене генетическим материалом часто может встретиться ситуация, когда от каждого из родителей берутся гены, соответствующие наиболее удачному варианту определенной подсистемы (остальные "уродцы" постепенно вымирают). Другими словами, ГА позволяет накапливать удачные решения для систем, состоящих из относительно независимых подсистем (а это большинство современных сложных технических систем и все известные живые организмы). Соответственно, можно предсказать, когда ГА скорее всего даст сбой (или, по крайней мере, не покажет особых преимуществ перед методом Монте-Карло) - системы, которые сложно разбить на подсистемы (узлы, модули), а также при неудачном порядке расположения генов (рядом расположены параметры, относящиеся к различным подсистемам), когда преимущества обмена генетическим материалом сводятся к нулю. Последнее замечание несколько ослабляется в системах с диплоидным (двойным) генетическим набором.

 

Организация ЭВМ и систем/Архитектура ЭВМ и систем


Поделиться:

Дата добавления: 2015-04-18; просмотров: 64; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты