В прошлом году я делал доклад для конференции PGConf Russia 2023 по теме «Познакомимся с GEQO за 20 минут» (есть запись на Youtube). Но за двадцать минут у меня не получилось рассказать подробнее про все те механизмы, которые используются в PostgreSQL при реализации генетического алгоритма. Так что я решил написать подробную статью об этом.
Но быстро написать статью у меня не получилось, продолжаю над ней работать. И, параллельно (а заодно и чтобы исходный код GEQO понимать получше) решил написать простую программу на языке Си, которая бы решала задачу OneMax.
При написании программы вдохновлялся статьей «Делаем генетический алгоритм для задачи OneMax» (там есть код на Python, но в него я не смотрел). Я не Си-программист, так что косяков у меня в программе очень много.
Получившийся исходный код можно посмотреть в моём github-репозитарии: onemax.
Эту задачу я решаю с помощью генетического алгоритма используя:
- турнирный отбор (по умолчанию из трёх индивидов);
- одноточечное скрещивание (с вероятностью 90%);
- мутацию (с вероятностью 5%).
Если кратко, то задача onemax — это задача с битовой строкой, цель которой максимизировать количество единиц в двоичной строке (либо, наоборот, минимизировать).
В процессе эволюции программы я сначала сделал возможность «включать» отладочный режим — когда вся промежуточная информации (сгенерированные индивиды, результаты скрещивания и мутации) выводится на экран. Затем я научился работать с файлами, убрал отладочный режим и вся эта отладочная информация всегда попадает в файл. Это удобно, особенно когда надо ошибки посмотреть (что было очень много раз).
Заодно прикрутил рисование графиков с помощью gnuplot — очень удобная штука, мне очень нравится!
На этом примере можно понаблюдать как мутация влияет на скорость решение задачи onemax. Кстати, в текущей реализации GEQO в PostgreSQL не используется мутация. Хотя там и генетический алгоритм другой используется — Genitor, разработанный Д. Уитли.
Зачем же я написал свою реализацию генетического алгоритма?
- Это было интересно;
- Это был вызов себе;
- Надеюсь что получше разобрался с терминологией;
- Лучше понял функция srand для инициализации генератора случайных чисел;
- Да и в целом — лучше понял как работают генетические алгоритмы;
- Некоторые части моего кода были очень похожи на тот, что написан в PostgreSQL 🙂
- Но сам мой код очень неэффективен…
Надеюсь что это поможет мне дописать статью про генетический алгоритм GEQO в PostgreSQL.
Leave a Reply