随机染色体突变在整个人群中是相同的

Question

在我的遗传算法中，我试图突变染色体内的基因。染色体是问题的时间表(解决方案)，基因是时间表(子解决方案)中一项任务的分配。由于这种编码，问题与常规 GA 略有不同。染色体看起来像这样：[[gene],[gene],...]基因看起来像这样：[job_ID,stage_ID,Order_ID,duration,machine_ID].因此，它很快就会变成一长串列表。 当问题被编码到染色体中的基因列表列表中时，随机父母(随机染色体)被选择用于机器编号的突变。 在突变函数中，基因组的第五个条目(机器ID)根据可用的机器改变到当前生产阶段(基因组的第二个条目)。

输出中出现问题。在每条染色体中，相同的基因都被我的突变改变了，而对于每条染色体，变化都是随机的。例如，在每个解决方案/时间表(染色体)中，第四、第五和第十六条染色体发生了突变，而不是不同染色体之间的不同突变。

当我打印基因突变时(每个亲本染色体 1 = 4，和 4 个突变。所以总共 16 个)，随机性似乎是正确的。因此，我怀疑染色体或亲本的变量分配存在错误。不幸的是，在Stackoverflow和类似网站上进行了大量实验和搜索后，我未能找到解决方案。

提前谢谢你！ 很抱歉问了这么长的问题。

import random
import numpy as np

def encoding(jobs, stages, machines, P_ilj):
chromosomes = []
chromosome = []
i = 1
for n in range(n_chromosomes):
while i < 4:
for j in jobs:  # Initial solution: Each stage is linked to a machine available in that stage.
if i == 1:
l = 1
elif i == 2:
l = 3
else:
l = 5
# [job,stage,Order_ID,duration,machine_ID]
gene = [j, i, np.random.rand(), P_ilj[i][l][j], l]
chromosome.append(gene)
i += 1
chromosomes.append(chromosome)
return chromosomes

def parent_selection(chromosomes, n_parents):
parents = []
# Sample n parents from all chromosomes
chromosome_id = random.sample(range(len(chromosomes)), n_parents)
for parent in chromosome_id:
parents.append(chromosomes[parent])
return parents

def mutation(parents, n_mutations):  # Returns literally the same changes. Should return random
# changes. The genes have the same changes for all chromosomes.
# Random machine assignment
for c, chromosome in enumerate(parents):
for gene in random.sample(range(len(chromosome)), n_mutations):
# If the stage = 1, mutate by choosing a random processing machine.
if chromosome[gene][1] == 1:
chromosome[gene][4] = int(
np.array(random.sample(proc_machs, 1)).astype(int))
elif chromosome[gene][1] == 2:
chromosome[gene][4] = int(
np.array(random.sample(buff_machs, 1)).astype(int))
else:
chromosome[gene][4] = int(
np.array(random.sample(pack_machs, 1)).astype(int))
parents[c] = chromosome
# This function malfunctions. I.e. the last loop might overwrite all chromosomes, instead of only the last parent-chromosome.
return parents

# %% Set creation
G = 10
F = 3
M1 = 2  # 28
M2 = M1
M3 = 1  # 29
T = 60*24*1  # 60*24*7
JOBS = np.arange(1, G+1)
STAGES = np.arange(1, F+1)
MACHS_R = np.arange(1, M1+1)
BUFFERS = np.arange(M1+1, M1+M2+1)
MACHS_P = np.arange(M1+M2+1, M1+M2+M3+1)
MACHS = np.arange(1, M1+M2+M3+1)
TIMES = np.arange(0, T)

# %% Sets in lists
jobs = [j for j in JOBS]
stages = [i for i in STAGES]
machines = [int(l) for l in MACHS]
proc_machs = [int(l) for l in MACHS_R]
buff_machs = [int(l) for l in BUFFERS]
pack_machs = [int(l) for l in MACHS_P]
times = [t for t in TIMES]
# %% Parameters
np.random.seed(42)
random.seed(42)
j_d, j_m_d, P_ilj = {}, {}, {}
for k in stages:
for e in machines:
for y in jobs:
j_d[y] = round(np.random.rand()*10)
j_m_d[e] = j_d.copy()
# Processing time of job j on machine l in stage i.
P_ilj[k] = j_m_d.copy()

# %% DATA generation

n_parents, n_mutations, n_chromosomes = 4, 4, 8
chromosomes = encoding(jobs, stages, machines, P_ilj)
parents = parent_selection(chromosomes, n_parents)
mutated_children = mutation(parents, n_mutations)

Answer 1

在encoding中，你只进入一次while环，chromosomes.append(chromosome)将相同的染色体附加到染色体上。当您修改其中任何一个时，假设chromosomes[0][0][0]，即 1，并通过为其分配一个新值来修改它，例如chromosomes[0][0][0] = 2，那么不仅chromosomes[0]，而且所有其余的也会改变，它们的[0][0]元素也将是 2。Python不会复制chromosome，它只是链接到同一个对象。为了避免这种情况，并制作副本，你必须告诉python这样做。由于您有一个列表列表，因此必须制作一个深层副本。

# other imports
import copy
def encoding(jobs, P_ilj):
chromosomes = []
chromosome = []
i = 1
for n in range(n_chromosomes):
while i < 4:
for j in jobs:  # Initial solution: Each stage is linked to a machine available in that stage.
if i == 1:
l = 1
elif i == 2:
l = 3
else:
l = 5
# [job,stage,Order_ID,duration,machine_ID]
gene = [j, i, np.random.rand(), P_ilj[i][l][j], l]
chromosome.append(gene)
i += 1
chromosomes.append(copy.deepcopy(chromosome))
return chromosomes
# other part of the code

Answer 2

encoding生成的所有染色体都是相同的，因此尽管parent_selection选择不同的染色体，但输出始终相同。

根据我不太熟悉的命名约定，你可能想使用这个修改后的编码函数，它会产生不同的染色体：

def encoding_diff(jobs, P_ilj):
chromosomes = []
for n in range(n_chromosomes):
i = 1
chromosome = []
while i < 4:
for j in jobs:  # Initial solution: Each stage is linked to a machine available in that stage.
if i == 1:
l = 1
elif i == 2:
l = 3
else:
l = 5
# [job,stage,Order_ID,duration,machine_ID]
gene = [j, i, np.random.rand(), P_ilj[i][l][j], l]
chromosome.append(gene)
i += 1
chromosomes.append(chromosome)
return chromosomes