В предыдущей части статьи: https://medium.com/@eugenesh4work/building-a-basic-neuroevolution-self-evolving-neural-network-solution-a-comprehensive-guide-456602cc013a , мы исследовали алгоритм Нейроэволюция расширяющих топологий (NEAT), мощный подход к развитию нейронных сетей с адаптируемыми топологиями. NEAT предлагает многочисленные преимущества по сравнению с традиционными сетями с фиксированной топологией, позволяя находить инновационные и эффективные решения сложных проблем. В качестве практической демонстрации возможностей алгоритма NEAT мы рассмотрим классическую задачу XOR, которая уже давно является эталоном для оценки производительности нейронных сетей.
Задача XOR — это простая, но нелинейно разделимая задача, проверяющая способность нейронной сети к обучению и обобщению. В этой статье мы покажем вам процесс создания полного рабочего кода примера очень простого алгоритма NEAT, решающего проблему XOR. Эта статья предоставит вам прочную основу для применения алгоритма NEAT для решения широкого круга задач: от реализации необходимых компонентов до настройки алгоритма и оценки его производительности.
К концу этой статьи вы получите полное представление о том, как реализовать алгоритм NEAT, который может развиваться и адаптироваться для решения проблемы XOR. Кроме того, вы получите представление о потенциале алгоритма для решения более сложных задач, подчеркнув мощь и гибкость подхода NEAT в эволюции нейронных сетей.
Определение проблемы и желаемого результата
Задача XOR (исключающее ИЛИ) — это задача двоичной классификации, цель которой состоит в том, чтобы правильно предсказать выходные данные функции XOR с учетом двух двоичных входных данных. Функция XOR определяется следующим образом:
- Исключающее ИЛИ(0, 0) = 0
- Исключающее ИЛИ(0, 1) = 1
- Исключающее ИЛИ(1, 0) = 1
- Исключающее ИЛИ(1, 1) = 0
Желаемый результат нашей нейронной сети NEAT должен быть правильным значением функции XOR для каждой возможной входной пары. Другими словами, нейронная сеть должна иметь возможность обобщать и точно определять значение XOR для любой заданной комбинации двоичных входов.
Проблема XOR особенно сложна для линейных классификаторов, поскольку она не является линейно разделимой. Это означает, что нельзя провести прямую линию, чтобы отделить входы, которые производят выход 0, от тех, которые производят выход 1. Следовательно, задача XOR требует, чтобы нейронная сеть изучала нелинейные границы принятия решений, что делает ее идеальным испытательным стендом для оценки способности алгоритма NEAT развивать сложные и адаптируемые топологии нейронных сетей.
В этой статье мы разработаем нейронную сеть NEAT для решения проблемы XOR, реализовав следующие компоненты:
- Инициализация популяции. Мы создадим первоначальную популяцию нейронных сетей с различными топологиями, которые можно будет развивать с течением времени.
- Оценка производительности. Мы будем оценивать производительность каждого человека в популяции, сравнивая его прогнозируемые результаты XOR с правильными результатами.
- Выбор наиболее приспособленных особей. Мы выберем наиболее эффективные нейронные сети для производства потомства для следующего поколения, гарантируя, что наиболее приспособленные особи будут иметь более высокую вероятность передачи своего генетического материала.
- Применение генетических операторов. Мы будем использовать операции мутации и скрещивания для создания потомков с новыми и разнообразными топологиями, что позволит популяции исследовать широкий спектр потенциальных решений.
- Повторение процесса. Мы продолжим выполнять описанные выше шаги до тех пор, пока не найдем нейронную сеть, которая точно решает задачу XOR, или пока не будет достигнут заранее определенный критерий остановки.
Реализуя эти компоненты, мы продемонстрируем, как алгоритм NEAT можно применять для развития нейронных сетей, способных решать проблему XOR, подчеркивая потенциал алгоритма для решения более сложных задач и создания инновационных решений.
Реализация компонентов NEAT
В этом разделе я предоставлю подробное описание реализации ключевых компонентов алгоритма NEAT для решения проблемы XOR. Для наших примеров кода мы будем использовать Javascript, но эти концепции можно легко перевести на другие языки программирования.
Для начала давайте возьмем простую нейронную сеть прямого распространения, аналогичную той, которую я использовал в статье https://medium.com/@eugenesh4work/from-inputs-to-outputs-understanding-the- внутренняя работа нейронной сети-8a5fc25c7388, а затем применить к ней алгоритм NEAT.
Вот исходный код:
class Node {
id
value = 0.0
type
constructor(id, type) {
this.id = id
this.type = type
}
sigmoid(x) {
return 1 / (1 + Math.exp(-x))
}
compute(incoming) {
if (this.type === 'input') return this.value
const sum = incoming.reduce((sum, connection) => {
return sum + connection.weight * connection.from.value
} , 0)
this.value = sum
return this.sigmoid(this.value)
}
}
class Connection {
from
to
weight
enabled = true
constructor(from, to, weight) {
this.from = from
this.to = to
this.weight = weight
}
}
class Genome {
nodes = []
connections = []
forward(inputs) {
this.inputNodes.forEach((node, i) => {
node.value = inputs[i]
})
this.nodes.forEach(node => {
const incoming = this.connections.filter(connection => connection.enabled && connection.to === node)
node.compute(incoming)
})
return this.outputNodes.map(node => node.value)
}
get inputNodes() {
return this.nodes.filter(node => node.type === 'input')
}
get outputNodes() {
return this.nodes.filter(node => node.type === 'output')
}
addNode = (nodeType) => {
const nodeId = this.nodes.length
const newNode = new Node(nodeId, nodeType)
this.nodes.push(newNode)
return newNode
}
addConnection(from, to, weight) {
const newConnection = new Connection(from, to, weight)
this.connections.push(newConnection)
return newConnection
}
getRandomNode() {
return this.nodes[Math.floor(Math.random() * this.nodes.length)]
}
getRandomConnection() {
return this.connections[Math.floor(Math.random() * this.connections.length)]
}
}
Этот код содержит 3 класса: Node (нейрон), Connection и Genome (нейронная сеть). Сеть поддерживает только один скрытый слой и использует функцию активации Sigmoid для выходных узлов. Он может распространять входные значения по сети для получения выходных значений, но ему не хватает алгоритма обучения для корректировки весов во время обучения. Вместо обучения мы попытаемся расставить приоритеты в использовании генетического алгоритма для развития сети, чтобы она могла решать XOR, и для этого нам нужно иметь свойство пригодности в классе Network.
Давайте добавим часть алгоритма NEAT:
NEAT (Нейроэволюция расширяющих топологий) – это эволюционный алгоритм, который вводит несколько типов мутаций, кроссинговер и отбор для развития нейронных сетей путем оптимизации их топологии и весов соединений.
Давайте реализуем класс NEAT, содержащий несколько свойств и методов для управления эволюцией популяции нейронных сетей (геномов):
class NEAT {
populationSize = 1
population = []
generation = 0
mutateWeightChance = 0.8
newConnectionChance = 0.05
newNodeChance = 0.03
constructor({populationSize}) {
this.populationSize = populationSize
// Initialize initial population
Array.from({length: populationSize}).forEach(() => {
this.population.push(createInitialGenome())
})
}
// other methods are here .... I've described them below.
}
- populationSize: указывает количество геномов в популяции.
- population: массив для хранения геномов.
- поколение: отслеживает текущее поколение.
- mutateWeightChance: вероятность изменения веса соединения.
- newConnectionChance: вероятность добавления нового соединения.
- newNodeChance: вероятность добавления нового узла.
Следующий метод мутации. Основными типами мутаций NEAT являются:
- Мутация веса. Эта мутация изменяет веса существующих соединений в сети. Он может включать небольшие изменения весов или полную замену новым случайным значением.
- Добавить мутацию соединения. Эта мутация добавляет новое соединение между двумя ранее не соединенными узлами. Новому соединению присваивается случайный вес.
- Добавить мутацию узла. Эта мутация добавляет в сеть новый скрытый узел путем разделения существующего соединения. Исходное соединение отключается, и создаются два новых соединения: одно от исходного узла к новому узлу, а другое от нового узла к узлу назначения. Каждому из новых соединений присваивается начальный вес.
- Включить/отключить мутацию соединения. Эта мутация переключает состояние соединения (т. е. включает ранее отключенное соединение или отключает активное соединение). Отключение соединения означает, что оно не будет способствовать активации целевого узла.
Эти типы мутаций позволяют NEAT исследовать различные топологии сети и веса соединений в ходе эволюционного процесса, ища оптимальную конфигурацию для решения заданной проблемы.
mutate(genome) {
if (Math.random() < this.mutateWeightChance) {
const connection = genome.getRandomConnection()
connection.weight += getRandomBetween(-0.5, 0.5)
}
if (Math.random() < this.newConnectionChance) {
const node1 = genome.getRandomNode()
const node2 = genome.getRandomNode()
if (node1.type !== node2.type) {
genome.addConnection(node1, node2, getRandomBetween(-1, 1))
}
}
if (Math.random() < this.newNodeChance) {
const connection = genome.getRandomConnection()
connection.enabled = false
const middleNode = genome.addNode('hidden')
genome.addConnection(connection.from, middleNode, 1)
genome.addConnection(middleNode, connection.to, connection.weight)
}
}
Код использует Math.random() вместе с предопределенными шансами (mutateWeightChance, newConnectionChance, newNodeChance), чтобы определить, произойдет ли каждый тип мутации. Это вводит элемент случайности, необходимый в эволюционных алгоритмах.
Поняв, как работают мутации, вы сможете лучше понять генетические и эволюционные принципы, лежащие в основе алгоритма NEAT.
Следующая часть — кроссовер. Давайте реализуем метод reproduce, который будет выполнять скрещивание, а затем применять мутацию к потомку.
reproduce(parent) {
// Select two genomes
// Crossover
// Mutate
const offspring = new Genome()
parent.nodes.forEach(node => {
offspring.addNode(node.type)
})
parent.connections.forEach(connection => {
offspring.addConnection(offspring.nodes[connection.from.id], offspring.nodes[connection.to.id], connection.weight)
})
this.mutate(offspring)
return offspring
}
Метод reproduce является неотъемлемой частью алгоритма NEAT (NeuroEvolution of Augmenting Topologies), поскольку он отвечает за создание новых геномов (нейронных сетей) на основе существующих. Это гарантирует, что черты, которые оказались полезными, могут быть переданы последующим поколениям с некоторой случайностью, вносимой посредством мутаций. Метод reproduce выполняет следующее:
- В качестве аргумента он принимает родительский геном.
- Он клонирует родительский геном, чтобы создать потомство.
- Он применяет случайные мутации к потомству.
- Он возвращает мутировавшее потомство, которое затем станет частью следующего поколения.
Этот метод служит краеугольным камнем эволюционного процесса, обеспечивая постоянное производство новых геномов, внося разнообразие, но также сохраняя хорошие черты для улучшения популяции с течением времени.
Чтобы сделать выборку лучших геномов, нам нужна фитнес-функция. Давайте реализуем это.
computeFitness(genome) {
// XOR cases
const cases = [
{ inputs: [0, 0], expected: [0] },
{ inputs: [0, 1], expected: [1] },
{ inputs: [1, 0], expected: [1] },
{ inputs: [1, 1], expected: [0] }
];
const totalError = cases.reduce((acc, testCase) => {
const inputs = testCase.inputs;
const expected = testCase.expected;
const output = genome.forward(inputs);
return acc + output.reduce((error, value, index) => {
return error + Math.pow(value - expected[index], 2);
}, 0);
}, 0.0);
// Fitness is inverse of error
return 1 / (1 + totalError);
}
В машинном обучении и эволюционных алгоритмах, таких как NEAT (Нейроэволюция расширяющих топологий), приспособленность — это мера того, насколько хорошо модель (в данном случае геном или нейронная сеть) выполняет конкретную задачу. Метод computeFitness предназначен для оценки эффективности генома для решения поставленной задачи. Чего достигает этот метод?
- Оценка эффективности: метод
computeFitnessобеспечивает количественную оценку того, насколько хорошо геном выполняет задачу операции XOR. - Направляя эволюцию: значение приспособленности используется позже в методе
evolveдля выбора геномов для воспроизводства, гарантируя, что геномы, которые работают лучше, имеют более высокие шансы быть выбранными. - Минимизация ошибок: метод направлен на поиск генома, который минимизирует общую ошибку во всех тестовых случаях, по сути пытаясь решить проблему XOR как можно точнее.
Понимание того, как работает метод computeFitness, дает вам представление о том, как оцениваются геномы, и, таким образом, имеет решающее значение для понимания работы эволюционных алгоритмов, таких как NEAT.
Наконец, разработайте метод:
evolve() {
console.log('Evolving...')
// Compute fitness for each genome
const fitnesses = this.population.map(genome => this.computeFitness(genome))
const totalFitness = fitnesses.reduce((acc, fitness) => acc + fitness, 0)
console.log(`Total fitness: ${totalFitness}`)
// Select genomes based on their fitness
const newPopulation = []
while (newPopulation.length < this.populationSize) {
// Roulette wheel selection
const pick = Math.random() * totalFitness;
let current = 0;
for (let i = 0; i < this.population.length; i++) {
const genome = this.population[i];
current += fitnesses[i];
if (current > pick) {
const offspring = this.reproduce(genome);
newPopulation.push(offspring);
break;
}
}
}
this.population = newPopulation;
this.generation++;
}
Метод evolve в алгоритме NEAT (Нейроэволюция расширяющих топологий) служит организатором эволюционного процесса для популяции нейронных сетей (геномов). Он отвечает за три основных действия: оценку текущей популяции, отбор геномов на основе их приспособленности и создание новой популяции посредством воспроизводства и мутации.
Ключевые шаги:
- Вычисление приспособленности: оно начинается с расчета приспособленности каждого генома в текущей популяции с использованием метода
computeFitness. Эти оценки пригодности служат основой для процесса отбора. - Расчет общей приспособленности: затем суммируются индивидуальные показатели приспособленности, чтобы получить общую приспособленность населения. Эта общая приспособленность используется для взвешенного отбора геномов для воспроизводства.
- Отбор и воспроизводство генома. Используя такой метод, как выбор колеса рулетки, геномы выбираются на основе их показателей приспособленности. Затем выбранные геномы воспроизводятся для создания потомства с использованием метода
reproduce. - Обновление популяции: новое потомство заменяет старую популяцию, а количество поколений увеличивается.
- Ведение журнала: для наглядности метод регистрирует такие детали, как общая приспособленность и текущая стадия эволюции.
Проходя циклически через эти этапы, метод evolve помогает продвигать эволюционный процесс вперед, стремясь генерировать все более подходящие геномы на протяжении нескольких поколений.
Есть также вспомогательная функция, которую я использовал:
function getRandomBetween(min, max) {
return Math.random() * (max - min) + min;
}
function createInitialGenome() {
const genome = new Genome()
const input1 = genome.addNode('input')
const input2 = genome.addNode('input')
const output = genome.addNode('output')
genome.addConnection(input1, output, getRandomBetween(-1, 1))
genome.addConnection(input2, output, getRandomBetween(-1, 1))
return genome
}
Теперь мы можем запустить наше простое решение NEAT:
function findBest(populationSize, maxGenerations) {
console.log('Finding best genome...')
const neat = new NEAT({populationSize})
const targetFitness = 0.99
let bestGenome
let bestFitness = 0.0
neat.generation = 0
for (let i = 0; i < maxGenerations; i++) {
console.log(`Generation ${neat.generation}`);
neat.evolve();
// Check the best genome in current generation
let fitnesses = neat.population.map(genome => neat.computeFitness(genome));
let currentBestFitness = Math.max(...fitnesses);
let bestGenomeIdx = fitnesses.indexOf(currentBestFitness);
if (currentBestFitness > bestFitness) {
bestFitness = currentBestFitness;
bestGenome = neat.population[bestGenomeIdx];
}
// Break if target fitness achieved
if (bestFitness >= targetFitness) {
break;
}
}
return bestGenome
}
const bestGenome = findBest(100, 100)
console.log('Best genome found: ', bestGenome)
const testCases = [
{inputs: [0, 0], expected: [0]},
{inputs: [0, 1], expected: [1]},
{inputs: [1, 0], expected: [1]},
{inputs: [1, 1], expected: [0]}
];
const predictions = testCases.map(testCase => {
return {
inputs: testCase.inputs,
prediction: bestGenome.forward(testCase.inputs)
};
});
console.log(predictions);
/* [
{ inputs: [ 0, 0 ], prediction: [ -0.03263881966621418 ] },
{ inputs: [ 0, 1 ], prediction: [ 0.9900228300086165 ] },
{ inputs: [ 1, 0 ], prediction: [ 0.9141289991639834 ] },
{ inputs: [ 1, 1 ], prediction: [ 0.03070735406843328 ] }
] */
Заключение
В этой статье мы рассмотрели реализацию алгоритма NEAT для решения проблемы XOR. Мы определили проблему, реализовали основные компоненты NEAT и создали эволюционный цикл для развития наших нейронных сетей с течением времени. Красота алгоритма NEAT заключается в его гибкости и способности адаптироваться, что делает его отличным выбором для различных сложных задач, помимо задачи XOR. Поняв принципы и реализовав их, как мы показали, теперь вы можете применять NEAT для решения других сложных проблем, с которыми вы можете столкнуться.
В следующих частях я постараюсь показать и объяснить более продвинутые методы генетических алгоритмов и нейронных сетей, такие как видообразование, сложные мутации, лучшее генетическое кодирование и т. д.
Полный код можно найти по адресу: https://gist.github.com/esshka/ff3374f755fea014b51b3d9757f41435
