Random chromosome mutation is the same in the entire population

Question

In my Genetic Algorithm of a generic production planning problem, I am trying to mutate a gene inside a chromosome. A chromosome is a schedule (solution) of the problem, and a gene is the assignment of one task in the schedule (sub-solution). Due to this encoding the problem is slightly different than a regular GA. A chromosome looks something like this: [[gene],[gene],...] and a gene looks like this: [job_ID,stage_ID,Order_ID,duration,machine_ID]. Therefore it becomes a long list of lists quite quickly. When the problem is encoded into a list of lists of the genes in the chromosomes, random parents (random chromosomes) are selected for the mutation of a machine number. In the mutation function, the fifth entry of a genome (the machine ID) is altered according to the available machines to the current stage of production (second entry of a genome).

The problem arises in the output. In every chromosome, the same genes have been changed by my mutation, whereas it was expected that for every chromosome the changes would be random. So for example, in every solution/schedule (chromosome) the fourth, fifth, and sixteenth chromosome have mutated, instead of different mutations between the different chromosomes.

When I print the gene mutations (1 for each parent-chromosome = 4, and 4 mutations. So 16 in total), the randomness seems correct. Therefore, I suspect that there is a mistake in the variable assignment of the chromosome(s) or parent(s). Unfortunately, I did not manage to find a solution after a lot of experimenting and searching on Stackoverflow and similar sites.

Thank you in advance! Sorry for asking such a long question.

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

All your chromosomes generated by encoding are the same, therefore although parent_selection selects different chromosomes, the output is always the same.

Based on the naming convention I am not really familiar with, you may want to use this modified encoding function, which produces different chromosomes:

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

In encoding, you enter the while loop only once, and chromosomes.append(chromosome) appends the same chromosome to the chromosomes. When you modify any of them, let's say chromosomes[0][0][0], which is 1, and you modify it by assigning a new value to it, e.g. chromosomes[0][0][0] = 2, then not only chromosomes[0], but all the rests will change too, their [0][0] element will be also 2. Python doesn't make a copy of chromosome, it just links to the same object. To avoid this, and to 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