A new multiobjective evolutionary optimization algorithm based on θ -multiobjective clonal selection

Abstract

In this paper a new multi-objective clonal selection algorithm (θ-MCSA) is presented to solve multi-objective problems with multimodal and non-continuous functions. The concept of clonal selection algorithm (CSA) is based on the immune system and white blood cells behavior that select the antibodies similar to antigen for cloning. Although the clonal selection is a robust optimization method, however, as a shortcoming, it takes long time to find optimal Pareto front especially in problems with large search space. To overcome this problem, the proposed method replaces the large search space with the θ-search based on the phase angles. To avoid trapping into local optima in mutation step, two strong mutation methods are implemented according to the iteration number and algorithm efficiency. For converging to uniformly Pareto front in less iterations, the proposed multi-objective algorithm handles the size of the repository and a new population updating mechanism is iteratively applied to select the non-dominate, one-dominate and two-dominate solutions of prior iteration. The experimental results show the efficiency of the proposed θ-MCSA algorithm compared to other methods.

Keywords

Clonal selection multi-objective optimization problem niching non-dominate solution

Nomenclature

X _i

The ith antibody of the θ-MCSA

X_{i}^{mut}

The ith antibody of the θ-MCSA after using mutation

X _best

The best antibody with the maximum affinity value

af _i

The affinity value of the ith antibody and antigen

num _ clone_i

The number of clones of ith antibody

Clonal factor which is generated in the range of [0,1]

Number of antibodies

Number of clones that are selected for new generation

Number of rest population that are generated randomly

levy

Mathematical levy operator

Iter

Iteration index

prob _i

Probability of the ith search method

probn _i

Normalized probability of the ith search method

θ _i,j

Angle of the jth gene of ith antibody in polar coordinate

σ _share

Threshold factor of niching method

1 Introduction

Optimization techniques are worldwide used in several fields of science such as economic and engineering. The main purpose of these techniques is to find the variables for maximizing or minimizing an objective function. The optimization problems are generally divided into single objective and multi-objective ones. The multi-objective ones try to find the values of a set of variables that lead to an optimal solution for multiple objective functions simultaneously where optimal solutions need to be taken in the presence of trade-offs between two or more conflicting objectives. Therefore, a unique optimal solution in multi-objective problems does not exist and the aim is to provide the decision maker with a set of best answers. Since most of problems in real world have more than one objective function, multi-objective optimization problems have found increasing attentions.

In the last decade, several optimization algorithms have been proposed to solve a set of well-known optimization problems. They can be classified into two groups: classical optimization methods and evolutionary ones. Methods in the first group are based on the mathematical theory, such as: golden mean, conjugate gradients, modified Newton method, linear and quadratic programming. Algorithms in the second group are inspired by natural phenomena and the behavior of living organisms. The main strength of these algorithms is their random motion and avoiding from trapping into local optima in finding the global optimum. Genetic algorithm (GA), Particle Swarm Optimization (PSO) and Teaching–Learning-Based Optimization (TLBO) are well known optimization algorithms in the second category.

Some drawbacks of the classical optimization methods are lack of convergence guarantee, long running time, computational complexity and weakness in dealing with multi-objective problems. To overcome these deficiencies, many researchers have attained to this field of research area to develop and improve the evolutionary algorithms (EAs). They derived many enhanced solution methodologies for numerically solving the optimization problems, irrespective of the type of objective functions and constraints. It means that the EAs can be performed in optimization problem with continuous or discrete control variables and concave or convex objective functions. It can be applied on different optimization problems with different characteristic of objective functions to effectively demonstrate their features and capabilities.

The economic and engineering problems are very complex due to the huge number of their objective functions and their types. Therefore, it excites researchers to use EAs in these fields. Though, the primary EAs have some shortcomings, e.g. their dependency to the control parameters and possibility of falling into local optimum solutions. As a result, many researchers followed the natural phenomena with high probability of success and less dependency to the parameters tuning like body immune system.

In the past decade, a lot of studies have been performed in the field of artificial immune systems and their applications [1 –4]. The clonal selection algorithm (CSA) designed based on immune system has been introduced in [5] to solve the optimization problems. Special features of the CSA are strong search process and its proper balance between global and local search.

As mentioned before, the idea of the CSA is based on the immune system operation. This means that when an antigen such as bacteria, viruses, man-made molecules or any potentially harmful thing is introduced into the body, it stimulates an immune response, specifically activates white blood cell to produce antibody. White blood cells create different and various antibodies, each can react to a special antigen with similar characteristic and neutralize it. According to the presented theory in [6], the reaction of one antibody with intended antigen causes white blood cells to produce more antibodies with similar specificity of the reactant antibody. This theory is known as clonal selection theory. The CSA is based on finding the best antibody which has maximum affinity with the antigen and then proliferation and mutation for reaching the goal.

