如何优化遗传算法数独求解器的运行速度？

我用遗传算法实现了一款数独求解器，但运行速度极慢，排查后发现计算种群个体适应度及筛选最优适应度是性能瓶颈，对应耗时2.80秒的代码片段如下：

#2.80 seconds
fitness_list = [fitness_function(individual, fixed_indices) for individual in current_generation]
fitness_list_indices = np.argsort(fitness_list, kind='heapsort')
fitness_over_time.append(fitness_list[fitness_list_indices[0]]) #append for plot

相关函数定义如下：

def fitness_function(puzzle, fixed_indices):
    return len(remove_fixed_indices(sudoku_validifier(puzzle), fixed_indices))

def remove_fixed_indices(badboard, fixedboard):   
    """Removes fixed indices from list. fix = list of fixed indices as '[(2,5), (3,7), ...].
        bad = list of new boardnumbers as [(3,7,9), (2,5,9), ...]
        where first two integers are indices and third is their number
    """                                  
    return [badboard[x] for x in range(len(badboard)) if badboard[x][:-1] not in fixedboard]  

def sudoku_validifier(puzzle):      
    """returns all duplicates of sudoku board and the corresponding
        2d-index of each duplicate. Return example of 1 duplicate:
        '[(3, 5), (6, 5)]'. 2 duplicates: '[(3, 5), (3, 8), (2, 8), (3, 8)]'.
        Multiple of the same index occurs because duplicates in both row/column and/or square
    """
    puzzle = np.array(puzzle)       
    duplicate_indices = []           
                                     
    for i in range(9):
        for dup in return_duplicate_index(puzzle[i]):
            for dup_index in dup:
                duplicate_indices.append((i, dup_index))

    for j in range(9):
        for dup in return_duplicate_index(puzzle[:,j]):
            for dup_index in dup:
                duplicate_indices.append((dup_index, j))

    mesh = (0,3,6)
    for k, l in np.nditer([mesh, mesh]):
        list = puzzle[k:k+3,l:l+3].flatten()
        for dup in return_duplicate_index(list):
            for dup_index in dup:
                duplicate_indices.append((dup_index//3 + k, dup_index%3 + l))
    return duplicate_indices

def return_duplicate_index(list):
    """#returns index of all duplicates except for 0-duplicates, input: list"""
    dup = {}
    for i,x in enumerate(list):
        dup.setdefault(x,[]).append(i)
    duplicate_index = [x for i,x in dup.items() if len(x) > 1 and i > 0]
    return duplicate_index

fixed_indices是数独求解前已确定数字的索引列表。我知道当前存在大量循环操作，想问是否还有优化空间来提升速度？

测试用的数独示例：

easy =  [
        [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]
        ]

1. 预处理fixed_indices为集合，加速成员判断 #

remove_fixed_indices里的badboard[x][:-1] not in fixedboard是O(n)的查找操作，把fixed_indices提前转成集合，将查找复杂度降到O(1)：

# 初始化时只预处理一次，无需每次调用函数都转换
fixed_indices_set = set(fixed_indices)

def remove_fixed_indices(badboard, fixed_set):                                  
    return [item for item in badboard if item[:-1] not in fixed_set]  

2. 重构sudoku_validifier，用numpy向量化+自动去重替代多层嵌套循环 #

原函数的多层嵌套循环是性能核心瓶颈，改用numpy的统计函数简化重复项检测，同时用集合存储重复索引，自动过滤重复添加的同一索引：

def sudoku_validifier(puzzle):
    puzzle = np.asarray(puzzle)
    duplicate_indices = set()

    # 检查行重复
    for i in range(9):
        row = puzzle[i]
        non_zero = row[row != 0]
        idx = np.where(row != 0)[0]
        vals, counts = np.unique(non_zero, return_counts=True)
        dup_vals = vals[counts > 1]
        for val in dup_vals:
            dup_idx = idx[non_zero == val]
            for col in dup_idx:
                duplicate_indices.add((i, col))

    # 检查列重复
    for j in range(9):
        col = puzzle[:, j]
        non_zero = col[col != 0]
        idx = np.where(col != 0)[0]
        vals, counts = np.unique(non_zero, return_counts=True)
        dup_vals = vals[counts > 1]
        for val in dup_vals:
            dup_idx = idx[non_zero == val]
            for row in dup_idx:
                duplicate_indices.add((row, j))

    # 检查3x3宫格重复
    for k in range(0, 9, 3):
        for l in range(0, 9, 3):
            block = puzzle[k:k+3, l:l+3].flatten()
            non_zero = block[block != 0]
            idx = np.where(block != 0)[0]
            vals, counts = np.unique(non_zero, return_counts=True)
            dup_vals = vals[counts > 1]
            for val in dup_vals:
                dup_idx = idx[non_zero == val]
                for pos in dup_idx:
                    row = pos // 3 + k
                    col = pos % 3 + l
                    duplicate_indices.add((row, col))

    return list(duplicate_indices)

3. 简化fitness_function，避免不必要的列表生成 #

原函数需要生成完整的过滤后列表再取长度，可直接计数符合条件的项，省去列表生成的开销：

def fitness_function(puzzle, fixed_set):
    duplicates = sudoku_validifier(puzzle)
    count = 0
    for idx in duplicates:
        if idx not in fixed_set:
            count += 1
    return count

4. 并行计算种群适应度 #

利用多核CPU并行计算每个个体的适应度，适合种群规模较大的场景：

from multiprocessing import Pool

# 并行计算适应度列表
with Pool() as pool:
    fitness_list = pool.starmap(fitness_function, [(ind, fixed_indices_set) for ind in current_generation])

5. 优化最优适应度筛选逻辑 #

原代码用排序取首项的复杂度是O(n logn)，改用np.argmin直接找到最小适应度的索引，复杂度降为O(n)：

fitness_array = np.array(fitness_list)
best_idx = np.argmin(fitness_array)
fitness_over_time.append(fitness_array[best_idx])

内容的提问来源于stack exchange，提问作者Mangokalsong