Advanced Control Techniques—Assignment

Introduction

Inspired by the process of natural selection and principle of genetics, genetic algorithms are implemented to handle various optimization problems. Basic theorem and mathematical derivation has given by J. H. Holland. This research report is intended as a solution, performing optimization on two fitness functions. The reminder of this report is structured as follows. Section 2 reviews the relevant fundamentals of genetic algorithm, which includes the detailed structure with its component parts. In Section 3, the maximal of two fitness function are given with the optimal populations which contain exhaustive revolutionary process. Conclusions of the report are presented in Section 4.

Methods

Genetic algorithm is constructed from distinct components, which are the chromosome encoding, the fitness function, selection, crossover and mutation. Starting with a randomly generated population of chromosomes, a genetic algorithm carried out a process of fitness based selection and recombination to produce a successor population, the next generation. During the recombination, parent chromosomes which encoded by binary strings are selected, depending on their fitness. In this case, those chromosomes who can obtain larger function values own larger fitness, and the possibilities of producing offspring increase. Although crossover may decrease the fitness of some individuals, the population fitness will be improved. Mutations ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children. As this process is iterated, a sequence of successive generations evolves and the average fitness of the chromosomes tends to increase until stopping criterion is reached. Two functions which needed to be optimized are defined as follows:

Encoding

Binary encoding is implemented to represent the chromosome, which is a string of bits, 0 or 1. The bit strings with 10 genes can provide a solution space consisting individuals. Take function as an example, the domain of function is ,and the standard binary encoding can only represent integer, which cannot satisfy the demanded accuracy. Thus, a linear mapping, which map domain: to , is introduced. Obviously, a binary string, which has 18 genes, provides diverse individuals. In conclusion, the chromosome with 18 genes and the chromosome with 15 genes is adopted, encoding the domains of function respectively.

Selection

Roulette wheel selection is a genetic operator for selecting potentially useful solutions for recombination. In roulette wheel selection, the fitness function assigns a fitness to generated individuals. The values, which are achieved by dividing the fitness of a selection by the total fitness of all the selections, determine the possibility that those parents can produce offsprings. If is the fitness of individual in the population, its probability of being selected is

where is the number of individuals in the population. This process is introduced in Algorithm 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
\begin{algorithm}
\caption{Roulette Wheel Selection}
\begin{algorithmic}[1]
\FOR{each $fitness \in [1,IndividualsCount]$}
\IF{$fitness$ is Negative}
\STATE $fitness \Leftarrow 0$;
\ENDIF
\ENDFOR
\STATE $IndividualProb \Leftarrow IndividualFit/PopulationFit$;
\STATE Calculate the $CumulativeSum$ of the $IndividualProb$;
\STATE Sort a random $List \in [0, 1]$;
\STATE $i \Leftarrow 1$;
\STATE $j \Leftarrow 1$;
\WHILE {each $i \in [1,IndividualsCount]$}
\IF{$List \leq CumulativeSum$}
\STATE $i_{th} NewIndividual \Leftarrow j_{th} OldIndividual$;
\STATE $i \Leftarrow i + 1$;
\ELSE
\STATE $j \Leftarrow j + 1$;
\ENDIF
\ENDWHILE
\label{code:ag1}
\end{algorithmic}
\end{algorithm}

Crossover

Crossover is used to combine the genetic information of two parents to generate new offspring. Bit strings are used to be recombined by crossover. Uniform crossover, which uses binary mask, makes the crossover more flexible. By choosing a random crossover mask with the same length of parent’s chromosome, genes are copied from one parent when there is in the crossover mask, the other genes are copied from the other parent when there is in the crossover mask. Thus, offsprings contain a mixture of genes from each parent. In this case, the probability of crossover is .

Mutation

Mutation is used to maintain and introduce diversity in the genetic population. Bit flip mutation is implemented in our solutions, a certain number of bits was selected to perform flip. Mutation happens with a low frequency, probability of mutation occurrence is selected as 0.001 to 0.01. In this case, mutation occurred once on 2 random genes whose population has 288 genes per iteration.

Algorithm

