Binary and Real-Coded Genetic Algorithms in MATLAB

A genetic algorithm (GA) searches for a low-cost solution by evolving a population of candidates. Selection favors promising parents, crossover combines their variables, and mutation introduces new values. Binary chromosomes suit yes-or-no choices, while real-coded chromosomes suit continuous parameters.

This package includes both versions in MATLAB, with a separate sample problem and genetic operators for each. The common optimization loop makes it useful for studying how the representation changes the search. For background, see the Wikipedia article on genetic algorithms (opens in a new tab).

John Holland developed the foundations of genetic algorithms and presented them in his 1975 book Adaptation in Natural and Artificial Systems.

The optimization problem

Both versions minimize a cost function $f(x)$ over a vector of decision variables $x = (x_1, \dots, x_n)$:

• In the binary version, every $x_i$ is 0 or 1. The sample problem is MinOne, $f(x) = \sum_{i=1}^{n} x_i$, with $n = 50$ bits. Its best solution is the all zeros vector.
• In the real-coded version, every $x_i$ is a real number between a lower bound and an upper bound. The sample problem is the sphere function, $f(x) = \sum_{i=1}^{n} x_i^2$, with $n = 10$ variables in $[-10, 10]$. Its best solution is the origin.

How the algorithm works

Each generation of the code has these steps:

1. Selection. Pick two parents from the population.
2. Crossover. Combine the two parents into two offspring. The number of offspring is set by the crossover percentage.
3. Mutation. Pick random members of the population and create mutated copies of them. The number of mutants is set by the mutation percentage.
4. Replacement. Merge the population, the offspring and the mutants, sort them by cost, and keep the best nPop solutions.

The best solution and the best cost of every iteration are recorded, and a convergence plot is drawn at the end.

Parent selection

When the code starts, a dialog box asks for the selection method:

• Roulette wheel selection. Each solution gets a selection probability that falls quickly as its cost grows. The code uses $P_i \propto e^{-\beta c_i / c_{\text{worst}}}$, where $c_i$ is the cost of solution $i$, $c_{\text{worst}}$ is the worst cost seen so far, and $\beta = 8$ is the selection pressure.
• Tournament selection. Three solutions are picked at random, and the one with the lowest cost wins.
• Random selection. Parents are picked at random, with equal chances.

Operators of the binary GA

Crossover chooses one of three methods at random. Single point crossover (probability 0.1) cuts both parents at one random point and swaps the tails. Double point crossover (probability 0.2) swaps the part between two random cut points. Uniform crossover (probability 0.7) takes each bit from either parent at random.

Mutation flips a fixed number of randomly chosen bits: $\lceil \mu n \rceil$ bits, where $\mu$ is the mutation rate.

Operators of the real-coded GA

Crossover makes each offspring a random blend of the two parents, gene by gene:

Each element of $\alpha$ is drawn uniformly from $[-\gamma, 1+\gamma]$. With $\gamma > 0$, an offspring can fall a little outside the segment between its parents, which helps the search explore.

Mutation adds a Gaussian step to $\lceil \mu n \rceil$ randomly chosen variables. The step size is $\sigma = 0.1\,(\text{VarMax} - \text{VarMin})$. After crossover and mutation, any value outside the bounds is set back to the nearest bound.

Parameters

The parameters are set at the top of ga.m in each folder.

The real-coded version also sets VarMin = -10 and VarMax = 10.

What is in the download and how to run it

The download has two folders:

• 01 Binary Genetic Algorithm: ga.m, main.m, the cost function MinOne.m, the crossover functions (Crossover.m, SinglePointCrossover.m, DoublePointCrossover.m, UniformCrossover.m), Mutate.m, RouletteWheelSelection.m and TournamentSelection.m.
• 02 Real-Coded Genetic Algorithm: the same structure, with Sphere.m as the cost function and the real-coded Crossover.m and Mutate.m.

To run a version, open its folder in MATLAB and run main.m. Choose the selection method in the dialog box. The program prints the best cost of each iteration and then plots it.

To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar and the bounds in ga.m.

The code uses randsample and, in the real-coded version, unifrnd. Both come from the Statistics and Machine Learning Toolbox, so the code probably needs that toolbox.

Check the result

For the MinOne example, inspect the returned bit vector as well as its cost: the known minimum is 0 at the all-zero vector. For the Sphere example, the minimum is 0 at the origin. Run each version several times before comparing settings, and compare both solution quality and the number of cost evaluations. A falling convergence curve shows progress during that run, not a guarantee that a new problem has been solved globally.

Applications

GAs are used where the cost function is hard to handle with gradient methods, for example when it is noisy, discontinuous or has many local minima. Typical uses are engineering design, scheduling, feature selection and the tuning of model parameters. The binary version suits yes or no decisions, such as selecting items or features. The real-coded version suits continuous parameters.

Learn more

• Practical Genetic Algorithms in Python and MATLAB is a free video course by Mostapha Kalami Heris. It builds a binary GA and a real-coded GA from scratch in MATLAB, and a real-coded GA in Python.
• YPEA is a MATLAB toolbox that includes a GA among 15 algorithms, with the same problem definition for all of them.

Mostapha Kalami Heris, Binary and Real-Coded Genetic Algorithms in MATLAB (YPEA101), Yarpiz, 2015. https://yarpiz.com/genetic-algorithms-ypea101

@misc{yarpiz-ypea101,
  author = {{Mostapha Kalami Heris}},
  title = {{Binary and Real-Coded Genetic Algorithms in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA101},
  url = {https://yarpiz.com/genetic-algorithms-ypea101}
}