Genetic Algorithm

A metaheuristic is a high-level, problem-independent algorithmic framework designed to guide subordinate heuristics in a search for near-optimal solutions. Unlike specific algorithms, metaheuristics provide a general strategy that can be adapted to various optimization problems. Genetic algorithms are a prime example. Key characteristics include:

• Exploration vs. Exploitation: Balancing the search of new areas of the solution space with the refinement of known good solutions.
• Stochasticity: Incorporating randomness to avoid local optima.
• Flexibility: Applicable to problems where gradient information is unavailable or the search space is discrete and non-convex.

Evolutionary algorithms are a subclass of population-based metaheuristics inspired by biological evolution. A genetic algorithm is the most prominent type. They operate on a population of candidate solutions, applying principles of selection, crossover (recombination), and mutation across generations. The core cycle involves:

• Fitness Evaluation: Assigning a score to each solution based on an objective function.
• Selection: Choosing parent solutions for reproduction, favoring those with higher fitness.
• Variation: Applying crossover to combine parent traits and mutation to introduce random changes.
• Replacement: Forming a new population for the next generation. This process iteratively drives the population toward better regions of the search space.

The fitness function is the objective function that evaluates the quality of a candidate solution in an evolutionary algorithm. It is the primary force driving evolution by assigning a numerical fitness score; higher scores indicate better solutions. In priority-based routing, a fitness function might combine:

• Makespan minimization (total schedule length).
• Adherence to deadlines or time windows.
• Total travel distance or energy consumption.
• Penalties for violating hard constraints (e.g., collisions). Designing an effective fitness function is critical, as it directly defines what "optimal" means for the algorithm.

Crossover is a genetic operator that combines the genetic information of two parent solutions to produce one or more offspring. It is the primary mechanism for exploiting and recombining successful traits. Common techniques include:

• Single-Point Crossover: Splitting both parent solution representations at a random point and swapping the tails.
• Uniform Crossover: Each gene (solution component) is randomly chosen from one of the two parents.
• Order-Based Crossover: Used for permutation problems (like vehicle routing), preserving relative order of elements from parents. Effective crossover promotes the inheritance of beneficial schemata (building blocks) from parents to children.

Mutation is a genetic operator that introduces random, typically small, alterations to an offspring's solution. It serves as the primary mechanism for exploration, injecting new genetic material into the population to maintain diversity and prevent premature convergence to local optima. Examples in routing include:

• Swapping two tasks in a vehicle's route.
• Reversing a segment of a route.
• Randomly reassigning a task to a different agent.
• Perturbing a numerical parameter (e.g., a timing offset). Mutation rates are usually low (e.g., 1-5%) to avoid turning the search into a random walk.

Selection is the process of choosing individuals from the current population to become parents for the next generation. It applies selective pressure, mimicking natural selection by favoring fitter solutions. Common selection methods are:

• Fitness-Proportionate Selection (Roulette Wheel): Probability of selection is proportional to fitness.
• Tournament Selection: Randomly select k individuals and choose the fittest among them.
• Rank-Based Selection: Selects based on the rank of individuals rather than raw fitness values.
• Elitism: A strategy that directly copies the best-performing individuals to the next generation unchanged, ensuring the best solution never deteriorates.