O
problema do caixeiro viajante (TSP) é nosso velho conhecido: alguém pretende visitar um certo número de cidades, uma e uma só vez, regressando à cidade de origem. Quer minimizar o custo da viagem, entendido aqui pela menor distância percorrida. Como em qualquer problema envolvendo algoritmos evolucionários a primeira questão que se coloca é a da representação das soluções candidatas. A solução mais evidfewnte é uma permutação de inteiros, que nos obriga a escolher posteriormente com cuidado os operadores de variação. Mas existem alternativas. Uma recorre às chamadas chaves aleatórias (
random keys). Trata-se de vectores de reais, entre 0 e 1 que permitem representar permutações. A vantagem é a de que se podem usar os operadores de variação simples para reais. Claro que necessitamos de estabelecer uma relação entre um vector de reais e uma permutação. O código para o fazer é trivial:
def decode_rk(vector):
aux = deepcopy(vector)
aux.sort()
permutation =[ vector.index(elem) + 1 for elem in aux]
return permutation
Ordenamos o vector e procuramos a sua posição no vector original!
O algoritmo para o TSP segue o modelo habitual de um algoritmo evolucionário.
def ea_tsp_rk(numb_cities,fitness,population_size,sel_parents,sel_survivals,mutation,
prob_mutation,crossover, prob_crossover,num_generations):
"""
numb_cities = number of cities
fitness = to calculate the fitness : city matrix
"""
population = random_population(numb_cities,population_size)
population = evaluate_population(population,fitness)
list_best_generation = [best_population(population)[1]]
for i in range(num_generations):
print 'gener %d\n' % i
aux_pop = copy.deepcopy(population)
mates = sel_parents(aux_pop)
offspring = crossover(mates, prob_crossover)
offspring = mutation(offspring,prob_mutation)
offspring = evaluate_offspring(offspring,fitness)
population = sel_survivals(population,offspring)
list_best_generation.append(best_population(population)[1])
print 'FINAL BEST: ',list_best_generation[-1]
return list_best_generation
O algoritmo utilizado recorre a uma selecção por torneio, mutação gaussiana, cruzamento uniforme e selecção de sobreviventes de estado estável.
Selecção por torneio de tamanho 5
def sel_parents(population):
"""Tournament of size 5."""
new_pop = []
for i in range(len(population)):
indiv = tournament(population, 5)
new_pop.append(indiv)
return new_pop
def sel_tournament(population,size):
"""Tournament of size."""
new_pop = []
for i in range(len(population)):
indiv = tournament(population, size)
new_pop.append(indiv)
return new_pop
def tournament(population, size):
"""Minimization problem."""
group = random.sample(population,size)
group.sort(key=operator.itemgetter(1))
return group[0]
Mutação Gaussiana
def mutation(offspring, prob_mutation):
new_off = [mutation_one(child,prob_mutation) for child in offspring]
return new_off
def mutation_one(off,prob_mutation):
""" Gaussian mutation."""
muta = random.random()
if muta < prob_mutation:
cromo = off[0]
index = random.randint(0,len(cromo)-1)
value = cromo[index]
delta = random.gauss(0,1.0)
while not in_bounds(value + delta):
delta = random.gauss(0,1.0)
cromo[index] = value + delta
return [cromo,0]
else:
return off
def in_bounds(value):
return (0.0 <= value <= 1.0)
Cruzamento Uniforme
def uniform_crossover(mates,prob_crossover):
random.shuffle(mates)
off = []
for i in range(0,len(mates)-1,2):
off.extend(uni_cross(mates[i][0],mates[i+1][0],prob_crossover))
return off
def uni_cross(cromo_1, cromo_2,prob_cross):
value = random.random()
if value < prob_cross:
f1=[]
f2=[]
for i in range(0,len(cromo_1)):
if random.random() < 0.5:
f1.append(cromo_1[i])
f2.append(cromo_2[i])
else:
f1.append(cromo_2[i])
f2.append(cromo_1[i])
return [[f1,0],[f2,0]]
else:
return [[cromo_1,0],[cromo_2,0]]
Selecção Estado Estável
def sel_survivals(population,offspring):
""" mu + lambda."""
all_pop = population + offspring
all_pop.sort(key=operator.itemgetter(1))
return all_pop[:len(population)]
AvaliaçãoA avaliação é feita no fenótipo, isto é, numa permutação de inteiros, usando uma matriz de distâncias.
def evaluate_population(population,fitness):
population = [[individual[0],evaluate(fenotype(individual[0]), fitness)] for individual in population]
return population
def evaluate_offspring(offspring,fitness):
return evaluate_population(offspring,fitness)
def fenotype(genotype):
"""From a random key to a permutation."""
aux = copy.deepcopy(genotype)
aux.sort()
permutation =[ genotype.index(elem) for elem in aux]
return permutation
def evaluate(tour, city_matrix):
numb_cities = len(tour)
cost = 0
for i in range(numb_cities):
j = (i+1) % numb_cities
cost += city_matrix[tour[i]][tour[j]]
return cost
TestarPode testar o algoritmo gerando a sua própria matriz de distâncias:
def create_distance_matrix(size):
matrix = [ [0] * size for i in range(size)]
for i in range(size):
for j in range(i+1,size):
value = random.randint(500,1500)
matrix[i][j] = matrix[j][i] = value
return matrix
VisualizarPara ver o resultado:
def visualize_fitness(list_values):
x = range(1,len(list_values)+1)
y = list_values
plt.title('Best Fitness')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.plot(x,y,'r-o')
#plt.savefig('one_and_one.png')
plt.show()
ExecutarPara executar (cuidasdo que pode demorar muito tempo....)
def main_all(num_runs, algorithm,problem):
all_best = []
for i in range(num_runs):
best = algorithm(problem[0],problem[1],50, sel_parents, sel_survivals,mutation,\
0.1, uniform_crossover, 0.7,1000)
all_best.append(best)
transformed = zip(*all_best)
best_best = [max(gener) for gener in transformed]
average_best = [sum(gener) / float(num_runs) for gener in transformed]
visualize_fitness(average_best)
Exemplo No nosso caso usámos a matriz das distâncias das 29 cidades do Sahara Ocidental (ver ficheiro wi29.tsp na InforEstudante ou procure pelo nome usando um motor de busca. este ficheiro guarda as
coordenadas das cidades que têm que ser transformadas em distâncias). O resultado óptimo é 27603.
A solução óptima.
Uma execução.
