Keywords

1 Introduction

Simulation-based design optimization (SBDO) supports the design of complex engineering systems. The process consists in the evaluation of several numerical simulations to the aim of exploring and assessing design opportunities with improved performance for a set of often conflicting objectives. Multi-objective optimization algorithms drive the search for the best compromise among all design objectives, which are generally provided in the form of Pareto solutions. In this context, objectives may be noisy and/or their derivatives are often not provided by the simulation tool. Therefore, derivative-free optimization algorithms are preferred as a viable option for the SBDO.

Global or local optimization algorithms are used, whether a fine search region is or is not known a priori. Global methods explore the whole design domain, providing approximate solutions to the decision problem. Local algorithms investigate accurately a limited domain region, also providing proof of convergence (generally not available for global methods). Hybrid global/local algorithms combine the global search capability of global methods with the accuracy and convergence properties of local algorithms. Examples of hybrid methods in the context of multi-objective optimization can be found in [1, 2].

Among other derivative-free global methods, particle swarm optimization [3] has been successfully applied in SBDO [4] and extended to hybrid global/local formulations for both single- [5, 6] and multi-objective [7,8,9,10,11,12,13] problems. Most algorithms are stochastic, requiring extensive numerical campaigns to achieve statistically significant results. Often this is not attainable in SBDO, especially if CPU-time expensive simulations provide directly objectives and constraints. Therefore, deterministic methods have been developed and assessed [4, 14].

The objective of the present work is to introduce and assess a novel multi-objective deterministic hybrid algorithm (MODHA), which combines the global exploration capabilities of multi-objective deterministic particle swarm optimization (MODPSO [14]) with the local search accuracy of a deterministic derivative-free multi-objective (DFMO [15]) linesearch method.

Six formulations are proposed, based on two MODPSO formulations [14] and three DFMO activation criteria. Two of these are based on the particle velocity and one on the hypervolume metric [16]. A comparative study is performed using 45 analytical test problems, with a number of objective functions ranging from two to three and a number of variables from one to twelve. The DFMO activation criterion is investigated along with the number of function evaluations assigned to the local search. A full-factorial combination of formulations and setting parameters is investigated through more than 14,000 optimization runs. Two multi-objective performance metrics are assessed, namely the number of solutions found and the hypervolume bounded by the solution set.

The most promising formulations are applied to the reliability-based robust design optimization (RBRDO) of a high-speed catamaran in realistic ocean environment, sailing in head waves in the North Pacific Ocean with stochastic sea state and speed [17]. A comparison with MODPSO and DFMO is provided.

2 Optimization Problem Formulation

The multi-objective minimization problem can be formulated as

$$\begin{aligned} \begin{aligned} \mathrm {minimize} ~~~~&{ \mathbf f(\mathbf{x})} = \{f_m(\mathbf{x})\}, ~~~~ \mathrm {with} ~~~~ m=1,\dots ,N_\mathrm{{of}}\\ \mathrm {subject~ to} ~~~~&z_i(\mathbf{{x}})\le 0, ~~~~ \mathrm {with} ~~~~~ i=1,\dots ,I\\ \mathrm {and~ to} ~~~~&h_j(\mathbf{{x}})=0, ~~~~ \mathrm {with} ~~~~ j=1,\dots ,J\\ \mathrm {and~ to} ~~~~&\mathbf {l}\le \mathbf {x}\le \mathbf {u} \end{aligned} \end{aligned}$$
(1)

where \(\mathbf{x} \in \mathbb {R}^{N_\mathrm{dv}}\) is the vector collecting the \(N_\mathrm{{dv}}\) variables, \(N_\mathrm{{of}}\) is the number of objective functions \({f}_{m}\), \(z_i\) are the inequality constraints, \(h_j\) are the equality constraints, and \(\mathbf {l}\) and \(\mathbf {u}\) are the lower and upper bound for \(\mathbf {x}\), respectively.

