Python-сообщество

Некоторое время назад я создавал темку про алгоритмы оптимизации и свою с ними проблему. Не найдя лучшего решения, я в тот же день начал разработку собственного Генетического алгоритма.
Задача моя была - оптимизировать конфиг-файл для биржевого робота, с чем он успешнее аналогов справляется. Тем не менее я старался его сделать максимально универсальным в использовании, и надеюсь, это получилось.
По интерфейсу он похож на алгоритмы оптимизации из 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)

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)

Отредактировано pasaranax (Май 5, 2016 20:29:48)

Прикреплённый файлы:
ga.png (54,9 KБ)

А что Вы читали по ГА, до того как это написать?

Отредактировано 4kpt_IV (Май 5, 2016 20:54:39)

4kpt_IV
А что Вы читали по ГА, до того как это написать?

Просто ГА уже шагнуло давно вперед. Есть механизмы для определения оптимальных параметров ГА, так называемый тестовый ГА, есть принцип управляемых мутаций и т.п. Вы сделали колоссальную работу, но по очень “каноничному” ГА. А вот сходимость у него низкая Можете проверить на тестовых функциях нелинейного программирования…

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

Банди. Методы оптимизации. Вводный курс. Страница 36,37. Там есть несколько тестовых функций. Для начала Вам должно хватить. Сравнивать сходимость можно с методами прямого поиска типа метода “Нелдера-Мида”.

Отредактировано 4kpt_IV (Май 5, 2016 21:13:05)

pasaranax
он успешнее аналогов справляется

Shaman
Была ли Deap среди этих аналогов?

Ясно. В таком случае альтрнативу ей искать пока не буду.