1 Introduction

Multi-Agent Collaborative Search (MACS) has been proposed as a framework for the implementation of hybrid, population-based, approaches for multi-objective optimization [20]. In this framework a number of heuristics are blended together in order to achieve a balanced global and local exploration. In particular, the search for Pareto optimal solutions is carried out by a population of agents implementing a combination of social and individualistic actions. An external archive is then used to reconstruct the Pareto optimal set.

The individualistic actions are devised to allow each agent to independently converge to the Pareto optimal set, thus creating its own partial representation of the Pareto front. Therefore, they can be regarded as memetic mechanisms associated to a single individual. The effectiveness of the use of local moves was recently demonstrated by Schuetze et al. [14]; Lara et al. [7] who proposed innovative local search mechanisms based on mathematical programming.

Other examples of memetic algorithms for multi-objective optimization use local sampling [5] or gradient-based methods [1–4, 6, 12, 16], generally building a scalar function to be minimized or hybridizing an evolutionary algorithm with a Normal Boundary Intersection (NBI) technique. The schedule with which the local search is run is critical and defines the efficiency of the algorithm.

MACS has been applied to a number of standard problems and real applications with good results, if compared to existing algorithms [10, 13, 18, 21]. The algorithm proposed in this paper is a novel version of Multi-Agent Collaborative Search, for multi-objective optimization problems, that implements some key elements of innovation. Most of the search mechanisms have been simplified but more importantly in this version Pareto dominance is not the only criterion used to rank and select the outcomes of each action. Instead, agents are using Tchebycheff decomposition to solve a number of single objective optimization problems in parallel. Furthermore, opposite to previous implementations of MACS, here all agents perform individualistic actions while social actions are performed only by selected sub-populations of agents.

Recent work by Zhang and Li [25] has demonstrated that Tchebycheff decomposition can be effectively used to solve difficult multi-objective optimization problems. Another recent example is Sindhya et al. [16] that uses Tchebycheff scalarization to introduce a local search mechanisms in NSGA-II. In this paper, it will be demonstrated how MACS based on Tchebycheff decomposition can achieve very good results on a number of cases, improving over previous implementations and state-of-the-art multi-objective optimization (MOO) algorithms.

The new algorithm is here applied to a set of known standard test cases and to two space mission design problems. The space mission design cases consider spacecraft equipped with a chemical engine and performing a multi-impulse transfer. They are part of a test benchmark for multi-impulsive problems that has been extensively studied in the single objective case but for which only a few comparative studies exist in the multi-objective case [11].

The paper is organized as follows: section two contains the general formulation of the problem with a brief introduction to Tchebycheff decomposition, the third section starts with a general introduction to the multi-agent collaborative search algorithm and heuristics before going into some of the implementation details. Section four contains a set of comparative tests that demonstrates the effectiveness of the new heuristics implemented in MACS. The section briefly introduces the performance metrics and ends with the results of the comparison.

2 Problem formulation

The focus of this paper is on finding the feasible set of solutions that solves the following problem:

$$ \min_{\mathbf{x}\in D} \mathbf{f}(\mathbf{x)} $$
(1)

where D is a hyperrectangle defined as \(D = \lbrace x_{j} \mid x_{j} \in[b_{j}^{l}\ b_{j}^{u}] \subseteq \mathbb {R}, j=1,\ldots,n \rbrace\) and f is the vector function:

$$ \mathbf{f}:D \rightarrow \mathbb {R}^m,\quad \mathbf{f}(\mathbf{x)}=\bigl[f_1(\mathbf{x}),f_2( \mathbf{x}),\ldots,f_m(\mathbf{x})\bigr]^T $$
(2)

The optimality of a particular solution is defined through the concept of dominance: with reference to problem (1), a vector y∈D is dominated by a vector x∈D if f l (x)≤f l (y) for all l=1,…,m and there exists k so that f k (x)≠f k (y). The relation x≺y states that x dominates y. A decision vector in D that is not dominated by any other vector in D is said to be Pareto optimal. All non-dominated decision vectors in D form the Pareto set D P and the corresponding image in criteria space is the Pareto front

