Файл: Практикум по дисциплинам Методы искусственного интеллекта в управлении, Интеллектуальное управление сложными объектами.pdf

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

2.3. Основные понятия генетических алгоритмов
ГА используют словарь, заимствованный из естественной генетики:
– хромосомы (цепочки, или кодовые последовательности)– это упорядоченные последовательности генов. Хромосома – битовая строка 0101…101, или вектор из нулей и единиц, которая определяет точку пространства поиска и представляет собой потенциальное решение задачи;
– гены – элементы, из которых состоит хромосома;
– популяция – это конечное множество особей;
– особи, входящие в популяцию, в ГА представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска;
– генотип, или структура, – это набор хромосом определенной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (генотип может состоять даже из одной хромосомы);
– фенотип – это набор значений, соответствующих данному генотипу; иначе его называют либо декодированной структурой, либо множеством параметров задачи;
– аллель – значение конкретного гена, также определяемое как значение свойства;
– локус, или позиция, – место размещения данного гена в хромосоме (цепочке). Множество позиций генов называются локами;
– кроссовер – операция скрещивания хромосом, при котором хромосомы обмениваются своими частями;
– мутация – случайное изменение одной или нескольких позиций в хромосоме;
– функция приспособленности, или функция пригодности (fitness
function), – функция оценки, мера приспособленности особи в популяции, которая позволяет выбирать наиболее приспособленные особи;
– механизм селекции заключается в выборе хромосом с наивысшей оценкой (т.е. наиболее приспособленных), которые репродуцируют чаще, чем особи с более низкой оценкой;

– репродукция – создание новых хромосом в результате
рекомбинации генов родительских хромосом;
– рекомбинация – это процесс, в результате которого возникают новые комбинации генов. Для этого используется две операции:
скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызвать изменения в отдельных хромосомах.
2.4. Стандартный генетический алгоритм
Стандартный ГА состоит из следующих шагов: 1) инициа- лизация, или выбор исходной популяции хромосом; 2) оценка приспособленности хромосом в популяции; 3) проверка условия остановки алгоритма; 4) селекция хромосом; 5) применение генетических операторов; 6) формирование новой популяции;
7) выбор «наилучшей» хромосомы.
На рис. 5.1 представлена блок-схема ГА, включающего следующие этапы:
Шаг 1. Инициализация, т.е. формирование исходной популяции хромосом, заключается в случайном выборе заданного количества хромосом (особей), представляемых двоичными последователь- ностями фиксированной длины.
Шаг 2.
Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение функции приспособленности, тем выше «качество» хромосомы.
Шаг 3.
Проверка условия остановки алгоритма. Остановка работы ГА определяется следующими условиями:
1) в оптимизационных задачах, если известно максимальное
(или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения;
2) остановка алгоритма также может произойти в случае, когда его выполнение не приводит к улучшению уже достигнутого значения;

3) алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций.
Рис. 5.1. Блок-схема генетического алгоритма
Если условие остановки выполнено, то осуществляется переход к этапу выбора «наилучшей» хромосомы, вывода результата алгоритма и завершение работы алгоритма. В противном случае – переход к следующему шагу.
Шаг 4. Селекция хромосом, которая заключается в выборе тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Селекция хромосом нужна для создания условий преимущества более приспособленным хромосомам в процессе репродукции новой

