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

Question

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

问题出现在输出中。在每条染色体中，我的突变改变了相同的基因，而对于每条染色体，预期的变化都是随机的。所以举例来说，在每个solution/schedule（染色体）中，第四、第五和第十六条染色体发生了突变，而不是不同染色体之间的不同突变。

当我打印基因突变时（每个 parent-chromosome = 4，以及 4 个突变。总共 16 个），随机性似乎是正确的。因此，我怀疑是chromosome(s)或parent(s)的变量赋值有误。不幸的是，在 Whosebug 和类似网站上进行了大量试验和搜索后，我未能找到解决方案。

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

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生成的所有染色体都是一样的，因此虽然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

Answer 2

在encoding中，你只进入while循环一次，chromosomes.append(chromosome)将相同的染色体追加到染色体上。当您修改其中任何一个时，假设 chromosomes[0][0][0]，即 1，您可以通过为其分配一个新值来修改它，例如chromosomes[0][0][0] = 2，那么不仅chromosomes[0]，其余的也会改变，它们的[0][0]元素也将是2。Python不会复制[=18] =], 它只是链接到同一个对象。为了避免这种情况，并 make a copy, you have to tell python to do so. As you have a list of list, you must make a deep copy.

# 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

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

Random chromosome mutation is the same in the entire population

python

random

genetic-algorithm

mutation