Теория оптимизации: Репозиторий Самарского национального исследовательского университета имени академика С.П. Королёва: Недопустимый идентификатор

Тема 1. Основы теории оптимизации

1

1.Основы теории оптимизации 1.1.Постановка и решение задачи оптимизации

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

Постановка любой задачи оптимизации включает в себя 4 этапа.

1)Установление границ подлежащей оптимизации системы

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

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

2)Выбор характеристического критерия

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

Критериев может быть много и тогда задача становится многокритериальной. Существуют специальные методы решения многокритериальных задач, но можно привести многокритериальную задачу к однокритериальной. Для этого один из критериев выбирается в качестве первичного, а остальные становятся вторичными. Первичный критерий используется как характеристический, а вторичные формируют ограничения задачи. (Многокритериальная оптимизация: Мат. аспекты / Б. А. Березовский, Ю. М. Барышников, В. И. Борзенко, Л. М. Кемпнер; М. Наука 1989)

3)Выбор независимых переменных, используемых для определения характеристик системы и идентификации вариантов решения Необходимо разделить переменные на те, значения которых могут изменяться в достаточно

широком диапазоне и те, значения которых фиксированы и определяются внешними факторами. Первые являются независимыми переменными, а вторые – параметрами задачи.

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

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

2

Последнее стремление продиктовано необходимостью разумного упрощения задачи.

4)Построение математической модели системы

Модель системы описывает взаимосвязь между переменными и отражает степень их влияния на характеристический критерий.

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

“Корректная постановка задачи служит ключом к успеху оптимизационного исследования и ассоциируется в большей степени с искусством, нежели с точной наукой.”[3] Решение оптимизационной задачи – это приемлемый набор значений независимых

переменных, которому отвечает оптимальное значение характеристического критерия.

1.3. Структура оптимизационных задач

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

Общий вид задачи условной оптимизации

Минимизировать f (x) : R N R1 при ограничениях

 

 

 

 

 

 

 

 

 

hk (x) 0 ,

k 1…K

(1.1)

g j (x) 0 ,

 

 

 

 

 

 

 

j 1…J

(1.2)

xiL xi xiR ,

 

 

 

i 1. ..I

(1.3)

Здесь f (x) — целевая функция задачи, уравнения hk (x) 0 – называются ограничениями в виде равенств, а неравенства g j (x) 0 – ограничениями в виде неравенств. Предполагается, что все функции в задаче вещественнозначны, а число ограничений конечно.

Задачи оптимизации можно классифицировать в соответствии с видом функций f (x) , g(x) и h(x) , а также размерностью вектора x .

Если ограничения (1.1) – (1.3) отсутствуют, то это задача безусловной оптимизации. Такие задачи с N 1 называются задачами одномерной оптимизации, при N 1 – многомерной безусловной оптимизации.

Если в задаче оптимизации функции hk (x) и g j (x) линейны, то это задача с линейными ограничениями. При этом целевая функция может быть как линейной, так и нелинейной. Задача условной оптимизации, в которой все функции линейны, называется задачей

3

линейного программирования (ЛП). Если при этом координаты вектора x должны принимать только целые значения, то задача называется задачей целочисленного программирования

(ЦЛП).

Задачи с нелинейными целевой функцией и/или ограничениями называются задачами нелинейного программирования (НЛП).

1.3. Практическое применение методов оптимизации

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

Математическая теория оптимизации и исследованиe операций

Новости


07.11.2022

International Conference Mathematical Optimization Theory and Operations Research (MOTOR 2023), July 2-8, 2023, Ekaterinburg, Russia, http://motor2023. uran.ru


07.07.2022

ТВ-репортаж о конференции:

https://vk.com/sampotv360?w=wall-28174864_59165


21.06.2022

Conference proceedings MOTOR 2022, LNCS 13367, free online access from June, 24, 2022 till July, 26, 2022:

https://link.springer.com/book/10.1007/978-3-031-09607-5


29.04.2022

