多目标优化

A novel MOIA with a decomposition-based clonal selection

“参考文献 A novel multi-objective immune algorithm with a decomposition-based clonal selection,Applied Soft Computing Journal 81 (2019) 105490

摘要

• In recent years, a number of multi-objective immune algorithms (MOIAs) have been proposed as inspired by the information processing in biologic immune system. Since most MOIAs encourage to search around some boundary and less-crowded areas using the clonal selection principle, they have been validated to show the effectiveness on tackling various kinds of multi-objective optimization problems (MOPs). The crowding distance metric is often used in MOIAs as a diversity metric to reflect the status of population’s diversity, which is employed to clone less-crowded individuals for evolution. However, this kind of cloning may encounter some difficulties when tackling some complicated MOPs (e.g., the UF problems with variable linkages). To alleviate the above difficulties, a novel MOIA with a decomposition-based clonal selection strategy (MOIA-DCSS) is proposed in this paper. Each individual is associated to one subproblem using the decomposition approach and then the performance enhancement on each subproblem can be easily quantified. Then, a novel decompositionbased clonal selection strategy is designed to clone the solutions with the larger improvements for the subproblems, which encourages to search around these subproblems. Moreover, differential evolution is employed in MOIA-DCSS to strength the exploration ability and also to improve the population’s diversity. To evaluate the performance of MOIA-DCSS, twenty-eight test problems are used with the complicated Pareto-optimal sets and fronts. The experimental results validate the superiority of MOIADCSS over four state-of-the-art multi-objective algorithms (i.e., NSLS, MOEA/D-M2M, MOEA/D-DRA and MOEA/DD) and three competitive MOIAs (i.e., NNIA, HEIA, and AIMA).

MOEA简介

• In the last decades, there are a number of multi-objective evolutionary algorithms (MOEAs) proposed to tackle various kinds of MOPs. NSGA-II [3], SPEA2 [4], and MOEA/D [5] are widely acknowledged as the three well-known state-of-the-art MOEAs. NSGA-II [3] was designed with a fast nondominated sorting approach to ensure the convergence first and then using the crowding-distance metrics to guarantee the population’s diversity. SPEA2 [4] was proposed with the aim to balance convergence and diversity by using a fine-grained fitness assignment strategy. MOEA/D [5] was presented to decompose the target MOP into a set of subproblems and then to optimize them simultaneously on a cooperative manner. These well-known MOEAs have inspired many research studies [6–10], such as a new definition of dominance relation [11] and an integrated weight assignment strategy [12] for NSGA-II, a shift-based density estimation strategy [13] and an efficient reference direction-based density estimator [14] for SPEA2, an indicator-based method [15] and an acute angle based approach [16] for MOEA/D. Some recent research studies have extended MOEAs to solve many-objective optimization problems [17–20]. For more detailed review of MOEAs, please refer to [21,22].

MOIA历史

• On the other hand, a number of multi-objective immune algorithms (MOIAs) have been proposed as inspired by the clonal selection principle in biologic immune system, showing the superiority over some state-of-the-art MOEAs [11–16]. Only a small ratio of individuals showing good convergence and diversity capabilities are selected for clonal proliferation and then a number of clones are generated in MOIAs. Then, each clone is evolved by hyper-mutation, expecting to produce the superior offspring. This way, the individuals with high potentiality will have more clones to be evolved, aiming to speed up convergence or extend diversity. The first real-coded MOIA may retrospect to a nondominated neighbor-based immune algorithm (NNIA) [23] based on the clonal selection principle, which was experimentally validated to show some advantages over NSGA-II and SPEA2. After that, a larger number of MOIAs were also designed based on the clonal selection principle, such as HEIA [24], AIMA [25], theta- MCSA [26], and CMIGA [27]. Most of them have demonstrated the superiorities on solving the simple MOPs (like ZDT [28] and DTLZ [29]).

但是在解决复杂的多目标问题上表现得不好

