# A Genetic Optimization Algorithm Based on Adaptive Dimensionality Reduction

Authors: Tai Kuang; Zhongyi Hu; Minghai Xu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

With the rise of big data in cloud computing, many optimization problems have gradually developed into high-dimensional large-scale optimization problems. In order to address the problem of dimensionality in optimization for genetic algorithms, an adaptive dimensionality reduction genetic optimization algorithm (ADRGA) is proposed. An adaptive vector angle factor is introduced in the algorithm. When the angle of an individual’s adjacent dimension is less than the angle factor, the value of the smaller dimension is marked as 0. Then, the angle between each individual dimension is calculated separately, and the number of zeros in the population is updated. When the number of zeros of all individuals in a population exceeds a given constant in a certain dimension, the dimension is considered to have no more information and deleted. Eight high-dimensional test functions are used to verify the proposed adaptive dimensionality reduction genetic optimization algorithm. The experimental results show that the convergence, accuracy, and speed of the proposed algorithm are better than those of the standard genetic algorithm (GA), the hybrid genetic and simulated annealing algorithm (HGSA), and the adaptive genetic algorithm (AGA).


---

## Body

## 1. Introduction

High-dimensional optimization problems have become increasingly prevalent in many fields, for example, radar waveform optimization [1, 2] and water quality monitoring [3]. Recently, major breakthroughs have been made with respect to solving such problems. Tuo et al. [4] proposed a global optimization algorithm that used the membrane calculation principle to solve high-dimensional functions in 2011. Their algorithm, by implementing high-dimensional segmentation, achieved the segmentation of a high-dimensional space into a low-dimensional one, thereby improving the performance. Also addressing the problem of high-dimensional space processing, Chen et al. [5] described an approach that established a sparse regression model by utilizing the geometric structural features of the approximate solution set, mapping the high-dimensional target space into a low-dimensional one. In 2015, Chen et al. [6] designed a congestion control strategy based on the concept of open angles and compared it against the indication-based evolutionary algorithm (IBEA) [7], NSGA III (nondominated sorting genetic algorithm III) [8], and the grid-based evolutionary algorithm (GrEA) [9]. The results indicated a significant improvement by the proposed algorithm. In the same year, Zheng et al. [10] proposed a high-dimensional multiobjective evolutionary algorithm based on information separation. Although this algorithm decomposed the high-dimensional space into a low-dimensional one, it did not remove the excess dimensions. In order to maintain a balance between the convergence and distributed features of the objective evolutionary algorithms, Bi and Wang [11] proposed a high-dimensional objective evolutionary algorithm based on an angle penalty. In 2018, He et al. [12] combined a dimensionality reduction and differential evolution algorithm to solve the knapsack problem. The experimental results showed that this algorithm achieved good accuracy and stability and is suited for solving large-scale problems. Liang et al. [13] first conducted an analysis of the features of large-scale high-dimensional problems and developed a coevolutionary dynamic particle swarm optimization algorithm, dividing the whole swarm into different groups. Unlike the improvement targeting the number of dimensions, Xia et al. [14] proposed a fitness-based multiplayer swarm optimization algorithm (FMPSO), with the addition of a new component into the particle velocity update rules, called the “subspace learning” component. During the evolutionary process, two adjustment operators were introduced to adjust the roles and number of objective dimensions of the particles. Xu et al. [15] proposed a multidimensional learning strategy based on the experience of the best individuals, which was used to discover and integrate valuable information from the best swarm solution. In their experimentation, 16 classical benchmark functions, 30 CEC 2014 testing functions, and one actual optimization problem were used. This algorithm demonstrated higher convergence, accuracy, and speed. In 2015, Wu et al. [16] described a nondominated sorting genetic algorithm utilizing fractal dimensions and an elitist strategy for feature selection. This algorithm could successfully reduce the number of dimensions for the objective problems. This algorithm, however, only improved the classification accuracy as compared with the standard genetic algorithms to a limited extent. He and Yen [17] used the minimum included angle between two vectors to look for similar individuals, among which the individuals with poor convergence were deleted. However, it was still difficult to set the difference threshold. Xiang et al. [18] implemented priority selection based on the maximum included angle between two vectors, thereby ensuring the diversity of the swarm. However, a good strategy for determining the angle threshold was still not provided. Furthermore, the U-model methodology, which is a generic systematic approach to convert a nonlinear polynomial model into a controller output u(t − 1) -based time-varying polynomial model, has been studied for facilitating a nonlinear control system design over the last decade [19–22]. Given the aforementioned, we define the concept of an adaptive vector angle factor, which changes with the swarm size and number of dimensions. In this paper, the adaptive vector angle factor is used for realizing dimensionality reduction with a GA. At the same time, it also provides a reference for U-model approaches in algorithm implementation.


