多目标优化

An adaptive hybrid MOIA based on uniform distribution selection

“参考文献 An adaptive hybrid evolutionary immune multi-objective algorithm based on uniform distribution selection,Information Sciences 512 (2020) 446–470

摘要

• In general, for the iteration process of an evolutionary algorithm (EA), there exists the problem of uneven distribution (不均匀的分布) of individuals in the target space for both multi-objective and single-objective optimization problems. This uneven distribution significantly degrades the population diversity and convergence speed. This paper proposes an adaptive hybrid evolutionary immune algorithm based on a uniform distribution selection mechanism (AU- DHEIA) for solving MOPs efficiently. In AUDHEIA, the individuals in the population are mapped to a hyperplane, which is correlated with the objective space and are clustered to increase the diversity of solutions. To improve the distribution of the solutions, the mapped hyperplane(超平面) is evenly sectioned. With the constantly changing distribution during the iteration, a threshold as a standard for judging the distribution level is adjusted adaptively. When the threshold is not satisfied in the corresponding interval, the distribution enhancement module is activated. Then, the same number of individuals should be selected in each interval. However, sometimes, there are insufficient or no individuals in the interval during the iterative process. To obtain sufficient individuals, the limit optimization variation strategy(极限优化变分策略) of the best individual is adopted. Experiments show that this algorithm can escape from local optima and has a high convergence speed. Moreover, the distribution and convergence of this algorithm are superior to the peer algorithms tested in this paper.

MOIA的优点

• In MOIAs, only a few individuals with better convergence and diversity are selected to propagate, thus producing multiple cloned individuals [7,28,45] . Moreover, each clone evolves better individuals through hypermutation. In this manner, excellent individuals have more evolutionary opportunities. Therefore, MOIAs have a competitive advantage in terms of population diversity and convergence speed compared with other MOEAs [36] .

本文提出MOIA的优点--在复杂问题中具有更好的分布

• However, most MOIAs use a single hypermutation strategy [14,29,36] , which can lead to unsatisfactory results when dealing with complex MOPs [14] . This may be because it is rather difficult to balance the proximity and diversity. This conforms to the no-free-lunch theorem [2] . To tackle this problem, Lin et al. [30] proposed a novel hybrid evolutionary framework for MOIAs (HEIA). This algorithm employs multiple evolutionary strategies to combine their advantages and overcome the shortcomings of any single strategy. However, [36] the purpose of many multi-objective optimization algorithms is to find a certain number of Pareto optimal solutions uniformly distributed along the PF, to better represent the entire PF [2,14,29,46] . Therefore, it is necessary and meaningful to find a solution that can converge better and be distributed more widely and evenly to the PF front for the next generation to increase the diversity of the population.
• In fact, there still exist two issues to be addressed for all MOEAs during the iteration process, and HEIA is no exception, in this regard: 1) how to select individuals in the population to in- crease the distribution of individuals during the iteration procedure [44] ; in general, the individuals are severely unevenly distributed ., i.e., there may be many individuals residing at some areas of the objective space, while there are few or even no individuals in other areas; and 2) supplement deficiency when there are no sufficient individuals on the Pareto front during the solving process, which is a challenging problem. 实际上，在迭代过程中，所有MOEA仍然存在两个要解决的问题，在这方面，HEIA也不例外：1）如何在总体中选择个体以在迭代过程中增加个体的分布[44] ]；通常，个体分布严重不均匀，即可能有很多个体在在目标空间的某些区域，而在其他区域则很少甚至没有个体；2）当求解过程中在帕累托前沿没有足够的个体时，补充不足，这是一个具有挑战性的问题。

关于解的分布性的分析个人觉得十分的好！

论文写作时，加上自己的见解和评论很能提升整篇论文的档次

• For the first question, the objective of multi-objective optimization is to make the solution converge uniformly as widely as possible at the Pareto front [10] . This is because an uneven individual distribution can lead to poor population diver- sity in the iteration procedure. Therefore, it is easy for the solutions to fall into a local optimum. Some parts of the Pareto front may be empty and the convergence speed decelerates. To overcome these issues, the sharing mechanism proposed by Goldberg and Richardson [13] can be used. This approach to producing new individuals considers the similarity levels among individuals in the population. However, it requires extensive calculation resources. Zhu and Chen [47] adopted the population distribution entropy to portray the diversity and distribution of a population.(Zhu和Chen[47]采用种群分布熵来描述种群的多样性和分布) However, this method lacks the characterization of relations between individuals within groups. Therefore, it is not easy to regulate the diversity and dis- tribution during the evolutionary process. Corne et al. [3,6] presented grid technology in which the individuals with high packing density in the grid are deleted. Nonetheless, the poles cannot be deleted.(然而，两极不能被删除) Knowles and Corne [24] suggested an adaptive grid technique. This algorithm adaptively adjusts the boundary according to the current individual distribution in every evolution. Morse [33] proposed a clustering analysis method to maintain the diversity of the population. Han et al. [16] proposed a method based on the population spacing and population distribution entropy. However, the above methods just delete the individuals with small crowding distances. They cannot resolve the problem of no or insufficient individuals in some regions during the iterations. In addition, MOEA/D can obtain a set of well-distributed solutions by its diversity maintenance among subproblems, which is implemented by a uniform distribution of weight vectors. In MOEA/D, the num- ber of weight vectors is fixed, and only one individual is chosen in each weight vector interval. For simple MOPs, MOEA/D exhibits good performance. However, the results are not satisfactory for complex MOPs [21] . (哈哈哈23333333333333333)

