Abstract
An interactive preference-based evolutionary algorithm is proposed to solve multi-criteria satisfactory optimization problems. Using the proposed method, Decision Makers (DMs) can easily obtain the preferred parts of the actual Pareto front. Based on the satisfactory theory, the feasible region is constructed to evaluate the obtained candidates in terms of satisfactory degree. Furthermore, optimal weights are generated by minimizing the weighted ℓ p -norm of the conflicting satisfactory and unsatisfying candidates, to form the evaluation function by which the next generation would evolve towards the preferred optimization solutions. The layout optimization of a retrievable satellite module is used to verify the effectiveness of proposed method.
Keywords
Introduction
Multi-objective optimization problem (MOP) is a typical trade-off issue which is prevalent in many practical applications [1–3]. For instance, a comfortable vehicle usually costs much more than an uncomfortable one. The objectives of high comfort and low price are contradictory. The result of a MOP therefore is a set of Pareto optimal solutions that are non-inferior to each other rather than one single solution that optimizes all objectives simultaneously [4–10]. Without loss of generality, the Pareto optimal definitions with respect to a minimization MOP are listed below [6, 11].
In the light of the difficulty in generating the actual PF, an approximation to the actual PF is deemed to be an incontrovertible alternative in most practical cases. It is well recognized that convergency and diversity are two critical performance metrics of the generated approximation [12, 13]. However, it is difficult or even impossible to obtain a guarantee of good convergence and diversity at the same time. Furthermore, the obtained solutions are essentially intended for the Decision Makers (DMs) to select from. A multi-criteria satisfactory optimization (MCSO) scenario, of which the ultimate goal is to select the satisfactory part of the PF (denoting the preference of the DM), would be a valid and efficient alternative to the conventional MOP.
Moreover, implementation of the MCSO requires a specification of the satisfactory degree of each objective whereby the evaluation and discrimination of satisfactory solutions are carried out. Typically, three prevalent classes of methods, i.e. priori preference, posteriori preference, and interactive preference, are applied to address the aforementioned evaluation and discrimination [4, 15]. The first class utilizes different terms (e.g. weights, bounds, reference point, lexicographic order, etc.) to articulate the preference information prior to the process of solution [11, 16]. Its limitation is that the DM doesn’t necessarily know the casual relationship between the articulation and the corresponding possible outcome. The obtained optimal result may not be as satisfied as expected and it will entail another substitutive articulation of the preference. The posteriori method is the straightforward generating method of which the basic principle is literally to select the satisfactory set from the obtained Pareto non-dominated solutions [15, 18]. In addition to the computational complexity of obtaining the approximation of the PF, there’s still a challenge to select the satisfactory solution out of the large set of approximation set. Furthermore, in the light of high dimensional problem (more than 3), an illustration of obtained alternatives, which will intuitively specify a satisfactory solution, is generally indeterminable. Referring to the interactive preference method, the full participation of the DM differentiates it from the aforementioned two methods. The insight of DMs into the problem updates after each or several iterations, and no more global preference information of the problem is essential. In addition, as only preferred Pareto optimal solutions are generated after each iteration for DMs to select, the computational cost would be saved. In light of the superiority of interactive method, several algorithms have been proposed to develop the interactive methodology in terms of two main categories: preference point and classification of objective functions [19]. Thiele et al. [20] incorporated the DM’s preference in terms of preference point. The modified utility functions are deemed to direct the search to the preferred region of the PF. The synchronous NIMBUS algorithm [21] utilized different scalarization functions synchronously based on the same reference information to alleviate the discrepancy of optimal results caused by the selection of different scalarization functions. Deb et al. [22] incorporated the partial or complete preference ranking obtained by the DM and PI-EMO-CF algorithm in terms of tree ways to iteratively direct the solution process to obtain the preferred part of Pareto front. Among all the aforementioned methods, one key In light of the superiority of interactive method, several researches have been developed [23–28].
In this work, a model is proposed to discriminate obtained candidates by genetic algorithm (GA). The feasible domain, therefore, is established for the multi-objective optimization problems. Optimal weights are generated by resorting to the minimization of the weighted ℓ p -norm of the conflicting satisfactory and unsatisfying candidates, DMs can use their objective preference in GA to obtain the preferred search direction.
The rest of this paper is organized as follows. Section 2 introduces the definition of Satisfactory Theory and a general formulation of MCSO. In Section 3, our proposed interactive preference-based evolutionary algorithm is presented in detail. One practical application is included to verify the effectiveness of the proposed method in Section 4, followed by conclusions and future work in Section 5.
Satisfactory theory
Definition of satisfactory problem
Simon [29] first introduced the scenario of satisfactory criteria optimization and proposed the satisfactory solutions instead of the conventional ones. Takatsu [30] elaborated the basic mathematical principle and properties of the satisfactory theory. In engineering applications, the theory of satisfactory control was studied by Goodrich et al. [31] and utilized to control classical problems. Satisfactory theory has prospered and grown in engineering fields. Some definitions of satisfactory theory are listed below [32].
Given a feasible solution set X, X ⊆
Given a feasible solution set X, X ⊆
Assume that the decision variable is
The quality criteria set is denoted as
Given a satisfactory degree function h
k
:
The overall satisfactory degree function is defined as fop : [0, 1]
m
→ [0, 1]. Generally, fop can be formulated in terms of several different terms in accordance with the characteristics of problems [33, 34]. In this work, the linear weighted-sum method that is prevalent in addressing the specification of satisfactory degree is introduced
Thus, the multi-criteria satisfactory problem is formulated as a model with inequality constraints g
i
(x) as follows:
In this paper, we formulate Equation (8) as the overall satisfactory degree function and focus on the specification of its weights for the MCSO.
In order to obtain Pareto optimal solutions for the DMs, the parallel search based evolutionary optimization algorithms, originating from Darwinian Theory, have its remarkable adaptability and good efficiency in solving single objective and multi-objective optimization problems [35–37]. Among typical evolutionary algorithms, including genetic algorithm (GA [38, 39], particle swarm optimization (PSO) [40, 41], artificial bee colony algorithm [42, 43], etc, GA, of which the basic operators are selection, crossover and mutation, is widely used in the area of evolutionary optimization during the last decades. We hereby combine the Pareto GA with preference-based method, and propose an interactive preference-based GA for MCSO.
Binary relation
To discriminate two candidates in the population, a binary relation mechanism is defined as Table 1.
Binary relations
Binary relations
The symbol d illustrated in Table 1 denotes the discrimination of satisfactory degrees between arbitrary two candidates, and formulated as
A positive d denotes that the candidate x i is superior to x j and vice versa. If d equals to 0, it means that both candidates are equivalent to each other. For the sake of simplicity, only “Equivalent”, “Superior”, and “More superior” are utilized for the rest of this paper.
The symbol ɛ illustrated in Table 1 denotes a positive constant, say 10-5, and is utilized to be the upper bound of |d|. The symbols α and β illustrated in Table 1 are 2 tunable parameters denoted as the upper bounds for “≻” and “≻≻”, respectively, where (0 < ɛ < α < β < 1). The binary relations “≻” and “≻≻” are literally 2 metrics to measure the preferences of different candidates. Figure 1 illustrates 6 candidates with two types of binary relations, “≻” and “≻≻”.

Two types of binary relations.
It can be seen from Fig. 1 that “≻≻” denotes larger preferred tendency. In practical applications, symbols α and β are utilized to specify preference degree by DMs. The initialization of symbols α and β can resort to the prior knowledge or experience of the DMs.
It can be seen from Equations (6) and (9) that the MCSO algorithm necessitates proper specification of weights to obtain preferred solutions at each generation. In light of the importance of weights, the following optimization model is introduced to transfer the preferences of particular limit candidates into the preferences of weights to depict the overall satisfactory degree.
Assume that L is the set of candidates selected by DM, and l denotes the ℓ0 -norm (total number of the nonzero entries) of L.
The preference relations between these candidates in set L are given as follows:
The objective is to minimize the weighed ℓ
p
-norm of the satisfactory degree for x
k
, xk-l-1 while the feasible region are defined in accordance with Equation (11).
Note that in constraints g1, g2,
, g
l
of Equation (12), c is formulated as
The utilization of coefficient c can avoid dynamically adjusting α, β in the process of evolution. This method is called the adaptive ratio method. swmax and swmin are changed with different evolutionary generations.
The optimal solution obtained by solving Equation (12) can be assigned to the corresponding satisfactory degree objective function. Then it can be used to design a new classification function for the next generation.
Here, we utilize the selection mechanism and the sharing method proposed by Kiyota et al. [28] to discriminate the candidates. All non-dominated candidates obtained at each generation are selected from the population in accordance with the Pareto selection. In the tournament selection, two candidates are randomly chosen to distinguish the superiority. R
sw
for arbitrary candidates i and j is formulated as
To maintain a good diversity of the obtained candidates, the niche criteria is applied in the tournament selection and formulated as [44]:
The niche count m
i
denotes the sum of Sh (·) of the ith candidate and arbitrary candidate in the population, and formulated as
Given a uniform random number R (0 ≤ R ≤ 1), if R sw ≤ R, the candidate with the larger sw i is selected to be the winner, else if R sw > R, the candidate with the smaller m i is selected to be the winner.
By resorting to this particular mechanism, the search would be directed towards the preferred region of the PF, as depicted in Fig. 2.

The search directed by a DM.

The flowchart of the algorithm of the interactive algorithm.

Distribution of satisfactory solutions: a1) initial candidates with respect to direction 1, a2) solutions after 3rd preference optimization with respect to direction 1, a3) solutions after 5th preference optimization with respect to direction 1, b1) initial candidates with respect to direction 1, b2) solutions after 3rd preference optimization with respect to direction 1, b3) solutions after 5th preference optimization with respect to direction 1.
The flowchart of the interactive algorithm is shown in Fig. 3.