## 2. The Proposed ADRGA Algorithm

### 2.1. Vector Angle Factor

Dimensionality reduction is a good approach for solving large-scale problems. However, most dimensionality reduction algorithms are random processes; those dimensions carrying important information or those crucial for objective problem solving may be deleted. Consider a 2D vector coordinate (a, b) in Figure 1. When the included angle θ between this vector and the x-axis (y-axis) is infinitely small, the vector coordinate is approximated to (a, 0) or (0, b). In this way, the 2D vector is approximately mapped into a one-dimensional one, as illustrated in Figure 2. Similarly, a 3D vector can be approximately mapped into a 2D or one-dimensional one, depending on the set threshold for the included angle between the two vectors. Apparently, setting an appropriate threshold for the included angle between the two vectors is very important.Figure 1
2D vector representation.Figure 2
Changes of the included angle between the two vectors.The dimension describes the precision of the required solution target characteristics. For example, when describing a pen in one dimension, only its length or width can be described, and so it is impossible to perform dimensionality reduction through mapping. In this case, the threshold for the included angleθ between the two vectors must be close to 0. When a pen has two dimensions, both its length and width can be described. At this point, if the included angle between the two vectors is smaller than a certain threshold, the dimension where the smaller values are located can be neglected. In this case, the threshold for the included angle θ between the two vectors may be close to a value above 0. The threshold range can be set according to an individual problem. When three dimensions are used for the description, not only the pen’s length and width but also its cross-sectional radius can be described. Therefore, the threshold for the included angle θ between the two vectors is larger than that for the 2D situation. As the number of dimensions increases, the threshold range of the included angle θ between the two vectors increases as well. Experiments have shown that the threshold range cannot be infinitely large. Whatever the number of dimensions, the threshold must be maintained within the interval 0,π/4. In this paper, the vector included angle factor is represented by the sigma function in equation (1), which is a monotonically increasing function and also a bounded function:(1)sigmax=11+e−x,where x∈−∞,+∞,sigma∈0,1.The vector included angle factor proposed in this study must be within the interval0,π/4. An adaptive vector angle factor can be obtained by transformation of the sigma function, as shown in equation (2), where a is the control parameter, a=4.3926, b is the adjustment parameter, b=3.6072, and D is the number of dimensions. When the tangent of the included angle between the two vectors in adjacent dimensions tanθ<tansigma∗, the dimension where the smaller value is located is denoted as 0 (θ=xmi/xmj, xmi is the i-th dimension of the m-th individual; xmj is the j-th dimension of the m-th individual).(2)sigma∗D=a∗11+e−D−b.


### 2.2. ADRGA Workflow

