Поляк Введение В Оптимизацию
Примеры приложений: арбитражная теорема финансовой математики, робастная оптимизация. Введение в оптимизацию.
Введение в оптимизацию, Б. Поляк Ленанд Книга является систематическим введением в довременную теорию и методы оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач - от линейного программирования и безусловной минимизации до стохастического программирования. Обсуждается методика постановки и решения прикладных проблем оптимизации.
Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач. Исследуется влияние помех, негладкости функций, вырожденности минимума. Книга предназначена для инженеров, экономистов, статистиков, вычислителей, сталкивающихся с задачами оптимизации. По своему математическому аппарату книга доступна студентам технических и экономических вузов. Описание Книга является систематическим введением в довременную теорию и методы оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования.
- May 7, 2009 - Москва, Наука, 1983, 384стр. Книга является систематическим введением в современную теорию и методы оптимизации.
- Москва: Наука, 1983. Книга является систематическим введением в современную теорию и методы оптимизации для конечномерных задач.
Охвачен широкий круг задач - от линейного программирования и безусловной минимизации до стохастического программирования. Обсуждается методика постановки и решения прикладных проблем оптимизации. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач. Исследуется влияние помех, негладкости функций, вырожденности минимума. Книга предназначена для инженеров, экономистов, статистиков, вычислителей, сталкивающихся с задачами оптимизации. По своему математическому аппарату книга доступна студентам технических и экономических вузов.
В этой статье я постараюсь максимально доходчиво рассказать о таком простом, но эффективном методе оптимизации, как (simulated annealing). А чтобы не быть причисленным к далёким от практики любителям теоретизировать, я покажу как применить этот метод для решения задачи коммивояжёра. Для понимания статьи Вам понадобятся минимальные навыки программирования и владение математикой на уровне 9 класса средней школы. Статья рассчитана на людей не знакомых с методами оптимизации или только делающих первые шаги в этом направлении.
Чтобы максимально расширить круг читателей, мне пришлось почти полностью отказаться от формальных определений и сознательно пойти на некоторые не совсем точные упрощения. Надеюсь, что с водой я не выплеснул ребёнка (а если это произошло, то буду рад вашим замечаниям). Об оптимизации Для того, чтобы понять, что такое оптимизация, стоит сначала узнать, для чего она нужна. Сразу скажу, что с «задачами оптимизации» в повседневной жизни мы сталкиваемся с завидной регулярностью, не отдавая себе в этом отчёта.
Допустим, мы, получив очередную зарплату, решаем подбить семейный бюджет. Нужно распределить деньги так, чтобы в первую очередь удовлетворить самые важные потребности (еда, плата за электричество, интернет и т.д.), а остаток можно спустить на что-нибудь приоритетом пониже. Купить на все деньги дизайнерский телефон и умереть от голода – не самое лучшее решение, не находите?
Или другой вариант, мы решили отправиться в поход и собираем ранец. Одна проблема – вещей очень много, а ранец у нас не слишком большой (да и сами мы имеем ограниченную грузоподъёмность). Мы хотим взять как можно больше наиболее важных для нас предметов. Если мы идём в горы, прихватить с собой страховочный трос – хорошее решение, взять вместо него любимую PlayStation Vita, а остальное место забить печеньками – наверное, не очень. Так что же делает оптимизация? Она ищет то самое, хорошее решение.
Возможно, не самое лучшее из всех, но точно хорошее. Теперь чуточку формальнее. Если заглянуть в википедию, можно без труда найти вот такое определение: Оптимальное (от лат. Optimus — наилучшее) решение — решение, которое по тем или иным признакам предпочтительнее других. Следовательно, оптимизация – это способ нахождения оптимального решения.
Теперь, давайте представим, что мы можем измерить насколько хорошее наше решение. Например, в случае «задачи про ранец», каждой вещи присвоим натуральное число (чем больше число, тем важнее вещь). Тогда наша задача приобретает уже более чёткую постановку: мы хотим заполнить ранец такими вещами, суммарный приоритет которых будет максимален, а вес не превысит определенного значения.
Мы ищем максимум некоторой функции, которую принято называть целевой. Чтобы свести всё к единому знаменателю, снова заглянем в википедию: Оптимизация (математика) — нахождение экстремума (минимума или максимума) целевой функции в некоторой области. Теперь, когда мы более-менее определились, с тем, что делает оптимизация, появляется резонный вопрос – «Как?».
Конечно, мы можем особо не заморачиваться и перебрать все-все решения, а затем сравнить их. В случае с ранцем, нам, наверное, даже это удастся проделать. Но теперь давайте представим, что наш ранец – вовсе не ранец, а целый поезд с множеством вагонов, а перевозим мы разные товары в другой город.
Задача не изменилась (загрузить как можно больше ценного), а целевой функцией будет суммарная стоимость товаров. Сколько времени уйдёт у нас на полный перебор решений? Думаю, что много. Можно выбирать решения случайно. Допустим, сто каких-нибудь решений, а затем из них взять самое лучшее. Несомненно, это будет значительно быстрее полного перебора, но кто даст гарантию, что наше итоговое решение будет сколько-нибудь близко к экстремуму? Не буду томить и скажу, что существует великое множество.
Настолько много, что их принято разбивать на классы, все их я перечислять не буду. Скажу лишь, что «имитация отжига» относится к классу стохастических (от греч. Στοχαστικός — « умеющий угадывать») или вероятностных методов.
А причём здесь вероятность и как она поможет отыскать решение – чуть ниже. Имитация отжига Как и всё гениальное, данный метод подсмотрен у матушки природы. За основу взят процесс кристаллизации вещества, который в свою очередь «приручили» хитрые металлурги, для повышения однородности металла.
Напомню, что у каждого металла есть кристаллическая решетка, если совсем коротко, она описывает геометрическое положение атомов вещества. Совокупность позиций всех атомов будем называть состоянием системы, каждому состоянию соответствует определенный уровень энергии. Цель отжига – привести систему в состояние с наименьшей энергией. Чем ниже уровень энергии, тем «лучше» кристаллическая решетка, т.е. Тем меньше у нее дефектов и прочнее металл. В ходе «отжига» металл сначала нагревают до некоторой температуры, что заставляет атомы кристаллической решетки покинуть свои позиции.
Затем начинается медленное и контролируемое охлаждение. Атомы стремятся попасть в состояние с меньшей энергией, однако, с определенной вероятностью они могут перейти и в состояние с большей. Эта вероятность уменьшается вместе с температурой.
Переход в худшее состояние, как ни странно, помогает в итоге отыскать состояние с энергией меньшей, чем начальная. Процесс завершается, когда температура падает до заранее заданного значения. Как видите, в рамках данного процесса происходит минимизация энергии. Меняем энергию на нашу целевую функцию, и voilà! Давайте задумаемся, а чем же так хорош столь мудрёный процесс? Почему бы нам, например, всегда не переходить в состояния с меньшей энергией? Примерно так работает имеющий широкое распространение метод.
На просторах интернета мне удалось отыскать совершенно чудесную картинку, которая как нельзя лучше иллюстрирует все плюсы алгоритма. Давайте на минуточку представим себя лыжником, несущемся по крутому склону нашей целевой функции. Задача спуститься в самую нижнюю точку (глобальный минимум). Но, как видите, склон нам попался не совсем ровный, есть на нём низменности, заехав в которые, нам может показаться, что мы уже у подножья. Дабы не остаться в дураках, нам придётся проявить любопытство и вскарабкаться на небольшой холмик, чтобы продолжить спуск.
Чтобы метафора стала окончательно понятна, в примере с лыжником склон – функция измерения энергии вещества (она же целевая функция). А вероятностный переход в состояние с большей энергией – карабканье на холм справа от низменности.
Как видите, такой алгоритм позволяет нам с большой вероятностью избежать «застревания» в локальном минимуме. Теперь мы готовы перейти к более строгому описанию метода. Введём обозначения: Пусть S – множество всех состояний (решений) нашей задачи. Например, для задачи о ранце это будет множество всевозможных наборов вещей. Пусть – состояние на i-м шаге алгоритма. – температура на i-м шаге.
Для того, чтобы использовать имитацию отжига, нам понадобится определить три функции:. Функцию энергии или, проще говоря, то что мы оптимизируем. Функцию изменения температуры с течением времени.
На всякий случай оговорюсь, что она обязательно должна быть убывающей. Функцию, порождающую новое состояние. Теперь остановимся на каждой подробнее. E каждому решению по какому-то правилу ставит в соответствие число.
Зависит от конкретной задачи. T ставит номеру итерации i в соответствие температуру. Функция определяет, как долго будет работать наш алгоритм (на самом деле она имеет более глубокое значение, но нам это знать пока не обязательно).
Если T будет линейной функцией, то время работы будет относительно большим. В случае же со степенной функцией, скажем, всё закончится очень быстро, но далеко не факт, что мы не застрянем в низменности, так не добравшись до финиша. Для этой статьи я выбрал самый простой, линейный вариант. Function T = DecreaseTemperature( initialTemperature, i)%initialTemperature - начальная температура%i - номер итерации T = initialTemperature. 0.1 / i; end Сразу оговорюсь, что весь код в этой статье был написан. Эту среду я выбрал, так как «из коробки» можно рисовать красивые графики – не более. Писать я старался, не используя специфичной матлабной магии, чтобы код можно было легко портировать на Ваш любимый язык.
Функция F на основе предыдущего состояния порождает новое состояние-кандидат, в которое система может перейти, а может и отбросить. Обозначим его. Способ получения кандидата полностью зависит от решаемой задачи, конкретную функцию Вы сможете увидеть в примере. Теперь мы можем в самом общем виде описать алгоритм метода имитации отжига:. На входе: минимальная температура, начальная температура. Задаём произвольное первое состояние.
Пока. Если, тогда. Если переход осуществляется с вероятностью. Понижаем температуру.
Возвращаем последнее состояние s Как видите, всё очень просто, отдельно стоит пояснить только переход в новое состояние. Если энергия «кандидата» меньше, он становится новым состоянием, в противном случае, переход будет вероятностным (поэтому метод относят к классу стохастических). Чтобы это точно не вызывало трудностей, я позволю себе напомнить некоторые самые базовые понятия теории вероятностей. Неформально определим вероятность, как меру возможности наступления некоторого события.
Вероятность достоверного события (событие, которое точно случится) равна единице, невозможного – нулю. Все остальные значения находятся между. Например, при броске игральной кости вероятность выпадения любого числа равна единице, а тройки – 1/6.
В нашем случае, подставив в формулу значения разницы энергий и температуры мы получим вероятность перехода. Остаётся только этот переход осуществить, но как это сделать? Код вычисления вероятности: function P = GetTransitionProbability( dE, T ) P = exp(-dE/T); end Давайте представим себе единичный отрезок и разобьём его на две части относительно значения нашей вероятности. Если число попало в левую часть – осуществляем переход, в правую – не делаем ничего. Function a = IsTransition(probability) value = rand(1); if(value. Данные можно без труда получить в Matlab при помощи следующего кода: data = rand(2,100).10; В других языках придётся написать цикл, но по сути это ничего не меняет. Мы генерируем случайные числа уже знакомой нам функцией rand и домножаем их на 10, чтобы они лежали в заданной области.
Решение задачи методом имитации отжига Обозначим множество всех городов C, общее количество обозначается C и в нашем случае равно 100. Каждый город представляется как пара координат с соответствующим индексом.
По условию, решением является маршрут между всеми городами, значит множество состояний S – это все возможные маршруты, проходящие через каждый город. Другими словами множество всех упорядоченных последовательностей элементов C, в которой всякий встречается ровно один раз.
Очевидно, что длина каждой такой последовательности C. Как мы помним, для того, чтобы использовать метод имитации отжига мы должны определить две функции, зависящие от каждой конкретной задачи. Это функция энергии E (или «целевая функция» в общепринятой терминологии) и функция F, порождающая новое состояние.
Так как мы стремимся минимизировать расстояние, оно и будет «энергией». Следовательно, наша целевая функция будет иметь такой вид. Где Теперь давайте подумаем, как же нам получать новое состояние? Первое что приходит в голову – менять местами два произвольных города в маршруте. Идея правильная, но такое изменение непредсказуемо влияет на, метод будет работать долго и не факт, что успешно. Хорошим вариантом в данном случае будет выбрать два произвольных города в маршруте и инвертировать путь между ними.
Например, у нас был маршрут (1,2,3,4,5,6,7). Генератор случайных чисел выбрал города 2 и 7, мы выполнили процедуру и получили (1,7,6,5,4,3,2).
Ниже представлен код для функции F: function seq = GenerateStateCandidate(seq)%seq - предыдущее состояние (маршрут), из которого%мы хотим получить состояние-кандидат n = size(seq,1);% определяем размер последовательности i = randi(n,1);% генерируем целое случайное число j = randi(n, 1);% генерируем целое случайное число if(i j) seq(j:i) = flipud(seq(j:i));% обращаем подпоследовательность else seq(i:j) = flipud(seq(i:j));% обращаем подпоследовательность end end Теперь у нас есть всё что нужно, и мы можем начать процесс оптимизации. Но прежде чем мы перейдём к самому интересному, я приведу полный код программы. Однако, стоит отметить, что не смотря на то, что алгоритм в текущей реализации работает достаточно эффективно (точно гораздо быстрее полного перебора), есть мнение, что можно добиться куда лучшего времени без потери «качества». Для этого предлагаю Вам, в качестве практического задания поэкспериментировать с функцией T и поделиться результатами в комментариях. Исходные коды можно скачать. Надеюсь, что прочтённое оказалось полезным для вас. Конструктивная критика приветствуется.
Пользуясь случаем, хотел бы поблагодарить Антонову Анну и Дмитрия Игнатова, которые прочли статью перед публикацией и дали мне несколько хороших советов. Метки:. Добавить метки Пометьте публикацию своими метками Метки необходимо разделять запятой. Например: php, javascript, андронный коллайдер, задача трех тел. Не могли бы вы добавить в статью сравнение этого метода с генетическим алгоритмом? Плюсы и минусы этих методов относительно друг-друга.
Поляк Введение В Оптимизацию
Ведь в целом они похожи, но хотелось бы увидеть, когда какой следует применять. Я вот несколько раз применял ген.
Алг для различных задач, в частности для обучения многослойного перцептрона — получил весьма интересные результаты, но с методом из вашей статьи знаком только понаслышке и не знаю его преимуществ и недостатков относительно ген. Алга (в частности, в вопросе обучения НС) Upd: не увидел ваше заключение, прошу прощения. Но вопрос остается открытым, и, на мой взгляд, ответ на него даже важнее реализации метода имитации отжига в матлабе. Интересный метод. Спасибо за наглядное описание. Надо бы попробовать его приспособить к задачам решения нелинейных уравнений.
Иногда, вместо решения сложной системы многих переменных f(x1.xn) = 0 можно попытаться минимизировать каким-нибудь образом построенную из этих уравнений функцию, например, сумму их квадратов (что абсолютно естественно для комплексных чисел — минимизация квадрата модуля). Возможно, этот метод себя сможет хорошо проявить, в отличие от многомерных секущих (плохо сходятся) или Ньютона-Рафсона (жутко долго писать и неудобно вычислять производные, если функция не задана аналитически). Поиск кратчайшего пути по «бразильской» системе! Очень напоминает как много-много стартапов 99% из которых проваливается в итоге рождают что-нибудь в духе эппл или макрософт! Конечно в реальной жизни множество особенностей, но метод отжига заполнил очень большой кусок в картине того, как реальный человек (или структура состоящая из людей) взаимодействует с миром!
И прямо так руки к чешутся взять и применить этот алгоритм к какой-нибудь олимпиадной задачке из школьных времен. Такое чувство, что множество хитрых задачек сведутся к одному алгоритму и будут проходить 90% тестов:). Собственно, в этом и сидит физический аспект алгоритма. Чистая термодинамика и никакой магии. Вероятность пребывания системы в состоянии с энергией E при температуре T равна C.exp(-E/T), где С — нормировочный множитель.
Это свойство общее для любых макроскопических систем и известно под названием распределения Гиббса. Вероятность состояния с энергией повыше равна, соответственно, C.exp(-(E+dE)/T).
А вероятность перехода между двумя этими состояниями равна экспоненте, в которой вместо энергии стоит dE — если условно принять нижний уровень за основное состояние (считать, что для него E=0 — в случае с потенциальной энергией именно это и можно сделать), как раз и получим, что вероятность попасть в состояние с энергией dE равна exp(-dE/T), только нормировка C здесь будет пересчитана. Очень интересная и крайне доступно написанная статья! Что можете сказать про скорость такого алгоритма и точность относительно других методов? Я занимался подобными изысканиями. Мне нужно было найти не только глобальный экстремум, но и максимально исследовать все локальные экстремумы! Разработал новый алгоритм, который не стремится к глобальному экстремуму, а удаляет из пространства исследования все минимумы и сходится ко всем экстремумам.
Метод оказался эффективнее и удобнее по сравнению с теми, которые я ранее использовал. Буду рад, если вы как эксперт оцените мой алгоритм, а то я прямых аналогов ему пока не нашел.
Спасибо, статья пришлась кстати. Попробую «метод отжига» (MO) при случае на своих реальных данных. На практике приходится работать с оптимизацией и еще один метод не помешает. Пользуясь случаем, хотелось бы обсудить пару моментов.
На правоту не претендую, скорее рассуждаю вслух. Главное, на что я хочу обратить внимание: предпочтение одного метода другому определяется в первую очередь характером ваших данных. Это из личного опыта.
Так, например, может и не быть большого смысла применять МО в задаче коммивояжера с простым (как в примере) — равномерным распределением городов по некоторой плоскости. Здесь вполне прилично справится метод монотонного спуска (ММС). Ну или преимущества МО еще прийдется поискать и доказать. Проблема возможной сходимости к локальным максимумам (что призван преодолеть МО), по моему мнению, возникнет тогда, когда в расположении городов будет присутствовать выраженная кластеризация. Другая возможность — если функция генерации нового состояния почему-то из каких-то тактических соображений работает не затрагивает весь набор «городов. Вид и свойствацелевой функции (как вычисляется „энергия“) тоже будут влиять.
Первое что приходит в голову – менять местами два произвольных города в маршруте. Идея правильная, но такое изменение слишком слабо влияет на E, метод будет работать долго и не факт, что успешно.
По-моему, наоборот. Такое изменение, напротив, сильно влияет на E и, вероятнее всего, его увеличивает. Вот что говорит на этот счет английская википедия: In the traveling salesman problem above, for example, swapping two consecutive cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two arbitrary cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbour generator is expected to perform better than the arbitrary-swap one. Да, Вы правы, тут ошибка. Попробую объяснить почему. Если представить города в виде графа, то видно, что для того, чтобы поменять местами два произвольных города нужно изменить четыре ребра.
Поляк Б.т. Введение В Оптимизацию
В случае, когда мы «переворачиваем» подпоследовательность — изменяется только два. Следовательно, влияние на E меньше (что хорошо). Futanaliz 8.1 ключ.
Тогда встаёт вопрос почему вторая эвристика лучше? Тут Википедия совершенно права, при перестановке двух произвольных элементов вероятность получить плохое состояние выше. Попытаюсь проиллюстрировать на примере: Меняем A и B. Даже получив выигрыш за счёт ребер XB и AY, мы много потеряли на последовательности между A и B (рёбра BZ и WA). В случае с другим способом генерации, мы меняем только два ребра, не трогая саму подпоследовательность и гарантировано не делая её хуже. Такое объяснение, конечно, не подходит на роль полноценного доказательства. Постараюсь, когда будет больше свободного времени найти правильные слова и дополнить статью.
Спасибо за замечание. 1.Мы случайно экспериментируем с функцией T (временем или количеством итераций, что у вас там). А вдруг при 10T найдется лучшее решение? И при 100T еще лучшее?
Как оценить точность приближения? (тест в студию, где заранее полностью просчитаны глобальный минимум и локальные минимумы и при различных T как успешно ваша программа находит глобальный минимум) 2.Область обсчета и точки заведомо конечны. Что будете делать, когда они огромны (почти бесконечны)?
Как оценивать будете, что в таком-то направлении считать невыгодно, а в другом выгодно и в какой момент программа остановится? 3.Предлагаю вам написать ваш программу на Lua и посмотреть, насколько выгодно она находит глобальный минимум в самых жестких условиях, где ваш алгоритм будет конкурировать с другими известными алгоритмами при поиске максимально выгодного свертывания белков — на foldit. Очень хорошая и интересная статья!
Местами, на мой вкус, слишком формализовано, но это я говорю как человек который более-менее «в теме». Для людей, впервые знакомящихся с данным материалом, зато будет легко вникнуть и разобраться. Данный пост сподвиг меня на написание на эту же тему. Вернее, конкретно эта фраза: «Первое что приходит в голову – менять местами два произвольных города в маршруте. Идея правильная, но такое изменение непредсказуемо влияет на, метод будет работать долго и не факт, что успешно.». Я как раз недавно сам решал задачу коммивояжера и придумал очень похожий на метод отжига алгоритм и использовал как раз идею случайного обмена местами двух городов.
Кому интересно — почитайте.