Операция кроссовера в генетическом алгоритме для TSP

Question

Я пытаюсь решить задачу коммивояжера (TSP) с помощью Генетический алгоритм . Мой геном - перестановка вершины в графе (путь для продавца).

Как мне выполнить операцию кроссовера над моими геномами?

Где я могу найти реализации моей проблемы в C #?

Answer 1

Вы должны проверить « Решение генетического алгоритма TSP, избегающее специального кроссовера и мутации » от Gokturk Ucoluk. Он дает обзор специальных операторов кроссовера для перестановок и предлагает умное представление перестановок, которое хорошо работает со стандартным кроссовером (т. Е. Пересечение двух перестановок всегда приводит к двум перестановкам).

Основная идея заключается в том, чтобы представить перестановку в виде последовательности инверсии, то есть для каждого элемента i, сохранить в a[i], сколько элементов больше i слева от i в перестановке. В отличие от прямого представления, единственное ограничение на a[i] является локальным, то есть a[i] не может быть больше, чем N - i. Это означает, что простое пересечение двух действительных последовательностей инверсии всегда приводит к двум действительным последовательностям инверсии - нет необходимости в специальной обработке повторяющихся элементов.

Answer 2

Вместо того, чтобы использовать стандартную технику пересечения GA (как , изложенную MusiGenesis ), лучше использовать заказанное пересечение для задачи коммивояжера .

Обычный подход не работает так хорошо для TSP, потому что фитнес-функция очень чувствительна к относительным позициям различных городов в развитом маршруте, а не к их абсолютным позициям. Например, если вы посещали все европейские столицы, самый короткий маршрут на самом деле не зависит от того, посещаете ли вы Братиславу 1-го, 2-го или 9-го. Что более важно, вы посещаете его непосредственно перед или сразу после посещения Вены , а не посещаете Хельсинки, Афины и 6 других столиц между ними.

Конечно, как mjv также указывает , традиционный переход также будет вводить дубликаты на вашем маршруте. Если у одного из родителей Париж находится в положении 2, а у другого - в положении 14, пересечение может привести к одному усовершенствованному маршруту, который дважды посещает Париж (и пропускает другой город), и к другому развитому маршруту, который вообще не посещает его. Упорядоченный перекрестный генетический оператор не страдает от этой проблемы. Сохраняет элементы и изменяет порядок.

Answer 3

Вот программа на C # подход к тому, что вы ищете.

Что касается интереса (или отсутствия такового) реализации кроссовера , все это зависит от конкретной логики выбора, которую ваша реализация будет использовать (и / или самой функции оценки, если, например, она включает оценку скорости улучшения). Во многих случаях кросс-операции «спасут от рубящего блока» некоторые решения, которые эффективны / оптимальны в области графика, но каким-то образом «застряли» в других . Это не означает, что если общий алгоритм является достаточно медленным и покрывает значительный процент пространства решений, те же самые решения, возможно, не были обнаружены заново, но перекрестный переход также может увеличить эти открытия (и / или позволить вам застрять в еще один локальный минимум ;-))

Не имеет прямого отношения, но представляет интерес для тех, кто изучает ГА, это оригинальный «окончательный» эксперимент в ГА оригинальный «окончательный» эксперимент в ГА, проф. Олдерман (из Известность RSA), которая использовала фактические молекулы ДНК [в программу на C - просто шучу], чтобы решить связанную проблему графов, проблему гамильтоновых графов.

Редактировать : Перечитывая вопрос, я понимаю, почему вы задали его или, точнее, , почему вы хотели бы ответить "Нет, вы не хотите перекрестного ответа" ; -)
Ваш геноним напрямую связан с самим графиком (ничего страшного в этом, a priori ), но это создает препятствие для того, чтобы большинство перекрестных потомков не было жизнеспособными, поскольку они могут может иметь повторяющиеся узлы (посещать один и тот же город дважды или более) и не иметь узлов (не посещать некоторые города) ... Кроме того, жизнеспособные перекрестные переходы будут влиять на похожие графики и, следовательно, могут просто увеличивать затраты на поиск по сравнению с какими мутациями обнаружил бы ...
Гм ... Тогда, может быть, кроссовер, в этой конкретной реализации не очень поможет алгоритму (и действительно потребует значительную часть его ЦП для создания, тестирования и часто отбрасывать кросс -по потомкам, процессор, который лучше использовать, предоставляя больше итераций и более медленную скорость охлаждения ...). Если не! Вы найдете умный способ выполнения перекрестных операций; -)

Answer 4

Цель кроссовера - расширить пространство эволюционного поиска, объединив новые геномные комбинации.

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

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

Answer 5

Вот моя точная реализация так называемого метода "частично сопоставленного кроссовера" в GA для TSP.

Здесь - статья, которая объясняет частично сопоставленный кроссовер в теории, а ниже - мой код.

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}

Answer 6

Когда я был на первом курсе в моем университете, я делал некоторые вычисления (которые заняли около 30 страниц) о влиянии различных операторов GA на сходимость решения. Насколько я помню, кроссовер - не лучшее решение для TSP, более подходящим решением является мутация, которая инвертирует подпоследовательность вершин.

пример:

до: A BCDEF GH

после: A FEDCB GH

Answer 7

«Кроссовер» в генетических алгоритмах просто относится к произвольному способу смешивания двух «генетических последовательностей», каждая из которых представляет конкретное решение проблемы (то, как последовательность сопоставляется с решением, зависит от вас). Так, например, скажем, у вас есть популяция, которая состоит из следующих двух последовательностей:

AAAAAAAAAA
BBBBBBBBBB

Один из способов рекомбинирования этих двух «родительских» последовательностей состоит в том, чтобы случайным образом выбрать точку пересечения (скажем, положение 3), в результате чего получаются следующие две «дочерние» последовательности:

AAABBBBBBB
BBBAAAAAAA

Или вы можете случайно выбрать две точки пересечения (скажем, 3 и 8), что приведет к следующим двум последовательностям:

AAABBBBBAA
BBBAAAAABB

Для забавы и дополнительной изменчивости вы также можете ввести возможность случайных точечных мутаций:

AAABBBABAA
BBBAAAAABB

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