Как сделать свой генетический алгоритм более эффективным?

Question

Я создал игру (в основном клон Agar.io), где игрок-человек помещается против контролируемых AI ботов, работающих на генетическом алгоритме и нейронных сетях.

Проблема в том, что я считаю, что мой алгоритм неэффективен. У меня 10 ботов, оцененных по их фитнес-функции, и это время выжило. Их ген состоит из действительных чисел между -1 и 1.

От самого низкого до самого высокого уровня я беру n ботов до 5 ботов и беру текущее значение веса и добавляю его по гауссовскому числу, умноженному на (10^-n). У меня возникли проблемы с выполнением кроссовера с номерами с плавающей запятой, таким образом, я сделал такую ​​мутацию, как это.

Очевидно, что мой ИИ не очень умен.

Как я мог улучшить свой алгоритм?

Вот где большая часть исходного кода заключается в случае необходимости: https://github.com/jadenyjw/evo/blob/master/core/src/com/evo/game/stages/GameStage.java

Answer 1

Agar.io сравним с другими искусственного интеллекта соревнований, как Марио AI. Проблема заключается в том, что разрешено много разных проблем, и что для новичков очень легко реализовать нейроэволюцию, генетическое программирование и обучение маше. К сожалению, невозможно увеличить масштаб этих ботов до более умных, чем определенный уровень. Это потому, что само генетическое программирование - неправильный путь. Лучшее решение - Scripting AI, которое не только масштабируется до любого уровня интеллекта, но также использует меньшую мощность процессора как так называемый «эволюционный AI».

Позволяет глубже изучить исходный код. В соответствии с операциями импорта в начале использовалась «Encog Framework». Это известная библиотека машинного обучения, которая поддерживает GPU Computing и похожа на pybrain. Даже с лучшим параметрированием Encog никогда не сможет с нуля сгенерировать агента, который готов выиграть у человека. Но это хороший способ понять, что такой алгоритм оптимизации не подходит для реальных проблем.

Answer 2

Имея векторы реальных номеров, вы можете попробовать Differential Evolution.

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

В отличие от вашего подхода DE обменивается информацией между решениями и поэтому может работать лучше.

Последнее, но не менее важное: переход от вашего подхода к DE относительно прост: вам нужно только закодировать конкретный оператор мутации/кроссовера.

Answer 3

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

Например, с n генов:

For i from 0 to n-1 
    r = random interger number 
    If(r modulo 2 == 0) 
    gene[i] of new bot = gene[i] of bot number 1 
    Else 
    gene[i] of new bot = gene[i] of bot number 2 
    EndIf 
EndFor 

Вы можете также «крест» сами гены путем вычисления среднего значения из двух действительных чисел:

gene[i] of new bot = ((gene[i] of bot 1) + (gene[i] of bot 2))/2 

Население может быть слишком маленький, может быть, вы получите лучшие результаты с населением в 100 ботов и более, вместо 10. Но, возможно, ваша игра не позволяет этого, и поэтому вам, вероятно, понадобится запустить генетический алгоритм для большего количества поколений ботов.

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

Некоторые алгоритмы имеют переменную скорость мутации, контролируемую геном, который также может мутировать. Таким образом, вы можете протестировать его, введя 2 гена, которые контролируют скорость мутации для небольших и огромных мутаций. Но я не знаю, может ли он иметь эффективные результаты для небольших групп населения.

О нейронной сети вы можете протестировать другие макеты, потому что может быть слишком много или недостаточно нейронов для эффективного управления ботами. Это та же проблема о количестве скрытых слоев.