Задача моя была - оптимизировать конфиг-файл для биржевого робота, с чем он успешнее аналогов справляется. Тем не менее я старался его сделать максимально универсальным в использовании, и надеюсь, это получилось.
По интерфейсу он похож на алгоритмы оптимизации из scipy и pybrain. Зависимостей у него нет, только matplotlib, если интересно наблюдать график эволюционного прогресса.
Надеюсь, любителям мат. моделей с красивыми названиями понравится :) Алгоритм я использую в работе, так что буду его поддерживать на гитхабе. Он местами несовершенен (например, график надо сделать в отдельном потоке), возможно содержит баги. Если такие найдете, сообщите мне.
Проект на Гитхабе
Пример использования для решения диофантова уравнения взял из статьи на хабре. На гитхабе есть версия этого текста в более красивой разметке.
Попробуем найти одно из решений диофантова уравнения (с целочисленными корнями): a + 2b + 3c + 4d = 30. Фитнес-функция example_equation получает на вход список предположительных корней уравнения и возвращает отрицательное расстояние (чем больше фитнес, тем лучше) до его равенства (30). То есть при корнях являющихся решением, фитнес-функция вернет 0, во всех других случаях отрицательное число, которое чем ближе к нулю, тем больше наши корни похожи на решение.
def example_equation(x): '''Equation: a + 2b + 3c + 4d = 30''' a, b, c, d = x z = a + 2*b + 3*c + 4*d ans = 30 print("{:.0f} {:+.0f}*2 {:+.0f}*3 {:+.0f}*4 = {:.0f}".format(a, b, c, d, z), "- Solved!" if z == ans else "") return -abs(ans-z)
Параметры конструктора:
steps = 40 - дадим эволюции не более 40 поколений
stop_fitness = 0 - останавливаем эволюцию, когда функция вернула 0, значит решение найдено
bounds = (-100, 100, 1) - предположим корни лежат где-то в диапазоне (-100, 100), шаг единица, поскольку корни целочисленные. От шага зависит точность поиска решения. Иррациональные корни ГА не найдет.
num_genes = 4 - у нас 4 корня
stagnation = 3 - если эволюция войдет в застой на 3 поколения, применяем катаклизм (более сильная мутация)
mutagen = “1_step” - у каждой особи (потенциального решения) при рождении создаем мутацию - меняем один из параметров на размер шага
cata_mutagen = “full_step” - если мы вошли в стагнацию, применяем катаклизм - меняем все параметры на размер шага
population_limit = 10 - в каждом поколении будем тестировать 10 вариантов решения (особей)
survive_coef = 0.2 - из каждого поколения выбираем 20% лучших решений (то есть 2 особи из 10 смогут оставить потомков)
productivity = 4 - на каждую из двух выживших особей после скрещивания приходится 4 потомка, то есть в новом поколении будет 8 потомков, остальные 2 места в популяции займут особи сгенерированные случайным образом
plot = True - если установлен matplotlib, будем наблюдать эволюционный прогресс на графике
if __name__ == '__main__': ga = GA(example_equation, bounds=(-100, 100, 1), num_genes=4, steps=40, stop_fitness=0, stagnation=3, population_limit=10, survive_coef=0.2, productivity=4, mutagen="1_step", cata_mutagen="full_step", plot=True) result = ga.evolve() print("Best solution:", result)
Результат работы:
- Step 10 / 40 results: best: -2.000, spread: 4.000, elapsed: 0m 1s, remaining: 0m 0s
-100 +68*2 -66*3 +48*4 = 30 - Solved!
-100 +67*2 -65*3 +48*4 = 31
-99 +67*2 -66*3 +47*4 = 25
-100 +67*2 -66*3 +48*4 = 28
-99 +67*2 -66*3 +48*4 = 29
-100 +67*2 -67*3 +47*4 = 21
-100 +67*2 -66*3 +46*4 = 20
-100 +68*2 -66*3 +48*4 = 30 - Solved!
-76 -30*2 +69*3 +69*4 = 347
27 -73*2 -32*3 -20*4 = -295
- Step 11 / 40 results: best: 0.000, spread: 0.000, elapsed: 0m 1s, remaining: 0m 0s
- Evolution complete: best fitness = 0.000 <= 0.000
Best solution: (, 0)
Можете проверить на тестовых функциях нелинейного программирования…