популяции. Такой выбор соответствует принципу естественного отбора, согласно которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности.
Наиболее популярным методом селекции считается метод
рулетки, который свое название получил по аналогии с азартной игрой: каждой хромосоме сопоставляется сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Очевидно, что все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматри- ваемой популяции. Итак, каждой хромосоме
,
1,2, … , , соответствует сектор колеса
∗
, выраженный в процентах:
∗
∗
∙ 100%, (5.1) где
∗
∙– вероятность селекции i-й хромосомы, которая рассчитывается с использованием функции приспособленности каждой хромосомы
∗
:
∗
∗
∑
∗
. 5.2
Селекция хромосомы, таким образом, осуществляется на основе моделирования поворота колеса рулетки, где «выигравшая» (т.е. выбранная) хромосома определяется по выпавшему сектору колеса.
Разумеется, чем больше такой сектор, тем больше вероятность
«победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности.
В результате процесса селекции создается родительская
популяция, также называемая родительским пулом, с численностью
, равной численности текущей популяции.
Шаг 5. Применение генетических операторов к хромосомам, отобранным с помощью селекции. Формируется новая популяция потомков от созданной на предыдущем шаге родительской популяции.
Применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation).
Оператор скрещивания моделирует процесс скрещивания особей путем обмена частями хромосом между двумя или более

особями в популяции следующим образом. На первом этапе скрещивания выбираются пары хромосом из родительской популяции
(родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. Хромосомы из родительской популяции случайным способом объединяются в пары.
Для каждой пары отобранных родителей разыгрывается позиция гена
(локус) в хромосоме, определяющая точку скрещивания. Если хромосома каждого из родителей состоит из генов, то очевидно, что точка скрещивания представляет собой натуральное число, меньшее . Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала
1,
1 . В результате скрещивания пары родительских хромосом получается следующая пара потомков:
1) потомок, хромосома которого на позициях от 1 до состоит из генов первого родителя, а на позициях от
1 до – из генов второго родителя;
2) потомок, хромосома которого на позициях от 1 до состоит из генов второго родителя, а на позициях от
1 до – из генов первого родителя.
Оператор мутации – оператор, моделирующий стохастическое изменение части хромосом. Оператор с вероятностью изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Например, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0, что приводит к образованию хромосомы [100110001010].
Оператор мутации играет второстепенную роль по сравнению с оператором скрещивания, т.к. мутация осуществляется достаточно редко (из аналогии с миром живых организмов) и составляет примерно 1%. Оператор мутации необходим, чтобы, с одной стороны, ввести в популяцию некоторое разнообразие и расширить область поиска, а с другой – чтобы предупредить потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания и не привести к таким изменениям потомков, которые будут далеки от приемлемых решений.

В ГА мутация хромосом может выполняться на популяции родителей перед скрещиванием либо на популяции потомков, образованных в результате скрещивания.
Шаг 6. Формирование новой популяции. Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции, которая становится так называемой текущей популяцией для данной итерации ГА. Далее осуществляется переход к шагу 2, на котором определяются оценки приспособленности хромосом в носой популяции.
Шаг 7. Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.
3. Методика выполнения работы
Пример. Необходимонайти максимум функции
2 1 на отрезке
0 31 с помощью генетических алгоритмов.
Очевидно, что эта задача легко решается с использованием необходимого условия экстремума, однако на этом примере удобно проиллюстрировать принципы работы ГА.
Допустим, что принимает целые значения из заданного диапазона. Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 32 точек со значениями
0, 1, … , 31, для обнаружения той точки, в которой функция принимает максимальное (или минимальное) значение. В этом случае в качестве параметра задачи выступает переменная .
Множество
0, 1, … , 31 составляет пространство поиска и одновременно – множество потенциальных решений задачи. Каждое из 32 чисел, принадлежащих этому множеству, называется либо точкой пространства поиска решений, либо решением, либо значением параметра, либо фенотипом. Решение, оптимизирующее функцию, называется наилучшим, или оптимальным, решением.
В качестве функции пригодности (приспособленности) выступает сама исходная функция. Чем больше ее значение, тем лучше пригодность хромосомы.

