Abstract
The traditional global convergence optimization algorithm is prone to premature convergence and slow convergence in the face of complex non-convex function. To this end, a new intelligent optimization algorithm based on improved fuzzy algorithm for global convergence of non-convex function is proposed. The general model of the optimal problem is designed and the general model of non-convex function is established. The genetic algorithm is used to optimize the non-convex function, and the global convergence of the current non-convex function is analyzed. It is found that the global convergence of non-convex function is actually based on the optimization of crossover probability and mutation probability to decide the convergence of genetic algorithm, so as to improve the global convergence. A fuzzy controller is designed, which determines the input and output variables and their membership functions, establishes fuzzy rules and anti-fuzzing process to control the crossover rate. The fuzzy control of mutation rate is similar to the crossover rate, but the difference is that the new fuzzy control rule is needed. The experimental results show that the proposed algorithm can effectively optimize the global convergence of non-convex function.
Introduction
Global optimization is widely seen in economic models, finance, network traffic, database, integrated circuit design, image processing, chemical engineering design and control, molecular biology, environmental engineering and so on [1]. Most of these problems belong to the global optimization problem of non-convex functions. Because there are many local optimal solutions that are different from the global optimal solutions, the optimization process is more complex [2]. The genetic algorithm has been widely used in solving the optimal solution in terms of its robustness, parallelism and efficiency [3]. However, there is a problem of premature convergence and poor convergence performance when the genetic algorithm is used to solve the global optimization of non-convex function [4]. Therefore, it is of great theoretical and practical significance to develop a global convergence algorithm which can improve the global convergence performance of the optimized non-convex function.
The current global convergence algorithm for non-convex functions mainly includes the following:
In reference [5], a global optimization algorithm for non-convex function based on Chaos was proposed. The algorithm improves diversity by using chaotic characteristics under the condition of convergence, and introduces chaos into optimization variables to improve global convergence of non-convex function. The algorithm has improved significantly for high-dimensional and multimodal function optimization problems, but for the non-convex function with many local optimal solutions, there is still a problem of premature convergence.
Reference [6] optimized the global convergence of a class of unconstrained optimization methods including the Fletcher-Reeves method. Some properties of Fletcher-Reeves method played an important role in the optimization of convergence. It had the property of decreasing and global convergence for smooth non-convex function. But for practical applications, the unsmooth non-convex function could not improve their global convergence.
In reference [7], the conjugate gradient method was used to optimize the global convergence of non-convex function. The conjugate gradient method was very suitable for large-scale convergence optimization because of its simple algorithm and small storage requirement. However, for the general non-convex function, the conjugate gradient algorithm could not guarantee the global convergence even if the exact line search was used.
In reference [8], an improved FR conjugate gradient method was proposed for unconstrained non-convex function. The conjugate gradient formula was established when the objective function was strict non-convex and under the condition of exact line search. It does not depend on any line search condition, and it can always generate a full descent direction. The global convergence under the condition of standard wolfe inexact line search was obtained. The efficiency of the algorithm was high, but the phenomenon of over convergence was easy to appear.
Based on the Lasalle invariance principle, a global optimization model of non-convex function was established in reference [9]. The global convergence optimization process of a bounded convex function was studied in detail, and the global convergence condition was given. The model had an optimal effect on the global convergence of bounded constrained non-convex function, but the global convergence of non-convex function with unbounded constraints was not optimal.
Firstly, the convergence of genetic algorithm for solving non-convex unconstrained optimization problems is studied. Based on that, the improved fuzzy algorithm is used to optimize its global convergence. The structure of the article is as follows:
Section 1 is the introduction. It analyzes the significance of the research on the global convergence optimization of the non-convex function, and gives the existing problems.
Section 2 is the main body. The improved fuzzy algorithm is used to optimize the global convergence of non-convex function. Firstly, the global optimization of the non-convex function is carried out by genetic algorithm. The global convergence of the non-convex function is analyzed. Aiming at its premature convergence, the convergence is optimized by the improved fuzzy algorithm.
Section 3 is the experiment. The optimization performance of the proposed algorithm for the global convergence of non-convex functions is verified by experiments.
Section 4 is the discussion. The effect of the proposed algorithm on the optimization of the global convergence of non-convex function is discussed.
Section 5 is the conclusion. A summary and prospect of this paper is made.
Material and methods
Description of non-convex function
The general model of the optimization problem is as follows:
Where, X is a closed convex set, and f (x) and g i (x) ≤ 0 (i = 1, 2, ⋯, m) are functions defined on a set containing X. f (x) is the objective function, and g i (x) is the constraint function.
When f (x) and g
i
(x) ≤ 0 (i = 1, 2, ⋯, m) are linear functions, the problem (1) is called linear programming; when there is at least one nonlinear function in f (x) and g
i
(x) ≤ 0 (i = 1, 2, ⋯, m), the problem (1) is called nonlinear programming; when f (x) and g
i
(x) ≤ 0 (i = 1, 2, ⋯, m) are convex functions, the problem (1) is called convex programming; when there is at least one non-convex function in f (x) and g
i
(x) ≤ 0 (i = 1, 2, ⋯, m), the problem (1) is called non-convex programming, and the feasible domain of the current problem (1) is:
At this point, the problem can be simplified to:
Because
So the maximization problem can be converted to solve the minimization problem, so we only discuss the minimization problem of non-convex function.
If there is a point x* ∈ S, there are inequalities for any x ∈ S:
It is established that x* is the global optimal solution of the problem (1), f (x*) is called the global optimal value of f (x) in S, and the set of all global optimal solutions of the problem (1) is recorded as: arg min f (S).
In this section, the genetic algorithm is used to solve the optimal solution of non-convex function. When the genetic algorithm is used to deal with the optimal solution problem of non-convex function, the discrete process is usually involved. It is assumed that the number of evolutional times is expressed by t = 1 ⋯ T. A chromosome with a length of n is represented by a string of symbol X = x1, x2, ⋯, x
n
. x
i
(i = 1, 2, ⋯, n) is used to describe a genetic gene, all of which are called a allele. The basic space of the entire allele genome is as follows:
The population at t evolution times is described by A (t). The corresponding environment is described by B (t). The adaptability of the population to the environment is described by C (t), while under the influence of the natural selection and genetic mechanism d
t
, the new solution set population A (t + 1) is:
According to Darwin’s theory of natural evolution (Groenwold et al. 2015), the species adapted to the environment will be survived, and the species that are not adapted to the environment are eliminated. As a result, the environment plays a vital role in the evolution of the biological population. We cannot simply examine the adaptation of a population to a specific environment, but we should integrate the population into a dynamic environment to study the evolution process of the population. Therefore, it is not reasonable to consider the adaptation ability of the previous model only to the environment corresponding to the current evolutionary times. To this end, a new variable E
B
(t) =〈 C (1), C (2), ⋯, C (t - 1) 〉 is introduced, which reflects the dynamic adaptation of population and environment to historical information before this evolution time, and reproduces the natural evolution process of the population more appropriately. Therefore, the above model is modified to be:
Where, the generation of E
B
(t + 1) reflects the process of natural selection and genetic mechanism in the process of natural evolution of the population:
E B (t + 1) is related to the crossover and the genetic probability.
For finite solution set space, X = {x1, x2, ⋯, x
n
], n = |X|. If A (t) = x
j
(j = 1, 2, ⋯, n), under the influence of natural selection and genetic mechanism d
t
, a new set of solutions is generated. The probability of A (t+ 1) = { x
q
|q = 1, 2, ⋯, n} can be described as:
The above model can be converted into:
The adaptive measure of the population A (t) to environment B (t) is usually described with the real number more than 0.
In the formula, μB,J is used to describe the adaptability of the population A (t) to environment B (t) in the t times of evolution. If the population changes, the ability to adapt to the environment will also change, and the adaptive measure function will be revised accordingly.
At the time of the tth evolution, the population’s adaptability C (t) to the environment can be described as:
When the environment and the population change, natural selection and genetic mechanism d
t
also need to be adapted to make the population having better adaptability. The adjustment of natural selection and genetic mechanism should take account of the current mechanism of the population, the current group’s adaptability C (t) to the environment, the dynamic adaptation of population and environment to historical information E
B
(t), the historical natural selection and genetic mechanism E
d
(t) =〈 d (1), d (2), ⋯, d (t - 1), d (t) 〉 and so on. It is expressed as follows:
In the process of population using the evolutionary environment, the measure of population adaptability can be described as:
The adaptation process of the population to the environment is related to the natural selection and the genetic mechanism E
d
(T). Under the natural selection and the genetic mechanism E
di
(T) =〈 d
i
(1), d
i
(2), ⋯, d
i
(T) 〉, the adaptive measure of the population can be described as:
For the global optimal solution of a non-convex function, the optimal adaptation plan for the minimum cumulative value in the evolutionary phase is the best.
The global convergence of non-convex functions is analyzed by using genetic algorithm.
It is assumed that X
t
={ x1 (t), x2 (t), ⋯, x
N
(t)} is the tth generation of the genetic algorithm, and x
i
(t) is the individual in the tth generation population, i = 1, 2, ⋯, N and N is the population size (that is, the number of individuals in the population). Supposing that F
i
= max{ f (x
i
(t)) |i = 1, 2, ⋯, N} is the optimal fitness for the individual in the population. f* = max(f (x) |x ∈ S) represents the global optimal fitness, S is the individual space and x is an any individual in S. Then the global convergence of the non-convex function can be expressed as:
p{ F t = f*} indicates that the optimal individual in the tth generation population is called the global optimal probability.
From a visual point of view, in order to achieve global convergence, it is necessary to prevent the loss of the optimal solution by preserving the optimal operation.
Because the intelligence optimization of the global convergence of non-convex functions is to optimize the convergence of the genetic algorithm, and the parameters related to algorithm mainly include crossover probability and mutation probability.
The cross probability is the probability for controlling the cross operation (Cartis Gould and Toint 2015). When the probability is too large, the number of chromosomes in the population is updated quickly, and the individuals of the high fitness value will be destroyed quickly. When the probability is too small, the cross operation is rarely carried out, which makes the search stagnant and causes the algorithm to not converge [10–13].
The variation probability is an important factor to increase the diversity of the population. In genetic algorithm based on binary coding, a lower rate of variation is usually sufficient to prevent the gene being kept at any location in the whole population. However, if the probability is too small, it will not produce new individuals, and the probability is too large to make the genetic algorithm as a random searchalgorithm.
In summary, the operation related to the global convergence of non-convex functions is the operation related to the convergence of genetic algorithm, namely genetic operators such as crossover and mutation.
The cross operation is used to produce new individuals in combination, to search effectively in the solution space and to reduce the failure probability of the effective mode. In binary encoding, single point crossover is to determine a cross position at random, and then replace the corresponding substring. Multi-point crossover is to identify multiple cross positions randomly, and then replace the corresponding substrings.
When the fitness value of cross operation is no longer evolutional and does not reach the best, it means the premature convergence of the algorithm. The root of this phenomenon is the deletion of effective genes. If the chromosome string is expressed by H, the mutation rate is P M , and the destruction probability of the chromosome mode is 1 - (1 - P M ) O(H). The mutation operation overcomes this situation to a certain extent, which is beneficial to increase the diversity of the population. Substitution variation is often used in binary or decimal coding, that is, the replacement of the original gene in a certain location with another gene. Perturbed variation is often used in real number coding, which is the disturbance by adding a certain mechanism to the original individual to achieve variation [14, 15].
Through the above analysis, we can see that the global convergence of non-convex functions is essentially a series of operations on genetic chromosome patterns. Crossover operator is used to reorganize patterns and mutation operator is used to carry out pattern mutation. Through these genetic operations, some cross patterns are gradually eliminated and gradually evolved into good models.
The direct cause of premature convergence of non-convex functions is the pattern loss (Curtis Mitchell and Overton 2015). In binary encoding, the expression of pattern loss is gene loss, which means that all individuals in a population have the same character value on a gene location, and the whole population has no complementary character value on this gene position. As a result, the pattern is lost. Through the understanding of the function of the genetic operator above, only the mutation operator is used to restore the lost complementary character values [16]. The mutation operator cannot effectively maintain the gene diversity on the same gene location. Once the pattern loss occurs, the search efficiency of the algorithm will be greatly affected, which will easily lead to premature convergence and stagnation. By using the improved fuzzy algorithm, we intelligently optimize the global convergence of the non-convex function after optimization by genetic algorithm, to overcome premature convergence, and an example is given to prove the effectiveness of the proposed algorithm.
It is known from the Section 2.3 that E
B
(t + 1) is related to the crossover and the genetic probability. When the individual population is moderately consistent or tends to be locally optimal, it increases P
c
and P
m
, and decreases P
c
and P
m
when the population fitness is dispersed, so as to ensure the genetic performance. The analysis of its characteristics helps to determine the input of the fuzzy controller, in which the expressions of P
c
and P
m
are as follows:
Where, fmax is the maximum fitness of the current population; f avg is the average fitness; f is the larger fitness value in the parent populations who are to be crossed, and f is the fitness value of variant string.
It can be seen from the two above mentioned formulas, as the evolution of individuals in the population tend to be consistent, (fmax - f avg ) is small, P c and P m become larger, increase the possibility of crossover and mutation, so as to improve the population diversity and enhance the search ability of the algorithm; the diversity of the population; and when the already strong, (fmax - f avg ) larger, the smaller value of P c and P m is given, making it to find the optimal solution as soon as possible.
The probability of crossover and mutation has a great influence on the convergence speed and convergence performance of genetic algorithm. It is of great significance to further improve their determination methods. In addition, from the above algorithm and other algorithms to determine P c and P m , we can find that there are many vague concepts in their adjustment strategies, for example, if (fmax - f avg ) is smaller, the value of mutation probability P m is larger. These fuzzy concepts are difficult to accurately measure by traditional mathematical methods to better deal with fuzzy information in adjustment strategies, so an improved fuzzy genetic algorithm is proposed.
First, the fuzzy controller is designed.
Fuzzy controller usually adopts double input and single output structure mode (Le 2015). Its block diagram is shown in Fig. 1, which includes five parts: input fuzzification, database, rule base, fuzzy inference and fuzzy processing.
Composition of fuzzy controller.
In the database, the membership function values of all fuzzy subsets of all input and output variables are stored in the database. In the rule base, a set of fuzzy rules for fuzzy reasoning is applied to fuzzy theory.
Then the cross rate is made fuzzy control, and the detailed process is as follows:
Determine the input and output variables
For the improved fuzzy genetic algorithm, the index of population diversity can be simplified. The two input variables of a fuzzy controller are c and d, respectively. Where, c = fmax - f avg representing that the difference between the maximum fitness value fmax and the average fitness value f avg of current generation, also known as the population diversity factor. d is the repeat factor, and the implication is that compared with the previous generation, if the average fitness value of each generation is lower than the previous generation, then d + 1, otherwise the value of d is 1 constantly. Obviously, when d maintains a small value, it shows that the population is in the normal evolutionary process, and the control of crossover rate P c is moderate; if d increases, the evolution ability of population is reduced, then it should avoid unnecessary cross, and P c should be small; P c is taken as output variables directly.
Determine the membership function of the input and output variables
The membership degree represents the degree of fuzzy variables belonging to a fuzzy set, and the membership function represents the characteristics of the corresponding fuzzy sets (HanifKashif and Saqib 2016). At present, the membership function commonly used on the basis of experience are trigonometric and Gauss type. In this section, the membership function of the input and output variables are all Gauss type used for the fuzzy control of P
c
. It is treated as follows: when normalizing the fitness value, the range of input variable c is (0,1), the value of output variable P
c
is (0,1). For the input variable d, the range of the d is (0200) because the algorithm is set at the maximum generation (200 generation) to end. d and P
c
are divided into five language values, namely, very small (VS), small (S), moderate (M), big (B), and very big (VB). For c, three language values are used as follows: S, M, and B. Limited to space, only the membership function of P
c
is taken as an example, as shown in Fig. 2.
The membership function of the cross rate.
Fuzzy rules and fuzzy reasoning methods
Fuzzy control rule of cross rate
In the table, the same row with P
m
is the language value of the repetition factor d, and the same column with P
m
is the language value of the population diversity factor c. The Mamdani reasoning method is chosen in this paper. The fuzzy implication relation is expressed in its Cartesian product,which is:
In the formula, R represents a fuzzy relation, A and B are fuzzy sets on different domains of X and Y, respectively. C is the corresponding fuzzy conclusion.
Anti-fuzzy modeling
The center of gravity method is used in the anti-fuzzy modeling. In this method, the fuzzy membership function curve and the center of gravity surrounded by the abscissa are taken as the final output value of the fuzzy reasoning. The formula is as follows:
Where, v0 represents the final output value of the fuzzy system, μ v (v) represents the degree of membership of the variable v corresponding to the corresponding fuzzy set.
Compared with the method of maximum membership degree, the center of gravity method is simple (Guo. Wang and Shen 2016), with clear reasoning and more smooth output inference control.
Finally, the variation rate is made fuzzy control.
Fuzzy control rule of variation rate
Where, the same row with P m is the language value of the repetition factor d, and the same column with P m is the language value of the population diversity factor c. The output range of P m is (0,0.4).
In this section, two non-convex functions are taken as an example and the algorithms in reference [6, 7] are as a contrast to verify the effectiveness of the proposed algorithm.
The first non-convex function of the study is as follows:
Where, x = (x1, x2)
T
∈ R, the non-convex function has only one extreme value point, and the function form is shown in Fig. 3.
Non-convex function form of Example 1.
In view of the above functions, the global convergence of the proposed algorithm, the algorithm in reference [6, 7] are optimized respectively. Figure 4 describes the convergence curves of the above-mentioned non-convex functions with the changes of the number of iterations under the optimization of the proposed algorithm, the algorithm in reference [6, 7]. The values of the target function after difference number of iterations can be seen from the figure.
Convergence curves of three algorithms for Example 1.
Analysis of Fig. 4 shows that the algorithm can achieve global convergence when it iterates 20 times. The algorithm in reference [6, 7] can achieve global convergence, but the number of iterations is 40 times and 60 times, and the convergence rate is slow. To sum up, the convergence performance of this algorithm is the best.
Example 2 is as follows:
Wherein, x = (x1, x2)
T
∈ R2, the function is a non-convex function, and there are 15 extreme points. The form is as shown in Fig. 5.
The non-convex function form of Example 2.
The convergence curves of the non-convex function by using the three algorithms are described in Fig. 6.
Convergence curves of three algorithms for Example 2.
Analysis of Fig. 6 shows that the algorithm can achieve global convergence when it iterates 20 times. Although the algorithm in reference [6] achieves less convergence times, the convergence rate is not significantly different from the algorithm in this paper, the algorithm is premature convergence without global convergence. Although the algorithm in reference [7] achieves global convergence, the number of iterations is more and the convergence rate is slow. It shows that the performance of the proposed algorithm isoptimal.
As everyone knows, the genetic algorithm is one of the most effective algorithms for solving unconstrained non-convex optimization problem, it has very good numerical results and fast convergence, but the exact linear search or inexact search in solving non-convex minimization problem is not a global convergence. Therefore, an improved fuzzyalgorithm is proposed to optimize the global convergence of non-convex functions.
Two examples of non-convex functions are used, and the algorithms in reference [6, 7] are as the comparison to test the convergence optimization results of the proposed algorithm. In Example 1, there is only one extreme value for the selection of non-convex functions, and the convergence speed is obviously improved after the optimization by using the algorithm in this paper. In Example 2, non-convex functions contain many extreme values, which is prone to local convergence. After optimization by using the proposed algorithm, not only the convergence speed is obviously improved, but also the global convergence is guaranteed, which verifies the effectiveness of the algorithm.
Conclusions
In this paper, an intelligent optimization algorithm for global convergence of non-convex functions based on improved fuzzy algorithm is proposed. For non-convex functions, genetic algorithm is first used to optimize it. Then the fuzzy algorithm is applied to optimize the global convergence of the optimized non-convex function. The experimental results show that the algorithm can improve the convergence speed and ensure the global convergence.
For the proposed intelligent optimization algorithm for global convergence of non-convex function, its efficiency and complexity will be further studied, to find a more easily implemented algorithm.
Footnotes
Acknowledgments
Projects funded by the National Natural Science Foundation (U1504105).
