32.10 Population-based methods: genetic and memetic algorithms

Part 4 · Heuristic algorithms · Chapter 32 · Chapter 32: Metaheuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search

A genetic algorithm (denoted by \(GA\)) keeps a population of solutions, encoded as strings (chromosomes). At every iteration it selects two parents, preferring the fitter ones, recombines them into a child (crossover), changes a few random genes of the child (mutation), repairs it if it is infeasible, and inserts it into the population in place of a worse individual. A memetic algorithm also applies a local search to every child.

• The pseudo-code of a steady-state \(GA\) for the KP with binary encoding reads as follows; with \(memetic=\mathrm{true}\) it is a memetic algorithm.

Algorithm: Genetic and memetic algorithm for the KP

Input: KP instance \(p[1..n]\), \(w[1..n]\), \(c\); population size \(P\); mutation probability \(p_m\); \(maxIter\); \(memetic\)

Output: best individual of the final population

1Function GeneticKP(\(p, w, c, P, p_m, maxIter, memetic\))

2for \(s := 1\) to \(P\) do ▹ random initial population

3for \(j := 1\) to \(n\) do \(pop[s][j] := 1\) if \(\textsc{Rand}()<0.5\), else \(0\)

4\(\textsc{RepairKP}(pop[s])\);

5if \(memetic\) then \(\textsc{KPLocalSearch}(pop[s])\)

6\(fit[s] := \sum_j p[j]\,pop[s][j]\)

7end

8for \(it := 1\) to \(maxIter\) do

9\(a := \textsc{Tournament}()\); \(b := \textsc{Tournament}()\) \(cut := 1+\lfloor\textsc{Rand}()\cdot(n-1)\rfloor\) \(child := (pop[a][1..cut],\ pop[b][cut{+}1..n])\) ▹ selection one-point crossover

10for \(j := 1\) to \(n\) do \(\textsc{Rand}()<p_m\)\(child[j] := 1-child[j]\)

11\(\textsc{RepairKP}(child)\);

12if \(memetic\) then \(\textsc{KPLocalSearch}(child)\)

13\(worst :=\) the last index \(s\) of minimum \(fit[s]\)

14if \(child\notin pop\) and \(\sum_jp[j]\,child[j] > fit[worst]\) then ▹ replacement

15\(pop[worst] := child\); \(fit[worst] := \sum_jp[j]\,child[j]\)

16end

17end

18return the individual of maximum \(fit\)

19Function Tournament()

20\(a := 1+\lfloor\textsc{Rand}()\cdot P\rfloor\); \(b := 1+\lfloor\textsc{Rand}()\cdot P\rfloor\)

21if \(fit[a]\ge fit[b]\) then return \(a\) else return \(b\)

Run in Colab:PythonC++

• Genetic algorithms were introduced by Holland (1975) as a model of natural evolution, and made popular as optimization methods by Goldberg (1989). Memetic algorithms, in which every individual is improved by a local search, were proposed by Moscato (1989).

• Encoding. For the KP the binary vector \(x\) is a natural chromosome: the gene \(j\) says whether item \(j\) is selected. The fitness of an individual is its profit.

• Selection. A binary tournament draws two individuals at random and keeps the fitter one: good individuals are more likely to become parents, but every individual has a chance.

• Crossover. One-point crossover takes the genes \(1,\dots,cut\) from the first parent and the genes \(cut+1,\dots,n\) from the second one. The idea is that good solutions share good building blocks, and recombining two good parents can put the good blocks of both into one child.

• Mutation. Each gene is flipped with a small probability \(p_m\), typically \(\frac1n\): it brings back into the population genes that selection may have lost.

• Repair. The child can be infeasible. REPAIRKP removes the selected item of minimum efficiency until the capacity is respected (ties: the item of largest index). Alternatives are penalties, as in Section 32.4.3, or encodings in which every chromosome is feasible.

• Replacement. In the steady-state version of the pseudo-code, the child replaces the worst individual if it is better and not already in the population; duplicates would make the population lose its diversity.

• Selection and replacement intensify (the population concentrates on good solutions); crossover and mutation diversify. Without local search, a \(GA\) is good at finding promising regions but slow at reaching their local optima: the memetic algorithm adds the missing intensification.

Example 32.11: \(GA\) on the KP reference instance

With \(P=4\), \(p_m=\frac14\) and \(seed=36\). The first \(16\) random numbers build the initial population (gene \(1\) if the number is smaller than \(0.5\)):

\[ \begin{array}{lll}pop[1]: & 0.0003,\ 0.7354,\ 0.2018,\ 0.5114 & \to (1,0,1,0) \\ pop[2]: & 0.1796,\ 0.8825,\ 0.6936,\ 0.4391 & \to (1,0,0,1) \\ pop[3]: & 0.4547,\ 0.6489,\ 0.8061,\ 0.6990 & \to (1,0,0,0) \\ pop[4]: & 0.9148,\ 0.2446,\ 0.9246,\ 0.0692 & \to (0,1,0,1)\end{array} \]

All four individuals are feasible: \(pop[1]=(1,0,1,0)\), \(pop[2]=(1,0,0,1)\), \(pop[3]=(1,0,0,0)\), \(pop[4]=(0,1,0,1)\), with fitness \((16,14,10,11)\).

Iteration 1 (random numbers \(0.1614\), \(0.2771\), \(0.8030\), \(0.4063\), \(0.0295\), \(0.7238\), \(0.2032\), \(0.4957\), \(0.4620\)). The first tournament draws individuals \(1+\lfloor 4\cdot 0.1614\rfloor=1\) and \(1+\lfloor 4\cdot 0.2771\rfloor=2\), and selects \(a=1\) (fitness \(16>14\)); the second draws \(4\) and \(2\) and selects \(b=2\) (fitness \(14>11\)). The cut is \(1+\lfloor 3\cdot 0.0295\rfloor=1\): the child takes gene \(1\) from \(pop[1]\) and genes \(2\), \(3\), \(4\) from \(pop[2]\), \(child=(1,0,0,1)\). Only the second mutation number, \(0.2032\), is smaller than \(p_m=0.25\): gene \(2\) flips, \(child=(1,1,0,1)\), of weight \(12>9\). The repair removes item \(4\), the selected item of minimum efficiency: \(child=(1,1,0,0)\), of weight \(9\) and profit \(17\). It replaces the worst individual, \(pop[3]\) of fitness \(10\).

Iteration 2 selects \(a=2\) and \(b=3\), cuts after gene \(1\) and builds \((1,1,0,0)\), with no mutation: it is already in the population, and it is discarded. Iteration 3 selects \(a=2\) and \(b=1\), cuts after gene \(3\), builds \((1,0,0,0)\), and the mutation flips genes \(1\) and \(4\): \((0,0,0,1)\), of profit \(4\), worse than every individual, discarded.

The best individual is \((1,1,0,0)\): \(GA(I)=17=z(I)\), found by crossover, mutation and repair together.

• On KP20, with \(P=10\), \(p_m=0.05\) and \(300\) iterations, for \(seed=1,\dots,10\):

	min	average	max	optimal	best profit per seed
\(GA\)	\(508\)	\(516.9\)	\(521\)	\(4\)	\(521,519,521,508,514,521,510,519,521,515\)
memetic	\(521\)	\(521.0\)	\(521\)	\(10\)	\(521,521,521,521,521,521,521,521,521,521\)

• The plain \(GA\) reaches the optimum \(521\) in \(4\) runs out of \(10\); the memetic algorithm in every run. The local search makes every individual a local optimum, and the crossover then recombines local optima instead of arbitrary solutions.

---

Next: 32.11 Comparison and conclusions