ADRGA targets high-dimensional swarms. First, the tangent value of the included angle between the two vectors in adjacent dimensions is calculated for each individual and is compared against the adaptive vector angle factorsigma∗. If it is smaller than the latter, the dimension where the smaller value of the individual is located is denoted as 0. Then, using the same method, the tangent values of the included angle between the two vectors in adjacent dimensions for all individuals are compared against sigma∗. Finally, the number of 0 elements in each dimension in the updated swarm pop is determined; if it is above the critical value Q, then this dimension is deleted.Adaptive dimensionality reduction is feasible following the principle mentioned above. The pseudocode for ADRGA is shown in Algorithm1 (Pc is the probability of crossover, Pm is the probability of mutation, N is the swarm size, G is the number of generations upon termination of evolution, T is the number of tests, Q is the critical value).Algorithm 1: ADRGA.
Step 1: initialize parametersPc, Pm, N, G, T, and Q and randomly generate the first swarm pop
Step 2: fori<popsize
Step 3: calculate the tangent valuetanxin/xin+1 of the included angle between the two vectors in adjacent dimensions for each individual popi
Step 4: iftanxin/xin+1<4.39261/1+e−D−3.6072, then update the value of the n-th dimension of the i-th individual to 0; otherwise, do not update the value
Step 5: return to step 2
Step 6: calculate the number of 0 elements in each dimension for the updated swarmpop; if it is above the critical value Q, then delete this dimension
Step 7: obtain the updated swarmpop
Step 8: calculate the fitness valueFi of each individual in the swarm pop
Step 9: initialize the new swarmnewpop
Step 10: select two individuals from the swarmpop according to the fitness using the proportional selection algorithm
Step 11: ifrandom0,1<Pc, then move on to step 12; otherwise, implement step 13
Step 12: apply the crossover operator according to the crossover probabilityPc on the two individuals
Step 13: ifrandom0,1<Pm, then move on to step 14
Step 14: apply the mutation operator according to the mutation probabilityPm on the two individuals
Step 15: add the two new individuals into the swarmnewpop
Step 16: repeat this process until theN-th generation is produced; otherwise, return to step 4
Step 17: replacepop with newpop
Step 18: repeat this process until the number of generations exceedsG; otherwise, return to step 8
Step 19: end


## 2.1. Vector Angle Factor

Dimensionality reduction is a good approach for solving large-scale problems. However, most dimensionality reduction algorithms are random processes; those dimensions carrying important information or those crucial for objective problem solving may be deleted. Consider a 2D vector coordinate (a, b) in Figure 1. When the included angle θ between this vector and the x-axis (y-axis) is infinitely small, the vector coordinate is approximated to (a, 0) or (0, b). In this way, the 2D vector is approximately mapped into a one-dimensional one, as illustrated in Figure 2. Similarly, a 3D vector can be approximately mapped into a 2D or one-dimensional one, depending on the set threshold for the included angle between the two vectors. Apparently, setting an appropriate threshold for the included angle between the two vectors is very important.Figure 1
2D vector representation.Figure 2
Changes of the included angle between the two vectors.The dimension describes the precision of the required solution target characteristics. For example, when describing a pen in one dimension, only its length or width can be described, and so it is impossible to perform dimensionality reduction through mapping. In this case, the threshold for the included angleθ between the two vectors must be close to 0. When a pen has two dimensions, both its length and width can be described. At this point, if the included angle between the two vectors is smaller than a certain threshold, the dimension where the smaller values are located can be neglected. In this case, the threshold for the included angle θ between the two vectors may be close to a value above 0. The threshold range can be set according to an individual problem. When three dimensions are used for the description, not only the pen’s length and width but also its cross-sectional radius can be described. Therefore, the threshold for the included angle θ between the two vectors is larger than that for the 2D situation. As the number of dimensions increases, the threshold range of the included angle θ between the two vectors increases as well. Experiments have shown that the threshold range cannot be infinitely large. Whatever the number of dimensions, the threshold must be maintained within the interval 0,π/4. In this paper, the vector included angle factor is represented by the sigma function in equation (1), which is a monotonically increasing function and also a bounded function:(1)sigmax=11+e−x,where x∈−∞,+∞,sigma∈0,1.The vector included angle factor proposed in this study must be within the interval0,π/4. An adaptive vector angle factor can be obtained by transformation of the sigma function, as shown in equation (2), where a is the control parameter, a=4.3926, b is the adjustment parameter, b=3.6072, and D is the number of dimensions. When the tangent of the included angle between the two vectors in adjacent dimensions tanθ<tansigma∗, the dimension where the smaller value is located is denoted as 0 (θ=xmi/xmj, xmi is the i-th dimension of the m-th individual; xmj is the j-th dimension of the m-th individual).(2)sigma∗D=a∗11+e−D−b.