本文贡献

• Based on the above discussions, this paper presents an adaptive hybrid evolutionary artificial immune algorithm based on a uniform distribution mechanism (AUDHEIA). In this algorithm, HEIA is used for its ability to solve complex MOPs [30] . However, the problem of the individuals being unevenly distributed during the evolution process significantly affects the population diversity and convergence speed. To solve this problem, the hyperplane is evenly divided, and an equal number of individuals are selected from each interval. However, most Pareto fronts are curves or surfaces. How dimension reduction is performed is very important. For this purpose, motivated by literature [38] , the individuals are mapped to a hyperplane that is correlated with the objective space, and they are clustered to increase the diversity of solutions. The results show that this can achieve faster convergence toward the Pareto-optimal front without loss in diversity. However, how to choose individuals from each interval remains a challenging question, and there is no experience to be found in the literature. An indicator is required to measure the distribution of individuals in each interval, and a threshold to judge the distribution standard is also necessary. Because the distribution of individuals changes unceasingly during the iterations, the threshold needs to be adjusted adaptively in this paper. When clustering individuals, if the distribution levels in the corresponding intervals do not meet the threshold, the distribution enhancement module is activated. When the threshold is satisfied, a certain number of superior individuals are selected from each cluster. Then the distribution of individuals can be improved.
• However, in the selection process, there are sometimes insufficient individuals or even no individuals in some intervals during the iteration process. Regarding this problem, the individuals with poor diversity values are deleted in most of the literature, and this issue has only rarely been studied. To solve this problem, a limit optimization variation strategy of the best individual is utilized in this paper to produce new antibodies. To verify the performance of AUDHEIA, the inverted generation distance (IGD) function and spacing (SP) function are selected to test diversity and convergence. The experimental results show that our proposed algorithm’s inverted generational distance (IGD) and spacing (SP) values are higher than those of other strategies. Therefore, the modified algorithm has better population diversity and distribution, and it converges faster than peer algorithms.
• The main contributions of this paper are summarized as follows:

1. A distribution measurement indicator is proposed to measure the distribution of individuals in a population. The individuals are mapped to a hyperplane that corresponds to the objective space, and they are clustered on this hyperplane. The hyperplane is equally divided, and the number of segmentations(分段的数目) is adjusted adaptively in the iteration process. When the number of species in the interval is less than the threshold, the distribution enhancement module is activated.(分块增强模式被激活)
2. A distribution enhancement module is introduced to increase the distribution of the individuals. In the population se- lection process, individuals with the same number are selected in every interval. Furthermore, the choice mechanism is offered.
3. A limit optimization variation strategy of the best individual is taken to generate local solutions. Sometimes the indi- viduals are insufficient or not present at all in the iteration process, so two variation strategies are used to supplement the insufficient individuals. The first strategy can effectively im prove the local search ability. The other can prevent the algorithm from falling into local optima, thus improving the search speed.
4. The threshold for judging the distribution level of individuals is adjusted adaptively. During the iterations, the dis- tribution of individuals changes unceasingly. Therefore, this paper designs an adaptive threshold adjustment strategy based on the evolutionary state of the population and the distribution of individuals.

Immunology terms in MOIAs

