От генов к нейронным сетям: понимание и создание NEAT (нейроэволюции расширяющихся топологий) с нуля

Практическая нейроэволюция: воспроизведение инноваций NEAT и пошаговое руководство по коду

Делиться

Введение

Нейроэволюция расширяющихся топологий (NEAT) — мощный алгоритм, представленный в 2002 году Кеннетом О. Стэнли и Ристо Мииккулайненом из Техасского университета в Остине в данной статье. Алгоритм NEAT привнес новую идею в стандартные методы нейроэволюции, которые развивали сети с фиксированной топологией, динамически увеличивая сложность сетей от поколения к поколению.

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

Эволюционные алгоритмы: общий обзор

Прежде чем перейти к NEAT, давайте рассмотрим основы эволюционного алгоритма. Вдохновленные генетикой и естественным отбором, эволюционные алгоритмы — это тип алгоритмов оптимизации, которые решают сложные задачи путём итеративного улучшения популяции возможных решений.

Основная идея — имитировать процесс биологической эволюции:

1. Инициализация: процесс начинается с генерации начальной популяции потенциальных решений. Эти начальные решения генерируются случайным образом, и каждое решение обычно представляется в виде «генома» или «хромосомы», кодирующей его особенности и характеристики.
2. Оценка: каждая особь в популяции оценивается по тому, насколько хорошо она решает поставленную задачу. Это делается с помощью функции приспособленности , которая присваивает каждому решению числовой балл. Чем выше приспособленность, тем лучше решение.
3. Отбор: на основе их приспособленности выбирается подгруппа популяции, которая становится «родителями» следующего поколения. Особи с более высокими показателями приспособленности имеют более высокую вероятность быть выбранными.
4. Размножение: Отобранные особи размножаются, создавая «потомство» для следующего поколения с помощью генетических операторов . На этом этапе происходят два основных процесса:
   • Кроссовер: два или более родительских генома объединяются для создания новых геномов потомков, объединяя выгодные признаки.
   • Мутация: небольшие изменения случайным образом вносятся в геномы потомков. Это вносит новизну и помогает исследовать пространство поиска, предотвращая застревание алгоритма в локальном оптимуме.
5. Замена: вновь появившееся потомство заменяет текущую популяцию (полностью или частично), образуя новое поколение.
6. Завершение: Шаги 2–5 повторяются в течение фиксированного числа поколений, пока не будет достигнут определенный порог приспособленности или пока не будет найдено удовлетворительное решение проблемы.

Что делает NEAT особенным?

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

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

• Как выполнить кроссинговер между топологически разнообразными сетями: В традиционных генетических алгоритмах объединение двух геномов с существенно различающимися структурами часто приводит к появлению нефункциональных или деформированных потомков. Представьте себе попытку объединить две разные нейронные сети, одна из которых имеет три скрытых слоя, а другая — только один. Простое усреднение весов или случайное объединение связей, скорее всего, нарушит функциональность сети.
• Как поддерживать разнообразие в популяции с существенно различающейся топологией: Когда сети могут усложняться (добавляя новые узлы и связи), эти структурные мутации часто приводят к временному снижению их приспособленности. Например, новая связь может нарушить функциональность существующей сети до того, как её параметры будут настроены должным образом. В результате недавно мутировавшие сети могут быть преждевременно вытеснены более простыми и оптимизированными, даже если новый вариант имеет потенциал эволюционировать в более совершенное решение со временем. Такая преждевременная сходимость к локальному оптимуму является распространённой проблемой.

Как NEAT решает эти проблемы

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

Исторические отметки

Для решения задачи кроссинговера между топологически разнообразными сетями в NEAT введена концепция инновационных чисел . При добавлении к сети нового соединения или узла в процессе мутации ему присваивается глобально уникальный инновационный номер. Этот номер служит исторической меткой, указывающей на историческое происхождение данной генетической особенности.

Рассмотрим пример на изображении выше, где у нас есть две сети, «Родитель 1» и «Родитель 2», проходящие кроссинговер. Мы видим, что обе сети имеют связь от узла 2 к узлу 5 с номером инновации 4. Это говорит о том, что эта связь, должно быть, была унаследована обеими сетями от общего предка в какой-то момент. Однако мы также видим, что у «Родителя 1» есть связь (от узла 1 к узлу 5) с номером инновации 8, а у «Родителя 2» такой связи нет. Это показывает, что «Родитель 1» развил эту связь независимо.