3.1. Инициализация, или выбор исходной популяции хромосом
3.1.1. Кодирование фенотипов в хромосомы.
Очевидно, что для кодирования в двоичную систему значений аргументов функции , изменяющихся в диапазоне
0 31, потребуется 5 двоичных разрядов. Соответствие фенотипов и генотипов (хромосом) показано в табл. 5.1.
Таблица 5.1
Кодирование значений параметра в двоичной системе
Фенотип ch
*
0 1 2 3 4 5 6 7
Генотип ch
00000 00001 00010 00011 00100 00101 00110 00111
Фенотип ch
*
8 9 10 11 12 13 14 15
Генотип ch
01000 01001 01010 01011 01100 01101 01110 01111
Фенотип ch
*
16 17 18 19 20 21 22 23
Генотип ch
10000 10001 10010 10011 10100 10101 10110 10111
Фенотип ch
*
24 25 26 27 28 29 30 31
Генотип ch
11000 11001 11010 11011 11100 11101 11110 11111
Представленные кодовые последовательности называются
хромосомами, которые выступают в роли генотипов. Каждая из хромосом состоит из 5 генов (длиной 5 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1.
3.1.2. Генерация начальной выборочной популяции особей, или генотипов.
Итак, популяция состоит из особей, выбираемых среди исходных
32 хромосом. Встает вопрос: какого размера должна быть начальная популяция и каким методом ее определять. В классическом генетическом алгоритме принято определять выборочную популяцию случайным образом.
Устанавливается размер исходной популяции с численностью, равной шести хромосомам
6; а затем случайным образом генерируется популяция. Предположим, что случайный выбор определил множество хромосом
,
, … ,
, представляющих собой закодированную форму фенотипов:
∗
,
∗
, … ,
∗
(табл. 5.2).

Таблица 5.2
Хромосомы исходной популяции и их фенотипы
Хромосома
Фенотип
Хромосома
Фенотип
10011 00011 00111
∗
19
∗
3
∗
7 10101 01000 11101
∗
21
∗
8
∗
29 3.2. Оценка приспособленности хромосом в популяции
Функция приспособленности отдельных хромосом в популяции определяется значением исходной функции
2 1 для значений , соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам (табл. 5.3).
Таблица 5.3
Значения функции приспособленности для каждой хромосомы
Хромосома
Фенотип
Функция приспособленности
10011 00011 00111 10101 01000 11101
∗
19
∗
3
∗
7
∗
21
∗
8
∗
29
∗
723
∗
19
∗
99
∗
883
∗
129
∗
1683 3.3.
Проверка условия остановки алгоритма
Наибольшим значением функции приспособленности характеризуется хромосома
(
∗
1683
), п оэтому в этой популяции она считается наилучшим кандидатом на решение задачи.
Очевидным является то, что в данной задаче максимум исходной функции достигается на интервале
0 31 в точке
31 (
1923 , поэтому можно сделать вывод о том, что лучшее значение F еще не найдено. Это означает, что условие остановки алгоритма не выполняется и осуществляется переход к следующему шагу алгоритма.
3.4. Селекция хромосом
Селекция хромосом осуществляется методом рулетки. Для отбора наиболее приспособленных хромосом для каждой из
6 хромосом текущей популяции задается вероятность выбора

∗
∙по формуле (5.2) пропорционально относительной приспособленности. Затем числовой промежуток [0, 100] разбивается на интервалы длиной
∗
(5.1) и формируются секторы колеса рулетки, выраженные в процентах (табл. 5.4).
Таблица 5.4
Секторы колеса рулетки
Фенотип
∗
Значения функции приспособленности
∗
Вероятность выбора
∗
,%
– сектор колеса рулетки
Σ
∗
,%
∗
19
∗
723 20,45 20,45
∗
3
∗
19 0,54 20,99
∗
7
∗
99 2,80 23,79
∗
21
∗
883 24,97 48,76
∗
8
∗
129 3,64 52,41
∗
29
∗
1683 47,59 100
∑
∗
3536 100
На рис. 5.2. представлено колесо рулетки, построенное на основе табл. 5.4. Чем больше сектор колеса рулетки, тем больше вероятность победы соответствующей хромосомы, поэтому в среднем функция приспособленности от поколения к поколению будет возрастать.
Рис. 5.2. Колесо рулетки для селекции
Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому.
Процесс отбора основан на вращении колеса рулетки в количестве раз, равном размеру популяции. Так, для рассматриваемого примера