2015-09-06

Эволюционная оптимизация в SmathStudio

SmathStudio очень хорош для быстрого прототипирования алгоритмов. В этот раз опробовал его для написания эволюционного алгоритма несколько нестандартного вида.

Для создания начальной популяции используются ЛПТау последовательности вместо обычного random. Это позволило создать более равномерную и предсказуемую последовательность точек.
Распределение особей в зависимости от способа создания - слева ЛПтау, справа с помощью равномерного случайного непрерывного распределения (uniform)
 
  • Адаптивный механизм формирования новой популяции - помимо обычного скрещивания добавляются новые особи в окрестностях лучших параметров особей из предыдущих популяции. Соотношение количества скрещенных и новых особей зависит от величины мутации. Размер области добавления новых особей также зависит от величины мутации. В качестве отправной точки принимаются значение параметров лучшей особи из предыдущего поколения
Размер области в зависимости от величины мутации

  • Величина мутации меняется в зависимости от скорости сходимости. Если фитнесс-функция на протяжении нескольких поколений меняется незначительно - увеличивается величина мутации. Это не даёт застревать алгоритму на локальном минимуме.
Сходимость алгоритма весьма приличная - при пяти особях в популяции минимум функции Розенброка находит на 5-10 поколении, вплотную подходит к минимуму функции Химельбау в точке [3.0, 2.0] на 40 поколении. С функцией Растригина пока беда - застревает на одной точке. 

В дальнейшем можно использовать его для оптимизации размеров конструкций, также рассчитанных в Smath - размеры подпорных стен, высота крепления анкеров в шпунтовых стенах, шаг прогонов и прочее.

Здесь можно скачать файл с вспомогательными таблицами. После распаковки в переменные Path и Данные необходимо записать путь к файлу и таблицам.

Схожий алгоритм реализован на Python для нахождения минимальных областей течения грунта для диссертации. Исходный код можно посмотреть тут, описание тут.

Поиск минимальных областей течения

Вообще о генетических и эволюционных алгоритмах хорошо написано на хабрахабре
http://habrahabr.ru/post/122222/
http://habrahabr.ru/post/171751/
http://habrahabr.ru/post/114910/