## 2.2. ADRGA Workflow

ADRGA targets high-dimensional swarms. First, the tangent value of the included angle between the two vectors in adjacent dimensions is calculated for each individual and is compared against the adaptive vector angle factorsigma∗. If it is smaller than the latter, the dimension where the smaller value of the individual is located is denoted as 0. Then, using the same method, the tangent values of the included angle between the two vectors in adjacent dimensions for all individuals are compared against sigma∗. Finally, the number of 0 elements in each dimension in the updated swarm pop is determined; if it is above the critical value Q, then this dimension is deleted.Adaptive dimensionality reduction is feasible following the principle mentioned above. The pseudocode for ADRGA is shown in Algorithm1 (Pc is the probability of crossover, Pm is the probability of mutation, N is the swarm size, G is the number of generations upon termination of evolution, T is the number of tests, Q is the critical value).Algorithm 1: ADRGA.
Step 1: initialize parametersPc, Pm, N, G, T, and Q and randomly generate the first swarm pop
Step 2: fori<popsize
Step 3: calculate the tangent valuetanxin/xin+1 of the included angle between the two vectors in adjacent dimensions for each individual popi
Step 4: iftanxin/xin+1<4.39261/1+e−D−3.6072, then update the value of the n-th dimension of the i-th individual to 0; otherwise, do not update the value
Step 5: return to step 2
Step 6: calculate the number of 0 elements in each dimension for the updated swarmpop; if it is above the critical value Q, then delete this dimension
Step 7: obtain the updated swarmpop
Step 8: calculate the fitness valueFi of each individual in the swarm pop
Step 9: initialize the new swarmnewpop
Step 10: select two individuals from the swarmpop according to the fitness using the proportional selection algorithm
Step 11: ifrandom0,1<Pc, then move on to step 12; otherwise, implement step 13
Step 12: apply the crossover operator according to the crossover probabilityPc on the two individuals
Step 13: ifrandom0,1<Pm, then move on to step 14
Step 14: apply the mutation operator according to the mutation probabilityPm on the two individuals
Step 15: add the two new individuals into the swarmnewpop
Step 16: repeat this process until theN-th generation is produced; otherwise, return to step 4
Step 17: replacepop with newpop
Step 18: repeat this process until the number of generations exceedsG; otherwise, return to step 8
Step 19: end


## 3. Experimental Results

