8-Queen_Genetic

#!/usr/bin/env python

import random
import string


def random_individual(size):
    return [random.randint(1, size) for _ in range(size)]


maxFitness = 28


def calculate_fitness(individual):
    horizontal_collisions = sum([individual.count(queen) - 1 for queen in individual]) / 2
    diagonal_collisions = 0

    n = len(individual)
    left_diagonal = [0] * 2 * n
    right_diagonal = [0] * 2 * n
    for i in range(n):
        left_diagonal[i + individual[i] - 1] += 1
        right_diagonal[len(individual) - i + individual[i] - 2] += 1

    diagonal_collisions = 0
    for i in range(2 * n - 1):
        counter = 0
        if left_diagonal[i] > 1:
            counter += left_diagonal[i] - 1
        if right_diagonal[i] > 1:
            counter += right_diagonal[i] - 1
        diagonal_collisions += counter / (n - abs(i - n + 1))

    return int(maxFitness - (horizontal_collisions + diagonal_collisions))


def calculate_probability(individual):
    return calculate_fitness(individual) / maxFitness


def random_pick(population, probabilities):
    population_with_probability = zip(population, probabilities)
    total = sum(w for c, w in population_with_probability)
    r = random.uniform(0, total)
    up_to = 0
    for c, w in zip(population, probabilities):
        if up_to + w >= r:
            return c
        up_to += w
    assert False, "Shouldn't get here"


def cross_over(x, y):
    n = len(x)
    c = random.randint(0, n - 1)
    return x[0:c] + y[c:n]


def mutate(x):
    n = len(x)
    c = random.randint(0, n - 1)
    m = random.randint(1, n)
    x[c] = m
    return x


def genetic_queen(population):
    mutation_probability = 0.03
    new_population = []
    probabilities = [calculate_probability(n) for n in population]
    for i in range(len(population)):
        x = random_pick(population, probabilities)
        y = random_pick(population, probabilities)
        child = cross_over(x, y)
        if random.random() < mutation_probability:
            child = mutate(child)
        print_individual(child)
        new_population.append(child)
        if calculate_fitness(child) == 28: break
    return new_population


def genetic_queen_with_best_probabilities(population):
    population.sort(key=lambda t: calculate_probability(t),
                    reverse=True)

    fittest_population = population[0: (len(population) // 2)]
    new_population = []
    for individual in fittest_population:
        random_position = random.randint(0, len(fittest_population) - 1)
        other1 = fittest_population[random_position]
        random_position = random.randint(0, len(fittest_population) - 1)
        other2 = fittest_population[random_position]

        child1 = cross_over(individual, other1)
        if calculate_fitness(child1) <= calculate_fitness(individual):
            child1 = mutate(child1)

        child2 = cross_over(individual, other2)
        if calculate_fitness(child2) <= calculate_fitness(individual):
            child2 = mutate(child2)

        new_population.append(child1)
        new_population.append(child2)
        if calculate_fitness(child1) == 28: break
        if calculate_fitness(child2) == 28: break
    for i in new_population:
        print_individual(i)

    return new_population


def print_individual(x):
    print("{},  fitness = {}, probability = {:.6f}"
          .format(str(x), calculate_fitness(x), calculate_probability(x)))


if __name__ == "__main__":
    population = [random_individual(8) for _ in range(100)]
    generation = 1

    # genetic_queen_with_best_probabilities(population)

    while 28 not in [calculate_fitness(x) for x in population]:
        print("=== Generation {} ===".format(generation))
        population = genetic_queen_with_best_probabilities(population)
        print("Maximum fitness = {}".format(max([calculate_fitness(n) for n in population])))
        generation += 1

    print("Solved in Generation {}!".format(generation - 1))
    for x in population:
        if calculate_fitness(x) == 28:
            print_individual(x)