Starting from the concept of dominance, it is possible to associate, to each solution in a finite set of solutions, the scalar dominance index:

$$ I_d(\textbf{x}_i)=\bigl| \bigl\{i^{*}\bigm{|} i, i^{*}\in N_p \wedge\textbf{x}_{i^{*}}\prec \textbf{x}_i\bigr\}\bigr| $$
(3)

where the symbol |.| is used to denote the cardinality of a set and N p is the set of the indices of all the solutions. All non-dominated and feasible solutions x i ∈D with i∈N p form the set:

$$ X=\bigl\{\textbf{x}_i\in D \mid I_d(\textbf{x}_i)=0\bigr\} $$
(4)

The set X is a subset of D P , therefore, the solution of problem (1) translates into finding the elements of X. If D P is made of a collection of compact sets of finite measure in \(\mathbb {R}^{n}\), then once an element of X is identified it makes sense to explore its neighborhood to look for other elements of X. On the other hand, the set of non dominated solutions can be disconnected and its elements can form islands in D. Hence, multiple parallel exploration can increase the collection of elements of X.

2.1 Tchebycheff decomposition

In Tchebycheff’ approach to the solution of problem (1), a number of scalar optimization problems are solved in the form:

$$ \min_{\mathbf{x}\in D} g\bigl( \mathbf{f}(\mathbf{x}),\mathbf{\lambda},\mathbf{z}\bigr)=\min _{\mathbf{x}\in D} \max_{l=1,\ldots,m} \bigl\{\lambda _l|f_l(\mathbf{x})-z_l|\bigr\} $$
(5)

where z=[z 1,…,z m ]T is the reference objective vector whose components are z l =min x∈D f l (x), for l=1,…,m, and λ l is the l-th component of the weight vector \(\mathbf{\lambda}\). By solving a number of problems (5), with different weight vectors, one can obtain different Pareto optimal solutions. Although the final goal is always to find the set X, using the solution of problem (5) or index (3) has substantially different consequences in the way samples are generated and selected. In the following, the solution to problem (5) will be used as selection criterion in combination with index (3).

3 MACS with Tchebycheff decomposition

The key idea underneath multi-agent collaborative search is to combine local and global search in a coordinated way such that local convergence is improved while retaining global exploration [19]. This combination of local and global search is achieved by endowing a set of agents with a repertoire of actions producing either the sampling of the whole search space or the exploration of a neighborhood of each agent. Actions are classified into two categories: social, or collaborative, and individualistic. In this section, the key heuristics underneath MACS will be described in details. Compared to previous implementations of MACS [20], this paper proposes a number of key innovations. First of all, Tchebycheff decomposition is used in combination with dominance-based ranking to accept the outcome of an action. The idea is that each agent can either try to improve its dominance index or can try to improve one particular objective function by working on a subproblem characterized by a subset of weights λ. This combination extends the accepted individualistic moves and improves the spreading of the solutions in the criteria space. The second innovation comes from an inversion of the policy to schedule individualistic and social actions. In previous implementations the whole population was participating in the implementation of social actions at every generation, while an elite of agents was implementing individualistic actions. In this paper, this policy is inverted and now all the agents perform individualistic actions while selected subpopulations perform social actions either with other agents in the current population or with elements in the archive. This inversion is quite significant as it translates into a parallel local search performed by the whole population at each iteration, rather than having the local search performed by a selected number of individuals at a particular time of the evolution. More specific heuristics are described in the next sections.

The use of either dominance or Tchebycheff scalarization leads to the selection of different outcomes of the actions executed by the agents. With reference to Fig. 1(a) the dominance criterion can be used to select a displacement of agent x in the dominating region. In this case only strongly dominant solutions are accepted as admissible for a displacement of agent x. Tchebycheff scalarization, instead, allows for movements in the region of decreasing g(x) in Fig. 1(a).

Fig. 1
figure 1

Selection criteria

Full size image

