1
\$\begingroup\$

I used uniform crossover to solve eight queens problem. It is taking more than an hour to get the result. Is there any way to reduce the running time or improve the crossover to solve eight queens problem? Following is the code:

import random
import numpy as np
from math import gamma as G

def random_chromosome(size): #making random chromosomes 
    return [ random.randint(1, nq) for _ in range(nq) ]

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

    n = len(chromosome)
    left_diagonal = [0] * 2*n
    right_diagonal = [0] * 2*n
    for i in range(n):
        left_diagonal[i + chromosome[i] - 1] += 1
        right_diagonal[len(chromosome) - i + chromosome[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)) #28-(2+3)=23


def probability(chromosome, fitness):
    return fitness(chromosome) / maxFitness

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

#Uniform crossover
def reproduce(x, y): #doing cross_over between two chromosomes
    n = len(x)
    c = random.randint(0, n - 1)
    x = c*x+(1-c)*y; 
    y = c*y+(1-c)*x;
    
    return x[0:c] + y[c:n] 

def mutate(x):  #randomly changing the value of a random index of a chromosome
    n = len(x)
    c = random.randint(1,n-1)
    m = random.randint(1, n)
    x[c] = m
    #x = x+[c];
    #y = y+[c];
    return x

def genetic_queen(population, fitness):
    mutation_probability = 0.03
    #eta_m=20
    
    new_population = []
    probabilities = [probability(n, fitness) for n in population]
    for i in range(len(population)):
        x = random_pick(population, probabilities) #best chromosome 1
        y = random_pick(population, probabilities) #best chromosome 2
        child = reproduce(x, y) #creating two new chromosomes from the best 2 chromosomes
        if random.random() < mutation_probability:
            child = mutate(child)
        print_chromosome(child)
        new_population.append(child)
        if fitness(child) == maxFitness: break
    return new_population

def print_chromosome(chrom):
    print("Chromosome = {},  Fitness = {}"
        .format(str(chrom), fitness(chrom)))

if __name__ == "__main__":
    nq = int(input("Enter Number of Queens: ")) #say N = 8
    maxFitness = (nq*(nq-1))/2  # 8*7/2 = 28
    population = [random_chromosome(nq) for _ in range(50)]

    generation = 1

    while not maxFitness in [fitness(chrom) for chrom in population]:
        print("=== Generation {} ===".format(generation))
        population = genetic_queen(population, fitness)
        print("")
        print("Maximum Fitness = {}".format(max([fitness(n) for n in population])))
        generation += 1
    chrom_out = []
    print("Solved in Generation {}!".format(generation-1))
    for chrom in population:
        if fitness(chrom) == maxFitness:
            print("");
            print("One of the solutions: ")
            chrom_out = chrom
            print_chromosome(chrom)

    board = []

    for x in range(nq):
        board.append(["x"] * nq)

    for i in range(nq):
        board[nq-chrom_out[i]][i]="Q"


    def print_board(board):
        for row in board:
            print (" ".join(row))

    print()
    print_board(board)

where x and y are offspring.

I am not sure uniform crossover is more suitable for eight queens problem. At last I am getting the following output,

Maximum Fitness = 28 Solved in Generation 2972!

One of the solutions: Chromosome = [6, 4, 7, 1, 3, 5, 2, 8], Fitness = 28

x x x x x x x Q

x x Q x x x x x

Q x x x x x x x

x x x x x Q x x

x Q x x x x x x

x x x x Q x x x

x x x x x x Q x

x x x Q x x x x

Any answer regarding this will be appreciated.

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

The number of potential crossovers is much larger (read: exponentially) than the number of solutions since the next crossover can easily end up in the same row, column or (not covered by your code:) diagonal occupied by an earlier queen. Keeping track of the state (previous generations) to quickly prune branches that are doomed to fail would certainly help, but in the end you'd just be implementing an "ordinary" algorithm. So I'm inclined to answer as follows: don't use crossover.

PS: just to make sure I'm not misunderstood: the key problem of using crossover here is that next generations/sub-solutions don't nicely converge towards an optimum.

\$\endgroup\$
3
  • \$\begingroup\$ What your are saying is correct. Here I am using Evolutionary Algorithms to implement eight queens problems, so need to use crossover or mutation to create offspring. I am wondering is there any crossover or mutation would reduce running time of my code. \$\endgroup\$
    – Chandan
    Jul 23, 2021 at 7:05
  • \$\begingroup\$ I understand that, but I don't believe it exists. The whole foundation of this approach is essentially that the probability of stumbling upon a solution is an increasing function of the number of generations, and for this particular problem I can't imagine such a function exists. I admit there's a big chunk of intuition behind my reasoning and I'm no expert, so keep looking. \$\endgroup\$
    – Koen AIS
    Jul 23, 2021 at 8:18
  • \$\begingroup\$ PS: I'm not the author of the imperative solution that was posted. If I had thought you'd be interested in such a version I would simply have posted a link to some (more solid-looking) implementation. \$\endgroup\$
    – Koen AIS
    Jul 23, 2021 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.