不完全免疫算法简介HEIA--AIS学习笔记2

多目标优化

A Hybrid AIS for MOP

“参考文献 A Hybrid Evolutionary Immune Algorithm for Multiobjective Optimization Problems, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 20, NO. 5, OCTOBER 2016

优点

• Compared with MOEAs, multiobjective immune algorithms (MOIAs) have shown some advantages related to an improved convergence speed and maintaining a better population diversity [23]. Specifically, MOIAs are characterized by the clonal selection principle, in which only a small proportion of individuals with better convergence and diversity are proliferated to produce multiple clones [23]–[25]. Then, each clone is evolved by hypermutation to search for the better individuals. In this way, superior individuals have more opportunities for evolving, which helps to speed up convergence.

缺点

However, most MOIAs only adopt a single hypermutation operator to evolve each clone [23]–[25], which may induce some difficulties in solving complicated MOPs (e.g., complicated unconstrained MOPs such as the unconstrained functions (UFs) in [26]). This may be due to the fact that a single hypermutation operator will have difficulties to achieve a proper balance between proximity and diversity. This conforms to the no-free-lunch theorem that states that a single search strategy cannot have the best performance in terms of both proximity and diversity [27]. This motivated us to study whether multiple search strategies can be combined in MOIAs so that their search patterns can complement each other.

改进

Therefore, in this paper, we propose a novel hybrid evolutionary framework for MOIAs (HEIA), in which the cooperation of multiple evolutionary strategies allows us to combine their advantages and overcome the inherent limitations of adopting a single strategy. Our proposed approach is more capable of maintaining the tradeoff between proximity and diversity, and, consequently, has better performance than other multiobjective optimization algorithms when dealing with different types of MOPs. To validate the effectiveness of our hybrid framework, an implementation example is proposed, which considers simulated binary crossover (SBX) [28] and differential evolution (DE) [29] followed by polynomial-based mutation as two evolutionary strategies. The main features of our proposed HEIA are the following.

1. The cloned population is randomly divided into several subpopulations, which will be subject to different evolutionary strategies, separately. This hybrid framework with multiple evolutionary strategies is different from the traditional MOIAs that only apply one hypermutation operator on the cloned population. The cooperation of multiple evolutionary strategies in our scheme can overcome the inherent limitations of using a single strategy, and enhances the exploratory capability and robustness of our proposed approach, thus allowing it to handle a wide variety of MOPs.
2. Two evolutionary strategies are included in HEIA. The first one adopts SBX followed by polynomial-based mutation. This strategy is found to perform well on simple MOPs with independent decision variables. The second strategy applies DE crossover and polynomialbased mutation, and is especially effective for complicated problems with variable linkages (i.e., parameter dependencies) [29]. These two evolutionary strategies can complement each other by exploiting their advantages and it is experimentally shown that they perform better than the separate use of any of them.
3. A fine-grained selection mechanism and a novel elitist sharing strategy are adopted in HEIA. After the hybridized evolution from item 2) shown above is undertaken, the subpopulations are combined with an elitist archive and a fine-grained selection mechanism proposed in our previous work [25], with the aim of preserving the nondominated individuals found in the elitist archive. An elitist sharing strategy is then operated by selecting some less-crowded individuals (measured by the crowding distance metric [2]) from the elitist archive. Such individuals are cloned and divided into different subpopulations for independent evolution in the next generation. In this way, the search experience of one subpopulation can be shared by another subpopulation.

术语

As MOIAs are designed based on the principles and processes of biological immune systems [34], [35], some immunological terms used in MOIAs are introduced next in order to better understand them. Definition 5 (Antigen抗原): An antigen refers to the problem and constraints to be solved, e.g., the minimization problem F(x) in (1). 需要解决的问题本身 Definition 6 (Antibody抗体): An antibody refers to a candidate solution of the target problem, e.g., the decision variable x in (1). 解-决策变量 Definition 7 (Affinity亲和力): Affinity usually represents the objective function values or the fitness measurement of the problem related to a candidate solution. 目标函数值

To mimic the clonal selection principle, MOIAs usually apply the cloning operator, which generates copies of the antibodies that are selected due to their better affinities. After that, hypermutation (which refers to applying a mutation operator at a high rate), is applied on each clone to alter the decision variables. This process is aimed at searching the antibodies with better affinities and achieving affinity maturation (实现亲和力成熟) (i.e., individuals that represent better solutions). The set of antibodies is called an antibody population. Using the definition of Pareto dominance, an antibody is called a nondominated antibody when it is not dominated by any other antibodies in the population.

Related Work on MOIAs

The first MOIA was reported in [36], and incorporated the concept of antibody-antigen affinity(抗原抗体亲和力) into a standard genetic algorithm to modify its fitness assignment mechanism. Afterward, many other MOIAs were designed, most of which have a superior performance. Based on the special features inspired by the immune system, MOIAs can be classified into three categories:1) clonal selection approaches; 2) immune network approaches; and 3) hybrid approaches (i.e., combinations of an immune system with another heuristic).

clonal selection approaches

