4.11.2. Решение комбинаторных задач с помощью программы Evolver

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

Скрещивание разбивается на следующие шаги:

1) случайным образом выбираются позиции у первого родителя; их количество зависит от показателя скрещивания;

2) находятся позиции с такими же значениями генов (аллелями) у второго родителя;

3) значения оставшихся позиций первого родителя копируются на оставшиеся позиции второго родителя в последовательности, в которой они записаны у первого родителя.

Описанный способ скрещивания иллюстрируется на рис. 4.111.

Рис. 4.111. Скрещивание с сохранением порядка в генетическом алгоритме программы Evolver.

На этом рисунке показаны две хромосомы родителей, состоящие из семи генов со значениями из интервала целых чисел от 1 до 7. Каждый ген в хромосоме характеризуется уникальным значением. Каждая хромосома представляет собой перестановку натуральных чисел от 1 до 7. Под каждым геном указан номер его позиции (locus). Допустим, что показатель скрещивания равен 0,5, и у первого родителя случайным образом выбраны позиции 1, 4, 5, 6, на которых находятся значения 3, 7, 6, 2 соответственно. У второго родителя эти значения находятся на позициях 1, 5, 6, 7. В результате копирования значений оставшихся позиций первого родителя (т.е. чисел 5, 1, 4 с позиций 2, 3, 7 соответственно) на оставшиеся позиции второго родителя (т.е. на позиции 2, 3, 4) в последовательности, в которой они записаны у первого родителя, образуется потомок со значениями генов 3, 5, 1, 4, 7, 2, 6.

Представленный метод скрещивания применяется в программе Evolver для решения задач, которые сводятся к поиску хромосом с наилучшим упорядочением генов. Описываемый способ подобен упорядоченному скрещиванию (order crossover) [9], показанному на рис. 4.112.

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

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

Мутация. Оператор мутации реализует так называемую мутацию, основанную на упорядочении (order-based mutation) [9]. Определенная таким образом мутация заключается в случайном выборе двух позиций в хромосоме и обмене значений генов на этих позициях. Например, после мутации хромосомы  на выбранных позициях 2 и 5 будет получена хромосома . Количество обменов возрастает или снижается пропорционально увеличению или уменьшению показателя мутации.

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

Пример 4.29

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

Для упрощения будем рассматривать очень короткий список из семи имен, начинающихся буквами J, М, В, R, S, Н, F. Таким образом, наилучшее решение ищется в пространстве решений, состоящем из  возможных перестановок семи элементов. Наилучшее решение очевидно - это В, F, Н, J, М, R, S. На этом простейшем примере познакомимся с тем, как генетический алгоритм решает задачи этого типа. Припишем каждому имени, включенному в исходный (несортированный) список, порядковый номер так, как это сделано в первом столбце на рис. 4.113.

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

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

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

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

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

.

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

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

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

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

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