Оптимизируй это: учёные рассказали, как решать сложные задачи с помощью эволюционных алгоритмов

Учёные Сибирского федерального университета объяснили, как достичь оптимального решения сложных задач в различных областях при помощи особого семейства эволюционных алгоритмов. На примере алгоритма L-SHADE-RSP исследователи показали преимущества эволюционных алгоритмов в сравнении с классическими подходами к оптимизации. Подобные алгоритмы, следующие принципам, озвученным Чарлзом Дарвином в теории эволюции живых организмов, уже сейчас могут успешно применяться в приборостроении, радиоэлектронике, спортивной индустрии, строительстве, при создании космических спутников и т.д. Кроме того, в учёные планируют достичь автоматического машинного проектирования эволюционных алгоритмов без участия человека – для этого планируется использовать генетическое программирование и нейроэволюцию.

Алгоритм L-SHADE-RSP, созданный учёными СФУ, приспособлен для решения задач оптимизации различных процессов. По словам одного из разработчиков, доцента базовой кафедры интеллектуальных систем управления Института космических и информационных технологий (ИКиИТ) СФУ Владимира Становова, речь идёт об оптимизации в математическом смысле этого термина.

«Например, требуется оптимизировать форму антенны для наилучшего приёма сигнала на заданных частотах, или же нужна оптимизация траектории космического аппарата для снижения затрат топлива, или оптимизация выработки энергии в электросетях с учетом потерь и наполнения/расхода воды в каскаде ГЭС с целью снижения выбросов – во всех этих случаях существует математическая модель процесса, по которой можно оценить качество решения. Если модель относительно простая, можно использовать классические оптимизационные подходы, но для сложных реальных процессов они часто не работают. В таких случаях используют эволюционные и бионические алгоритмы. В конце концов, принципы естественной эволюции создали всё многообразие природы, а также и самого человека, так что следование им является мощным инструментом решения любого рода проблем при наличии достаточных вычислительных ресурсов», – сообщил Владимир Становов.

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

Алгоритм L-SHADE-RSP (Линейное уменьшение размеров популяции в Дифференциальной Эволюции с Адаптацией по Истории Успеха и Ранговым Селективным Давлением), представленный специалистами ИКиИТ СФУ в 2018 году, - это, фактически, развитие популярного алгоритма L-SHADE, представленного японцами в 2014 году. Суть модификации состоит в том, что красноярские учёные добавили в дифференциальную эволюцию усиленные механизмы селекции (отбора). В «прокачанном» варианте алгоритма более качественные решения выбираются с большей вероятностью в процессе поиска, чем менее качественные. Владимир Становов называет это отсылкой к базовому принципу теории эволюции, сформулированному Чарлзом Дарвином: «выживает наиболее приспособленный».

«Область применения нашего алгоритма практически неограничена, он поистине универсален. Единственное условие – наличие математической модели и критерия качества. К примеру, если бы у нас была точная математическая модель спортсмена со всеми параметрами (рост, вес, сила мышц и т.д.), то с помощью L-SHADE-RSP можно было найти наилучший набор и последовательность движений для совершения самого высокого прыжка. А если иметь достоверную математическую модель учебного процесса, можно оптимизировать процесс обучения, руководствуясь нужным критерием качества (допустим, выпуск наибольшего количества высококлассных специалистов). К сожалению, модели для приведенных примеров построить очень сложно, поскольку их сложно формализовать. С техническими системами гораздо проще – генетический алгоритм может научиться ходить смоделированным человеком, потому что у него будет физическая модель с трением, инерцией и массой, а также критерий качества – количество успешно сделанных шагов», - объяснил Владимир Становов.

В качестве одной из тестовых задач для проверки работы алгоритма учёные СФУ использовали задачу оптимизации траектории аппарата Cassini, который был запущен для исследования Сатурна ещё в 90-х годах. Ещё одна задача – оптимизация кредитного портфеля предприятия. Зная риски и прибыльность, при заданном бюджете можно рассчитать наилучшее вложение средств с допустимым уровнем риска.

Одним из интересных достижений исследователей можно считать создание модифицированной схемы адаптации параметров, за счет которой алгоритм настраивает сам себя в ходе решения задачи. Ещё одно перспективное направление будущего эволюционных алгоритмов – визуализация процесса поиска. Учёные говорят, что в данной области результатов достаточно мало, но визуализация поиска важна для понимания и разработки новых, более эффективных алгоритмов. На сегодняшний день программисты СФУ работают над реализацией автоматического проектирования алгоритмов: ожидается, что однажды компьютер сможет самостоятельно проектировать оптимизационные методы без участия человека – для этого эксперты используют генетическое программирование и нейроэволюцию.

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