给我一份用遗传算法解决数独问题的代码
时间: 2023-12-16 21:04:51 浏览: 45
以下是一份使用遗传算法解决数独问题的 Python 代码:
```python
import random
# 定义数独棋盘
puzzle = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
# 定义遗传算法参数
POPULATION_SIZE = 100
MUTATION_RATE = 0.1
GENERATIONS = 1000
def fitness(solution):
"""计算解的适应度"""
score = 0
# 计算行适应度
for row in solution:
score += len(set(row))
# 计算列适应度
for col in zip(*solution):
score += len(set(col))
# 计算九宫格适应度
for i in range(0, 9, 3):
for j in range(0, 9, 3):
square = [solution[x][y] for x in range(i, i+3) for y in range(j, j+3)]
score += len(set(square))
return score
def generate_individual():
"""生成随机解"""
individual = []
for i in range(9):
row = []
for j in range(9):
if puzzle[i][j] == 0:
row.append(random.randint(1, 9))
else:
row.append(puzzle[i][j])
individual.append(row)
return individual
def crossover(parent1, parent2):
"""交叉操作"""
child = []
for i in range(9):
row = []
for j in range(9):
if random.random() < 0.5:
row.append(parent1[i][j])
else:
row.append(parent2[i][j])
child.append(row)
return child
def mutate(solution):
"""变异操作"""
for i in range(9):
for j in range(9):
if random.random() < MUTATION_RATE:
solution[i][j] = random.randint(1, 9)
return solution
def genetic_algorithm():
"""遗传算法"""
population = [generate_individual() for _ in range(POPULATION_SIZE)]
for generation in range(GENERATIONS):
# 计算适应度
fitness_scores = [(solution, fitness(solution)) for solution in population]
fitness_scores.sort(key=lambda x: x[1], reverse=True)
# 选择操作
elite_size = POPULATION_SIZE // 10
elites = [fitness_scores[i][0] for i in range(elite_size)]
selection_probs = [f[1] for f in fitness_scores]
selection_probs = [p / sum(selection_probs) for p in selection_probs]
parents = random.choices(population, weights=selection_probs, k=POPULATION_SIZE-elite_size)
# 交叉操作
offspring = []
for i in range(0, len(parents), 2):
parent1 = parents[i]
parent2 = parents[i+1]
child = crossover(parent1, parent2)
offspring.append(child)
# 变异操作
mutated_offspring = [mutate(child) for child in offspring]
# 新一代种群
population = elites + mutated_offspring
print(f"Generation {generation+1}: Best score = {fitness_scores[0][1]}")
if fitness_scores[0][1] == 243:
# 找到最优解,结束算法
return fitness_scores[0][0]
# 没有找到最优解,返回适应度最高的解
return fitness_scores[0][0]
# 运行遗传算法,输出最优解
solution = genetic_algorithm()
for row in solution:
print(row)
```
代码中首先定义了一个数独棋盘,然后通过遗传算法求解数独问题。具体来说,每个解都是一个 $9\times9$ 的矩阵,其中未知数用随机数填充。每一代种群都由上一代的优良解经过交叉和变异产生。交叉操作使用单点交叉,变异操作是随机替换某个位置的数。每代种群中,根据适应度对解进行排序,选取适应度最高的一部分作为精英解,然后按照适应度的概率对解进行选择,得到父代解。最终的适应度是行适应度、列适应度和九宫格适应度的加权和。算法在达到一定迭代次数或找到最优解时终止,输出最优解。