Я играю с генетическим алгоритмом, в котором хочу развивать графики. Вы знаете, как применить кроссовер и мутацию, когда хромосомы являются графиками?
Или мне не хватает кода для графиков, который позволяет мне применять «обычный» кроссовер и мутацию к битовым строкам?
большое спасибо! Любая помощь, даже если она не связана напрямую с моей проблемой, приветствуется!
Мануэль
Мне нравится предложение Сандора об использовании NEAT, разработанный Кеном Стэнли.
NEAT был разработан для развития нейронных сетей с произвольной топологией, но в основном это просто ориентированные графы. До NEAT было много способов развития нейронных сетей, но одним из наиболее важных достижений NEAT было то, что он предоставил способ выполнения значимого кроссовера между двумя сетями с разными топологиями.
Для этого NEAT использует исторические отметки, прикрепленные к каждому гену, чтобы" выровнять "гены двух геномов во время кроссовера (биологи называют этот процесс синапсис). Например:
(источник: natekohl.net)
(В этом примере каждый ген представляет собой прямоугольник и представляет связь между двумя узлами. Число вверху каждого гена является исторической меткой для этого гена.)
Вкратце: выстраивание генов на основе исторических данных - принципиальный способ выполнить кроссовер между двумя сетями без дорогостоящего топологического анализа.
Вы также можете попробовать генетическое программирование. Граф будет наиболее близким к дереву, а GP использует деревья ... если вы все еще хотите использовать GA вместо GP, посмотрите, как выполняется кроссовер на GP, и это может дать вам представление о том, как это сделать на графиках вашего ГА:
(источник: Geneticprogramming.com < / а>)
Вот как работает кроссовер для деревьев (и графов):
Как уже упоминалось, один из распространенных способов пересечения графов (или деревьев) в GA - это замена подграфов (поддеревьев). Для мутации просто случайным образом измените некоторые узлы (с небольшой вероятностью).
В качестве альтернативы, если вы представляете график как матрицу смежности, вы можете поменять местами / изменить элементы в матрицах (что-то вроде использования двумерной битовой строки).
Я не уверен, что использование битовой строки - лучшая идея, я бы предпочел представлять хотя бы веса с реальными значениями. Тем не менее, битовые строки также могут работать.
Если у вас фиксированная топология, то и кроссовер, и мутация довольно просты (при условии, что вы изменяете только веса сети):
Кроссовер: взять некоторые веса у одного родителя, остальные - у другого, можно очень легко сделать, если вы представите веса в виде массива или списка. Для получения дополнительных сведений или альтернатив см. 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
Что ж, я никогда не играл с такой реализацией, но в конечном итоге для кроссовера вы можете выбрать ветвь одного из графов и поменять ее ветвью из другого графа.
Для мутации вы можете случайным образом изменить узел внутри графа, с небольшой вероятностью.
