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

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

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

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

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

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

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

На этом рисунке показаны две хромосомы родителей, состоя­щие из семи генов со значениями из интервала целых чисел от 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 соответственно) на оставшиеся позиции второго родителя

4.11. Приложения эволющ

(т.е. на позиции 2, 3, 4) в последовательности, в которой они записа­ны у первого родителя, образуется потомок со значениями генов 3, 5 1,4,7,2,6.

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

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

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

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

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