Springer принял решение опубликовать наши труды в сериях Lecture Notes in Computer Science (LNCS) и Communications in Computer and Information Science (CCIS).

Каждому автору будет отправлено письмо через систему EasyChair с приглашением и инструкцией как загрузить файл camera-ready zip. в систему.

Важные даты:

статьи в LNCS — загрузить в систему до 15 мая

статьи в CCIS — загрузить в систему до 1 июня


Анонс


Международная конференция «Математическая теория оптимизации и исследование операций» (MOTOR-2022) состоится 2-6 июля 2022 года в г. Петрозаводске, Республика Карелия.


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


«MOTOR 2022» — это четвертая международная конференция, объединяющая четыре известные российские и международные конференции, которые долгое время проводились на Урале, в Сибири и на Дальнем Востоке:

* Байкальский международный трехгодичный школьный семинар по методам оптимизации и их применению

http://isem.irk.ru/conferences/mopt2017/en/index.html

* Математическое программирование и прикладные программы http://mpa.imm.uran.ru/96/en

* Дискретная оптимизация и исследование операций http://www.math.nsc.ru/conference/door/2016/

* Задачи оптимизации и их приложения http://opta18. oscsbras.ru/en/


Предыдущие MOTOR конференции:


* Mathematical Optimization Theory and Operations Research (MOTOR 2019) (Ekaterinburg) http://motor2019.uran.ru/

* Mathematical Optimization Theory and Operations Research (MOTOR 2020) (Online) http://www.math.nsc.ru/conference/motor/2020/

* Mathematical Optimization Theory and Operations Research (MOTOR 2021) (Иркутск, Hybrid) https://conference.icc.ru/event/3/


Конференция «MOTOR 2022» будет организована в Петрозаводске 2-6 июля 2022 года. Будут обсуждены современные проблемы оптимизации и исследования операций, в частности проблемы теории математической оптимизации, целочисленного программирования и комбинаторной оптимизации, глобальной оптимизации, стохастического целочисленного программирования, многоцелевого программирования, вычислительной сложности задач комбинаторной оптимизации, аппроксимационные алгоритмы и схемы, эвристика и метаэвристика для принятия решений и искусственного интеллекта, теория игр, математическая экономика и многоуровневое программирование, оптимизация в области машинного обучения и анализа данных, применение в исследованиях операций: планирование, маршрутизация, расположение объекта, упаковка и резка, цепочка поставок и т. д.


В рамках конференции будет проведена молодежная школа по оптимизации и исследованию операций.


Организаторы планируют опубликовать лучшие доклады в Lecture Notes in Computer Science (Springer) и специальном выпуске Communications in Computer and Information Science (CCIS).



Раздел 1) Теория оптимизации. Обзор теории оптимизации и… | Брендон Морган

КУРС ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ

Обзор теории оптимизации и четырех основных типов задач оптимизации

Здравствуйте и добро пожаловать снова на этот полный курс по эволюционным вычислениям! В этом посте мы начнем с раздела 1 курса «Теория оптимизации». В предыдущем посте мы рассмотрели базовый обзор курса, вы можете ознакомиться с ним здесь:

Эволюционные вычисления (ПОЛНЫЙ КУРС) Обзор

Вводный пост о материале, концепциях и приложениях, которые я буду освещать в этой совершенно новой серии!

в направлении datascience. com