• An artificial immune system is mainly based on the information processing mechanism of a biological immune system [48] . It is developed to solve complex problems. To describe the algorithm better, several common immunological terms for an artificial immune system are described as follows: Definition 5 (Antigen) . An antigen refers to the problem and constraints to be solved. It is defined as the objective func- tion(s) in an MOP. Definition 6 (Antibody) . An antibody refers to a candidate solution of the problem. It is described as a candidate solution in the decision space for an MOP. Definition 7 (Affinity) . An affinity refers to the adaptive measure of candidate solutions or problems that correspond to the value(s) of the objective function(s).
• Yoo and Hajela [40] introduced the first related work on MOIA, and the concept of antibody and antigen affinity was introduced. To imitate the biological immune system, the clone operator is usually chosen by MOIAs to select and clone antibodies with high affinities. Then, the decision variables are altered by the hypermutation. In the process, the aim is to evolve solutions toward having better and better affinities. Since then, many other MOIAs have been designed, most of which have excellent performance. According to the characteristics of the immune system, MOIAs can be divided into three categories: 1) clonal selection methods; 2) immune network methods; and 3) hybrid methods (i.e., combinations of immune systems and other heuristic methods).
• Among them, Coello and Cortés [4] proposed a clonal selection based multi-objective immune algorithm (MISA). In this method, only antibodies with high affinity can multiply and produce multiple clonal antibodies, and the adaptive grid method is used to maintain the diversity of the population. In [5] , the performance of MISA is further improved [22] . The immune dominant cloning multi-objective algorithm was introduced. The method uses antibody anti-affinity to re- flect the similarity between antibodies. This will guide cloning operations to select the most efficient search area (i.e., the least crowded area). In addition, Hu [17] proposed a new MOIA using a multimodal model. Six affinity assignment methods were used in this method, i.e., cloning, hypermutation and immunosuppression. Immunosuppression refers to the removal of similar antibodies in variable and target spaces.
• In addition, an artificial immune system based on vectors [11] has been extended by the artificial immune network algorithm (opt-ainet) to solve MOPs. In this case, two cycles of evolution are carried out. The purpose of internal circulation is to utilize the search space, while the purpose of external circulation is to avoid redundancy caused by similar antibodies. In [12] , a new weight-based MOIA was proposed. This method uses a random weighted sum method as a fitness allocation scheme and combines it with a new truncation algorithm to eliminate similar individuals. The results show that the method has low computational complexity and can obtain Pareto-optimal solutions with good distributions.
• However, most of the above MOIAs only use simple hypermutation operators to evolve antibodies [12,36,42,43] . The use of simple evolutionary methods in MOIAs may lead to monotonous search patterns, which makes existing MOIAs unable to deal with complex MOPs (for example, the UF test problem [32] ). In fact, the hybrid mutation method has been studied in immune algorithms [19,20,27,39] , and good results have been achieved. For example, Sindhya et al. [38] introduced a hybrid framework for MOEAs, which uses local search modules to speed up convergence. Tang and Wang [39] proposed a new hybrid MOEA that combines the concepts of individual optimum and global optimum from PSO. In addition, Lin et al. [30] proposed a novel hybrid evolutionary framework for MOIAs (HEIA), which selects multiple high-affinity antibodies from antibodies for cloning and then performs SBX and crossover operations. This hybrid evolutionary strategy can overcome the limitations of using a single strategy and has better results in solving different types of MOP problems. Even though HEIA has advantages in terms of convergence speed and population diversity [30] , the individuals in the population exhibit the uneven distribution problem during the iteration process. This problem occurs in many MOPs

HEIA虽然是为解决复杂的多目标优化问题提出的，但是仍然存在解的分布不均匀的情况

• For the ZDT test problems, Fig. 1 demonstrates the individual evolution process at different stages. Fig. 1 (a) and (b) present HEIA’s nondominant solutions to the ZDT1 problem. Fig. 1 (a) is the nondominant solution of the objective functions f 1 ( x ) and f 2 ( x ) in the first to tenth iterations of HEIA. Because of the initial stage of the algorithm, the population is randomly initialized. Therefore, as seen from Fig. 1 (a), individuals in the population are evenly distributed in the target space at the beginning of the iteration. However, with the continuous evolution of individuals in the population, if the distribution of individuals in the population is not taken into account when selecting the elite solution, it is likely that some individuals will be concentrated in some regions and that some regions will have very few or no individuals. This will seriously affect the diversity of the population, which may cause a Pareto solution to fall into a local optimum and affect the convergence of the algorithm. Fig. 1 (b) gives the nondominated solutions of the objective functions f 1 ( x ) and f 2 ( x ) of HEIA in the 1st to 20th iterations. It can be seen that in the 10th to 20th iterations, due to the uneven distribution of individuals in the population and the insufficient diversity of the population, the individuals in the population spend a long time searching in the target space with dense individual aggregation. It was not until the 20th iteration that a very few individuals began to look for other regions. In this manner, the convergence rate of Pareto solution is greatly reduced, and the difficulty of extending and evenly distributing Pareto solution to PF front is also increased. This phenomenon exists in almost all of the test problems. Due to the page limitation, they are not introduced here. However, most MOEAs just delete the individuals with smaller crowding distances to increase the diversity of the population. When the Pareto front is continuous, how to solve the empty or insufficient problem in some regions during iterations is a particularly challenging problem. In addition, there are few studies concerning this aspect.

• To address this problem, a hybrid evolutionary artificial immune algorithm with adaptive uniform distribution is used to solve the multi-objective optimization problem. At the same time, to compare with HEIA, the nondominant solutions for the ZDT1 problem are also given in Fig. 1 (c) and (d). As seen from Fig. 1 (c), individuals in the population have been relatively uniformly distributed in the target space. In this manner, the diversity and distribution of the population have been greatly improved. This reduces the possibility of a Pareto solution falling into a local optimum. Fig. 1 (d) shows the nondominated solutions of the objective functions f 1 ( x ) and f 2 ( x ) of AUDHEIA in the 1th to 20th iterations. It can be seen that,because the individual distribution in the previous population is more uniform, when very few better individuals find the Pareto front, the rest of the individuals can be more quickly and evenly distributed on the Pareto front. Therefore, in the process of iteration, it is necessary to increase the uniformity of the individual distribution in the population, to improve the diversity of the population. To summarize, it is necessary to ensure that individuals are distributed uniformly and increase the population diversity when individuals in the population are unevenly distributed during the iteration process.