CODEWITHSUNDEEP
pythongenetic-algorithmn-queens
John Fekoter
John Fekoter

Reputation: 35

Genetic Algorithm for 8 queens puzzle

I'm trying to apply genetic algorithm for 8 queens puzzle. I've coded whole algorithm but it keeps getting stuck when it finds solution with 6 unhit queens and can't get over it. I feel like there's some diversity problem but I can't figure out what to do with it. My question is what is wrong with this realisation and why it keeps getting stuck on 6 unhit queens and can't make a final move? I've already examined every bit of code and I think there's some misinterpretation of algorithm itself evolved. That's why I attached whole code. So I hope that someone would tell me where I did wrong. Thanks in advance.

    def mutate(self, children):
        rnd.seed()
        count = 0
        for child in children:
            count += 1
            if rnd.random() < self.mut_prob:
                i = rnd.randrange(0, 7)
                ind = child[i].index(1)
                child[i][ind] = 0
                j = rnd.randrange(0, 7)
                child[i][j] = 1



    def solve(self, min_fitness= 7, max_epochs=100):
        prev_pop = self.initial_population()
        epochs = 0
        max_fitness = 0

        while (max_fitness <= min_fitness) and (epochs < max_epochs):
            fitness = self.fitness_function(prev_pop)
            fitness.sort(key=lambda tup: tup[1])

            best_sol = fitness[len(fitness) - 1][0]
            max_fitness = fitness[len(fitness) - 1][1]
            mating = self.roulette(fitness)

            mating_chromes = []
            pop = copy.deepcopy(prev_pop)
            for chrom in mating:
                mating_chromes.append(pop[chrom])
            pop.clear()

            children = self.crossover(mating_chromes)
            self.mutate(children)
            fit = self.fitness_function(prev_pop)


            to_destroy = self.reduction(fitness)

            for el in to_destroy:
                prev_pop[el] = children.pop(0)

            epochs += 1
        print(max_fitness)
        print(epochs)
        for el in prev_pop[best_sol]:
            print(el)
            print("\n")
        print("im fine")
        return 0

s = Solver_8_queens()
arr = s.solve()

Upvotes: 0

Views: 2601

Answers (1)

kindanoob
kindanoob

Reputation: 623

One problem with your code is the way you use Python function random.randrange(). The documentation says that randrange(a, b) will return a random number x such that a <= x < b (note that b is not included).

When you write something like i = random.randrange(0, 7) you will get a random number from the semi-open interval [0, 7), while what you (most likely) want is the number from closed interval [0, 7], because board size is 8x8. So check all calls to randrange(), fix them if they are incorrect and see whether it solves the problem.

Upvotes: 3

Related Questions