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]. Определенная таким образом мутация заключается в случайном выборе двух позиций в хромосоме и обмене значений генов на этих позициях. Например, после мутации хромосомы Этот способ мутации отличается тем, что в результате ее выполнения формируется новая хромосома с измененной последовательностью генов. Такая мутация применяется для поиска наилучшей перестановки параметров задачи. Пример 4.29 Этот пример демонстрирует применение генетического алгоритма для сортировки списка имен в алфавитном порядке. Для упрощения будем рассматривать очень короткий список из семи имен, начинающихся буквами J, М, В, R, S, Н, F. Таким образом, наилучшее решение ищется в пространстве решений, состоящем из Рис. 4.113. Одно из допустимых решений задачи из примера 4.29. Допустимое решение, представленное на рисунке - это В, F, R, H, J, М, S. Приведенным первым буквам имен предшествуют соответствующие им порядковые номера из первого столбца. Последовательность этих номеров (на рисунке они вписаны в клетки) идентифицирует данное решение. На рис. 4.114 таким же образом представлено наилучшее решение, определяемое последовательностью 3, 7, 6, 1, 2, 4, 5. Рис. 4.114. Наилучшее решение задачи из примера 4.29. Рассматриваемая задача имеет семь переменных (параметров задачи). Обозначим их Прежде чем определить функцию приспособленности для рассматриваемой задачи, введем ряд обозначений. Пусть
Очевидно, что если последовательность Задача, сформулированная в примере 4.29, решается с помощью программы Evolver, размерность популяции принята равной 10, показатель скрещивания равен 0,5, показатель мутации равен 0. При Рис. 4.115. Популяция особей в генетическом алгоритме программы Evolver для задачи из примера 4.29. Первый столбец определяет последовательность хромосом в популяции (от «наихудшей» к «наилучшей»). Во втором приведены значения функции принадлежности каждой хромосомы. В третьем столбце записаны сами хромосомы, состоящие из семи генов. Каждая из этих хромосом представляет собой перестановку натуральных чисел от 1 до 7. Первое значение функции приспособленности, очерченное прямоугольником и равное 15, относится к хромосоме, исключенной из предыдущей популяции. Вместо нее вводится хромосома Пример 4.29 легко обобщить на любые перечни имен или названий, подлежащих сортировке в алфавитном порядке (либо в соответствии с другим ключом). Задачи такого типа можно решать с помощью эволюционного алгоритма программы Evolver. Эта программа также позволяет решить известную из литературы задачу о коммивояжере [33], имеющую гораздо более сложную структуру, чем рассмотренная задача из примера 4.29.
|