Материалы портала «Научная Россия»

Ускорить на порядки решения задач оптимизации обещает новый алгоритм

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

Сэм Вонг (Sam Wong) из Университета Калифорнии в Беркли и двое студентов Массачусетского технологического института Инь-Тат Ли (Yin-Tat Lee) и Аарон Сидфорд (Aaron Sidford) разработали новый алгоритм решения проблемы оптимизации, который увеличит эффективность ее решения на несколько порядков. Полностью он представлен в статье на сайте arxiv.org, кратко о нем рассказывает сайт MIT.

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

Суть проблемы оптимизации с точки зрения математики — это попытка найти минимальное значение математической функции, известной как функция стоимости. К примеру, в алгоритме для обнаружения объектов как положительный фактор будет учтена правильная классификация объекта, а как отрицательный — ложные срабатывания. Поиск оптимального варианта при создании такого датчика — это поиск оптимального соотношения первого и второго, такое инженерное решение, которое максимально увеличит плюсы и при этом оставит лишь минимальную возможность ошибок.

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

алгоритм алгоритм оптимизации оптимизация

Назад

Социальные сети

Комментарии

Авторизуйтесь, чтобы оставить комментарий