МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

"ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ"

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к практической работе №11

"Исследование генетических алгоритмов"

по курсу " ОСНОВЫ ВЫЧИСЛИТЕЛЬНОГО ИНТЕЛЛЕКТА "

для студентов специальностей 7.091501, 7.091502, 7.091503

дневной и заочной форм обучения

Харьков НТУ "ХПИ" 2010

1. Цель работы

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

2. Краткие сведения из теории

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

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

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

НАЧАЛО /*генетический алгоритм*/

Создать начальную популяцию

Оценить приспособленность каждой особи

останов := ЛОЖЬ

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /*создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /*цикл воспроизводства */

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

Скрестить выбранные особи и получить двух потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ приспособленность лучшего потомка > порога ТО

останов := ИСТИНА

КОНЕЦ

КОНЕЦ

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

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

Для реализации в среде Matlab генетических вычислений существуют следующие элементарные функции.

Функция	Назначение
1	2
Chromobin (length,cod)	Задает хромосому в форме бинарной строки длины length, если cad = 0, используется двоичное кодирование, если cod= 1, используется код Грэя.
Chrotnoint (length)	Задает хромосому в форме последовательности целых чисел длины length.
Chromolist(length)	Задает хромосому в форме списка пар (номер гена, целое значение) длины length.
InitPopuIation (rand, chl, S)	Создает исходную первичную популяцию объектов – хромосом, причем rand – это функция порождения случайной хромосомы, cht – тип хромосомы (Chromobin, Chromoint, Chromolist), по умолчанию Chromobin, S — количество хромосом в популяции.
Mutationbin (chromo)	Мутация в форме инверсии случайно выбранного гена хромосомы chroma.
1	2
Mutationint (chroma, max)	Мутация случайно выбранного гена дополнением до max значения.
Mutationlist (chroma, max)	Мутация случайно выбранного гена дополнением до max значения.
Recombinationbin (chromo1, chromo2)	Возвращает двух потомков, составленных из родительских фрагментов chromo1, chromo2, причем фрагменты получены в случайной точке разрезания, а хромосомы — это бинарные строки.
Recombinationint (chromo1, chromo2)	Возвращает двух потомков, составленных из родительских фрагментов chromo1, chromo2, причем фрагменты получены в случайной точке разрезания, а хромосомы — это последовательности целых чисел.
Recombinationbinm (chromolist, parents, sons)	Возвращает потомков в количестве sons, составленных из родительских фрагментов, причем список chromolist содержит родителей в количестве parents. Фрагменты получены в случайных точках разрезания случайных родителей из chromolist, а хромосомы — это бинарные строки.
Recombinationintm (chromolist, parents, sons)	Возвращает потомков в количестве sons, составленных из родительских фрагментов, причем список chromolist содержит родителей в количестве parents. Фрагменты получены в случайных точках разрезания случайных родителей из chromolist, а хромосомы — это последовательности целых чисел.
Rang(P, fitfunction)	Ранжирование хромосом популяции Р с помощью функции оптимальности fitfunction, причем функция оптимальности задается конкретно для каждой проблемной области.
Selection (Pparents)	Пропорциональный отбор хромосом из популяции Р. Возвращает подпопуляцию хромосом, участвующих в формировании следующего поколения.
Newgeneration (Pold, Pparents, elite)	Формирует новое поколение популяции из старой, популяции потомков, выбранных для рекомбинации хромосом Pparents, причем, если параметр elite = 0, то элитное сохранение лучших не используется, если elite — целое число, то столько лучших хромосом текущего поколения переходит в следующее.
InitPapulationM (rand, S)	Создает исходную первичную популяцию объектов – хромосом, причем rand – функция порождения случайной хромосомы, S – количество хромосом в популяции, причем формируются не полностью определенные хромосомы типа Chromolist. Функция используется для мобильного ГА.
1	2
Cut (cromo)	Разрезает хромосому типа Chromolist в случайном месте.
Splice (chromo1, chromо2)	Склеивает две хромосомы типа Chromolist, причем в результирующей хромосоме возможно дублирование генов, которые доминируют слева направо.
AccumulatePop (P, q)	Функция разрезает и склеивает хромосомы популяции Pop, причем склеивание доминирует над разрезанием. Функция реализует стадию насыщения мобильного ГА. Параметр q — количество поколений в стадии насыщения.

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

Функция standartga (cht, qpop, initpopfun, mutfun, recfun, fitfun, rangfun, selfun, newgen, terminationcond, fitgoalpmut, precom) реализует генетическую оптимизацию популяции хромосом типа cht размера qpop, которая инициализируется функцией инициализации initpopfun. Генетическая оптимизация использует оператор мутации типа mutfun с вероятностью pmut, оператор рекомбинации — с вероятностью precom. Ранжирование, селекция и формирование нового поколения осуществляются функциями rangfun, selfun, newgen соответственно на основе функции оптимальности fitfun. Завершение оптимизации задается либо параметром terminationcond, как число поколений, либо параметром fitgoal, как целевым значением функции оптимальности. Если параметр pmut = 0, то мутация не используется; если precom = 0, то рекомбинация не используется и стандартный ГА превращается в алгоритм «только мутация».

Функция mobilga (qpop, initpopfun, accumfun, cutfun, splicefun, fitfun, rangfun, selfun, newgen, terminationcond, fitgoal, pcut, psplice) реализует генетическую оптимизацию популяции хромосом размера qpop с помощью мобильного ГА, которая инициализируется функцией инициализации initpopfun. Стадия насыщения реализуется функцией accumfun. Генетическая оптимизация использует оператор разрезания cutfun с вероятностью рсut, оператор склеивания — с вероятностью psplice. Ранжирование, селекция и формирование нового поколения осуществляются функциями rangfun, selfun, newgen соответственно на основе функции оптимальности fitfut. Завершение оптимизации задается либо параметром terminationcond, как число поколений, либо параметром fitgoal, как целевым значением функции оптимальности.