D. W. Gong et al.
obtained until the most satisfactory solution is found [14].
In the method proposed by Deb et al. a strictly increasing
function is constructed to reflect the user’s preferences after
the population has evolved for a number of generations set
in advance. Then the function is used to compare differ-
ent solutions to guide the population evolving towards the
most preferred region [15]. In the study of Sinha et al. a
preference-based methodology is proposed, where the pref-
erences provided by the user in the intermediate runs of an
evolutionary multi-objective optimization algorithm is used
to construct a polyhedral cone, which is used to eliminate
a part of search space and conduct a more focused search.
The dominance principle is modified to search for better
solutions lying in the preferred region [16].
Expression of the user’s preferences is also important
besides the means of embedding them. There are various
expression forms of the user’s preferences, e.g., reference
point [17], reference direction [18], solution ranking [19],
and so on. In the work of Bently et al. the importance of
objectives is defined, allowing evolutionary algorithms to
converge on a small subset of acceptable non-dominated
solutions [20]. It is convenient and common to adopt
weights to represent importance values of different objec-
tives. However, it is difficult and less reasonable to specify
a precise weight for the user aprioribecause of the uncer-
tainty of the user’s cognition. Therefore, the user’s prefer-
ences to different objectives were expressed with intervals
in this study to alleviate the user’s burden resulting from
assigning precise weights. Note that both the optimization
problem and the user’s preference have uncertainties, these
make the problem considered here more complex. There-
fore, appropriate methods are required to make the user’s
preferences precise. In the work of Wang et al., a method
of calculating the user’s precise preferences is obtained by
deduction, and different schemes are compared based on
the corresponding intervals accumulated from all attributes
[21]. In this study, the user’s interval preferences were made
precise by solving an auxiliary optimization problem in
view of the idea of [21].
3 Proposed method
3.1 Overview
In the framework of NSGA-II, a novel evolutionary opti-
mization algorithm with a user’s preferences to solve the
problem described with formula (1) is presented in this
section. In the algorithm, the user is requested to input
his/her interval preferences to different objectives before the
evolution; a large population is adopted and theK-means
clustering [25] is utilized to reasonably cluster it; then the
computer is employed to calculate the values of explicit
objectives of all evolutionary individuals, and the user eval-
uates only the values of implicit objectives of the centers
of all clusters; for evolutionary individuals not evaluated
by the user, a similarity-based estimation strategy is used
to estimate the values of implicit objectives described in
subsection 3.3. The user’s interval preferences to differ-
ent objectives are quantified by solving a single-objective
optimization problem with constraints, elaborated in sub-
section 3.4. In addition, a sorting scheme based on the user’s
preferences is proposed to steer the search towards the user’s
preferred region, given in subsection 3.5. The user can mod-
ify his/her preferences during the evolution. The steps of the
proposed method are as follows:
1. Set the values of evolutionary control parameters in the
method, and initialize a population x(t), t = 0.
2. Input the user’s interval preferences to each objective.
3. Divide x(t) into N
c
clusters using the method in [25].
4. Decode each evolutionary individual, evaluate all
implicit objectives of the centers of all clusters by the
user, estimate the values of all implicit objectives of the
rest evolutionary individuals in all clusters according to
(4), and calculate the values of all explicit objectives of
all evolutionary individuals by the computer.
5. Make the user’s interval preferences precise by solving
an auxiliary optimization problem.
6. Employ the tournament selection with size 2, and
perform crossover and mutation operations to create
offspring populations.
7. Combine parent and offspring populations.
8. Rank the combined population according to the sort-
ing scheme based on the user’s preferences, and select
superior individuals to form a new population, x(t + 1).
9. Judge whether termination criteria have been met or
not, if yes, stop the evolution and output the optimal
solutions; otherwise, let t = t + 1. If the user’s prefer-
ences are changed, go to Step 2; otherwise, go to Step
3.
The flow chart of the proposed method is depicted as
Fig. 1 according to the above steps, and the shaded parts will
be introduced in the following subsection.
3.2 Relation to our previous work
As stated in Section 1, based on the characteristics of uncer-
tainties contained in the two types of objectives, HIMOP
is first transformed into one without uncertainties by using
interval analysis, and then an evolutionary optimization
algorithm is employed to effectively solve the transformed
problem by combining a traditional GA [4]. To be solved,
however, is the optimization problem without uncertain-
ties, transformed from the original one. In our recently
proposed method for interval MOPs, a novel interval