-
Notifications
You must be signed in to change notification settings - Fork 2
/
GSInverOver.m
156 lines (141 loc) · 6.41 KB
/
GSInverOver.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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
function [fitness_average, distHistory, toctime] = GSInverOver(city_list, dmat, pop, popSize, totalDist, frequency, p, total_iterations)
% Initialization
iter_count = 0;
count = 0;
numIter = total_iterations;
distHistory = zeros(1,numIter);
fitness_average = zeros(1,numIter);
toctime = zeros(1,numIter);
p1 = 0.2;
p2 = 0.9;
maxTimes = 20;
while iter_count < numIter
tic();
iter_count = iter_count + 1;
% % Mapping function
% if mod(iter_count, frequency) == 0
% [city_list, totalDist, dmat] = MappingFunction(city_list, pop, popSize, p, 10);
% end
%
tic();
for i = 1:popSize
current_route = pop(i, :);
[r, route_length] = size(current_route);
city_index = ceil(route_length*rand()); % Randomly select the index for city C from route*
city = current_route(city_index); % The City C from route*
% getting previous and next cities in the route for later
% if it's the first city, previous is the last city
if city_index == 1
prev_city = current_route(route_length);
next_city = current_route(city_index + 1);
% if it's the last city, next is the first city
elseif city_index == route_length
prev_city = current_route(city_index - 1);
next_city = current_route(1);
else
prev_city = current_route(city_index - 1);
next_city = current_route(city_index + 1);
end
while true
p0 = rand();
if p0 < p1
% choose C* randomly from the current route
selected_city_index = ceil(route_length*rand());
while(selected_city_index == city_index)
selected_city_index = ceil(route_length*rand());
end
city_ = current_route(selected_city_index);
elseif p0 < p2
% choose one of the best routes
[~,y] = getNElements(totalDist, 4);
best_routes = pop(y, :);
temp_route_index = ceil(4*rand());
temp_route = best_routes(temp_route_index, :);
city_index_temp_route = find(temp_route == city);
if(city_index_temp_route == route_length) % if the city is the last in the route
city_ = temp_route(1); % set C* to the first city in the route (closed path)
else
city_ = temp_route(city_index_temp_route + 1); % set C* to the next city in the route
end
selected_city_index = find(current_route == city_);
else
temp_route_index = ceil(popSize*rand());
while(temp_route_index == i)
temp_route_index = ceil(popSize*rand());
end
temp_route = pop(temp_route_index, :);
city_index_temp_route = find(temp_route == city);
if(city_index_temp_route == route_length) % if the city is the last in the route
city_ = temp_route(1); % set C* to the first city in the route (closed path)
else
city_ = temp_route(city_index_temp_route + 1); % set C* to the next city in the route
end
selected_city_index = find(current_route == city_);
end
if city_ == prev_city || city_ == next_city
break;
end
% Inversing
if(city_index > selected_city_index)
temp = zeros(1, city_index - selected_city_index);
temp_num = city_index;
count = 0;
for j=selected_city_index+1:city_index
count = count + 1;
temp(count) = current_route(j);
end
for j=1:size(temp, 2)
current_route(temp_num) = temp(j);
temp_num = temp_num - 1;
end
end
if(selected_city_index > city_index)
temp = zeros(1, selected_city_index - city_index);
temp_num = selected_city_index;
count = 0;
for j=city_index+1:selected_city_index
count = count + 1;
temp(1,count) = current_route(j);
end
for j=1:size(temp, 2)
current_route(temp_num) = temp(j);
temp_num = temp_num - 1;
end
end
count = count + 1;
if(count > maxTimes)
break;
end
city = city_;
end
% Calculating total distance of the newly made route
d = dmat(current_route(route_length), current_route(1));
for k = 2:route_length
d = d + dmat(current_route(k-1),current_route(k));
end
new_total_dist = d;
% Keeping the new route if it's better
if new_total_dist < totalDist(i)
totalDist(i) = new_total_dist;
pop(i, :) = current_route;
end
end
% Collecting data about run-time
if(iter_count == 1)
toctime(iter_count) = toc();
else
toctime(iter_count) = toctime(iter_count-1) + toc();
end
% Getting the average distances each generation
fitness_average(iter_count) = mean(totalDist);
% Finding the Best Route in the Population
[minDist,minIndex] = min(totalDist);
distHistory(iter_count) = minDist;
% Collecting data about run-time
if(iter_count == 1)
toctime(iter_count) = toc();
else
toctime(iter_count) = toctime(iter_count-1) + toc();
end
end
end