Я играю arround с генетическим алгоритмом, в котором я хочу развить графики. Знаете ли вы способ применения кроссовера и мутации, когда хромосомы являются графиками?
Или мне не хватает кодирования для графиков, которые позволяют мне применять "обычный" кроссовер и мутацию над битовыми строками?
Большое спасибо! Любая помощь, даже если она не связана напрямую с моей проблемой, оценивается!
Мануэль
Мне нравится предложение Шандора использования Ken Stanley алгоритм NEAT.
NEAT был разработан для развития нейронных сетей с произвольными топологиями, но это только ориентированные в основном графики. Было много способов развития нейронных сетей до NEAT, но один из важных вкладов NEAT заключался в том, что он обеспечил способ выполнять значимый кроссовер между двумя сетями, имеющими разные методы работы.
Для этого NEAT использует исторические маркировки, прикрепленные к каждому гену, чтобы "выровнять" гены двух геномов во время кроссовера (процесс биологи называют synapsis). Например:
кроссовер с различными топологиями в NEAT http://natekohl.net/media/neat-crossover.png
(В этом примере каждый ген представляет собой коробку и представляет собой связь между двумя узлами. Число в верхней части каждого гена является исторической маркировкой для этого гена.)
В заключение: выстраивание генов на основе исторических меток является принципиальным способом выполнения кроссовера между двумя сетями без дорогого топологического анализа.
Вы также можете попробовать Генетическое программирование. График будет самым близким к дереву, а GP использует деревья... если вы все еще хотите использовать GA вместо GP, тогда посмотрите, как кроссверь выполняется на GP, и это может дать вам представление о том, как его выполнить на графиках вашего GA:
Кроссовер http://www.geneticprogramming.com/Tutorial/cross1.gif
Вот как работает кроссовер для деревьев (и графиков):
Как отмечали другие, один общий способ пересечения графов (или деревьев) в GA состоит в замене подграфов (поддеревьев). Для мутации просто произвольно меняйте некоторые узлы (с малой вероятностью).
В качестве альтернативы, если вы представляете график как матрицу смежности, то вы можете менять/изменять элементы в матрицах (например, используя двумерную битовую строку).
Я не уверен, что использование битовой строки - лучшая идея, я скорее представляю по крайней мере веса с реальными значениями. Тем не менее, битстроны также могут работать.
Если у вас есть фиксированная топология, то и кроссовер, и мутация довольно просты (предполагая, что вы только развиваете весы сети):
Кроссовер: возьмите несколько весов от одного родителя, а остальные - от другого, можно очень легко сделать, если вы представляете веса как массив или список. Для получения дополнительной информации или альтернатив см. http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29.
Мутация: просто выберите некоторые из весов и слегка настройте их.
Эволюция некоторых других вещей (например, функция активации) очень похожа на них.
Если вы также хотите развить топологию, тогда все станет намного интереснее. Существуют некоторые дополнительные возможности мутации, такие как добавление node (скорее всего, к двум уже существующим узлам), разделение соединения (вместо 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
Ну, я никогда не играл с такой реализацией, но в конечном итоге для кроссовера вы могли выбрать ветвь одного из графиков и обменять ее веткой с другого графика.
Для мутации вы можете случайно изменить node внутри графика с небольшой вероятностью.