This region extends the dominating region of Fig. 1(a) and includes part of the non-dominating region. Therefore, Tchebycheff scalarization, as defined in (5) allows for the selection of weakly efficient solutions. If λ is kept constant the agent would progressively try to align along the direction ζ (see Fig. 1(b)). The rectilinear line ζ divides the criteria space in Fig. 1(b) in two half-planes, one, below ζ, where λ 1|f 1(x)−z 1|>λ 2|f 2(x)−z 2|, the other, above ζ, where λ 1|f 1(x)−z 1|<λ 2|f 2(x)−z 2|. The rectilinear line ζ is, therefore, the locus of points, in the criteria space, for which λ 1|f 1(x)−z 1|=λ 2|f 2(x)−z 2|. Figure 1(b) shows that by solving problem (5) one would take displacements in any direction that improves f 1, starting from a solution that is under the ζ line. If one of these displacements crosses the ζ line, the solution of problem (5) would then generate displacements that improve f 2. This mechanisms allows for the generation of dominating steps (see Fig. 1(c)) as well as side steps (see Fig. 1(d)). Side steps are important to move along the Pareto front (see [7] for more details on the effect of side steps). In MACS side steps were generated by accepting displacements in the non-dominating regions of Fig. 1(a) when no dominant solutions were available. In MACS2 instead side steps are generated by selecting displacements according to Tchebycheff scalarization when strongly dominant solutions are not available. Note however, that although displacements are computed considering a combination of strong dominance and Tchebycheff scalarization, the archive is filled with all the solutions that have dominance index I d =0 and a large reciprocal distance (see Sect. 3.4).

3.1 General algorithm description

A population P 0 of n pop virtual agents, one for each solution vector x i , with i=1,…,n pop , is deployed in the problem domain D, and is evolved according to Algorithm 1.

Algorithm 1
figure 2

MACS2

Full size image

The population P h at iteration h=0 is initialized using a Latin Hypercube distribution. Each agent then evaluates the associated objective vector f i =f(x i ) and all non-dominated agents are cloned and inserted in the global archive A g (lines 4 and 5 in Algorithm 1). The archive A g contains the current best estimation of the target set X. The q-th element of the archive is the vector \(\mathbf{a}_{q}=[\mathbf {\xi }_{q}\ \mathbf{\phi}_{q}]^{T}\) where \(\mathbf{\xi}_{q}\) is a vector in the parameter space and \(\mathbf{\phi}_{q}\) is a vector in the criteria space.

Each agent is associated to a neighborhood \(D_{\rho_{i}}\) with size ρ i . The size ρ i is initially set to 1, i.e. representing the entire domain D (line 6 in Algorithm 1).

A set of n λ , m-dimensional unit vectors \(\mathbf{\lambda }_{k}\) is initialized such that the first m vectors are mutually orthogonal. The remaining n λ −m have random components instead. In two dimensions the vectors are initialized with a uniform sampling on a unit circle and in three dimensions with a uniform sampling on a unit sphere, while in n-dimensions with a Latin Hypercube sampling plus normalization, such that the length of each vector is 1 (see line 7 in Algorithm 1). For each vector \(\mathbf{\lambda}_{k}\), the value of an associated utility function U k is set to 1 (see line 8 in Algorithm 1). The utility function is the one defined in [28] and its value is updated every u iter iterations using Algorithm 5. In this work it was decided to maintain the exact definition and settings of the utility function as can be found in [28], the interested reader can therefore refer to [28] for further details.

Each \(\mathbf{\lambda}_{k}\) represents a subproblem in Eq. (5), i.e. it is used to compute the scalar function g k . A total of n social =round(ρ pop n pop ) λ vectors are inserted in the index set I a . The first m indexes in I a correspond to the m orthogonal λ vectors, the other n social −m are initially chosen randomly (line 9 of Algorithm 1).

Each \(\mathbf{\lambda}_{k}\) for k=1,…,n λ is associated to the element in A g that minimizes g k such that:

$$ \underline{\phi}_k= \mathop {\mathrm {arg\,min}}_{\phi_q}g(\phi_q,\lambda_k,\mathbf{z}) $$
(6)

