An Immune Multiobjective Optimization with Backtracking Search Algorithm Inspired Recombination

Abstract

We propose a novel hybrid multiobjective (MO) immune algorithm for tackling continuous MO problems. Similarly to the nondominated neighbor immune algorithm (NNIA), it considers the characteristics of OM problems: based on the fitness values, the best individuals from the test population are selected and recombined to guide the rest of the individuals in the population to the Pareto front. But NNIA uses the simulated binary crossover (SBX), which uses the local search method. In our algorithm, the recombination is essentially inspired by the cross used in the backtracking search algorithm (BSA), but the adaptations are found in the immune algorithm. Thus, three variants are designed in this chapter, resulting in new recombination operators. They are evaluated through 10 benchmark tests. For the most advanced proposed variant, which is designed to have global search ability, results show that an improved convergence and a better diversity of the Pareto front are statistically achieved when compared with a basic immune algorithm having no recombination or to NNIA. Finally, the proposed new algorithm is demonstrated to be successful in approximating the Pareto front of the complex 10 bar truss structure MO problem.

1. Introduction

Planty of the multiobjective (MO) optimization problems lie in the engineering field. The objective functions are contradictory, the optimal solutions of these problems are known by the Pareto front. To get the optimal solutions of these problems, evolutionary algorithms (EAs) have been recognized to be very efficient in solving MO optimization problems by finding a representative Pareto front in one run. State-of-the-art algorithms are presented in [1, 2, 3, 4, 5]. These algorithms, which are population-based, are able to simultaneously explore various regions of the Pareto front.

In last past few years, immune systems have inspired new algorithms for resolutions OM problems. The fundamental principles of the artificial immune system (AIS) algorithm are clonal selection, [6] mutation, and more recently, recombination [7, 8, 9, 10, 11, 12, 13, 14, 15].

The nondominated neighbor-based immune optimization algorithm (NNIA) is effective to deal with MO problems [9]. NNIA has proved that it is advantageous to incorporate a crossover operator into the algorithm. To do this, it uses simulated binary crossover (SBX). But SBX is a recombination operator, which performs search near the recombination parent [16].

Backtracking Search Optimization Algorithm (BSA) is a new nature-inspired algorithm proposed by [17]. BSA’s special mechanism to ensure a trial individual is effective, ability to learn fast solving different numerical optimization problems sequentially and quickly, with a clear structure. Since it was introduced, the BSA has attracted many research studies, and it has been applied to various optimization problems [18, 19, 20].

In this chapter, we develop a novel hybrid MO immune method to solve the problems of continuous multiobjective optimization. The NNIA algorithm uses the best individuals in the trial population to drive the search to Pareto front. But NNIA uses SBX, which mainly has local search capability. In our proposal, the recombination is inspired by the cross used in the BSA algorithm, but adaptations are found to fit the immune algorithm. Therefore, three variants are considered in the context of this chapter, which gives rise to new recombination operators for immune algorithm.

This chapter is organized as follows: In Section 2, we introduce the MO problem. In Sections 3 and 4, NNIA algorithm and BSA recombination are presented, and we propose new algorithms to solve the MO problem. The effectiveness of these algorithms is investigated in Section 5 when confronting to various MO test problems. In Section 6, the chosen algorithm is applied to solve the multiobjective topology optimization of truss structures. A short summary is proposed to conclude this paper.

2. Multiobjective optimization problem

The multiobjective optimization problem is formalized in this section. Concepts related to the Pareto front are introduced, firstly from a theoretical point of view and then when considering its approximation through a numerical approach [21].

2.1 Pareto front

Let us consider the following multiobjective optimization (MO) problem:

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{min}\mathbf{f}\left(\mathbf{x}\right)={\left(f_1\left(\mathbf{x}\right),\cdots ,f_m\left(\mathbf{x}\right)\right)}^{\mathrm{T}}$$E1

where $m$ is the number of objective functions, $\mathbf{x}=\left({\mathrm{x}}_1,\cdots ,{\mathrm{x}}_n\right)\in \mathrm{\Omega }$ is the $n_x$-dimensional decision space where each decision variable $x_i$ is bounded by lower and upper limits $x_{\mathit{li}}\le x_i\le x_{\mathit{ui}}$ for $i=1,\cdots ,n_x$.

Pareto-front-related concepts are [22]:

