Эволюционные вычисления

Целью группы эволюционных вычислений является повышение эффективности эволюционных алгоритмов. Повышение эффективности можно рассматривать с двух точек зрения. Первая точка зрения состоит в повышении качества эвристик, составляющих основное содержание эволюционных алгоритмов, в частности, адаптируемость этих алгоритмов к особенностям решаемых задач. Вторая точка зрения состоит в повышении эффективности реализации эволюционных алгоритмов без изменения выдаваемых результатов, а именно, снижения вычислительной сложности наиболее трудоемких компонентов эволюционных алгоритмов и повышения эффективности использования ресурсов вычислительной техники (в частности, многопроцессорных систем). Настоящая деятельность группы нацелена на повышение эффективности эволюционных алгоритмов с обеих точек зрения, что позволяет достигать комплексности решения проблемы.

 

Основные проекты

 

В рамках решения проблемы повышения эффективности эволюционных вычислений деятельность группы развивается в следующих направлениях:

 

Разработка методов теоретической оценки вычислительной сложности оптимизационных задач, а также теоретической оценки времени, за которое тот или иной эволюционный алгоритм находит оптимальное решение оптимизационной задачи.

 

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

 

Разработка методов адаптации эволюционных алгоритмов, а также комбинаций таких алгоритмов, к особенностям решаемой оптимизационной задачи в процессе оптимизации.

 

Современные тренды в области эволюционных алгоритмов состоят, в частности, в самоадаптации алгоритмов к решаемой задаче непосредственно в процессе оптимизации. Важное место занимает адаптация параметров алгоритмов, при этом в области комбинаторной оптимизации общих и при этом действенных методик пока не разработано, и даже в области вещественной оптимизации не все параметры поддаются гибкой адаптации. Группой разрабатывается несколько самоадаптирующихся эволюционных алгоритмов, наиболее законченным из которых  является метод EA+RL, с помощью которого выбираются наиболее адекватные оптимизируемые функции для ускорения процесса оптимизации.

 

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

 

Многие современные эволюционные алгоритмы состоят из "кирпичиков", среди которых встречаются имеющие достаточно высокую вычислительную сложность. Далеко не для всех них теоретические нижние оценки на сложность совпадают с достигнутыми, что мотивирует дальнейшие исследования. В 2014-2015 году исследовательской группой уже разработаны несколько улучшенных алгоритмов для "кирпичиков" такого рода.

 

Разработка эффективной и дружественной к пользователю программной библиотеки алгоритмов и структур данных для реализации эволюционных алгоритмов.

 

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