• However, the experiments in [24,25] showed that most MOIAs were difficult to handle the UF test problems [30] with the complicated PF or PS. This is mainly because most MOIAs implement the clonal selection operators only on nondominated individual according to their crowding distance values [23], which may cause the difficulties on these complicated MOPs [30]. This observation motivates us to study whether a novel clonal selection strategy can be implemented in MOIAs to alleviate the above problem. Therefore, in this paper, we propose a novel MOIA with a decomposition-based clonal selection strategy, called MOIADCSS. Instead of using the crowding distance metric in clonal selection, the proposed MOIA-DCSS exploits the decomposition approach to realize the clonal selection approach, which has some advantages in selecting the potential solutions for cloning and evolution. By this way, our algorithm is more able tokling maintain the balance of convergd MOPs. Morence and diversity, especially on tac some complicateeover, following the design of some recent MOIAs [24,25], differential evolution is also used in MOIADCSS to improve the exploration ability and the population’s diversity. To have a comprehensive evaluation on the performance of MOIA-DCSS, three different test suites are used, i.e., the walking fish group (WFG) [31], the UF [30], and the F [32] test suites. When compared to four state-of-the-art multi-objective algorithms (i.e., NSLS [33], MOEA/D-M2M [34], MOEA/D-DRA [30], and MOEA/DD [35]) and three competitive MOIAs (i.e., NNIA [23], HEIA [24], and AIMA [25]), the performance of MOIA-DCSS is superior when considering the convergence speed and the population’s diversity. Moreover, the effectiveness of our clonal selection strategy is also experimentally studied to confirm its superiority.

The related work of MOIAs

• The concept of antibody–antigen affinity in biologic immune system was firstly used as a fitness assignment mechanism for a standard genetic algorithm [36], which may be a first attempt to present an MOIA. Since then, a large number of MOIAs were designed in order to further enhance the performance. Based on the features inspired from the biologic immune system, most MOIAs can be categorized into three main kinds. The first class of MOIAs simulates the clonal selection principle [37] and clones the superior individuals with the highest affinity values, e.g., NNIA [24] and MAM-MOIA [38]. The second type of MOIAs maintains the population’s diversity as inspired from the immune network theory, such as VAIS [39] and WBMOAIS [40]. The last category of MOIAs embeds other heuristic operators into MOIAs, like MOGAIS [41] and MOBAIS [42] which replaces the mutation and cloning operators with a probabilistic model, i.e., Gaussian network and Bayesian network, respectively.
• In recent years, some competitive MOIAs have been proposed with more promising performance. For example, CMIGA [43] based on the model of biological immune system was presented to solve the MOPs with multimodel nonlinear constraints; IMADE [44] was proposed to combine a newly designed DE operator and simulated binary crossover (SBX); mcDMOA [45] was designed with an adaptive change reaction strategy to track the changing PFs; IDSMOA [46] was introduced by using various immune operators in two co-evolutionary populations. To combine the advantages of different evolutionary strategies, a novel hybrid evolutionary framework was designed for MOIAs, which implements a hybrid evolutionary MOIA called HEIA [24]. The cloned individuals in HEIA are separated into several sub-populations and then independently evolved by different evolutionary strategies (e.g., SBX and DE). More recently, AIMA [25] was proposed by dividing the process of evolution into three main stages (the early, middle and last stages). Three different DE strategies showing distinct search capabilities are sequentially used on these stages, as controlled by an adaptive selection strategy. Besides that, MOIAs were also studied to solve some constrained MOPs in [47–49], and extended to solve some real-world applications, such as [50,51] for the traffic environmental problems, [52,53] for job-shop scheduling problem, and [54,55] for the dynamic optimization problem.

Clonal selection in MOIAs

• Most of MOIAs [24–27,41,44–46,56] were designed based on the clonal selection principle. In order to show the running of clonal selection in MOIAs, the population’s evolution in one generation t of MOIAs is illustrated in Fig. 1. At first, the population Pt is evolved by the meta-heuristic operators (e.g., SBX and polynomial-based mutation [57]) to produce the offspring population Dt . Then, the populations Pt and Dt are combined to update external archive, as marked by Et . At last, the clonal selection is further run to select some promising individuals (At ) for cloning a new population (Pt+1) for the next generation, as shown in the procedures of selection and cloning from Fig. 1.

However, when solving some complicated MOPs (e.g., the UF test problems [30] and F test problems [32]), this kind of clonal selection operator based on the crowding distance metric is not so effective due to the complicated PSs and PFs. Therefore, this paper presents a novel MOIA with a clonal selection strategy based on decomposition approach (MOIA-DCSS), which is expected to have a stronger exploration capability on tackling these complicated MOPs.