Permuta-me as viagens

Em post anterior já falámos no problema do caixeiro viajante. Agora mostramos uma solução alternativa, recorrendo a permutações de inteiros. Os operadores de variação são a mutação por troca e o cruzamento por ordem. Sem mais explicações deixamos o código.

""" Basic Evolutionary Algorithms for the TSP problem.
Representation = integers permutation. """

__author__ = 'Ernesto Costa'
__date__ ='April 2012'

import math
import random
import copy
import operator

# ---
import matplotlib.pyplot as plt

# Main function

def ea_tsp_permutation(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

# Generate population
def random_population(dim, pop_size):
    pop = []
    for i in range(pop_size):
 indiv = range(dim)
 random.shuffle(indiv)
 pop.append([indiv,0])
    return pop

def best_population(population):
    pop = copy.deepcopy(population)
    pop.sort(key= operator.itemgetter(1))
    return pop[0]
    
    
# Selection parents
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 tournament(population, size):
    group = random.sample(population,size)
    group.sort(key=operator.itemgetter(1))
    return group[0]

# Mutation
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):
    """ Swap mutation."""
    muta = random.random()
    if muta < prob_mutation:
 cromo = off[0]
 i,j = random.sample(range(len(cromo)),2)
 cromo[i],cromo[j] = cromo[j],cromo[i]
 return [cromo,0]
    else:
 return off

# Crossover

def crossover(mates,prob_crossover):
    random.shuffle(mates)
    off = []
    for i in range(0,len(mates)-1,2):
 off.extend(order_cross(mates[i][0],mates[i+1][0],prob_crossover))
    return off

# OX - order crossover
def order_cross(cr_1,cr_2,prob_cross):
 size = len(cr_1)
 value = random.random()
 if value < prob_cross:
     pc= random.sample(range(size),2)
     pc.sort()
     pc1,pc2 = pc
     f1 = [None] * size
     f2 = [None] * size
     f1[pc1:pc2+1] = cr_2[pc1:pc2+1]
     f2[pc1:pc2+1] = cr_1[pc1:pc2+1]
     indexes = range(pc2+1,size) + range(pc1)
     j = k = pc2 + 1
     for i in indexes:  
  while cr_1[j%size] in f1:
      j += 1
  f1[i%size] = cr_1[j%size]
  j += 1
  while cr_2[k%size] in f2:
      k += 1
  f2[i%size] = cr_2[k%size]
  k += 1
     return [[f1,0],[f2,0]]
 else:
     return [[cr_1,0],[cr_2,0]]

 
# Selection of the survivals
def sel_survivals(population,offspring):
    """ mu + lambda."""
    all_pop = population + offspring
    all_pop.sort(key=operator.itemgetter(1))
    return all_pop[:len(population)]
 
def sel_survivals_elite(population,offspring):
    """ Elitism."""
    population.sort(key=operator.itemgetter(1))
    offspring.sort(key=operator.itemgetter(1), reverse=True)
    elite = int(0.05 * len(population))
    all_pop = population[:elite] + offspring[elite:]
    random.shuffle(all_pop)
    return all_pop


# Evaluation of the fitness
def evaluate_population(population,fitness):
    population = [[individual[0],evaluate(individual[0], fitness)] for individual in population]
    return population

def evaluate_offspring(offspring,fitness):
    return evaluate_population(offspring,fitness)
 
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


# Create data if needed
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

# Simple visualization
   
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()
 
      
def main(num_runs, algorithm,problem):
    all_best = []
    for i in range(num_runs):
        best = algorithm(problem[0],problem[1],150, sel_parents, sel_survivals_elite,mutation,\
                          0.01, crossover, 0.8,5000)
        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)