where z is the vector containing the minimum values of each of the objective functions. Then, for each \(\mathbf{\lambda}_{l}\), with l∈I a and associated vector \(\underline{\phi}_{l}\), a social agent x q is selected from the current population P h such that it minimizes g(f q ,λ l ,z). The indexes of all the selected social agents are inserted in the index set I λ (see lines 14 to 17 in Algorithm 1). The indexes in I a and I λ are updated every u iter iterations.

At the h-th iteration, the population P h is evolved through two sets of heuristics: first, every agent x i performs a set of individualistic actions which aims at exploring a neighborhood \(D_{\rho_{i}}\) of x i (line 20 of Algorithm 1), the function explore described in Algorithm 2 is used to implement individualistic actions. All the samples collected during the execution of individualistic actions are stored in the local archive A l . The elements of A l and the outcome of social actions are inserted in the global archive A g if they are not dominated by any element of A g (line 22 in Algorithm 1).

Algorithm 2
figure 3

explore—Individualistic Actions

Full size image

Then, a sub-population I λ of n social selected social agents performs a set of social actions (see line 23 of Algorithm 1). Social actions aim at sharing information among agents. More details about individualistic and social actions are provided in the following sections. The function com described in Algorithm 3 is used to implement social actions.

Algorithm 3
figure 4

com—Social Actions

Full size image

At the end of each iteration the global archive A g is resized if its size has grown larger than n A,max (line 25 in Algorithm 1). The resizing is performed by function resize described in Algorithm 4.

Algorithm 4
figure 5

resize—Archive Resizing

Full size image

The value n A,max was selected to be the largest number between 1.5n λ and 1.5n A,out , where n A,out is the desired number of Pareto optimal elements in A g at the last iteration. This resizing of the archive is done in order to reduce the computational burden required by operations like the computation of the dominance index. It also provides an improved distribution of the solutions along the Pareto front as it discards solutions that are excessively cluttered.

At the end of each iteration the algorithm also checks if the maximum number of function evaluations n feval,max , defined by the user, has been reached and if so, the algorithm terminates. At termination, the archive A g is resized to n A,out if its cardinality is bigger than n A,out .

3.2 Individualistic actions

Individualistic actions perform an independent exploration of the neighborhood \(D_{\rho_{i}}\) of each agent. As in the original version of MACS [18] the neighborhood is progressively resized so that the exploration is over the entire D when the size ρ i is equal to 1 and becomes progressively more and more local as the neighborhood shrinks down. In this new implementation of MACS each agent performs only a simple sampling along the coordinates. The neighborhood \(D_{\rho_{i}}\) is a hypercube centered in x i with size defined by ρ i such that each edge of the hypercube has length ρ i (b u−b l). Algorithm 2 describes individualistic actions.

The search is performed along a single component of x i at a time, in a random order: given an agent x i , a sample y + is taken within \(D_{\rho_{i}}\) along the j-th coordinate with random step size \(r\in\mathcal{U}(-1,1)\), where \(\mathcal{U}(-1,1)\) is a uniform distribution over the closed interval [−1 1], leaving the other components unchanged. If y + dominates x i , y + replaces x i , otherwise another sample y − is taken in the opposite direction with step size rr, with \(rr\in\mathcal {U}(0,1)\). Again, if y − dominates x i , y − replaces x i . If y i is not dominating and is not dominated by x i and the index i of x i belongs to I λ , then y i replaces x i if y i improves the value of the subproblem associated to x i . Whether a dominant sample or a sample that improves the value of the subproblem is generated the exploration terminates. This is a key innovation that exploits Tchebycheff decomposition and allows the agents to perform moves that improve one objective function at the time. The search terminates also when all the components of x i have been examined, even if all the generated samples are dominated (see Algorithm 2 lines 3 to 40).

If all children are dominated by their parent, the size of the neighborhood ρ i is reduced by a factor η ρ . Finally, if ρ i is smaller than a tolerance tol conv , it is reset to 1 (see Algorithm 2 lines 41 to 46). In all the tests in this paper η ρ was taken equal to 0.5 as this value provided good results, on average, across all test cases.

