\def\papertitle{Decomposition Based Parallel Hybrid MOEA with Application to the multiobjective multidimensional Knapsack Problem }
\def\paperauthorB{Khadidja Chaabane}
\def\paperauthorC{Sadek Bouroubi}
\def\paperauthorA{\underline{Nedjmeddine Kantour}}
%\def\paperauthorB{Author_B_fullname}
% you can add more authors using alphabets after \paperauthor
% 
%------------------------------------------------------------------------------------------
% Do not delete this part starting from here and up to .....
\documentclass[oneside]{article}
\usepackage{icma2021,amssymb,amsmath,mathrsfs} 
%\setcounter{page}{1}
%\input{../../expages.tex}\setpagenumber{1}
%\input{expages.tex}\setpagenumber{1}
\ninept
\usepackage{pgfplots}
\usepackage{multirow}
\usepackage{mathptmx} 
% Saves a lot of ouptut space in PDF... after conversion with the distiller	  
% Delete if you cannot get PS fonts working on your system.

% pdf-tex settings: detect automatically if run by latex or pdflatex
\newif\ifpdf
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\pdffalse
\else
\pdftrue
\fi

\ifpdf % compiling with pdflatex
\usepackage[pdftex,
pdftitle={\papertitle},
pdfauthor={\paperauthorA , \paperauthorB , \paperauthorC},

% for more than one author use pdfauthor={\paperauthorA,\paperauthorB, .....},
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
colorlinks=false, % links are activated as colror boxes instead of color text
bookmarksnumbered, %use section numbers with bookmarks
pdfstartview= XYZ	% starts with zoom=100% instead of full screen; especially useful if working with a big screen :-)
]{hyperref}
\pdfcompresslevel=9
\usepackage[pdftex]{graphicx}
\usepackage[figure,table]{hypcap}
\else % compiling with latex
\usepackage{graphicx}
\usepackage[dvips,
colorlinks=false,           % no color links
bookmarksnumbered, %use section numbers with bookmarks
pdfstartview= XYZ	% starts with zoom=100% instead of full screen
]{hyperref}
% hyperrefs are active in the pdf file after conversion
\usepackage[figure,table]{hypcap}
\fi