Simulation was carried out using MATLAB 2014b under Windows 7 (also applicable to a higher version). A comparison was made between ADRGA, the standard GA [1], the hybrid genetic and simulated annealing algorithm (HGSA) [23], and the adaptive genetic algorithm (AGA) [24].In this study, 8 standard composite testing functions were used, namely,F1∼F8, as shown in Table 1. F1∼F3 are high-dimensional unimodal functions, which only have one global best solution; F4∼F8 are high-dimensional multimodal functions, which have several local best solutions, but only one global best solution. The latter are generally hard to optimize. The global best solutions of all testing functions were 0. Since some testing functions have several optimal solutions, the algorithm is very likely to be trapped in a local optimum. This aspect may be challenging for the proposed ADRGA algorithm.Table 1
Benchmark testing functions.
Testing function
Number of dimensions
Feasible solution space
F
1
=
∑
i
=
1
D
x
i
2
1000
[−100, 100]
F
2
=
x
1
−
1
2
+
∑
i
=
1
D
i
∗
2
x
i
2
−
x
i
−
1
2
1000
[−10, 10]
F
3
=
∑
i
=
1
D
x
i
i
+
1
1000
[−1, 1]
F
4
=
−
a
∗
exp
−
b
1
/
D
∑
i
=
1
D
x
i
2
−
exp
1
/
D
∑
i
=
1
D
cos
c
x
i
+
a
+
exp
1
,
a
=
20
,
b
=
0.2
,
c
=
2
π
1000
[−32.768, 32.768]
F
5
=
∑
i
=
1
D
x
i
2
−
10
∗
cos
2
∗
π
∗
x
i
+
10
1000
[−5.12, 5.12]
F
6
=
∑
i
=
1
D
x
i
2
/
4000
−
∏
i
=
1
D
cos
x
i
/
i
+
1
1000
[−600, 600]
F
7
=
sin
2
π
ω
1
+
∑
i
=
1
D
−
1
ω
i
−
1
2
1
+
10
sin
2
π
ω
i
+
1
+
ω
D
−
1
2
1
+
sin
2
2
π
ω
D
ω
i
=
1
+
x
i
−
1
/
4
1000
[−10, 10]
F
8
=
418.9829
D
−
∑
i
=
1
D
x
i
sin
x
i
1000
[−500, 500]In the experimentation, the value of the fitness functionf was the function value at the current position. The parameters of the GA were configured as follows: crossover probability Pc = 0.70, mutation probability Pm = 0.05, number of iterations FEs = 1000, swarm size sizepop = 50, number of dimensions D = 1000, and the critical value Q = 1.Each of the four algorithms was run 20 times on the 8 testing functions, and the means and standard deviations are shown in Table2. Table 3 presents the improvement percentages of the optimal solutions using ADRGA as compared with the other three algorithms, calculated as follows: (mean of other algorithm−mean of ADRGA)∕(mean of other algorithm). When optimizing these 8 classical testing functions, ADRGA could obtain a solution closer to the global best solution compared to the other algorithms, as shown in Table 2. This was especially true for the testing functions F3, F4, and F6. But on the other testing functions, although a better solution was obtained using ADRGA, it failed to find the global optimum and was still far from achieving this goal. As shown in Table 3, the higher the improvement percentage, the greater the amplitude of performance improvement of ADRGA would be, and vice versa. Although a solution closer to the global optimum was obtained for F4 in Table 2, its improvement percentage was smaller than for the other 7 functions, indicating that F4 was less influenced by the number of dimensions.Table 2
Optimization results of the different algorithms on 8 standard composite testing functions.
Function
Mean and standard deviation
GA
HGSA
AGA
ADRGA
F
1
1.78e + 05 ± 6.12e + 03
8.44e + 05 ± 2.02e + 05
1.30e + 06 ± 2.07e + 05
9.46e + 04 ± 2.65e + 03
F
2
3.65e + 07 ± 1.85e + 06
4.08e + 08 ± 1.10e + 08
8.04e + 08 ± 2.36e + 08
9.97e + 06 ± 8.74e + 05
F
3
1.11e − 07 ± 1.84e − 07
0.1793 ± 0.0885
3.95e − 06 ± 5.84e − 06
7.22e − 08 ± 1.77e − 07
F
4
13.2492 ± 0.1323
18.3028 ± 0.7001
19.9960 ± 0.0226
12.6016 ± 0.2194
F
5
9.68e + 03 ± 86.5390
1.21e + 04 ± 512.6435
1.31e + 04 ± 369.5460
5.84e + 03 ± 147.5333
F
6
1.61e + 03 ± 64.0915
7.37e + 03 ± 1.56e + 03
1.17e + 04 ± 1.76e + 03
874.5617 ± 40.2598
F
7
8.62e + 03 ± 366.1671
2.83e + 04 ± 4.72e + 03
4.01e + 04 ± 5.71e + 03
4.52e + 03 ± 280.3275
F
8
3.70e + 05 ± 2.42e + 03
4.17e + 05 ± 757.5530
3.98e + 05 ± 2.56e + 03
2.27e + 05 ± 5.62e + 03Table 3
Improvement percentage of optimal solutions for ADRGA.
Function
Algorithm
GA (%)
HGSA (%)
AGA (%)
F
1
46.85
88.79
92.72
F
2
72.68
97.56
98.76
F
3
34.95
100.00
98.17
F
4
4.89
31.15
36.98
F
5
39.67
51.74
55.42
F
6
45.68
88.13
92.53
F
7
47.56
84.03
88.73
F
8
38.65
45.56
42.96The number of dimensions after dimensionality reduction and the average number of dimensions after running each algorithm 20 times are shown in Table4. The number of residual dimensions varied after each run, indicating that the dimensionality reduction with the proposed algorithm changed with the initialized swarm in each run. Therefore, valuable information could be preserved when reducing the number of dimensions. Under the similar minimum included angle between the two vectors, the larger the included angle for the newly generated swarm, the smaller the number of dimensions deleted would be, and vice versa. As shown in Table 3, the maximum number of dimensions deleted was 40%, and the minimum was 34%. The maximum number of dimensions deleted was not above 50%, but it was ensured that the dimensions were not deleted randomly. Table 4 provides a better proof of the adaptive features of the proposed algorithm.Table 4
Number of residual dimensions and means after each cycle of dimensionality reduction using each algorithm.
Function
Experiment
1
2
3
4
⋯
10
11
⋯
16
17
18
19
20
Mean
F
1
642
637
635
631
⋯
614
656
⋯
621
633
625
631
641
636.65
F
2
620
638
654
622
⋯
656
641
⋯
634
635
649
660
634
639.25
F
3
635
657
652
646
⋯
633
637
⋯
620
633
643
612
649
638.45
F
4
642
637
635
631
⋯
614
656
⋯
621
633
625
631
641
636.65
F
5
620
638
654
622
⋯
656
641
⋯
634
635
649
660
634
639.25
F
6
635
657
652
646
⋯
633
637
⋯
620
633
643
612
649
638.45
F
7
653
632
638
648
⋯
650
639
⋯
612
661
641
647
619
639.05
F
8
646
625
619
641
⋯
649
641
⋯
638
660
647
600
631
638Figure3 shows the comparison of convergence for the eight testing functions F1∼F8. The x-axis is the number of fitness calculations, and the y-axis is the mean fitness value. As shown in Figure 3, ADRGA had a faster convergence speed and accuracy on the functions F1, F2, F5, F6, and F7, though it was more likely to be trapped in a local optimum. For the testing function F3, the convergence curves of ADRGA and GA nearly coincided. This was because the value range of the independent variable in function F3 was [−1, 1]. Therefore, when the numbers of dimensions were 600 and 1000, the difference was negligibly small. This also demonstrated that the impact on F3 was small if the number of dimensions did not change significantly. For the multimodal function F4, the convergence curve of ADRGA not only had a faster convergence speed but also showed a more apparent decreasing trend as compared with the other six testing functions (except for F8). This suggested that ADRGA was not trapped in the local optimum on F4. For the testing function F8, ADRGA outperformed all the other algorithms. There was a dramatic improvement in the convergence accuracy and speed with ADRGA, and the convergence curve displayed a more apparent decreasing trend. For the five high-dimensional multimodal functions, ADRGA achieved better results on two testing functions, indicating that this algorithm was more appropriate for solving high-dimensional multimodal targets.Figure 3
Convergence curve of different algorithms compared with the standard composite test function (including AGA, GA, HGSA, and ADRGA proposed in this paper). (a) FunctionF1. (b) Function F2. (c) Function F3. (d) Function F4. (e) Function F5. (f) Function F6. (g) Function F7. (h) Function F8.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)


## 4. Conclusion

This paper aims to find the optimal solutions for high-dimensional testing functions based on GAs. Similarity, the minimum included angle between the two vectors is utilized, and a GA approach for adaptive dimensionality reduction is proposed. The specific steps for dimensionality reduction are provided. The critical valueQ is defined to ensure the diversity of the swarm information. It was then demonstrated via eight testing functions that ADRGA displays faster convergence speed and higher accuracy than other algorithms. However, a major problem with ADRGA is that the critical value Q is prespecified instead of changing with the swarm size and number of dimensions in real-time. In the future, the critical value Q will be the focus in order to achieve better control of the number of dimensions in the swarm and more accurate dimensionality reduction.



---

*Source: 8598543-2020-05-11.xml*