Методы оптимизации
Наверное, нет свете такой сферы деятельности, где не возникала бы задача оптимизации. Практически любую проблему или задачу можно свести к задаче оптимизации чего-либо.
Примеры задач оптимизации
- Задача коммивояжера – нахождение минимального пути обхода всех городов, с посещением каждого только 1 раз.
- Заполнение рюкзака или вагонов состава с максимальным использованием доступного объема (минимальным незаполненным пространством).
- Максимизация прибыли компании
- Минимизация затрат компании
- Подбор компонентов изделия с максимальной стоимостью готового продукта
- Нахождение оптимального времени в ряде задач
- И т. д. и т. п.
Так как математически максимум всегда можно обратить в минимум, будем считать, что оптимизация означает нахождение минимального значение чего-то.
Задача оптимизации в общем виде
Имеется совокупность (популяция) объектов (особей, точек, частиц) с n-ым количеством свойств. Нужно составить функцию, которую можно минимизировать. В функцию нужно включить свойства, которые мы хотим контролировать. Можно добавить также свойства, которые можно получить расчетным путем из реально существующих. И, конечно же, нужно добавить наложенные ограничения.
Реальный пример из жизни: Задачи логистики
Дано: парк транспортных средств и сеть пунктов доставки.
Общая постановка задачи: составить расписание машин так, чтобы в течение суток они объехали все пункты доставки и вернулись на базу.
Что будем минимизировать? Наверное, затраты?
Чтобы понять, что и как, сначала нужно ответить на ряд вопросов. Например:
- То, что расстояния между пунктами придется учитывать – это очевидно. Для того, чтобы рассчитать время, необходимое для проезда в пункт доставки. А скорость какую брать? Среднюю? А пробки и время суток? А обеденное время водителя? А время на погрузку/разгрузку?
- А в затраты включаем зарплату водителей? А страховку или аренду машин? А бензин/дизель и масло?
- А что если из пункта доставки нам хотят тоже отдать груз, который нужно отвезти в другую точку?
- А грузоподъемность машин учитывать?
Вопросов просто множество.
И более конкретных задач тоже может возникнуть немало. Например, экономия всех затрат. Или только на бензин? Или только на аренду машин? Или машинки старенькие и нам важнее будет минимизировать общий пробег?
В общем, для решения нашей конкретной задачи собираем все параметры, которые для нас важны или влияют на решение. Составляем из них функцию и находим ее минимум. Он нам даст информацию, что и как нужно контролировать.
Методы оптимизации
Методов оптимизации и типов их классификации существует много.
Например, нашел в интернете такую схему.
Не стал тратить время на перевод.
Просто поясню. Нас не интересуют так активно изучаемые в вузах методы линейного и целочисленного программирования и иже с ними. В реальной жизни, со множеством данных и параметров, которые хотелось бы учитывать, они практически бесполезны из-за ограничений на данные и неумения работать с BigData.
Зато обведены красным полезные методы:
Алгоритмы оптимизации – это методы, которые позволяют найти оптимальные значения параметров или решения для задачи. Они используются для настройки моделей, минимизации ошибок или максимизации заданных функций. Давайте рассмотрим некоторые популярные алгоритмы оптимизации.
- Градиентный спуск: Это один из наиболее распространенных алгоритмов оптимизации. Он базируется на идее использования градиента функции для определения направления, в котором нужно двигаться, чтобы найти минимум функции. Градиентный спуск постепенно обновляет значения параметров в направлении, противоположном градиенту. Итерации продолжаются до достижения минимума.
- Алгоритмы генетической оптимизации: Они основаны на принципах естественного отбора и эволюции. В этих алгоритмах создается популяция кандидатов, в которой происходят операции скрещивания и мутации – так появляются новые особи, с характеристиками, унаследованными от родителей. Для выживаемости популяции выбираются наилучшие особи с помощью особой функции приспосабливаемости (целевой функции).
- Алгоритмы роевого интеллекта: Имеется несколько разновидностей роевых алгоритмов. Например, алгоритм роя частиц моделирует поведение группы агентов (частиц), которые движутся в пространстве параметров. Каждая частица имеет свое положение и скорость, которые обновляются на основе лучшего результата, достигнутого этой частицей и группой в целом. Процесс продолжается до достижения оптимального решения.
Это лишь несколько примеров алгоритмов оптимизации, и на самом деле их существует множество. Каждый алгоритм имеет свои особенности и подходит для разных типов задач. Они могут быть применены в различных областях, таких как машинное обучение, искусственный интеллект, финансы, логистика и другие.
Классические задачи по оптимизации:
— Посадка лунного модуля на поверхность Луны
В этом случае целевой функцией будет расстояние между самим модулем и поверхностью Луны. Оно станет равным нулю при мягкой посадке и больше меняться не будет. Если же оно станет меньше нуля, то значит, аппарат врезался в поверхность. И задача не была решена положительно.
— Поддержание равновесия вертикально стоящего шеста на двигающейся тележке
Задача – сохранение шестом своего вертикального положения на движущейся тележке. При этом нужно учитывать: скорость движения и направление движения, отклонение шеста от горизонтального равновесного положения, влияние силы гравитации. Понятно, что в данном случае целевой функции будет угол отклонения шеста от 90°.
— Предоление машинкой высшей точки возвышенности и скатывание её на противоположную сторону
Задачах по распознаванию изображений и образов целевой функции будет отклонение каких-то рассчитанных параметров например плотности изображения суммарной плотности изображения сгенерированного изображения от целевого образца.
Использование весов позволяет при изначально случайных значениях разных параметров автоматически изменять их значение для нахождения экстремального значения
Общая схема решения оптимизационных задач
- Как правило, все исходные данные в начале нормируются, т. е. приводятся к диапазону [0, 1] или [-1, 1]
- Создается начальная популяция из заданного количества особей/точек/частиц/. Т. е. задаются значения их свойств. Как правило, это – случайные значения, соответствующие вышеуказанным границам.
- Задается набор параметров (свойств), которые необходимо определить (лучшее решение) и допустимые границы их изменения. При этом значения этих свойств устанавливается максимально неправдоподобным (чтобы далее итерационно искать более лучшее решение).
- Рассчитывается значение целевой функции для текущих параметров.
- Если значение целевой функции меньше ранее выбранной как лучшее решение, то текущий набор параметров принимается за лучший.
- По специальным правилам вычисляются новые значения параметров.
- Если условия останова выполнены, то выходим из цикла с лучшим решением. Если нет – возвращаемся в п. 3.
Алгоритмы решения оптимизационных задач
Здесь я еще раз упомяну те алгоритмы, которые рассмотрим в дальнейшем.
Для нахождения оптимальных значений целевой функции используют алгоритмы, которые можно разделить на 3 класса:
Статистические методы, основанные на обучении нейронных сетей. При этом нейросетям “скармливается” информация об образцах уже существующих объектов. Далее с ее помощью выводятся зависимости в данных. В основном, это – методы градиентного спуска.
Генетические алгоритмы. Используют объекты и свойства типа:
- популяция
- особь
- ген
- хромосома
- скрещивание
- выживаемость
- вероятность скрещивания и т. д.
Алгоритмы роевого интеллекта. Как и генетические алгоритмы, они тоже базируются на понятиях популяция и особь. Но если в генетике во главу угла поставлена выживаемость популяции, в алгоритмах роя главное – коллективное поведение, взаимодействие особей популяции.