All the non-dominated children generated by each agent x i during the exploration form the local archive A l,i . The elements of A l,i are inserted in the global archive A g if they are not dominated by any element in A g .

3.3 Social actions

Social actions are performed by each agent whose index is in the set I λ . Social actions are meant to improve the subproblem defined by the weight vectors \(\mathbf{\lambda}_{k}\) in I a and associated to the agents x i in I λ . This is done by exploiting the information carried by either the other agents in the population P h or the elements in the archive A g . Social actions implement the Differential Evolution (DE) heuristic:

$$ \mathbf{y}_i=\mathbf{x}_i+K \bigl[(\mathbf{s}_{1}-\mathbf{x}_i)+F(\mathbf {s}_{2}-\mathbf{s}_{3})\bigr] $$
(7)

where the vectors s l , with l=1,…,3, are randomly taken from the local social network I T of each social agent x i . The local social network is formed by either the n social agents closest to x i or the n social elements of A g closest to x i . The probability of choosing the archive vs. the population is directly proportional to p AvsP (see line 3 of Algorithm 3). The parameter p AvsP is defined as \(1-e^{-|A_{g}|/n_{social}}\). This means that in the limit case in which the archive is empty, the population is always selected. On the other hand, if the archive is much larger than the population, it is more likely to be selected. Note that, if the size of A g is below 3 elements, then the population is automatically chosen instead (line 4 of Algorithm 3) as the minimum number of elements to form the step in (7) is 3. The offspring y i replaces x i if it improves the subproblem associated to x i otherwise y i is added to the archive A g if it is not dominated by any of the elements of A g . The value of F in this implementation is 0.9. Social actions, described in Algorithm 3, dramatically improve the convergence speed once a promising basin of attraction has been identified. On the other hand, in some cases social actions lead to a collapse of the subpopulation of social agents in one or more single points. This is in line with the convergence behavior of DE dynamics presented in [24]. This drawback is partially mitigated by the remaining agents which perform only individualistic actions. Algorithm 3 implements social actions.

3.4 Archive resizing

If the size of A g exceeds a specified value (as detailed in Sect. 3.1), a resizing procedure is initiated. The resizing procedure progressively selects elements from the current archive and adds them to the resized archive until its specified maximum size n A,max is reached. First, the normalized Euclidean distances, in the objective space, between all the elements of the current archive are computed (lines 3–8 of Algorithm 4). Then the l-th element minimizing the l-th objective function, with l=1,…,m, is inserted in the resized archive (lines 9 to 12 of Algorithm 4). The remaining n A,max −m elements are iteratively selected by considering each time the element of the current archive (excluding those which are already in the resized one) which has the largest distance from its closet element in the resized archive (lines 13 to 17 of Algorithm 4). This procedure provides a good uniformity in the distribution of samples. Future work will investigate the comparative performance of different archiving strategies like the one proposed in [8] and [15].

3.5 Subproblem selection

Every u iter iterations the active subproblems in I a and the associated agents in I λ performing social actions are updated. The agents performing social actions are updated through function select described in Algorithm 5.

Algorithm 5
figure 6

select—Subproblem Selection

Full size image

The improvement γ between \(\underline{\mathbf{\phi}}_{k}\) (i.e. the best value of g k at current iteration in the global archive) and \(\underline{\mathbf{\phi}}_{old,k}\) (the best value of g k , u iter iterations before) is calculated. Then, the utility function U k associated to \(\mathbf{\lambda}_{k}\) is updated according to the rule described in [28] and reported in Algorithm 5, lines 2 to 10.

Once a value U k is associated to each \(\mathbf{\lambda}_{k}\), n social new subproblems and associated λ vectors are selected. The first m λ vectors are always the orthogonal ones. The remaining n social −m are selected by taking t size =round(n λ /60) random indexes and then choosing the one with the largest value of U k . This is repeated till I a is full (see lines 11 to 17 in Algorithm 5). Note that t size cannot exceed the size of I tmp in Algorithm 5 if the number of social agents n social is small compared to n λ