Для начала, что такое теория оптимизации? Теория оптимизации — это раздел математики, посвященный решению задач оптимизации. Задачи оптимизации — это математические функции, в которых мы хотим минимизировать или максимизировать значение функции. Эти типы задач часто встречаются в информатике и прикладной математике. Поиск хороших решений этих проблем — это то, что обеспечивает хорошую точность моделей науки о данных и машинного обучения, поскольку они сами построены на численных методах, используемых для поиска хороших решений для минимизации функций ошибок. Примерами общих проблем оптимизации в машинном обучении являются минимизация MSE, MAE, кросс-энтропии и т. д.

  • Обзор
  • Неограниченные проблемы
  • С ограниченными проблемами
  • Проблемы с несколькими сериями
  • Многообъективные проблемы
  • Функции теста

    • .

    1. Что такое целевая функция?

    2. Каков набор интересующих переменных?

    3. Что такое набор ограничений?

    Знание того, как выглядит ваша целевая функция с точки зрения количества измерений, домена и количества локальных экстремумов, жизненно важно при выборе алгоритма. Кроме того, необходимо понимать тип данных для каждой из переменных: дискретный или непрерывный? Наконец, знание набора ограничений важно для ограничения вашего алгоритма поиска в доменном пространстве только возможных решений.

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

    1. Слабый экстремум

    2. Сильный экстремум

    3. Глобальный экстремум

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

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

    Неограниченный Проблемы таковы, как они звучат, неограниченные. Это функции, в которых мы хотим минимизировать или максимизировать функцию с заданным набором переменных, область определения которых либо непрерывна, либо дискретна, либо и то, и другое. Здесь у нас есть определение:

    Изображение автора

    Задачи с ограничениями аналогичны задачам без ограничений с точки зрения настройки, но имеют уникальные ограничения на входное пространство. Здесь у нас есть определение:

    Изображение автора

    В качестве наглядного примера ниже приведен пример этих компонентов. Во-первых, у нас есть целевая функция, обозначенная как A . Затем у нас есть глобальный неограниченный минимум внизу справа в точке E . Однако мы вводим ограничение неравенства, обозначенное строкой D , где любое значение в клетчатой ​​области невозможно. Таким образом, у нас остается часть домена для работы. Точки B и C являются двумя критическими точками в допустимом доменном пространстве. Однако следующий глобальный минимум в ограниченной среде будет в точке 9.0065 Ф . Таким образом, в подобных сценариях мы хотели бы, чтобы наш алгоритм отклонялся от невозможного доменного пространства и находил следующее наилучшее минимальное значение.

    Image by Author

    Ниже приведен пример взаимодействия доменного пространства между двумя переменными в ограниченной среде. Здесь мы видим, что X и Y являются непрерывными переменными, которые могут находиться в диапазоне от 0 до 2. Однако мы добавляем такое ограничение, что по мере того, как X стремится к 2, Y уменьшается; но если Y стремится к 2, X начинает уменьшаться. Это видно по синему полукольцу, которое представляет допустимое входное пространство, а прозрачный фон представляет собой недопустимое доменное пространство.

    https://en.wikipedia.org/wiki/Nonlinear_programming

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

    Изображение автора

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

    Image By Author

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

    1. Взвешенное агрегирование

    2. Оптимальность по Парето

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

    Изображение автора

    Вот точное определение взвешенного агрегирования:

    Изображение автора

    Оптимальность по Парето — это еще один способ решения MOP путем классификации возможных решений в структуре доминирования. Доминирование — это способ отличить хорошие решения от плохих. Есть два основных типа доминирования: Сильный и Слабый. Сильное доминирование происходит, когда возможное решение равно или лучше другого возможного решения по всем целям и лучше, чем по крайней мере по одной цели. Вот точное определение из учебника:

    Image by Author

    Слабое доминирование, с другой стороны, означает, что возможное решение не хуже другого решения во всех задачах. Вот точное определение:

    Изображение автора

    Для примера обоих типов доминирования здесь у нас есть фигура из учебника с некоторыми переигранными числами, которые я добавил:

    Изображение Автор

    На оси x у нас есть значение F1 а по оси y у нас есть значение F2. В этом сценарии мы хотим минимизировать как F1, так и F2, поэтому абсолютно лучшее решение получается в начале координат, когда F1 == F2 == 0. Точка F обозначена в левом нижнем углу красным кругом. Во-первых, у нас есть все точки, в которых сильно доминирует F, по разделу B. Эти точки сильно доминируются F, поскольку они имеют худшие значения в F1 И в F2. С другой стороны, в разделах A и D преобладает F лишь в незначительной степени, поскольку они имеют лучшие значения по крайней мере по одной цели. Участок A хуже, чем F, с точки зрения F2, так как его значения функции больше, но лучше с точки зрения F1, поскольку его значения функции меньше. Участок D наоборот, хуже F по F1, но лучше по F2. Наконец, у нас есть раздел C, который доминирует над разделами 1, 2, 4 и пунктом F, поскольку этот раздел лучше, чем все остальные функции, по крайней мере, в одной цели, но он равен или лучше, чем в остальных.

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

    Изображение автора

    Как мы видим, минимум возникает, когда оба F1 == F2 == 0; однако проблема в том, что минимальная точка для F1, вероятно, не такая же, как и для F2. Таким образом, мы получаем диапазон значений на выбор. Как указывалось ранее, фронт Парето слабо доминирует над собой, но сильно доминирует над остальной частью доменного пространства; таким образом, возвращение на этот фронт дает пользователю возможность выбирать решения, которые лучше всего соответствуют его потребностям. Например, если F1 важнее для минимизации F2, вы можете выбрать решение со слабым доминированием, которое благоприятствует F1. Вот еще один пример фронта Парето для дискретной задачи:

    Изображение автора

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

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

    Изображение от AuthorImage от AuthorImage от Author

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

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

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

    Image by Author

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

    Это завершает Раздел 1 по теории оптимизации, следите за обновлениями для Раздела 2 по Введению в эволюционные вычисления, методологии решения задач типа оптимизации:

    Модуль 2) Введение в эволюционные вычисления

    Краткий обзор эволюционных вычислений и генетического алгоритма !

    в сторону datascience.com

    Теория оптимизации. Сердце науки о данных | by Saman Siadati

    Фото Diego PH на Unsplash

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

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

    В общем, термин оптимизация относится к процессу, целью которого является поиск наилучших значений одной (или нескольких) целевых функций в определенной области. Иногда при оптимизации одновременно рассматриваются несколько целей; Такие задачи оптимизации, которые включают несколько целевых функций, называются многокритериальными задачами. Простейшим способом решения таких задач является формирование новой целевой функции в виде линейной комбинации основных целевых функций, в которой эффективность каждой функции определяется присвоенным ей весом. Каждая задача оптимизации имеет ряд независимых переменных, которые называются проектными переменными и представлены n-мерным вектором x. (Для получения дополнительной информации, пожалуйста, прочитайте эту статью: Линейная алгебра, скрытый механизм машинного обучения)

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

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

    Различные задачи оптимизации делятся на следующие две категории:

    A) Неограниченные задачи оптимизации: В этих задачах цель состоит в том, чтобы максимизировать или минимизировать целевую функцию без каких-либо ограничений на проектные переменные.

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

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

    При оптимизации в условиях неопределенности или стохастической оптимизации неопределенность комбинируется в модели. Надежные методы оптимизации можно использовать только тогда, когда параметры задачи находятся в определенных границах; В таком случае цель состоит в том, чтобы найти ответ, который выполним для всех данных и оптимально в пространстве поиска или выбора. Стохастические модели оптимизации используют тот факт, что «распределение вероятностей», управляющее данными, известно или оценено. В таком случае цель состоит в том, чтобы найти политику, приемлемую для всех выборок данных и оптимизирующую ожидаемую производительность модели.

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

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

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

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

    Ду, Д. З.; Пардалос, П. М.; Ву, В. (2008). «История оптимизации». Во Флудасе, К.; Пардалос, П. (ред.). Энциклопедия оптимизации. Бостон: Спрингер. стр. 1538–1542.

    А. Г. Маллиарис (2008 г.). «Стохастическое оптимальное управление», Новый экономический словарь Пэлгрейва, 2-е издание

    Сиадати, Саман. (2013). Эволюционные вычисления.10.13140/RG.2.2.36143.15526.

    Херти, М.; Клар, А. (2003–01–01). «Моделирование, симуляция и оптимизация сетей транспортных потоков».