Gene Algorithm(GA) is a very popular intelligent optimization algorithm. It was proposed by professor John H. Holland and his students of University Michigan at 1960s and 1970s. By evolution of populations, solutions represented by individuals promote the fitness to the environment. After enough generations, we get the optimal solution of the problem.
1) Basic Ideas
By constructing a fitness function from target function, GA evaluates, operates and selects individuals in a population, which represents all the solutions of the problem, with every individual standing for a chromosome. The optimal solutions which have the largest fitness function value are obtained after enough generations.
2) How to implement?
Confronting an optimization problem, we should select an encoding scheme at first. What the solutions of the problem look like? How to give all the solutions gene representaion? Maybe binary encoding is good enough, maybe float encoding is better.
Secondly, how do we operate on chromosome, i.e. individual encoded solution? There are crossover and mutation operators. By swapping corresponding segments of two chromosomes one can get two new chromosomes. Mutation is operated on one chromosome. By changing some genes of a chromosome, we can get a new chromosome. Whether to do the crossover and mutation are controlled by crossover rate and mutation rate, respectively. Crossover rate is usually large, such as 0.8, while mutation rate is small, may be 0.03.
Thirdly, how do we select individuals to operate on from population? The mostly used selection strategy is proportional selection, in which every individual is selected with the probability of ratio of fitness of the individual and sum of fitness of all the individuals. For individual $i$ with fitness $F_i$, if population size is $NP$, then the selection probability is
\[P_i=\frac{F_i}{\sum\limits_{i=1}^{NP}F_i},\]
then do the selection by roulette wheel. Set $PP_0=0$,
\[PP_i=\sum\limits_{j=1}^{i}P_j.\]
For individual $i$, generate a random number $\xi\in{U(0,1)}$, if $PP_{i-1}\le{\xi}\lt{PP_i}$, then individual $i$ is selected.
There are population size $NP$ and stopping rule to be determined. In practice, population size is usually set to $100\sim{1000}$ or set to a value related to the generation count. Stopping rule is usually set to a maximal generation count.
Now we present an example. Solve the optimization problem
\[\mathop{max}f(x)=x^3-60x^2+900x+100,\]
where $x\in{[0,30]}, and the tolerance is $10^{-3}$.
We use binary encoding for solutions. Set the length of chromosome is $L$, then
\[\frac{30-0}{2^L}\le{10^{-3}}\]
must be satisfied for the tolerance. So $L\ge{log_{2}30000=14.87}$, we take $L=15$.
1) Set population size $NP=5$, number of generation $NG=10$.We use the target function $f(x)$ as the fitness function. Initial population can be generated by random. Table 1 is an example
| $j$ | encode | $x_j$ | $f(x_j)$ | $P_j$ | $PP_j$ |
| 1 | 10011 | 19 | 2399 | 0.206 | 0.206 |
| 2 | 00101 | 5 | 3225 | 0.277 | 0.483 |
| 3 | 11010 | 26 | 516 | 0.044 | 0.527 |
| 4 | 10101 | 21 | 1801 | 0.155 | 0.682 |
| 5 | 01110 | 14 | 3684 | 0.317 | 0.999 |
2) Set the crossover rate $P_c=0.9$, the mutation rate $P_m=0.02$. We use segment crossover and mutation, set segment length $SL=6$. For crossover, find crossover start index $i\in{[1,9]}$ for parent chromosomes. For mutation, also find mutation start index in $[1,9]$ to reverse the bits in the segment, i.e. set the bit 0 if it was 1, set the bit 1 if it was 0. By gene operation we generate the next generation. we find the fittest individual and record its code. Comparing with the global optimal individual(fittest up to now), we update the global optimal individual by each iteration. When stopping rule satisfied, the algorithm gets the solution of the problem.