Finally, the agent x i , that minimizes the scalar objective function in Eq. (5) is associated to each \(\mathbf {\lambda}_{k}\) with index in I a , and its index is included in the new subset I λ (lines 18 to 21 in Algorithm 5).

4 Experimental results

The new implementation of MACS is here called MACS2. This section presents the performance of MACS2 on a standard benchmark for multi-objective optimization algorithms and on some space-related test cases. Through an experimental analysis an optimal settings for MACS2 is derived. The results obtained with MACS2 will also be compared with those of MACS and other known multi-objective optimization algorithms [26]. The standard benchmark problems aim at optimizing the UF1-10 functions in the CEC09 test suite [27] and the test instances ZDT2, ZDT4, ZDT6 [29]. UF1 to UF7 are bi-objective test functions with 30 optimization parameters. UF8 to UF10 are tri-objective functions, again with 30 optimization parameters. The CEC09 competition rules specified 300000 function evaluations and 100 and 150 elements for the output Pareto fronts for the bi- and tri-objective functions respectively. ZDT2 ZDT4 and ZDT6 are bi-objective test cases with 30 parameters for the first one and 10 for the remaining two. They are tested running the algorithm for 25000 evaluations and taking an output front of 200 elements. The space-related test instances are given by two trajectory optimization problems as described in [11, 21]. The former is a 3-impulse transfer between a circular Low Earth Orbit (LEO) with radius r 0=7000 km to a Geostationary Orbit (GEO) with radius r f =42000 km. The latter test case, Cassini, describes a trajectory optimization instance from Earth to Jupiter with four intermediate gravity assists at Venus (twice), Earth and Jupiter respectively. For both test cases the objective functions to be minimized are total ΔV and time of flight. The 3-impulse test case has 5 optimization parameters and is run for 30000 function evaluations while Cassini has 6 parameters and is run for 600000 evaluations as it was demonstrated, in the single objective case, to have multiple nested local minima with a funnel structure [24]. The metrics which will be used in order to evaluate the performance of the algorithms are chosen so to have a direct comparison of the results in this paper with those in previous works. Therefore, for the CEC09 test set the IGD performance metric will be used [27]:

$$ \mathit{IGD}\bigl(A,P^{*}\bigr)=\frac {1}{|P^{*}|}\sum _{\mathbf{v}\in P^{*}}{\min_{\mathbf{a}\in A}\|\mathbf{v}-\mathbf{a}\|} $$
(8)

where P ∗ is a set of equispaced points on the true Pareto front, in the objective space, while A is the set of points from the approximation of the Pareto front. As in [27], performance will be assessed as mean and standard deviation of the IGD over 30 independent runs. Note that a second batch of tests was performed taking 200 independent runs but the value of the IGD was providing similar indications. For the ZDT test set and for the space problems, the success rate on the convergence M conv and spreading M spr metrics are used instead. Note that, the IGD metric has been preferred for the UF test problems in order to keep consistency with the results presented in the CEC’09 competition. Convergence and spreading are defined as:

$$ M_{conv}=\frac{1}{|A|}\sum _{\mathbf{a}\in A}\min_{\mathbf{v}\in P^{*}}\biggl\| \frac{\mathbf {v}-\mathbf{a}}{\mathbf{\delta}}\biggr\| $$
(9)
$$ M_{spr}=\frac{1}{|P^{*}|}\sum _{\mathbf{v}\in P^{*}}\min_{\mathbf{a}\in A}\biggl\| \frac{\mathbf {v}-\mathbf{a}}{\mathbf{\delta}}\biggr\| $$
(10)

with \(\mathbf{\delta}=\max_{i}{\mathbf{a}_{f,i}}-\min_{i}{\mathbf {a}_{f,i}}\). It is clear that M spr is the IGD but with the solution difference, in objective space, normalized with respect to the exact (or best-so-far) solution. In the case of the ZDT test set, the two objective functions range from 0 to 1, therefore no normalization is required and M spr is in fact the IGD. The success rates for M conv and M spr is defined as p conv =P(M conv <τ conv ) and p spr =P(M spr <τ spr ) respectively, or the probability that the indexes M conv and M spr achieve a value less than the threshold τ conv and τ spr respectively. The success rates p conv and p spr are computed over 200 independent runs, hence they account for the number of times M conv and M spr are below their respective thresholds. According to the theory developed in [11, 23], 200 runs provide a 5 % error interval with a 95 % confidence level. Values for thresholds for each test case are reported in Table 1.

