КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Пример 9.2
Рассмотрим сильно упрощенный и довольно искусственный пример, состоящий в нахождении хромосомы с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Посмотрим, как протекает процесс решения этой весьма тривиальной задачи с помощью генетического алгоритма. Инициализация, или выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной 12 битов. Это можно достигнуть, например, подбрасыванием монеты (96 раз, при выпадении «орла» приписывается значение 1, а в случае «решки» – 0). Таким образом, можно сформировать исходную популяцию сh1 = [111001100101] ch5 = [010001100100] ch2 = [001100111010] ch6 = [010011000101] ch3 = [011101110011] ch7 = [101011011011] ch4 = [001000101000] ch8 = [000010111100] Оценка приспособленности хромосом в популяции. В рассматриваемом упрощенном примере решается задача нахождения такой хромосомы, которая содержит наибольшее количество единиц. Поэтому функция приспособленности определяет количество единиц в хромосоме. Обозначим функцию приспособленности символом F. Тогда ее значения для каждой хромосомы из исходной популяции будут такие: F (ch1) = 7 F (ch5) = 4 F (ch2) = 6 F (ch6) = 5 F (ch3) = 8 F (ch7) = 8 F (ch4) = 3 F (ch8) = 5 Хромосомы ch3 и ch7 характеризуются наибольшими значениями функции принадлежности. В этой популяции они считаются наилучшими кандидатами на решение задачи. Если в соответствии с блок-схемой генетического алгоритма (рис.9.1) условие остановки алгоритма не выполняется, то на следующем шаге производится селекция хромосом из текущей популяции. Селекция хромосом. Селекция производится методом рулетки. На основании формул (9.2) и (9.3) для каждой из 8 хромосом текущей популяции (в нашем случае – исходной популяции, для N = 8) получаем секторы колеса рулетки, выраженные в процентах (рис.9.2).
v (ch1) = 15,22 v (ch5) = 8,70 v (ch2) = 13,04 v (ch6) = 10,87 v (cn3) = 17,39 v (ch7) = 17,39 v (ch4) = 6,52 v (ch8) = 10,87 Рис. 9.2. Колесо рулетки для селекции в примере 6.4. Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел: 79 44 9 74 44 86 48 23 Это означает выбор хромосом ch7 ch3 ch1 ch7 ch3 ch7 ch4 ch2 Как видно, хромосома ch7 была выбрана трижды, а хромосома ch3 – дважды. Заметим, что именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана и хромосома ch4 с наименьшим значением функции приспособленности. Все выбранные таким образом хромосомы включаются в так называемый родительский пул. Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания р с = 1, а вероятность мутации рm = 0. Допустим, что из этих хромосом случайным образом сформированы пары родителей ch2 и ch7 ch1 и ch7 ch3 и ch4 ch3 и ch7 Для первой пары случайным образом выбрана точка скрещивания l k = 4, для второй – l k = 3, для третьей – l k = 11, для четвертой – l k = 5. В результате выполнения оператора скрещивания получаются 4 пары потомков. Если бы при случайном подборе пар хромосом для скрещивания были объединены, например, ch3 с ch3 и ch4 с ch7 вместо ch3 с ch4 и ch3 с ch7, а другие пары остались без изменения, то скрещивание ch3 с ch3 дало бы две такие же хромосомы независимо от разыгранной точки скрещивания. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация наиболее вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию.
Формирование новой популяции. После выполнения операции скрещивания мы получаем следующую популяцию потомков: Ch1 = [001111011011] Ch5 = [011101110010] Ch2 = [101000111010] Ch6 = [001000101001] Ch3 = [111011011011] Ch7 = [011101011011] Ch4 = [101001100101] Ch8 = [101011110011] Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с заглавной буквы С. Согласно блок-схеме генетического алгоритма (рис.9.1) производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей. Значения функций приспособленности хромосом этой популяции составляют F (Ch1) = 8 F (Ch5) = 7 F (Ch2) = 6 F (Ch6) = 4 F (Ch3) = 9 F (Ch7) = 8 F (Ch4) = 6 F (Ch8) = 8 Заметно, что популяция потомков характеризуется гораздо более высоким средним значением функции приспособленности, чем популяция родителей. Обратим внимание, что в результате скрещивания получена хромосома Сh3 с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из родительской популяции. Однако могло произойти и обратное, поскольку после скрещивания на первой итерации хромосома, которая в родительской популяции характеризовалась наибольшим значением функции приспособленности, могла просто «потеряться». Помимо этого «средняя» приспособленность новой популяции все равно оказалась бы выше предыдущей, а хромосомы с большими значениями функции приспособленности имели бы шансы появиться в следующих поколениях.
Дата добавления: 2014-01-05; Просмотров: 379; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |