Genetic Algorithm: A to Z with Combinatorial Problems

Explore the genetic algorithm inspired by Darwin and Lamar, emphasizing natural selection, reproduction via crossover and mutation, and fitness-based selection across generations, with an analogy to DNA and genotype-phenotype.

Define an optimization problem with an objective function, decision variables, and constraints. Distinguish linear versus non-linear and single versus multi-objective cases, using car purchase as a real-world example.

Start with binary GA: define a binary GA function, set up a folder, and initialize with clc, clear, and close all to access workspace parameters.

Explore problem definition in binary genetic algorithms, detailing optimization problems with cost functions, constraints, and binary variables, and illustrate constructing fitness functions and chromosome representations in Matlab.

Learn how genetic algorithm parameters: max iterations, population size, crossover and mutation counts that shape performance within the genetic algorithm framework from initialization to selecting the best solution.

Initialize a population with binary positions, evaluate them with the fitness function, and store results in a structure array during the genetic algorithm's initialization stage.

We sort cost function by collecting all costs into a cost matrix, then reorder population by sorted indices to identify the best solution and track the best cost per iteration.

Execute the genetic algorithm main loop and apply single point crossover to two parents to generate two offspring, with a random cut point and two-column storage.

Apply mutation in genetic algorithms by randomly selecting a binary variable and flipping it, turning 1 to 0 or 0 to 1, then evaluate the resulting solution’s cost.

Combine crossover and mutation results into a single population, sort by cost, truncate to the best n, and select next generation while tracking and plotting the best cost per iteration.

Enhance genetic algorithm performance by implementing double-point and uniform crossovers, alongside single-point crossover, with random selection of crossover strategies and integration into code for improved offspring generation.

Improve mutation in a genetic algorithm by introducing a rate of mutation (RMU) to mutate multiple variables, using RMU to determine the number of mutations and Mu as input.

Explore real-valued genetic algorithms for continuous problems, using arithmetic crossover with delta extension and normal-distribution mutation on a sphere objective.

Explore the hub location problem and its applications, and learn to model it with a genetic algorithm by selecting open centers, minimizing distance, and using various distance measures.

Follow five steps to connect any optimization problem to a metaheuristic: create a model, generate random solutions, convert to mathematical variables, handle constraints, and define the cost function.

Create a model for a hub location problem by generating random customer and service center positions, computing Manhattan distances, setting demand and opening costs, and saving the completed model.

Create a random solution by calling a function that uses the model and binary variables sized by M, with N as input, then run to generate new solutions.

Define a cost function for a genetic algorithm by combining the distance to the nearest service centers with the opening cost, using mean, Dmin, and weights W1 and W2.

Connect the cost function to binary GA by defining the model, creating a new cost function, and adapting for two outputs: cost and solution, with mutation and tuning notes.

Visualize the genetic algorithm solution by plotting the best solution at each iteration, showing customer and service center assignments and how tuning the cost function parameters guides the search.

Explore a transportation model in operations research and supply chain management linking manufacturers to customers, using a chromosome for a genetic algorithm to minimize cost under capacity and demand constraints.

Generate random problem instances by defining i and j sizes and parameters a, b, and c, then save, load, and select models via a user interface.

Define the chromosome as a real-valued matrix X with rows as customers and columns as manufacturers; normalize by row and scale by demand to meet constraints using a penalty function.

Implement genetic algorithm chromosome-based representations in Matlab by generating a random x_hat matrix of size I by J, then convert it to a normalized x that satisfies the equal constraint.

Explore penalty functions for constraint handling in genetic algorithms, including violation measures, cost adjustments, and feasibility as the preferred approach before applying alpha and beta.

Define and implement a cost function with inputs and outputs, compute the total cost and capacity violations, and combine them for use in genetic algorithms.

Connect the problem to the real GA by adapting the cost function, implementing matrix-based crossover and mutation, and validating feasibility with penalties to show convergence.

Explore a genetic algorithm approach to a mixed integer transportation model with a binary open/close decision for manufacturers, including fixed opening costs and capacity constraints.

Refine the model by adding random features and a fixed-cost function for manufacturers, using E0 and E1 to define cost as E0 plus E1 times B, then generate new data.

Create a two-part solution representation for the genetic algorithm, combining a binary open variable with a continuous x hat for i, j. Run the code to generate the random solution.

Create a parse solution by combining a solution with an active F and x hat, forming a two-part binary x and real x with manufacturers 1 and 2 active.

Modify the crossover operator in a two-part solution (F and X hat), switching between binary, real, or both crossovers, with relevant functions (single, double, uniform).

Modify mutations in genetic algorithms by applying the crossover-based procedure to binary and real mutations, with three cases: binary only, real only, or both, using RMU and X hat.

Modify the cost function by combining the first part C with the second part E, updating X hat, X, and f, and store keys for both parts of the cost.

Connect new problems to RealGa by aligning Sol one as the main input, review and modify the genetic algorithm code, and validate the model through saving and running.

Explore the quadratic assignment problem (QAP), its relation to linear and assignment problems, and a matlab-based model to minimize a cost function using a metaheuristic algorithm.

Create a random, symmetric workload matrix for a quadratic assignment problem, then define locations and distances to build and visualize the QAP model.

Represent the quadratic assignment problem solution as a permutation encoding the sequence of locations and facilities, preserving ordering and uniqueness as the final decision variables for cost evaluation.

Generate a random permutation as a QAP solution using M locations, then split into two parts with the first N numbers as the final decision variables.

Explore how to compute the cost function for the quadratic assignment problem, using inputs solution and model, with workload W, distance D, and index P to evaluate site assignments.

Present a permutation-aware crossover for the qap that fixes duplicates by identifying duplicated points in the first and second parts and swapping them to produce feasible offspring.