Во время скрещивания NEAT выравнивает гены (узлы и связи) двух родителей на основе их инновационных чисел.

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

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

Видообразование

Для поддержания разнообразия в популяции с существенно различающейся топологией и предотвращения преждевременной конвергенции NEAT использует метод видообразования . В результате видообразования популяция разделяется на различные «виды» на основе топологического сходства. Сети внутри одного вида с большей вероятностью будут иметь общие предковые черты и, следовательно, более схожую структуру.

Сходство между двумя сетями (геномами) рассчитывается с помощью функции расстояния совместимости. Эта функция учитывает три компонента:

• Число непересекающихся генов (генов, присутствующих в одном геноме, но отсутствующих в другом, но находящихся в пределах общего исторического диапазона).
• Число избыточных генов (генов, присутствующих в одном геноме, но отсутствующих в другом, и находящихся за пределами общего исторического диапазона).
• Средняя разница веса совпадающих генов.

Если расстояние совместимости между двумя сетями падает ниже определенного порога, они считаются принадлежащими к одному виду.

Видоизменяя популяцию, NEAT обеспечивает следующее:

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

Основные компоненты NEAT

Алгоритм NEAT состоит из четырех основных компонентов:

Узловые гены

Каждый ген узла представляет собой нейрон нейронной сети. Каждый узел имеет:

• Идентификатор (уникальный идентификатор)
• Слой: он может быть входным, скрытым или выходным.
• Функция активации
• Значение смещения

class NodeGene: def __init__(self, id, layer, activation, bias): self.id = id self.layer = layer # Слой, к которому принадлежит узел self.activation = activation # Функция активации self.bias = bias

Гены связи

Гены связей (синапсы) представляют собой связи между нейронами сети. Каждый ген связей имеет:

• Идентификатор входного узла
• Идентификатор выходного узла
• Масса
• Флаг «Включено» (указывает, включено ли соединение)
• Номер инновации (уникальный идентификатор, присваиваемый при первом создании соединения)

class ConnectionGene: def __init__(self, in_node_id: int, out_node_id: int, weight: float, innov: int, enabled: bool = True): self.in_node_id = in_node_id self.out_node_id = out_node_id self.weight = weight self.enabled = enabled # Включено ли соединение или нет self.innov = innov # Номер инновации, описанный в статье

Геномы

Геном — это «генетический чертеж» отдельной нейронной сети в алгоритме NEAT. По сути, это совокупность всех генов узлов и связей, определяющих структуру и параметры сети. Используя геном, мы впоследствии сможем построить работоспособную сеть (которую назовём фенотипом). Каждый геном представляет одну особь в популяции.

класс Геном: def __init__(self, nodes, connections): self.nodes = {node.id: node для node в nodes, если node не None} self.connections = [c.copy() для c в connections] self.fitness = 0

Трекер инноваций

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

class InnovationTracker: def __init__(self): self.current_innovation = 0 self.connection_innovations = {} # (in_node_id, out_node_id) -> innovation_number self.node_innovations = {} # connection_innovation -> (node_innovation, conn1_innovation, conn2_innovation) self.node_id_counter = 0 def get_connection_innovation(self, in_node_id, out_node_id): «»»Получить номер инновации для соединения, создав при необходимости новое»»» key = (in_node_id, out_node_id) if key not in self.connection_innovations: self.connection_innovations[key] = self.current_innovation self.current_innovation += 1 return self.connection_innovations[key] def get_node_innovation(self, connection_innovation): «»»Получаем числа инноваций для вставки узла, создавая новые при необходимости»»» if connection_innovation not in self.node_innovations: # Создаем новый узел и два соединения node_id = self.node_id_counter self.node_id_counter += 1 conn1_innovation = self.current_innovation self.current_innovation += 1 conn2_innovation = self.current_innovation self.current_innovation += 1 self.node_innovations[connection_innovation] = (node_id, conn1_innovation, conn2_innovation) return self.node_innovations[connection_innovation]

Поток алгоритма NEAT

Разобравшись с основными компонентами, мы можем собрать их воедино и понять, как работает NEAT. В показанном примере алгоритм пытается решить задачу XOR.

1. Инициализация

Первое поколение геномов всегда создаётся с очень простой и фиксированной структурой. Этот подход соответствует философии NEAT: «Начиная с простого и постепенно усложняя», что гарантирует сначала изучение самых простых решений, постепенно увеличивая сложность.

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

