Генетический алгоритм своими руками

Генетический алгоритм — способ оптимизации, какой-либо функции. Но, в нашем случае, мне просто был интересен принцип его работы, своеобразное моделирование эволюции. Ну и чтобы проэволюционировать самому. Мы имеем абстрактное поле, в котором есть организмы (синие и бирюзовые клетки), еда (зеленые) и яд (красные).

У созданий всего 64 гена, но можно ввести всего лишь 10 первых.

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

У создания 8 положений головы, ее положение учитывается при выполнении команд.

Команды [0, 7] — направление ходьбы.
Команды [8, 15] — направление поворота.
Команды [16, 23] — направление осмотра, если видит яд/еду, то ест.
Команды [24, 31] – безопасный осмотр, если видит яд — перерабатывает в еду и ест, если видит еду, то ест.
Команды [32, 39] — направление безопасной ходьбы (если впереди стена или другое создание, то меняет направление).

Выполнение команд происходит в цикле, у которого максимальное кол-во итераций – 10.
Команды ходьбы – завершающие. Если существо выполнило команду восемь, то к итератору выполнения команды прибавляется восьмерка, и он увеличивается на единицу. Это сделано для большего рандома.

Все есть примитив

Поле состоит из примитивов и, по сути, является матрицей из объектов базового класса, который имеет один из типов Type. Примитив это базовый класс, от которого наследуется класс CreationC.

enum Type { Void, Food, Poison, Wall, Crt };  // Типы клеток поля

Реализация объектов:

class Prim
{
protected:
    Type _type;
    int _x; //Координаты клеток
    int _y;
    int _healthPointChange; // Размер отнятия/прибавления жизней при взаимодействии с клеткой
    Color _color; //цвет клетки

public:
    Type GetType();
    void SetType(Type);
    int GetX();
    int GetY();
    void SetX(int);
    void SetY(int);
    Prim();
    Prim(Type);
    ~Prim();
    int getHPC();
    void setHPC(int);
    Color& getColor();   
    void setColor(float, float, float);
}; 

Реализация существ:

class CreationC : public Prim
{
    enum direction { lU, up, uR, right, rD, dowm, dL, left }; // Варианты положения головы

    AreaCLA* _world; // Указатель на объект, которому принадлежит существо
    direction _head; // Положение головы
    short int _hp; 
    vector<UNI> _commandList; //  Массив команд
    UNI _itForCommand;  // Номер команды которая будет выполняться 
    Prim*** _area; //Указатель на поле

    boost::signal <void()> _eatingFood;//Событие поедания еды
    boost::signal <void()> _eatingPoison;//Событие поедания яда
    //.......................................   
    void _Step(UNI); //Функция ходьбы
    bool _See(UNI); //Функция проверки заполненности клетки
    void _Roll(UNI); //Функция поворота бота
    void _AddSlots();//Функция привязки функций поля к событиям
    void _Eat(UNI); //Функция поедания
    bool _isNextCellClose(UNI); //Функция проверки клетки на проходимость
public:
    void Mutation();//Функция, меняющая рандомный ген на другой рандомный ген
    bool IsAlive();//Функция проверки на жизнеспособность
    void Execute();//Функция, которая бьет существо и заставляет работать 
    short int GetHP();
    CreationC(vector<UNI>& gens, AreaCLA*, int x, int y);
    CreationC();
    vector<UNI>& GetCommandList();
    ~CreationC();
};

Количество существ зависит от размера поля, изначально, допустим есть N ботов, из которых в живых останется N/8. Мутирует N/32, для большего разнообразие (мутанты — бирюзовые).

class AreaCLA
{
    Prim*** _map;
    int _heigh; //Высота поля
    int _width;//Ширина поля
    UNI _countOfFood; //Количество еды на поле
    UNI _countOfPoison;// Количество яда на поле
    UNI _FPCount;//Максимальное количество еды и яда

    CreationC** _crtns; //Массив существ
    int _crtnsCount; //Количество существ на поле
    int _maxCrtnsCount;
    int _minCrtnsCount; 
    void _cicle(); //Цикл работы ботов
    void _refresh(); // Функция обновляющая кол-во еды и яда
    void _Reborn(); //Функция возрождения ботов
    void _delCrt(int, int, int);  //Функция погребения падших
public: 
    AreaCLA()
    ~AreaCLA();
    void SetFood(COORD coord);
    void SetPoison(COORD coord);
    void SetWall(COORD coord);
    void SetVoid(COORD coord);
    void Start(); //Функция запуска симуляции

    void minFood(); //Функция уменьшающая кол-во еды
    void minPoison();//Функция уменьшающая кол-во яда
};
void AreaCLA::_cicle()
{
        for (int i = 0; i < _crtnsCount; i++)
        {
            if (!_crtns[i]) continue;
                _crtns[i]->Execute(); // Выполнение команд существом
            if (_crtns[i]->IsAlive() == 0) //Если бот был слишком слаб происходит вынос трупа
                delCrt(i, _crtns[i]->GetX(), _crtns[i]->GetY()); // <-вот тут
            if (_crtnsCount == this->_minCrtnsCount)// Если количество выживших достигло минимума происходит прерывание.
                return;

            if (_countOfCtrnsChenged)
            {
                i--;
                _countOfCtrnsChenged = 0;
                continue;
            }
        }
}

Заключение

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

Кому интересно – прикрепляю ссылку на гитхаб. Последняя версия: Evolution 1.0.

Автор: Hrodvitnir

Источник