Layout of the two preferred directions: (a) The original solution (b) Preference 1 solution (c) Preference 2 solution.
The proposed method is applied to a layout problem of retrievable satellite module [45]. This is a test problem of N (=9) different scaled circles in circle-packing with performance constraints. The radius of the circular container is R = 105 mm. r
i
, (x
i
, y
i
), and m
i
are the radius of circles, centroid coordinate, and mass, respectively. The original optimization problem is transferred into a 2-objective MOP to test the effectiveness of proposed method and formulated as
where R
s
denotes the circumcircle radius, J denotes the value of static equilibrium, g1 denotes the interference constraint, g2 denotes the geometric size constraint, g3 denotes the static equilibrium constraint, i, j ∈ I, i ≠ j, I = {1, 2, . . . , N} , N = 9, and
The objective satisfactory function is formulated as
Assume that there are two types of preference direction. Three candidates are selected to calculate the optimal weights ω1, ω2. The preferred evaluation function sw is reformulated after every ten generations. After 50 generations of evolution, the satisfactory s1, s2 of each candidate is distributed in the population as shown in Fig. 4.
Figures 4 (a1) and (b1) present the initial distributions of candidates. Figures 4 (a2) and (b2) present the distributions of candidates after the 3rd preference optimization. Figures 4 (a3) and (b3) present the distributions of candidates after the 5th preference optimization. It is obvious that candidates can reach the Pareto frontier in the two preference situations, as shown in Fig. 4 (a1)-(a3) and (b1)-(b3). Moreover, the moving directions of candidates in the final population are the same as with the preferred directions of DMs.
Performance indexes of two preferred directions
Two kinds of layout solutions corresponding to the two preferred directions are shown in Figs. 5(b) and 5(c). The performance indexes of the two preferred directions are shown in Table 2.
In this paper, an interactive preference-based evolutionary algorithm is proposed to address multi- criteria satisfactory optimization problems. By resorting to the satisfactory theory, obtained candidate at each generation can be interactively evolved towards the satisfactory parts of the PF. The proposed method differs from the conventional Pareto GA and fixed weights approach in two aspects: (1) Pareto solution boundary specification, and (2) adaptive target weights. A classification model is then proposed to evaluate obtained candidates by GA. The feasible domain therefore, is established for the multi-objective optimization problems. Optimal weights generated by resorting to the minimization of the weighted ℓ p -norm of the conflicting satisfactory and unsatisfying candidates are utilized by the DMs to obtain the preferred search direction. A layout optimization of a retrievable satellite module demonstrated the effectiveness of the proposed method.
In the future work, we would like to focus on the investigation of the dynamic formulation of the constraints, which is a promising and open issue in the field of multi-objective optimization.
Footnotes
Acknowledgments
This research was supported by the National Natural Science Foundation of China (Contract No. 51775090).