Genetic algorithm can be presented by the following algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
\begin{algorithm}
\caption{Genetic Algorithm}
\begin{algorithmic}[1]
\STATE SET individuals count $N$;
\STATE SET genes count $M$;
\STATE Generate a $N\times M$population matrix $\bm{P}$;
\FOR{each $iter \in [1,LargeNum]$}
\STATE Calculate fitness for each individual;
\STATE \textbf{call} Algorithm 1;
\IF{$random(0 \to 1) > SetProbability$}
\STATE Crossover with a random generated mask;
\ENDIF
\STATE $x \leftarrow random(0 \to N)$
\STATE $y \leftarrow random(0 \to M)$
\STATE Flip $\bm{P}_{x,y}$
\IF{$timeout \cup isOptimalFound$}
\STATE \textbf{break};
\ENDIF
\ENDFOR
\label{code:ag2}
\end{algorithmic}
\end{algorithm}

Results

The proposed algorithm has been implemented on analysis of and , the solution involves finding the maximal and its corresponding locations. The evolutionary processes are also presented in detail.

Analysis of

Apparently, function , whose domain is , acquires the maximum value when , nevertheless, can not be zero. Under this circumstances, the fitness function used in genetic algorithm is defined by the following equation:

where is a small positive real number.

Because of the Roulette Wheel algorithm, which needs positive input, the values calculated by the fitness function may not satisfy that. Thus, we assume that those parents whose fitness is negative cannot produce offsprings. i.e, if the function , let . Algorithm parameter is listed in TABLE 1.

Parameter Name Value
Iteration 600
Individuals Count 8, 8 for x, y
Genes Count 18 per individual
Probability of Crossover 60%
Probability of Mutation 0.6%

Genetic algorithm with 600 iteration finished within 0.133901 seconds on average, the highest fitness value achieved is 0.9998. Those maximal fitness values are recorded on 100th, 200th, 300th iteration and the final iteration. The reason why data dropped between the 300th to final iteration is the fitness remain the same practically. Evolutionary process of 8 groups of individuals is shown in Fig. 1, the maximal fitness and its corresponding individuals are shown in TABLE Maximal fitness and groups, which are marked on the curve of in Fig. 2.

N_th iteration Optimal Groups Optimal Fitness
100 x=-0.3374,y=2.3562 0.2944
200 x=-0.1838,y=0.6664 0.9224
300 x=-0.1836,y=-0.1016 0.9904
600 x=-0.0001,y=-0.0352 0.9998

In Fig. 1, the random generated 8 groups whose fitnesses are around reached 0.9998(fitness) on average at the 230th iteration. We further analyze the varieties of each group, noticing that the improvement of the population’s average fitnesses depends on the mutations occur on the isolated group, which elevated the whole population by crossover. The process can be recognized in 70th, 110th and 260th iteration in Fig. 1.

Analysis of

The function is defined as follows:

where there is no need to tweak the function for satisfying the requirements of genetic algorithm except the domain. in range from , which are considered as the floating number with 4 decimal. That is, we can use chromosomes with 15 bits which have 32768 individuals to encode the domain.

Differ from function which attained maximal value at $(0, 0)$, $f_2$’s maximal value at the “border” of the domain. Evidently, $f_2$ is symmetric with respect to the x-axis and the y-axis, so we investigate on the positive plane. To achieve maximum, for both x, y shall be the largest numbers in the domain which satisfy

Thus, those individuals generated randomly which range from must be rejected to ensure the correctness. In light of this, the following states shall be inserted between line 12-13 in Algorithm 2:

1
2
3
4
5
6
7
8
9
10
11
\begin{algorithm}[!htbp]
\caption{Appendix States}
\begin{algorithmic}[1]
\STATE Check the new individuals;
\IF{individuals out of range}
\STATE \textbf{pass}
\ELSE
\STATE $new\bm{P}_{x, y} \leftarrow \bm{P}_{x, y}$
\ENDIF
\end{algorithmic}
\end{algorithm}

Algorithm parameter is listed in TABLE 3

Parameter Name Value
Iteration 1200
Individuals Count 8, 8 for x, y
Genes Count 15 per individual
Probability of Crossover 60%
Probability of Mutation 0.8%

