-
Notifications
You must be signed in to change notification settings - Fork 18
/
ACO.m
112 lines (89 loc) · 3.12 KB
/
ACO.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
% Ant Colony Opimization - Ant Colony System for Hybird Job Shop Sceduling
% Problem.
function [costs, bestSol] = ACO(jobs, m, n, ants, iterations, ...
rzero, costFunc)
costEnd = 0;
costs = [];
bestSol = ones(1, n);
bestSolCost = costFunc(bestSol, jobs, m, n);
phermone = ones(n, m*m); % track phermone value on each path.
for i = 1:iterations
antPaths = []; % stores all antPaths
for a = 1:ants;
antPath = []; % current ants path
for l = 1:n % going down n layers in total
phermoneToNextLevel = [];
if l == 1 % layer 1 to n mapping
for j = 1:m
phermoneToNextLevel(j) = phermone(1, j);
end
else % rest layers are n to n mapping
lastNode = antPath(l-1);
phermoneRow = l;
phermoneColS = (lastNode - 1) * m + 1;
phermoneColF = lastNode * m;
phermoneToNextLevel = phermone(phermoneRow, ...
phermoneColS:phermoneColF);
end
randVal = rand(1);
weights = phermoneToNextLevel;
testPath = antPath; % copy current ant path to calculate distance
for mi = 1:m
testPath(l) = mi;
% Construct a matrix to memorize this for better performance
distance = costFunc(testPath, jobs, m, l) - costFunc(antPath, ...
jobs, m, l-1);
weights(mi) = weights(mi) / (distance+1);
end
totalWeight = sum(weights);
weightAcc = 0;
nextIndex = 0;
if rand(1) < rzero % experience vs exploration
nextIndexs = find(weights == max(weights));
nextIndex = nextIndexs(randi(numel(nextIndexs)));
else
while randVal > (weightAcc / totalWeight)
nextIndex = nextIndex + 1;
weightAcc = weightAcc + weights(nextIndex);
end
end
antPath(l) = nextIndex;
end
antPaths(a, :) = antPath;
end
antCosts = [];
% Find costs for all ant paths. Consider to use a vectoralization
% version of cost function for this process in matlab.
for a = 1:ants
antCosts(a) = costFunc(antPaths(a,:), jobs, m, n);
end
bestAntCost = min(antCosts);
worstAntCost = max(antCosts);
bestAntPaths = antPaths(find(antCosts==bestAntCost), :);
% Update phermone
phermone = phermone .* 0.4;
if bestAntCost <= bestSolCost
% ONLY THE GLOBAL BEST ALLOW TO UPDATE
deltaPhermone = 1 / bestAntCost;
for s = 1:size(bestAntPaths, 1)
bestAntPath = bestAntPaths(s,:);
for ji = 1:n
pcol = 0;
if ji == 1 % first job
pcol = bestAntPath(ji);
else
lastNode = bestAntPath(ji - 1);
pcol = (lastNode - 1) * m + bestAntPath(ji);
end
phermone(ji, pcol) = phermone(ji, pcol) + deltaPhermone;
end
end
end
costEnd = costEnd + 1;
costs(costEnd) = bestAntCost;
if bestAntCost < bestSolCost
bestSol = bestAntPaths(1,:);
bestSolCost = bestAntCost;
end
end
end