1_intro.tex

\section{Introduction}

% Define MOP
Multi-objective Optimization Problems (MOP) are maximization (or minimization)
problems characterized by multiple, conflicting objective functions. It arises
in real world applications that require a compromise among multiple objectives.
The set of optimal trade off solutions in the decision space is the \emph{Pareto
Set (PS)}, and the image of this set in the objective space is the \emph{Pareto
Front (PF)}. Finding a good approximation of the Pareto Front is a hard problem for
which multiple Evolutionary Algorithms have been proposed.

% Mention that MOEAD is a good approach for MOP
The Multi-Objective Evolutionary Algorithm Based on Decomposition
(MOEA/D)~\cite{zhang2007moea} is an effective algorithm for solving MOPs. The
key idea of the MOEA/D is that the multi-objective optimization problem is
decomposed into a set of single objectives subproblems All subproblems
are then solved in parallel.

% Mention that MOEAD all problems are treated equally, but in actually they are
In the original MOEA/D, all subproblems are treated uniformly, in the sense that
all of them receive the same computational effort. However, it has been observed
that some subproblems are harder than others, and take more effort to converge
to an optimal solution~\cite{zhou2016all}. Because of this, \emph{Resource
Allocation} approaches have been proposed to allocate different amount of
computational effort to different subproblems, based on an estimation of the
relative difficulty of each subproblem~\cite{zhou2016all, zhang2009performance,
kang2018collaborative}. The most popular approach for estimating subproblem
difficulty is the Relative Improvement, which calculates how much a subproblem
has improved in recent iterations.

% Motivation for this approach
Here, we propose a new approach for estimating difficulty and
calculating priority in Resource Allocation for MOEA/D. Our approach uses the
idea of \emph{diversity} in decision space and in objective space to calculate
the priority of solutions. Our motivation for this choice is that the quality of
a MOP solution set is often evaluated by the diversity in the objective space.
If we assign higher priority for regions with lower diversity, we are
encouraging the algorithm to spend more computational effort in regions that are
not yet well explored.

% Simplify the paragraph below (important point is an outline of how we calculate diversity in both cases (In this paper, we define a priority function based on diversity using .........))
In this paper, we define a priority function based on diversity on the objective space using the MRDL, proposed by Gee~\cite{gee2015online}. The MRDL is an online diversity metric based on a geometrical perspective and indicates the loss of diversity related to a solution to the whole population. We also define a priority function based on diversity on the decision space using the Norm. It considers diversity of compared solutions by measuring the norm of  the difference of these solutions. We understand that these priority functions are able to monitor diversity during the execution of the algorithm guiding the search behavior of the algorithm.


% Expand the paragraph below with more details on the results and conclusions
% Use the abstract as inspiration. 
We compare the new approach with the Relative Improvement and with the standard MOEA/D (with no priority function). The results show that a priority function focused on decision space lead to better results on the metrics Hypervolume (HV) and Inverted Generational Distance (IGD) and also lead to a higher percentage of non-dominated solutions. The diversity on the decision space shows better performance on the benchmark function,  generally being better than using the Relative Improvement. To our surprise, priority function on objective space did not perform so well, barely improving the results compared with no Resource Allocation at all. On the Lunar Landing problem, all methods achieved similar HV values but, the proposed priority function obtained higher proportion of feasible solutions.


%The results found supported that idea, since in the real-world Lunar Landing problem these priority functions performed very well (with emphasis on the results of the 2-Norm). In the UF benchmark problem only 2-Norm performed well, followed closely by the relative improvement. All code is available for reproducibility purpose.

% This balance is defined by the concept of ``pareto dominance''. Given two
% solutions vectors $u, v$ in $\mathbb{R}^{D}$, $u$  Pareto-dominates $v$, we
% say that denoted by $f(u) \prec f(v)$, if and only if $f_k(u) \leq f_k(v),
% \forall_k \in \{1,..., m\}$ and $ f(u) \neq f(v)$. Likewise, a solution $x \in
% \mathbb{R}^{D}$ is considered Pareto-Optimal if there exists no other solution
% $y \in \mathbb{R}^{D}$ such that $f(y) \succ f(x)$, i.e., if $x$ is
% non-dominated in the feasible decision space. A non-dominated solution exists
% if no other solution provides a better trade-off in all objectives.

% Consequently, the set of all Pareto-Optimal solutions is known as the Pareto-Optimal Set (PS), while the image of this set is referred to as the Pareto-optimal Front (PF).\\
% \vspace{-1em}
% \begin{equation}
% PS = \{x \in \mathbb{R}^{D} | \nexists y \in \mathbb{R}^{D} : f(y) \succ f(x)  \},
% \end{equation}
% \vspace{-1em}
% \begin{equation}
% PF = \{f(x) | x \in PS \}.
% \end{equation}

