Алгоритм имитации отжига:

Чтобы решить проблему локального оптимального решения, Киркпатрик и др. предложили алгоритм имитации отжига (SA) в 1983 году, который может эффективно решить проблему локального оптимального решения. Мы знаем, что в мире молекул и атомов чем выше энергия, тем нестабильнее молекулы и атомы, а чем ниже энергия, тем стабильнее атомы. «Отжиг» — это физический термин, который относится к процессу нагревания и охлаждения объекта. Алгоритм имитации отжига исходит из процесса охлаждения кристалла.Если твердое тело не находится в самом низком энергетическом состоянии, нагрейте твердое тело, а затем охладите его.Поскольку температура медленно падает, атомы в твердом теле располагаются в определенной форме, чтобы образуют правильные кристаллы с высокой плотностью и низкой энергией, что соответствует глобальному оптимальному решению в алгоритме. И если температура падает слишком быстро, это может привести к тому, что атомы не успеют организоваться в кристаллическую структуру, в результате чего получится аморфная структура с более высокой энергией, что является локальным оптимальным решением. Поэтому, согласно процессу отжига, к нему можно добавить немного энергии, а затем охладить.Если увеличить энергию, то локальное оптимальное решение может выскочить.На этот раз отжиг проходит успешно, и мы объясним в подробно опишите, как это происходит в локальном оптимальном решении.Оптимальное решение переходит в глобальное оптимальное решение:

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

Предполагая, что начальное состояние находится в A, с количеством итераций, обновленным до локального оптимального решения B, обнаруживается, что при обновлении до B способность ниже, чем у A, а это означает, что она близка к оптимальной. решение, поэтому оно передается на 100% и состояние достигает B. После этого обнаруживается, что энергия на следующем шаге возросла.Если это градиентный спуск, ему не разрешается продолжать движение вперед.Здесь он будет прыгать из этой ямы с определенной вероятностью.Каждая вероятность связана с текущим состоянием,энергией и т.д.,о чем будет подробно сказано ниже.Скажем,если В наконец выскочит и дойдет до С,то и дальше будет выскакивать с определенной вероятностью Некоторых людей может смутить, перепрыгнут ли они обратно на предыдущую Б? Как поясняется ниже, он стабилизируется до тех пор, пока не будет достигнуто значение D. Поэтому расчет этой вероятности очень важен, и нижеследующее поясняется с математической точки зрения.

Предположим, что предыдущее состояние x(n) , система по определенному показателю (градиентный спуск, энергия предыдущего участка) переходит в состояние $x(n+1)$ , соответственно, энергия системы определяется выражением E(n) стать $E(n+1)$ , система определяется x(n) стать $x(n+1)$ Вероятность принятия P:

