Пример 4.29

Этот пример демонстрирует применение генетического алго­ритма для сортировки списка имен в алфавитном порядке.

Для упрощения будем рассматривать очень короткий список из семи имен, начинающихся буквами J, М, В, R, S, H, F. Таким образом, наилучшее решение ищется в пространстве решений, состоящем из 7! = 5040 возможных перестановок семи элементов. Наилучшее ре­шение очевидно - это В, F, H, J, M, R, S. На этом простейшем приме­ре познакомимся с тем, как генетический алгоритм решает задачи

Родитель 1: [3 5 126 2 4]

локус: 1 23 456 7

Родктель2:[ 345 17621 локус- 1 23 45 6 7

Потомок ^-> [3514726]

локус 12 3 4 5 6 7

Родитель 1 [abcdefgh]

локус:

Родитель2: [gcfaebdh]

локус: 1<2>&4®67®

[abcdefgh] Потомок1

:: 12 3 4 5678

[gbfacedh] Потомок^ локус: 12 3 4 5 6 7 8

Рис. 4.112. Упорядоченное скрещивание (order crossover).

Глава 4. Генетические алгоритмы

4.11. Приложения эволюционных алгоритмов

этого типа. Припишем каждому имени, включенному в исходный (не­сортированный) список, порядковый номер так, как это сделано в пер­вом столбце на рис. 4.113.

Допустимое решение, представленное на рисунке - это В, F, R, Н, J, M, S. Приведенным первым буквам имен предшествуют соответ­ствующие им порядковые номера из первого столбца. Последова­тельность этих номеров (на рисунке они вписаны в клетки) идентифи­цирует данное решение. На рис. 4.114 таким же образом представле­но наилучшее решение, определяемое последовательностью 3, 7, 6, 1,2,4,5

Рассматриваемая задача имеет семь переменных (параметров задачи). Обозначим их Р_ь Р₂,..., Р₇. Каждая из этих переменных мо­жет принимать целые значения от 1 до 7. На рис. 4.113 показана од­на из особей популяции, для которой значения конкретных перемен­ных (параметров задачи) равны 3, 7, 4,6, 1, 2, 5, а наилучшее реше­ние на рис. 4.114 характеризуется значениями этих переменных 3, 7, 6,1,2, 4, 5. Приведенные последовательности чисел рассматривают­ся как аллели хромосом, представляющих соответствующие особи. Для каждой особи, входящей в популяцию, при выполнении генетиче­ского алгоритма рассчитывается значение функции приспособленно­сти и на этой основе выбираются наилучшие и наихудшие особи.

Прежде чем определить функцию приспособленности для рас­
сматриваемой задачи, введем ряд обозначений. Пусть п(Р,) соответ­
ствует имени, определенному порядковым номером Р,-, i = 1,2,..., 7,
и пусть п(Р/) < n(Pj) означает, что имя с порядковым номером Р,-долж­
но предшествовать имени с порядковым номером Pj, т.е. они упорядо­
чиваются по алфавиту. Пусть G обозначает последовательность, со­
ставленную из элементов д_кт, /с = 2 7, т = 1,.... /с-1, где

[ 1, еслил(Р,)<л(Р_т), [ 0 в противном случае

Очевидно, что если последовательность G состоит из одних ну­лей, то последовательность имен будет корректной. Поэтому наилуч­шая особь должна характеризоваться последовательностью G, все элементы которой равны нулю. Следовательно, функцию приспособ­ленности можно определить как сумму элементов последовательнос­ти G, и нас, конечно, будет интересовать минимизация этой функции (которая может принимать целые значения в интервале от 0 до 21). Заметим, что если бы элемент д^т принимал нулевое значение при п(Рк) < п(Рт) и значение 1 в противном случае, то следовало бы мак­симизировать количество единиц в последовательности G. Теперь пе­рейдем к интерпретации функции приспособленности из примера 4.4.

Задача, сформулированная в примере 4.29, решается с помо­щью программы Evolver, размерность популяции принята равной 10, показатель скрещивания равен 0,5, показатель мутации равен 0. При t = 10, что соответствует первой популяции классического генетичес­кого алгоритма, получена популяция, представленная на рис. 4.115.

Первый столбец определяет последовательность хромосом в популяции (от «наихудшей» к «наилучшей»). Во втором приведены значения функции принадлежности каждой хромосомы. В третьем столбце записаны сами хромосомы, состоящие из семи генов. Каж­дая из этих хромосом представляет собой перестановку натуральных чисел от 1 до 7. Первое значение функции приспособленности, очер­ченное прямоугольником и равное 15, относится к хромосоме, исклю­ченной из предыдущей популяции. Вместо нее вводится хромосома [3514726], полученная в результате скрещивания хромосом [3 5 1 7 6 2 4] и [3 4 5 1 7 2 6], присутствующих на рис. 4.115. Последняя хро­мосома, имеющая функцию приспособленности, равную пяти, после 10 «тактов» является «наилучшей на данный момент». При продол­жении выполнения алгоритма можно получить наилучшую хромосому [3 7 6 1 2 4 5] с функцией приспособленности, равной 0. Эта опти­мальная хромосома представлена на рис. 4.114. Заметим, что в рас-

Исходный (к

№ Имена

Исходный список Наилучшее

(несортированный) решение

№ Имена

= 0.g4)	= 0
= 0	= o.Bs4=o
=°,g63	= 0. 8«= 0. g«
= 0, g,,	= 0, g,4=0, g,,

ae функции приспособлгнности -З

G = [ООООООООООООООООООООО] Значение функции приспособленности = 0

Рис. 4.113. Одно из допустимых решений задачи из примера 4.29.

Рис. 4.114. Наилучшее решение задачи из примера 4.29.

Глава 4. Генетические алгоритмы

4.12. Эволюционные алгоритмы в нейронных о

Рис. 4.115. Популяция особей в генетическом алгоритме программы Evolver для задачи из примера 4.29.

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

Пример 4.29 легко обобщить на любые перечни имен или на­званий, подлежащих сортировке в алфавитном порядке (либо в соот­ветствии с другим ключей). Задачи такого типа можно решать с помо­щью эволюционного алгоритма программы Evolver. Зга программа также позволяет решить известную из литературы задачу о коммиво­яжере [33], имеющую гораздо более сложную структуру, чем рассмо­тренная задача из примера 4.29.

4.12. Эволюционные алгоритмы в нейронных сетях

Объединение генетических алгоритмов и нейронных сетей из­вестно в литературе под аббревиатурой COGANN {Combinations of Genetic Algorithms and Neural Networks). Это объединение может быть вспомогательным (supportive) либо равноправным [collaborative) [39]. Вспомогательное объединение двух методов означает, что они при­меняются последовательно один за другим, причем один из них слу­жит для подготовки данных, используемых при реализации второго метода. При равноправном объединении оба метода применяются одновременно. Классификация этих типов объединений генетических алгоритмов и нейронных сетей представлена в табл. 4.6.

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

Таблица 4.6. Объединение генетических алгоритмов и нейронных сетей

Вид объеди-	Характеристика объединения	Примеры использования	Литера­тура
	Генетические алгоритмы и нейронные сети независимо применяются для решения одной и той же задачи	Однонаправленные нейронные сети, сети Кохоненас самоорганизацией и генетические алгоритмы в задачах классификации	(40,46]
Вспомо-гатель-ное	Нейронные сета для обеспечения алгоритмов	Формирование исходной популяции для генетического алгоритма	I26,27]
Генетические алгоритмы для обеспечения нейронных сетей	Анализ нейронных сетей	[5,10. 11.42]
Подбор параметров либо преобразование пространства параметров	[17.22, 24]
Подбор параметров либо правила обучения (эволюция правил обучения)	[3.6, 20.38]
Равно­правное	Генетические алго­ритмы для обучения нейронных сете"*	Эволюционное обучение сети (эволюции весов связей)	[2. 35. 44]
Генетические алго­ритмы для выбора топологии нейрон-	Эволюционный подбор топологии сети (эволюция сетевой архитектуры)	[17.20, 45]
Системы, объединяющие адаптивные стратегии генети­ческих алгоритмов и нейронных сетей	Нейронные сети для решения оптимизационных задач с применением генетического алгоритма для подбора весов сети	П1
Реализация генетического алгоритма с помощью нейронной сети	116]
Применение нейронной сети для реализации оператора скрещивания в генетическом алгоритме	[41]

Глава 4 Генетические алгоритмы

4.12. Эволюционные алгоритмы в нейронных сетях

Необходимо отметить, что в соответствии с замечаниями, при­веденными в разд. 4.10, термин «генетические алгоритмы» применя­ется здесь в более широком смысле, чем классический генетический алгоритм

4.12.1. Независимое применение генетических алгоритмов
и нейронных сетей

Генетические алгоритмы и нейронные сети могут незави­симо применяться для решения одной и той же задачи. Этот подход иллюстрируется на рис. 4.116.

Например, описаны независимые применения нейронных се­тей, генетических алгоритмов и алгоритма KNN «ближайший сосед» (К - means nearest neighbour) для решения задач классификации. В работе [40] проведено сравнение трехслойной однонаправленной нейронной сети с обучением по методу обратного распространения ошибки (обучение с учителем), сети Кохонена с самоорганизацией (обучение без учителя), системы классификации, основанной на гене­тическом алгоритме, а также алгоритма KNN «ближайший сосед». Ав­торы работы [39] считают независимое применение этих методов для решения задачи автоматической классификации результатов ЭМГ (электромиография - регистрация электрической активности мышц) вспомогательным объединением.

Известны и другие работы, в которых сравниваются возможно­сти применения различных методов (в частности, генетических алго­ритмов и нейронных сетей) для решения одних и тех же задач [46]. Примером задачи, которую можно решить с помощью как нейронной сети, так и генетического алгоритма, может служить задача о комми­вояжере [28, 33. 36].

Дата добавления: 2015-06-04