def create_initial_genome(num_inputs, num_outputs, innov: InnovationTracker): input_nodes = [] output_nodes = [] connections = [] # Создаем входные узлы for i in range(num_inputs): node = NodeGene(i, «input», lambda x: x, 0) input_nodes.append(node) # Создаем выходные узлы for i in range(num_outputs): node_id = num_inputs + i # Начинаем идентификаторы с того места, где остановились в предыдущем цикле node = NodeGene(node_id, «output», sigmoid, random.uniform(-1, 1)) output_nodes.append(node) # Обновляем идентификатор узла innov-трекера innov.node_id_counter = num_inputs + num_outputs # Создаем соединения for i in range(num_inputs): for j in диапазон(число_выходов): in_node_id = i out_node_id = j + num_inputs innov_num = innov.get_connection_innovation(in_node_id, out_node_id) вес = случайный.uniform(-1, 1) conn = ConnectionGene(in_node_id, out_node_id, вес, innov_num, True) соединения.append(conn) все_узлы = входные_узлы + выходные_узлы вернуть геном(все_узлы, соединения) def create_initial_population(размер, num_inputs, num_outputs, innov): популяция = [] for _ в диапазоне(размер): геном = create_initial_genome(число_входов, num_outputs, innov) популяция.append(геном) вернуть популяцию

2. Оценить приспособленность популяции

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

1. Выражение фенотипа: Для каждого генома сначала необходимо выразить его в фенотипе (работающей нейронной сети). Это включает в себя построение самой нейронной сети на основе списков узлов и связей внутри генома.
2. Прямой проход: После построения сети мы выполняем прямой проход с заданными входными данными для получения выходных данных.
3. Расчёт приспособленности: Зная входные и выходные данные сети, мы можем рассчитать её приспособленность с помощью функции приспособленности. Функция приспособленности зависит от конкретной задачи и предназначена для возврата численного показателя, показывающего, насколько хорошо сеть достигла своей цели.

def topological_sort(edges): «»» Вспомогательная функция для сортировки узлов сети «»» visit = set() order = [] def visit(n): if n in visit: return visit.add(n) for m in edges[n]: visit(m) order.append(n) for node in edges: visit(node) return order[::-1] class Genome: … # Остальные методы будут здесь def estimate(self, input_values: list[float]): «»» Метод класса Genome. Выполняет выражение фенотипа и прямой проход «»» node_values = {} node_inputs = {n: [] for n in self.nodes} input_nodes = [n for n in self.nodes.values() if n.layer == «input»] output_nodes = [n for n in self.nodes.values() if n.layer == «output»] # Проверяет, что количество входных значений совпадает с количеством входные узлы if len(input_nodes) != len(input_values): raise ValueError(f»Количество входов не совпадает с количеством входных узлов. Input={len(input_nodes)}, num_in_val={len(input_values)}») # Назначить входные значения для node, val in zip(input_nodes, input_values): node_values[node.id] = val edges = {} for n in self.nodes.values(): edges[n] = [] for conn in self.connections: # Создавать включенные соединения только если conn.enabled: in_node = self.get_node(conn.in_node_id) out_node = self.get_node(conn.out_node_id) edges[in_node].append(out_node) node_inputs[conn.out_node_id].append(conn) sorted_nodes = topological_sort(edges) for node in sorted_nodes: if node.id in node_values: continue input = node_inputs[node.id] total_input = sum( node_values[c.in_node_id] * c.weight for c in input ) + node.bias node_values[node.id] = node.activation(total_input) return [node_values.get(n.id, 0) for n in output_nodes] def fitness_xor(genome): «»»Рассчитать приспособленность для задачи XOR»»» # Данные задачи XOR X = [[0, 0], [0, 1], [1, 0], [1, 1]] y = [0, 1, 1, 0] total_error = 0 for i in range(len(X)): try: output = genome.evaluate(X[i]) # print(f»Output: {output}») if output: error = abs(output[0] — y[i]) total_error += error else: error = y[i] total_error += error except Exception as e: print(f»Error: {e}») return 0 # Верните 0 fitness, если оценка не удалась fitness = 4 — total_error return max(0, fitness)

3. Видообразование

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

Процесс видообразования в каждом поколении включает в себя:

1. Измерение совместимости: Мы используем функцию расстояния совместимости для измерения степени различий двух геномов. Чем меньше расстояние между ними, тем больше сходства между ними. Следующая реализация кода использует формулу, предложенную в оригинальной статье, с предложенными параметрами.