Many studies have been conducted to improve the CSA method that modifies selection, clonal or mutation operations [7 –9], they suffer from many shortcomings yet. In multimodal problems, CSA traps into local extremes. Also, it needs many generations to converge into the optimal solutions in problems with large search space.

In this paper, the θ-search has been used to improve the CSA that accelerate the algorithm convergence. Moreover, two mutation methods are utilized to find global solutions. Also, in the proposed θ-search method, the polar symmetric search space is applied instead of Cartesian type. This leads to more uniform responses and faster convergence.

Another important point is that most of single objective EAs can also be utilized to solve multi-objective problems. There are several well-known methods for this purpose, and among them, the simplest way is to combine the objectives into a single problem. This method is called scalarization technique [10] such as the weighted-sum, epsilon, fuzzy and fuzzy clustering methods [11 –16]. Though they find just one solution in each run, researchers would rather to have a set of solutions to select the best one based on the circumstance. As a result, the best technique in multi-objective problems is Pareto method in which there are multiple optimal solutions [17 –20]. The concern of the Pareto method is to find solutions those are not dominated by the other solutions. Pareto front consists of a set of optimal solutions in each run using all the objectives with continuous and uniform distribution ideally. Multi-objective algorithms are not usually able to find the ideal Pareto. In many cases, the output solutions do not uniformly cover the entire surface of the Pareto and a lot of algorithms represent local Pareto in multimodal problems that do not match to optimal Pareto. Some of studies propose CSA as a multi-objective optimization method [21 –24]. In spite of better results, it has some disadvantages such as low speed and local convergence. In this paper, the CSA has been extended for solving multi-objective problems in which θ-search and two strong mutation methods guarantee the speed and global convergence. Furthermore, the proposed algorithm uses non-dominate, one-dominate and two-dominate solutions to generate the new population leading to convergence in fewer generations and populations.

The rest of this paper is organized as follows: in Section 2 the original CSA and the modification in mutation algorithm is completely explained. Section 3 includes description of some important terms used in multi-objective problems and the proposed MCSA. In Section 4 the proposed algorithm is tested in four multi-objective experiments and finally Section 5 presents the conclusion.

2 Improved clonal selection algorithm

2.1 Original clonal selection algorithm [5]