A multiobjective immune system algorithm (MISA) based on clonal selection was proposed in [37]. In this approach, only the antibodies with high affinities are proliferated to generate multiple clones, and an adaptive grid is used to maintain diversity. The performance of MISA was further improved in [38]–[40]. An immune dominance clonal multiobjective algorithm was introduced in [41]. This approach adopts the antibody–antibody affinity to reflect the similarity among antibodies. This guides the cloning operator to select an effective search region (i.e., the least-crowded region).(这将引导克隆操作符选择一个有效的搜索区域即，最不拥挤的地区) This approach was further extended to solve dynamic MOPs [42] and it was improved in [24]. A novel MOIA using a multipleaffinity model was presented in [43]. This approach adopts six measures for affinity assignment 赋值, where cloning, hypermutation, and immune suppression were applied according to such affinity measurements. In this case, immune suppression refers to removing similar antibodies in both variable and objective space.(在这种情况下，免疫抑制是指在变量和目标空间中去除相似的抗体。)

immune network approaches

On the immune network approach, a vector artificial immune system [44], [45] was extended from the artificial immune network algorithm (opt-aiNet) [46] to solve MOPs. In this case, two evolutionary loops are performed. The inner loop is aimed at exploiting the search space, while the outer one is aimed to avoid the redundancy produced by similar antibodies (suppression is used to avoid such redundancy). (内部循环的目的是利用(局部搜索)搜索空间，而外部循环的目的是避免类似抗体产生的冗余(使用抑制来避免这种冗余)) A novel weight-based MOIA was presented in [47]. This approach adopts a random-weighted sum method as its fitness assignment scheme combined with a new truncation algorithm that eliminates similar individuals.(该方法采用随机加权和法作为适应度分配方案，结合新的截断算法消除相似个体。) Its authors claimed that this approach has a low computational complexity and is able to obtain a well-distributed PFknown.

hybrid approaches

Regarding hybrid approaches, one called immune-inspired Pareto archived evolution strategy was introduced in [48]. In this approach, two hypermutation operators are combined to solve an MOP extracted from ab initio protein structure prediction problems. An evolutionary artificial immune algorithm designed for solving MOPs was reported in [49]. This approach combines the global search capabilities of EAs with the learning capabilities of artificial immune systems. A novel immunity-based hybrid EA was proposed in [50] to tackle both unconstrained and constrained MOPs. This approach uses a sorting scheme featuring uniform crossover, multipoint mutation, and crowding distance sorting, to efficiently approximate PFtrue.(该方法采用均匀交叉、多点突变和拥挤距离排序的排序方案，有效地逼近PFtrue。)

recent years

In recent years, several new MOIAs with competitive performance have been proposed. For example, a dynamic MOIA was introduced in [51] for constrained nonlinear MOPs and it was extended for its use in greenhouse control [52]. A hybrid immune multiobjective algorithm was proposed in [53]. This approach uses a hybrid operator combining Gaussian and polynomial-based mutation. It was further improved by using an adaptive mutation operator [25] and a novel adaptive DE operator [54] with a fine-grained selection mechanism. An NICA [23] was reported to solve complex MOPs. This approach adopts a full cloning scheme and a novel antibody population updating operation after clonal selection.

混合增强克隆算法和其他混合增强算法的不同

However, in the above-mentioned MOIAs, most of them only adopt a simple hypermutation operator to evolve the antibodies, e.g., [23], [47], [51], and [52] only use a hypermutation operator, while [24], [25], [43], and [53] utilize a combination of one crossover operator with a mutation operator. The use of simple evolutionary operators in MOIAs may lead to a monotonous search pattern(单调的搜索模式), which makes the existing MOIAs incapable of tackling complicated MOPs (e.g., the UF test problems [26]). Actually, hybrid mutation approaches have been investigated in immune algorithms [48], [53], [55], [56], with promising results.Working in this same direction, this paper presents a general HEIA, which adopts different search strategies to complement each other, thus providing superior performance.The cooperation of hybrid evolutionary strategies can overcome the inherent limitations of using a single strategy and is expected to be better and more robust when solving different types of MOPs. To the best of our knowledge, this is the first attempt to construct an HEIA. For MOEAs, some hybrid frameworks have been proposed, e.g., Sindhya et al. [57] introduced a hybrid framework for MOEAs, which uses a local search module to speed up convergence. Tang and Wang [58] proposed a novel hybrid MOEA, which incorporates the concepts of personal best and global best in PSO and multiple crossover operators.The differences between HEIA and existing hybrid MOEAs are the following. One natural difference is that cloning is performed in HEIA, which generates multiple copies of the high-affinity antibodies to be evolved, while existing hybrid MOEAs generally evolve the entire population. The other one is that the proposed hybrid operators in HEIA are modified for MOIAs, e.g., SBX and DE crossover are applied by selecting parent antibodies only from the chosen high-affinity antibodies, while the evolutionary operators in existing hybrid MOEAs usually select parents from the entire population.To describe our proposed hybrid framework in a better way, an implementation example is also included in this paper and some experiments are carried out to assess its performance.