Table 1 Convergence tolerances
Full size table

MACS2 was initially set with a some arbitrary values reported in Table 2. The size of the population was set to 60 for all the test cases except for the 3-impulse and ZDT functions. For these test cases the number of agents was set to 30. In the following, these values will identify the reference settings.

Table 2 Reference settings for MACS2. Values within parenthesis are for 3-impulse and ZDT test cases
Full size table

Starting from this reference settings a number of tuning experiments were run to investigate the reciprocal influence of different parameters and different heuristics within the algorithm. Different combinations of n pop , ρ pop , F and Tol conv were considered. Furthermore, the social moves were activated or de-activated to assess their impact. The success rates were then used to tune the algorithm in order to improve the spreading, and therefore the IGD. After an extensive testing of the algorithms, it was realized that the use of the success rates offers a clearer metric, than the mean and variance of the IGD, to understand the impact of some user-defined parameters. In the following, only the most significant results with the most significant metric are presented.

Table 3 summarizes the success rates on the Cassini test case for different values of n pop and ρ pop but with all the heuristics active.

Table 3 Tuning of n pop and ρ pop on the Cassini test case
Full size table

One can see that the best convergence is obtained for n pop =150 and in particular when combined with ρ pop =0.5. On the other hand, best spreading is obtained with medium sized populations with n pop =60. A good compromise seems to be n pop =150 and ρ pop =0.2. Results on the other test cases (as shown in Table 4, Table 5 and Table 6, with n pop =150 and ρ pop =0.2) show in general that large populations and small ρ pop are preferable. This also means that social actions on a large quota of the populations are undesirable and it is better to perform social moves among a restricted circle of agents. Table 4 reports the results of the tuning of MACS2 on the 3-imp and Cassini test cases. Table 5 and Table 6 report the results of the tuning of MACS2 on the UF and ZDT test sets respectively.

Table 4 Tuning of MACS2 on the 3-impulse and Cassini test cases
Full size table
Table 5 Tuning of MACS2 on the UF test cases
Full size table
Table 6 Tuning of MACS2 on ZDT test cases
Full size table

Table 4 shows a marked improvement of p conv on the Cassini when the population size is 150. Likewise, Table 5 shows that in general, with a population of 150 agents, there is an improvement in performance, and on p spr in particular, on the UF1, 2, 6, 8 and 9 test cases. Notable exceptions are the ZDT in Table 6, for which the best performance is obtained for a small population with n pop =20.

The impact of F is uncertain in many cases, however, Table 7 shows for example that on the UF8 test case a better performance is obtained for a high value of F. Table 5 and Table 6 show that the default value for Tol conv already gives good performance and it does not seem advantageous to reduce it or make it larger.

Table 7 Tuning of F on the UF8 test cases
Full size table

The impact of social actions can be seen in Table 4, Table 5 and Table 6. Table 4 shows that on the 3-impulse and Cassini test cases the impact is clearly evident, since there is a marked worsening of both p conv and p spr . On the UF benchmark, see Table 5, removing social actions induces a sizeable worsening of the performance metrics. This is true in particular for functions UF1, UF3, UF5, UF6, UF7, UF8 and UF9. Notable exceptions are UF2, UF4 and UF10. As a results of the tuning test campaign, the settings reported in Table 8 are recommended. Note that the recommended population size for all the cases except the ZDT functions, is 150 agents, while for the ZDT functions remains 20 agents.

Table 8 Settings for MACS2 after tuning
Full size table

With these settings, the performance of MACS2 was compared, on the UF test suite in Table 9, with that of MACS, Multi objective Evolutionary Algorithm based on Decomposition (MOEAD [25]), Multiple Trajectory Search (MTS [17]) and Dynamical Multi Objective Evolutionary Algorithm (DMOEADD [9]). The last three are the best performing algorithms in the CEC09 competition [26].