Defining the feasible solution set as \(\mathcal {X} = \{ \mathbf{x} \in \mathbb {R}^{N_\mathrm{dv}} \,\,\, | \,\,\, [\cap _i^I z_i(\mathbf{{x}})\le 0]\wedge [\cap _j^J h_j(\mathbf{{x}})=0\wedge [\mathbf{l}<\mathbf{x}<\mathbf{u}]\}\), the solution of Eq. 1 is the locus of non dominated feasible solutions represented in the variable space by the Pareto solution set \(\mathcal {PS}=\{\mathbf{x} \in \mathcal X \,\,\, | \,\,\, \mathbf{f}(\mathbf{x})\prec \mathbf{f}(\mathbf{y}), \forall \mathbf{y} \in \mathcal X \}\). In the objective function space, the locus is represented by the Pareto front \(\mathcal {PF}=\{\mathbf{f(x)} \,\,\, : \,\,\, \mathbf{x} \in \mathcal {PS} \}\). In the following, the approximate solution set \(\mathcal {S}\) (set of non dominated solutions represented either in the variable or function space) achieved by the optimizer at a specific iteration n is indicated by \(\mathcal {S}^n=\{ (\mathbf{x,s}) \, : \, \mathbf{s = f}(\mathbf{x})\prec \mathbf{f}(\mathbf{y}), \forall \mathbf{y} \}\). Similarly, the approximate Pareto front (assessed by numerical experiments and used as a reference solution set for the performance analysis) is defined as \(\mathcal {R}=\{ (\mathbf{x, r}) \in \cup _{i=1}^{N_\mathrm{s}} \mathcal {S}_i \, : \, \mathbf{r = f(x)} \prec \mathbf{f}(\mathbf{y}), \forall \mathbf{y}\}\), where \(N_\mathrm{s}\) is the number of solution sets available, provided by different algorithm formulations/setups.

3 Performance Metrics

The algorithm performance is evaluated in terms of capacity (related to the number of Pareto solutions \(\mathcal {S}\)), convergence (related to the distance between \(\mathcal {S}\) and \(\mathcal {R}\)), and diversity (related to how \(\mathcal {S}\) is wide). Here, the following two metrics are used. The Ratio of Reference Point Found (\(\mathrm {C1_R}\), [18])

$$\begin{aligned} \mathrm {C1_R} = \frac{|\mathcal {S}\cap \mathcal {R}|}{|\mathcal {R}|} \end{aligned}$$
(2)

is used as capacity metric, whereas a normalized version of the hypervolume (HV) [16] is used as a convergence-diversity metric, defined as

$$\begin{aligned} \mathrm {NHV}=\frac{\mathrm {HV}(\mathcal {S},\mathcal {R})}{\mathrm {HV}(\mathcal {R},\mathcal {R})}, ~~~ \text {with} ~~~ \mathrm {HV}(\mathcal {S},\mathcal {R})=\mathrm {volume} \left( \bigcup \limits _{i=1}^{|\mathcal {S}|} v_i \right) \end{aligned}$$
(3)

where \(\mathrm {HV}(\mathcal {S},\mathcal {R})\) gives the (hyper) volume dominated by the solution set \(\mathcal S\), evaluated using as a reference the anti-ideal point of \(\mathcal R\) [19].

Additionally, the relative variability \(\sigma _{r,k}^2\) [20] is used to assess the impact of the k-th setting parameter on the algorithm performance.

4 Hybrid Global/Local Deterministic Algorithm

The selected global and local algorithms are described in the following along with their hybridization.

4.1 MODPSO

PSO algorithm [3] is based on the social-behaviour metaphor of a flock of birds or a swarm of bees searching for food and belongs to the class of metaheuristic algorithms for single-objective derivative-free global optimization. Pinto et al. [21] proposed a multi-objective deterministic version of PSO as

$$\begin{aligned} \left\{ \begin{aligned} \mathbf {v}_{i}^{n+1}&=\chi \left[ \mathbf {v}_{i}^{n}+{{c}_{1}}\left( {{\mathbf {p}}_{i}}-\mathbf {x}_{i}^{n} \right) +{{c}_{2}}\left( {{\mathbf {g}}_i}-\mathbf {x}_{i}^{n} \right) \right] \\ \mathbf {x}_{i}^{n+1}&=\mathbf {x}_{i}^{n}+\mathbf {v}_{i}^{n+1} \\ \end{aligned} \right. \end{aligned}$$
(4)

where \({{\mathbf {v}}_{i}^n}\) and \({{\mathbf {x}}_{i}^n}\) are the velocity and the position of the i-th particle at the n-th iteration, \(\chi \) is a constriction factor, \({{c}_{1}}\) and \({{c}_{2}}\) are the cognitive and social learning rate, and \({{\mathbf {p}}_{i}}\) and \({{\mathbf {g}}_i}\) are the cognitive and social attractor.

In this work two MODPSO formulations are selected from [14], namely:

  • MODPSO1, where \({{\mathbf {p}}_{i}}\) is the closest point to the i-th particle of the personal solution set \(\mathcal {S}^n_{\mathrm{p},i}\) (i.e., the set of all non dominated solutions ever visited by the i-th particle) and \({{\mathbf {g}}_i}\) is the closest point to the i-th particle of the solution set \(\mathcal {S}^n\);

  • MODPSO3, where \({{\mathbf {p}}_{i}}\) is the personal minimizer of the aggregated objective function \(F(\mathbf{x}_i)=\sum _{m=1}^{N_\mathrm{of}} f_m(\mathbf{x}_i)\) and \({{\mathbf {g}}_i}\) is the closest point to the i-th particle of the solution set \(\mathcal {S}^n\).

4.2 DFMO

It is a derivative-free algorithm for constrained (possibly) non-smooth multi-objective problems [15], representing a so-called “a posteriori” method in the sense that it is able to approximate the entire \(\mathcal {PF}\) by producing in output a set of non dominated points. More in particular, at every iteration, the algorithm produces (or updates) a set of non dominated points (rather than a single point, as it is common in the single-objective case). As the iteration count grows, these sets of points tend to the \(\mathcal {PF}\) of the problem.

Other relevant features of DFMO are: (i) a linesearch approach that takes into account the presence of multiple objectives; (ii) an exact penalty approach for dealing with the nonlinear constraints. At each iteration, for each point in \(\mathcal {S}\), DFMO starts a linesearch along a suitably generated direction \(d_j\). If such a direction is able to guarantee “sufficient” decrease, then a “sufficiently” large movement \(\lambda \) along the direction is performed. This allows to (possibly) improve \(\mathcal {S}\). Detail of algorithm formulation and implementation can be found in [15].

4.3 MODHA

A critical issue when combining MODPSO and DFMO is to define when and where from the local search starts. Here, three approaches are defined: two are based on the velocity of the particle and one on the HV metric.

The velocity-based formulation starts a local search if the normalized speed of the i-th particle drops under a threshold value \(\beta \), namely when \(\left| \left| \mathbf{v}_i\right| \right| /\left| \left| (\mathbf{u}-\mathbf{l})\right| \right| < \beta \). The local search starts either from the current particle position (PP) or from the particle social attractor (SA). The hypervolume-based formulation starts the local search from each point of the current solution set (SS) if \(\mathrm {HV}(\mathcal {S}^n,\mathcal {S}^n) < \gamma \mathrm {HV}(\mathcal {S}^{n-1},\mathcal {S}^n)\). \(\mathrm {HV}(\mathcal {S}^n,\mathcal {S}^n)\) is the hypervolume associated to \(\mathcal {S}^n\), \(\gamma \) is the threshold coefficient, and \(\mathrm {HV}(\mathcal {S}^{n-1},\mathcal {S}^n)\) is the hypervolume associated to \(\mathcal {S}^{n-1}\).

The number of problem evaluations (\(N_\mathrm{DFMO}\)) performed at each call of the local algorithm is defined as \(N_\mathrm{DFMO}=\alpha N_\mathrm{dv}N_\mathrm{of}\) and \(N_\mathrm{DFMO}=\alpha N_\mathrm{p}\) for velocity- and hypervolume-based formulations, respectively. Algorithm 1 shows the pseudo code for the current hybrid formulations.

figure a

4.4 Algorithm Parameters and Setup

The MODPSO1 and MODPSO3 setups are defined as in [14]. The number of particles \(N_\mathrm{p}\) is set to \(8N_\mathrm{of} N_\mathrm{dv}\), initialized using a Hammersley sequence sampling [22] over variable domain and boundary. The coefficients are set as proposed by Clerc [23], with \(\chi =0.721\) and \(c_1=c_2=1.655\). A semi-elastic wall-type approach is used for box constraints [4].

Threshold values for local search activation are set to \(\beta =\{0.1, 1.0, 10\}\) and \(\gamma =\{1.0, 1.1, 1.2\}\). The budget of local search evaluations (for each call) is set by \(\alpha =\{1, 5, 10\}\). The linesearch step is reduced by a factor of two until it reaches a minimum step size \(\lambda _{\min }=1\)E − 9, starting from a maximum value equal to the 10% of the design variables space dimension.

The number of problem evaluations (\(N_\mathrm{peval}\)), where one problem evaluation involves one evaluation of each objective function, is assessed by \(N_\mathrm{peval}=\nu N_\mathrm{of}N_\mathrm{dv}\) where \(\nu =125\cdot 2^c, ~ c\in \mathbb {N}[0,4]\) therefore \({{N}_\mathrm{peval}}\) ranges between \(125N_\mathrm{of}N_\mathrm{dv}\) and \(2000N_\mathrm{of}N_\mathrm{dv}\).

5 Numerical Results

A preliminary study on analytical benchmark problems is used to identify the most promising MODHA formulation and setup. The MODHA formulations under analysis are summarized in the following:

  • PP1 and PP3 perform \(\alpha N_\mathrm{dv}N_\mathrm{of}\) local search for each call, starting from the current particle position \(\mathbf {x}_i^n\), and are activated by the velocity threshold \(\beta \);

  • SA1 and SA3 perform \(\alpha N_\mathrm{dv}N_\mathrm{of}\) local search for each call, starting from the particle social attractor \(\mathbf {g}_i\), and are activated by the velocity threshold \(\beta \);

  • SS1 and SS3 perform \(\alpha N_\mathrm{p}\) local search for each call, starting from the current solution set \(\mathcal {S}^n\), and are activated by the HV threshold value \(\gamma \).

“1” and “3” indicate the MODPSO formulation. The most promising MODHA formulations are finally applied to the RBRDO of the high-speed catamaran and compared with MODPSO1, MODPSO3, and DFMO.

5.1 Analytical Benchmark Problems

A number of 45 benchmark problems [14] is used, including convex and non-convex, continuous and discontinuous Pareto fronts, with \({{N}_\mathrm{of}}=2\), 3 and \(1\le N_\mathrm{dv}\le 12\).

In order to provide a proper comparison between different problems with different codomain size, each solution set \(\mathcal {S}\) is normalized with the function range, therefore \(\mathbf{s}_i\in [0,1]\) and the reference point HV is \(\{1\}_{i=1}^{N_\mathrm{of}}\). The computation of HV is performed with the code provided in [24].

Figure 1 shows the relative variability of \(\mathrm {C1_R}\) and NHV, conditional to the setup parameters. Considering both metrics, the velocity-based formulations (PP1, PP3, SA1, and SA3) are mainly affected by the velocity threshold \(\beta \), whereas the hypervolume-based formulation is mainly influenced by the coefficient \(\alpha \), but SS3.

Fig. 1.
figure 1

Analytical test problems, relative variability \(\sigma ^2_{r,k}\) conditional to the formulation parameters

Full size image
Fig. 2.
figure 2

Analytical test problems, comparison of MODPSO1, MODPSO3, DFMO, and most promising setup of MODHA formulations

Full size image

Figure 2 compares \(\mathrm {C1_R}\) and NHV provided by global, local, and hybrid global/local algorithms. Although DFMO achieves the highest \(\mathrm {C1_R}\), hybrid methods provide significantly larger NHV values. In general, within the same hybridization approach, MODPSO1 and MODPSO3 achieve similar performances. It is worth noting that the velocity-based hybrid formulation, that start the local search from the current particle position (PP1 and PP3), are not able to outperform the corresponding global algorithms.

Table 1 summarizes the most promising setup for each hybrid formulation, based on budget-averaged NHV. MODHA-SS3 with an activation threshold \(\gamma =1.0\) and a coefficient \(\alpha =10\) for the DFMO problem evaluations is the best performing overall (on average).

Table 1. Most promising MODHA setup based on budget-averaged NHV
Full size table

Finally, Fig. 3 shows illustrative examples of the solution achieved by global, local, and hybrid (SS1 and SS3) algorithms for the Sch1 problem [25] with \(N_\mathrm{of}=2\) and \(N_\mathrm{dv}=1\). The hybrid algorithms show a more accurate approximation of the Pareto front than local and global algorithms.

Fig. 3.
figure 3

Global, local, and hybrid algorithm solution for the Sch1 problem with \(2000N_\mathrm{of}N_\mathrm{dv}\) problem evaluations

Full size image

5.2 High-Speed Catamaran Optimization

A reliability-based robust design optimization of a 100 m high-speed catamaran is solved for realistic conditions, associated to the North Pacific Ocean including stochastic sea state and speed [17]. The multi-objective problem aims at the reduction of the expected value of the mean total resistance in irregular waves (\(\varphi _1\)) and the increase of the ship operability referring to a set of motion-related constraints (\(\varphi _2\)). The design optimization problem is formulated as

$$\begin{aligned} \begin{aligned} \mathrm{minimize}&\,\,\,\,\,\,\, \{\varphi _1(\mathbf {x}),\,-\varphi _2(\mathbf {x})\}^T\\ \mathrm{subject \, to}&\,\,\,\,\,\,\, \mathbf {l}\le \mathbf {x}\le \mathbf {u}\\ \mathrm {\,and\,\,\, to}&\,\,\,\,\,\,\, {{\varphi }_{1}} \le 0; \,\,\, {{\varphi }_{2}}\ge 0 \end{aligned} \end{aligned}$$
(5)

The problem is solved by means of stochastic radial-basis function interpolation [26] of high-fidelity URANS simulations. The inequalities in Eq. 5 are handled by a linear penalty function, so that \(\varphi _{k}=\varphi _{k}+100\sum ^{N_{dv}}_{j=1} \max (x_j-u_j,0)+100\sum ^{N_{dv}}_{j=1}|\min (l_j-x_j,0)|\) if domain bounds violation occurs and \(\varphi _{k}=10000\varphi _{k}\) if \(\varphi _{1}>0\) or \(\varphi _{2}<0\). Four design variables (\(N_\mathrm{dv}=4\)) control global shape modifications of the catamaran hull, based on the Karhunen-Loève expansion of the shape modification vector. Details may be found in [17]. A total number of 16,000 problem evaluations are performed and used to compute the reference non dominated solution set \(\mathcal {R}\).

Fig. 4.
figure 4

Global, local, and hybrid algorithm solution for the catamaran problem with \(2000N_\mathrm{of}N_\mathrm{dv}\) problem evaluations

Full size image

Figure 4 shows the solution obtained by MODPSO1 and 3, DFMO, and the hybrid algorithms SS1 and SS3 with the most promising parameter set summarized in Table 1. The hybrid algorithms are able to cover the reference solution, outperforming the global and local algorithms. It is worth noting that the hybrid algorithms are able to accurately identify the upper right section of \(\mathcal {R}\). The solution provided by SS3 is more accurate than that provided by SS1.

Table 2 summarizes \(\mathrm {C1_R}\) and NHV percentage values achieved by each algorithm, conditional to the budget parameter \(\nu \). Both metrics confirm the results depicted in Fig. 4. The hybrid algorithms perform better than the global and local algorithms and provide more dense solutions. In particular, SS3 is found to be the best formulation, achieving higher values of \(\mathrm {C1_R}\) and NHV and providing more dense solutions than SS1.

Table 2. Catamaran problem, summary of the optimization results
Full size table

6 Conclusions and Future Work

A multi-objective deterministic hybrid algorithm (MODHA) has been presented, combing two multi-objective deterministic particle swarm formulations with a local derivative-free multi-objective linesearch algorithm. Three hybridization schemes have been studied: two are based on the particle velocity and one on the hypervolume metric. The velocity-based formulation starts the local search when the particle velocity drops under a threshold value (\(\beta \)) and use as a starting point either the current particle position (PP) or the particles social attractor (SA). The hypervolume-based formulation starts the local search when the HV associated to the current solution set does not improve sufficiently (by a factor equal to \(\gamma \)) compared to the previous iteration. In this case, a local search is performed starting from each point of the current solution set (SS). These hybridization schemes are combined to both MODPSO1 and MODPSO3, resulting in six MODHA formulations.

A comparative study has been performed using 45 analytical test problems, with a number of objective functions ranging from two to three and a number of variables from one to twelve, varying the activation criterion and the number of problem evaluations for the local search. A full-factorial combination of formulations and parameters has been investigated through more than 14,000 optimization runs. Two multi-objective performance metrics (\(\mathrm {C1_R}\) and NHV) have been evaluated and discussed.

Velocity-based formulations depend significantly on the local search activation threshold, whereas the hypervolume-based formulation is affected mainly by the coefficient related to the number of evaluations reserved for the local search. Hybrid formulations based on the hypervolume show the best performance. Specifically, MODHA-SS3 with \(\alpha =10\) and \(\gamma =1.0\) is found the most promising on average. Hypervolume formulations have been applied to the hull-form optimization of a high-speed catamaran (aimed at reducing the resistance and increasing the operability in realistic ocean conditions), showing better results than global and local algorithms. Also for the catamaran, MODHA-SS3 provides the best performance.

Current results are promising and motivate further investigations of metrics-based formulations, with focus on the method for the selection of local search starting points. Future work includes the development and assessment of a hybrid version of the crowding-distance based MOPSO [27] and the use of the crowding distance to select the local search starting points. The effects of the local search stop criterion on the overall performance will be included in the analysis. Finally, novel strategies for the approximation of the Pareto front (e.g. [28]) will be considered to enhance the exploration capabilities of the MODHA formulations.