Apply a permutation crossover in Matlab for the quadratic assignment problem, producing two offspring from x1 and x2 using cut points and intersection-based swaps via X11/X12, X21/X22, R1, and R2.

Apply permutation-friendly mutation techniques by swapping, reversion, or inserting elements to create new chromosomes, illustrated with index-based examples for permutation solution representations.

Learn how to implement a permutated mutation for the QAP by choosing one of three operators—swap, reversion, and insertion—and applying them to two selected indices.

learn how to connect and solve the quadratic assignment problem with a binary genetic algorithm, including custom initialization, a tailored cost function, permutation crossover, and mutation strategies.

Visualize the quadratic assignment problem solution by plotting facility locations and convergence plots, using yellow markers for assigned locations and blue markers for others, with indices labeled by text.

Explore the knapsack problem, a classic combinatorial optimization task with items of weights and values, binary decision variables, and capacity constraints to maximize total value.

Create a knapsack model by defining parameters v and w, generating random items and matrices, and saving the parameters to the model with a 10,000 knapsack constraint.

Explore solution representation in genetic algorithms using a binary knapsack scheme where ten items map to zeros and ones, indicating unselected or selected, and code this representation for metaheuristic method.

Create a matlab function that outputs X as a random solution from a model, using model.n and rand to generate 0–1 inputs.

Explore penalty function strategies for handling a knapsack constraint in a genetic algorithm, defining violation-based costs and comparing additive, multiplicative, and mixed approaches to adjust the objective.

Code a Matlab cost function for a genetic algorithm with inputs x and model, compute a loss as 1 minus x, and apply a weighted violation.

Explore how to connect the knapsack problem to a genetic algorithm by adjusting the model, cost function, crossover and mutation, and feasibility checks to obtain feasible solutions.

Explore the traveling salesman problem by visiting each city exactly once and returning to the origin. Model with binary variables x_ij, minimize total distance, and apply subtour elimination.

Define a function to generate a random TSP model by assigning city coordinates within bounds, computing an Euclidean distance matrix, and saving the results for visualization.

Generate and save models of varying sizes, then load and select a main model to solve with genetic algorithm in MATLAB.

Learn to generate a random solution in a genetic algorithm by determining the number of cities, setting model.n, and using permutation to create varying solutions.

Define the TSP cost function by summing distances between consecutive cities in a route, using the model's distance data and modulo n to wrap the tour.

Explore how genetic algorithm crossover for TSP handles permutation representations by identifying duplicated points and swapping them between two offspring to produce a feasible solution.

Learn a permutation-aware crossover for the TSP that prevents duplicates by cutting at a line excluding the last city and reassembling offspring. Resolve duplicates with intersection checks and index-based replacements.

Explore mutation strategies for TSP using permutations: swap two points, reverse the segment between two points, and insert a point, with practical coding approaches.

Develops a permutation mutation for TSP, randomly selecting among insertion, swap, and reversal via a switch, and implements three functions to apply each strategy.

Connect the genetic algorithm to the traveling salesman problem by designing a model, adapting mutation and crossover for TSP, and comparing binary GA and real GA with tournament selection.

Visualize the best TSP route across iterations by plotting solutions, highlighting city coordinates and routes, while experimenting with mutation and crossover in a genetic algorithm.

The lecture proposes a new TSP model with a unit-distance cost, handling an asymmetric price matrix and a symmetric distance matrix while enforcing visit-all and no-subtour constraints.

Explore how to tune metaheuristic parameters by comparing approaches—from literate view and trial-and-error to full factorial designs—emphasizing Taguchi and response surface methodology for practical parameter optimization.

Explore normalization of objective functions in genetic algorithms, using percentage deviation and division index to scale values, with practical Excel examples illustrating min/max references for minimization and maximization.

Determine the control factors and their levels, select an orthogonal array, apply the Taguchi method, run experiments with a mathematical model, and identify the best combination of factor levels.

Identify the main parameters of a genetic algorithm for a knapsack problem, including max iterations, population size, crossover probability, mutation probability, selection pressure, and tournament size.

This lecture explains determining parameter levels in Taguchi for genetic algorithms. It details population size, crossover and mutation rates, beta, and tournament settings, and contrasts literature-based and trial-and-error level selection.

Explore selecting an orthogonal array for a six-parameter, three-level Taguchi design, using L27 designs and Minitab to determine the appropriate array, then apply the array in Matlab code.

Carry out a taguchi-designed experiment in MATLAB by configuring 27 runs across different parameter levels for a knapsack problem, storing costs in Z, and logging best results for later analysis.

Analyze 27 Taguchi experiments in minitab, normalize Z values, and determine the best parameter levels for minimizing the cost function using the signal-to-noise ratio and means.

Explore the response surface methodology (RSM)—a regression-based approach using linear and quadratic models, central composite designs, and center-point coding to optimize parameters in metaheuristics.

identify the parameters for design of experiments using rsm, with two levels and a center point. build a linear expression from x1 and x2 and set the center to zero.

Open design expert and create a six-factor, face-centered full 86-run response surface design, then convert -1/0/1 codes to 1/2/3 for Matlab.

Carry out experiments using a response surface methodology workflow: import and configure design, set levels, run designs, capture z values, normalize data, and compute p-values for knapsack and RSA methods.

Explore how to analyze experiment results using quadratic and linear models, anova, and normal plot regression within rsm, identifying optimal parameters and transferring them to design.

Learn how to compare metaheuristics using nonparametric tests, especially the Wilcoxon signed-rank test for pairwise comparisons, including p-values, hypotheses, and rank-based interpretation.

Use wilcoxon rank sum tests in MATLAB to compare two algorithms, interpret p-values, and identify when GA outperforms PSL or ACO across multiple test functions.