When an antigen introduces into the body, it stimulates an immune response, specifically activates white blood cell to produce antibody. It has been equated with the first stage of CSA in which the primary population of antibodies is generated randomly. Antigen plays the role of optimal solution which is the purpose of the algorithm. Therefore, an affinity criterion should be identified for comparing antibodies with antigen defined as: $af = {\begin{matrix} fitness function & if aim is maximizing \\ - fitness function & if aim is minimizing \end{matrix}$ (1) where af is affinity value between antibody and antigen. Each antibody with more similarity to the antigen has higher affinity.

The antibodies with high affinity value stimulate the related white cells to clone and secrete more similar antibodies. As a result, the population members of the clone are generated in CSA according to the affinity value for each antibody as follows: $num_c {lone}_{i} = round (\frac{β \times Na}{i} + 0.5)$ (2) where i is the order of antibody after sorting the population in ascending order into affinity value, num _ clone_i is the number of clones secreted from a specific white cell related to ith antibody, Na is the fraction of antibodies assigned to clone and d remaining antibodies discard (d = N - Na). Finally, β is the clonal factor such that β ∈ (0 - 1]. The clonal factor can change the number of clone. The algorithm converges faster when β is closer to 1. Of course, higher computational complexity would be increased. For example if Na is 10 with β = 1, the number of clones for the best antibody is num _ clone₁ = 10 and for the second one is. However, if β = 0.5, num _ clone₁ and num _ clone₂ are 5 and 3 respectively. The remaining antibodies are discarded.

When an antigen enters the body for the first time, immune system randomly creates some antibody. However, only the antibody with high affinity is saved in a memory pool. As a result, if that antigen attacks for the second time the body recognizes this and uses the antibody from the pool. It leads to a faster reaction. On the other hand, the immune system changes some genes of antibody for better encountering the antigen. This stage is called mutation step in which the generated clones mutate for achieving better affinity value.

After mutation step, the affinity values of clones are calculated and Na of best clones are replaced by the selected antibodies from the prior population. Then d antibodies are randomly generated to provide the new antibodies. The d is equal to N - Na. The CSA is repeated to satisfy the stopping condition.

2.2 Modification in mutation step of CSA

In this paper the mutation step has been modified to increase the local and global search ability of the CSA. Two mutation and search algorithms are introduced and each clone selects one of them according to the iteration number and algorithm efficiency in prior iteration. These methods are as follow:

Search algorithm1: This search method is used to guarantee that the whole search space is covered by levy flight algorithm. Levy flight is a random walk in which step length obeys the heavy-tailed distribution. This algorithm inspired by the search method that animals use to find food which include small step in a specific location and then large relocation to another place with high chance of finding food. Levy flight is a strong search tool that can search locally and globally. This algorithm is expressed as follows: $levy (w) = {iter}^{- w}, 1 < w \leq 3$ (3)

Now the mutated clone is: $X_{i}^{new} = X_{i}^{old} + φ_{i} levy (w)$ (4)

The antibody genes can be changed using the proposed tool. The antibody changes more when the w is small. The levy flight is perfect in multimodal problem because it can appropriately escape from locals.

Search algorithm 2: in this algorithm, the search space is explored by the combination of the existent population feature. Using the following simple mathematical formula, five variant members of population is combined:

$\begin{matrix} X_{i}^{mut} = X_{k 1} + F_{1} (X_{k 2} - X_{k 3}) + F_{2} (X_{k 4} - X_{k 5}) \\ k 1 \neq k 2 \neq k 3 \neq k 4 \neq k 5 \neq i \end{matrix}$ (5)

There is another version of this search algorithm in which exploration is in the direction of the best member as follow:

$\begin{matrix} X_{i}^{mut} = X_{best} + F_{1} (X_{k 1} - X_{k 2}) + F_{2} (X_{k 3} - X_{k 4}) \\ k 1 \neq k 2 \neq k 3 \neq k 4 \neq i \end{matrix}$ (6)

Finally, by using the cross over parameter some genes of $X_{i}^{mut}$ or X_i are chosen as follows: $x_{i, j}^{new} = {\begin{matrix} x_{i, j}^{mut} & if Cr > rand \\ x_{i, j}^{old} & o . w \end{matrix}$ (7) where x_i,j for {j = 1, 2, …, n} are genes of X_i. The new one is replaced if it has been improved. This is a well-known global search method which is the mutation method in the DE algorithm.

In the first iteration which is needed to explore globally both of methods are perfect. The DE mutation method is basically a global search method and the levy flight has large jump. In the last iteration the steps of levy flight is small that is more appropriate for local search and extraction rather than DE mutation method. For selecting mutation method the following methods are used:

The simplest way is random-selection. Although it would be considered logically unreliable, the evolutionary algorithms are random-based and it makes our algorithm faster.

A more acceptable method is self-adaptive selection for mutation method [9] in which all mutation methods have the same probability values at the beginning (prob_s = 0.5, s = 1, 2). For each clone, one of them is chosen by roulette wheel selection (RWS) [25], but in each iteration the probability values will be updated adaptively by considering their performance in previous iteration. The better mutation method it is, the larger value it has. Therefore, the best mutation is applied more.

This method is more reliable, of course, with higher computational complexity. If the clone population and the number of generations are high, the proposed method will be time consuming.

In the third method, each of search methods has a probability value fixed during the algorithm. The user selects the probability value due to the objective function. Then a search method is selected for each clone by using RWS.

This method is more logical than the first one and it is easy to use in comparison with the second one. Also if the user has more information about the objective he can control it slightly.

The roulette wheel selection (RWS) is applied as follow:

First the probability values are normalized asfollows: ${probn}_{s} = \frac{{prob}_{s}}{\sum_{s} {prob}_{s}}$ (8)

RWS algorithm is described as follows. $\begin{matrix} a = rand \\ if {probn}_{1} > a 1 pt then mutation method = 1 \\ else mutation method = 2 end \end{matrix}$

2.3 θ-CSA

Each function has some variables with different search space and the search spaces are considerably large in some cases. Finding the optimum solution in the large space is really time consuming and needs the numerous population and many iterations. In the θ search method, the polar coordination of variables has been used instead of Cartesian one. This procedure makes all the variables to be only one dimensional. Accordingly, the angle variable is considered for each gene of antibodies. In this order, the limitation of all variables map to (- π/ - 2, π/ - 2). The following operation does this mapping for each antibody’s gene:

$\begin{matrix} θ_{i, j} & = & M (x_{i, j}) \\ = & {sin}^{- 1} (\frac{2 x_{i, j} - (x_{{min}_{j}} + x_{{max}_{j}})}{x_{{min}_{j}} - x_{{max}_{j}}}) \end{matrix}$ (9)

This mapping has one-to-one corresponding so it has inverse for going back to real space:

$\begin{matrix} x_{i, j} = M^{- 1} (θ_{i, j}) \\ = (\frac{x_{{min}_{j}} - x_{{max}_{j}}}{2} \times sin (θ_{i, j}) \\ + \frac{x_{{min}_{j}} + x_{{max}_{j}}}{2}) \end{matrix}$ (10)

So Equations (5–8) change as: $Θ_{i}^{new} = Θ_{i}^{old} + φ_{i} levy (w)$ (11) where Θ is antibody in θ–space, $\begin{matrix} (Θ_{i} & = & {θ_{i, 1}, θ_{i, 2}, \dots, θ_{i, n}}) \\ Θ_{i}^{mut} & = & Θ_{k 1} + F_{1} (Θ_{k 2} - Θ_{k 3}) \\ + F_{2} (Θ_{k 4} - Θ_{k 5}) \end{matrix}$ (12) $\begin{matrix} k 1 & \neq & k 2 \neq k 3 \neq k 4 \neq k 5 \neq i \\ Θ_{i}^{mut} & = & Θ_{best} + F_{1} (Θ_{k 1} - Θ_{k 2}) \\ + F_{2} (Θ_{k 3} - Θ_{k 4}) \end{matrix}$ (13) $\begin{matrix} k 1 & \neq & k 2 \neq k 3 \neq k 4 \neq i \\ θ_{i, j}^{new} & = & {\begin{matrix} θ_{i, j}^{mut} & if Cr > rand \\ θ_{i, j}^{old} & o . w . \end{matrix} \end{matrix}$ (14)

This mapping is for mutation step and for calculating affinity value, the variable is returned back to real space.

Computations would be simpler for variables with the same search space. Furthermore in θ search, the search space is usually smaller than the real space that so that the local solution are closer to global solution and with small movement that the best antibody is found. In the similar size of population, small search space leads to global solution in less number of iteration compared to large search space.

2.4 Methodology of ICSA

Step 1: set prob_s for s = 1, 2, β = 0.9, w ∈ [0.5, 3], the size of population (N),

Step 2: Initialize the antibodies population with size N randomly as follow: X_i = {x_i,1, x_i,2, ⋯ , x_i,n} for i = 1, 2, …, N where n is the number of antibody’s genes.

Step 3: calculate the affinity of each antibody to the antigen Equation (1) and sort them in descending order and select the Na antibodies from the top of list for cloning.

Step 4: produce num _ clone_i clones for each antibody Equation (2).

Step 5: select one of mutation methods by RWS according to their probability and apply it on clones.

Step 6: do Step 3 for clones.

Step 7: produce d = N - Na antibodies randomly. Na antibodies from Step 6 and these d ones generate the new population.

Step 8: Go to Step 3 until the stop conditions are satisfied.

3 Multi-objective improved clonal selection algorithm

3.1 Basic concept of multi-objective problems for CSA

Optimizing some objectives which are conflicting with each other is a multi-objective problem. The purpose of CSA is maximizing affinity values between antibodies and antigen. In CSA, there are multiple antigens in multi-objective problems, each objective is considered as an antigen. The purpose is to find antibody that satisfies multiple affinity criteria simultaneously as follows: $Maximize af = [{af}_{1} (x), {af}_{2} (x), \dots, {af}_{k} (x)]$ (15) where k is the number of objectives. For this kind of problems, typically not only there is a single optimal solution, but also a set of solutions are explored called Pareto solution. All of these solutions are optimal without any preferences. A solution except the Pareto solution makes one of the objectives better and other objectives worse.

The Pareto solutions are non-dominate solutions among the population. x₁ dominate x₂ if: $\forall l \in {1, 2, \dots, k} {af}_{l} (x_{1}) \geq {af}_{l} (x_{2})$ (16) $\exists l \in {1, 2, \dots, k} {af}_{l} (x_{1}) > {af}_{l} (x_{2})$ (17)

The multi-objective CSA (MCSA) is trying to find some antibodies with high similarity to antigen according to all of affinity criteria. In initialization step, a population of antibodies is randomly generated. Among the population, the non-dominate solutions are stored in repository (archive).

3.2 Modification in mutation step of CSA

After some generations, the size of repository might considerably increase leading to more complex computation and less speed. To solve this problem, the maximum size of repository is presetted. If the number of non-dominate solution is more than this size, the following procedure is applied:

Each non-dominate solution is considered as a separate cluster.

For each pair of clusters, the following destination value is calculated: $d_{i, j} = \frac{1}{n_{i} n_{j}} \sum_{i} \sum_{j} d (z_{i}, z_{j})$ (18)

where z_i and z_j are elements of ith and jth clusters and n_i and n_j are their size, respectively. Operator d is the Euclidean distance.

Two clusters with minimum distance merge together and organize a larger cluster.

Steps 2 and 3 are repeated until the number of clusters becomes the maximum size of repository.

In each cluster, antibody with the highest affinity store to repository.

3.3 Sorting the repository in multi-objective problem

Each non-dominate antibody clone is proportional to the order in population due to its affinity value. Now as multiple affinity values exist for antibodies, it is recommended to replace a single value to sort repository elements. There are some methods in this regards as follow:

Max-Min: a fuzzy membership function is introduced for mapping all the affinity functions to fuzzy space as follow:

$\begin{matrix} μ_{l} (i) \\ = {\begin{matrix} \begin{matrix} 0 \\ \frac{{af}_{l} (X_{i}) - {af}_{{min}_{l}}}{{af}_{{max}_{l}} - {af}_{{min}_{l}}} \\ 1 \end{matrix} & \begin{matrix} {af}_{l} (X_{i}) < {af}_{min_{l}} \\ {af}_{min_{l}} < {af}_{l} (X_{i}) < {af}_{max_{l}} \\ {af}_{l} (X_{i}) > {af}_{max_{l}} \end{matrix} \end{matrix} \end{matrix}$ (19)

μ_l (i), l∈ { 1, 2, …, k } and i ∈ {1, 2, …, N_rep} are calculated for all non-dominate antibodies where N_rep is size of repository. $μ (i) = min_{l} {μ_{l} (i)}$ is considered as a symbol of each antibody. Then, the solutions are sorted according to μ (i). The higher membership function value the antibody has, the better order it achieves.

Fuzzy clustering: the first step includes introducing a membership function and computing membership values for repository elements. It is like the prior method. However the single value for lying to each antibody calculated as: $μ_{n} (i) = \frac{\sum_{l = 1}^{k} μ_{l} (i)}{\sum_{i = 1}^{N_{rep}} \sum_{l = 1}^{k} μ_{l} (i)}$ (20)

where k and N_rep are the number of objective functions and repository size.

In this equation all objectives are of the same weight. In specific situations, as some objectives are more important than the others, the decision maker needs to control the effect of each objective by using weighted coefficient as follows: $μ_{n} (i) = \frac{\sum_{l = 1}^{k} ω_{l} μ_{l} (i)}{\sum_{i = 1}^{N_{rep}} \sum_{l = 1}^{k} ω_{l} μ_{l} (i)}$ (21) where ω_l is weight of lth objective function.

Niching [26]: we expect the repository to distribute uniformly in Pareto space. For this propose, the antibodies whose difference of affinity values to others (d_ij) is less than a threshold (σ_share), should clone more. Therefore, the solutions are sorted by the following equation: $sh (d_{ij}) = {\begin{matrix} 1 - \frac{d_{ij}}{σ_{share}} & if d_{ij} < σ_{share} \\ 0 & o . w . \end{matrix}$ (22)

Summation of sh (d_ij) for each solution(i) is inversely proportional to its order in the repository.

After cloning and mutation, non-dominate clones are stored in the repository. Here the first iteration is finished and new population is generated in size of N as follow: if the size of repository is less than N then we use F1 and F2 sets of clones which are dominated one and two times. Finally the repository forms the Pareto solutions.

3.4 Methodology of MCSA

Step 1: Set prob_s for s = 1, 2, β = 0.9, w ∈ [0.5, 3], the size of population (N), N_rep (the maximum size of repository).

Step 2: Initialize the antibodies population of size N randomly as X_i ={ x_1i, x_2i, ⋯ , x_ni } for i = 1, 2, …, N where n is the number of antibody’s genes.

Step 3: Calculate all of affinity values for each antibody as follow: [af₁ (x_i) , af₂ (x_i) , ⋯ , af_k (x_i)] for i = 1, 2, …, N.

Step 4: Determine non-dominate antibodies and store them into the repository.

Step 5: Limit the maximum size of repository to N_rep.

Step 6: Sort the members of repository by one of the following methods: max-min, fuzzy clustering or niching.

Step 7: Produce num _ clone_i clones for each antibody Equation (2).

Step 8: Select one of mutation methods by RWS and apply that on clones.

Step 9: Do Steps 3 to 6 for clones.

Step 10: Produce the new population from N top members of the repository. If the size of repository is less than N, use the antibodies with one, two and more times dominant antibodies, respectively.

Step 11: Go to Step 3 until the stop condition satisfied.

4 Experimental result

Two important parameters for multi-objective algorithms evaluation are efficiency and robustness. More efficient algorithms find the optimal solution or Pareto in fewer generations. This characteristic is important because some multi-objective problems are time consuming. Robustness means the independence from initial conditions and repeatable optimal Pareto. To satisfy the robustness condition of the proposed algorithm, it has been run20 times.

4.1 Experiment 1

In this experiment result of the proposed method on two-objective problems has been compared with optimal Pareto solution. Figure 1 demonstrates that the Pareto of proposed method is matched with optimal Pareto. These results obtain by 12 populations and 100 generations.

1. Schaffer function 1 [27]: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = x^{2} and f_{2} (x) = {(x - 2)}^{2} \end{matrix}$ where -A ≤ x ≤ A while A changes from 10 to 10⁵. Increasing A leads to increasing the difficulty of problem. The proposed algorithm has solved this problem with different values of A successfully.

2. Schaffer function 2 [27]: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = {\begin{matrix} \begin{matrix} - x & if x \leq 1 \end{matrix} \\ \begin{matrix} x - 2 & if 1 < x \leq 3 \end{matrix} \\ \begin{matrix} 4 - x & if 1 < x \leq 3 \end{matrix} \\ \begin{matrix} x - 4 & if x \leq 1 \end{matrix} \end{matrix} \\ and f_{2} (x) = {(x - 5)}^{2} \end{matrix}$ where -5 ≤ x ≤ 10.

3. Poloni function: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (\vec{x}) = [1 + {(A_{1} - B_{1} (\vec{x}))}^{2} + {(A_{2} - B_{2} (\vec{x}))}^{2}] \\ f_{2} (x) = {(x + 3)}^{2} + {(y + 1)}^{2} \end{matrix}$ where: ${\begin{matrix} A_{1} = 0.5 sin (1) - 2 cos (1) + sin (2) - 1.5 cos (2) \\ A_{1} = 1.5 sin (1) - cos (1) + 2 sin (2) - 0.5 cos (2) \\ A_{1} = 0.5 sin (x) - 2 cos (x) + sin (y) - 1.5 cos (y) \\ A_{1} = 1.5 sin (x) - cos (x) + 2 sin (y) - 0.5 cos (y) \end{matrix}$ and -π ≤ x, y ≤ π.

Although Schaffer function 2 and Poloni function are non-continuous, our algorithm has found their optimal Pareto fast.

4.2 Experiment 2

Here, some criteria have been used to quantitatively evaluate the proposed method.

Generational distance (GD): GD value that introduced in [28] shows the matching factor between the Pareto optimal and Pareto of our method according to following equation: $GD = \frac{\sqrt{\sum_{i = 1}^{neq} d_{i}^{2}}}{N}$ (23) where neq is the number of non-dominate solutions in the found Pareto and d_i is the Euclidean distance between ith non-dominate solution and the nearest element of optimal Pareto.

Spacing (SP) [29]: This criterion measures the variance of non-dominate solutions for determining the distribution of Pareto front members. $SP = \sqrt{\frac{1}{neq - 1} \sum_{i = 1}^{neq} {(\vec{d} - {dm}_{i})}^{2}}$ (24) where ${dm}_{i} = min_{j} (\sum_{l = 1}^{k} | f_{l}^{i} - f_{l}^{j} |)$ . If non-dominate solutions distribute uniformly, SP is zero.

Error rate(ER) [30]: It indicates the fraction of repository members that are not from optimalPareto. $ER = \frac{\sum_{i = 1}^{neq} e_{i}}{neq}$ (25) where e_i = 0 if ith non dominate solution is a member of Pareto optimal and e_i = 1 otherwise.

In the proposed method, two search algorithms have been used. As using two search methods together lead to more computational complexity, it results in acceleration of convergence. Table 1 demonstrates criteria values for our proposed method in prior multi-objective functions. First and second rows just consider one of search methods and the third one both of them are used that it achieves the best results. These results have been obtained for the same condition as 12 populations and 100 generations.

In the other experiment, we evaluate the performance of θ-search MCSA compared to MCSA. Table 2 shows the criteria values for the proposed algorithm with and without θ-search. For this part the Schaffer function 1 for different values of A has been used, because increasing A makes the real search space larger and improvement by θ-search is more clear and of course, convergence to global solution needs more generations. Therefore for fixed iteration number θ-search has better result due to small search space.

4.3 Experiment 3

There are a lot of evolutionary algorithms for solving single- and multi-objective optimization problems. As a result, to make sure about performance, the proposed algorithm should be tested for different diversity problems and compared with other well-known algorithms. In this paper, ZDT functions [31] has been used and the method is compared with non-dominated sorting genetic algorithm II (NSGA II) proposed by Deb et al. [32] that is one of the most important multi-objective methods. Also the proposed algorithm has been compared with a similar method, the immune clonal multi-objective algorithm (ICMOA) proposed in [33].

The test functions are:

C.1.ZDT2 function: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = x_{1} \\ f_{2} (x) = g (x) (1 - {(\frac{x_{1}}{g (x)})}^{2}), g (x) \\ = 1 + 9 \frac{\sum_{i = 2}^{n} x_{i}}{n - 1} \end{matrix}$ where 0 ≤ x_i ≤ 1, i = 1, 2, …, n and n = 30. The Pareto optimal of ZDT2 has non-convex form.

C.2.ZDT3 function: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = x_{1} \\ f_{2} (x) = g (x) (1 - \sqrt{\frac{x_{1}}{g (x)}} - \frac{x_{1}}{g (x)} sin (10 π x_{1})) \\ g (x) = 1 + 9 \frac{\sum_{i = 2}^{n} x_{i}}{n - 1} \end{matrix}$ where 0 ≤ x_i ≤ 1, i = 1, 2, …, n and n = 30. ZDT3 consists of some non-continuous parts because of sine term.

These two functions are easy problems and all of forefront optimization methods including proposed algorithm has output Pareto matched by the optimal Pareto. Their Pareto front have been demonstrated in Figs. 2 and 3.

C.3.ZDT4 function: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = x_{1} \\ f_{2} (x) = g (x) (1 - \sqrt{\frac{x_{1}}{g (x)}}) \\ g (x) = 1 + 10 (n - 1) \\ + \sum_{i = 2}^{n} [x_{i}^{2} - 10 cos (4 π x_{i})] \end{matrix}$ where 0 ≤ x₁ ≤ 1, - 5 ≤ x_i ≤ 5, i = 2, 3, … n and n = 10. This multi-objective problem is multimodal because it has 21 local Pareto and just the global optimization algorithms can find the truth Pareto. Figure 4 shows the performance of mentioned methods in this problem. NSGAII and ICMOA have been converged to local extremes. However, the proposed method has found the global Pareto in the low generations successfully.

C.4.ZDT6 function: $\begin{matrix} Minimize F = (f_{1}, f_{2}) \\ f_{1} (x) = 1 - e^{(- 4 x_{1})} {sin}^{6} (6 π x_{1}), \\ f_{2} (x) = g (x) (1 - {(\frac{f_{1} (x)}{g (x)})}^{2}), \\ g (x) = 1 + 9 {[\frac{\sum_{i = 2}^{n} x_{i}}{n - 1}]}^{\frac{1}{4}} \end{matrix}$ where 0 ≤ x_i ≤ 1, i = 1, 2, …, n and n = 30. This test function is difficult due to the non-uniformity of search space. The result in Fig. 5 indicates the CSA-based algorithms are strong for this kind of problems. Table 3 compares the proposed algorithm and NSGAII according to three mentioned criteria. Superiority of our method is clear in this table.

5 Conclusion

In this paper, we have extended the CSA algorithm to handle the multi-objective problems. Two strong mutation and search methods are performed for exploration and exploitation that are chosen proportional to their probability values. As both mutation algorithms are global search method and are applied separately in many evolutionary algorithms, the experimental result confirm that applying both of them together leads to better results. On the other hand, due to small and fix search space, θ-search method reduces the iterations and population size for convergence and simplifies the calculations. Finally, this method is really fast and achieves the optimal Pareto front with fewer generations. As non-dominate antibodies have been stored in the repository clone for new population, to increase the speed of algorithm, the size of repository has been limited by clustering methods. To obtain the best new population in the next generation the non-dominate clones have been used and if they are not enough then the one-dominate and two-dominate clones have been used. The performances of the proposed algorithm have been compared with three well-known methods on some multi-objectives problems. The results show that the proposed algorithm is faster and more efficient in comparison with the others. Although many famous algorithms never reached the vicinity of the optimal front in multimodal and non-continuous functions, the θ-MCSA performs the smooth and uniform Pareto similar to Optimal Pareto.

References

Ishida

, The Immune System as a Self-Identification Process: A Survey and a Proposal, In Proc of the IMBS’96, 1996.

Hunt

J.E.

and Cooke

D.E.

, Learning using an artificial immune system, Journal of Network and Computer Applications 19 (1996), 189–212.

Dasgupta

, Artificial Immune Systems and Their Applications, Ed., Springer-Verlag, 1999.

Hofmeyr

S.A.

and Forrest

, Immunity by Design: An Artificial Immune System, Proc Of GECCO’99, (1999), pp. 1289–1296.

De Castro

L.N.

and Von Zuben

F.J.

, The Clonal Selection Algorithm with Engineering Applications, In: Proceedings of GECCO 2000, (2000), pp. 36–37.

Silverstein

A.M.

, A History of Immunology. Academic Press, San Diego, 1989.

de Castro

L.N.

and Von Zuben

F.J.

, Learning and optimization using the clonal selection principle, IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems 6(3) (2002), 239–251.

de Castro

L.N.

and Von Zuben

F.J.

, Learning and optimization using the clonal selection principle, IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems 6(3) (2002), 239–251.

Kavousi-Fard

and Niknam

, Optimal distribution feeder reconfiguration for reliability improvement Considering Uncertainty, IEEE Transactions on Power Delivery 29(3) (2014), 1344–1353.

10.

Caramia

and Dell’Olmo

, Multi-objective Management in Freight Logistics: Increasing Capacity, Service Level and Safety with Optimization Algorithms, Springer, 2008.

11.

Koski

, Defectiveness of weighting method in multicriterion optimization of structures, Commun Appl Numer Methods 1 (1985), 333–337.

12.

Koski

, Multicriteria truss optimization. In: Stadler

, (ed.) Multicriteria Otimization in Engineering and in the Sciences, New York: Plenum, 1988.

13.

Das

and Dennis

J.E.

, A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, Struct Optim 14 (1997), 63–69.

14.

Marglin

, Public Investment Criteria. Cambridge, MA: MIT Press, 1967.

15.

Steuer

R.E.

, Multiple Criteria Optimization: Theory, Computation and Application. New York: Wiley, 1986.

16.

Lin

, Multiple objective problems: Pareto-optimal solutions by method of proper equality constraints, IEEE Trans Autom Control 21 (1976), 641–650.

17.

Messac

and Mattson

C.A.

, Generating well-distributed sets of pareto points for engineering design using physical programming, Optim Eng 3 (2002), 431–450.

18.

Messac

, Ismail-Yahaya

and Mattson

C.A.

, The normalized normal constraint method for generating the pareto frontier, Struct Multidisc Optim 25 (2003), 86–98.

19.

Mattson

C.A.

and Messac

, Concept selection using s-Pareto frontiers, AIAA J 41 (2003), 1190–1204.

20.

Messac

and Mattson

C.A.

, Normal constraint method with guarantee of even representation of complete pareto frontier, AIAA J 42 (2004).

21.

Wang

X.L.

and Mahfouf

, ACSAMO an adaptive multi objective optimization algorithm using the clonal selection principle, 2th European Symposium on Nature Inspired Smart Information System, Puerto de la Cruz, Tenerife, Spain, 2006.

22.

Batista

L.S.

, Oliveira

D.B.

, Guimarães

F.G.

and Silva

E.J.

, Dynamic multiobjective clonal selection algorithm for engineering design, IEEE Transactions on Magnetics 46(8) (2010), 3033–3036.

23.

Hong

and Ji

, An adaptive multi-objective clonal selection algorithm, International Symposium on Computer Communication Control and Automation (3CA) 1 (2010), 233–236.

24.

Srinivasa Rao

, and Vaisakh

, Multi-objective adaptive Clonal selection algorithm for solving environmental/economic dispatch and OPF problems with load uncertainty, International Journal of Electrical Power & Energy Systems 53 (2013), 390–408.

25.

Goldberg

D.E.

, Genetic Algorithms for Search, Optimization, and Machine Learning, Reading, MA: Addison-Wesley, 1989.

26.

Horn

, Nafpliotis

and Goldberg

D.E.

, A niched Pareto genetic algorithm for multiobjective optimization, in Proc 1st IEEE Conf Evol Comput, IEEE World Congr Comput Intell, 1, (1994), pp. 67–72.

27.

Fogel

D.B.

, An introduction to simulated evolutionary optimization, IEEE Trans on Neural Networks: Special Issue on Evolutionary Computation 5(1) (1994), 3–14.

28.

Van Veldhuizen

D.A.

and Lamont

G.B.

, Multiobjective evolutionary algorithm research: A history and analysis, Dept Elec Comput Eng, Graduate School of Eng, Air Force Inst Technol, Wright-Patterson AFB, OH, Tech Rep TR, 1998.

29.

Schott

J.R.

, Fault tolerant design using single and multicriteria genetic algorithm optimization, M.S. Thesis, Dept Aeronautics and Astronautics, Massachusetts Inst Technol, Cambridge, MA, 1995.

30.

Van Veldhuizen

D.A.

, Multiobjective evolutionary algorithms: Classifications, analyzes, and new innovations, Ph.D. Dissertation, Dept Elec Comput Eng, Graduate School of Eng, Air Force Inst Technol, Wright-Patterson AFB, OH, 1999.

31.

Zitzler

, Deb

and Thiele

, Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary Computation 8(2) (2000), 173–195.

32.

Pratap

, Deb

, Agarwal

and Meyarivan

, A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, in KanGAL Report 200001, Indian Institute of Technology, Kanpur, India, 2000.

33.

Ronghua

, Wenping

and Wei

, Immune Clonal MO Algorithm for ZDT Problems, Advances in Natural Computation Lecture Notes in Computer Science, 4222, (2006), pp. 100–109.