def distance(genome1: Genome, genome2: Genome, c1=1.0, c2=1.0, c3=0.4): genes1 = {g.innov: g for g in genome1.connections} genes2 = {g.innov: g for g in genome2.connections} innovations1 = set(genes1.keys()) innovations2 = set(genes2.keys()) matching = innovations1 & innovations2 disjoint = (innovations1 ^ innovations2) excess = set() max_innov1 = max(innovations1) if innovations1 else 0 max_innov2 = max(innovations2) if innovations2 else 0 max_innov = min(max_innov1, max_innov2) # Отделить избыток от непересекающегося for innov in disjoint.copy(): if innov > max_innov: excess.add(innov) disjoint.remove(innov) # Разница в весе совпадающих генов, если совпадает: weight_diff = sum( abs(genes1[i].weight — genes2[i].weight) for i in matching ) avg_weight_diff = weight_diff / len(matching) else: avg_weight_diff = 0 # Нормализовать по NN = max(len(genome1.connections), len(genome2.connections)) if N < 20: # NEAT обычно использует 1, если N < 20 N = 1 delta = (c1 * len(excess)) / N + (c2 * len(disjoint)) / N + c3 * avg_weight_diff return delta

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

class Species: def __init__(self, represent: Genome): self.representative = represent self.members = [representative] self.adjusted_fitness = 0 self.best_fitness = -float('inf') self.stagnant_generations = 0 def add_member(self, genome: Genome): self.members.append(genome) def clear_members(self): self.members = [] def update_fitness_stats(self): if not self.members: self.adjusted_fitness = 0 return current_best_fitness = max(member.fitness for member in self.members) # Проверка на улучшение и обновление стагнации if current_best_fitness > self.best_fitness: self.best_fitness = current_best_fitness self.stagnant_generations = 0 else: self.stagnant_generations += 1 self.adjusted_fitness = sum(member.fitness for member in self.members) / len(self.members) class Speciator: def __init__(self, compatibility_threshold=3.0): self.species = [] self.compatibility_threshold = compatibility_threshold def speciate(self, population: list[Genome]): «»» Группировка геномов в виды на основе расстояния «»» # Очистка всех видов для нового поколения for s in self.species: s.clear_members() for genome in population: found_species = False for species in self.species: if distance(genome, species.representative) < self.compatibility_threshold: species.add_member(genome) found_species = True break if not found_species: new_species = Species(representative=genome) self.species.append(new_species) # Удалить пустые виды self.species = [s for s in self.species if s.members] # Пересчитать скорректированную приспособленность для видов в self.species: species.update_fitness_stats() # Обновить представителя, чтобы он стал лучшим членом species.representative = max(species.members, key=lambda g: g.fitness) def get_species(self): return self.species

4. Корректировка физической формы

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

Для корректировки приспособленности особи её приспособленность делится между количеством особей её вида. Этот механизм реализован в методе update_fitness_stats класса Species.

5. Размножение

После видоизменения и корректировки приспособленностей алгоритм переходит к фазе воспроизводства, где следующее поколение геномов создается посредством комбинации отбора, кроссинговера и мутации.

1. Отбор: В этой реализации отбор осуществляется посредством элитарности в основном эволюционном цикле.

2. Кроссовер: некоторые ключевые аспекты этой реализации:

• Наследование узлов: входные и выходные узлы явно передаются потомкам. Это делается для того, чтобы функциональность сети не нарушалась.
• Совпадение генов: если у обоих родителей есть ген с одинаковым числом инноваций, один из них выбирается случайным образом. Если ген был деактивирован у одного из родителей, вероятность того, что он будет деактивирован у потомства, составляет 75%.
• Избыточные гены: Избыточные гены от менее приспособленного родителя не наследуются.

