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