TSP Genetic Algorithm

tsp_ga.py

from random import sample, uniform, randrange, shuffle


def is_circuit(chromosome):
    global adj_mat
    if adj_mat[chromosome[0]][chromosome[-1]] == -1:
        return False
    for i in range(len(chromosome) - 1):
        if adj_mat[chromosome[i]][chromosome[i+1]] == -1:
            return False
    return True


def dist(chromosome, i, j):
    return adj_mat[chromosome[i]][chromosome[j]]


def is_hamiltonian_circuit(chromosome):
    global adj_mat

    if not is_circuit(chromosome):
        return False

    if dist(chromosome, 0, -1) == -1:
        return False

    for i in range(len(chromosome) - 1):
        if dist(chromosome, i, i+1) == -1:
            return False

    for i in range(chromosome_len):
        if i not in chromosome:
            return False
    return True


def create_first_generation():
    global chromosome_len, population
    l = [i for i in range(chromosome_len)]
    first_generation = []
    while len(first_generation) <= population:
        new_chromosome = sample(l, len(l))
        # TODO
        if not is_hamiltonian_circuit(new_chromosome) or new_chromosome in first_generation:
            continue
        first_generation.append(new_chromosome)
    return first_generation


def fitness(chromosome):
    global adj_mat
    if not is_hamiltonian_circuit(chromosome):
        return 0

    path_len = 0
    for i in range(len(chromosome) - 1):
        path_len += dist(chromosome, i, i+1)
    return 1./path_len


def weighted_choice(choices):
    total = sum(w for c, w in choices)
    if total == 0:
        return sample(choices, 1)[0][0]
    r = uniform(0, total)
    upto = 0
    for c, w in choices:
        if upto + w >= r:
            return c
        upto += w
    assert False, "Shouldn't get here"


def find_maximum_fitness():
    global generation
    max_index = 0
    for i in range(len(generation)):
        if fitness(generation[i]) > fitness(generation[max_index]):
            max_index = i
    return max_index, generation[max_index], fitness(generation[max_index])


def selection():
    global generation
    generation_fitness = []
    for chromosome in generation:
        generation_fitness.append((
            chromosome[:],
            fitness(chromosome)
        ))

    selected = []
    while len(selected) <= 2:
        new_chromosome = weighted_choice(generation_fitness)
        selected.append(new_chromosome)

        # TODO check if chromosome was not here

    loop = 0
    while selected[0] == selected[1]:
        new_chromosome = weighted_choice(generation_fitness)
        selected[1] = new_chromosome
        loop += 1
        if loop > 10:
            selected[1] = sample(generation, 1)[0]

    return selected[0], selected[1]


def crossover():
    global generation, crossover_probability, chromosome_len, best_chromosome_ever

    max_index, max_chromosome, max_fitness = find_maximum_fitness()
    new_generation = [max_chromosome]

    if best_chromosome_ever is None:
        best_chromosome_ever = max_chromosome[:]
    elif max_fitness > fitness(best_chromosome_ever):
        best_chromosome_ever = max_chromosome[:]
    else:
        new_generation.append(best_chromosome_ever[:])

    random_chromosome = [i for i in range(chromosome_len)]
    while not is_hamiltonian_circuit(random_chromosome):
        shuffle(random_chromosome)
    new_generation.append(random_chromosome[:])

    shuffle(random_chromosome)
    new_generation.append(random_chromosome[:])

    while len(new_generation) <= len(generation):
        selected1, selected2 = selection()
        if selected1 == selected2:
            continue
        prob = randrange(0, 100) / 100.
        if prob <= crossover_probability:
            pivot = randrange(0, chromosome_len)
            new_chromosome = selected1[:pivot] + selected2[pivot:]
            if new_chromosome in new_generation:
                continue
            new_generation.append(new_chromosome)
        else:
            first_or_second = randrange(0, 2)
            if first_or_second == 0:
                new_generation.append(selected1)
            else:
                new_generation.append(selected2)

    return new_generation


def mutation():
    global population, generation, mutation_probability, chromosome_len
    new_generation = []
    for i in range(population):
        prob = randrange(0, 100) / 100.
        if prob <= mutation_probability:
            index = randrange(0, chromosome_len)
            data = randrange(0, chromosome_len)
            new_chromosome = generation[i][:]
            new_chromosome[index] = data
            new_generation.append(new_chromosome)
        else:
            new_generation.append(generation[i])

    return new_generation


def print_to_file_each_generation(generation_number):
    global generation, output_file
    max_index, max_chromosome, max_fitness = find_maximum_fitness()

    output_file.write("%d %f %d\n" %(
        generation_number, max_fitness, max_index
    ))
    for chromosome in generation:
        output_file.write("%s %f\n"%(
            chromosome,
            fitness(chromosome)
        ))


def compute_path_len(chromosome):
    path_len = 0
    for i in range(len(chromosome) - 1):
        path_len += dist(chromosome, i, i+1)

    return path_len


def main_function():
    global adj_mat, generation
    for i in range(chromosome_len):
        adj_mat.append([int(j) for j in input_file.readline().split()])

    # print(adj_mat)

    generation = create_first_generation()
    print_to_file_each_generation(-1)
    # print(generation)

    for i in range(generation_count):
        generation = crossover()
        generation = mutation()

        print_to_file_each_generation(i)
        print(i)

    max_index, max_chromosome, max_fitness = find_maximum_fitness()
    output_file.write("\n\n%s\n" % max_chromosome)

    if is_hamiltonian_circuit(max_chromosome):
        print(compute_path_len(max_chromosome))
    else:
        print("Wrong Output")


if __name__ == '__main__':
    input_file = open(input(), 'r')
    population = int(input_file.readline())
    chromosome_len = int(input_file.readline())
    generation_count = int(input_file.readline())
    crossover_probability = float(input_file.readline())
    mutation_probability = float(input_file.readline())
    output_file = open(input_file.readline(), 'w')

    adj_mat = []
    generation = []
    best_chromosome_ever = None

    main_function()