Genetic Algorithms: Representation and Crossover

1. The Core Idea of Genetic Algorithms

Genetic Algorithms belong to a broader class of evolutionary algorithms. They work by evolving a population of candidate solutions over many generations, iteratively improving them through processes that mimic natural selection, recombination, and mutation.

To get an intuitive feel for how this works, let's start with a video that explains the core concepts using the knapsack problem—a classic combinatorial optimization problem.

From the video, we can identify the main components of a GA:

• A population of solutions (chromosomes).
• A fitness function to evaluate each solution.
• A selection mechanism to choose parents.
• Genetic operators (crossover and mutation) to create offspring.
• A replacement strategy to form the next generation.

This cycle directly relates to our previous lesson:

• Selection is the primary driver of exploitation. By giving preference to fitter solutions, the algorithm intensifies the search in promising regions of the solution space.
• Crossover and Mutation are the primary drivers of exploration. They introduce new genetic material and random changes, allowing the search to discover novel solutions and escape local optima.

2. Chromosome Representation: Encoding a Schedule

The first and most critical step in applying a GA is deciding how to represent a solution as a chromosome. The simple binary string used for the knapsack problem is not suitable for scheduling problems, where the order of tasks is paramount.

Permutation Representation for Simple Scheduling

For a standard Flow Shop or Job Shop problem, a common approach is a permutation-based representation. A chromosome is simply a list of job IDs, representing the sequence in which jobs are processed.

For $n$ jobs, a chromosome could be: [J3, J1, J4, J2]
This means Job 3 is processed first, then Job 1, and so on.

An Advanced Representation for Flexible Job Shop (FJSP)

Your thesis focuses on FJSP, which has two components:

1. Routing: Assigning each operation to a machine.
2. Sequencing: Ordering the operations on the assigned machines.

A simple permutation is not enough. The chromosome must encode both assignment and sequence information. A highly effective representation for this is the task sequencing list.

As the paper explains, a chromosome is a string whose length is the total number of operations. Each gene in the string corresponds to one operation and encodes its machine assignment. The order of genes in the string defines the overall processing sequence.

For an operation $O_{ij}$ (the $j$-th operation of job $i$) assigned to machine $M_k$, the gene could be represented as a triple $(i,j,k)$.

• The sequence of these triples in the chromosome gives the dispatching order of operations.
• The machine part ($k$) of each triple defines the machine assignment.

This representation is powerful because it encodes a complete solution for both the routing and sequencing subproblems of FJSP in a single string.

3. Crossover: Creating New Solutions from Good Parents

Crossover (or recombination) is the process of combining two parent chromosomes to create one or more offspring. The goal is to merge the desirable features of the parents.

Why Simple Crossover Fails for Permutations

Basic crossover operators, like those used for binary strings, are not suitable for permutation-based representations.

To maintain the validity of the permutation, we must use specialized crossover operators.

Crossover Operators for Permutation-based Chromosomes

There are many such operators. We will focus on two classic examples to understand the mechanics, and then a third one that is particularly relevant for job shop problems.

Let's summarize the logic:

• Partially Mapped Crossover (PMX):

  1. Select a random substring within two parents.
  2. Swap these substrings to create initial offspring. This introduces duplicates from one parent and omits genes from the other.
  3. A "mapping" is established between the swapped values (e.g., if 3 was swapped with 6, then 3 maps to 6).
  4. Outside the swapped section, any gene that is a duplicate of one already in the swapped section is replaced by its mapped value. This process is repeated until all duplicates are resolved. PMX is effective at preserving the relative order of genes.

• Cycle Crossover (CX):

  1. Identifies "cycles" of values between the two parents. A cycle exists if the gene at position p in Parent 1 corresponds to the gene at position q in Parent 2, and the gene at position q in Parent 1 corresponds to the gene at position p in Parent 2 (this can extend over multiple positions).
  2. To create an offspring, genes from one cycle are copied from Parent 1, and genes from the next cycle are copied from Parent 2, and so on.
  3. CX is useful because it preserves the absolute position of many genes from the parents.

Precedence Preserving Crossover (POX) for Job Shop

For job shop and flexible job shop problems, we have an additional constraint: the operations within a single job must be performed in a specific order (e.g., $O_{11}$ must precede $O_{12}$). The chromosome representation from the Pezzella paper handles this implicitly by its decoding, but the crossover operator can also be designed to respect this.

The Pezzella paper you read earlier (Section 3.5, "Offspring generation") mentions the Precedence Preserving Order-based Crossover (POX). Here’s how it works:

1. Divide the set of all jobs into two random, disjoint sets, JobSet1 and JobSet2.
2. To create the first offspring, copy all operations belonging to jobs in JobSet1 from Parent 1 into the offspring, preserving their positions.
3. Fill the remaining empty positions in the offspring with the operations from jobs in JobSet2, taking them in the order they appear in Parent 2.
4. The second offspring is created symmetrically.

This operator is powerful because it transfers entire, valid job sub-sequences from parents to children, which can be a very effective way to propagate good scheduling patterns.

Conclusion

Today we've laid the groundwork for using Genetic Algorithms to solve complex scheduling problems. We've moved from the single-solution view of local search to the parallel, population-based approach of evolutionary computation.

Key Takeaways:

• Genetic Algorithms evolve a population of solutions, balancing exploitation (through selection of the fittest) and exploration (through crossover and mutation).
• Chromosome representation is a critical design choice. Simple permutations work for basic sequencing, but complex problems like FJSP require richer encodings that capture both assignment (routing) and sequence information.
• Crossover is the main engine for combining features of successful parent solutions. Standard operators are invalid for permutations.
• Specialized operators like PMX and CX are required to maintain valid permutation-based chromosomes, while operators like POX are specifically designed to respect precedence constraints found in job shop environments.

Preview of the Next Lesson:

While we used Simulated Annealing (SA) as an example in our lesson on the exploration-exploitation trade-off, we have yet to do a deep dive into its mechanics. In the next lesson, we will focus exclusively on SA, covering its core components in detail. You will learn how to formally apply its acceptance criteria and design effective cooling schedules, which are the key parameters for controlling its performance.