[Из песочницы] Генетический алгоритм своими руками09.12.2016 21:04

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


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 _commandList; //  Массив команд
    UNI _itForCommand;  // Номер команды которая будет выполняться 
    Prim*** _area; //Указатель на поле

    boost::signal  _eatingFood;//Событие поедания еды
    boost::signal  _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& gens, AreaCLA*, int x, int y);
    CreationC();
    vector& 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.

Комментарии (7)

  • 9 декабря 2016 в 17:33

    +5

    ↑

    ↓

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

    • 9 декабря 2016 в 17:38

      0

      ↑

      ↓

      Спасибо за замечание.
      Учту и, возможно, перепилю. Больно тема зацепила.

  • 9 декабря 2016 в 17:37

    +1

    ↑

    ↓

    более подробное описание алгоритма https://www.youtube.com/watch? v=SfEZSyvbj2w

  • 9 декабря 2016 в 17:52

    +3

    ↑

    ↓

    У тебя очень своеброзный контроль версий как для пользователя github

    • 9 декабря 2016 в 17:53

      –2

      ↑

      ↓

      Первый репозиторий + рваный режим.
      Да и изначально не планировал, что люди увидят.

  • 9 декабря 2016 в 19:14 (комментарий был изменён)

    0

    ↑

    ↓

    Я лет 10 или 12 назад, на серверах LineAge собственных ботов запускал и смотрел как ни выживают в зависимости от алгоритмов.
    Если бы тогда имел представление о генетических алгоритмах, возможно боевку можно было еще веселее сделать.

    зы
    правда на живых серверах лучше всего показали себя торговые группы, которые скупали, продавали и крафтили все подряд с плавающими ценами в зависимости от кол-ва товара на «складе».

  • 9 декабря 2016 в 20:05

    +3

    ↑

    ↓ 

    if (_crtns[i]->IsAlive() == 0)

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

© Habrahabr.ru