Как реализовать алгоритм имитации отжига в Matlab как фазу локального поиска эволюционного алгоритма? - PullRequest
Новая
       21

Как реализовать алгоритм имитации отжига в Matlab как фазу локального поиска эволюционного алгоритма?

0 голосов
/ 04 апреля 2019

Я работаю над эволюционным алгоритмом.Код реализован в Matlab.Шаг «Локальный поиск» выглядит следующим образом: 

%% Local Search
for iter2 = 1:MaxIter2
v = ceil(number_Best*rand);
w = ceil(number_Best*rand);
Best1 = Best_History(v,:);
Best2 = Best_History(w,:);
[New_Best,New_fBest] = two_way(Best1,Best2,SE,nodes_number);
Best_History = [Best_History;New_Best];
fBest_History = [fBest_History;New_fBest];
end

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

%% Local Search
%SA Parameters
MaxIt=40;      % Maximum Number of Iterations
MaxSubIt=15;    % Maximum Number of Sub-iterations
T0=0.025;       % Initial Temp.
alpha=0.99;     % Temp. Reduction Rate

% Initialize Temp.
T=T0;

for iter2 = 1:MaxIt
    for subit=1:MaxSubIt
 v = ceil(number_Best*rand);
 w = ceil(number_Best*rand);
 Best1 = Best_History(v,:);
 Best2 = Best_History(w,:);
 [New_Best,New_fBest] = two_way(Best1,Best2,SE,nodes_number);

if New_fBest>=fBest_History 
        Best_History = [Best_History;New_Best];
        fBest_History = [fBest_History;New_fBest];


    else 

        DELTA=(New_fBest-fBest_History)/fBest_History;

        P=exp(-DELTA/T);
        if rand<=P
            Best_History = [Best_History;New_Best];
            fBest_History = [fBest_History;New_fBest];
        end

end

% Update Best Solution Ever Found
    if New_fBest>=fBest_History 
        Best_History = [Best_History;New_Best];
        fBest_History = [fBest_History;New_fBest];
    end

end


% Store Best Solution Ever Found
Best_History = [Best_History;New_Best];
fBest_History = [fBest_History;New_fBest];

% Update Temp.
T=alpha*T;  

end

Код работает без ошибок.Однако вывод точно такой же, как и у «старого» подхода локального поиска.По-видимому, этот код не влияет на весь процесс эволюционного алгоритма (но время выполнения).Не могли бы вы сказать мне, что не так с моей реализацией алгоритма SA?

Я также не уверен в значениях инициализации переменных SA.Любое предложение для этого?

1 Ответ

1 голос
/ 04 апреля 2019

Я не уверен в вашем коде, однако я создал псевдокод метода SA, учитывая целевую функцию f , интервал домена Omega, функцию окрестности N используется для вычисления случайного вектора z ^ k и максимальной температуры T_0 . Более того, я предположил, что температура обновляется на каждой итерации:

enter image description here

Сравнивая это с вашим кодом, я вижу, что:

  1. Вы не применяете функцию min между 1 и вашим значением P

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

  3. Метод SA требует много итераций, попробуйте увеличить его!

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

Надеюсь, это помогло!

...