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

⇐ ПредыдущаяСтр 6 из 11Следующая ⇒

Простой генетический алгоритм состоит из следующих стадий:

1. Генерация исходного поколения (случайный выбор аллелей).

2. Циклический процесс смены поколений.

Пример подпрограммы смены поколений:

For (k=0; k< G; k++)

{for (c_j=0, j< N; j++)

{Выбор родительской пары хромосом;

Кроссовер[1]

Мутации

Оценка F потомков

Селекция

}

Замена текущего поколения

}

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

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

Пример кроссовера рассмотрен на прошлом занятии.

Расстояние от максимума функции полезности (или от минимума функции стоимости или ущерба) определяет вероятность выбора родителей для следующего поколения.

, если ищем минимум.

Это - правило колеса рулетки

Кроссовер (скрещивание)

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

Пример.

Родитель A	a	b	c	d	e	f	g	h
Родитель B	i	j	k	l	m	n	o	p

Потомок С	a	b	c	d	m	n	o	p
Потомок D	i	j	k	l	e	f	g	h

Мутации. Оператор мутации расширяет область генетического поиска. С некоторой вероятностью происходит замена гена не от родителя. Новые гены, не из имеющегося набора только так и могут возникать. Мутации остро необходимы в экстремальных случаях, например, при сокращении количества особей до критического уровня (Адам + Ева).

Селекция. Из каждой генерации пары потомков (или более) в новое поколение включается только лучший потомок из пары. Внутренний цикл оканчивается, когда количество экземпляров нового поколения достигает количества экземпляров старого поколения. Следовательно, происходит замена поколения на новое. (Например, по мере приобретения гражданами телевизоров Sharp, телевизоры «Рубин» оказываются на помойке).

Количество циклов (внешних) определяется по признакам стагнации (застоя, вырождения) популяции, но с условием превышения заданного предельного времени.

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

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

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

Метод частично спаренных скрещиваний PMX (Partly Matched Crossover). Метод состоит в том, что после скрещивания анализируется результат на наличие повторов. При наличии повторов лишние «гены» меняются на их парно-сопряженные гены. Этот метод целесообразно применять в том случае, когда наличие одинаковых «генов» нежелательно, либо нецелесообразно, а разнообразие, наоборот, приветствуется. Такая ситуация имеет место далеко не всегда.

Пример.

Родитель A
Родитель B

Предполагаемый «Потомок_С» получает запрещенную комбинацию «генов».

Потомок С

Повторяющиеся «гены» заменяем на сопряженные с ними: 1→ 3, 2→ 5, 9→ 4. Получаем «разрешенного потомка».

Потомок D

Селекция может осуществляться тут же.

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

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

Вариант 3. Из M родителей создадим много больше, чем M потомков (и мутантов), выберем M лучших особей и включим в результат.

Уточнение: При анализе для определения «лучших» родителей тоже целесообразно принимать во внимание наряду с потомками (можно считать, что в частности наряду с потомками всегда имеются клоны) – в качестве претендентов в «лучшие». Если родители (клоны) не попадают в список лучших, они не включаются в результат, если попадают, включаются на правах полноценного члена нового поколения.

Признак стагнации популяции: «клоны» лучше всех потомков от скрещиваний и мутаций. Т.е развития нет, развитие из этой ситуации противопоказано, зашло в тупик.

Выбор из совокупности клонов, потомков и мутантов может быть жестким или «по вероятности». По тем же правилам, по которым выбирались родители, выбирается и новое поколение (не следует путать – это не «такое же» правило, это то же самое правило, оно же).

где N_r – размер репродукционной группы.

Если функция полезности F зависит еще и от порядка «генов» то необходимо переупорядочивание. Цель – «нащупать» «полезные сочетания», «хромосомные блоки», разместить их близко друг к другу.

Дихотомическая кластеризация – разбиение множества элементов на два подмножества с минимальным числом связей между ними.

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

Движение к оптимуму методом синхронного детектирования.

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

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

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

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

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

Бесполое размножение – применение только мутаций.

Половое размножение – скрещивание пар по следующей схеме (для одного потомка):

- в потомках присутствует половина генного набора от каждого родителя. Могут браться и не равные части генных наборов:

Трехполое размножение:

- в потомках присутствует треть генного набора от каждого родителя. В случае неравных частей набора:

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

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

1. Создание начального множества кодов K (популяции) – «сотворение мира».

2. Селекция (отбор) по значению целевой функции.

3. Скрещивание (обмен кодовыми последовательностями, кроссовер): а) точечный, б) двухточечный, в) равномерный, г) другой.

4. Если необходимо, то коррекция.

5. Мутации.

6. Если необходимо, то перестановка.

7. Редукция (сокращение получаемого множества K* за счет роста количества особей на этапах 3-5 до множества изначальной величины K).

8. Исследование критерия остановки, если нет, то возврат на 2, если да, то вывод результата из 7.

Вопрос: в чем отличие редукции от селекции?

Редукция – отсечение плохих вариантов.

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

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