Chaves aleatórias

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ção

A 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

Testar

Pode 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

Visualizar

Para 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()

Executar

Para 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.