1. Pareto dominance: Suppose${\mathbf{x}}_a$and${\mathbf{x}}_b$are two different feasible solutions to the MO problem. Then${\mathbf{x}}_a$dominates${\mathbf{x}}_b$if and only if

$$f_i\left({\mathrm{x}}_a\right)\le f_i\left({\mathbf{x}}_b\right))\forall i\in \left\{1,\cdots ,m\right\}$$E2

and:

$$\exists k\in \left\{1,\dots ,m\right\}{f}_k\left({\mathbf{x}}_a\right)<f_k\left({\mathbf{x}}_b\right)$$E3

1. Pareto-optimal solution: A solution ${\mathbf{x}}^{\ast }$ is said to be Pareto-optimal if there does not exist another solution that dominates it.

2. Pareto-optimal set: The Pareto-optimal set is the set $X^{\ast }$ of all Pareto-optimal solutions.

3. Pareto-optimal front: The Pareto-optimal front is the set $F^{\ast }$ of values or outcomes of all the objective functions, which corresponds to the solutions:

$$F^{\ast }=\left\{\mathbf{f}\left({\mathbf{x}}^{\ast }\right)={\left(f_1\left({\mathbf{x}}^{\ast }\right),\dots ,f_m\left({\mathbf{x}}^{\ast }\right)\right)}^{\mathrm{T}}\text{such\hspace{0.17em}that}:{\mathbf{x}}^{\ast }\in X^{\ast }\right\}$$E4

2.2 Multiobjective solution

Otherwise, the following terms are cited in the reference [9]:

1. Antibody: An antibody refers to the coding of a decision variable $\mathbf{x}$. In this study, a real-valued representation is adopted, being $\mathbf{x}$ itself.

2. Crowding distance: The crowding distance (CD) is a measure for diversity maintenance [1]. It reads:

$$\mathit{CD}\left(\widehat{\mathbf{X}}\right)=\sum _{j=1}^m\frac{D_j\left(\widehat{\mathbf{X}}\right)}{f_j^{\max }-f_j^{\min }+{\epsilon }_D}$$E5

where $f_j^{\max }$ and $f_j^{\min }$ are maximal and minimal values of the $j$-th objective respectively, ${\epsilon }_D$ is a small number and:

