Нелинейная многомерная оптимизация - это просто. Часть 3. Имитация отжига

13.10.15

Разработка - Инструментарий разработчика

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

Скачать файлы

Наименование Файл Версия Размер
ИмитацияОтжига.epf
.epf 18,05Kb
31
.epf 18,05Kb 31 Скачать

Сегодня у нас тема для довольно долгого и, надеюсь, интересного разговора - метода имитации отжига.

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

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

Теперь выделим основные черты отжига, которые необходимо смоделировать при поиске решения:

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

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

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

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

3. Температура должна снижаться постепенно и достичь значения, при котором движение атомов полностью прекращается. Это и будет означать окончание процессов отжига и поиска решения.

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

Теперь введем несколько обозначений:

Х - множество значений переменных, составляющих возможное решение задачи оптимизации.

Z(X) - целевая функция, которую возможно рассчитать для любой совокупности Х. Оптимальное решение будет означать минимум данной функции.

Tmax и Tmin - максимальная и минимальная температуры отжига.

Frand(Xi) - функция случайного преобразования решения Xi. Функция произвольная и теоретически должна выбираться с учетом специфики задачи, но на практике замена случайных переменных новыми случайными значениями дает вполне приличный результат. Количество изменяемых на случайные (инвертируемых) переменных также выбирается произвольно. Для гибкости я сделал интенсивность инверсии одним из параметров функции поиска решения.

N - количество итераций поиска решения (длительность отжига).

И под конец распишем алгоритм по шагам:

1. Формируем начальное решение, инициируя Хi случайными значениями. i=0.

2. Устанавливаем температуру.

  

3. Если Тi>Tmin продолжаем. Иначе возвращаем Xi.

4. Вычисляем возможное решение Х* 

 

3. Находим

 

5. Определяем Xi+1. В зависимости от значения ΔZ и текущей температуры вероятность того, что Xi+1 будет равно Х*, выражается формулой:

 

Определяем, переходит ли Х* в Хi+1, бросая монетку. То есть генерируем случайное число от 0 до 1 и сравниваем с вероятностью Р. Если случайное число превысило или равно Р - переход произошел, и мы присваиваем Xi+1=X*, если же Х* не перешло в Хi+1, тогда присваиваем Xi+1= Xi.

6. Увеличиваем счетчик итераций i=i+1. Переходим к шагу 2.

Единственное, что хочется пояснить - это пункт 5 алгоритма. А точнее, формулу  вероятности того, что следующее текущее решение будет хуже предыдущего. Если вспомнить математику, то становится понятным, что дробь тем меньше, чем меньше числитель и чем больше знаменатель, и именно при значениях показателя дроби близких к 0 вероятность перехода к новому решению будет максимальна и близка к 1. Как видим, эта вероятность тем выше, чем меньше разница между оценками целевой функции и чем выше текущая температура. При больших (по модулю) значениях отрицательного показателя степени вероятность перехода к возможному решению стремится к нулю. Например, для числа е показатель по модулю больше пяти дает практически нулевую вероятность того, что система перейдет в новое, менее оптимальное состояние.

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

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

И под конец гифка о том, как решается задача коммивояжера методом имитации отжига на карте США.

 

 

оптимизация имитация отжига алгоритм поиска решения многомерная оптимизация поиск решения

См. также

SALE! 20%

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

Инструментарий разработчика Роли и права Запросы СКД Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

13000 10400 руб.

02.09.2020    122157    670    389    

714

SALE! 25%

Infostart PrintWizard

Пакетная печать Печатные формы Инструментарий разработчика Платформа 1С v8.3 Запросы 1С:Зарплата и кадры бюджетного учреждения 1С:Конвертация данных 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 Платные (руб)

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

18000 15300 руб.

06.10.2023    7292    21    6    

39

SALE! 20%

Infostart УДиФ: Управление данными и формами

Инструменты администратора БД Инструментарий разработчика Роли и права Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

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

10000 8000 руб.

10.11.2023    3537    11    1    

34

SALE! 30%

PowerTools

Инструментарий разработчика Инструменты администратора БД Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Россия Платные (руб)

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

3600 2520 руб.

14.01.2013    177749    1073    0    

849

Многопоточность. Универсальный «Менеджер потоков» 2.1

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Восстановление партий или взаиморасчетов, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

5000 руб.

07.02.2018    99347    239    97    

296

[ЕХТ] Фреймворк для Расширений 1С

Инструментарий разработчика Платформа 1С v8.3 Управляемые формы Платные (руб)

"Фреймворк для Расширений 1С" это универсальное и многофункциональное решение, упрощающее разработку и поддержку создаваемых Расширений. Поставляется в виде комплекта из нескольких Расширений с открытым исходным кодом. Работает в любых Конфигурациях в режиме Управляемого приложения с режимом совместимости 8.3.12 и выше без необходимости внесения изменений в Конфигурацию.

3000 руб.

27.08.2019    18113    6    8    

39

1С HTML Шаблоны / HTML Templates

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Быстрая и удобная обработка для работы с шаблонами HTML. Позволяет легко и быстро формировать код HTML.

2040 руб.

27.12.2017    28110    3    10    

15

Выполнение произвольного кода или запроса с параметрами через Web-сервис (замена COM-подключений)

Инструментарий разработчика Обмен между базами 1C Платформа 1С v8.3 Платные (руб)

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

2400 руб.

24.09.2019    23602    15    15    

32
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. dj_serega 390 13.10.15 14:36 Сейчас в теме
Как всегда круто :)
Но эту публикацию даже знаю где можно взять в работу.
Спасибо.
2. dusha0020 1103 14.10.15 10:18 Сейчас в теме
(1) dj_serega, И Вам спасибо за теплые слова. А где это можно взять в работу - решайте сами. Самая очевидная сфера применения - логистические задачи. Можно оптимизировать не только маршруты, а и загрузку транспорта или размещение ТМЦ на складе и т.д. Главное набраться смелости, сделать презентацию, подсчитать возможную экономию и пойти к начальству с предложением. И сразу обсудить премию в случае успеха:)
3. aspirator23 339 17.10.15 14:33 Сейчас в теме
Гораздо интересней чем бесконечные печатные формы.
Приятно, что число "ильдаровичей" растет.
4. igo1 266 08.12.16 14:35 Сейчас в теме
Отличное решение!!! Спасибо.
При 8000 итераций отжигом, он не очень оптимально работает, так что лучше пользоваться ген алгоритмом.
Оставьте свое сообщение