CODEWITHSUNDEEP
matlabsimulated-annealing
Ehsan Jkr
Ehsan Jkr

Reputation: 31

How to implement Simulated Annealing algorithm in Matlab as a Local Search phase of an evolutionary algorithm?

I’m working on an evolutionary algorithm. The code is implemented in Matlab. The “Local Search” step is as follows:

%% 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

The algorithm works well and there is an acceptable output. To improve the output, I’ve decided to use “Simulated Annealing” algorithm in the local search phase. Here is my proposed implementation, which is replaced by the above mentioned Local Search:

%% 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

The code runs with no error. However, the output is exactly the same as that of the “old” local search approach. Apparently, this code doesn’t affect the whole process of the evolutionary algorithm (but the run time). Could you please tell me what’s wrong with my SA algorithm implementation?

I’m not also sure about the initialization values of the SA variables. Any suggestion for this?

Upvotes: 0

Views: 1211

Answers (1)

Rui Valente
Rui Valente

Reputation: 91

I'm not sure about your code, however I constructed a pseudo-code of the SA method, given an objective function f, the domain interval Omega, the neighborhood function N used to calculate the random vector z^k and the maximum temperature T_0. Moreover, I assumed that the temperature is updated at every iteration:

enter image description here

Comparing this with your code, I see that:

  1. You are not applying the min function between 1 and your value P

  2. The values T0 and alpha have always to be adjusted to the function you want to minimize, yet the value of T0 must be much higher, and alpha lower.

  3. The SA method requires a lot of iterations, try to increase it!

  4. About the initialization values of the SA variables, you should be as random as you can inside the domain. During the loop you can generate the new values with, p.e., a normal distribution (the function in matlab is normrnd) with the best value as avg point of the distribution.

Hope it helped!

Upvotes: 1

Related Questions