8皇后难题的遗传算法

Question

我正在尝试将遗传算法应用于 8 皇后拼图。我已经编写了整个算法，但是当它找到具有 6 个未命中皇后的解决方案并且无法克服它时，它会一直卡住。我觉得存在一些多样性问题，但我不知道该怎么办。我的问题是这种认识有什么问题，为什么它一直卡在 6 个未命中的皇后上，无法做出最后一步？我已经检查了每一段代码，我认为对算法本身的演变存在一些误解。这就是为什么我附上整个代码。所以我希望有人能告诉我我哪里做错了。提前致谢。

    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()

Answer 1

您的代码有一个问题是您使用 Python 函数 random.randrange() 的方式。 documentation 表示 randrange(a, b) 将 return 一个随机数 x 使得 a <= x < b （注意 b 不包括在内）。

当你写类似 i = random.randrange(0, 7) 的东西时，你会从半开区间 [0, 7) 中得到一个随机数，而你（最有可能）想要的是闭区间 [=17] 中的数字=]，因为电路板尺寸为 8x8。所以检查所有对 randrange() 的调用，如果它们不正确就修复它们，看看它是否解决了问题。

8皇后难题的遗传算法

Genetic Algorithm for 8 queens puzzle

python

genetic-algorithm

n-queens