\newcommand\dsum{\displaystyle\sum}
\newcommand\dprod{\displaystyle\prod}
%------------------------------------------------------------------------------------------
\title{\papertitle}
\affiliation{\paperauthorA , \paperauthorB , \paperauthorC}	% This command replaces \name{The DAFx Crew} 
{L'IFORCE Laboratory, Department of Operations Research,\\ Faculty of Mathematics, USTHB.}


%\usepackage{layout}
%------------------------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%% to here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
	
	%\layout
	
	% more pdf-tex settings:
	\ifpdf % used graphic file format for pdflatex
	\DeclareGraphicsExtensions{.png,.jpg,.pdf}
	\else  % used graphic file format for latex
	\DeclareGraphicsExtensions{.eps}
	\fi
	
	\maketitle
	
\begin{abstract}
Recently, there has been a noticeable tendency in research for combinatorial optimization issues toward the hybridization of metaheuristics with other optimization techniques. On the other hand, parallel conception of multiobjective evolutionary algorithms (MOEAs) provides a significant enhancements in terms of efficiency and effectiveness. In this paper, we propose a hybrid parallel multiobjective evolutionary algorithm, with an application to the multiobjective multidimensional Knapsack Problem (MOMKP). The suggested approach can be considered as an enhanced parallel variant of two-phase method. Finally, we present an experimental study, where we assess the suggested approach against state-of-the-art sequential and parallel MOEAs, as to emphasize the contribution of the search strategy of the parallel MOEAs and its ability to approximate target areas of the true Pareto Front.
\end{abstract}

\section{Introduction}
% Introduction section

Multiobjective Problems consists to optimize $k$ objective functions simultaneously. The general form of MOPs is stated as follows:
$$ \left\{
\begin{array}{l}
  "max"\, Z(x) = (Z^1(x), Z^2(x), \dots, Z^k(x)), \\
  \; s.t., \quad x \in \Omega. 
\end{array}
\right.
$$
where $\Omega$ is the decision space, $x \in \Omega$ is a decision vector, and the vector $Z(x)$ consists of $k$ objective functions $Z^i(x) : \Omega \rightarrow \mathbb{D}_i,\; i \in \{ 1, . . . , k\}$. Since the aim in MOPs is to find good compromises. Here, we present the dominance relation, as to define optimality in MOPs. For any couple of feasible solutions $x$ and $x'$ in $\Omega$, the vector $Z(x) = (Z^1(x), . . . , Z^k(x))$ is said to dominate the vector \mbox{$Z(x^{'}) = (Z^1(x^{'}), \dots , Z^k(x^{'}))$}, denoted as $Z(x) \succ Z(x^{'})$, if and only if, $\forall i \in \{1, \dots , k\}$,\ $Z^i(x) \leq Z^i(x^{'})$ and $Z(x) \not = Z(x^{'})$. A feasible solution $x^* \in \Omega$ is called a Pareto optimal solution or an efficient solution, if and only if, $\not\exists y \in \Omega$ such that $Z(y)\succ Z(x^{*})$. The set of Pareto optimal solutions is called the Pareto-optimal Set (PS): $PS = \{ x \in \Omega | \not\exists y \in \Omega, Z(y)\succ Z(x^{*})\}. $ The evaluation of solutions in $PS$ is called the Pareto Front ($PF$): $PF = \{Z(x)| x\in PS \}. $

Furthermore, there exists an important classification of efficient solutions: supported efficient solutions and non-supported efficient solutions. According to Geoffrion's theorem \cite{35}, the supported efficient solutions, denoted $X_{SE}$, can be obtained by solving the parametric single-objective problems obtained by a linear aggregation of the different objectives $P_\lambda$:
$$ (P_\lambda) \left\{
\begin{array}{l}
  max\, \sum_{i=1}^{k} \lambda_i Z^i(x), \\
  \; s.t., \quad x \in \Omega, 
\end{array} 
\right.
$$
where, $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)\in \mathbb{R}^{k}_+$ is a weight vector with all positive components. 

On the other hand, there exists the non-supported efficient solutions set, denoted $X_{NS}$, this subset of the efficient solutions set cannot be obtained by solving $P_\lambda$. Furthermore, the images of the unsupported solutions are not located on the boundary of the convex envelope. 

% literature review for related work
In this paper, we propose a parallel hybrid multiobjective evolutionary algorithm, designed in a master/salve model, we call it Decomposition Based Parallel Hybrid MOEA (D/PHMOEA). The suggested algorithm is an enhanced  two-phase type algorithm, where the first phase consists of finding the supported solutions set using an exact method. In the second phase, the decision space is structurally decomposed and allocated to multiple MOEAs operating in parallel. Each
MOEA is dedicated to a specific region of the decision space that is initially characterized by a subset of the supported solutions found in the first phase. We assess the suggested method against some successful MOEAs using benchmark instances of the Multiobjective Multidimensional Knapsack Problem (MOMKP). This latter is a variant of the Knapsack Problem (KP), which is known to be NP-hard \cite{15}. Mathematically, MOMKP can be stated as follows: given $n$ items having $p$ characteristics (weight, volume, etc.) $w^i_{j}\geq 0,$ where, $ j\in \{1, \dots ,p\}$, $ i\in \{1, \dots , n\}$, and $m$ profits $c^{k}_{j},\ k\in \{1, \dots ,m\}$, we want to select items as to maximize the $m$ total profits, while not exceeding the $p$
knapsack capacities $W_i$ with regards to the different characteristics. The MOMKP is formulated as follows:

$$(MOMKP)
\left\{
\begin{array}{l}
\vspace{-0.5cm}\\
 \vspace{-5mm} \\
\displaystyle "max\," \ Z^k(x)=\sum_{j=1}^{n} c^{k}_{j}x_{j},\quad k\in \{1, \dots ,m\}\vspace{-1mm}\\
\begin{array}{ll}
s.t., & \displaystyle \sum_{j=1}^{n} w^i_{j}\,x_{j} \leq W_i ,\quad j\in \{1, \dots ,p\}\vspace{0.4em}\\

 & {\displaystyle x_{j} \in \{0,1\} ,\: \forall j\in \{1, \dots , n\}. }\vspace{1.3mm}
\end{array}
\end{array}
\right.
 $$ 
\section{Suggested Algorithm (D/PHMOEA)}

\subsection{Description}
In this section, we present a resumed description of the suggested algorithm, which is, as we already mentioned, an enhanced variant of the two-phase method. The first phase of the suggested algorithm method remains unchanged, as it is the case for all two-phase algorithms. It consists in the construction of the set of efficient solutions supported by the dichotomy method proposed by Aneja \& Nair \cite{36}, based on Geoffrion's theorem \cite{35}. This algorithm generates all the supported efficient solutions, including extreme and non-extreme ones, using a single objective problem whose objective function is a linear aggregation of two objectives (see $P_\lambda$ in the introduction). Next, after having the set of supported efficient solutions in hand, the second phase consists of approximating the set of non-supported solutions using multiple asynchronous parallel MOEAs. Each one of the parallel search entity is designed to target a specific region of the Pareto optimal front. This is by initializing its archive solutions set using a subset of the supported efficient solutions set gathered form the same region. Furthermore, the selection operator is defined according to the following order relation : let $P_t$ be the current population of a search entity, $PS_t$ be the set of Pareto solutions obtained at iteration $t$ (i.e., $ = \{x\in P_t | \not\exists y\in P_t : y\succ x\}$), and $R \subset Z(PS_t)\cap Z(X_{SE})$ the extreme points enclosing the predefined region for the search entity, $|R| = k$ the number of objective functions. The order relation is defined as follows:

$$ \forall x,y\in P_t, x \geq y \iff (x\succeq y) \lor \left(\phi(x)\geq \phi(y)\right), $$

where, $$\phi(x) = \sum_{i=1}^{k} \left( Z^i(x)\sum_{j=1}^{k} \dfrac{R_j^i}{{||\sum_{j=1}^k R_j ||}_2}  \right). $$

Hence, the process of selecting individuals that pass to the next generation $P_{t+1}$ is given explicitly as follows:
$$ P_{t+1} = \{ x\in P_{t} | (x\in PS_t) \lor (rank(x, P_t\backslash PS_t \leq N))\}, $$

where, $rank(x, P)$ is the order of a solution $x$ compared to elements of a set $P$ according to the function $\phi$, and $N$ is the parameter fixing the size of the current directing population.

     The suggested pMOEA can be classified as a cooperative algorithmic level parallel model designed in a master/worker paradigm, handling: (1) a master entity in charge of gathering and computing the global approximated Pareto solutions, (2) multiple MOEAs with directed the search to specific regions of the true Pareto front, with the help of a specific selection operator described above defined with a subset of supported efficient solutions.
     Regarding the decomposition procedure, this occurs over the decision space using the supported efficient solutions set found in the first phase. This is by partitioning this set into $p$ equally sized sets, according to one of the objective functions. As we mentioned earlier, the extreme solutions of each subset is used to construct the selection operator of each parallel MOEAs. 
     
      Figure \ref{fig: h}\, presents an example of the decomposition procedure applied to a bi-objective Knapsack instance: 2KP100-TA-0 \cite{37}. The decision space is decomposed into $p=4$ sub-regions. 
     
     \begin{figure}[h!]
     \centering
\pgfplotsset{width=7cm, compat=newest}
\begin{tikzpicture}[scale = 0.9]
\begin{axis}[ 
    title={},
    xlabel={},
    ylabel={},
    xmin=32600, xmax=43500,
    ymin=33400, ymax=42800,
    x=.0105mm,
    legend pos=north east] 
\addplot[only marks,
    mark=square,mark=x]
    coordinates {
 (42864, 34214)  (42795, 34365)  (42785, 34680)  (42750, 34851)  (42696, 35441)  (42625, 35555)  (42581, 35663)  (42538, 35807)  (42501, 35878)  (42490, 35957)  (42455, 35960)  (42446, 36020)  (42440, 36022)  (42436, 36301)  (42365, 36536)  (42298, 36554)  (42290, 36667)  (42268, 36822)  (42255, 36838)  (42220, 36983)  (42206, 37095)  (42137, 37136)  (42135, 37209)  (42123, 37248)  (42052, 37362)  (41981, 37459)  (41940, 37484)  (41914, 37598)  (41857, 37637)  (41817, 37659)  (41786, 37751)  (41722, 37821)  (41694, 37831)  (41651, 37879)  (41623, 37945)  (41580, 37993)  (41522, 38079)  (41459, 38128)  (41428, 38220)  (41388, 38242)  (41357, 38334)  (41264, 38412)  (41221, 38460)  (41150, 38574)  (41036, 38641)  (40936, 38656)  (40918, 38716)  (40914, 38749)  (40887, 38808)  (40843, 38854)  (40737, 38887)  (40723, 39000)  (40652, 39058)  (40635, 39093)  (40516, 39138)  (40459, 39139)  (40428, 39231)  (40311, 39257)  (40218, 39336)  (40144, 39345)  (40109, 39447)  (40019, 39450)  (40002, 39483)  (39959, 39485)  (39952, 39513)  (39931, 39597)  (39877, 39651)  (39835, 39655)  (39774, 39729)  (39706, 39742)  (39678, 39752)  (39658, 39796)  (39652, 39820)  (39567, 39867)  (39521, 39884)  (39485, 39992)  (39314, 40022)  (39261, 40027)  (39250, 40038)  (39226, 40079)  (39198, 40089)  (39148, 40111)  (39113, 40139)  (39008, 40182)  (38992, 40241)  (38937, 40272)  (38876, 40308)  (38844, 40311)  (38785, 40379)  (38739, 40396)  (38669, 40446)  (38660, 40563)  (38444, 40591)  (38416, 40601)  (38257, 40602)  (38226, 40694)  (38191, 40733)  (38058, 40850)  (37740, 40859)  (37702, 40890)  (37690, 41011)  (37652, 41042)  (37417, 41054)  (37100, 41177)  (36998, 41184)  (36979, 41209)  (36744, 41221)  (36614, 41273)  (36493, 41305)  (36446, 41319)  (36325, 41351)  (35991, 41385)  (35953, 41416)  (35832, 41448)  (35668, 41483)  (35547, 41515)  (35156, 41570)  (34988, 41588)  (34753, 41600)  (34652, 41622)  (34417, 41634)  (34311, 41636)  (33920, 41691)  (33416, 41743)  (33181, 41755)  };
  \addlegendentry{True Pareto Front}

 
 \addplot[ red!70,
    mark=square,mark=x]
    coordinates { (33181, 41755)(33416, 41743) (34652, 41622) (35156, 41570) (35547, 41515) (36979, 41209) (37652, 41042) (38660, 40563) (39485, 39992) (40635, 39093) (41150, 38574) (41357, 38334) (41914, 37598) (42123, 37248) (42206, 37095)  (42696, 35441)  (42864, 34214)                   };
    \addlegendentry{Supported Solutions}
 \draw[-,thick, dotted, gray] (0, 0) -- (33181, 41755);   
 \draw[-,thick, dotted, gray] (0, 0) -- (35547, 41515); 
 %\draw[->,thick, red] (0, 0) -- (68728, 83270);
 \draw[->,very thick, green!40] (0, 0) -- (33864, 41029);
 
 \draw[-,thick, gray] (33181, 41755) -- (33181, 41515);
 \draw[-,thick, gray] (33181, 41515) -- (35547, 41515);
 
 \draw[-,thick, dotted, gray] (0, 0) -- (35547, 41515);   
 \draw[-,thick, dotted, gray] (0, 0) -- (39485, 39992); 
 %\draw[->,thick,red] (0, 0) -- (75032, 81507);
 \draw[->,very thick, green!40] (0, 0) -- (37250, 40464);

\draw[-,thick, gray] (35547, 41515) -- (35547, 39992);
 \draw[-,thick, gray] (35547, 39992) -- (39485, 39992);
 

 
 \draw[->,thick, dotted, gray] (0, 0) -- (39485, 39992);   
 \draw[->,thick, dotted ,gray] (0, 0) -- (41914, 37598); 
 %\draw[->,thick,red] (0, 0) -- (81399, 77590);
 \draw[->,very thick, green!40] (0, 0) -- (40535, 38638);

\draw[-,thick, gray] (39485, 39992) -- (39485, 37598);   
 \draw[-,thick,gray] (39485, 37598) -- (41914, 37598); 
 
 
 \draw[->,thick, dotted, gray] (0, 0) -- (41914, 37598);   
 \draw[->,thick, dotted, gray] (0, 0) -- (42864, 34214); 
 %\draw[->,thick,red] (0, 0) -- (84778, 71812); 
 \draw[->,very thick, green!40] (0, 0) -- (42349,35678 ); 
 \draw[-,thick, gray] (41914, 37598) -- (41914, 34214);   
 \draw[-,thick, gray] (41914, 34214) -- (42864, 34214); 

     \end{axis}
\end{tikzpicture}
\caption{Illustrative example of the used decision space decomposition (Bazgan KP instance \cite{37}, 2KP100-TA-0)}
\label{fig: h}
\end{figure} 



\subsection{Experimental results}

We tested the sugessted algorithm on benchmark instances of MOMKP chosen from the instance libraries: Zitzler and al. \cite{16}, of which we consider for this experiments three instances with the number of items 250, 500, and 750, with two objective functions. We compared the performance of the suggested algorithm three four multiobjective algorithms with different concepts and/or different search strategies: NSGAII \cite{6}, SPEA2 \cite{7}, MOEA/D \cite{8}, MOFPA \cite{40}, PCPMOEA \cite{39}. The evaluation and comparison of the obtained solution's the quality, one must consider (convergence, and the spread), we used three performance metrics: Inverted Generational Distance (IGD) \cite{43}, Hypervolume \cite{16}, and the set coverage metric \cite{43}. 

Table \ref{igd} resumes the obtained values of the IGD metric assessing the convergence of the obtained Pareto sets. The IGD values shows clearly that, in general, D/PHMOEA converges better than all of the competing algorithms, especially for large instances, with the exception of the instance 2.250.
\begin{table}[h]
\begin{footnotesize}
\begin{center}
\centering
\setlength{\tabcolsep}{.7em}
{\renewcommand{\arraystretch}{1.3}
\begin{tabular}{lccccc}
\multirow{ 2}{*}{Instance} &  \multicolumn{ 5}{c}{Algorithm}  \\\cline{2-6}
 & SPEA2 & MOEA/D & MOFPA & PCPMOEA & D/PHMOEA \\ \hline
% 100 & & & & & \\ \hline
 250 & 14.883 & 3.9690 & 0.7248 & \textbf{0.2964} & 0.5248\\ \hline
 500 & 79.743 & 14.466 & 2.2850 & 0.7961 & \textbf{0.3226}\\ \hline
 750 & 224.794 & 32.655 & 10.062 & 3.1302 & \textbf{2.1359}\\ \hline
\end{tabular}
}
\end{center}
\end{footnotesize}
\caption{Experimental results concerning the IGD metric of the MOMKP instances.}
\label{igd}
\end{table}

Table $\ref{hyperv}$ resumes the obtained results regarding the Hypervolume indicator. This indicator is used to evaluate the convergence to the true Pareto front and diversity of the obtained Pareto front. As it is shown below, it is obvious that the suggested algorithm produces higher quality fronts, with significant difference especially when compared to SPEA2 and MOEA/D, and it's at least comparable to MOFPA and PCPMOEA algorithms.

\begin{table}[h]
\begin{footnotesize}
\begin{center}
\centering
\setlength{\tabcolsep}{.7em}
{\renewcommand{\arraystretch}{1.3}
\begin{tabular}{lccccc}
\multirow{ 2}{*}{Instance} &  \multicolumn{ 5}{c}{Algorithm}  \\\cline{2-6}
 & SPEA2 & MOEA/D & MOFPA & PCPMOEA & D/PHMOEA \\ \hline
% 100 & & & & & 1.7003306E+7 \\ \hline
 250 & 9.1677527E+7 & 9.8374725E+7 & 9.8556257E+7 & 9.8654313e+7 & \textbf{9.8692999E+7}\\ \hline
 500 & 3.6944050E+8 & 4.0515241E+8 & 4.0707772E+8 & 4.0772607E+8 & \textbf{4.0787113E+8}\\ \hline
 750 & 7.8038570E+8 & 8.8553814E+8 & 8.8572075E+8 & 8.9260224E+8 & \textbf{8.9351766e+8}\\ \hline
\end{tabular}
}
\end{center}
\end{footnotesize}
\caption{Experimental results concerning the Hypervolume indicator of the MOMKP instances.}
\label{hyperv}
\end{table}
Table \ref{cov} shows the obtained mean coverage values for each pair adduced as follows: the symboles
$\succeq$ and $\preceq$ refer to $C(own\ algo.,\ competing\ algo.)$ and $C(competing\ algo.,\ own\ algo.)$ respectively. The
results show that D/PHMOEA produces a better quality of Pareto fronts when compared to SPEA2, MOEA/D. However, PCPMOEA and MOFPA are shown to be the most competitive, especially for the smaller instances, although, the suggested algorithm maintained to be dominant, scoring an overall mean coverage values of
$78\%$ as dominant and $16\%$ as dominated.

\begin{table}[h]
\centering
\setlength{\tabcolsep}{0.3em}
\setlength{\arrayrulewidth}{.05em}
{\renewcommand{\arraystretch}{1.2}
\begin{footnotesize}
\begin{tabular}{cccccc}
\multirow{ 2}{*}{Instance} &  & \multicolumn{ 4}{c}{Algorithm}  \\\cline{3-6}
& & SPEA2 & MOEA/D & MOFPA & PCPMOEA\\ \hline
\multirow{ 1}{*}{250} & $\succeq$ & 1 & 0.9930 & 0.6664 & 0.5783 \\
						& $\preceq$ & 0 &	0 & 0.2123 & 0.3772 \\ \hline                        
\multirow{ 1}{*}{500} & $\succeq$ & 1& 0.9995& 0.8299 & 0.9177 \\
                        & $\preceq$ & 0& 0& 0.0981 & 0.0047\\ \hline
\multirow{ 1}{*}{750} & $\succeq$ & 1& 0.9985& 0.8697 &  0.8531\\
                        & $\preceq$ & 0& 0& 0.0885 & 0.1122 \\ \hline

\hline                                             
\multirow{ 2}{*}{Average} & $\succeq$ & 1 & 0.9970 & 0.7886 & 0.7830\\
						& $\preceq$ & 0 &	0 & 0.3989 &  0.1647 \\ \hline
\multicolumn{6}{l}{{\scriptsize The last two rows contain the mean values for each column. }}
\end{tabular}
\end{footnotesize}
}
\caption{ Coverage metric of the suggested algorithm against other competing algorithms.}
\label{cov}
\end{table}

Figure \ref{fig: ht} presents an illustrative example of the obtained results. The visual observation confirms the fact that the suggested algorithm is at least comparable to recent state-of-the-art algorithms. 

\begin{figure}[h]
\centering
\pgfplotsset{width=7cm,compat=newest}
\begin{tikzpicture}[scale = 0.9]
\begin{axis}[ 
    title={},
    xlabel={},
    ylabel={},
    xmin=22973, xmax=30126,
    ymin=22950, ymax=30035,
    x=0.014mm,
    legend pos=south west] 
\addplot[only marks, red,
    mark=square,mark=x]
    coordinates {
 (22973, 30035)  (23144, 30030)  (23215, 30028)  (23292, 30026)  (23422, 30018)  (23556, 30010)  (23717, 29997)  (23851, 29984)  (23898, 29979)  (24154, 29948)  (24095, 29957)  (24307, 29923)  (24560, 29878)  (24693, 29849)  (24696, 29848)  (24800, 29824)  (24912, 29797)  (24971, 29782)  (25220, 29714)  (25279, 29696)  (25445, 29645)  (25474, 29635)  (25514, 29624)  (25642, 29573)  (25823, 29495)  (25947, 29438)  (26071, 29379)  (26173, 29328)  (26242, 29289)  (26361, 29225)  (29282, 26116)  (29341, 25999)  (29377, 25918)  (29422, 25815)  (29419, 25825)  (29601, 25371)  (29660, 25209)  (29721, 25044)  (29774, 24884)  (29788, 24849)  (29838, 24675)  (29849, 24637)  (29863, 24587)  (29908, 24410)  (29930, 24323)  (29958, 24199)  (30001, 24007)  (30048, 23747)  (30044, 23775)  (30051, 23732)  (30089, 23468)  (30106, 23302)  (30112, 23238)  (30111, 23240)  (30120, 23135)  (30122, 23059)  (30122, 23059)  (30125, 22954)  (30126, 22950)  (26493, 29150)  (26573, 29101)  (26689, 29027)  (26861, 28914)  (26976, 28826)  (27066, 28756)  (27206, 28641)  (27440, 28445)  (27616, 28289)  (27652, 28255)  (27743, 28172)  (27837, 28081)  (27971, 27942)  (28093, 27812)  (28157, 27740)  (28447, 27411)  (28500, 27344)  (28625, 27185)  (28675, 27120)  (28725, 27054)  (28762, 27007)  (28894, 26798)  (28987, 26653)  (29063, 26520)  (29122, 26416)  (29246, 26190)  (29279, 26129)  (28559, 27254)  (28371, 27477)  (25900, 29458)  (29309, 26020)  (26803, 28955)  (27150, 28654)  (30027, 23808)  (29685, 25081)  (26375, 29206)  (26529, 29106)  (29125, 26387)  (28778, 26926)  (29515, 25556)  (29988, 24018)  (29740, 24931)  (27136, 28690)  (27974, 27899)  (27009, 28781)  (26656, 29032)  (29150, 26332)  (27093, 28712)  (27469, 28402)  (25457, 29640)  (27991, 27878)  (26516, 29115)  (27551, 28302)  (29891, 24430)  (29126, 26356)  (27716, 28173)  (28428, 27412)  (25387, 29658)  (26412, 29192)  (26548, 29104)  (26942, 28830)  (28569, 27228)  (28562, 27250)  (28475, 27364)  (28510, 27297)  (28304, 27506)  (27899, 27966)  (29972, 24105)  (24206, 29938)  (26873, 28887)  (26392, 29194)  (29541, 25489)  (27749, 28118)  (25603, 29578)  (28064, 27814)  (26437, 29162)  (28292, 27568)  (25591, 29589)  (28028, 27852)  (29452, 25720)  (27877, 28020)  (28222, 27604)  (27394, 28449)  (28188, 27663)  (27168, 28647)  (28764, 26953)  (28727, 27008)  (28936, 26660)  (28477, 27356)  (26931, 28846)  (24982, 29771)  (29315, 26015)  (29606, 25337)  (28017, 27871)  (28824, 26818)  (27508, 28367)  (26987, 28794)  (27894, 27967)  (29066, 26430)  (28407, 27433)  (28857, 26811)  (29531, 25529)  (27552, 28299)  (27547, 28343)  (27518, 28344)  (27377, 28475)  (27300, 28528)  (27840, 28047)  (28579, 27196)  (26192, 29310)  (29166, 26299)  (29638, 25237)  (27771, 28115)  (28118, 27748)  (26639, 29046)  (25834, 29491)  (24353, 29908)  (26307, 29250)  (28220, 27631)  (26503, 29137)  (27146, 28673)  (26989, 28784)  (26574, 29089)  (25162, 29724)  (28386, 27456)  (28045, 27821)  (26738, 28959)  (28538, 27258)  (27248, 28585)  (30073, 23494)  (30061, 23609)  (28034, 27851)  (26875, 28878)  (28908, 26707)  (28921, 26702)  (27792, 28087)  (28575, 27200)  (28413, 27418)  (25486, 29627)  (28591, 27189)  (25302, 29686)  (26706, 29015)  (27483, 28385)  (28231, 27603)  (29006, 26588)  (27994, 27876)  (28794, 26911)  (28524, 27286)  (28301, 27559)  (27215, 28608)  (28239, 27597)  (28110, 27773)  (28387, 27444)  (28278, 27588)  (26199, 29306)  (28820, 26883)  (27175, 28643)  (29943, 24200)  (26716, 29005)  (26612, 29068)  (25070, 29747)  (30027, 23808)  (27251, 28553)  (27688, 28190)  (27713, 28183)  (29162, 26319)  (28344, 27505)  (27387, 28473)  (27869, 28035)  (29203, 26239)  (27681, 28207)  (27323, 28510)  (27022, 28761)  (28779, 26915)  (29387, 25881)  (26300, 29254)  (26426, 29182)  (26174, 29319)  (26337, 29228)  (27388, 28455)  (29016, 26534)  (29461, 25710)  (28357, 27485)  (29748, 24918)  (29013, 26575)  (27339, 28496)  (27102, 28709)  (30032, 23789)  (30016, 23876)  (27892, 27974)  (26443, 29160)  (29705, 25058)  (26728, 28973)  (27090, 28716)  (29473, 25663)  (27980, 27879)  (27903, 27964)  (27473, 28397)  (26623, 29066)  (27889, 27984)  (27775, 28099)  (27322, 28512)  (27234, 28590)  (27349, 28491)  (29581, 25386)  (27556, 28295)  (27916, 27958)  (28916, 26706)  (27315, 28518)  (29886, 24454)  (27292, 28542)  (26923, 28853)  (29430, 25770)  (27265, 28548)  (28634, 27128)  (27020, 28765)  (29494, 25597)  (26894, 28874)  (27516, 28352)  (27456, 28406)  (24817, 29817)  (27678, 28225)  (27281, 28544)  (28932, 26683)  (28804, 26892)  (29136, 26339)  (27171, 28644)  (29739, 24935)  (29689, 25071)  (28635, 27123)  (27926, 27944)  (29178, 26275)  (26512, 29131)  (28198, 27636)  (28775, 26935)  (28185, 27668)  (29937, 24242)  (29651, 25234)  (29824, 24708)  (29351, 25959)  (25096, 29745)  (29632, 25276)  (29668, 25168)  (23987, 29967)  (29799, 24771)  (29755, 24907)  (30097, 23360)  (29550, 25452)  (29865, 24523)  (29346, 25979)  (29806, 24735)  (30072, 23528)  (29571, 25394)  (29386, 25895)  (29670, 25132)  (29426, 25776)  (23439, 30011)  (29909, 24329)  (30018, 23819)  (29570, 25424)  (29490, 25636)  (29363, 25941)  (25525, 29616)  (30010, 23899)  (29635, 25241)  (24256, 29924)  (29556, 25450)  (29577, 25387)  (29728, 24979)  (29802, 24739)  (29881, 24501)  (29839, 24670)  (29462, 25709)  (29841, 24645)  (29437, 25740)  (29669, 25157)  (25106, 29738)  (25227, 29707)  (29976, 24094)  (29479, 25647)  (29500, 25593)  (26221, 29296)  (29873, 24504)  (29762, 24891)  (29796, 24807)  (29533, 25526)  (29466, 25664)  (29183, 26261)  (29817, 24720)  (29811, 24722)  (29695, 25066)  (29680, 25118)  (25720, 29528)  (29978, 24061)  (29614, 25312)  (29735, 24971)  (25915, 29449)  (29184, 26255)  (29204, 26221)  (25378, 29664)  (29677, 25124)  (29299, 26078)  (29870, 24521)  (29507, 25574)  (29557, 25442)  (29366, 25922)  (29396, 25857)  (29684, 25106)  (29510, 25566)  (29619, 25293)  (24944, 29787)  (26329, 29242)  (29568, 25436)  (26229, 29295)  (29892, 24415)  (23912, 29974)  (25992, 29407)  (29547, 25457)  (29628, 25286)  (29353, 25946)  (29224, 26208)  (29967, 24130)  (29751, 24915)  (29258, 26149)  (29583, 25375)  (29723, 24983)  (29981, 24019)  (23936, 29969)  (24863, 29798)  (23565, 30005)  (25317, 29683)  (25645, 29564)  (25983, 29421)  (25426, 29648)  (24403, 29898)  (25333, 29674)  (25292, 29689)  (24862, 29809)  (25807, 29497)  (24659, 29852)  (24709, 29841)  (24699, 29845)  (26036, 29390)  (25690, 29544)  (26176, 29316)  (24602, 29866)  (25403, 29656)  (23788, 29985)  (25177, 29721)  (24947, 29783)  (26137, 29336)  (25244, 29698)  (26288, 29267)  (26182, 29315)  (24856, 29810)  (25731, 29527)  (25410, 29652)  (24761, 29830)  (24748, 29835)  (25613, 29577)  (25066, 29753)  (25789, 29498)  (25041, 29761)  (26088, 29364)  (24354, 29900)  (25756, 29516)  (24329, 29916)  (26153, 29335)  (25865, 29466)  (25772, 29509)  (25683, 29546)  (26017, 29404)  (25568, 29595)  (25433, 29646)  (26203, 29304)  (25349, 29666)  (25561, 29600)  (25101, 29739)  (25663, 29558)  (25157, 29726)  (24250, 29927)  (24376, 29899)  (24223, 29931)  (25045, 29756)  (25778, 29502)  (25539, 29606)  (25784, 29500)  (24518, 29883)  (25969, 29422)  (24633, 29855)  (25344, 29671)  (25321, 29675)  (23744, 29987)  (25142, 29729)  (25231, 29706)  (25854, 29483)  (25674, 29555)  (25988, 29408)  (25238, 29704)  (26314, 29244)  (24979, 29776)  (25550, 29605)  (25569, 29594)  (25925, 29442)  (25574, 29591)  (26001, 29406)  (25987, 29412)  (25131, 29732)  (26092, 29352)  (25321, 29675)  (25752, 29517)  (25733, 29526)  (25872, 29464)  (24017, 29960)  (24013, 29965)  (25602, 29586)  (25178, 29720)  (25717, 29539)  (25115, 29733)  (25346, 29669)  (25869, 29465)  (24763, 29827)  (25676, 29549)  (25956, 29432)  (24628, 29859)  (24996, 29767)  (25004, 29766)  (25888, 29461)  (26091, 29354)  (25485, 29629)  (25655, 29562)  (24991, 29768)  (26258, 29279)  (24772, 29826)  (25746, 29524)  (26135, 29342)  (26031, 29394)  (25097, 29741)  (25855, 29479)  (25475, 29631)  (25763, 29511)  (23608, 30004)  (25528, 29608)  (25959, 29426)  (26184, 29312)  (26049, 29381)  (25318, 29680)  (25862, 29475)  (25454, 29641)  (25704, 29542)  (24725, 29837)  (25358, 29665)  (25913, 29450)  (26125, 29350)  (24755, 29832)  (25052, 29755)  (26048, 29385)  (26079, 29371)  (24480, 29884)  (25469, 29637)  (24442, 29895)  (24463, 29889)  (26090, 29358)  };
    \addlegendentry{{\footnotesize D/PHMOEA}}
    
    \addplot[blue, only marks,
    mark=square,mark=x]
    coordinates {
(25558, 29603)  (25890, 29423)  (29059, 26003)  (25457, 29640)  (27883, 27771)  (28822, 26525)  (28206, 27465)  (26796, 28854)  (27695, 27908)  (24683, 29836)  (24546, 29876)  (24161, 29941)  (29502, 24883)  (27305, 28312)  (24500, 29878)  (26947, 28573)  (26011, 29387)  (28921, 26326)  (28968, 26227)  (27750, 27854)  (23386, 30017)  (26939, 28575)  (28243, 27444)  (27956, 27686)  (28419, 27092)  (28333, 27267)  (28288, 27331)  (27140, 28472)  (27045, 28549)  (25761, 29498)  (26091, 29352)  (24377, 29902)  (24307, 29923)  (26859, 28760)  (25123, 29737)  (28410, 27253)  (23948, 29971)  (23793, 29985)  (29062, 25998)  (26710, 28902)  (25233, 29701)  (24995, 29769)  (26386, 29197)  (24876, 29804)  (24333, 29915)  (25151, 29723)  (26190, 29308)  (26541, 29059)  (24973, 29775)  (25816, 29470)  (26282, 29261)  (25871, 29453)  (26501, 29114)  (29815, 23454)  (25528, 29606)  (29763, 23675)  (29742, 23828)  (28712, 26648)  (26738, 28864)  (29150, 25953)  (29451, 24889)  (24042, 29956)  (29267, 25323)  (26717, 28868)  (25580, 29577)  (26504, 29096)  (29305, 25208)  (26652, 28954)  (27229, 28403)  (27369, 28229)  (26838, 28812)  (27615, 28168)  (29615, 24661)  (26610, 29028)  (29817, 23421)  (28498, 26918)  (25488, 29626)  (25623, 29568)  (26407, 29157)  (24803, 29821)  (26671, 28932)  (26739, 28858)  (29039, 26096)  (28542, 26822)  (26276, 29267)  (25496, 29613)  (25290, 29679)  (25097, 29741)  (24190, 29928)  (25626, 29562)  (25588, 29575)  (26118, 29344)  (25633, 29561)  (23723, 29988)  (26932, 28717)  (27308, 28237)  (27940, 27746)  (26655, 28946)  (26786, 28856)  (28769, 26623)  (28861, 26446)  (26144, 29330)  (29432, 24995)  (24772, 29824)  (25041, 29761)  (26130, 29331)  (26036, 29370)  (23738, 29986)  (24376, 29904)  (29767, 23567)  (24336, 29914)  (29876, 23248)  (29871, 23314)  (26250, 29275)  (25218, 29711)  (26589, 29051)  (23317, 30021)  (26230, 29297)  (23390, 30015)  (24489, 29886)  (23827, 29984)  (29169, 25589)  (26711, 28878)  (25004, 29763)  (25158, 29713)  (25566, 29589)  (24171, 29937)  (25045, 29753)  (24556, 29869)  (26176, 29327)  (26264, 29270)  (24993, 29770)  (26286, 29258)  (24404, 29897)  (26527, 29081)  (26180, 29318)  (29676, 24447)  (29726, 24013)  (26434, 29147)  (24807, 29819)  (28666, 26809)  (28532, 26865)  (29239, 25569)  (28434, 27060)  (28826, 26485)  (25152, 29719)  (26495, 29116)  (29646, 24472)  (25094, 29747)  (26375, 29213)  (25291, 29676)  (25374, 29655)  (26248, 29285)  (25718, 29518)  (24996, 29767)  (25338, 29670)  (24912, 29796)  (25600, 29572)  (24446, 29892)  (23292, 30026)  (25905, 29419)  (25954, 29394)  (24138, 29947)  (24464, 29887)  (26307, 29240)  (25352, 29662)  (24716, 29836)  (25726, 29505)  (28713, 26628)  (26154, 29328)  (29391, 25001)  (26090, 29357)  (29904, 22795)  (29284, 25286)  (29552, 24773)  (24937, 29779)  (24644, 29854)  (24659, 29843)  (29564, 24735)  (29682, 24048)  (29251, 25397)  (23565, 30005)  (24835, 29814)  (29349, 25141)  (29385, 25081)  (29367, 25112)  (26347, 29216)  (24598, 29864)  (24209, 29926)  (23996, 29965)  (24116, 29950)  (25666, 29560)  (25261, 29690)  (29583, 24730)  (24183, 29935)  (25686, 29521)  (29308, 25156)  (23619, 30002)  (25473, 29630)  (24756, 29830)  (29240, 25418)  (29764, 23633)  (24836, 29813)  (24924, 29783)  (24647, 29849)  (29751, 23702)  (24019, 29960)  (24327, 29918)  (24350, 29908)  (26303, 29248)  (23672, 29994)  (23533, 30006)  (29821, 23346)  (29809, 23563)  (26465, 29118)  (25922, 29416)  (25278, 29688)  (23504, 30010)  (23714, 29989)  (23665, 29995)  (23948, 29967)  (23849, 29974)  (25992, 29389)  (24497, 29880)  (29603, 24699)  (25573, 29580)  (23106, 30027)  (25377, 29652)  (25391, 29649)  (25581, 29575)  (29261, 25373)  (24068, 29956)  (26023, 29382)  (25819, 29464)  (25501, 29608)  (23836, 29982)  (29619, 24615)  (24986, 29771)  (24934, 29780)  (24669, 29842)  (26044, 29364)  (29293, 25225)  (29613, 24676)  (23651, 29996)  (25953, 29407)  (26637, 28974)  (26330, 29218)  (29906, 22660)  (23414, 30011)  (24564, 29865)  (25788, 29472)  (25048, 29750)  };
    \addlegendentry{{\footnotesize MOFPA}}


\addplot[green, only marks,
    mark=square,mark=x]
    coordinates {
(23028, 30021)  (23085, 30020)  (23125, 30019)  (23162, 30017)  (23221, 30015)  (23282, 30014)  (23295, 30012)  (23333, 30009)  (23338, 30007)  (23347, 30005)  (23390, 30004)  (23413, 30002)  (23455, 29999)  (23491, 29995)  (23533, 29991)  (23543, 29989)  (23627, 29984)  (23638, 29981)  (23732, 29975)  (23736, 29968)  (23737, 29962)  (23775, 29957)  (23831, 29952)  (23914, 29944)  (23934, 29941)  (23957, 29926)  (23997, 29925)  (24001, 29916)  (24085, 29910)  (24169, 29902)  (24193, 29894)  (24233, 29877)  (24246, 29858)  (24248, 29857)  (24256, 29856)  (24284, 29854)  (24330, 29852)  (24336, 29846)  (24372, 29843)  (24393, 29842)  (24542, 29830)  (24549, 29827)  (24614, 29800)  (24621, 29794)  (24654, 29781)  (24657, 29777)  (24696, 29776)  (24860, 29767)  (24914, 29736)  (24916, 29726)  (25041, 29713)  (25072, 29689)  (25081, 29686)  (25082, 29680)  (25211, 29674)  (25302, 29633)  (25309, 29616)  (25315, 29611)  (25364, 29598)  (25389, 29595)  (25414, 29592)  (25497, 29569)  (25548, 29544)  (25558, 29533)  (25560, 29532)  (25565, 29524)  (25666, 29511)  (25716, 29493)  (25742, 29454)  (25759, 29453)  (25786, 29445)  (25800, 29424)  (25887, 29421)  (25969, 29384)  (25983, 29369)  (26007, 29345)  (26031, 29336)  (26063, 29323)  (26075, 29306)  (26104, 29299)  (26138, 29286)  (26148, 29262)  (26180, 29259)  (26195, 29236)  (26205, 29231)  (26215, 29228)  (26218, 29225)  (26231, 29224)  (26250, 29219)  (26265, 29205)  (26293, 29197)  (26311, 29180)  (26312, 29174)  (26336, 29172)  (26366, 29170)  (26385, 29160)  (26394, 29155)  (26413, 29149)  (26445, 29128)  (26446, 29126)  (26452, 29107)  (26456, 29105)  (26478, 29103)  (26479, 29085)  (26486, 29083)  (26530, 29079)  (26545, 29061)  (26546, 29055)  (26557, 29052)  (26567, 29042)  (26577, 29033)  (26614, 29030)  (26624, 29023)  (26645, 29008)  (26671, 28999)  (26694, 28984)  (26713, 28956)  (26746, 28953)  (26778, 28915)  (26805, 28900)  (26847, 28889)  (26854, 28871)  (26876, 28855)  (26879, 28848)  (26901, 28838)  (26931, 28828)  (26936, 28814)  (26958, 28809)  (26995, 28788)  (27027, 28731)  (27050, 28730)  (27052, 28718)  (27069, 28706)  (27082, 28699)  (27083, 28682)  (27110, 28680)  (27121, 28668)  (27130, 28662)  (27133, 28653)  (27147, 28646)  (27150, 28640)  (27156, 28637)  (27177, 28629)  (27192, 28627)  (27214, 28598)  (27219, 28573)  (27236, 28569)  (27238, 28566)  (27252, 28559)  (27259, 28556)  (27264, 28543)  (27271, 28542)  (27300, 28528)  (27302, 28510)  (27332, 28507)  (27353, 28496)  (27360, 28473)  (27378, 28465)  (27387, 28459)  (27394, 28444)  (27440, 28415)  (27459, 28386)  (27472, 28372)  (27486, 28370)  (27497, 28365)  (27514, 28340)  (27530, 28335)  (27532, 28326)  (27542, 28315)  (27558, 28314)  (27560, 28287)  (27580, 28283)  (27591, 28272)  (27608, 28253)  (27615, 28243)  (27619, 28239)  (27622, 28238)  (27629, 28234)  (27659, 28211)  (27671, 28192)  (27685, 28179)  (27694, 28174)  (27701, 28147)  (27717, 28146)  (27720, 28133)  (27721, 28127)  (27739, 28124)  (27758, 28118)  (27760, 28101)  (27764, 28098)  (27768, 28092)  (27784, 28088)  (27800, 28078)  (27803, 28068)  (27810, 28060)  (27811, 28054)  (27821, 28052)  (27840, 28035)  (27849, 28020)  (27851, 28001)  (27859, 27998)  (27865, 27996)  (27868, 27994)  (27878, 27990)  (27885, 27981)  (27895, 27972)  (27915, 27960)  (27921, 27940)  (27923, 27939)  (27926, 27924)  (27930, 27919)  (27950, 27918)  (27952, 27904)  (27961, 27890)  (27980, 27888)  (28004, 27870)  (28007, 27864)  (28017, 27841)  (28018, 27829)  (28032, 27827)  (28061, 27810)  (28069, 27803)  (28086, 27788)  (28091, 27761)  (28097, 27757)  (28102, 27738)  (28121, 27737)  (28131, 27706)  (28134, 27695)  (28139, 27692)  (28141, 27691)  (28142, 27688)  (28159, 27686)  (28172, 27676)  (28188, 27665)  (28190, 27653)  (28200, 27637)  (28207, 27636)  (28212, 27608)  (28216, 27607)  (28242, 27592)  (28243, 27575)  (28254, 27571)  (28259, 27554)  (28269, 27548)  (28278, 27534)  (28288, 27527)  (28308, 27526)  (28323, 27497)  (28327, 27488)  (28334, 27475)  (28351, 27458)  (28361, 27452)  (28362, 27448)  (28365, 27437)  (28369, 27431)  (28395, 27416)  (28396, 27396)  (28398, 27395)  (28402, 27389)  (28426, 27385)  (28428, 27356)  (28440, 27351)  (28442, 27346)  (28454, 27335)  (28457, 27333)  (28484, 27303)  (28505, 27290)  (28520, 27261)  (28524, 27233)  (28533, 27229)  (28541, 27222)  (28544, 27212)  (28562, 27207)  (28571, 27197)  (28572, 27187)  (28583, 27170)  (28584, 27167)  (28593, 27145)  (28626, 27138)  (28637, 27103)  (28651, 27086)  (28658, 27075)  (28662, 27053)  (28676, 27042)  (28686, 27027)  (28704, 27018)  (28722, 26986)  (28739, 26974)  (28755, 26914)  (28760, 26908)  (28763, 26906)  (28768, 26900)  (28788, 26881)  (28802, 26841)  (28806, 26824)  (28817, 26805)  (28818, 26790)  (28831, 26782)  (28837, 26759)  (28848, 26757)  (28865, 26740)  (28873, 26730)  (28897, 26690)  (28903, 26657)  (28909, 26656)  (28930, 26638)  (28933, 26633)  (28942, 26615)  (28979, 26593)  (28989, 26523)  (28994, 26511)  (28996, 26461)  (29003, 26459)  (29014, 26456)  (29015, 26438)  (29022, 26435)  (29039, 26422)  (29039, 26422)  (29046, 26416)  (29049, 26394)  (29052, 26390)  (29059, 26372)  (29081, 26360)  (29088, 26341)  (29095, 26324)  (29100, 26289)  (29102, 26274)  (29105, 26271)  (29110, 26268)  (29115, 26258)  (29139, 26257)  (29140, 26234)  (29145, 26218)  (29172, 26214)  (29182, 26138)  (29186, 26132)  (29190, 26120)  (29191, 26108)  (29193, 26103)  (29195, 26098)  (29227, 26094)  (29228, 26057)  (29232, 26013)  (29256, 26002)  (29263, 25979)  (29270, 25972)  (29271, 25950)  (29279, 25945)  (29293, 25926)  (29314, 25911)  (29317, 25894)  (29326, 25851)  (29332, 25848)  (29342, 25831)  (29357, 25798)  (29381, 25782)  (29398, 25734)  (29399, 25670)  (29407, 25661)  (29408, 25631)  (29412, 25626)  (29420, 25619)  (29427, 25607)  (29435, 25596)  (29445, 25587)  (29448, 25575)  (29457, 25557)  (29476, 25545)  (29483, 25501)  (29506, 25496)  (29509, 25390)  (29519, 25374)  (29523, 25372)  (29536, 25369)  (29545, 25332)  (29560, 25301)  (29576, 25216)  (29578, 25202)  (29582, 25189)  (29594, 25160)  (29598, 25155)  (29599, 25114)  (29606, 25107)  (29616, 25087)  (29635, 25062)  (29652, 25037)  (29662, 25034)  (29672, 24934)  (29673, 24931)  (29677, 24930)  (29691, 24929)  (29720, 24900)  (29721, 24849)  (29725, 24812)  (29727, 24809)  (29735, 24785)  (29743, 24758)  (29748, 24731)  (29753, 24704)  (29785, 24675)  (29789, 24596)  (29803, 24555)  (29810, 24507)  (29813, 24479)  (29820, 24468)  (29826, 24449)  (29865, 24434)  (29881, 24344)  (29886, 24248)  (29890, 24230)  (29895, 24210)  (29896, 24179)  (29903, 24175)  (29919, 24147)  (29920, 24080)  (29930, 24074)  (29949, 24051)  (29960, 23955)  (29965, 23942)  (29967, 23894)  (29968, 23858)  (29979, 23849)  (29988, 23822)  (30000, 23813)  (30003, 23751)  (30010, 23714)  (30012, 23704)  (30015, 23686)  (30032, 23679)  (30043, 23589)  (30048, 23555)  (30049, 23550)  (30055, 23515)  (30057, 23509)  (30060, 23481)  (30061, 23468)  (30063, 23452)  (30068, 23440)  (30079, 23398)  (30081, 23365)  (30086, 23356)  (30087, 23306)  (30088, 23291)  (30091, 23249)  (30093, 23243)  (30094, 23237)  (30097, 23229)  (30098, 23217)  (30100, 23213)  (30104, 23199)  (30105, 23172)  (30107, 23143)  (30108, 23084)  (30111, 23078)  (30112, 23051)  (30115, 22991)  };
    \addlegendentry{{\footnotesize PCPMOEA}}

\addplot[gray, only marks,
    mark=x]
    coordinates {
(29985, 22725)  (27255, 27801)  (23485, 29827)  (23070, 29954)  (28583, 26417)  (23106, 29943)  (23175, 29940)  (29234, 25146)  (29290, 25115)  (28261, 26868)  (27065, 28035)  (29340, 24964)  (27233, 27846)  (28164, 26959)  (27588, 27496)  (27510, 27597)  (25570, 29213)  (28503, 26567)  (23865, 29725)  (28470, 26577)  (29228, 25295)  (28517, 26513)  (25317, 29379)  (25585, 29174)  (28226, 26921)  (29994, 22706)  (29427, 24671)  (29686, 23970)  (27353, 27701)  (26522, 28537)  (24705, 29515)  (27697, 27411)  (28568, 26435)  (25437, 29304)  (27249, 27805)  (28521, 26474)  (28398, 26735)  (29358, 24771)  (25767, 29075)  (29555, 24374)  (25393, 29328)  (27068, 28024)  (29511, 24592)  (27324, 27790)  (25032, 29409)  (25461, 29269)  (26514, 28554)  (29475, 24617)  (30015, 22594)  (27022, 28066)  (24483, 29614)  (24218, 29615)  (27568, 27522)  (24118, 29672)  (26980, 28169)  (25500, 29230)  (25730, 29170)  (27183, 27953)  (29975, 22838)  (28740, 26141)  (29428, 24663)  (29666, 24021)  (29688, 23858)  (25021, 29449)  (25598, 29172)  (26992, 28104)  (29312, 24998)  (29412, 24744)  (29413, 24728)  (30016, 22522)  (24147, 29664)  (26864, 28249)  (27456, 27677)  (27543, 27560)  (26822, 28280)  (28810, 26028)  (25745, 29130)  (28083, 27126)  (29737, 23837)  (23020, 29957)  (27272, 27792)  (27155, 27977)  (23471, 29887)  (28674, 26294)  (28436, 26670)  (23015, 29969)  (24751, 29469)  (25444, 29277)  (24734, 29508)  (27340, 27744)  (28917, 25968)  (26918, 28208)  (29605, 24060)  (27966, 27142)  (29303, 25066)  (29926, 23203)  (29527, 24397)  (23547, 29824)  (29694, 23855)  (26513, 28663)  (28700, 26201)  (28989, 25710)  (28974, 25822)  (27798, 27363)  (29368, 24767)  (29398, 24757)  (28803, 26126)  (26734, 28461)  (28299, 26796)  (22922, 29971)  (28031, 27129)  (24612, 29550)  (26345, 28725)  (29058, 25597)  (27671, 27417)  (28585, 26392)  (28979, 25725)  (24543, 29557)  (29345, 24867)  (27359, 27686)  (29195, 25310)  (29973, 23175)  (29991, 22722)  (26452, 28701)  (27030, 28055)  (27918, 27226)  (23857, 29802)  (23900, 29698)  (28955, 25932)  (27927, 27213)  (29809, 23712)  (25930, 29023)  (26577, 28505)  (29603, 24189)  (30011, 22680)  (29894, 23319)  (27824, 27284)  (29821, 23554)  (24499, 29572)  (28545, 26445)  (28804, 26038)  (29810, 23640)  (24063, 29696)  (28145, 26979)  (29523, 24413)  (26768, 28400)  (25770, 29060)  (29756, 23744)  (24202, 29653)  (26132, 28944)  (27655, 27486)  (27913, 27230)  (29041, 25606)  (29145, 25372)  (26436, 28704)  (26832, 28250)  (28826, 26005)  (29121, 25557)  (29847, 23468)  (26039, 29022)  (25300, 29389)  (28658, 26381)  (29144, 25542)  (29560, 24194)  (29867, 23334)  (26199, 28840)  };
    \addlegendentry{{\footnotesize MOEA/D}}
    
        \addplot[black, only marks,
    mark=x]
    coordinates {
    (26632, 27769)  (26713, 27729)  (26786, 27653)  (26816, 27636)  (26889, 27630)  (26933, 27612)  (26968, 27591)  (26998, 27505)  (27222, 27450)  (27246, 27380)  (27309, 27320)  (27355, 27303)  (27371, 27167)  (27434, 27138)  (27528, 27102)  (27563, 27073)  (27568, 27066)  (27717, 27054)  (27793, 26988)  (27799, 26801)  (27810, 26759)  (27880, 26703)  (27904, 26565)  (27905, 26478)  (27927, 26434)  (27943, 26411)  (27954, 26401)  (28049, 26391)  (28069, 26389)  (28080, 26274)  (28100, 26248)  (28104, 25851)  (28137, 25755)  };
    \addlegendentry{{\footnotesize SPEA2}}
 \end{axis}
\end{tikzpicture}
\caption{Illustrative example of the obtained approximated Pareto fronts using SPEA2, MOEA/D, MOFPA, PCPMOEA, and D/PHMOEA.}
\label{fig: ht}
\end{figure}


 
\section{conclusions}

In this paper, we presented a parallel two-phase type algorithm with an application to the multiobjective multidimensional Kanapsack Problem, called Decomposition based Parallel Hybrid MOEA (D/PHMOEA). The suggested algorithm is a hybrid algorithm, combining an exact method for finding the set of supported solutions, and a parallel MOEA with weighted-criteria selection operator, designed in a master/worker paradigm, as to target specific regions of the true Pareto set. The suggested algorithm has been assessed against state-of-the-art algorithms with different search strategies. The approach has shown conclusive results regarding the convergence and diversity of the evolved solutions. 


\begin{thebibliography}{99}

\bibitem{3}
LUST, Thibaut et TEGHEM, Jacques. The multiobjective multidimensional knapsack problem: a survey and a new approach. \textit{International Transactions in Operational Research}, 2012, vol. 19, no 4, p. 495-520.


\bibitem{6} DEB, Kalyanmoy, PRATAP, Amrit, AGARWAL, Sameer, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. \textit{IEEE transactions on evolutionary computation}, 2002, vol. 6, no 2, p. 182-197.

\bibitem{7} ZITZLER, Eckart, LAUMANNS, Marco, et THIELE, Lothar. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report, 2001, vol. 103.

\bibitem{8} ZHANG, Qingfu et LI, Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 2007, vol. 11, no 6, p. 712-731.

\bibitem{11} BRANKE, Jürgen, BRANKE, Jurgen, DEB, Kalyanmoy, et al. (ed.). Multiobjective optimization: Interactive and evolutionary approaches. Springer Science \& Business Media, 2008.

\bibitem{15} R. Karp. Reducibility among combinatorial problems. Miller R.E. \& Thatcher, J.W.(eds.) Complexity of Computer Computations, Plenum Press, New York, page 85-103,
1972.

\bibitem{16} ZITZLER, Eckart et THIELE, Lothar. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 1999, vol. 3, no 4, p. 257-271.

\bibitem{35} GEOFFRION, Arthur M. Proper efficiency and the theory of vector maximization. \textit{Journal of mathematical analysis and applications}, 1968, vol. 22, no 3, p. 618-630.

\bibitem{36} ANEJA, Yash P. et NAIR, Kunhiraman PK. Bicriteria transportation problem. \textit{Management Science}, 1979, vol. 25, no 1, p. 73-78.

\bibitem{37} BAZGAN, Cristina, HUGOT, Hadrien, et VANDERPOOTEN, Daniel. Solving efficiently the 0-1 multi-objective knapsack problem. \textit{Computers \& Operations Research}, 2009, vol. 36, no 1, p. 260-279.

\bibitem{39} KANTOUR, Nedjmeddine, BOUROUBI, Sadek, et CHAABANE, Djamal. A parallel MOEA with criterion-based selection applied to the Knapsack Problem. \textit{Applied Soft Computing}, 2019, vol. 80, p. 358-373.

\bibitem{40} ZOUACHE, Djaafar, MOUSSAOUI, Abdelouahab, et ABDELAZIZ, Fouad Ben. A cooperative swarm intelli-
gence algorithm for multi-objective discrete optimization with application to the knapsack problem. \textit{European Journal of Operational Research}, 2018, vol. 264, no 1, p. 74-88.

\bibitem{43} VAN VELDHUIZEN, David A. et LAMONT, Gary B. On measuring multiobjective evolutionary algorithm
performance. In : Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. IEEE, 2000. p.
204-211.

\end{thebibliography}

\end{document}