$$D_j\left(\widehat{\mathbf{X}}\right)=\left\{\begin{array}{lll}\infty & \text{if}& {\widehat{\mathbf{x}}}_k\text{is}\mathrm{a}\text{boundary\hspace{0.17em}point\hspace{0.17em}of}\widehat{\mathbf{X}}\\ min\left|f_k\left(\widehat{\mathbf{X}}\right)-f_l\left(\widehat{\mathbf{X}}\right)\right|& & \text{otherwise}\end{array}\right.$$E6

for $k,l\in \left\{1,\cdots ,n_x\right\}$ such that $k\ne l\ne j$.

3. Immune optimization algorithm and recombination operator

3.1 Nondominated neighbor immune optimization algorithm

Nondominated neighbor immune algorithm (NNIA), using the nondominated neighbor-based selection and proportional cloning, pays more attention to the less-crowded regions of the current trade-off front.

We denote by $\widehat{\mathbf{X}}$ the dominant population, ${\mathbf{X}}_A$ the active population and ${\mathbf{X}}_C$ the clone population at time $t$ are stored by time-dependent variable matrices, Their sizes are $n_{\widehat{X}}$, $n_A$, and $n_C$ respectively.

The NNIA algorithm is presented in 1 where: = is the update operator. $n_D$, $n_{\hat{X}max}$, $n_{Amax}$, $n_C$, and $n_{\mathit{it}}$, the number of iterations.

Algorithm 1 Pseudo code of NNIA

$\mathbf{\text{Function}}\widehat{\mathbf{X}}=\mathit{\text{NNIA}}\left(n_x,m,\mathbf{f}\left(\mathbf{x}\right),{\mathbf{x}}_l,{\mathbf{x}}_u,n_{\widehat{X}max},n_{Amax},n_C,n_{\mathit{it}}\right)$

1: Generate a uniform random initial population $\widehat{\mathbf{X}}$ of size $n_C\times n_x$ in respect to ${\mathbf{x}}_l$ and ${\mathbf{x}}_u$;

2: $\widehat{\mathbf{X}}≔\mathit{\text{Find}}\_\mathit{\text{Non}}\_\mathit{\text{Dominated}}\left(\widehat{\mathbf{X}}|\mathbf{f}\left(\mathbf{x}\right)\right)$;

3: for$t=0:n_{\mathit{it}}$, do

4:  ${\mathbf{X}}_A≔\mathit{CD}\_\mathit{\text{Truncation}}\left(\widehat{\mathbf{X}},n_{Amax}\right)$;

5:  ${\mathbf{X}}_C≔\mathit{\text{Cloning}}\left({\mathbf{X}}_A,n_C\right)$;

6:  ${\mathbf{X}}_C≔\mathit{\text{Recombination}}\left({\mathbf{X}}_C,{\mathbf{X}}_A,{\mathbf{x}}_l,{\mathbf{x}}_u\right)$;

7:  ${\mathbf{X}}_C≔\mathit{\text{Hypermutation}}\left({\mathbf{X}}_C,{\mathbf{x}}_l,{\mathbf{x}}_u\right)$;

8:  $\widehat{\mathbf{X}}≔\mathit{\text{Find}}\_\mathit{\text{Non}}\_\mathit{\text{Dominated}}\left(\left[\widehat{\mathbf{X}};{\mathbf{X}}_C\right]|\mathbf{f}\left(\mathbf{x}\right)\right)$;

9:  $\widehat{\mathbf{X}}≔\mathit{CD}\_\mathit{\text{Truncation}}\left(\widehat{\mathbf{X}},n_{\widehat{X}max}\right)$;

end for

3.2 Recombination and crossovers

3.2.1 NNIA recombination

For a recombination, operation of NNIA has been adopted in many MO EAs [1, 4], an antibody of the cloning population and an antibody of the active population are selected and modified as:

$${\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}≔\left\{\begin{array}{lll}\frac{1-\beta }{2}{\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}+\frac{1+\beta }{2}{\left\{{\mathbf{X}}_A\right\}}_{\mathit{kj}}& \text{if}& a=1\&b=0\\ \frac{1+\beta }{2}{\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}+\frac{1-\beta }{2}{\left\{{\mathbf{X}}_A\right\}}_{\mathit{kj}}& \text{if}& a=1\&b=1\\ {\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}& \text{if}& a=0\end{array}\right.\mid a\sim \mathcal{U}\left(0,1\right),b\sim \mathcal{U}\left(0,1\right)$$E7

for $i\in \left\{1,\dots ,n_C\right\}$, $j\in \left\{1,\dots ,n_x\right\}$_, and $k$ a random integer uniformly chosen in $\left\{1,\dots ,n_A\right\}$. Above, $\mathcal{U}$ is the uniform discrete distribution, and $\beta$ is a sample from a random distribution having the density:

$$p\left(\beta \right)=\left\{\begin{array}{lll}0& \text{if}& \beta <0\\ \frac{\eta +1}{2}{\beta }^{\eta }& \text{if}& 0\le \beta \le 1\\ \frac{\eta +1}{2{\beta }^{\eta +2}}& \text{if}& \beta >1\end{array}\right.$$

where $\eta$ is a real nonnegative distribution. Hence, four independent random variables are involved in this recombination operation: $a$, $b$, $k$, and $\beta$. A boundary control is performed by:

$${\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}≔\left\{\begin{array}{lll}{x}_{\mathit{li}}& \text{if}& {\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}<x_{\mathit{li}}\\ {\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}& \text{if}& x_{\mathit{li}}\le {\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}\le x_{\mathit{ui}}\\ x_{\mathit{ui}}& \text{if}& {\left\{{\mathbf{X}}_C\right\}}_{\mathit{ij}}>x_{\mathit{ui}}\end{array}\right.$$

3.2.2 Crossover operator of backtracking search optimization algorithm

Crossover strategy of BSA [17]. It consists in mixing two input populations ${\mathbf{X}}_P$ and ${\mathbf{X}}_Q$ to form a new output population ${\mathbf{X}}_R$, of equal sizes: $n_X\times n_x$. Then, BSA’ crossover reads:

$${\left\{{\mathbf{X}}_R\right\}}_{\mathit{ij}}≔\left\{\begin{array}{lll}{\left\{{\mathbf{X}}_P\right\}}_{\mathit{ij}}& \text{if}& {\mathbf{T}}_{\mathit{ij}}=0\\ {\left\{{\mathbf{X}}_Q\right\}}_{\mathit{ij}}& \text{if}& {\mathbf{T}}_{\mathit{ij}}=1\end{array}\right.$$E8

for $i\in \left\{1,\dots ,n_X\right\}$, $j\in \left\{1,\dots ,n_x\right\}$ and where $\mathbf{T}$ is a boolean matrix of sizes: $n_X\times n_x$_, which is formed by following the algorithm 2.

To control the amount of mixing between the two populations ${\mathbf{X}}_P$ and ${\mathbf{X}}_Q$, we must define the parameter $\eta$ such that $0<\eta \le n_x$. Moreover, we perform a random permutation on the lines of the ${\mathbf{X}}_P$ population before applying the relation (8).

Algorithm 2 Algorithm for the generation of the T matrix used in the BSA crossover

1: Initialize $\mathbf{T}≔\mathbf{0}$ and $a≔\mathcal{U}\left(0,1\right)$;

2: if$a=0$then

3:  for$i=1:n_X$do

4:   $u≔\mathit{\text{Permuting}}\left(1:n_x\right);$

5:   $b≔\mathcal{U}\left(0,\eta \right);$

6:   for$k=1:b$do

7:   $j=u_k;$

8:   $T_{\mathit{ij}}=1;$

9:   end for

10:  end for

11: else

12:  for$i=1:n_X$do

13:   $j≔\mathcal{U}\left(0,n_x\right);$

14:   $T_{\mathit{ij}}=1;$

15:  end for

16: end if

4. Recombination propositions for an hybrid algorithm

To get a more efficient immune algorithm, we will propose a hybridization method, which consists of exchanging the crossover operator used for recombination in NNIA with a new recombination operator inspired by BSA [23].

To find this new algorithm, we have to use two ideas:

1. The first idea consists of expanding the active population in order to obtain an extended active population, having its size equal to the clonal population size. The simplest way to achieve this consists of duplicating the active population;

2. The second idea consists of replacing the active population for the crossover by the clonal population, leading finally to a crossover that uses only the clonal population.

5. Experiments

In this section, we study the performance of the hybridization when solving some well-known MO techniques including five ZDT problems [24] and five DTLZ problems [25].

An optimization problem is typically written as:

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{min}\mathbf{f}\left(\mathbf{x}\right)={\left(f_1\left(\mathbf{x}\right),\cdots ,f_m\left(\mathbf{x}\right)\right)}^{\mathrm{T}}$$E9

where $m$ is the number of objective functions, $\mathbf{x}=\left({\mathrm{x}}_1,\cdots ,{\mathrm{x}}_n\right)\in \mathrm{\Omega }$ is the $n_x$-dimensional decision space where each decision variable $x_i$ is bounded by lower and upper limits $x_{\mathit{li}}\le x_i\le x_{\mathit{ui}}$ for $i=1,\cdots ,n_x$.

5.1 Performance metrics

Approximate Pareto front solution of MO algorithms must achieve these two goals:

1. Convergence toward the true Pareto front; and

2. Diversity of solutions: the Pareto front must be uniformly distributed and spread over the entire feasible objective space to adequately capture the trade-offs.

For benchmark test problems, the true Pareto front is known, allowing to exploit performance metrics that used it.

We opted for two performance metrics for assessing algorithms efficiency. To measure the extent of the convergence to the true set of Pareto-optimal solutions and the spread of the Pareto front set, a normalized version of the inverted generational distance (IDG) metric proposed by [26] is adopted, while a normalized version of the spacing metric introduced by [27] enables to measure the uniformity of the obtained solutions.

5.1.1 Normalized inverted generational distance

The normalized inverted generational distance (NIGD) is based on a proposition of [26]. For measuring of the distance between the true Pareto front $F^{\ast }$, which is known at $n^{\ast }$ discrete values—and stored in the matrix $\mathbf{F}\left({\mathbf{X}}^{\ast }\right)$—and approximate solutions of the Pareto-optimal front $\mathbf{F}\left(\widehat{\mathbf{X}}\right)$:

$$\text{NIGD}\left(\mathbf{F}\left({\mathbf{X}}^{\ast }\right),\mathbf{F}\left(\widehat{\mathbf{X}}\right)\right)=\frac{1}{n^{\ast }}\sqrt{{\sum }_{j=1}^{n^{\ast }}{\mathbf{c}}_j^2},$$E10

for:

$${\mathbf{c}}_j=\underset{i\in \left\{1,\dots ,n_X\right\}}{min}\left(\sqrt{{\sum }_{k=1}^m{\left({\overline{\mathbf{F}}}_k\left({\mathbf{X}}_i^{\ast }\right)-{\overline{\mathbf{F}}}_k\left({\widehat{\mathbf{X}}}_j\right)\right)}^2}\right),j\in \left\{1,\dots ,n^{\ast }\right\}$$

where $\overline{•}$ denotes a normalized objective function, ranging from 0 to 1 and defined by:

$${\overline{\mathbf{F}}}_k\left(\mathbf{x}\right)=\frac{{\mathbf{F}}_k\left(\mathbf{x}\right)-min\left({\mathbf{F}}_k\left({\mathbf{X}}^{\ast }\right)\right)}{max\left({\mathbf{F}}_k\left({\mathbf{X}}^{\ast }\right)\right)-min\left({\mathbf{F}}_k\left({\mathbf{X}}^{\ast }\right)\right)}.$$E11

To obtain smaller values of this measure, the approximated set $\mathbf{F}\left(\widehat{\mathbf{X}}\right)$ must be very close to the Pareto front and cannot miss any part of the whole Pareto front at the same time.

5.1.2 Normalized spacing measure

The spacing metric introduced by [27] is modified by taking normalized objectives functions. This leads to the normalized NSP measure, defined by:

$$\mathrm{NSP}\left(\mathbf{F}\left(\widehat{\mathbf{X}}\right)\right)=\sqrt{\frac{1}{n_X-1}{\sum }_{j=1}^{n_X}{\left({\mathbf{d}}_j-\overline{d}\right)}^2}$$E12

for:

$${\mathbf{d}}_j=\underset{\begin{array}{c}i\in \left\{1,\dots ,n_X\right\}\\ i\ne j\end{array}}{min}\left(\sqrt{{\sum }_{k=1}^m{\left({\overline{\mathbf{F}}}_k\left({\widehat{\mathbf{X}}}_i\right)-{\overline{\mathbf{F}}}_k\left({\widehat{\mathbf{X}}}_j\right)\right)}^2}\right),j\in \left\{1,\dots ,n_X\right\}$$

where $\overline{d}$ is the mean of $\mathbf{d}$.

5.2 Empirical comparison

In this section, performance of five NNIA variants are evaluated. The five variants are:

1. NNIA-X: the NNIA algorithm without crossover;

2. NNIA: the algorithm proposed by [9];

3. NNIA+X1: the hybridization of the NNIA algorithm with the BSA crossover by using the first strategy proposed in the Section 4. Inputs of the BSA crossover function are (1) the clonal population and (2) a random permutation of an extended active population obtained by duplicating individuals;

4. NNIA+X2: the hybridization of the NNIA algorithm with the BSA crossover by using the second strategy proposed in the Section 4. Inputs of the BSA crossover function are (1) the clonal population and (2) a random permutation of the clonal population;

5. NNIA+X3: the hybridization of the NNIA algorithm with the BSA crossover by using the third strategy proposed in the Section 4. Inputs of the BSA crossover function are (1) the clonal population and (2) a random permutation of an extended active population obtained by duplicating individuals with a proportion of random individuals.

For NNIA, parameters proposed in Ref. [9] are set:

• maximum size of dominant population: $n_{\widehat{X}max}=100$,

• maximum size of active population: $n_{Amax}=20$, and

• size of clone population $n_C=100$,

with the distribution index for SBX that is 15, the distribution index for polynomial mutation that is 20 and the mutation probability of $1/n_x$ and the number of iterations stopped at 250. For NNIA+X3, the proportion of random individuals is chosen to be equal to $n_A$ and their distribution is uniform.

Figures 1 and 2 show the statistic box plots for NIGD and NSP obtained for 1000 independent runs performed on each test problems ZDT and DTLZ that are chosen by [9]¹.

Figure 1.

NIGD obtained from 1000 independent runs of problems ZDT1, ZDT2, ZDT3, ZDT4, ZDT6, DTLZ1, DTLZ2, DTLZ3, DTLZ4, and DTL7.

Figure 2.

Statistics box plots of NSP obtained from 1000 independent runs of benchmark test problems ZDT1, ZDT2, ZDT3, ZDT4, ZDT6, DTLZ1, DTLZ2, DTLZ3, DTLZ4, and DTL7.

NIGD’s statistical results show that the NNIA algorithm is better than NNIA-X for the problems addressed. We also observe the efficiency of the NNIA+X1 and NNIA+X2 algorithms compared with NNIA with the exception of the difficult DTLZ4 test problem. For ZDT4 problem, NNIA+X3 is lower than NNIA+X1 and NNIA+X2. But we can always notice that our proposed algorithm NNIA+X3 remains superior to NNIA for the problems treated. Except for the two issues ZDT4 and DTLZ4, NSP shows the superiority of NNIA over NNIA-X. In all treated cases, NNIA+X1, NNIA+X2, and NNIA+X3 appear to be equal to or greater than NNIA. But for all these algorithms, the DTLZ4 problem seems to be the most difficult, since there are runs for which the Pareto front is approximated by a single, unique, point.

Table 1 shows the percentage of results showing a single point for the Pareto front of the DTLZ4 test problem when a sequence of 1000 runs is performed with each algorithm. Generally, we conclude that NNIA+X3 retains better population diversity, and its convergence is faster than NNIA for these two and three objective test problems.

NNIA-X	NNIA	NNIA+X1	NNIA+X2	NNIA+X3
2%	11%	13%	11%	0.2%

Table 1.

Percentage of results exhibiting a single point for the Pareto front of the DTLZ4 test problem when 1000 runs are carrying out.

6. Experiments on the 10 bar truss design problem

In this section, we address the multi-objective sizing optimization of truss-like structures which is a continuous subject of researches in structural design [28, 29, 30].

6.1 Problem formulation

In this study, we consider the 10 bar truss test, ketch in the Figure 3. Two objective functions have to be minimized: the mass and the displacement; and one objective function has to be maximized: the first flexible natural frequency of the structure.

Figure 3.

Sketch of the 10 bar truss.

Denoting $\mathbf{x}\in \mathrm{\Omega }$ the vector of the topological and sizing optimization parameters, such that $0\le x_i\le 1$ for $i\in \left\{1,\dots ,n\right\}$ where $n=10$ is the number of elements, the three individual objectives are:

1. The mass $w$ of the structure

$$w\left(\mathbf{x}\right)=\sum _{i=1}^n\rho {\mathit{Al}}_i{x}_i,$$

where $l_i$ is the length of the $i$-th element, $\rho =2768$ kg/m³ is the density of the material and $A=0.01419352$ m² is the element cross-section area.

1. The maximum displacement $u$ of the structure

$$u\left(\mathbf{x}\right)=max\left({\mathbf{u}}^{\ast }=arg\underset{\mathcal{S}}{min}\left(\frac{1}{2}{\mathbf{u}}^{\mathrm{T}}\mathbf{K}\left(\mathbf{x}\right)\mathbf{u}-{\mathbf{u}}^{\mathrm{T}}\mathbf{F}\right)\right),$$

where:

• $\mathbf{F}$ is the vector of loads

• $\mathbf{K}$ is the stiffness matrix of the finite element (FE) model, having the Young’ modulus $E=68.95$ GPa.

The set $\mathcal{S}$ refers to the kinematic admissible space, i.e. the one that satisfies the imposed boundary conditions given by the supports while carrying all the prescribed loads, where $P=448.2$ kN.

1. The function (minimum flexible natural frequency $f$) to maximize it

$$-f\left(\mathbf{x}\right)=-min\left(\frac{1}{2\pi }{\omega }^{\ast }\right),$$

$$\text{where}:\left\{{\omega }^{\ast 2},{\mathbf{u}}^{\ast }\right\}=arg\underset{\mathbf{u}\in \mathcal{S}}{min}\left({\omega }^2=\frac{{\mathbf{u}}^T\mathbf{K}\left(\mathbf{x}\right)\mathbf{u}}{{\mathbf{u}}^T\mathbf{M}\left(\mathbf{x}\right)\mathbf{u}}\right),‖\mathbf{u}‖\ne 0$$

where $\mathbf{M}$ is the mass matrix of the FE model².

Moreover, this MO problem is subjected to constraints for the mechanical stress ${\sigma }_i$ for each element $i$:

$$\left|{\mathit{\sigma }}_i\left(\mathbf{x}\right)\right|\le \overline{\sigma }i\in \left\{1,\dots ,n\right\}$$

where $\overline{\sigma }=172.4$ MPa is the yield strength.

As designs with local rigid body modes or kinematic modes are not of interest, constraints are added to the MO problem formulation:

$$\frac{\left|{\mathit{\sigma }}_i\left(\mathbf{x}\right)\right|}{\overline{\sigma }}>\epsilon ,i\in \left\{1,\dots ,n\right\}\text{such\hspace{0.17em}that}{x}_i>0$$

where $\epsilon =0.001$.

Since the optimal Pareto front is unknown for this problem, unnormalized metric indicators are to assess for the MO algorithm performance. Thus, in practice, we introduce an a priori scaling of the three objectives, by defining:

$$f_1\left(\mathbf{x}\right)=\frac{w\left(\mathbf{x}\right)}{\mathrm{7,000}},f_2\left(\mathbf{x}\right)=\frac{u\left(\mathbf{x}\right)-0.016}{20},f_3\left(\mathbf{x}\right)=\frac{\mathrm{22,500}-{\left(2\mathit{\pi f}\left(\mathbf{x}\right)\right)}^2}{\mathrm{5,000}}$$

Moreover, in order to handle constraints of this MO problem, we use the penalty method. This technique consists of replacing the constrained optimization problems by an optimization problems without constraints, when introducing new objective functions to be optimized:

$${\varphi }_k\left(\mathbf{x}\right)=f_k\left(\mathbf{x}\right)+\mathit{r\phi }\left(\mathbf{x}\right)$$E13

where the penalty function chosen here is:

$$\phi \left(\mathbf{x}\right)=\sum _{i=1}^n{\left(max\left\{0,\frac{\left|{\sigma }_i\left(\mathbf{x}\right)\right|}{\overline{\sigma }}-1\right\}\right)}^2+\sum _{i=1}^n{\left(max\left\{0,\epsilon -\frac{\left|{\sigma }_i\left(\mathbf{x}\right)\right|}{\overline{\sigma }}\right\}\right)}^2$$E14

and where $r$ is a positive penalty parameter. We have chosen here $r={10}^{10}$.

Finally, the MO problem definition for the 10 bar truss of this work is:

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{min}\left(f_1\left(\mathbf{x}\right)+\mathit{r\phi }\left(\mathbf{x}\right),f_2\left(\mathbf{x}\right)+\mathit{r\phi }\left(\mathbf{x}\right),f_3\left(\mathbf{x}\right)+\mathit{r\phi }\left(\mathbf{x}\right)\right)$$

6.2 Numerical simulations for two objective functions

In this subsection, we will subdivide and transform the 10 bar MO problem from the previous section into three MO subproblems. Objective functions are considered two by two: $\left(w,u\right)$, $\left(w,f\right)$_, and $\left(u,f\right)$ To solve each of these 10 bar MO problems, we use the NNIA algorithms and the NNIA+X3, keeping the parameters to those of the previous subsection 5.2.

After 250 and 750 iterations, we obtain the two Figures 4 and 5 (respectively), which show Pareto fronts of a typical execution, if the two algorithms start from the same initial population. In these figures, we observe that the NNIA+X3 algorithm shows better diversity for each subproblem, and that NNIA+X3 gives better convergence for the subproblems $\left(w,f\right)$ and $\left(u,f\right)$. Since each iteration of one of these algorithms requires $n_c=100$ evaluations of the mechanical problem, 25,000 function evaluations are performed when 250 iterations are performed, and 75,000 function evaluations are performed when 750 iterations are performed.

Figure 4.

Pareto fronts of the 10 bar truss MO problem two by two: $\left(w,u\right)$ (up-left), $\left(w,f\right)$ (up-right), $\left(u,f\right)$ (down), after 250 iterations.

Figure 5.

Pareto fronts of the 10 bar truss MO problem, after 750 iterations for two by two: $\left(w,u\right)$ (up-left), $\left(w,f\right)$ (up-right), $\left(u,f\right)$ (down).

Figure 6 shows the evolution of two metric indicators along the number of iterations for one typical run. Metric indicators chosen here are spacing and hyper-volume of Pareto fronts. Spacing evolution is presented in log-log scale in the figure. Each evaluation of the hyper-volume is achieved by using the same anti-utopia point and utopia point for results consistency. Moreover, in order to compare the three MO results on the same graph, a relative hyper-volume is plotted: the graph corresponds to the hyper-volume obtained divided by its maximum value. These graphs show a better diversity and convergence for NNIA+X3 compared with NNIA when early number of iterations are considered.

Figure 6.

Metrics indicators of the 10 bar truss MO problem for the three objectives functions two by two: spacing (up) and relative hyper-volume (down).

Tendency observed in the previous figure is confirmed by statistical results of Figure 7 and Figure 8. These figures show box plots statistic for spacing and hyper-volume (respectively) when 300 runs stopped at 250 iterations are carried out. For spacing, means and variance are clearly better for NNIA+X3. Hyper-volume statistic results are also better for the NNIA+X3 when considering the $\left(w,u\right)$ and $\left(u,f\right)$ subproblems, while they are almost identicals for the $\left(w,f\right)$ supbproblem, although the mean and variance are also better for the NNIA+X3. From results for the hyper-volume of the $\left(w,f\right)$ supbproblem, it is assessed that this subproblem is the most difficult to solve since a wide spread is observed in data for both algorithms.

Figure 7.

Statistics box plots of spacing for 300 runs of the two-by-two MO 10 bar subproblems: $\left(w,u\right)$ (left), $\left(w,f\right)$ (middle), $\left(u,f\right)$ (right).

Figure 8.

Statistics box plots of relative hyper-volume for 300 runs of the two-by-two MO 10 bar subproblems: $\left(w,u\right)$ (left), $\left(w,f\right)$ (middle), $\left(u,f\right)$ (right).

6.3 Numerical simulation for three objective functions

Figure 9 shows different views of the Pareto front obtained for one typical run when solving the three objectives 10 bar truss problem, using NNIA+X3 with the following parameter values: size of active population 30, clonal scale 150 and 750 iterations. In this case, the size of the dominant population is not limited to any number and all Pareto points found are kept. Figure 10 shows the evolution of the number of points in the dominant population for the Pareto front given in Figure 9. It ends at 2216 Pareto points for this run.

Figure 9.

Four different views of the Pareto front obtained for solving the three objective functions of the 10 bar truss problem; Colorized surface of the down-right subfigure is added for a better visualization, and the color corresponds to the frequency objective $f$.

Figure 10.

Evolution of results for a typical run of the MO 10 bar problem: Number of points for the Pareto front (left), spacing (middle), and relative hyper-volume (right); Blue line with cross markers: NNIA; Red line with squared markers: NNIA+X3.

Figure 11 shows box plot statistics when 300 runs are carried out with NNIA and NNIA+X3. It is observed that the number of points for the Pareto front is higher for NNIA+X3, with a better spacing. But the hyper-volume is better for NNIA. Detailled analysis of results has revealed that bad results for hyper-volume are due to a slow convergence to an extreme Pareto front point: the individual optima for the frequency objective. For this problem, the individual minima found for the frequency objective are most of the time better for NNIA than for NNIA+X3. However, it is also found that individual minima of the three objectives are rarely found in the Pareto front by both algorithms.

Figure 11.

Statistics box plots for 300 runs of the three objectives 10 bar problem with NNIA and NNIA+X3 with random initial population: Number of Pareto front points (left), spacing (middle), and relative hyper-volume (right).

For better results, the idea is to handle the three individual minima found by a mono-objective optimization into the random initial population of both NNIA and NNIA+X3. This simple modification greatly improves performance results. Figure 12 shows statistics box plots when 300 runs of MO problem are carried out when the three individual optima are given in the initial population. In such a situation and for each of the 300 runs done, NNIA+X3 appears to be superior to NNIA for all performance aspects, including the computed hyper-volume.

Figure 12.

Statistics box plots for 300 runs of the three objectives 10 bar problem with NNIA and NNIA+X3 when individual optima are handled in the initial population: Number of Pareto front points (left), spacing (middle), and relative hyper-volume (right).

7. Summary

This work is devoted to recombination for an NNIA algorithm. We propose three recombinations, inspired by the BSA algorithm crossing operator when adapting input populations.

In the first NNIA+X1 algorithm, the clonal population and an extended active population are concerned, when the extended active population is founded by duplicating individual antibodies.

In the second algorithm, NNIA+X2, recombination is achieved by using the clonal population and itself.

The NNIA+X3 algorithm uses the clonal population and an extended working population, which finds by duplicating individual antibodies and a proportion of random individuals. From this algorithm, a certain degree of mutation is carried out. The results obtained for the benchmark, ZDT, and DTLZ functions show that our proposed algorithm NNIA+X3 can accelerate the speed of convergence and maintain the desirable diversity, especially when solving problems with many local Pareto-optimal fronts. The experimental results of this algorithm to solve the problems of bi-objectives and three-objectives of optimization of 10 bar trellis structure indicate that the proposed NNIA+X3 surpasses the NNIA algorithm in terms of convergence rate and of course of quality of the solution.