1.

INTRODUCTION

Many problems, such as engineering design, combinatorial optimization, decision-making, optimal path selection, etc., can be reduced to function optimization problems after mathematical modelling¹. Finally, the optimal results can be solved under certain constraints, which can reduce manpower expenditure. Therefore, it is meaningful to discuss the problem of function optimization in theory and application.

Genetic Algorithm (GA) is first proposed by John Holland in the 1970s in the United States². Genetic algorithm comes from the natural evolution process of nature. The algorithm solves the optimal solution through mathematical coding, and uses the selection, crossover and mutation process to search for the optimal result. Because the optimization is independent of gradients and has strong robustness and global search ability, combinatorial optimization problems can be quickly and accurately solved. GA had been widely used in combinatorial optimization, machine learning, signal processing, adaptive control and other fields³.

However, many of its deficiencies and defects have also been exposed, such as poor local search ability, slow convergence speed and it is easy to fall into local optima⁴. With the expansion of the dimensions of the problem to be optimized, these deficiencies are becoming more and more prominent, and the most prominent problem is the problem of premature convergence. All individuals in the group tend to the same state and stop evolving, the biodiversity is lost, and it is meaningless to iterate again.

A multi-population genetic algorithm (MPGA) can be used to replace the conventional standard genetic algorithm. Multi-population genetic algorithm performs among multiple populations by introducing different optimization parameters, and the optimization results are derived from the final elite population. Compared with the traditional GA, the improved MPGA has better adaptability and result accuracy for solving the multimodal function optimization problem with high difficulty coefficient⁵.

This paper proposes to use the new algorithm to solve the overall optimization problem of multimodal nonlinear functions, and changes the relevant variables to observe the stability of the algorithm and compared it with the traditional genetic algorithm. Simulation results show that the MPGA has better optimization ability and higher calculation accuracy for solving local optimal problems of nonlinear multimodal functions.

2.

DISADVANTAGES OF GENETIC ALGORITHMS

Genetic algorithm is a random search algorithm. The first step is to randomly generate a population, then searches for the optimal solution of the optimization problem through genetic operations to generate a new population. After gradual evolution, the GA converges to the optimization accurately with a high probability, so as to obtain the optimal solution or sub-optimal solution of the optimization problem⁶. The GA structure is shown in Figure 1.

Figure 1.

GA flow chart.

Premature convergence problem is one of the biggest problems of GA⁷. All individuals in the group tend to the same state and stop evolving, the biodiversity is lost, and it is meaningless to iterate again.

The occurrence of premature convergence is mainly related to the following aspects⁸:

3.

MULTI-POPULATION GENETIC ALGORITHM

3.1

Algorithm improvement

Based on the original standard GA, MPGA mainly introduces the following concepts⁹:

• • Breaking through the framework of the standard genetic algorithm that only relies on a single population for genetic evolution, which can be performed among multiple populations by introducing different optimization parameters.

• • The various populations are connected through the migration operator. The optimal solution is obtained through the co-evolution of multiple populations.

• • The optimal individuals in each evolutionary generation of each group are preserved and selected to decide whether to achieve optimal convergence.

The structural flow chart of the MPGA is shown in Figure 2.

Figure 2.

Schematic diagram of the structure of MPGA.

In this paper, binary coding is used for individuals, which has high stability and large population diversity. The decision variables x₁ and x₂ are represented by binary strings. For example, the domain of x_j is [a_j, b_j], and the accuracy requirement is ten thousandths, which requires the domain of x_j to be divided at least(b_j, − a_j) × 10⁵ spaces, and the binary string length required by the set variable x_j is m_j, which should satisfy:

4.

EXPERIMENTAL DESIGN AND RESULTS

This paper selected the following typical nonlinear multimodal functions for research and analysis

We set a small area for calculation. The value range of x in f(x, y) is [-2,2], and the value range of y is [-2,2]. Through the initial derivation, it is concluded that the stagnation point range is not within the definition domain, and the optimal value of the function should be obtained at the boundary. Near (0,0), the function will oscillate, and it is easy to generate local extrema.

In order to test and evaluate the performance of MPGA for multimodal function optimization, this paper defines the optimal solution value, iterative stability, and optimal time as the algorithm evaluation indicators.

This paper compares the standard GA and the improved MPGA. Table 1 shows the initial setting of the genetic algorithm and the influence on the results after considering the changes of the crossover probability and mutation probability.

Table 1.

Initial parameters and variables of GA.

The variation of the optimal solution of the GA with the evolution number is shown in Figure 3.

Figure 3.

Optimal solution change.

Table 2 shows the parameter settings of the improved multi-population genetic algorithm. Since the immigration operator between multiple populations can communicate with each population, the crossover probability and mutation probability will take a random probability between each population.

Table 2.

Improved initial parameters of MPGA.

Table 3 shows the calculation results. The standard genetic algorithm was calculated 7 times. Due to the existence of crossover and mutation probability, the results are different each time. However, the improved genetic algorithm can better obtain a stable optimal value.

Table 3.

GA and MPGA algorithm optimization results.

The variation of the optimal solution of the GA and the MPGA with the evolution number is shown in Figure 4.

Figure 4.

Evolution process diagram.

The optimization results obtained each time are different by using genetic algorithm, (as shown in Table 3 above), and even the signs of x and y are opposite. It could be seen that the standard genetic algorithm is very unstable, and sometimes it is still not stable when it is close to 500 generations, the convergence speed is slow, and the convergence accuracy is poor.

Using the improved multi-population genetic algorithm, the optimization results obtained each time are completely consistent, the stability is good, the genetic algebra is within 30 generations, the convergence speed is fast, and the convergence accuracy is high, which is suitable for the optimization of such complex functions.

5.

CONCLUSION

The improved MPGA expands the structure of the standard GA, and introduces multiple populations to search the solution space at the same time, and greatly reduces the inappropriate genetic control parameters. The influence of the settings on the optimization results has a significant effect on suppressing the occurrence of immature convergence. The examples show that the multi-population genetic algorithm has better optimization ability and higher calculation accuracy and stability for solving the local optimal problem of nonlinear multimodal functions.