Как я уже писал, помимо проекта OutWiker, в последнее время я занялся проектом optlib, библиотекой на языке Rust с реализацией разных алгоритмов оптимизации. На данный момент в библиотеке реализованы генетический алгоритм и алгоритм роя частиц. На днях я выложил новую версию этой библиотеки под номером 0.3.0.

У библиотеки optlib есть документация, но в ближайшее время я собираюсь заняться написанием статей с более подробным описанием работы этой библиотеки. В этом посте я коротко расскажу о том, что появилось нового в версии 0.3.0.

Во-первых, в версии 0.3.0 я продолжил добавлять разные варианты алгоритма роя частиц. Например, была добавлена структура InertiaVelocityCalculator, которая реализует алгоритм роя частиц с инерцией, т.е. когда скорость каждой частицы рассчитывается по формуле:

Параметр w(t) задает инерцию. Инерция благоприятно сказывается на сходимости алгоритма. Закон изменения w может быть различным, например, w может не меняться от номера итерации (быть константой), а может линейно уменьшаться. В этом посте я не буду подробно описывать, как используются структуры (пока нет новых статей о библиотеке optlib, интересующиеся могут посмотреть примеры в папке optlib/examples (в новой версии optlib примеров стало больше, но о них я скажу чуть позже). В частности, «из коробки» поставляются структуры, реализующие оба варианта изменения инерции (константа и линейное убывание).

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

В-третьих, в новую версию optlib были добавлены изменения, ломающие обратную совместимость с предыдущей версией. Я думаю, что это нормально, пока библиотека находится на стадии бурного развития. Например, некоторые параметры алгоритмов (например, список логгеров) были убраны из обязательных параметров конструктора структуры оптимизаторов, а устанавливать их теперь нужно с помощью специальных методов (для логгеров — это set_loggers). Также были переименованы некоторые методы.

И, наконец, самое интересное. Поскольку библиотека optlib предназначена для исследования работы алгоритмов и выбора наиболее оптимального из них для каждой задачи, то необходимо как-то сравнивать результаты работы разных алгоритмов или разных настроек одного и того же алгоритма. И генетический алгоритм, и алгоритм роя частиц используют случайные числа, поэтому для адекватной оценки результатов работы нужно набирать статистику их работы по большому количеству запусков. Для этой цели в optlib 0.3.0 были добавлены структуры, сохраняющие результаты работы алгоритмов для каждого запуска, а также для каждой итерации внутри запуска. Благодаря этому можно, например, построить усредненные графики сходимости алгоритма (зависимости значения целевой функции от номера итерации алгоритма). Также можно рассчитать вероятность нахождения правильного решения — отношение количества запусков, когда алгоритм успешно нашел глобальный минимум к общему количеству запусков алгоритма, причем успешность запуска алгоритма может определяться либо с помощью сравнения найденного решения и известного решения, или по известному значению целевой функции в глобальном экстремуме.

Также была добавлена возможность подсчета, сколько раз вызывалась целевая функция. Это важно во многих задачах оптимизации, поскольку расчет целевой функции может быть достаточно долгим (до десятков минут и больше), и чем меньше раз мы ее рассчитываем, тем быстрее закончит работу алгоритм оптимизации.

Все эти варианты использования статистики можно увидеть в примерах, прилагающихся к библиотеке. Для запуска каждого из примеров в корневой папке исходников нужно выполнить команду

cargo run —example имя_примера —release

Примеры, в именах которых присутствует слово «statistics», запускают алгоритм оптимизации 500 раз и некоторые статистические результаты (например, вероятность успешного нахождения правильного экстремума) выводят в консоль, а некоторые (по которым можно строить графики сходимости) — в файлы.

Это, пожалуй, самые интересные изменения, сделанные в optlib 0.3.0, остальные изменения описаны в файле CHANGELOG.md.

PS. Вы можете подписаться на новости сайта через RSS, Группу Вконтакте или Канал в Telegram.