def crossover(parent1: Genome, parent2: Genome) -> Genome: «»» Кроссовер, предполагающий, что parent1 является наиболее приспособленным родителем «»» offspring_connections = [] offspring_nodes = set() all_nodes = {} # Собрать все узлы от обоих родителей for node in parent1.nodes.values(): all_nodes[node.id] = node.copy() if node.layer in («input», «output»): offspring_nodes.add(all_nodes[node.id]) # Обеспечить включение входных и выходных узлов for node in parent2.nodes.values(): if node.id not in all_nodes: all_nodes[node.id] = node.copy() # Построить карты генов, отмеченных числом инноваций genes1 = {g.innov: g for g in parent1.connections} genes2 = {g.innov: g for g in parent2.connections} # Объединить все числа инноваций all_innovs = set(genes1.keys()) | set(genes2.keys()) for innov in sorted(all_innovs): gene1 = genes1.get(innov) gene2 = genes2.get(innov) if gene1 and gene2: # Соответствующие гены selected = random.choice([gene1, gene2]) gene_copy = selected.copy() if not gene1.enabled или not gene2.enabled: # 75% вероятность того, что ген потомка будет отключен if random.random() < 0.75: gene_copy.enabled = False elif gene1 and not gene2: # Непересекающийся ген (от наиболее приспособленного родителя) gene_copy = gene1.copy() else: # Не берем непересекающиеся гены от менее приспособленного родителя continue # получаем узлы in_node = all_nodes.get(gene_copy.in_node_id) out_node = all_nodes.get(gene_copy.out_node_id) если in_node и out_node: offspring_connections.append(gene_copy) offspring_nodes.add(in_node) offspring_nodes.add(out_node) offspring_nodes = list(offspring_nodes) # Удалить дубликаты return Genome(offspring_nodes, offspring_connections)

3. Мутация: После кроссинговера к потомству применяется мутация. Ключевым аспектом этой реализации является то, что мы избегаем образования циклов при добавлении связей.

class Genome: … # Остальные методы будут здесь def _path_exists(self, start_node_id, end_node_id, checked_nodes=None): «»» Рекурсивная функция для проверки существования точки доступа между двумя узлами.»»» if checked_nodes is None: checked_nodes = set() if start_node_id == end_node_id: return True checked_nodes.add(start_node_id) for conn in self.connections: if conn.enabled and conn.in_node_id == start_node_id: if conn.out_node_id not in checked_nodes: if self._path_exists(conn.out_node_id, end_node_id, checked_nodes): return True return False def get_node(self, node_id): return self.nodes.get(node_id, None) def mutate_add_connection(self, innov: InnovationTracker): node_list = list(self.nodes.values()) # Попробуйте максимум 10 раз max_tries = 10 found_appropiate_nodes = False for _ in range(max_tries): node1, node2 = random.sample(node_list, 2) if (node1.layer == «output» or (node1.layer == «hid» and node2.layer == «input»)): node1, node2 = node2, node1 # Поменяйте их местами # Проверяем, не создается ли цикл с тем же узлом if node1 == node2: continue # Проверяем, не создается ли соединение между двумя узлами на одном слое if node1.layer == node2.layer: continue if node1.layer == «output» or node2.layer == «input»: continue # Проверяем, существует ли уже соединение conn_exists=False for c in self.connections: if (c.in_node_id == node1.id и c.out_node_id == node2.id) или (c.in_node_id == node2.id и c.out_node_id == node1.id): conn_exists = True break if conn_exists: continue # Если есть путь от node2 до node1, то добавление соединения от node1 к node2 создает цикл if self._path_exists(node2.id, node1.id): continue innov_num = innov.get_connection_innovation(node1.id, node2.id) new_conn = ConnectionGene(node1.id, node2.id, random.uniform(-1, 1), innov_num, True) self.connections.append(new_conn) return def mutate_add_node(self, innov: InnovationTracker): enabled_conn = [c for c in self.connections if c.enabled] если не enabled_conn: return connection = random.choice(enabled_conn) # выбрать случайное включенное соединение connection.enabled = False # Отключить соединение node_id, conn1_innov, conn2_innov = innov.get_node_innovation(connection.innov) # Создать узел и соединения new_node = NodeGene(node_id, «hid», ReLU, random.uniform(-1,1)) conn1 = ConnectionGene(connection.in_node_id, node_id, 1, conn1_innov, True) conn2 = ConnectionGene(node_id, connection.out_node_id, connection.weight, conn2_innov, True) self.nodes[node_id] = new_node self.connections.extend([conn1, conn2]) def mutate_weights(self, rate=0.8, мощность = 0,5): для conn в self.connections: если random.random() < скорость: если random.random() < 0,1: conn.weight = random.uniform(-1, 1) иначе: conn.weight += random.gauss(0, мощность) conn.weight = max(-5, min(5, conn.weight)) # Фиксированные веса def mutate_bias(self, скорость = 0,7, мощность = 0,5): для node в self.nodes.values(): если node.layer != "input" и random.random() < скорость: если random.random() < 0,1: node.bias = random.uniform(-1, 1) иначе: node.bias += random.gauss(0, мощность) node.bias = max(-5, min(5, node.bias)) def mutate(self, innov, conn_mutation_rate=0,05, node_mutation_rate=0.03, weight_mutation_rate=0.8, bias_mutation_rate=0.7): self.mutate_weights(weight_mutation_rate) self.mutate_bias(bias_mutation_rate) если random.random() < conn_mutation_rate: self.mutate_add_connection(innov) если random.random() < node_mutation_rate: self.mutate_add_node(innov)

