139 lines
5.7 KiB
Python
139 lines
5.7 KiB
Python
import math
|
|
import random
|
|
from model.base_model import Model
|
|
|
|
class MyACOModel(Model):
|
|
def __init__(self):
|
|
super().__init__()
|
|
|
|
class Edge:
|
|
def __init__(self, a, b, weight, initial_pheromone):
|
|
self.a = a
|
|
self.b = b
|
|
self.weight = weight
|
|
self.pheromone = initial_pheromone
|
|
|
|
class Ant:
|
|
def __init__(self, alpha, beta, num_nodes, edges):
|
|
self.alpha = alpha
|
|
self.beta = beta
|
|
self.num_nodes = num_nodes
|
|
self.edges = edges
|
|
self.tour = None
|
|
self.distance = 0.0
|
|
|
|
def _select_node(self):
|
|
roulette_wheel = 0.0
|
|
unvisited_nodes = [node for node in range(self.num_nodes) if node not in self.tour]
|
|
heuristic_total = 0.0
|
|
for unvisited_node in unvisited_nodes:
|
|
heuristic_total += self.edges[self.tour[-1]][unvisited_node].weight
|
|
for unvisited_node in unvisited_nodes:
|
|
roulette_wheel += pow(self.edges[self.tour[-1]][unvisited_node].pheromone, self.alpha) * \
|
|
pow((heuristic_total / self.edges[self.tour[-1]][unvisited_node].weight), self.beta)
|
|
random_value = random.uniform(0.0, roulette_wheel)
|
|
wheel_position = 0.0
|
|
for unvisited_node in unvisited_nodes:
|
|
wheel_position += pow(self.edges[self.tour[-1]][unvisited_node].pheromone, self.alpha) * \
|
|
pow((heuristic_total / self.edges[self.tour[-1]][unvisited_node].weight), self.beta)
|
|
if wheel_position >= random_value:
|
|
return unvisited_node
|
|
|
|
def find_tour(self):
|
|
self.tour = [random.randint(0, self.num_nodes - 1)]
|
|
while len(self.tour) < self.num_nodes:
|
|
self.tour.append(self._select_node())
|
|
return self.tour
|
|
|
|
def get_distance(self):
|
|
self.distance = 0.0
|
|
for i in range(self.num_nodes):
|
|
self.distance += self.edges[self.tour[i]][self.tour[(i + 1) % self.num_nodes]].weight
|
|
return self.distance
|
|
|
|
def init(self, nodes):
|
|
super().init(nodes)
|
|
|
|
# Set hypter-parameters
|
|
mode=['ACS']
|
|
colony_size=10
|
|
elitist_weight=1.0
|
|
min_scaling_factor=0.001
|
|
alpha=1.0
|
|
beta=3.0
|
|
rho=0.1
|
|
pheromone_deposit_weight=1.0
|
|
initial_pheromone=1.0
|
|
labels = None
|
|
|
|
self.mode = str(mode[0])
|
|
self.colony_size = colony_size
|
|
self.elitist_weight = elitist_weight
|
|
self.min_scaling_factor = min_scaling_factor
|
|
self.rho = rho
|
|
self.pheromone_deposit_weight = pheromone_deposit_weight
|
|
self.num_nodes = len(nodes)
|
|
self.nodes = nodes
|
|
|
|
if labels is not None:
|
|
self.labels = labels
|
|
else:
|
|
self.labels = range(1, self.num_nodes + 1)
|
|
self.edges = [[None] * self.num_nodes for _ in range(self.num_nodes)]
|
|
for i in range(self.num_nodes):
|
|
for j in range(i + 1, self.num_nodes):
|
|
self.edges[i][j] = self.edges[j][i] = self.Edge(i, j, math.sqrt(
|
|
pow(self.nodes[i][0] - self.nodes[j][0], 2.0) + pow(self.nodes[i][1] - self.nodes[j][1], 2.0)),
|
|
initial_pheromone)
|
|
self.ants = [self.Ant(alpha, beta, self.num_nodes, self.edges) for _ in range(self.colony_size)]
|
|
self.global_best_tour = None
|
|
self.global_best_distance = float("inf")
|
|
|
|
def _add_pheromone(self, tour, distance, weight=1.0):
|
|
pheromone_to_add = self.pheromone_deposit_weight / distance
|
|
for i in range(self.num_nodes):
|
|
self.edges[tour[i]][tour[(i + 1) % self.num_nodes]].pheromone += weight * pheromone_to_add
|
|
|
|
def _acs(self, max_it):
|
|
for step in range(0, max_it):
|
|
# print('[step]', step)
|
|
for ant in self.ants:
|
|
self._add_pheromone(ant.find_tour(), ant.get_distance())
|
|
if ant.distance < self.global_best_distance:
|
|
self.global_best_tour = ant.tour
|
|
self.global_best_distance = ant.distance
|
|
self.fitness_list.append(ant.distance)
|
|
for i in range(self.num_nodes):
|
|
for j in range(i + 1, self.num_nodes):
|
|
self.edges[i][j].pheromone *= (1.0 - self.rho)
|
|
|
|
def _elitist(self, max_it):
|
|
for step in range(0, max_it):
|
|
# print('[step]', step)
|
|
for ant in self.ants:
|
|
self._add_pheromone(ant.find_tour(), ant.get_distance())
|
|
if ant.distance < self.global_best_distance:
|
|
self.global_best_tour = ant.tour
|
|
self.global_best_distance = ant.distance
|
|
self.fitness_list.append(ant.distance)
|
|
self._add_pheromone(self.global_best_tour, self.global_best_distance, weight=self.elitist_weight)
|
|
for i in range(self.num_nodes):
|
|
for j in range(i + 1, self.num_nodes):
|
|
self.edges[i][j].pheromone *= (1.0 - self.rho)
|
|
|
|
def fit(self, max_it=1000):
|
|
"""
|
|
Execute simulated annealing algorithm.
|
|
"""
|
|
# Initialize with the greedy solution.
|
|
if self.mode == 'ACS':
|
|
self._acs(max_it)
|
|
elif self.mode == 'Elitist':
|
|
self._elitist(max_it)
|
|
else:
|
|
print("Un supported")
|
|
# print('Sequence : <- {0} ->'.format(' - '.join(str(self.labels[i]) for i in self.global_best_tour)))
|
|
# print('Total distance travelled to complete the tour : {0}\n'.format(round(self.global_best_distance, 2)))
|
|
|
|
return self.global_best_tour, self.fitness_list
|