Genetic algorithm with 1200 iteration finished within 0.2818147 seconds on average, the highest fitness value achieved was 3.6996, which is shown on Fig. 3:

Compared to the fix-step logging strategy for , a variable-step strategy was applied to log the evolutionary progress in this section. If a gap with a certain threshold existed between the maximal fitness calculated by the current population and the last population, we call location who gains the first maximal fitness after the gap where M is gap threshold and i is the iteration after a gap. By connecting the nodes, we obtained the evolutionary progress, EP for short. A sample epoch result with 4 nodes is listed in TABLE 4:

N_th iteration Optimal Groups Optimal Fitness
4 x=1.6486,y=-0.4975 1.6890
15 x=1.8262,y=1.2434 2.5558
41 x=1.8514,y=1.4544 3,2901
157 x=1.8512,y=1.8498 3.6996

Fig. 4 shows a sample progress by connecting , as the figure shows, evolutionary progress started at doesn’t have plenty of chatter, hence this sample are considered as an efficient evolutionary progress.

Conclusions

This report has presented the solutions to function optimization problem. In general, we have some interesting observations on genetic algorithms. The evolutionary progress demonstrated genetic algorithm may show an ultimate efficiency though lack robustness hence the stop criterion is not clear in every problem. Moreover, we noticed that genetic algorithms have a tendency to converge towards local optimum, an evolutionary progress may stuck at some certain points for hundreds of iterations, depending on random mutations. Another problem is we can’t simply deploy parallel computing to accelerate the evolutionary progress because the new population are generated by the last population which has a sequential logic.

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
clear
chroLen = 15; chroNum = 16; i = 1;
chroList = zeros(chroNum, chroLen);
list = zeros(1,1000);
%% generate chromosome
while(i <= chroNum)
preChk = round(rand(1,chroLen));
if b2d(preChk) < 3e4
chroList(i,:) = preChk;
i = i + 1;
end
end
for step = 1:600
%% calculate fitness
a = chroList(1:8,:);b = chroList(9:16,:);
for i = 1:chroNum/2
fitness(i) = calcFitness(a(i,:),b(i,:));
end
%% select chromosome
for i = 1:chroNum/2
if fitness(i) < 0
fitness(i) = 0;
end
end
fitness_ = 0.0001+fitness;
sum_fitness = sum(fitness_);
proba = cumsum(fitness_/sum_fitness);
newChroList = zeros(chroNum,chroLen);
rndList = sort(rand(chroNum/2,1));
i = 1; j = 1;
while i <= chroNum/2
if rndList(i) <= proba(j)
newChroList(i,:) = chroList(j,:);
newChroList(i+8,:) = chroList(j+8,:);
i = i + 1;
else
j = j + 1;
end
end
%% crossover
if(rand(1) > 0.6)
swap = zeros(1,chroLen);
mask = logical(round(rand(1,chroLen)));
for i = 1:2:15
swap(1,mask) = newChroList(i,mask);
newChroList(i,mask) = ...
newChroList(i+1,mask);
newChroList(i+1,mask) = swap(1,mask);
end
end
%% mutation
if(rand(1) > 0)
i = floor(numel(newChroList)...
*rand(1)/chroLen)+1;
m = floor(numel(newChroList)...
*rand(1)/chroLen)+1;
j = mod(round(numel(newChroList)...
*rand(1)),chroLen)+1;
n = mod(round(numel(newChroList)...
*rand(1)),chroLen)+1;
newChroList(i,j) = not(newChroList(i,j));
newChroList(m,n) = not(newChroList(m,n));
end
a = newChroList(1:8,:);
b = newChroList(9:16,:);
for i = 1:chroNum/2
newFitness(i) = ...
calcFitness(a(i,:),b(i,:));
end
if max(newFitness) >= max(fitness)
if ~chk(newChroList)
chroList = newChroList;
end
end
end
\end{lstlisting}
\begin{lstlisting}
function y = calcFitness(a , b)
a_ = (b2d(a)-1e5)/1e4; b_ = (b2d(b)-1e5)/1e4;
y = sin(a_)/a_*sin(b_)/b_;
end