$P = \left\{\begin{matrix} 1, E(n+1)<E(n)& \\ & \\ & \\ e^{-\frac{E(n+1) - E(n)}{T}}, E(n+1) \geq E(n)& \end{matrix}\right.$

Из приведенной выше формулы видно, что если энергия уменьшается, то передача принимается (с вероятностью 1), если энергия увеличивается, то это означает дальнейшее отклонение системы от глобального оптимального значения. алгоритм не будет немедленно отброшен, и будет выполнена вероятностная операция: сначала будет сгенерировано равномерно распределенное случайное число в интервале [0,1] $\varepsilon$ ,если $\varepsilon$ P передача принимается, в противном случае передача отклоняется, и вводится следующий шаг, и цикл возвратно-поступательный. Среди них P определяется изменением энергии, а T определяет размер вероятности P, поэтому эта величина является динамической.

Управление параметрами алгоритма отжига

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

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

(2) Скорость отжига. Самый простой способ спуска — экспоненциальный спуск:

$T(n) = \lambda T(n) ,n =1,2,3,.....$

в $\lambda$ является положительным числом меньше 1, обычно между 0,8 и 0,99. Так что для каждой температуры достаточно попыток переноса, скорость сходимости экспоненциального спуска относительно медленная, а другие методы спуска следующие:

$T(n) = \frac{T(0)}{log(1+t)}$

$T(n) = \frac{T(0)}{1+t}$

(3) Температура окончания

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

Шаги для имитации отжига:

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

2. Основная идея имитации отжига:

(1) Инициализация: начальная температура T (достаточно большая), начальное состояние решения S (которое является начальной точкой итерации алгоритма), количество итераций L для каждого значения T

(2) Выполните шаги с (3) по 6 для k=1, …, L:

(3) Создать новое решение S′

(4) Рассчитайте приращение ΔT=C(S′)-C(S), где C(S) — функция стоимости.

(5) Если ΔT

(6) Если условие завершения выполнено, вывести текущее решение как оптимальное и завершить программу.

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

(7) Т постепенно уменьшается, и Т->0, затем переходим к шагу 2.

Генерацию и принятие новых решений алгоритма имитации отжига можно разделить на следующие четыре этапа:

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

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

Третий шаг заключается в том, чтобы оценить, принято ли новое решение или нет. Решение основано на критерии приемлемости. Наиболее часто используемым критерием приемлемости является критерий Метрополиса: если ΔT

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

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

Блок-схема программы алгоритма отжига;

Описание проблемы планирования работы магазина

Job Shop Scheduling (JSP) — одна из самых классических NP-сложных задач. Области его применения чрезвычайно широки, включая планирование авианосцев, планирование самолетов в аэропортах, планирование грузовых судов в портах и пристанях, линии обработки автомобилей и т. д.

Описание проблемы JSP: система обработкиMмашина для обработкиNдомашнее задание, из них домашнее заданиеiКоличество включенных шагов равноLi. порядок, тоL- общее количество операций в наборе задач. Среди них определено время обработки каждого процесса, и каждая операция должна быть обработана в соответствии с последовательностью процессов. Задача планирования состоит в том, чтобы организовать последовательность планирования обработки всех заданий таким образом, чтобы можно было оптимизировать показатели производительности при соблюдении ограничений.

При планировании работы цеха необходимо учитывать следующие ограничения:

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

Cons2: Одна машина может обрабатывать только одно задание в определенное время;

Cons3: Каждое задание может быть обработано только 1 раз на 1 машине;

Cons4: Последовательность процесса и время обработки каждой операции известны и не изменятся при изменении последовательности обработки.

Экземпляр проблемы

Ниже приведен пример задачи планирования цеха заданий, где каждый процесс отмечен парой значений (m, p), где m означает, что текущий процесс должен быть обработан на m-й машине, а p означает, что m-я машина обрабатывает текущий Время обработки, необходимое для процесса. (Примечание: нумерация машин и заданий начинается с 0)
jop0=[(0,3),(1,2),(2,2)]
jop1=[(0,2),(2,1),(1,4)]
jop2=[(1,4),(2,3)]
В этом примере задание jop0 имеет 3 операции: его 1-я операция помечена (0,3), что означает, что 1-я операция должна выполняться на 0-й машине и требует 3 единиц времени обработки; ее второй процесс помечен (1,2), что означает, что второй процесс должен выполняться на первой машине и требует 2 единицы времени обработки, то же верно и для остальных. Всего в этом примере 8 операций.
Возможным решением этой проблемы является перестановка L=8 моментов начала процесса, которая удовлетворяет ограничениям задачи. На следующем рисунке показан пример допустимого решения (примечание: это решение не является оптимальным):
在这里插入图片描述

clc
clear
%=========数据录入，参数调整=================
swarminitNum=20;%初始生成的粒子数；
 
MM=[1 2 3 4 5 6 
    6 6 6 6 6 6];%工件、工序数量矩阵，MM第一行表示工件，第二行表示每个工件的工序数；
 
machineNum=6;   %加工机器数；
 
initT=1000;          %模拟退火初始温度；
 
gen=500;        %循环迭代数；
 
w1=0.35;          %变异率；
 
changeNum=3;     %变异变换对数；
 
restrictmatrixM=[3     1     2     4     6     5
                 2     3     5     6     1     4
                 3     4     6     1     2     5
                 2     1     3     4     5     6
                 3     2     5     6     1     4
                 2     4     6     1     5     3];%job-shop机器约束矩阵；
             
restrictmatrixT=[1     3     6    7      3     6
                 8     5     10   10     10    4
                 5     4     8     9     1     7
                 5     5     5     3     8     9
                 9     3     5     4     3     1
                 3     3     9     10    4     1];%job-shop时间约束矩阵；
             
%===============PSO算法==========================
swarminit=cell(1,swarminitNum);
swarminitLong=sum(MM(2,:));          %所有工序数即粒子长度；
for i=1:swarminitNum,
    swarminit{i}=randomparticle(MM) ;
end                                  %随机生成初始粒子群体
[popu,s] = size(swarminit); 
trace = ones(1,gen); 
trace(1) = 10000; % 初始全局最佳适应度设为足够大 
for i = 1:s,
    bestfit(i) = 10000; % 初始个体历史最佳适应度设为足够大 
end
bestpar = swarminit; % 个体历史最佳粒子初始化
for u=1:swarminitNum,
    fitlist=[0]; 
end
T=initT;
for step = 1:gen,
    for q=1:swarminitNum,
            
       swarminit{j}=cross(bestparticle1,swarminit{j},l4,l3);%粒子交叉；
   end 
end
[a,b,c]=timedecode2(bestparticle,restrictmatrixM,restrictmatrixT,machineNum);
disp(['优化目标: 最小平均流动时间'])
disp(['粒子数:' int2str(swarminitNum)  '   循环代数:' int2str(gen)])
disp(['变异率:' num2str(w1)  '   变异变换对数:' int2str(changeNum)])
disp(['模拟退火初始值:' int2str(initT)  '  模拟退火终值:' int2str(T)])
disp(['迭代循环值:' int2str(trace)])
disp(['最小平均流动时间:' int2str(a)  '   最大完工时间:'  int2str(b)  '   最小间隙时间:' int2str(c) ])
disp(['最优粒子' int2str(bestparticle)])
pause
gant(bestparticle,swarminitLong,restrictmatrixM,restrictmatrixT,b)