6. Повторение процесса в пределах основного эволюционного цикла

После того, как всё потомство будет рождено и новая популяция сформирована, текущее поколение завершается, и новая популяция становится отправной точкой для следующего эволюционного цикла. Этим занимается главный эволюционный цикл, который координирует весь алгоритм.

def evolution(population, fitness_scores, speciator: Speciator, innov: InnovationTracker, stagnation_limit: int = 15): new_population = [] # Назначить приспособленность геномам for genome, fitness in zip(population, fitness_scores): genome.fitness = fitness # Видовая популяция speciator.speciate(population) species_list = speciator.get_species() species_list.sort(key=lambda s: s.best_fitness, reverse=True) # Сортировать виды по best_fitness print(f»Species created: {len(species_list)}») # Удалить застойные виды surviving_species = [] if species_list: surviving_species.append(species_list[0]) # Оставить лучший вид независимо от застоя for s in species_list[1:]: if s.stagnant_generations < stagnation_limit: surviving_species.append(s) species_list = surviving_species print(f"Выжившие виды: {len(species_list)}") total_adjusted_fitness = sum(s.adjusted_fitness for s in species_list) print(f"Общая скорректированная приспособленность: {total_adjusted_fitness}") # элитарность для видов из species_list: if species.members: best_genome = max(species.members, key=lambda g: g.fitness) new_population.append(best_genome) remain_offspring = len(population) - len(new_population) # Распределяем оставшееся потомство для видов из species_list: if total_adjusted_fitness > 0: offspring_count = int((species.adjusted_fitness / total_adjusted_fitness) * remaining_offspring) # Более приспособленный вид будет иметь больше потомков else: offspring_count = remaining_offspring // len(species_list) # Если все виды показали себя плохо, распределить потомков поровну if offspring_count > 0: offspring = produce_species(species, offspring_count, innov) new_population.extend(offspring) # Гарантируем, что особей достаточно (из-за ошибки округления их может быть меньше) while len(new_population) < len(population): best_species = max(species_list, key=lambda s: s.adjusted_fitness) offspring = produce_species(best_species, 1, innov) new_population.extend(offspring) return new_population

7. Запуск алгоритма

def run_neat_xor(save_best=False, generations=50, pop_size=50, target_fitness=3.9, speciator_threshold=2.0): NUM_INPUTS = 2 NUM_OUTPUTS = 1 # Инициализируем количество инноваций и Speciator innov = InnovationTracker() speciator = Speciator(speciator_threshold) # Создаем начальную популяцию population = create_initial_population(pop_size, NUM_INPUTS, NUM_OUTPUTS, innov) # Статистика best_fitness_history = [] avg_fitness_history = [] species_count_history = [] # основной цикл for gen in range(generations): fitness_scores = [fitness_xor(g) for g in population] print(f»fitness: {fitness_scores}») # получаем статистику best_fitness = max(fitness_scores) avg_fitness = sum(fitness_scores) / len(fitness_scores) best_fitness_history.append(best_fitness) avg_fitness_history.append(avg_fitness) print(f»Поколение {gen}: Best={best_fitness}, Avg={avg_fitness}») # Проверяем, достигли ли мы целевой приспособленности if best_fitness >= target_fitness: print(f»Проблема была решена за {gen} поколений») print(f»Лучшая достигнутая приспособленность: {max(best_fitness_history)}») best_genome = population[fitness_scores.index(best_fitness)] if save_best: with open(«best_genome.pkl», «wb») as f: pickle.dump(best_genome, f) return best_genome, best_fitness_history, avg_fitness_history, species_count_history population = evolution(population, fitness_scores, speciator, innov) print(f»Не удалось решить задачу XOR за {generations} поколений») print(f»Наилучшая достигнутая приспособленность: {max(best_fitness_history)}») return None, best_fitness_history, avg_fitness_history, species_count_history

Полный код

Код Github

Источник: towardsdatascience.com