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

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


image


У созданий всего 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()) //Если бот был слишком слаб происходит вынос трупа
                delCrt(i, _crtns[i]->GetX(), _crtns[i]->GetY()); // <-вот тут
            if (_crtnsCount == this->_minCrtnsCount)// Если количество выживших достигло минимума происходит прерывание.
                return;

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

Заключение


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


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

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 17

    +10
    Хочется отметить, что реализованное здесь не является генетическим алгоритмом.
    Одна из ключевых особенностей именно генетических алгоритмов заключается не просто в случайных мутациях, а в порождении потомства как комбинации (с мутацией) генов наиболее жизнеспособных родителей.
    Именно благодаря получающемуся накоплению помогающих выживать генов и обеспечивается хорошая сходимость.
      +1
      Спасибо за замечание.
      Учту и, возможно, перепилю. Больно тема зацепила.
        +1
        Комбинация генов является хорошим бонусом, но не является необходимым условием, чтобы называться генетическим. Различные живые микроорганизмы успешно так мутируют пользуясь исключительно делением или почкованием, давая нам каждый год новые волны различных эпидемий.
        +2
        более подробное описание алгоритма https://www.youtube.com/watch?v=SfEZSyvbj2w
          +8
          У тебя очень своеброзный контроль версий как для пользователя github
            –2
            Первый репозиторий + рваный режим.
            Да и изначально не планировал, что люди увидят.
              –1
              Наверно, шутка было о схожести с этим:
              image
            0
            Я лет 10 или 12 назад, на серверах LineAge собственных ботов запускал и смотрел как ни выживают в зависимости от алгоритмов.
            Если бы тогда имел представление о генетических алгоритмах, возможно боевку можно было еще веселее сделать.

            зы
            правда на живых серверах лучше всего показали себя торговые группы, которые скупали, продавали и крафтили все подряд с плавающими ценами в зависимости от кол-ва товара на «складе».
              +7
              if (_crtns[i]->IsAlive() == 0)

              Предупреждене другим студентам: этот проект не является эталоном хорошего кода.

                0

                Можешь пояснить, что не эталонного?

                  0

                  Сравнивать bool с int как-то странно. Почему не false хотя бы? А вообще следовало бы написать


                  if (!_crtns[i]->IsAlive())

                  Собственно, я уже вижу, что автор это именно так и исправил.

                +2
                Близкое по теме видео
                Cимуляция эволюции

                • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Эх… Были времена, я тоже этим баловался…
                  https://habrahabr.ru/post/156085/
                  https://habrahabr.ru/post/156435/
                    0
                    Надо глянуть, а то в институте был предмет, но лабораторок по нему не было. Так и осталась теория без практики.
                    –2
                    хотел сам собрать, но компилятор (code block в Win10) ругается
                    Prim.h|7|fatal error: boost\signal.hpp: No such file or directory|
                    

                    предварительно выкачал boost, создал папку boost в проекте и положил туда signal.hpp и bind.hpp, добавил их в проект
                      0
                      А кто будет библиотеки компилировать? И складывать надо не два файла, а все.
                      Если эти файлы откроете, то увидите, что у них много зависимостей.

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

                    Самое читаемое