Файл: Генетические алгоритмы.ppt

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


Таблица 3: Вероятность оказаться родителем

Хромосома	Подходящесть
1	(1/84)/0.135266 = 8.80%
2	(1/24)/0.135266 = 30.8%
3	(1/26)/0.135266 = 28.4%
4	(1/133)/0.135266 = 5.56%
5	(1/28)/0.135266 = 26.4%

Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-гранная игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2840
сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:


Таблица 4: Симуляция выбора родителей

Хромосома отца	Хромосома матери
3	1
5	2
3	5
2	5
5	3

Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть отец содержит следующий набор решений: a1,b1,c1,d1, а мать- a2,b2,c2,d2, тогда возможно 6 различных кроссоверов
(| = разделительная линия):


Таблица 5: Кроссоверы между родителями

Хромосома-отец	Хромосома-мать	Хромосома-потомок
a1 | b1,c1,d1	a2 | b2,c2,d2	a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1	a2,b2 | c2,d2	a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1	a2,b2,c2 | d2	a1,b1,c1,d2 or a2,b2,c2,d1

Таблица 6: Симуляция кросс-оверов хромосом родителей

Хромосома-отец	Хромосома-мать	Хромосома-потомок
(13 | 5,7,3)	(1 | 28,15,3)	(13,28,15,3)
(9,13 | 5,2)	(14,9 | 2,4)	(9,13,2,4)
(13,5,7 | 3)	(9,13,5 | 2)	(13,5,7,2)
(14 | 9,2,4)	(9 | 13,5,2)	(14,13,5,2)
(13,5 | 7, 3)	(9,13 | 5, 2)	(13,5,5,2)

---

Таблица 7: Коэффициенты выживаемости потомков (fitness)

Хромосома-потомок	Коэффициент приспособленности
(13,28,15,3)	|126-30|=96
(9,13,2,4)	|57-30|=27
(13,5,7,2)	|52-30|=22
(14,13,5,2)	|63-30|=33
(13,5,5,2)	|46-30|=16

Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.
Продолжая таким образом, одна хромосома в конце концов достигнет коэффициента выживаемости 0, то есть станет решением.

ПРИМЕНЕНИЕ ГА

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


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

---

Poly Bot (PARK, USA), Polypod (Stanford University, USA), MTRAN (AIST, Japan) и др., неоднократно демонстрировалась возможность изменения кинематической структуры за счет автоматической перестыковки ее фрагментов.


PolyBot (PARK, Xerox, USA)


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


Формирование программы управления мехатронно-модульного робота в конфигурации шагающего устройства предполагает необходимость построения целесообразной последовательности циклических изменений состояния конечностей, обеспечивающей тот или иной вид походки. При этом изменение состояния конечностей соответствует выполнению элементарных движений из следующего набора:
• поднять конечность;
• опустить конечность;
• повернуть конечность вперед (+15°);
• повернуть конечность в нейтральное положение (0°);
• повернуть конечность назад (—15°).
Будем считать, что реализация оговоренных движений определяется радом допущений:
• прямоугольная система координат робота связана с его узловым модулем;
• точки крепления конечностей к узловому модулю совпадают с осями системы координат робота;
• движение каждой конечности в вертикальной, плоскости осуществляется поворотами шарниров первого и второго модулей (в порядке следования от узлового)
• движение каждой конечности в горизонтальной плоскости осуществляется поворотом шарнира, первого модуля (по отношению к узловому)


• Структура хромосомы, отвечающей этим требованиям, разбивается на несколько фрагментов, каждый из которых будет кодировать один такт алгоритма управления, задающий изменение состояний конечностей робота. Для кодирования могут использоваться три бита, первый из которых устанавливает движение конечности в вертикальной плоскости, а второй и третий — в горизонтальной плоскости

№ бита	Значе­ние	Элементарное движение
1	0 1	Опустить конечность Поднять конечность
2, 3	00 01 10 11	Повернуть конечность в нейтральное положение Повернуть конечность вперед Повернуть конечность назад Оставить конечность в текущем положении

---

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


Следовательно, исходя из предположения, что движение робота при моделировании начинается в точке с нулевыми координатами, функция оценки полезности хромосом может быть записана в следующем виде:


f = x2+y2


где х, у — координаты положения робота после отработки одного цикла синтезированного алгоритма управления движением.


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


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


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

---

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


В ходе выполнения экспериментальных исследований селекция синтезируемых хромосом осуществлялась по методу элитного отбора. Для эмуляции движений робота, отвечающих кодам полученных хромосом, использовался специализированный комплекс программно- инструментальных средств моделирования виртуальной реальности ODE (Open Dynamic Engine). При этом продолжительность "жизни" каждой особи ограничивалась 40 тактами, где под тактом понимается период выполнения команд одной подхромосомы.
Для полноты исследований был проведен сравнительный анализ программ управления роботом, одна из которых была синтезирована высококвалифицированным экспертом, а остальные формировались в автоматическом режиме с помощью генетического алгоритма. Составленная экспертом программа на алгоритмическом уровне рассмотрения представляла собой последовательность элементарных движений конечностей, регулярное повторение которой должно обеспечивать реализацию соответствующей походки робота.


Анализ экспериментальных данных показывает, что в смысле полезности полученных хромосом автоматически формируемые с помощью генетического алгоритма решения в ряде отдельных случаев оказываются намного более эффективными, чем синтезируемые экспертом. При этом следует отметить, что если поиск приемлемых решений по формированию программ управления походкой шагающего робота в автоматическом режиме по времени занимает от
10 до 30 минут, то для эксперта решение аналогичной задачи требует от 1,5 до 3
суток.
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ГА
К настоящему времени созданы многочисленные пакеты программного обеспечения по ГА. Одним из таких приложений является программный комплекс GeneHunter, разработанный российской компанией "НейроПроект", и программный пакет Auto2Fit от CPC-X Software. К пакетам, получившим широкое применение относятся Genesis, Evolution Machine, Genitor, Neuro-Genetic Optimizer, MATLAB Genetic Algorithm Toolbox и др.


АППАРАТНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Идея применения генетических алгоритмов в системах автоматизированного проектирования активно развивается наряду с другими направлениями. Впервые эта идея была предложена С. Луисом [Louis et al., 1991] и Д. Раулинсом [Rawlins

---