применение кроссовера и мутации к графу (генетический алгоритм)

Question

Я играю с Генетическим Алгоритмом, в котором я хочу развивать графики. Знаете ли вы способ применения кроссовера и мутации, когда хромосомы представляют собой графики?

Или я пропускаю кодирование для графиков, которое позволяет мне применять «обычный» кроссовер и мутацию по битовым строкам?

спасибо большое! Любая помощь, даже если она не имеет прямого отношения к моей проблеме, приветствуется!

Manuel

Answer 1

Мне нравится предложение Сандора об использовании алгоритма Кена Стэнли NEAT .

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

Для этого NEAT использует исторические отметки , прикрепленные к каждому гену, чтобы "выстроить" гены двух геномов во время кроссовера (процесс биологи называют synapsis ). Например:

кроссовер с различными топологиями в NEAT http://natekohl.net/media/neat-crossover.png

(В этом примере каждый ген является коробкой и представляет собой связь между двумя узлами. Число в верхней части каждого гена является исторической маркировкой для этого гена.)

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

Answer 2

Вы также можете попробовать Генетическое программирование . График был бы ближе всего к дереву, а GP использует деревья ... если вы все еще хотите использовать GA вместо GP, то посмотрите, как выполняется кроссовер на GP, и это может дать вам представление о том, как его выполнить на графиках вашей ГА:

Кроссовер http://www.geneticprogramming.com/Tutorial/cross1.gif

Вот как работает кроссовер для деревьев (и графиков):

1. Вы выбираете 2 образца для спаривания.
2. Вы выбираете случайный узел у одного родителя и меняете его случайным узлом у другого родителя.
3. Полученные деревья являются потомками.

Answer 3

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

Если у вас фиксированная топология, то и кроссовер, и мутация довольно просты (при условии, что вы только меняете вес сети):

Кроссовер: взять некоторые веса от одного родителя, остальные от другого, очень легко, если вы представите веса в виде массива или списка. Для более подробной информации или альтернатив см. http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29.

Мутация: просто выберите некоторые веса и немного их откорректируйте.

Развитие некоторых других вещей (например, функция активации) очень похоже на это.

Если вы также хотите развить топологию, тогда все станет намного интереснее. Есть довольно много дополнительных возможностей мутации, таких как добавление узла (скорее всего, подключенного к двум уже существующим узлам), разбиение соединения (вместо A-> B есть A-> C-> B), добавление соединения или противоположностей из них.

Но кроссовер не будет слишком простым (по крайней мере, если количество узлов не фиксировано), потому что вы, вероятно, захотите найти «совпадающие» узлы (где сопоставление может быть чем угодно, но, вероятно, связано с аналогичной «ролью» или аналогичное место в сети). Если вы тоже хотите это сделать, я настоятельно рекомендую изучить уже существующие методы. Тот, который я знаю и люблю, называется NEAT. Вы можете найти информацию об этом на
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
и http://www.cs.ucf.edu/~kstanley/neat.html

Answer 4

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

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

Answer 5

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