CHAPTER 4: DIFFERENTIAL EVOLUTION WITH ADAPTIVE
4.3.3 ARDE-SPX: Adaptive Repository with Fitness Based Selection
Algorithm 4.4: Update the value of πΆπ π scheme
01: Input: πΆπ π (mean value of previous successful πΆπ ), ππΆπ (set of successful crossover rates), π = 1.5 02: Output: πΆπ Μπ (updated mean value of πΆπ )
03: BEGIN
04: Step 1: πππππππ€ = β πππ€ππ((πππ€ππ(πΆπ |π π,π)
πΆπ | ),1/π)
|ππΆπ |
π=1 where πΆπ πβ ππΆπ
05: Step 2: π€πΆπ = 0.9 + 0.1 Γ ππππ(0,1)
06: Step 3: πΆπ Μ = π€π πΆπ Γ πΆπ π+ (1 β π€πΆπ ) Γ πππππππ€ 07: END
Algorithm 4.5: Generate πΉ value scheme
01: Input: π (the cellβs index in the repository), πΉπ (mean value of πΉ) 02: Output: πΉ (new πΉ value)
03: BEGIN
04: IF (βπΉπβ in πΆππππ ) THEN πΉ = πππππ(πΉπ, 0.1) ELSE πΉ = πππππ(πΉπ, 0.1) 05: END
Algorithm 4.6: Generate πΆπ value scheme
01: Input: π (the cellβs index in the repository), πΆπ π (mean value of πΆπ ) 02: Output: πΆπ (new πΆπ value)
03: BEGIN
04: IF (βπΆπ πβ in πΆππππ ) THEN πΆπ = πππππ(πΆπ π, 0.1) ELSE πΆπ = πππππ(πΆπ π, 0.1) 05: END
restriction on negative fitness function. Finally, it is a fast technique because it does not require any further calculations for the average of fitness or any other population statistics, all the solutions are sent to the same processor using only their relative fitness values (Elsayed, Sarker, & Essam, 2014).
The basic idea of FTS is to stochastically select individuals from the current generation to create the basis of the next generation. The selection process has replicated nature in that the individuals with better fitness values will tend to have better chance to survive to the next generation; whereas the individuals with weaker fitness values will have less probability to survive. The general idea of the FTS can be encapsulated as follows:
ο· Evaluate each individual using the fitness function to get the fitness values ππ.
ο· Set a value to the selection probability ππ β [0,1]. In practice, it has been found that it is always better to set the value of ππ to be greater than 0.5 in order to favor the fittest individuals and increase the selection pressure. The tournament selection with ππ = 1.0 is called deterministic tournament and the tournament selection with ππ < 1.0 is called stochastic tournament.
ο· Determine the tournament size ππ β [2, ππ], because at least two individuals should be involved in the competition. In practice, the larger the tournament size, the higher probability that the new population will contain individuals with fitness values above average. The lower tournament size will produce population consists of individuals with low fitness values.
ο· Generate randomly uniformly distributed number π β [0,1] . Then if π β€ ππ, the fitter candidate individual among the ππ individuals is selected; otherwise the weaker individual is chosen.
The last two steps are repeated until the desired number of survival individuals is obtained. Table 4.1 illustrates step-by-step on how to get the number of copies for 5
individuals using the simple fitness function, f(x)= π₯2. The problem is minimization of the fitness function. The values of ππ and ππ are set to 0.7 and 2, respectively.
Table 4.1: The π₯2 example of fitness tournament selection detailed steps
No. Individual x f(x)= ππ Compete individuals r Winners
1 11001 25 625 2 1 0.46 2
2 01100 12 144 4 2 0.39 2
3 00111 7 49 1 3 0.78 1
4 11100 28 784 3 5 0.50 3
5 10001 17 289 5 4 0.14 5
From Table 4.1, it can be noted that individual 2 has two copies to be included in the next generation because of its low fitness value compared to other individuals; whereas individual 4 fails to have even one copy. However, individual 3, even with its low fitness value, could obtain only one copy to be included in the next generation. For this reason, it is preferable to use either deterministic tournament or at the very least set the selection pressure to high probability values. The standard procedure of the FTS algorithm is shown in Algorithm 4.7. In this algorithm, the function bestind returns the best individual from a set of solutions, and worstind returns the worst individual from a set of solutions.
Algorithm 4.7: The standard FTS algorithm
01: Input: Np (population size), π (solution vectors), ππ (selection probability), and ππ (tournament size) 02: Output: M (mating pool)
03: Begin
04: Step 1: Evaluate each individual using fitness function, ππ= π(ππ), (π = 1,2 β¦ , ππ) 05: Step 2: WHILE (π < ππ) DO
06: Step 2.1: Select ππ individuals randomly from the current population 07: Step 2.2: Generate uniformly random number,
π = ππππ(0,1) 08: Step 2.3: Selection of the survival individual
if ( π β€ ππ) then ππ= πππ π‘πππ (π1, π2, β¦, πππ )
else ππ= π€πππ π‘πππ (π1, π2, β¦, πππ ) 09: Step 2.4: π = π + 1
10: END
The FTS method has been used as the base technique for the new adaptive procedure of the ARDE algorithm. This new adaptive procedure is implemented in conjunction with
the selection step of DE, as follows:
Step 1 (Repository Construction): In the same selection step, a repository of empty cells is created. This repository is a result of uniting the two initial repositories of the DE strategies and the parameter control schemes into one repository called adaptive repository (π΄π ). The address of each cell in this repository is one combination of the DE strategies and the parameter control schemes (DE strategy, πΉ adaptation scheme and/or πΆπ adaptation scheme) that are involved in the ARDE algorithm. So, the total number of the cells is 20 because there are six DE strategies, two πΉ adaptation schemes, and two πΆπ adaptation schemes to be involved in constructing the π΄π ; so the total number is (6 Γ 2 Γ 2) β 4 = 20 cells. This number is subtracted by 4 because the DE/current-to-pbest/1 with archive and DE/rand-to-pbest/1 with archive strategies do not require crossover strategy. The content of the cell is the fitness value(s) that has been obtained from applying its relative combination to the corresponding individual(s);
otherwise, it is an empty cell if its relative combination has not been attempted in the search process. Figure 4.2 depicts the strategies and schemes combinations repository in the ARDE.
Step 2 (Individuals Classification): In the selection step of ARDE, the target vectors π(π‘)βs and the trial vectors π(π‘)βs are first evaluated. Then a one-by-one competition is started to determine the vectors of the next generation π(π‘ + 1)βs. These new vectors are either successful individuals (i.e. the trial vectors that their fitness values are better than their corresponding target vectors after applying the DE strategy and parameter control schemes) or failure individuals (i.e. the target vectors that their fitness values are still better than their corresponding trial vectors even after applying the DE strategy and the parameter control schemes).
Step 3 (Averaging Cells): In this step, the cell that contains more than one fitness value is averaged using the equation,
πππππ = βππππ=1πππ,π
ππππ (4.5)
where ππ,π is the fitness values and ππππ is the total number of fitness values in cell π. So, the result is a repository with cells that are either empty from a value (non-attempted in the search process) or occupied with a value (attempted in the search process).
Step 4 (Cells Selection): In this step of ARDE, the π(π‘ + 1) individuals are generated by assigning DE strategies and parameter control schemes to the π(π‘ + 1)sβ successful and failure individuals using an adaptive technique as,
Step 4.1: For the successful individuals, the FTS mechanism is used to assign the DE strategies and parameter control schemes to them from the π΄π created in Step 1.
In this adaptive method, the same table of FTS is created with only one difference is that the column of individuals is replaced with a column that includes the attempted cells of the repository with their average fitness values, as illustrated in Table 4.2.
Then, for each successful individual, the FTS procedure determines which combination is to be assigned to it.
Table 4.2: The FTS method used to assign the DE strategies and parameter control schemes to the successful individuals
Successful Individuals
Repository of Strategies (AR)
Compete
Cells r Winner Cell
Cells Cellsβ
Avg.
Fitness Cell
No.
DE Strategies F Scheme
CR Scheme Individual
11
1 DE/current-to-pbest/1/bin
Fc CRc 9.703E+04 2 1 0.46 1
Individual 23
2 DE/current-to-pbest/1
Fc - 1.090E+05 4 2 0.39 4
Individual 15
3 DE/rand-to-pbest/1/bin
Fn CRn 8.386E+04 1 3 0.78 1
Individual 30
4 DE/current-to-pbest/1/exp
Fn CRc 6.236E+04 3 5 0.50 3
Individual 45
5 DE/rand-to-pbest/1/exp
Fc CRn 1.129E+05 5 4 0.14 4
In the same table, the problem is minimization and the values of ππ and ππ are set to 0.7 and 2, respectively.
In the same step, two counters are created. The first counter is called πΆππ’ππ‘π which records the number of times its corresponding cell has been selected during one generation. The second counter is called πΆππ’ππ‘π€ which records the number of times in which this cell has won the competition in FTS.
Step 4.2: For the failure individuals, a re-initialization mechanism is used to assign a combination of the strategies and schemes from the attempted and non-attempted cells of the π΄π with equal probability. In case there is not non-attempted cell, then the selection of combinations from the π΄π is applied among the attempted cells with equal probability.
Step 5 (Repository Cleaning, Rewarding, and Penalizing Processes):
Step 5.1 (Cleaning Process): In this step a cleaning mechanism is applied to discriminate the individuals on the basis of the age. In this mechanism the concept of
"history" or βfirst-in-first-out (FIFO)β technique is used to eliminate the oldest fitness values in the cells. For each fitness value stored in a cell, its generation number (i.e., its history of birth) is stored too. Then cleaning is applied to those old fitness values existing in the π΄π βs cells. A fitness value in a cell of the π΄π can be tagged as "old" if its history is earlier than the current generation number by 10 generations. For example, if the current number of generations is 11, then the clean operation is applied to all those fitness values with history equals to 1. And at generation 12, the clean operation removes all fitness values with history 2, and so on. Accordingly, the cell that contains one fitness value with βoldβ tag is turned to be empty cell (non-attempted).
Figure 4.2: The complete structure of the adaptive repository, π΄π in the ARDE algorithm
Repository of Parameters Control Schemes and DE Strategies
Cell 1
Cell 2
Cell 3
Cell 4
Cell 5
Cell 6
Cell 7
Cell 8
Cell 9
Cell 10
Cell 11
Cell 12
Cell 13
Cell 14
Cell 15
Cell 16
Cell 17
Cell 18
Cell 19
Cell 20 DE/rand-to-pBest/1/bin
Fn; CRc
DE/rand-to-pBest/1/bin Fn; CRn
DE/current-to-pBest/1/exp Fc; CRc
DE/current-to-pBest/1/exp Fc; CRn
DE/current-to-pBest/1/exp Fn; CRc
DE/current-to-pBest/1/exp Fn; CRn
DE/current-to-pBest/1/bin Fc; CRc
DE/current-to-pBest/1/bin Fc; CRn
DE/current-to-pBest/1/bin Fn; CRc
DE/current-to-pBest/1/bin Fn; CRn
DE/current-to-pBest/1 Fc
DE/rand-to-pBest/1 Fn
DE/current-to-pBest/1 Fc
DE/current-to-pBest/1 Fn
DE/rand-to-pBest/1/exp Fc; CRc
DE/rand-to-pBest/1/exp Fc; CRn
DE/rand-to-pBest/1/exp Fn; CRc
DE/rand-to-pBest/1/exp Fn; CRn
DE/rand-to-pBest/1/bin Fc; CRc
DE/rand-to-pBest/1/bin Fc; CRn
Empty Cell
(Non-attempted Cell) Occupied Cell
(attempted Cell)
Cell Content
Ft=1
Ft=1 Ft=2 Ft=3
Ft=4 Fitness
Value Fitness Age
Step 5.2 (Rewarding and Penalizing Processes): At each generation, the superior cell (cell with the highest π) is rewarded by eliminating its worst fitness value. The inferior cell (cell with the lowest π) is penalized by eliminating its best fitness value;
where π is the cellβs winning probability for each attempted-cell selected in the FTS mechanism and calculated as,
πΆππππ . π = πΆππππ . πΆππ’ππ‘π€ πΆππππ . πΆππ’ππ‘π
(4.6)
where π is the index of the attempted-cell that participated in the FTS mechanism during the current generation.
These steps of ARDE evolution are repeated till the stopping criteria are met. In Figure 4.2 and Table 4.2, the letters π and π attached with πΉ and πΆπ refer to the parameters adaptation schemes of Normal distribution and Cauchy distribution, respectively.