Table 9 Performance comparison on UF test cases: Average IGD (variance within parenthesis)
Full size table

As shown in Table 9, the tuned version of MACS2 outperforms the other algorithms on UF2, 3, 6, 8, 9 and 10, on UF1 is very close to MOEAD, while it ranks second on UF5 and 10 and finally third on UF7.

In Table 6 one can find the comparison against the old version MACS on the ZDT test set. MACS2 results generally better except on the ZDT4 case. Note that M spr of MACS for both ZDT2 and ZDT6 is always between 0.6e-2 and 0.9e-2, therefore always above the chosen threshold τ spr .

The poor performance of MACS2 on ZDT4, might be due to the relative ineffectiveness of the pattern search along the coordinates on this particular test case. In the attempt to improve performance on ZDT4, a second test set was run with a slightly modified version of MACS2: the number of components which are explored by each agent at the h-th iteration was reduced to 1 only, compared to the n in Algorithm 2, at the same time, all individuals were performing social actions, i.e. n social =n pop . With this modifications, a success rate of 0.66 both on convergence and spreading is achieved although the p conv and p spr on ZDT2 drops to 0 and the p conv on ZDT6 drops to 23 %.

Table 10 shows a comparison of the performance of MACS2 on 3-impulse and Cassini, against MACS, MOEAD, MTS and NSGA-II. Both MACS and MACS2 are able to reliably solve the 3-impulse case, while MOEAD manages to attain good convergence but with only mediocre spreading. On the contrary, both MTS and NSGA-II achieve good spreading but worse convergence, indicating that their fronts are quite well distributed but probably too distant from the true Pareto front. Cassini is a rather difficult problem and this is reflected by the generally lower metrics achieved by most algorithms. Only MACS, MACS2 and NSGA-II reach a high convergence ratio, but for the last two, their spreading is still rather low. After inspection of each of the 200 Pareto fronts one can see that such a low spreading implies that the algorithm did not converge to the global Pareto front. Figure 2 illustrates the difference between MACS and NSGA-II. The behavior of MACS2 is similar to the one of NSGA-II. MACS achieves the best known value for objective function Δv. Both NSGA-II and MACS2 instead fall in the basin of attraction of the second best value for objective function Δv [22].

Fig. 2
figure 7

Comparison of Pareto fronts for the Cassini case

Full size image
Table 10 Comparison of MACS, MACS2 and MOEAD on 3-impulse and Cassini test cases
Full size table

The performance of MOEAD and MTS on Cassini is rather poor, with the former attaining only 50 % convergence but with almost zero p spr ; conversely, only one third of the latter’s runs are below the spreading threshold and almost none meets the convergence criterion.

5 Conclusions

This paper has presented a version of Multi-Agent Collaborative Search based on Tchebycheff decomposition. Compared to the previous version of MACS a number of heuristics has been revised and in particular there was an inversion of the percentage of agents performing social and individualistic moves. The new version, denominated MACS2, demonstrated remarkable performance on known difficult benchmarks outperforming known algorithms. On the Cassini real case application, and on benchmark function ZDT4, MACS2 falls back behind its predecessor. In both cases there are multiple local Pareto fronts corresponding to strong attractors. From a first analysis it seems that the simple pattern search implemented in MACS2 is not sufficient and is limited by its search along the coordinates only. In MACS the search included random directions and directions derived from DE and PSO heuristics. It seems reasonable to assume that a more flexible set of individualistic moves might improve MACS2. This is the subject of current developments. Also, from the tests performed so far the actual contribution of the utility function is uncertain and more investigations are underway.

The use of a selection operator based on Tchebycheff decomposition, instead, appears to be beneficial in a number of cases. In MACS2, in particular, agents operating at the extreme of the range of each objective are always preserved and forced to improve a subproblem. A better solution of the subproblems is expected to further improve convergence. One possibility currently under investigation is to make some agents use a directed search exploiting the directions defined by the λ vectors.