Пример 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. Заметим, что в рас-

Исходный (к

№ Имена

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

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

№ Имена

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. Объединение генетических алгоритмов и нейронных сетей