Текст уведомления здесь

Эволюционные алгоритмы

Что это такое и для чего они нужны

Эволюционные алгоритмы были разработаны на основе эволюционных теорий для того, чтобы решать задачи, сложные для человека. Где применяются эти алгоритмы, как они работают и с чего началось их развитие, рассказывает Арина Буздалова, научный сотрудник лаборатории «Компьютерные технологии» Университета ИТМО.
Добавить в закладки
Комментарии

Арина БУЗДАЛОВА, научный сотрудник лаборатории «Компьютерные технологии» Университета ИТМО:

— Как развивается жизнь на Земле? На этот вопрос отвечают эволюционные теории. И на основе эволюционных теорий были разработаны эволюционные алгоритмы. Они в своей основе содержат простые идеи из данных теорий. Я приведу пример: опишем форму антенны с помощью каких-то моделей, и набор возможных форм — пусть сначала неэффективных, пусть сгенерированных случайным образом — будем называть «популяцией» (по аналогии с эволюцией в природе). А каждую конкретную форму назовем «особью». Особям можно сопоставлять приспособленность. В нашем примере с антенной — это то, насколько хорошо антенна передает сигнал. Но в принципе эволюционные алгоритмы хороши тем, что применимы для любой задачи оптимизации.

Приспособленность — это то, насколько наши пробные решения близки к оптимуму, насколько они хороши. Итак, у нас есть набор каких-то форм. У форм есть приспособленность. Значит, можно отобрать наиболее приспособленные и применить к ним опять же операции, вдохновленные естественной эволюцией. Например, мутацию — поменять какую-то форму немножко. Скрещивание — взять часть антенны от одного «родителя», часть — от другого и составить новую антенну, и т.д. Таким образом, мы получим т.н. потомков. Итак, у нас есть родители и потомки! Мы можем выбрать из них опять же наиболее приспособленных — для следующего поколения. И в следующем поколении мы можем повторить то же самое, и т.д., и т.п. От поколения к поколению мы будем получать все лучшие решения.

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

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

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

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

Но помимо этого, разумеется, есть у нас и практические направления. Я упоминала, что эволюционные алгоритмы хорошо решают задачи, сложные для человека. Одними из таких задач, например, являются задачи логистики. Задачи, в которых нужно распределить доставку груза клиентам. Есть несколько, условно говоря, водителей. Они должны как-то проехать по городу и, например, доставить вещи, заказанные в интернет-магазине. Это сложная задача не только потому, что в ее основе лежит задача коммивояжера, являющаяся NP-трудной, но и потому, что среда, в которой водителю необходимо перемещаться, динамическая, изменяющаяся. Может возникнуть пробка. Может случиться авария. Или клиент будет долго, придирчиво принимать заказ. Как же составить расписание разъезда водителей так, чтобы оно было достаточно гибким и при этом достаточно эффективным?

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

Добавить в закладки
Комментарии
Вам понравилась публикация?
Расскажите, что вы думаете, и мы подберем подходящие материалы

Всё по науке: часть четвертая

Что стоит почитать ВКонтакте, если я интересуюсь наукой, но не хочу наткнуться на обман или глупость

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

Скептик

https://vk.com/skeptic_magazine

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

Иными словами, не заблуждайтесь и просвещайтесь! [ ... ]

Читать полностью

Пермские кости в Кировской области

Котельнич и раскопки на Котельничском палеонтологическом местонахождении — в фоторепортаже «Чердака»

Корреспонденты «Чердака» побывали в городе Котельниче Кировской области, в его палеонтологическом музее и на Котельничском палеонтологическом раскопе. Здесь российские палеонтологи каждый год извлекают из красного вятского грунта скелеты древних звероящеров, которые жили на нашей планете задолго до динозавров и погибли 250 миллионов лет назад в ходе Великого пермского вымирания. Коротко о городе и раскопках — в фотографиях Максима Абдулаева.
Добавить в закладки
Комментарии

Котельнич — маленький городок в Кировской области. Там был кинотеатр «Родина», но он закрылся.

Фото: Максим Абдулаев / Chrdk.

Фото: Максим Абдулаев / Chrdk.

Там был «секонд хэнд», но и он закрылся.

Фото: Максим Абдулаев / Chrdk.

Фото: Максим Абдулаев / Chrdk.

[ ... ]
Читать полностью

Эволюция Вселенной

Мультфильм «Чердака» о том, с чего все-все началось

Что было после Большого взрыва, как образовались звезды и планеты, где на Земле зародилась жизнь и сколько времени потребовалось, чтобы на нашей планете появились растения, животные и мы с вами, смотрите в мультфильме «Чердака».
Добавить в закладки
Комментарии
Добавить в закладки
Комментарии
Вам понравилась публикация?
Расскажите, что вы думаете, и мы подберем подходящие материалы