%Multi-objective evolutionary algorithms (MOEAs) are one of the most widely used groups of algorithms for finding approximations to the PF of a MOP. They are characterized by their ability to find good approximations to PF in a single run~\cite{zhou2011multiobjective}. In recent years, there has been an increasing interest in studying MOEAs and with a primary concern of improving their general performance.% Among MOEAs, there are three major paradigms: Pareto domination-based approaches~\cite{deb2002fast},~\cite{zitzler2001spea2}; indicator-based approaches~\cite{beume2007sms},~\cite{zitzler2004indicator} and decomposition-based approaches~\cite{li2009multiobjective},~\cite{zhang2007moea}.

%Multi-objective evolutionary algorithms (MOEAs) are one of the most widely used groups of algorithms for finding approximations to the PF of a MOP. They are characterized by their ability to find good approximations to PF in a single run~\cite{zhou2011multiobjective}. In recent years, there has been an increasing interest in studying MOEAs and with a primary concern of improving their general performance. Among MOEAs, there are three major paradigms: Pareto domination-based approaches~\cite{deb2002fast}; indicator-based approaches~\cite{beume2007sms}; and decomposition-based approaches~\cite{zhang2007moea}.

% We are interested in analyzing the Multi-objective Evolutionary Algorithm based on Decomposition framework, MOEA/D~\cite{zhang2007moea}. It represents a class of population-based meta-heuristics for solving Multi Objective Problems. In
% this framework, each individual has a specific weight vector which is used to decompose the original multi-objective problem into simpler, single-objective subproblems by means of scalarizations. Each subproblem is then evaluated and its utility value is calculated by an aggregation function given the related weight vector.

% In the original MOEA/D, each solution of a subproblem have the same amount of computational resource (number of iteractions). Each subproblem relates to a region of the PF. Since all of them are uniformly treated, it is expected that different regions of the would be more difficult to find approximations than other areas leading to an unbalanced exploration of the search space.
%\begin{figure}[h]
%	\centering
%	\includegraphics[width=0.55\textwidth]{img/decomp2.png}
%	\caption{A decomposition strategy generates weight vectors that defines the subproblems. Figure from~\cite{chugh2017handling}.}
%	\label{fig1}
%\end{figure}
%
%\begin{figure}[h]
%	\centering
%	\includegraphics[width=0.43\textwidth]{img/harder_problems}
%	\caption{Distribution of optimal solutions of subproblems with uniform weight vectors on ZDT3. Figure from~\cite{li2015use}.}
%	\label{fig2}
%\end{figure}
%
%
%\begin{figure}[h]
%	\centering
%	\includegraphics[width=0.53\textwidth]{img/harder_problems2}
%	\caption{An example that uniformly distributed weights may lead to different distributions of optimal solutions. (a) Solutions $s_1$ to $s_7$ are the optimal solutions of weights $w_1$ to $w_7$, respectively. (b) Solutions $s_1$,$s_2$,$s_3$,$s_6$ and $s_7$ are the optimal solutions of $w_1$,$w_2$,$w_3$,$w_6$ and $w_7$, respectively, while solution $s_5$ is the optimal solution of $w_4$ and $w_5$.Figure from~\cite{li2017weights}}
%	\label{fig3}
%\end{figure}


%
%Another way, is allocating different number of evaluations to the subproblems based on some priority function. In a few recent works, a priority function (also called utility function) is used to prioritize resources given to subproblems that contribute more to the algorithm's search.  In the works of Zhang et al.~\cite{zhang2009performance} and Zhou et al.~\cite{zhou2016all} a priority function was proposed aiming to prioritize solutions based on a historical convergence information during different generations. Another approach was implemented in Kang et al.~\cite{kang2018collaborative}, where the priority function was based on the presence of a solution from the main population on a secondary population.

% Although researchers have not studied this problem in much detail, there have been some works that have discussed this matter. One way to address this problem is to allocate different number of evaluations to the subproblems based on some priority function. In a few recent works, a priority function (also called utility function) is used to prioritize resources given to subproblems that contribute more to the algorithm's search.  In the works of Zhang et al.~\cite{zhang2009performance} and Zhou et al.~\cite{zhou2016all} a priority function was proposed to prioritize solutions based on convergence information during different generations. Another approach was implemented in Kang et al.~\cite{kang2018collaborative}, where the priority function was based on the presence of a solution from the main population on a secondary population.