Linear Crossover in Genetic Algorithms

Linear Crossover

• Employs a linear function to produce offspring from parent chromosomes.
• Offspring parameters result from a linear combination of parent parameters.
• The formula for generating offspring Ci is defined as: Ci = αi * P1 + βi * P2 where P1 and P2 represent the chromosome values of parents 1 and 2, respectively, and αi and βi are user-defined parameters.
• αi and βi determine the weighting of each parent's contribution, allowing the user to control the range and distribution of offspring.
• Different αi and βi combinations can generate offspring outside the original parent range.
• Simple to calculate.
• Fast computation.
• Generation of a large offspring set from two parents is feasible via varying αi and βi.
• Offers control over the range of variation in offspring.
• Determining appropriate αi and βi values can be challenging for inexperienced users.
• Poorly chosen αi and βi values can lead to premature convergence or getting trapped in a local optimum.
• Generated solutions may not always be optimal.

Blend Crossover

• Aims to overcome the limitations of linear crossover.
• Generates offspring within a defined range between the values of parents.
• Given parent chromosome values P1 and P2, assumes P1 < P2.
• Offspring are generated within P1 and P2 α (P2 - P1), where α is a constant set by the programmer.
• Smaller α creates a narrower range, while larger α widens it.
• Incorporates another parameter γ, calculated as γ = r * α, with r being a random number between 0.0 and 1.0.
• The offspring C1 and C2 are calculated: C1 = (1 – γ) * P1 + γ * P2 and C2 = (1 − γ) * P2 + γ * P1.
• By generating multiple random values for r, a wider offspring range can be achieved.
• Computationally simple and fast.
• Generates a large offspring set from two parents.
• Offers more control over the range of variation in offspring compared to linear crossover.
• Requires α to be determined by the programmer, although this is generally easier than in linear crossover.
• Improperly selected α and γ values can still lead to premature convergence or local optima.

Simulated Binary Crossover (SBX)

• Aims to improve upon the limitations of linear and blend crossovers, using a statistically-driven approach.
• Uses probability distribution functions to generate offspring solutions.
• Uses a spread factor α, calculated based on the desired diversity between offspring solutions and input values P1 and P2.
• SBX considers three cases based on the value of α:
• Contraction (α < 1): Offspring values are within the range of the parent values.
• Intermediate (α = 1): Offspring values are between the parent values.
• Expansion (α > 1): Offspring values are outside the range of the parent values.
• The case α=1 is generally not considered useful as it produces no variation.
• Recommended probability distribution functions are C(x) for contraction and E(x) for expansion; these functions are defined based on a constant q, determined experimentally by the user.
• The process involves generating a random number r and then calculating α' based on r, q, and the chosen probability distribution function.
• Offspring C1 and C2 are then calculated using a formula involving α', P1, and P2.
• Does not require parameters like α to be determined beforehand, unlike the other methods.
• Allows for greater exploration of the solution space.
• Typically provides more accurate results and converges to a global optimum more often.
• Often requires fewer iterations than linear or blend crossover.
• Independent of chromosome length; same techniques apply for various numbers of parent values.
• Can use a single set of α' for different chromosome values.
• Computationally more expensive than linear and blend crossover.
• Careful selection of the probability distribution function and the q parameter is crucial to avoid premature convergence.