ГА для задач комбинаторной оптимизации

1 ГА ДЛЯ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ Задачи комбинаторной (дискретной) оптимизации сильно отличаются от задач непрерывной оптимизации, которые рассматривали до сих пор. В численной («непрерывной») оптимизации большое значение имеет выбор направления поиска решения в пространстве решений. Например, градиентные и близкие методы , в значительной мере используют эту информацию. При этом неявно используется «близость» решений в пространстве поиска. В комбинаторной оптимизации близость решений сильно зависит от кодирования решений и направления поиска фактически нет. Это сильно осложняет решений таких задач. 2 Задачи комбинаторной оптимизации могут иметь различную сложность. Это показано на следующем рисунке. Отношения между P,NP, NP –полными и NP- трудными задачами. 3 При решении задач комбинаторной оптимизации используются, в основном, : 1) Точные методы. 2) Эвристические алгоритмы. 3) Эволюционные методы. Соотношение между ними по качеству получаемых решений и их сложности построения представлено на следующих рисунках. Качество решений 4 Сложность алгоритмов решения. 5 Задача о покрытии Есть множество элементов S и множество подмножеств Fi , состоящих из элементов S . Необходимо найти минимальное число подмножеств из F таких, чтобы объединение этих подмножеств содержало все элементы множества S . Задача имеет простую экономическую интерпретацию: пусть, например, имеется некоторое количество клиентов и для их обслуживания необходимо выбрать некоторое количество сервисных центров. Очевидно, здесь решение можно также представить двоичным вектором X= (x1,…, xn), где: xi=1 , подмножество F i  входит в покрытие; xi=0, если F i  не входит в покрытие; При этом:  X i Fi  S  X i  min Поскольку решение задачи, как было показано выше, представляется двоичным вектором, то при его поиске можно использовать простой ГА со стандартными операторами кроссинговера и мутации. 6 Задача об укладке рюкзака Эта задача имеет следующую неформальную простую постановку. Имеется рюкзак объемом C и n различных предметов. Каждый предмет i имеет известный объем Wi и стоимость Pi ( i  1 n ). В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем С – емкость рюкзака. Форма предметов здесь не учитывается . Пример Постановка задачи: необходимо найти вариант укладки рюкзака, который дает максимум стоимости уложенных предметов при заданном ограничении на объем (рюкзака), т.е. 7 Т.е. для данного множества весов Wi , стоимостей Pi и объема W надо найти двоичный вектор X= (x1,…, xn), где xi=1 , если предмет укладывается в рюкзак;xi=0, если предмет не укладывается; n при этом должно выполняться: V   Wi  W , и i 1 Px i i  max . Рассмотрим различные варианты кодирования потенциальных решений для этой задачи на следующем примере. «Естественным» является эвристический («жадный») подход, при котором в первую очередь предметы с большей стоимостью и меньшим весом. Поэтому можно вычислить отношения pi /wi для всех предметов , упорядочить (ранжировать) предметы в порядке убывания и производить укладку в соответствии с этим порядком с проверкой ограничения (по весу или объему). 8 То есть первым укладываем предмет с наибольшим значением pi /wi , затем следующий по порядку предмет и т.д. При этом необходимо на каждом шаге проверять ограничение по весу(объему). Для нашего примера решением в соответствии с этим алгоритмом является укладка {1,2,7}, при этом стоимость предметов P= 6+5+7=18 и вес W=2+3+4=9. Рассмотрим несколько методов кодирования потенциальных решений для этой задачи. 1. Двоичный код Здесь каждому i-му предмету соответствует булева переменная xi и 1 разряд двоичного кода. При этом (как указано выше) значение xi=1 , если предмет укладывается в рюкзак;xi=0, если предмет не укладывается. Например, двоичный код представляет решение, где укладываются предметы 2, 4,6. Заметим, что такое кодирование может давать неправильные решения (с превышением веса(объема)). 9 В качестве фитнесс-функции в простейшем случае можно взять P X   n x P , i 1 i i но в этом случае, как указано выше, есть проблемы с неправильными решениями. Дело осложняется тем, что хорошие решения, естественно, лежат близко границе допустимых решений. Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы : 1) введение в фитнесс-функцию дополнительного штрафа; 2) использование алгоритмов “восстановления” некорректных решений. 1) В первом случае в фитнесс-функцию вводится дополнительная штрафная функция, которая для неправильных решений дает большие отрицательные значения ЦФ. При этом задача с ограничениями трансформируется в задачу без ограничений путем назначения штрафа для некорректных решений. Фитнесс-функция для каждой особи может быть определена следующим образом n f ( X )   xi  Pi  Pen ( X ) i 1 . 10 Разработано множество методов назначения штрафных значений, например: a) n Pen ( X )  log 2 (1    ( xi  Wi  W )), i 1 б) n Pen ( X )    ( xi  Wi  W ), i 1 в) n Pen( X )  (   ( xi Wi  C )) 2 . i 1 Здесь для всех трех случаев   max{Pi / wi } . 1i  n Кроме этого, иногда выполняют масштабирование согласно формуле , и применяется следующий вид штрафной функции: Графическая интерпретация этой функции представлена на следующем рис. , 11 Фитнесс-функцию в этом случае можно определить так 2) Второй подход к решению задач с ограничениями основан на специальных алгоритмах “восстановления” некорректных решений. Рассмотрим на следующем примере с W=90 и n=7, параметры предметов которого представлены в следующей табл. . 12 В этом случае решение , очевидно, является неправильным (недопустимым), поскольку сумма весов w2 + w4 + w6 =50+10+40=100 > 90=W. В соответствии с табл.можно удалить предмет 6 с минимальным отношением pi /wi и это делает решение допустимым. Следует отметить, что многие алгоритмы восстановления требуют значительных вычислительных ресурсов, и полученные решения иногда требуют адаптации к конкретным практическим приложениям. В этом случае в качестве фитнесс-функции используется n f ( X ' )   xi ' Pi , где вектор X  – i 1 восстановленная версия исходного вектора X. Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. 13 В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления. Восстановление(X) { переполнение_рюкзака=false; X’=X; n if ( f ( X ' )   xi 'Wi  C ) i 1 then переполнение_рюкзака=true; while(переполнение_рюкзака) { i=выбор предмета из рюкзака; // удаление выбранного предмета из рюкзака; x' i  0 ; n if ( f ( X ' )   x'i Wi  C ) i 1 then переполнение_рюкзака=false; } } 14 При этом используются два основных способа выбора объекта: а) случайный выбор объекта из рюкзака; б) “жадное восстановление”, при котором вначале все предметы сортируются в порядке убывания их стоимости Pi и на каждом шаге для удаления выбирается предмет минимальной стоимости (из имеющихся в рюкзаке). 3) Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения. 2. Кодирование переменной длины В этом случае длина хромосомы может изменяться в процессе искусственной эволюции. Здесь положение (локус) гена значения не имеет, а значение гена (аллель) определяет порядок предмета. Например, (1,6,5) означает укладку в рюкзак предметов 1, 6 и 5. Код переменной длины предусматривает специальные методы сохранения допустимости решений. При инициализации популяции можно случайно генерировать n случайных перестановок (номеров предметов). 15 Далее в порядке, определяемом, данной перестановкой мы проверяем каждый предмет на его укладку в рюкзак. Если укладка предмета не вызывает переполнения рюкзака, то рассматриваемы предмет укладывается в рюкзак. В противном случае данный предмет не укладывается и мы переходим к следующему предмету по порядку (в текущей перестановке). В этом случае одна случайная перестановка может породить 1 допустимое решение. Эта процедура повторяется для каждой перестановки. При выполнении кроссинговера необходимо поддерживать правильность (допустимость) решения. Т.е. 2 допустимые родительские особи должны давать допустимые особи -потомки. Рассмотрим эту проблему на последнем примере рюкзака с n=7 и W=90 , представленном табл. Кроссинговер выполняется следующим образом. 1. Выбрать случайную точку в 1-м родителе. 2. Выбрать случайный фрагмент во втором родителе. 3. Вставить выбранный фрагмент второго родителя в выбранную позицию первого родителя, удалить повторяющиеся предметы. При этом возможно построение недопустимых решений. 16 4. Для недопустимых решений выполнить процедуру восстановления на основе ранжирования предметов по отношениям pi /wi . Следующий рис. иллюстрирует выполнение для указанного примера. Здесь после выполнения 3-го шага получено недопустимое решение (2,5,7,6). Согласно порядку предметов по отношению pi /wi представленной таблицы мы пытаемся Сначала удалить предмет 5. Но этого недостаточно – получаемое решение (2,7,6) остается недопустимым. Поэтому мы пытаемся удалить следующий по порядку предмет (из начальной конфигурации) и получаем допустимое решение (2,5,7). 17 Оператор мутации выполняется проще – можно удалить случайно выбранный предмет и на его место вставить случайно выбранный из оставшихся. Затем, в случае недопустимости построенного решения, выполнить шаг 4 предыдущего алгоритма. 3.Перестановочное кодирование Любая перестановка n чисел может быть интерпретирована как последовательность укладываемых предметов. Слегка модифицируем последний пример: заменим на W=100 при сохранении n=7. Для особи (1,6,4,7,3,2,5) декодирование можно выполнить следующим образом. Мы укладываем в рюкзак первый предмет из этой перестановки –предмет 1. Далее укладываем второй предмет – предмет 6 и это не вызывает переполнения поскольку 40+40=80<100=W. Затем аналогично поступаем с предметом 4, который также не вызывает переполнения 40+40+10=90<100=W. Но при попытке уложить следующий согласно данной перестановке предмет 7 имеет место переполнение - 40+40+10+30=120>100=W. Поэтому предмет 7 не укладывается. Аналогично мы вынуждены пропустить предметы 3 и 2, поскольку они также вызывают переполнение. Наконец, последний предмет 5 не вызывает переполнения - 40+40+10+10=10=100=W В результате декодирования перестановки (1,6,4,7,3,2,5) получаем особь – решение задачи (1,6,4,5). 18 Таким способ любая перестановка декодируется в допустимое решение. Заметим, что обычный кроссинговер и мутация могут нарушить допустимость решения. Данный метод декодирования порождает отображение много-к-одному. Например, перестановки (1,6,4,7,3,2,5), (1,4,6,7,3,2,5), (6,4,1,7,3,2,5), …,(6,4,1,7,3,5,2) при декодировании порождают одно и тоже решение –(1,6,4,5). Это снижает эффективность кодирования за счет повышения размерности пространства поиска. Так для n предметов при двоичном кодировании пространство поиска содержит 2n вариантов решений. Для перестановочного кода пространство решений –n!, которое с ростом n растет гораздо быстрее, что показывает следующая табл. Таким образом сохранение допустимости решений достигается в этом случае ценой расширения пространства поиска (и снижения эффективности). 19 ЗАДАЧА КОММИВОЯЖЕРА Напомним неформальную постановку этой классической задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в некотором порядке все города и вернуться в исходный город. Расстояния между городами известны. Например. Рис. 1. Задача коммивояжера В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? 20 В формальной постановке задачи коммивояжера (ЗК): имеется полный взвешенный ориентированный граф без петель G с множеством вершин N={1,2,…,n}; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл с минимальной стоимостью. Исходная информация по ЗК представляется в виде n  n матрицы S  {sij } - вес дуги (i,j) графа G, i  1, n , j  1, n , i  j ; все элементы главной диагонали нулевые sii  0 (но в некоторых постановках полагаются sii   ). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные; повторяющийся в начале и в конце номер города j1, показывает, что перестановка циклическая. Пространством поиска решений этой задачи является множество перестановок n городов. Очевидно, размерность пространства поиска для несимметричной задачи равна (n-1)!. Таким образом, число возможных решений даже при умеренных значениях n огромно, например, при n=50 имеем 49!=6.1∙1062 . 21 Обозначим D(i,j) через расстояние между городами i и j. Мы будем, в основном, рассматривать симметричную ЗК, когда D(i,j)= D(j,i) для любой пары городов. Заметим, что туры могут быть правильными и неправильными. В правильном туре коммивояжер посещает все города по одному разу. В неправильном (некорректном) тур может быть неполным (некоторые города остаются не посещенными )или может посещать дважды. Туры могут быть открытыми и замкнутыми. Например, правильный открытый тур для 4 городов: , Правильный замкнутый тур При решении ЗК обычно минимизируется длина тура Хотя, в общем случае возможна минимизация стоимости , в том числе при несиммектричной матрице D. Эту задачу можно рассматривать как задачу разбиения (группировки) ребер на два класса -1) ребра, входящие в тур; 2) ребра, не входящие в тур. Известно, что эта задача является NP – полной, т.е. переборной. 22 ЭВРИСТИЧЕСКИЕ МЕТОДЫ И ИНИЦИАЛИЗАЦИЯ ПОПУЛЯЦИИ ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРА Рассмотрим наиболее популярные жадные эвристические алгоритмы решения задачи коммивояжера. Они представляют интерес сами по себе и еще больше для генерации начальной популяции ГА при решении ЗК, поскольку чисто случайная инициализация здесь не эффективна. 1. Метод ближайшего соседа Это самый простой и интуитивно понятный алгоритм решения ЗК. 1. Стартовать из любого города и взять его в качестве текущего города. 2. Выбрать ближайший к текущему еще не посещенный город, перейти в него сделать его текущим. 3. Повторять шаги 1,2 до тех пор, пока не будут посещены все города. Например, для ЗК, представленного рис.1 применение этого алгоритма со стартом в первом городе дает следующий результат, показанный на рис.2. Здесь расстояния между городами оценивались графически на указанном рисунке. 23 Рис.2 Результат решения ЗК методом ближайшего соседа Рассмотрим более детальный пример ЗК, представленный следующей матрицей расстояний между городами. Рис.3. Матрица расстояний ЗК Если мы стартуем из первого города, алгоритм дает тур с длиной 25. Если мы начнем из второго города, то алгоритм даст тур , с длиной 19. Заметим, что для симметричная матрица расстояний задается n(n-1)/2 элементами (над диагональю). 24 Если мы хотим выполнить «интеллектуальную» инициализацию популяции, то мы можем использовать этот алгоритм для генерации одной или нескольких особей начальной популяции. Но нет смысла генерировать дубликаты (одинаковые особи) в популяциии. Поэтому можно внести в этот процесс элементы случайности. Например, можно выбирать следующий город s(i+1) на каждой итерации с вероятностью обратно ппропорцианольной расстоянию от текущего города s(i). Данный метод основан на классическом жадном алгоритме и поэтому нетрудно привести контрпример, где он работает плохо. Следующий рис. 4 показывает это для 5 городов. Рис.4. Контрпример методу ближайшего соседа В зависимости от начального города мы можем получить либо: плохое решение (слева) со стартом в городе 1; хорошее решение (справа) со стартом в городе3. 25 2. Метод кратчайшей дуги В этом случае мы предварительно ранжируем по длине все n(n-1)/2 дуг согласно заданной матрице расстояний D в ЗК. Определим Lk дугу номер к в этом упорядоченном множестве {Lk}, которые ранжированы по возрастанию длины дуг. Тогда алгоритм можно сформулировать следующим образом. 1. Определить T как множество ребер строящегося тура. Инициалировать Т= 2. Найти кратчайшую дугу dij в {Lk}, которая удовлетворяет следующим условиям: 1) ее нет в туре Т; 2) при внедрении ее в тур она не дает замкнутый неполный тур (с числом городов меньше n): 3) в туре Т города i и j в случае внедрения этой дуги связаны не более чем с2-мя ребрами. 3. 3.Если Т содержит n городов, то конец –тур построен. Иначе переход на шаг 2. В отличие от предыдущего, данный метод является детерминированным и генерирует один тур, который можно (и нужно) включить в начальную популяцию. Исключением является случай, когда на текущей итерации есть 2 (или более) дуги с одинаковой длиной – в этом случае дуга выбирается случайно из множества претендентов. 26 Рассмотрим метод на примере ЗК с матрицей расстояний рис.3. 1. Кратчайшая дуга - d13, которую включаем в тур Т. 2. Следующими кратчайшими являются дуги d12 и d15 - случайно выбираем d15 и включаем ее в тур. 3. Далее кратчайшей является дуга d12, но город 1 уже имеет 2ребра в туре Т. Поэтому мы выбираем следующую дугу d34 и включаем ее в тур. 4. Следующей дугой является d23, но город 3 уже имеет 2 ребра в туре. Аналогично отвергаем дугу d35. Далее находим дугу d24 и включаем ее в тур. 5. Остается единственная дуга, которая удовлетворяет необходимым условиям – d25, которую мы и включаем в тур. Таким образом, мы построили замкнутый тур Если мы хотим получить открытый (незамкнутый) тур, мы должны оставиться после получения (n-1) дуг в туре. Например, так можно построить тур 27 3.Инициализация на основе внедрения Здесь процесс начинается с некоторого подтура и последующего его расширения по одному городу так, что внедрение города дает минимальное увеличение длины тура. В качестве начального тура может выступать и одна самая короткая дуга. В этом случае имеем алгоритм ближайшего внедрения. 1. Определить Т как множество вершин тура. Инициализировать Т кратчайшей дугой матрицы D. То есть среди оставшихся вне тура городов выбираем один, 2. ближайший к туру. 3. Выбираем дугу D(k,j) из тура Т так, чтобы разность между длинами подтуров и была минимальной. 4. Удалить из тура дугу D(k,j) и добавить в него D(k,c) и D(c,j). 5. Если Т содержит (n-1) дуг, то конец, иначе переход на шаг 2. Если мы хотим получить замкнутый тур, то добавляем еще 1 дугу. Можно модифицировать алгоритм путем изменения инициализации на шаге 1 , например, выпуклой оболочки городов или случайной инициализации. Это позволяет генерировать более одной особи начальной популяции. Рассмотрим метод на том же примере рис.3. 1. Кратчайшая дуга -(1,3), которую включаем в тур Т. 28 2. Пока в туре нет городов 2,4,5. Среди них мы должны выбрать ближайший к текущему туру Т(городам 1 или 3) - 2 или 5. Случайным образом выбираем 5 и включаем его в тур Т. Затем удаляем дугу (1,3) и включаем в тур дуги (1,5) и (5,3). 3. Вне тура города 2,4. Среди них один (город 2) ближе к туру(то есть ближе к годам 1, 3 или 5) . Это порождает 2 варианта. а) Можно удалить дугу (1,5) из тура Т и заменить ее дугами (1,2) и (2,5). Это ведет к увеличению длины подтура от 3 единиц (длина дуги (1,5)) до 14 единиц (сумма дуг (1,2) и (2,5)). Это увеличивает длину на 11 единиц. б) Можно удалить дугу (5,3) из Т и заменить ее дугами (5,2) и (2,3). Это ведет к увеличению длины подтура с 6 единиц (дуга(5,3)) до 16 единиц (сумма дуг (5,2) и (2,3)). Это дает увеличение на 10 единиц. Выбираеи вариант б) с меньшим увеличенем длины. Тогда тур Т включает дуги (1,5), (5,2) и (2,3). 4. Остается единственный город вне Т -4 и мы должны добавить ребро с этим городом. Имеем 3 варианта: а) можно удалить дугу (1,5) и заменить ее (1,4) и (4,5). Это дает увеличение 16 единиц. б) можно удалить (5,2) и заменить ее дугами (5,4) и (4,2). Это дает увеличение 7 единиц. 29 в) можно удалить дугу (2,3) и заменить ее (2,4) и (4,3), что дает увеличение 7 единиц. Можно выбрать минимальные варианты б) или с). Для определенности возьмем с) (случайно). В результате получаем открытый тур 4. Введение случайности в инициализации Рассмотренные выше жадные эвристические алгоритмы, в основном, являются детерминированными, что огранинивает их прямое использование в инициализации начальной популяции при решениии ЗК. Но их легко можно модифицировать путем ввода элементов случайности, например, следующим образом. 1) Так в методе ближайшего соседа на шаге 3 можно заменить выбор города, ближайшего к текущему городу s(i), на случайный выбор города с вероятностью обратно пропорциональной расстоянию до s(i). При этом желательно сохранить ненулевые вероятности выбора всех городов. 2)В методе кратчайшей дуги можно заменить выбор кратчайшей дуги также на случайный выбор ребра с вероятностью обратно пропорциональной длине дуги. 3)В методе внедрения можно внести случайность на 2-х шагах. Во-первых на шаге 2, вместо выбора города ближайшего к текущему туру Т ввести случайный выбор города с вероятностью обратно пропорциональной этой близости к туру. В-вторых, на шаге 3 вместо выбора с минимальной разностью длин опять-таки ввести случайный выбор дуги с вероятностью обратно пропорциональной этой разности. 30 Этот прием сохраняет доминирование прежнего выбора, но дает шансы и другим вариантам. 5.Локальные методы поиска Локальная перестановка 2-х ребер В данном методе для текущего решения ЗК устраняются 2 дуги и вместо них вводятся 2 другие дуги, что дает новое потенциальное решение. Пример представлен на следующем рисунке.5. Рис.5. Пример локального «возмущения(искажения)» 2-х дуг Здесь выбираются две дуги: ei между вершинами vW и vx ; ej между вершинами Эти дуги удаляются и «висячие» города соединяются так, как показано на рис.5b. Этот подход получил развитие, где искажаются уже 3 дуги. vy и vz. 31 Здесь выбираются 3 дуги, которые не разделяют города и «висячие» города соединяются по новому. Это дает новое потенциальное решение. Для множества из 3-х дуг можно построить 7 новых решений. Таким образом, для каждого подмножества из 3 дуг мы пытаемся улучшить решение путем локальных преобразований (размера 3). Аналогично можно рассматривать локальные преобразования и большего (чем 2 и 3) размера подмножеств дуг – к. Пример - известный алгоритм Lin-Kernigan. 32 СХЕМЫ КОДИРОВАНИЯ ПОТЕНЦИАЛЬНЫХ РЕШЕНИЙ ЗАДАЧИ КОММИВОЯЖЕРА Задача коммивояжера является одной из базовых для задач комбинаторной оптимизации, для которой разработан специальный каталог «трудно-решаемых» тестовых задач (benchmarks), га которых по международным стандартам принято проводить апробацию алгоритмов решения ЗК. Известно, что для симметричной матрицы (расстояний) ЗК с n городами существует (n-1)!/2 различных решений. В силу важности и большой практической значимости этой задачи она детально исследовалась многими авторами, которые предложили различные схемы кодирования потенциальных решений. потенциальных решений. 1. Кодирование ребер Для полного графа с n городами существует дуг. Идея заключается в том, что мы можем занумеровать их и выбрать из них n дуг, которые образуют Гамильтонов цикл. Например, для ЗК с 8 городами такой код может иметь вид (14, 28, 18, 23, 27, 7, 6, 16). Здесь перечислены дуги, которые образуют Гамильтонов цикл для данной задачи. 33 Основной недостаток этого кодирования в том, что здесь необходимо проверять код на Гамильтонов цикл и генетические операторы кроссинговера могут давать некорректные решения. Размерность поиска при этом кодировании (число потенциальных решений) - число перестановок n дуг из n(n-1)/2 т.е. 2. Двоичное кодирование На начальном этапе рассматривалось также двоичное кодирование, где двоичный код использовался представления номеров городов, которые обходит коммивояжер. Для n городов необходимо двоичных бит. Например, двоичный код для ЗК с 6 городами может иметь вид (000 010 001 100 011 101), который представляет тур 1-3-2-5-4-6-1. Очевидно, что стандартные генетические операторы кроссинговера будут нарушать корректность решений и их необходимо востанавливать. Поскольку каждый ген может принимать (размерность пространства поиска) - nn. n значений, то количество возможных кодов 34 3. Случайное кодирование Для ЗК с n городами случайным образом генерируются n чисел в диапазоне (0,1), которые затем ранжируются в порядке возрастания. Позиция (номер в ранжированном списке) наименьшего числа определяет номер города, который посещается первым и т.д. Например для 6 городов случайно генерировали числа , которым соответствует тур (2-3-4-6-5-1-2). При этом кодировании стандартные генетическин операторы кроссинговера дают корректные решения. Поэтому этот вид кодирования часто применяется при решении задач комбинаторной оптимизации. Проблема в том, при выполнении кроссинговера полезная информация, содержащаяся в родительских особях, часто теряется. Например, возьмем в качестве второго родителя код , который соответствует туру (2-5-1-4-6-3-2). При выполнении 1-точечного кроссинговера над двумя последними особями получаем и Которые соответствуют турам (2-5-3-4-6-1-2) и (2-1-4-6-3-5-2). 35 Из них видно, что информация, содержащаяся в родительских турах практически потеряна. Кроме этого, число вариантов кодирования здесь бесконечно, что существенно повышает размерность задачи. 4. Кодирование путей Наверное, это самый «естественный» способ кодирования – здесь тур явно представляется последовательностью посещаемых городов. Например, код (2-3-6-1-4-5) соответствует замкнутому туру 2-3-6-1-4-5-2. Здесь код является одной из возможных перестановок n городов, число которых n! показывает размерность пространства поиска. Такое кодирование является 2n избыточным – одному туру могут соответствовать 2n различных кодов. Например, хромосомы все представляют один и тот же тур. Очевидно, что обычный оператор кроссинговера может из корректных решений (правильных туров) порождпть некорректные решения. 36 5. Представление соседства В этом случае тур представляется списком соседних городов. Город j находится в позиции i если и только если в туре после города i посещается город j, что показано на рис. i … j ….. Рис. Следование городов в туре Например, вектор n1=(2 4 8 3 9 7 1 5 6) представляет следующий тур T1=(1-2-4-3-8-5-9-6-7). При этом любой тур имеет единственное представление списком соседства. Однако некоторые «списки соседей» могут представлять “неправильные” туры. Например, список соседства n2=(2 4 8 1 9 3 5 7 6) содержит “частичный” тур T2=(1-2-4-1). В этом случае количество кодов фактически также определяется числом перестановок n!. Заметим, что не любая перестановка дает правильный тур. Например, перестановка (2-3-1-6-4-5) дает два цикла 1-2-3-1 и 4-6-5-4. 37 6. Упорядоченное представление В этом случае тур представляется списком из n – городов, где i-й элемент списка имеет номер от 1 до n-i+1. При этом используется базовый упорядоченный список городов L, который служит для ссылок упорядоченного представления. T= (1-2-4-3-8-5-9-6-7), для которого упорядоченный список L = (1 2 3 4 5 6 7 8 9). Тогда данный тур при этом упорядоченном списке представляется следующим списком ссылок e=(1 1 2 1 4 1 3 1 1). Покажем, как из е (код потенциального решения) и базы L строится тур Т: Тур T1=(1), базовый L1= (2 3 4 5 6 7 8 9) , указатель e=(1 1 2 1 4 1 3 1 1). Тур T2=( 1-2), L1 = (3 4 5 6 7 8 9) и указатель в e сдвигается на третью позицию е = (1 1 2 1 4 1 3 1 1). Тур T3=(1-2-4), L = (3 5 6 7 8 9) , е = (1 1 2 1 4 1 3 1 1). Продолжая этот процесс в результате декодирования, мы по данному коду e=(1 1 2 1 4 1 3 1 1), базовому списку L = (1 2 3 4 5 6 7 8 9) построим тур T= (1-2-4-3-8-5-9-6-7) . Другой пример декодирования. 38 Основное преимущество упорядоченного представления в том, что в этом случае работает классический кроссинговер (над векторами целых чисел) !!! То есть для двух допустимых решений кроссиговер производит два допустимых решения – потомка. То есть для двух допустимых решений кроссиговер производит два допустимых решения – потомка. Например, для родителей e1 = (1 1 2 1 | 4 1 3 1 1) и e2 = (5 1 5 5 | 5 3 3 2 1), которые соответствуют турам T1=(1-2-4-3-8-5-9-6-7) и T2=(5-1-7-8-9-4-6-3-2) , имеем следующих потомков при скрещивании 39 О1 = (1 1 2 1 5 3 3 2 1) и О2 = (5 1 5 5 4 1 3 1 1), которые представляют правильные (!!!) туры T3=(1-2-4-3-9-7-8-6-5) и T4=(5-1-7-8-6-2-9-3-4). Здесь для первого гена можно выбрать n городов, для второго (n-1) и т.д., то есть размерность поиска n!. В заключение приведем таблицу, в которой показана размерность пространства поиска для различных методов кодирования. Из этой табл. видно, что хотя кодирование путей имеет 2n избыточность, размерность пространства поиска для него меньше, чем для многих других. Поэтому этот метод применяется чаще. 40 ОПЕРАТОРЫ МУТАЦИИ ДЛЯ ЗК Оператор мутации относительно легко определить на этих представлениях в виде различных перестановок городов в туре. 1. Обмен Выбираются случайно города (позиции) в туре и производится обмен между этими позициями. Например, в туре выбираются города 3 и 6, обмен которых дает тур (1-2-6-4-5-3-7-8-9), что показано на рисунке 2.Внедрение Случайно генерируется номер города и внедряется(переносится) также в случайную позицию. Например, в туре Получаем тур – мутант выбирается город 6 и вставляется между городами 2 и 3. 41 3.Инверсия Выбирается случайный подтур, в котором города порядок городов «инвертируется» Например, Графическая интерпретация 4.Инверсное внедрение Случайно выбирается подтур, инвертируется в нем порядок и внедряется в случайную поцицию. 42 5. Смещение Случайно выбираем подтур и внедряем его в случайную позицию. Например, выбираем подтур 4-5-6 в коде пути (1-2-3-4-5-6-7-8-9) и внедряем его между 8 и 9 позициями, что дает (1-2-3-7-8-4-5-6-9). Это показано на рис. 43 ОПЕРАТОР КРОССИГОВЕРА ДЛЯ РАЗЛИЧНОГО КОДИРОВАНИЯ Классичекий одно-и много-точечный, однородный кроссинговер разрушает перестановку городов и часто дает неправильные туры с преждевременной сходимостью. Поэтому для ЗК разработаны специальные проблемно-ориентированные операторы кроссинговера Прежде всего рассмотрим операторы кроссинговера для кодирования путей Тур (5-1-7-8-9-4-6-2-3) предоставляется просто упорядоченным списком (5 1 7 8 9 4 6 2 3) городов, входящих в тур. Для данного предоставления были определены и исследованы три типа кроссинговера: 1) частично соответствующий (partially-mapped - РМХ); 2) упорядоченный ОК (order - ОХ); 3) циклический ОК (cycle - CХ). Рассмотрим их по порядку. 1. Частично соответствующий ОК (РМХ) строит потомок путем выбора последовательности тура из одного родителя и сохранения порядка и позиции городов из другого родителя 44 насколько это возможно. Подпоследовательность из тура выбирается случайно с помощью двух “секущих” точек, которые служат границами для операции обмена. Рассмотрим алгоритм по шагам. 1. Выбрать 2 случайные позиции в первом родителе(например 3 и 6 в первом родителе) и 2 случайные позиции во втором родителе (6 и 1) на рис. 2. Обменять эти подтуры между собой и получить временные потомки, как показано на рис. Рис. 45 3. Определить частичное отображение (между городами) на основе выбранных подтуров.Для нашего примера это отображение включает 1  6  3, 49 5  2. 4. Используя построенные частичные отображения устранить конфликты во временных потомках путем замены конфликтующих (повторяющихся) городов. Например, в первом потомке меняем город1 на 6, затем, поскольку конфликт остается меняем 6 на 3. В результате получаем потомки, представленные внизу рисунка. Заметим, что этот оператор сохраняет, прежде всего, города в выбранных подтурах. Упорядоченный ОК строит потомок выбором подтура из одного родителя и сохранением относительного порядка городов из другого родителя. Например, для родителей P1 = (1 2 3 | 4 5 6 7 | 8 9) , P2 =(4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом. 1. Сначала сегменты между двумя секущими точками копируется в потомки: О1 = (X X X | 4 5 6 7 | X X), О2 = (X X X | 1 8 7 6 | X X). 2. Далее, в первом родителе начиная со второй секущей точки копируются города из другого родителя, пропуская уже присутствующие в построенном подтуре. 46 3. По достижению конца списка этот процесс продолжается с первой позиции и до первой точки сечения (по кольцу). Для нашего примера после второй точки сечения во втором родителе мы имеем следующую последовательность 9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6. Удаляем из нее города 4, 5, 6, 7 поскольку они уже есть в первом потомке и в результате получаем последовательность 9 – 3 – 2 – 1 – 8. Ее мы помещаем в первый потомок, начиная со второй точки сечения (по кольцу) и получаем потомок O1 = (2 1 8 | 4 5 6 7 | 9 3). Аналогично получаем второго потомка O2 = (3 4 5 | 1 8 7 6 | 9 2). Оператор кроссинговера ОХ использует то, что при представлении тура прежде всего важен порядок городов, например, два тура (9–3–4–5–2–1–8–7–6) и (4–5–2–1–8–7–6–9–3) идентичны. Еще один пример выполнения этого оператора. 47 Здесь выбран подтур в первом родителе, который перенесен в потомок. Оставшиеся места заполены городами из второго родителя с сохранением их порядка. При этом мы начинаем с выбранной позиции во втором родителе (на рис. отмечена стрелочкой). Если город уже присутствует в туре, то он пропускается. Позиционный кроссинговер (Position-based Crossover) выполняется следующим образом. 1. Выбрать случайно несколько позиций в первом родителе, например, позиции 2,5,6 и 9 первого родителя рис. 2. Построить частичный первый потомок путем переноса выбранных позиций. 3. Отметить во втором родителе города, вошедшие в частичный потомок. 4. Перенести оставшиеся города во втором родителе в потомок в том же порядке Рис.Пример позиционного кроссовера 48 Циклический ОК использует концепцию виртуального цикла и строит потомки таким образом, что каждый город вместе со своей позицией идет от одного из родителей. Опишем его по шагам. 1. Генерировать виртуальный цикл с первой неиспользованной позиции первого родителя. Предположим, что мы находимся в позиции i (значение) первого родителя, которая имеет аллель j. Далее переходим в позицию j второго родителя, значение которой в свою очередь показывает позицию в первом родителе, в которую надо перейти. Этот процесс показан на рис. Таким образом мы действуем до тех пор, пока не получим цикл. Для нашего примера это 1-5-2-4-9-1. 2. Копировать аллели (значения) построенного виртуального цикла из первого родителя в первый потомок. 49 3. Генерировать следующий виртуальный цикл, начиная с первой неиспользованной позиции второго родителя. Для нашего примера это 6-3. 4. Копировать аллели виртуального цикла второго родителя в первый потомок. 5. Повторять эти действия , пока не будет построен потомок. Таким образом, оператор ОК СХ сохраняет абсолютные позиции потомков и родителей. Рекомбинация дуг (Edge Recombination Crossover - ERC) Самой существенной информацией в кодировании путей (перестановке городов) является расположение дуг. Поэтому, желательно сохранить одни и те же дуги в обоих родителях. Пусть есть два родителя (тура) (1-2-3-4-5-6) и (4-1-2-6-3-5). Для них строится таблица дуг. 50 Знак + А означает, что данная дуга содержится в обоих родителях (и поэтому ее желательно сохранить в потомках). Выполнение оператора рекомбинации начинается случайным выбором одного города. Следующая дуга выбирается в соответствии с таблицей дуг по следующим правилам. 1. Если текущий город имеет общую (для 2-х родителей) дугу, то переход в следующий город согласно этой дуге. 2. Иначе переход на город с кратчайшим списком дуг. 3. Если таких городов несколько, то выполняется случайный выбор из них. После определения следующего города выполняется коррекция тещей таблицы дуг путем удаления посещенных городов. Повторить эту процедуру до тех пор, пока не будут посещены все города. Родители и потомки, полученные согласно этой процедуре представлены на следующе рис. 51 52 Упорядоченное представление В этом случае тур представляется списком из n – городов, где i-й элемент списка имеет номер от 1 до n-i+1. При этом используется базовый упорядоченный список городов L, который служит для ссылок упорядоченного представления. T= (1-2-4-3-8-5-9-6-7), для которого упорядоченный список L = (1 2 3 4 5 6 7 8 9). Тогда данный тур при этом упорядоченном списке представляется следующим списком ссылок e=(1 1 2 1 4 1 3 1 1). Покажем, как из е (код потенциального решения) и базы L строится тур Т: Тур T1=(1), базовый L1= (2 3 4 5 6 7 8 9) , указатель e=(1 1 2 1 4 1 3 1 1). Тур T2=( 1-2), L1 = (3 4 5 6 7 8 9) и указатель в e сдвигается на третью позицию е = (1 1 2 1 4 1 3 1 1). Тур T3=(1-2-4), L = (3 5 6 7 8 9) , е = (1 1 2 1 4 1 3 1 1). Продолжая этот процесс в результате декодирования, мы по данному коду e=(1 1 2 1 4 1 3 1 1), базовому списку L = (1 2 3 4 5 6 7 8 9) построим тур T= (1-2-4-3-8-5-9-6-7) . Основное преимущество упорядоченного представления в том, что в этом случае работает классический кроссинговер (над векторами целых чисел) !!! 53 То есть для двух допустимых решений кроссиговер производит два допустимых решения – потомка. Например, для родителей e1 = (1 1 2 1 | 4 1 3 1 1) и e2 = (5 1 5 5 | 5 3 3 2 1), которые соответствуют турам T1=(1-2-4-3-8-5-9-6-7) и T2=(5-1-7-8-9-4-6-3-2) , имеем следующих потомков при скрещивании О1 = (1 1 2 1 5 3 3 2 1) и О2 = (5 1 5 5 4 1 3 1 1), которые представляют правильные (!!!) туры T3=(1-2-4-3-9-7-8-6-5) и T4=(5-1-7-8-6-2-9-3-4). 54 Представление соседства В этом случае тур представляется списком соседних городов. Город j находится в позиции i если и только если в туре после города i посещается город j, что показано на рис. i … j ….. Рис. Следование городов в туре Например, вектор n1=(2 4 8 3 9 7 1 5 6) представляет следующий тур T1=(1-2-4-3-8-5-9-6-7). При этом любой тур имеет единственное представление списком соседства. Однако некоторые «списки соседей» могут представлять “неправильные” туры. Например, список соседства n2=(2 4 8 1 9 3 5 7 6) содержит “частичный” тур T2=(1-2-4-1). 55 Для данного способа кодирования решения были предложены и исследованы 3 основных оператора кроссинговера: 1) обмен ребер (дуг) графа; 3) обмен подтуров; 3) эвристический кроссинговер . 1) Обмен ребер Этот тип кроссинговера строит потомка (случайным) выбором ребра (пары городов i-j ) из первого родителя, затем выбором соответствующего ребра из второго родителя и т.д. Оператор наращивает тур выбором ребер из различных родителей. Если новое ребро (взятое у одного из родителей) образует преждевременный (частичный) цикл в текущем (ещё не полном) туре, то оператор выбирает (случайно) вместо этого ребра одно из оставшихся ребер, которое не дает преждевременного цикла. Например, для 2-х родителей n1 = (2 3 8 7 9 4 1 5 6), представляющего тур T1=(1-2-3-8-5-9-6-4-7-1), и n2 = (7 5 1 6 9 2 8 4 3) 1 = (2 5 8 7 9 4 3 1 6). тура T2=(1-7-8-4-6-2-5-9-3-1) получаем следующего потомка 56 Здесь произведен обмен (случайный) ребер 3  5 во второй позиции, далее при попытке обмена 8  1 в седьмой позиции возникает конфликт ( два ребра входят в 8), поэтому случайно выбирается 3 в позиции 7 (из оставшихся 6, 1, 3), 1 – в позиции 8 и 6 в позиции 9 . В результате порождается потомок 1, который соответствует туру T3=(1-2-5-9-6-4-7-3-8-1). Обмен подтуров Этот оператор строит потомки путём выбора (случайной длины) подтура из первого родителя, затем выбора подтура (опять случайной длины) из второго родителя и их обмена. Как и ранее в случае конфликта оператор случайно выбирает другое ребро (город) из не вошедших в построенный тур. Эвристическое скрещивание Данный оператор строит потомка случайным выбором города в качестве начальной точки для формирования тура. Затем сравниваются два ребра, исходящие из этого города, имеющихся в двух родителях, и из них выбирается лучшее с меньшей стоимостью. Полученный город (в него входит выбранное ребро на предыдущем этапе), используется в качестве начальной точки при выборе следующего ребра и т.д. 57 Как и ранее в случае возникновения преждевременного цикла, следующий город выбирается случайно из городов, еще не вошедших в текущий тур. Известна следующая модификация этого оператора. Если оптимальное (с меньшей стоимостью) ребро дает преждевременный цикл в потомке, то проверяется альтернативное ребро (с большей стоимостью) на генерацию преждевременного цикла. Если это ребро не генерирует цикл, то оно включается в тур, иначе выбирается минимальное из q ребер (где q –параметр пула выбора) случайно выбранных из оставшихся городов. Преимущество этого кодирования в том, что в этом случае анализ схем (шаблонов) можно проводить по аналогии с двоичным случаем. Например, схема (   3  7   ) представляет множество всех туров с ребрами (4-3) и (6-7). Однако основной недостаток этого представления в весьма посредственных результатах тестовых задач для всех 3-х рассмотренных операторов. Кроссинговер обмена ребер часто разрывает хорошие туры при обмене ребер родителей. Кроссинговер обмена подтуров даёт лучшие результаты, чем предыдущий так как “отношение разрыва” здесь меньше. 58 Матричное представление Опубликовано достаточно много работ, где для решения задачи коммивояжера используется представление тура в виде двоичной матрицы, элементы которой mij=0,1. При этом применяются два основных подхода, которые используют: 1) матрицу смежности; 2) матрицу предшествования, которые мы рассмотрим ниже. Матрица смежности В матрице смежности элемент mij=1 в том и только случае, если в туре после города i посещается город j (в графе есть ребро от вершины i в вершину j). Например, табл.3.7 содержит матрицу смежности для тура Т1 =(1-2-4-3-8-6-5-7-9) и табл.3.8 – матрицу смежности для тура Т2 =(14-3-6-5-7-2-8-9). Отметим, что в этом случае каждая строка и столбец матриц содержат одну единицу. Для матрицы смежности можно использовать одно- или двуточечный кроссинговер, где обмен производится, например, столбцами. Но в этом случае необходим дополнительный алгоритм восстановления, который позволяет восстанавливать полученные потомки до полных туров. Рассмотрим, этот подход на примере двухточечного вертикального кроссинговера с точками скрещивания 2 и 6. При этом производится обмен столбцами (3,4,5,6) матриц смежности (табл. 2.1 и 59 табл. 2.2). В результате получаем промежуточный результат в виде матриц, которые представлены табл.2.3 и табл.2.4. Обе матрицы не представляют правильных решений, но заметим, что суммарное число единиц в каждой из этих промежуточных матриц правильное (9 единиц). Таблица 3.7 1 2 3 4 5 6 7 8 9 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 60 Таблица 3.8 1 2 3 4 5 6 7 8 9 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 61 Матрица предшествования Рассмотрим представление тура в виде двоичной матрицы предшествования [4]. В этом случае элемент матрицы mij равен 1, если и только если город i предшествует (встречается в туре раньше) городу j. В противном случае mij=0. Отметим, что здесь имеется в виду не только непосредственное предшествование (город i связан непосредственно с городом j) но и более «глубокое». Например, тур Т3=(3-1-2-8-7-4-6-9-5) представляется бинарной матрицей предшествования, которая показана в табл.3.11. Здесь элементы главной диагонали mii=0 и mij=1, если i-й город предшествует в туре j-му городу. Например, в первой строке город 1 предшествует в туре городам 2, 4, ….,9, но не предшествует городу 3. 62 Таблица 3.11 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 4 1 1 1 5 6 1 1 7 1 1 1 1 8 1 1 1 1 1 9 1 63 В этом представлении тура матрица М размерности n  n обладает следующими свойствами: 1. число единиц в матрице равно точно 2. mij=0 для всех 1  i  n ; 3. если mij =1 и mjk = 1, то mik =1. n(n  1) ; 2 64 ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗК Ниже представлен псвевдокод ГА для решения ЗК 65 ГА_задачи_коммивояжера(матрица расстояний между городами) { Инициализация N потенциальных решений, значений вероятностей мутации, кроссовера Pm , Pc и других параметров; Представление потенциальных решений {xi} с помощью выбранного метода кодирования (путевое, соседство, упорядоченное и т.п.); Вычисление длины тура для каждого потенциального решения; While( не выполнен критерий останова) { For k=1 to N { Выбор родительских особей из множества {xi} для порождения потомка; Построение потомка Ck с помощью выбранного кроссовера; r  U (0,1) (случайное число из диапазона (0,1)); If r  Pm then Выполнение мутации над потомком Ck с помощью выбранного метода мутации; End if Вычисление длины тура для Ck; Замещение особей-дубликатов в {xi }  Ci ; {xi }  лучшие N особей из {xi }  Ci ; } Следующее поколение; } 66 Каждый шаг этого алгоритма можно реализовать различными методами, часть из которых изложены выше. Например, для инициализации популяции лучше использовать один из эвристических методов. Можно применять различные методы кодирования тура. Целесообразно использовать несколько методов кроссинговера с различными вероятностями с их случайным выбором. Более того, в процесе решения можно увеличивать значения вероятностей для более эффективных методов. Аналогично можно применять различные методы мутации также с адаптацией вероятностей. Это относится также к методам отбора родителей. Пример апробации для benchmark Berlin52(показан оптимальный тур с миниальной длиной 7542). 67 Использовались следующие параметры. Мощность популяции – N=50. Инициализация – случайная. Кодирование путей. Фитнесс-функция , где максимум и минимум берется по всей популяции, D(z) - длина тура z. Эта фитнесс-функция дает большие значения для туров с меньшей длиной (и наоборот). Метод отбора родителей – рулетка. Метод кроссинговера – РМХ (частичное отображение) и др.(показаны ниже). Контроль над дубликатами (одинаковыми особями популяции) – копии заменяются случайными особями. Результаты усреднялись по 20 запускам, каждый по 300 поколений. 68 Различные методы кросинговера дали разные результаты (минимальная длина тура) Также исследовались различные методы мутации, которые показали Применение эвристических методов инициализации позволило повысить качество решения 69 Пример типичного запуска с порядковым кроссинговером, мутацией – инверсией и инициализацией методом ближайшего соседа (длина тура -8036). Пример сканов из лабораторной работы . 70 71 72 73 74