遗传算法中子代数组修改引发父代数组变更的问题排查

算法流程与问题描述 #

我开发了一个从父代生成子代的遗传算法，流程如下：

• 初始生成随机工作负载（由子数组构成的数组），参数：工作负载L=2、种群规模N=30、InputsNumber=3、突变率m=0.05
• 对种群评分，选出得分最高的2个工作负载作为父代，此时新种群仅包含这两个父代
• 通过交叉、突变函数从父代生成子代，将子代加入含父代的种群
• 重复上述流程10次，每次从种群选最优2个作为父代

核心问题：调用mutation()函数修改子代值时，父代的值会同步变成子代的值——调用前父代数据正常，调用后父代数据被篡改。

父代/子代数组示例：[[0, 0, 0],[0, 0, 0]]
父代集合/子代集合数组示例：[ [[0, 0, 0],[0, 0, 0]], [[0, 0, 0],[0, 0, 0]] ]

原代码 #

import random

# 假设bcolors是已定义的颜色常量
bcolors = type('bcolors', (), {'OKGREEN': '\033[92m', 'ENDC': '\033[0m'})()

def generateRandomWorkload(inputsNumber, L, N):
    global population
    individualWorkload = []
    for n in range(N):
        for i in range(L):
            # 原代码此处可能存在问题：若inputsNumber是整数，len(inputsNumber)会报错
            individual = [0 for _ in range(len(inputsNumber))]
            individualWorkload.append(individual)

        population.append(individualWorkload)
        individualWorkload = []


def crossover(L):
    global parents, children

    children = []

    for i in range(2):
        C = random.randint(0, 1)
        R = random.randint(0, L)
        if C == 0:
            child = parents[0][0:R] + parents[1][R:L]
            children.append(child)
        elif C == 1:
            child = parents[1][0:R] + parents[0][R:L]
            children.append(child)

    return children


def mutation(mutation_rate):
    global children

    for i in range(len(children)):
        for j in range(len(children[i])):
            for k in range(len(children[i][j])):
                r = random.uniform(0, 1)
                if r <= mutation_rate:
                    children[i][j][k] = 1 - children[i][j][k]

    return children


def geneticAlgorithm(inputsNumber, L, N):
    global parents, children, population
    population = []
    generateRandomWorkload(inputsNumber, L, N)
    print("SEED POPULATION: ", population, "\n")

    for generation in range(10):
        print(bcolors.OKGREEN + "MEASUREMENTS OF ", generation+1, " GENERATION" + bcolors.ENDC)
        scoreI = []
        for individualWorkload in population:
            ### 此处计算评分（scoreI） ###
            # 示例：临时给个随机评分
            scoreI.append((individualWorkload, random.random()))

        # 父代选择
        print("PARENTS SELECTION...\n")
        scoreI.sort(key=lambda x: x[1])
        parents = [scoreI[-1][0], scoreI[-2][0]]
        population = [parents[0], parents[1]]
        print("SELECTED PARENTS:\n", parents, "\n")
        print("PARENTS IN POPULATION:", population)

        # 交叉
        print("BEGIN CROSSOVER...\n")
        print("PARENTS: ", parents)
        children = crossover(L)
        print("CROSSOVER CHILDREN:\n", children, "\n")

        # 突变
        print("BEGIN MUTATION...\n")
        print("PARENTS: ", parents)
        children = mutation(0.05)
        print("MUTATION CHILDREN:\n", children, "\n")

        # 新种群
        population.append(children[0])
        population.append(children[1])

        print("PARENTS: ", parents)
        print("NEW POPULATION:\n", population, "\n")

问题原因 #

问题根源是列表的浅拷贝：
在交叉函数中，child = parents[0][0:R] + parents[1][R:L]的切片操作仅对父代的外层列表做了拷贝，但内层的子数组（如[0,0,0]）仍然和父代中的子数组指向同一个内存对象。当突变函数修改子代的子数组元素时，实际上是在修改父代的对应子数组元素。

解决方案 #

需要在交叉生成子代时，对嵌套的子数组做深拷贝，确保子代与父代的内存完全独立，有两种修改方式：

方式1：对子数组逐个浅拷贝（适用于单层嵌套） #

修改交叉函数：

def crossover(L):
    global parents, children
    children = []
    for i in range(2):
        C = random.randint(0, 1)
        R = random.randint(0, L)
        if C == 0:
            # 对每个子数组单独拷贝，避免引用父代的子数组
            child = [sub.copy() for sub in parents[0][0:R]] + [sub.copy() for sub in parents[1][R:L]]
            children.append(child)
        elif C == 1:
            child = [sub.copy() for sub in parents[1][0:R]] + [sub.copy() for sub in parents[0][R:L]]
            children.append(child)
    return children

方式2：使用深拷贝（适用于多层嵌套） #

导入copy模块后修改交叉函数：

import copy

def crossover(L):
    global parents, children
    children = []
    for i in range(2):
        C = random.randint(0, 1)
        R = random.randint(0, L)
        if C == 0:
            child = copy.deepcopy(parents[0][0:R]) + copy.deepcopy(parents[1][R:L])
            children.append(child)
        elif C == 1:
            child = copy.deepcopy(parents[1][0:R]) + copy.deepcopy(parents[0][R:L])
            children.append(child)
    return children

额外修复：生成随机工作负载的错误 #

原代码中generateRandomWorkload函数的len(inputsNumber)会报错（若inputsNumber是传入的整数3），应改为：

individual = [0 for _ in range(inputsNumber)]

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