∎

11institutetext: Talat Nazir, 22institutetext: Department of Mathematical
Sciences, University of South Africa, Florida 0003, South Africa.
22email<EMAIL_ADDRESS>33institutetext: Sergei Silvestrov
44institutetext: Division of Mathematics and Physics, School of Education,
Culture and Communication, Mälardalen University, Box 883, 72123 Västerås,
Sweden.
44email<EMAIL_ADDRESS>
# Fixed point results for Prešić type contractive mappings in $b$-metric
spaces

Talat Nazir  Sergei Silvestrov

###### Abstract

The fixed point results for generalized Prešić type mappings in the setup of
$b$-metric spaces are obtained. The stability of fixed point set of Prešić
type mappings is also established. Several examples are also presented to
illustrate the validity of the main results.
MSC 2020 Classification: 47H10, 54C60, 54H25

###### Keywords:

Prešić type mapping, fixed point, generalized contraction, $b$-metric space

##  1 Introduction to Prešić type Mappings and Fixed Points

The study of fixed point of maps with certain type of contractive restrictions
is a powerful approach towards solving variety of scientific problems in
various areas of mathematics as well as important methodology for
computational algorithms in the natural sciences and engineering subjects.

Banach contraction principle Banach  is a simple powerful result with a wide
range of applications, including iterative methods for solving linear,
nonlinear, differential, integral, and difference equations. Banach Banach
initiated the study of fixed point theory for contraction mappings. There are
several generalizations and extensions of the Banach contraction principle in
the existing literature. Let us firstly recall the Banach contraction
principle. Henceforth, $\mathbb{R}$, $\mathbb{R}_{\geq 0}$, $\mathbb{R}_{>0}$,
$\mathbb{Z}_{\geq 0}$ and $\mathbb{Z}_{>0}$ denote the sets of real numbers,
non-negative real numbers, positive real numbers, non-negative integers and
positive integers, respectively.

######  Theorem 1.1 (Banach contraction principle, Banach )

If $(X,d)$ is a complete metric space and mapping $f:X\rightarrow X$ satisfies

$d(fx,fy)\leq\eta\,d(x,y),\ \text{for all }x,y\in X,$

where $0\leq\eta<1$, then there exists a unique $u\in X$ that satisfies
$u=fu$. Moreover, for any $x_{0}\in X$, the iterative sequence
$x_{n+1}=f\left(x_{n}\right)$ converges to $u$.

Let $f:X^{k}\rightarrow X$, where $k\in\mathbb{Z}_{>0}$. A point $x^{\ast}\in
X$ is called a fixed point of $f$ if $f(x^{\ast},\ldots,x^{\ast})=x^{\ast}$.
Consider the possibly non-linear $k$-th order difference equation

$x_{n+k}=f(x_{n},\ldots,x_{n+k-1}),\,\,n=1,2,\ldots$ (1)

with the initial values $x_{1},\ldots,x_{k}\in X$. The difference equation (1)
can be studied by means of fixed point theory in view of the fact that
$x^{\ast}$ in $X$ is a solution of (1) if and only if $x^{\ast}$ is a fixed
point of the self-mapping $F:X\rightarrow X$ given by

$F(x)=f(x,\ldots,x),\ \text{for all}\ x\in X.$

One of the most important results in this direction is obtained by Prešić
Presic .

###### Theorem 1.2

Let $(X,d)$ be a complete metric space, $k\in\mathbb{Z}_{>0}$, and let
$f:X^{k}\rightarrow X$ be a mapping satisfying the following contractive type
condition

$d(f(x_{1},\ldots,x_{k}),f(x_{2},\ldots,x_{k+1}))\leq\sum\limits_{j=1}^{k}r_{j}d(x_{j},x_{j+1}),$

for every $x_{1},\ldots,x_{k+1}\in X$, where
$r_{1},\ldots,r_{k}\in\mathbb{R}_{\geq 0}$ are non-negative constants such
that $r_{1}+\ldots+r_{k}<1$. Then there exists a unique point $u\in X$ such
that $f(u,\ldots,u)=u$. Moreover, for any arbitrary points
$x_{1},\ldots,x_{k}\in X$, the sequence (1) converges to $u$.

It is easy to show that for $k=1$, Theorem 1.2 reduces to the Banach
contraction principle.

Ćirić and Prešić CiricPresic07  generalized the above theorem as follows.

###### Theorem 1.3

Let $(X,d)$ be a complete metric space, $k\in\mathbb{Z}_{>0}$, and let
$f:X^{k}\rightarrow X$ be a mapping satisfying the following contractive type
condition

$d(f(x_{1},\ldots,x_{k}),f(x_{2},\ldots,x_{k+1}))\leq\kappa\max\\{d(x_{1},x_{2}),\ldots,d(x_{j},x_{j+1}),\ldots,d(x_{k},x_{k+1})\\},$

for every $x_{1},\ldots,x_{k+1}\in X$, where $0<\kappa<1$ is a constant. Then
there exists $u\in X$ such that $f(u,\ldots,u)=u$. Moreover, for any arbitrary
points $x_{1},\ldots,x_{k}\in X$, the sequence (1) is convergent and

$\lim\limits_{n\rightarrow\infty}x_{n}=f(\lim\limits_{n\rightarrow\infty}x_{n},\ldots,\lim\limits_{n\rightarrow\infty}x_{n}).$

If in addition we suppose that

$d(f(x,\ldots,x),f(y,\ldots,y))<d(x,y)$

for all $x,y\in X$ with $x\neq y$, then $u$ is the unique point in $X$ with
$u=f(u,u,\dots,u)$.

Abbas at al. AIN15  extended Theorem 1.2 and Theorem 1.3, and proved the
following results for Prešić type weakly contractive mappings.

###### Theorem 1.4

Let $(X,d)$ be a complete metric space, $k\in\mathbb{Z}_{>0}$ and
$f:X^{k}\rightarrow X$ be a mapping. If there exists a lower semi-continuous
function $\phi:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ with
$\phi(t)=0$ only for $t=0$, such that

$d(f(x_{1},x_{2},\ldots,x_{k}),f(x_{2},x_{3},\ldots,x_{k+1}))\\\
\leq\max\\{d(x_{i},x_{i+1}):1\leq i\leq
k\\}-\phi(\max\\{d(x_{i},x_{i+1}):1\leq i\leq k\\}),$

for all $(x_{1},\ldots,x_{k+1})\in X^{k+1}$, then, for any points
$x_{1},\ldots,x_{k}\in X$, the sequence $\\{x_{n}\\}_{n\geq 1}$ defined by (1)
converges to $u\in X$ when $n\to\infty$, and $u$ is a fixed point of $f$, that
is, $u=f(u,\dots,u)$. If, moreover,

$d(f(x,\dots,x),f(y,\dots,y))=d(x,y)-\phi(d(x,y)),$

for all $x,y\in X$ with $x\neq y$, then $u$ is the unique fixed point of $f$.

##  2 $b$-Metric Spaces

Czerwik introduced $b$-metric spaces as generalization of metric spaces, first
for special case $b=2$ in C93  in 1993, and then for arbitrary real $b\geq 1$
in C98  in 1998. In $b$-metric space, the triangular inequality involves a
constant $b\geq 1$ called $b$-metric constant.

###### Definition 1

Let $X\neq\emptyset$ be a set, and $b\in\mathbb{R}$, $b\geq 1$. A mapping
$d:X\times X\rightarrow\mathbb{R}_{\geq 0}$ is called a $b$-metric on $X$ if
for any $x,y,z\in X,$ the following conditions hold:

  1. (b1)

$d(x,y)=0$ if and only if $x=y,$

  2. (b2)

$d(x,y)=d(y,x),$

  3. (b3)

$d(x,y)\leq b\left(d(x,z)+d(z,y)\right).$

The pair $(X,d)$ is called a $b$-metric space with parameter
$b\in\mathbb{R}_{\geq 1}$.

Note that, if $b=1,$ the Definition 1 coincides with that of a metric space.

###### Example 1

(RPA14 ) Let $(X,d)$ be a metric space, and $\rho(x,y)=(d(x,y))^{p},$ where
$p\in\mathbb{R}$, $p>1$. Then $\rho$ is a $b$-metric with $b=2^{p-1}.$
Obviously, the conditions (b1) and (b2) in the Definition 1 are satisfied. If
$p\in\mathbb{R},p>1$ then the convexity of the function $f(x)=x^{p}$ on
$\mathbb{R}_{>0}$ implies

$\left(\frac{a+b}{2}\right)^{p}\leq\frac{1}{2}\left(a^{p}+b^{p}\right),$

and hence, $\left(a+b\right)^{p}\leq 2^{p-1}(a^{p}+b^{p})$. This inequality
and $f(x)=x^{p}$ being monotonically increasing on $\mathbb{R}_{>0}$ yield,
for all $x,y,z\in X$,

$\displaystyle\rho(x,y)$ $\displaystyle=$
$\displaystyle(d(x,y))^{p}\leq(d(x,z)+d(z,y))^{p}$ $\displaystyle\leq$
$\displaystyle 2^{p-1}(d(x,z)^{p}+d(z,y)^{p})$ $\displaystyle=$ $\displaystyle
2^{p-1}(\rho(x,z)+\rho(z,y)).$

So, the condition (b3) also holds, and hence $\rho$ is a $b$-metric on $X$
with $b=2^{p-1}$.

###### Example 2

If $X=\mathbb{R}$ and $d(x,y)=|x-y|$ is the usual Euclidean metric, then
$\rho(x,y)=(x-y)^{2}$ is a $b$-metric on $\mathbb{R}$ with $b=2,$ but is not a
metric on $\mathbb{R}$.

###### Example 3

(Bakhtin09 ) The space

$l_{p}=\\{\\{x_{n}\\}_{n\geq
1}\subset\mathbb{R}\mid\sum_{n=1}^{\infty}\left|x_{n}\right|^{p}<\infty\\},\
\text{for }0<p<1$

is a $b$-metric space with $b=2^{\frac{1}{p}}$ and the $b$-metric
$d:l_{p}\times l_{p}\rightarrow\mathbb{R}_{\geq 0}$ defined by

$d(x,y)=\left[\sum_{n=1}^{\infty}\left|x_{n}-y_{n}\right|^{p}\right]^{\frac{1}{p}}.$

For $p\geq 1$, it is a metric space, and hence, it is a $b$-metric space for
all $p>0$.

###### Example 4

((Koethe69TopvectspI, , §15.9, pages 157-158),
(BerghLofstrbook76InterpolatSps, , Lemma 3.10.3, pages 61-62)) For a measure
space $(\Omega,\mu)$ with finite measure $\mu$, the $L_{p}(\mu)$-space of the
equivalence classes of measurable functions $x:\Omega\rightarrow\mathbb{R}$,
satisfying $\int\limits_{\Omega}|x(t)|^{p}dt<\infty$ (with the equivalence
relation given by equality of functions up to $\mu$-measure zero), is a
$b$-metric space with $b=2^{\frac{1}{p}-1}$ for  $0<p<1$ with the $b$-metric

$d(x,y)=\big{(}\int\limits_{\Omega}|x(t)-y(t)|^{p}dt\big{)}^{\frac{1}{p}}.$

The condition (b3) follows by replacement of $x$ by $x-z$ and $y$ by $z-y$ for
$x,y,z\in L_{p}(\mu)$ in the following inequality:

$\big{(}\int\limits_{\Omega}|x|^{p}d\mu+\int\limits_{\Omega}|y|^{p}d\mu\big{)}^{\frac{1}{p}}\leq
2^{\frac{1-p}{p}}\big{(}\big{(}\int\limits_{\Omega}|x|^{p}d\mu\big{)}^{\frac{1}{p}}+\big{(}\int\limits_{\Omega}|y|^{p}d\mu\big{)}^{\frac{1}{p}}\big{)}.$

###### Definition 2

Let $(X,d)$ be a $b$-metric space. Then a subset $C\subset X$ is called:

  1. (i)

closed if and only if for each sequence $\\{x_{n}\\}$ in $C$ which converges
to an element $x$, we have $x$ $\in C$ (that is, $C=\overline{C}$).

  2. (ii)

compact if and only if for every sequence of elements of $C$ there exists a
subsequence that converges to an element of $C$.

  3. (iii)

bounded if and only if $\delta(C):=\sup\\{d(x,y):x,y\in C\\}<\infty$.

###### Definition 3

Let $(X,d)$ be a $b$-metric space. A sequence $\\{x_{n}\\}$ in $X$ is called:

  1. (I)

Cauchy if and only if for $\varepsilon>0,$ there exists
$n(\varepsilon)\in\mathbb{Z}_{>0}$ such that for each $n,m\geq
n(\varepsilon)$, we have $d(x_{n},x_{m})<\varepsilon.$

  2. (II)

Convergent if and only if there exists $x\in X$ such that for all
$\varepsilon>0$ there exists $n(\varepsilon)\in\mathbb{Z}_{>0}$ such that for
all $n\geq n(\varepsilon)$, we have $d(x_{n},x)<\varepsilon$. In this case, we
write $\lim\limits_{n\rightarrow\infty}x_{n}=x.$

It is known that a sequence $\\{x_{n}\\}$ in $b$-metric space $X$ is Cauchy if
and only if $\lim\limits_{n\rightarrow\infty}d(x_{n},x_{n+p})=0$ for all
$p\in\mathbb{Z}_{>0}$. A sequence $\\{x_{n}\\}$ is convergent to $x\in X$ if
and only if $\lim\limits_{n\rightarrow\infty}d(x_{n},x)=0.$ A $b$-metric space
$(X,d)$ is said to be complete if every Cauchy sequence in $X$ is convergent
in $X$.

The $b$-metric spaces have the following topological properties ATD15 :

  1. (a)

In a $b$-metric space $(X,d),$ $d$ is not necessarily continuous in each
variable.

  2. (b)

In a $b$-metric space $(X,d),$ an open ball is not necessarily an open set. An
open ball is open if $d$ is continuous in one variable.

######  Definition 4 (C98 )

Let $(X,d)$ be a $b$-metric space and $CB\left(X\right)$ denotes the set of
all non-empty closed and bounded subsets of $X.$ For $x,y\in X$ and $A\in
CB(X),$ the following statements hold:

  1. 1)

$d(x,A)\leq b\left(d(x,y)+d(y,A)\right),$ where $d(x,A)=inf\\{d(x,a):a\in
A\\}$;

  2. 2)

For every $\lambda>0$ and $\tilde{a}\in A,$ there is a $\tilde{b}\in B$ such
that $d(\tilde{a},\tilde{b})\leq\lambda;$

  3. 3)

$d(x,A)=0$ if and only if $x\in\bar{A}=A.$

###### Lemma 1

Let $(X,d)$ be a $b$-metric space. For any sequence $\\{u_{n}\\}$ in $X$,

$d(u_{0},u_{n})\leq
bd(u_{0},u_{1})+\dots+b^{n-1}d(u_{n-2},u_{n-1})+b^{n-1}d(u_{n-1},u_{n}).$

Boriceanu et al. BBP10  defined multivalued fractals in $b$-metric spaces.
Czerwik CDS97  defined round-off stability of iteration procedures for
operators in $b$-metric spaces. Czerwik C98  obtained nonlinear set-valued
contraction mappings in $b$-metric spaces.

##  3 Fixed Points of Prešić type Contractions in $b$-Metric Spaces

In 1997, Alber and Guerre-Delabriere Alber  proved that weakly contractive
mapping defined on a Hilbert space is a Picard operator. Rhoades Rhoades
proved that the corresponding result is also valid when Hilbert space is
replaced by a complete metric space. Dutta et al. Dutta  generalized the weak
contractive condition and proved a fixed point theorem for a selfmap. Berinde
and Pǎcurar Berinde1 ; Berinde2  established an iterative method for
approximating fixed points of Prešić contractive mappings. Chen CH  defined
some Prešić type contractive condition and its applications. Khan et al. K
obtained some convergence results for iterative sequences of Prešić type and
applications. Pǎcurar PA ; PA2  approximated common fixed points of Prešić-
Kannan type operators by a multi-step iterative method. Shukla Shulka1
obtained some Prešić type results in 2-Banach spaces. Shukla and Sen Shulka2
definded set-valued Prešić-Reich type mappings in metric spaces. Recently,
Abbas et al. ATD15  established the fixed point of Prešić type mapping
satisfying weakly contraction conditions.

In this section, we study several fixed point results for single-valued Prešić
type mappings that satisfying generalized contractions in the framework of
$b$-metric spaces. Also an example is given that support the results proved
therein. Our results extend and generalize many comparable results in the
existing literature proved. We attain fixed point results for single-valued
mappings in the framework of $b$-metric spaces along with an example and
corollaries. We begin with the following result.

###### Theorem 3.1

Let $(X,d)$ be a complete $b$-metric space, $k\in\mathbb{Z}_{>0}$ and
$f:X^{k}\rightarrow X$ be a given mapping. Suppose that there exists
$\phi:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ a lower semi-
continuous function having $\phi(t)=0$ if and only if $t=0$ such that

$\begin{array}[]{l}d(f(x_{1},x_{2},\ldots,x_{k}),f(x_{2},x_{3},\ldots,x_{k+1}))\\\
\quad\leq\max\\{d(x_{i},x_{i+1}):1\leq i\leq
k\\}-\phi(\max\\{d(x_{i},x_{i+1}):1\leq i\leq k\\}),\end{array}$ (2)

for all $(x_{1},x_{2},\ldots,x_{k+1})\in X^{k+1}$. Then, for any arbitrary
points $x_{1},x_{2},\ldots,x_{k}\in X$, the sequence $\\{x_{n}\\}$ defined by
(1) converges to $u\in X$ and $u$ is a fixed point of $f$, that is,
$u=f(u,u,\dots,u).$ Moreover, if

$d(f(x,\dots,x),f(y,\dots,y))=d(x,y)-\phi(d(x,y)),$ (3)

holds for all $x,y\in X$ with $x\neq y$, then $u$ is the unique fixed point of
$f$.

###### Proof

Let $x_{1},\ldots,x_{k}$ be arbitrary $k$ elements in $X$. Let us define the
sequence $\\{x_{n}\\}$ in $X$ by

$x_{n+k}=f(x_{n},\dots,x_{n+k-1}),\,\,n=1,2,\ldots_{.}$

If $x_{i}=x_{i+1}$ for $i=n,\dots,n+k-1$, then $u\in f(u,u,\dots,u),$ that is,
$u$ is fixed point of $f.$ So, we suppose that $x_{i}\neq x_{i+1}$ any
$i=n,\dots,n+k-1.$ Now for $n\in\mathbb{Z}_{>0},$ by using (2), we get the
following inequalities:

$\displaystyle
d(x_{k+1},x_{k+2})=d(f(x_{1},\ldots,x_{k}),f(x_{2},\ldots,x_{k+1}))$
$\displaystyle\leq\max\left\\{d(x_{i},x_{i+1}):1\leq i\leq
k\right\\}-\phi\left(\max\left\\{d(x_{i},x_{i+1}):1\leq i\leq
k\right\\}\right)$ $\displaystyle<\max\left\\{d(x_{i},x_{i+1}):1\leq i\leq
k\right\\}=\max\\{d\left(x_{1},x_{2}\right),d\left(x_{2},x_{3}\right),\ldots,d\left(x_{k},x_{k+1}\right)\\}.$
$\displaystyle
d(x_{k+2},x_{k+3})=d(f(x_{2},\ldots,x_{k+1}),f(x_{3},\ldots,x_{k+2}))$
$\displaystyle\leq\max\left\\{d(x_{i},x_{i+1}):2\leq i\leq
k+1\right\\}-\phi\left(\max\left\\{d(x_{i},x_{i+1}):2\leq i\leq
k+1\right\\}\right)$ $\displaystyle<\max\left\\{d(x_{i},x_{i+1}):2\leq i\leq
k+1\right\\}=\max\\{d\left(x_{2},x_{3}\right),d\left(x_{3},x_{4}\right),\ldots,d\left(x_{k+1},x_{k+2}\right)\\}$
$\displaystyle<\max\\{d\left(x_{1},x_{2}\right),d\left(x_{2},x_{3}\right),\ldots,d\left(x_{k},x_{k+1}\right)\\}.$

and, by mathematical induction, in general for all integers $n\geq 1$,

$\displaystyle
d(x_{k+n},x_{k+n+1})=d(f(x_{n},\ldots,x_{k+n-1}),f(x_{n+2},\ldots,x_{k+n}))$
$\displaystyle\leq\max\left\\{d(x_{i},x_{i+1}):n\leq i\leq
n+k-1\right\\}-\phi\left(\max\left\\{d(x_{i},x_{i+1}):n\leq i\leq
n+k-1\right\\}\right)$ $\displaystyle<\max\left\\{d(x_{i},x_{i+1}):n\leq i\leq
n+k-1\right\\}$
$\displaystyle=\max\\{d\left(x_{n},x_{n+1}\right),d\left(x_{n+1},x_{n+2}\right),\ldots,d\left(x_{n+k-1},x_{n+k}\right)\\}$
$\displaystyle<\max\\{d\left(x_{1},x_{2}\right),d\left(x_{2},x_{3}\right),\ldots,d\left(x_{k},x_{k+1}\right)\\}.$

Thus by combining above, we get

$\displaystyle\max\left\\{d(x_{i},x_{i+1}):n+1\leq i\leq n+k\right\\}$
$\displaystyle<$ $\displaystyle\max\left\\{d(x_{i},x_{i+1}):n\leq i\leq
n+k-1\right\\}$ $\displaystyle<$
$\displaystyle\dots<\max\left\\{d(x_{i},x_{i+1}):1\leq i\leq k\right\\}.$

We surmise that $\max\left\\{d(x_{i},x_{i+1}):n+1\leq i\leq n+k\right\\}$ is
monotone decreasing and bounded from below. Hence, there exists some $c\geq 0$
such that

$\lim\limits_{n\rightarrow\infty}\max\left\\{d(x_{i},x_{i+1}):n+1\leq i\leq
n+k\right\\}=c.$

For all $n\in\mathbb{Z}_{\geq 1}$, let $n+1\leq j_{n}\leq n+k$ be such that

$d(x_{j_{n}},x_{j_{n}+1})=\max\left\\{d(x_{i},x_{i+1}):n+1\leq i\leq
n+k\right\\}.$

Then, $\lim\limits_{n\rightarrow\infty}d(x_{j_{n}},x_{j_{n}+1})=c.$

We will show now that $c=0$. Actually, taking the upper limits as
$n\rightarrow\infty$ on both sides of the inequality

$d(x_{j_{n}+k},x_{j_{n}+k+1})=d(f(x_{j_{n}},\ldots,x_{j_{n}+k-1}),f(x_{j_{n}+1},\ldots,x_{j_{n}+k}))\\\
\leq\max\left\\{d(x_{i},x_{i+1}):j_{n}\leq i\leq j_{n}+k-1\right\\}\\\
-\phi\left(\max\\{d(x_{i},x_{i+1}):j_{n}\leq i\leq j_{n}+k-1\\}\right),$

yields $c\leq c-\phi\left(c\right),$ that is, $\phi\left(c\right)\leq 0.$ As a
result $\phi\left(c\right)=0$ by the definition of $\phi$, we get
$\lim\limits_{n\rightarrow\infty}d(x_{j_{n}},x_{j_{n}+1})=0$ and in addition,
we get

$\lim\limits_{n\rightarrow\infty}d(x_{n+k},x_{n+k+1})=0.$ (4)

Next we verify that $\\{x_{n+k}\\}$ is Cauchy. For any $n,p\in\mathbb{Z}_{>0}$
with $n>p$ and by using (2), Lemma 1 and $b\geq 1$, we get

$\displaystyle
d(x_{n+k},x_{n+k+p})=d(f(x_{n},\ldots,x_{n+k-1}),f(x_{n+p},\ldots,x_{n+p+k-1}))$
$\displaystyle\leq\sum\limits_{j=1}^{p}b^{j}d(f(x_{n+j-1},\ldots,x_{n+j+k-2}),f(x_{n+j},\ldots,x_{n+j+k-1}))$
$\displaystyle\leq\sum\limits_{j=1}^{p}b^{j}(\max\left\\{d(x_{i},x_{i+1}):n+j\leq
i\leq n+j+k-1\right\\}$ $\displaystyle\hskip
56.9055pt-\phi\left(\max\\{d(x_{i},x_{i+1}):n+j\leq i\leq n+j+k-1\\}\right)).$

From this we conclude that $\\{x_{n+k}\\}$ is a Cauchy sequence in $(X,d)$.
Since $(X,d)$ is complete $b$-metric, there exists a $u$ in $X$ such that

$\lim\limits_{n\rightarrow\infty}d(x_{n+k},x_{n+k+p})=\lim\limits_{n\rightarrow\infty}d(x_{n+k},u).$
(5)

For any $n\in\mathbb{R}_{>0}$, we have

$\displaystyle d(u,f(u,u,\ldots,u))\leq
bd(u,x_{n+k})+bd(x_{n+k},f(u,u,\ldots,u))$
$\displaystyle=bd(u,x_{n+k})+bd(f(u,u,\ldots,u),f(x_{n},x_{n+1},\ldots,x_{n+k-1}))$
$\displaystyle\leq
bd(u,x_{n+k})+\sum\limits_{j=1}^{k}b^{j+1}d(f(\underbrace{u,\dots,u}_{k-j+1},\underbrace{x_{n},\dots,x_{n+j-2}}_{j-1}),f(\underbrace{u,\dots,u}_{k-j},\underbrace{x_{n},\dots,x_{n+j-1}}_{j}))$
$\displaystyle\leq
bd(u,x_{n+k})+\sum\limits_{j=1}^{k}b^{j+1}(\max\\{d(u,x_{n}),d(x_{n},x_{n+1}),\ldots,d(x_{n+j-2},x_{n+j-1})\\}$
$\displaystyle\hskip
85.35826pt-\phi(\max\\{d(u,x_{n}),d(x_{n},x_{n+1}),\ldots,d(x_{n+j-2},x_{n+j-1})\\})).$

Now, by taking upper limit as $n\rightarrow\infty$ in the upper inequality and
by using (5), we get

$d(u,f(u,u,\ldots,u))\leq 0,$

which suggest that $u=f(u,u,\ldots,u)$. So $u$ is a fixed point of $f$.

To prove the fixed point uniqueness, suppose that there exists $v\in X$ with
$v\neq u$, such that $v=f(v,v,\dots,v)$. Then by (3), we get

$\displaystyle d(u,v)$ $\displaystyle=$ $\displaystyle
d(f(u,u,\dots,u),f(v,v,\dots,v))\leq d(u,v)-\phi(d(u,v))<d(u,v),$

a contradiction. Thus, $u$ is the unique point in $X$ and $u=f(u,u,\dots,u)$.
∎

###### Example 5

Let $X=[0,2]$ and $d(x,y)=(x-y)^{2}$ be a $b$-metric on $X$. Let $k\geq 1$ be
a positive integer and $f:X^{k}\rightarrow X$ be the mapping defined by

$f(x_{1},\dots,x_{k})=\frac{x_{1}+\dots+x_{k}}{2k}\text{ for all
}x_{1},\dots,x_{k}\in X.$

Define $\phi:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ by

$\phi(t)=\left\\{\begin{array}[]{l}\text{ \ \ }\frac{t}{5},\text{ \ \ \ \ if
}t\in[0,\frac{5}{2}),\\\ \\\ \frac{2^{2n}(2^{n+1}t-3)}{2^{2n+1}-1},\text{ \ \
if }t\in[\frac{2^{2n}+1}{2^{n}},\frac{2^{2(n+1)}+1}{2^{n+1}}],\text{
}n\in\mathbb{Z}_{>0}.\end{array}\right.$

An easy computation shows that $\phi$ is lower semi-continuous on
$\mathbb{R}_{\geq 0}$ and $\phi(t)=0$ if and only if $t=0.$

Now, for all $x_{1},\dots,x_{k+1}\in X$, we have

$\displaystyle
d(f(x_{1},\dots,x_{k}),f(x_{2},\dots,x_{k+1}))\leq\dfrac{|x_{1}-x_{k+1}|^{2}}{4k^{2}}\leq\frac{1}{4}\max\limits_{1\leq
i\leq k}\\{\left|x_{i}-x_{i+1}\right|^{2}\\}$
$\displaystyle\leq\frac{4}{5}\max\limits_{1\leq i\leq
k}\\{d(x_{i},x_{i+1})\\}=\max\limits_{1\leq i\leq
k}\\{d(x_{i},x_{i+1})\\}-\phi(\max\limits_{1\leq i\leq
k}\\{d(x_{i},x_{i+1})\\}).$

Also, for all $x_{1},x_{2}\in X$, we have

$\displaystyle d(f(x_{1},\dots,x_{1}),f(x_{2},\dots,x_{2}))$
$\displaystyle\leq$ $\displaystyle\frac{1}{8}\left|x_{1}-x_{2}\right|$
$\displaystyle\leq$
$\displaystyle\frac{4}{5}d(x_{1},x_{2})=d(x_{1},x_{2})-\phi(d(x_{1},x_{2})).$

Hence $f$ satisfies (2) and (3). Thus, all the required hypotheses of Theorem
3.1 are satisfied. Moreover, for any arbitrary points $x_{1},\dots,x_{k}\in
X$, the sequence $\\{x_{n}\\}$ defined by $x_{n+k}=f(x_{n},\dots,x_{n+k-1}),\
n=1,2,\ldots\ $converges to $u=0$, the unique fixed point of $f$. ∎

###### Corollary 1

Let $(X,d)$ be a complete $b$-metric space, $k\in\mathbb{Z}_{>0}$ and
$f:X^{k}\rightarrow X$ be a given mapping. If there exists $\lambda\in[0,1)$
such that

$d(f(x_{1},\ldots,x_{k}),f(x_{2},\ldots,x_{k+1}))\leq\lambda\max\\{d(x_{i},x_{i+1}):1\leq
i\leq k\\},$ (6)

for all $(x_{1},\ldots,x_{k+1})\in X^{k+1}$, then, for any
$x_{1},\ldots,x_{k}\in X$, the sequence $\\{x_{n}\\}$ defined in (1) converges
to $u$, and also $u$ is a fixed point of $f$ and $u=f(u,\ldots,u)$. Moreover,
if

$d(f(x,\ldots,x),f(y,\ldots,y))\leq\lambda d(x,y),$

holds for all $x,y\in X$ and $x\neq y$, then $u$ is the unique fixed point of
$f$.

###### Theorem 3.2

Let $(X,d)$ be a complete $b$-metric space, $k\in\mathbb{Z}_{>0}$ and
$f:X^{k}\rightarrow X$ be a given mapping. Let us consider that there exist
$a\in\mathbb{R}$ which is a constant such that $0\leq akb^{k+1}<1$ and

$d(f(x_{1},\dots,x_{k}),f(x_{2},\dots,x_{k+1}))\leq a\max_{1\leq i\leq
k+1}\\{d(x_{i},f(x_{i},\dots,x_{i}))\\}$ (7)

for all $(x_{1},\dots,x_{k+1})\in X^{k+1}$. Then,

  1. (i)

$f$ contain a unique fixed point $u\in X$,

  2. (ii)

For any points $x_{1},\dots,x_{k}\in X,$ the sequence $\\{x_{n}\\}$ defined in
(1) converges to $u$.

###### Proof

∎Let us define a mapping $F:X\rightarrow X$ by $F(x)=f(x,x,\dots,x),$ for all
$x\in X$.
For $x,y\in X$, we have

$\displaystyle d(F(x),F(y))$ $\displaystyle\leq$ $\displaystyle
d(f(x,\dots,x),f(y,\dots,y))$ $\displaystyle\leq$
$\displaystyle\sum\limits_{j=1}^{k}b^{j}d(f(\underbrace{x,\dots,x}_{k-j+1},\underbrace{y,\dots,y}_{j-1})),f(\underbrace{x,\dots,x}_{k-j},\underbrace{y,\dots,y}_{j})).$

Then from (7),

$\displaystyle d(F(x),F(y))$ $\displaystyle\leq$ $\displaystyle
a\sum\limits_{j=1}^{k}b^{j}\max\\{d(x,f(x,\dots,x),d(y,f(y,\dots,y)\\}$
$\displaystyle\leq$ $\displaystyle
a(b^{k}+\dots+b^{k})\max\\{d(x,f(x,\dots,x)),d(y,f(y,\dots,y))\\}$
$\displaystyle\leq$ $\displaystyle
akb^{k}\max\\{d(x,f(x,\dots,x)),d(y,f(y,\dots,y))\\},$

and we get

$d(F(x),F(y))\leq\lambda\max\\{d(x,F(x)),d(y,F(y))\\},$ (8)

where $\lambda=akb^{k}\in[0,1)$. Now, for any $x_{0}\in X,$ we define
$x_{n+1}=F\left(x_{n}\right)$ for $n\in\mathbb{Z}_{\geq 0}$. If
$x_{l}=x_{l+1}$ for some $l\in\mathbb{Z}_{\geq 0},$ then we get
$x_{l}=F\left(x_{l}\right),$ that is, $x_{l}=f(x_{l},\dots,x_{l}).$ We assume
that $x_{l+1}\neq x_{l}$ for all $l\in\mathbb{Z}_{\geq 0}$. From (8),

$d\left(x_{n},x_{n+1}\right)=d(F(x_{n-1}),F(x_{n}))\\\
\leq\lambda\max\\{d(x_{n-1},F(x_{n-1})),d(x_{n},F(x_{n}))\\}=\lambda\max\\{d(x_{n-1},x_{n}),d(x_{n},x_{n+1})\\}.$

If $\max\\{d(x_{n-1},x_{n}),d(x_{n},x_{n+1})\\}=d(x_{n},x_{n+1}),$ then we
obtain

$d\left(x_{n},x_{n+1}\right)\leq\lambda d(x_{n},x_{n+1}),$

which gives $x_{n}=x_{n+1}$ as $\lambda<1,$ a contradiction. Hence,

$\max\\{d(x_{n-1},x_{n}),d(x_{n},x_{n+1})\\}=d(x_{n-1},x_{n}),$

and for all $n\in\mathbb{Z}_{>0},$ we obtain

$d\left(x_{n},x_{n+1}\right)\leq\dots\leq\lambda^{j}d(x_{n-j},x_{j+1})\leq\dots\leq\lambda^{n}d\left(x_{0},x_{1}\right).$

Now for $m,n\in\mathbb{Z}_{>0}$ with $m>n,$ we have

$\displaystyle d\left(x_{n},x_{m}\right)$ $\displaystyle\leq$
$\displaystyle\sum\limits_{j=1}^{m-n}b^{j}d\left(x_{n+j-1},x_{n+j}\right)\leq\sum\limits_{j=1}^{m-n}b^{j}\lambda^{n+j-1}d(x_{0},x_{1})$
$\displaystyle=$ $\displaystyle
b\lambda^{n}\left(\sum\limits_{j=0}^{m-n-1}\left(b\lambda\right)^{j}\right)d\left(x_{0},x_{1}\right)=b\lambda^{n}\frac{1-\left(b\lambda\right)^{m-n}}{1-b\lambda}d\left(x_{0},x_{1}\right)$
$\displaystyle\leq$
$\displaystyle\frac{(b\lambda)^{n}}{1-b\lambda}d\left(x_{0},x_{1}\right)$

and on taking limit as $n,m\rightarrow\infty$ implies
$d\left(x_{n},x_{m}\right)\rightarrow 0.$ Hence the sequence $\\{x_{n}\\}$ is
Cauchy and their exists a $u\in X,$ such that $\\{x_{n}\\}$ converges to $u.$
Now again from (8), we have

$\displaystyle d\left(x_{n},F\left(u\right)\right)$ $\displaystyle=$
$\displaystyle d\left(F\left(x_{n-1}\right),F\left(u\right)\right)$
$\displaystyle\leq$
$\displaystyle\lambda\max\\{d(x_{n-1},F(x_{n-1})),d(u,F(u))\\}$

and taking limit as $n\rightarrow\infty$ yields that
$d\left(u,F\left(u\right)\right)\leq\lambda d\left(u,F\left(u\right)\right),$
which gives $u=F\left(u\right),$ that is, $u=f(u,\dots,u).$ Now, assume that
their exists another $v\in X$ such that $v=f(v,\dots,v).$ From (8), we obtain

$\displaystyle d\left(u,v\right)$ $\displaystyle=$ $\displaystyle
d\left(F\left(u\right),F\left(v\right)\right)$ $\displaystyle\leq$
$\displaystyle\lambda\max\\{d\left(u,F\left(u\right)\right),d\left(v,F\left(v\right)\right)\\}=\lambda\max\\{d\left(u,v\right),d\left(v,v\right)\\}=0,$

which implies that uniqueness of fixed point $u=Fu=f(u,\dots,u)$ of $f.$

For arbitrary points $x_{1},\dots,x_{k}\in X,$ we are going to prove the
convergence of the sequence $\\{x_{n}\\}$ defined by (1) to $u$, the unique
fixed point of $f$. For all $n\geq k+1$, we get

$x_{n}=f(x_{n-k},\dots.,x_{n-1}).$

As we know that $f$ has unique fixed point $u\in X,$ we can write

$\displaystyle d(x_{n+1},u)$ $\displaystyle=$ $\displaystyle
d(f(x_{n-k+1},x_{n-k+2},\dots,x_{n}),f(u,\dots,u))$ $\displaystyle\leq$
$\displaystyle\sum\limits_{j=1}^{k}b^{j}d(f(x_{n-k+j},\dots,x_{n},\underbrace{u,\dots,u}_{j-1}),f(x_{n-k+j+1},\dots,x_{n},\underbrace{u,\dots,u}_{j})).$

This suggest from (7) that

$\displaystyle d(x_{n+1},u)$ $\displaystyle\leq$ $\displaystyle
a\sum\limits_{j=1}^{k}b^{j}\max\\{{d(x_{n-k+j},F(x_{n-k+j})),\dots,d(x_{n},F(x_{n}))},$
$\displaystyle\hskip 113.81102pt\underbrace{d(u,F(u)),\dots,d(u,F(u))}_{j}\\}$
$\displaystyle\leq$ $\displaystyle
ab^{k}\sum\limits_{j=1}^{k}\max\\{{d(x_{n-k+j},F(x_{n-k+j})),\dots,d(x_{n},F(x_{n}))},$
$\displaystyle\hskip
113.81102pt\underbrace{d(u,F(u)),\dots,d(u,F(u))}_{j}\\}.$

Since $u=F(u)$, we get

$\displaystyle d(x_{n+1},u)$ $\displaystyle\leq$ $\displaystyle
ab^{k}\sum\limits_{j=1}^{k}\max\\{{d(x_{n-k+j},F(x_{n-k+j})),\dots,d(x_{n},F(x_{n}))}\\}.$
(9)

For all $j\in\mathbb{Z}_{>0}$, we have

$d(x_{j},F(x_{j}))\leq b[d(x_{j},u)+d(u,F(x_{j}))].$ (10)

By (8), we possess

$\displaystyle d(u,F(x_{j}))$ $\displaystyle=$ $\displaystyle
d(F(u),F(x_{j}))$ $\displaystyle\leq$
$\displaystyle\lambda\max\\{d(u,F(u)),d(x_{j},F(x_{j})\\}$ $\displaystyle=$
$\displaystyle\lambda d(x_{j},F(x_{j})).$

Thus (10) becomes

$d(x_{j},F(x_{j}))\leq b[d(x_{j},u)+\lambda d(x_{j},F(x_{j}))].$

which provides

$d(x_{j},F(x_{j}))\leq\frac{b}{1-\lambda b}d(x_{j},u)\text{, for all
}j\in\mathbb{Z}_{>0}.$ (11)

Using (9) and (11), we obtain

$\displaystyle d(x_{n+1},u)$ $\displaystyle\leq$
$\displaystyle\frac{ab}{1-\lambda b}\max\\{d(x_{n-k+1},u),\dots,d(x_{n},u)\\}$
$\displaystyle+\dots+\frac{ab}{1-\lambda
b}\max\\{d(x_{n-k+i},u),\dots,d(x_{n},u)\\}$
$\displaystyle+\dots+\frac{ab}{1-\lambda b}d(x_{n},u)$ $\displaystyle\leq$
$\displaystyle\frac{abk}{1-\lambda
b}\max\\{d(x_{n-k+1},u),\dots,d(x_{n},u)\\}$

for all $n\geq k$. Setting

$\displaystyle\zeta_{n}=d(x_{n},u)\text{, for all }n\in\mathbb{Z}_{>0},$
$\displaystyle\alpha=\frac{abk}{1-\lambda b},$

we obtain $\zeta_{n+1}\leq\alpha\max\\{\xi_{n-k+1},\dots,\zeta_{n}\\},$ for
all $n\geq k$. We have $0\leq\alpha<1$. Following the same arguments from
(Presic, , Lemma 2), there exists $L>0$ and $\theta\in(0,1)$ such that
$\zeta_{n}\leq L\theta^{n}$ for all $n\in\mathbb{Z}_{>0},$ namely such that

$d(x_{n},u)\leq L\theta^{n}\text{ for all }n\geq 1.$

Taking limit as $n\rightarrow\infty$ in the above inequality, we get
$\lim\limits_{n\rightarrow\infty}d(x_{n},u)=0$, So sequence $\\{x_{n}\\}$
converges to a unique fixed point of $f$. ∎

###### Theorem 3.3

Let $(X,d)$ be a complete $b$-metric space, $k\in\mathbb{Z}_{>0}$ and
$f:X^{k}\rightarrow X$ a mapping fulfilling the following contractive type
condition

$d(f(x_{1},\dots,x_{k}),f(x_{2},\dots,x_{k+1}))\leq\eta\max_{1\leq i\leq
k}\\{d(x_{i},x_{i+1})\\},$

where $\eta\in(0,1)$ a constant and $x_{1},\dots,x_{k+1}$ are the arbitrary
elements in $X$. Then there exists $x\in X$ such that $f(x,\dots,x)=x$.
Furthermore, if $x_{1},\dots,x_{k}$ are arbitrary points in $X$ and for
$n\in\mathbb{Z}_{>0},$

$x_{n+k}=f(x_{n},\dots,x_{n+k-1}),$

then the sequence taken $\\{x_{n}\\}_{n=1}^{\infty}$ is convergent and

$\lim\limits_{n\rightarrow\infty}x_{n}=f(\lim\limits_{n\rightarrow\infty}x_{n},\dots,\lim\limits_{n\rightarrow\infty}x_{n}).$

Additionally we suppose that, on the diagonal $\triangle\subset X^{k},$

$d(f(u,\dots,u),f(v,\dots,v))<d(u,v)$

holds for every $u,v\in X,$ and $u\neq v$. Then $x$ is the unique point in $X$
with $f(x,\dots,x)=x.$

###### Proof

∎Let $x_{1},\dots,x_{k}$ be $k$ arbitrary points in $X$. By using these
points, we define a sequence $\\{x_{n}\\}$ by

$x_{n+k}=f(x_{n},\dots,x_{n+k-1})$

for $n=1,2,\dots$. For simplicity of notation set
$\alpha_{n}=d(x_{n},x_{n+1}).$ We are going to prove by induction that for
each $n\in\mathbb{Z}_{>0},$

$\alpha_{n}\leq b^{k}K\theta^{n}\ \text{where}\ \theta=\eta^{\frac{1}{k}},\
K=\max\\{\frac{\alpha_{1}}{\theta},\dots,\frac{\alpha_{k}}{\theta^{k}}\\}.$
(12)

From the definition of $K$, we see that (12) is true for $n=1,\dots,k.$ Now
suppose the following $k$ inequalities:

$\alpha_{n}\leq b^{k}K\theta^{n},\text{ }\alpha_{n+1}\leq
b^{k}K\theta^{n+1},\dots,\text{ }\alpha_{n+k-1}\leq b^{k}K\theta^{n+k-1}.$

be the induction hypothesis. Then,

$\displaystyle\alpha_{n+k}$ $\displaystyle=$ $\displaystyle
d(x_{n+k},x_{n+k-1})$ $\displaystyle=$ $\displaystyle
d(f(x_{n},x_{n+1},\dots,x_{n+k-1}),f(x_{n+1},x_{n+2},\dots,x_{n+k}))$
$\displaystyle\leq$
$\displaystyle\eta\max\\{\alpha_{n},\alpha_{n+1},\dots,\alpha_{n+k-1}\\}\quad\text{(by
\eqref{t.2.16} and definition of }\alpha_{i})$ $\displaystyle\leq$
$\displaystyle\eta\max\\{b^{k}K\theta^{n},b^{k}K\theta^{n+1},\dots,b^{k}K\theta^{n+k-1}\\}\
\ \text{(by induction hypothesis)}$ $\displaystyle=$ $\displaystyle\eta
b^{k}K\theta^{n}\qquad\text{(as\ $0\leq\theta<1$)}$ $\displaystyle=$
$\displaystyle b^{k}K\theta^{n+k}\qquad\text{(as\
$\theta=\eta^{\frac{1}{k}}$)}$

and it completes the inductive proof of (12). Next by using (12) for any
$n,p\in\mathbb{Z}_{>0},$ we have

$\displaystyle d(x_{n},x_{n+p})\leq
d(x_{n},x_{n+1})+\dots+b^{j}d(x_{n+j-1},x_{n+j})+\dots+b^{p}d(x_{n+p-1},x_{n+p})$
$\displaystyle\leq
b^{p}d(x_{n},x_{n+1})+\dots+b^{p}d(x_{n+j-1},x_{n+j})+\dots+b^{p}d(x_{n+p-1},x_{n+p})$
$\displaystyle\leq
b^{p}K\theta^{n}+\dots+b^{p}K\theta^{n+j-1}+\dots+b^{p}K\theta^{n+p-1}$
$\displaystyle\leq b^{p}K\theta^{n}(1+\theta+\dots+\theta^{n+p-1})$
$\displaystyle=\frac{b^{p}K\theta^{n}}{1-\theta}.$

From this we conclude that $\\{x_{n}\\}$ is a Cauchy sequence. Since $X$ is
complete space, there exists $x\in X$ such that
$x=\lim\limits_{n\rightarrow\infty}x_{n}.$ Then for any integer $n$, we may
write

$\displaystyle d(x,f(x,\dots,x))\leq b(d(x,x_{n+k})+d(x_{n+k},f(x,\dots,x)))$
$\displaystyle=bd(x,x_{n+k})+d(f(x,\dots,x),f(x_{n},\dots,x_{n+k-1})))$
$\displaystyle\leq
bd(x,x_{n+k})+\sum\limits_{j=1}^{k}b^{j}d(f(\underbrace{x,\dots,x}_{k-j+1},\underbrace{x_{n},\dots,x_{n+j-2},}_{j-1}),f(\underbrace{x,\dots,x}_{k-j},\underbrace{x_{n},\dots,x_{n+j-1},}_{j}))$
$\displaystyle\leq
bd(x,x_{n+k})+\eta\sum\limits_{j=1}^{k}b^{j}\max\\{d(x,x_{n}),d(x_{n},x_{n+1}),\dots,d(x_{n+j-2},x_{n+j-1})\\}.$

In the limit, when $n\rightarrow\infty$, we get $d(x,f(x,\dots,x))\leq 0$,
which gives $f(x,\dots,x)=x.$ Thus, we proved that

$\lim\limits_{n\rightarrow\infty}x_{n}=f(\lim\limits_{n\rightarrow\infty}x_{n},\dots,\lim\limits_{n\rightarrow\infty}x_{n}).\
$

Now consider that $f(x,\dots,x)=x$ holds. To prove that the fixed point is
unique, Suppose that for some $y\in X$, $y\neq x$, we have $f(y,\dots,y)=y.$
Then by $d(x,y)=d(f(x,\dots,x),f(y,\dots,y))<d(x,y),$ which is a
contradiction. So, $x$ is the unique point in $X$ such that
$f(x,x,\dots,x)=x.$ ∎

## References

  * (1) Abbas, M., Ilić, D., Nazir, T.: Iterative approximation of fixed points of generalized weak Presic type k-step iterative method for a class of operators. Filomat 29:4, 713–724 (2015)
  * (2) Alber, Y., Guerre-Delabrere, S.: Principle of weakly contractive maps in Hilbert spaces. In: Gohberg, I, Lyubich, Yu (eds.) New Results in Operator Theory Advances and Applications, 98, 7–22 (1997)
  * (3) An, T. V., Tuyen, L. Q., Dung, N. V.: Stone-type theorem on $b$-metric spaces and applications. Topology Appl. 185-186, 50–64 (2015)
  * (4) Banach, S.: Sur les operations dans les ensembles abstraits et leur application aux equations int egrales. Fund. Math. 3, 133–181 (1922)
  * (5) Bergh, J., Löfstrom, J.: Interpolation Spaces, Springer-Verlag, New York/Berlin (1976).
  * (6) Berinde, V., Pǎcurar, M.: An iterative method for approximating fixed points of Presic nonexpansive mappings. Rev. Anal. Numer. Theor. Approx. 38 (2) (2009), 144-153.
  * (7) Berinde, V., Pǎcurar, M.: Two elementary applications of some Prešić type fixed point theorems. Creat. Math. Inform. 20 (1), 32-42 (2011)
  * (8) Boriceanu, M., Bota, M., Petruşel, A.: Multivalued fractals in $b$-metric spaces. Cent. Eur. J. Math. 8 (2), 367–377 (2010)
  * (9) Bakhtin, I. A.: The contraction mapping principle in quasimetric spaces, Func. An. Gos. Ped. Inst. Ulianowsk, 30, 26–37 (1989)
  * (10) Chen, Y.Z.: A Prešić type contractive condition and its applications. Nonlinar Anal. 71, 2012–2017 (2009)
  * (11) Ćirić, L. B., Prešić, S. B.: On Prešić type generalization of the Banach contraction mapping principle. Acta Math. Univ. Comenianae, Vol. LXXVI, 2, 143–147 (2007)
  * (12) Czerwik, S., Dlutek, K., Singh, S.L.: Round-off stability of iteration procedures for operators in $b$-metric spaces. J. Natur. Phys. Sci. 11, 87–94 (1997)
  * (13) Czerwik, S.: Contraction mappings in $b$-metric spaces. Acta Math. Inform. Univ. Ostrav. 1, 5–11 (1993)
  * (14) Czerwik, S.: Nonlinear set-valued contraction mappings in $b$-metric spaces. Atti Semin. Mat. Fis. Univ. Modena. 46, 263–276 (1998)
  * (15) Dutta, P. N., Choudhury, B.S.: A generalization of contraction principle in metric spaces. Fixed Point Theory Appl. Article ID 406368, 1–8 (2008)
  * (16) Khan, M. S., Berzig, M., Samet, B.: Some convergence results for iterative sequences of Prešić type and applications. Adv. Difference Equ. 2012:38, 1–11 (2012)
  * (17) Köthe, G.: Topological Vector Spaces I, Springer-Verlag, New York, 1969. (transl. from: Köthe, G.: Topologische lineare Räume, I, Springer, Berlin, 1960.)
  * (18) Pǎcurar, M.: Approximating common fixed points of Presić-Kannan type operators by a multi-step iterative method. An. Stiint. Univ. Ovidius Constanţa Ser. Mat. 17 (1), 153–168 (2009)
  * (19) Pǎcurar, M.: A multi-step iterative method for approximating fixed points of Presić-Kannan operators. Acta Math. Univ. Comenianae. 79 (1), 77–88 (2010)
  * (20) Prešić, S. B.: Sur une classe d’inéquations aux différences finies et sur la convergence de certaines suites. Publ. Inst. Math. 5 (19), 75–78 (1965)
  * (21) Rhoades, B. E.: Some theorems on weakly contractive maps. Nonlinear Anal. 47, 2683–2693 (2001)
  * (22) Roshan, J. R., Parvaneh, V., Altun, I.: Some coincidence point results in ordered $b$-metric spaces and applications in a system of integral equations. Appl. Math. Comput. 226, 725–737 (2014)
  * (23) Shukla, S.: Prešić type results in 2-Banach spaces. Afr. Mat. 25(4), 1043–1051 (2014)
  * (24) Shukla, S., Sen, R.: Set-valued Prešić-Reich type mappings in metric spaces. Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Math. 108 (2), 431–440 (2014)


# Component-wise Analysis of Automatically Designed Multiobjective Algorithms
on Constrained Problems

Yuri Lavinas<EMAIL_ADDRESS>0000-0003-2712-5340
University of TsukubaJapan ,  Marcelo Ladeira<EMAIL_ADDRESS>University of
BrasiliaBrazil ,  Gabriela Ochoa<EMAIL_ADDRESS>University of
StirlingUK and  Claus Aranha<EMAIL_ADDRESS>University of
TsukubaJapan

(2022)

###### Abstract.

The performance of multiobjective algorithms varies across problems, making it
hard to develop new algorithms or apply existing ones to new problems. To
simplify the development and application of new multiobjective algorithms,
there has been an increasing interest in their automatic design from component
parts. These automatically designed metaheuristics can outperform their human-
developed counterparts. However, it is still uncertain what are the most
influential components leading to their performance improvement. This study
introduces a new methodology to investigate the effects of the final
configuration of an automatically designed algorithm. We apply this
methodology to a well-performing Multiobjective Evolutionary Algorithm Based
on Decomposition (MOEA/D) designed by the irace package on nine constrained
problems. We then contrast the impact of the algorithm components in terms of
their Search Trajectory Networks (STNs), the diversity of the population, and
the hypervolume. Our results indicate that the most influential components
were the restart and update strategies, with higher increments in performance
and more distinct metric values. Also, their relative influence depends on the
problem difficulty: not using the restart strategy was more influential in
problems where MOEA/D performs better; while the update strategy was more
influential in problems where MOEA/D performs the worst.

algorithm analysis, continuous optimization, automatic algorithm
configuration, multi-objective optimization

††journalyear: 2022††copyright: acmcopyright††conference: Genetic and
Evolutionary Computation Conference; July 9–13, 2022; Boston, MA,
USA††booktitle: Genetic and Evolutionary Computation Conference (GECCO ’22),
July 9–13, 2022, Boston, MA, USA††price: 15.00††doi:
10.1145/3512290.3528719††isbn: 978-1-4503-9237-2/22/07††ccs: Computing
methodologies Continuous space search††ccs: Computing methodologies Randomized
search††ccs: Theory of computation Theory of randomized search heuristics

##  1\. Introduction

Multiobjective Optimisation Problems (MOPs) are problems with two or more
conflicting objective functions that are optimised simultaneously. The
evolutionary computation community has proposed several multiobjective
evolutionary algorithms (MOEAs), which can modify their behaviour when solving
a MOP.

Recently, there has been an increasing interest in automatically designing
MOEAs (Radulescu et al., 2013a; Nebro et al., 2019; Bezerra et al., 2015). In
these approaches, a configurator recombines components of established MOEAs,
creating more effective variants of the original MOEA. However, why these
variants perform well is only briefly analysed. We argue that by understanding
why these choices of components for multiobjective algorithms are made, we can
develop new and better components.

Here, we focus on analysing an instance of Multiobjective Evolutionary
Algorithm Based on Decomposition (MOEA/D) (Zhang and Li, 2007) from a
component-wise point of view in MOPs with complicated constraints. The MOEA/D
is a popular and efficient algorithm for solving MOPs and can modify its
behaviour by considering the constraints of these MOPs. However, to be best of
our knowledge, no previous work has analysed how the MOEA/D components affect
the dynamics of the search progress of this metaheuristic, especially in
constrained MOPs.

To analyse how the components contribute to an automatically designed MOEA,
first, we automatically generate a well-performing algorithm instance using
irace on a set of constrained MOPs. Then we conduct an experiment where the
designed algorithm is compared against a set of variants, each of which has at
most a single component altered. The experiment design to compare the variants
follows the work of Campelo and Wanner (Campelo and Wanner, 2020).

We obtain variants of the automatically designed MOEA in one of these two
ways: (1) when we can remove the component, the variant algorithm takes the
structure of the machine-generated MOEA minus this component; (2) otherwise,
we replace this component with its counterpart from the original algorithm. In
this way, we can find the most influential components of the automatically
designed MOEA configuration for the problems studied here. Moreover, we can
also verify how these influential components affect the algorithm’s ability to
navigate the landscape of MOPs here studied.

This investigation takes the form of a case study on nine continuous benchmark
problems with two and three objectives, with tunable constraints. We conduct
our analysis focusing on how these metaheuristics explore the decision space.
Furthermore, we contrast automatically designed MOEA against each of the
variants in terms of their Search Trajectory Networks (STNs) (Ochoa et al.,
2021; Lavinas et al., 2022a); the diversity of the population; and the
traditional metrics of hypervolume and inverted generational distance (IGD).
To the best of our knowledge, this is the first component-wise analysis of
MOEAs about the decision space dynamics in constrained MOPs. For
reproducibility purposes, all the code and experimental scripts are available
online at https://github.com/yurilavinas/MOEADr/tree/gecco22/.

The paper is organised as follows. Section 2 overviews previous work related
to the automated design of algorithms and constrained problems. Section 3
introduces relevant concepts. The automatic design of the MOEA is shown in
Section 4. Then, the comparison of the components setup is presented in
Section 5, and the analysis of the search behaviours dynamics of the different
MOEA/D variants is shown in Section 6. Finally, Section 7 outlines our main
findings, limitations and suggestions for future work.

##  2\. Related Work

Most approaches on the automatic design of evolutionary algorithms focus on
creating templates that can instantiate many algorithms and their parameter
settings for performance improvements. For example, there have been studies to
automatically design NSGA-II (Nebro et al., 2019) and MOEA/D (Bezerra et al.,
2015) on commonly used benchmark sets. Moreover, two seminal examples are the
works of Bezerra et al. (Bezerra et al., 2016, 2020a), which proposed a
component-wise MOEA template that instantiates multiple existing frameworks
for continuous and combinatorial optimisation MOPs.

Their research efforts mainly focus on exploiting the automatic configuration
to increase the performance of multiobjective algorithms in benchmark problems
without constraints. We also highlight the work of Radulescu et al. (Radulescu
et al., 2013a), that focus on improving the performance of multiobjective
metaheuristics. These works are insightful visual approaches; however, they
concentrate on finding well-performing configurations of multiobjective
algorithms. On the other hand, there are few studies in the context of the
automatic design of algorithms focusing on _the effect of the different
components_ on the algorithm’s performance.

Multiple works provide visualisations of Pareto front approximations for the
analysis of the MOP algorithms to help in understanding and contrasting
algorithm behaviour (Fonseca and Fleming, 1996; Kerschke and Grimme, 2017;
Schäpermeier et al., 2020; Liefooghe et al., 2018; Fieldsend and Alyahya,
2019). However, all of these works focus on increments in performance and
analyse the effects of the search progress with respect to the objective
space, with little focus on _the decision space dynamics_. We argue that
analysing the decision space might expand our understanding of the behaviour
of the multiobjective optimisation solvers. That is why we are focusing here
on studying and identifying useful metrics that evaluate these metaheuristics
from the perspective of exploring the decision space dynamics.

We highlight a recent work (Lavinas et al., 2022a) that generalises to
multiobjective optimisation a recent graph-based modelling tool, Search
Trajectory Networks (STNs) (Ochoa et al., 2020, 2021). These STN model the
search behaviour of MOEAs, allowing us to extract features and information
from regions of the decision space that an algorithm has transversed.
Therefore, we use these STN models as one of our tools to discriminate the
behavioural differences of MOEAs.

##  3\. Preliminaries

Few studies have considered the contribution of individual components to MOEAs
performance (Bezerra et al., 2016). Furthermore, in most cases, the
performance is evaluated in unconstrained problems or in problems where the
constraints are simple to address (Tanabe and Ishibuchi, 2020; Bezerra et al.,
2020b; Vaz et al., 2021). These constraints invalidate some solutions, which
makes finding a set of feasible solutions a challenging task.

The MOEA/D is a popular and efficient algorithm for finding good sets of
trade-off solutions for MOPs. The key idea of MOEA/D is to create a linear
decomposition of the MOP into a set of single-objective subproblems.
Decomposing the MOP in various single-objective subproblems makes the
algorithm very flexible for dealing with constraints because adding a penalty
value is straightforward: MOEA/D adds a penalty value related to the amount of
violation of the constraint for each one of the subproblems. Given this nature
of the single-objective subproblems, MOEA/D can easily use multiple constraint
handling techniques (CHTs).

Algorithm 1 MOEA/D outline

1:Initialize population and decomposition vectors.

2:while Computational budget is not meet do

3: Define Neighbourhood relations.

4: If partial update is used, select subset of solutions to update.

5: Else, all solutions are updated.

6: Generate candidates from the updated solutions and their neighbors.

7: Evaluate the candidates on their respective subproblems.

8: Update the population using the candidates.

9: Save non-dominated solutions in UEA.

10: if restart criteria is met, re-generate the population.

11:end while

The MOEA/D template we propose for instantiating and designing variants of
this metaheuristic is shown in Algorithm 1. We use the generational version of
MOEA/D incremented with the Unbounded External Archive (UEA). The UEA is used
to keep all nondominated solutions found by a multi-objective optimizer during
the search process. Solutions in the archive are only used as the output of
the algorithm and are stored in a way that they do not affect the search run
(Tanabe et al., 2017a; Bezerra et al., 2019).

###  3.1. Automatic Design Configurator

For the automated design, we use Iterated Racing (irace) (López-Ibáñez et al.,
2016). The irace package searches for a well performing set of components of
an algorithm over a set of optimization problems. After fine-tuning the MOEA/D
with irace, we conduct an ablation analysis (Fawcett and Hoos, 2016; López-
Ibáñez et al., 2016) to help us understand the choice of components values and
whether each of these choices effectively improves the MOEA/D performance.
This analysis investigates differences between configurations. We conduct an
ablation analysis between the first configuration tried and the best
configuration found by irace.

###  3.2. Search Trajectory Networks (STNs)

To visually and quantitatively analyze the dynamics of different algorithm
variants, we use the recently introduced extension of search trajectory
networks (STNs)(Ochoa et al., 2021) for MOPs (Lavinas et al., 2022a).

In an STN model, each solution in the search space is mapped to a location.
Similar solutions are generally mapped to the same location, as the locations
represent a partition of the search space. The network models are extracted
from data obtained during several runs of the studied algorithm(s). A network
model requires defining its nodes and edges. In an STN model, nodes are
locations in the search trajectories visited by a given algorithm, an edges
connect two consecutive locations in the trajectory. A strength of the network
models is that they can be visualized. When decorating the networks for
visualization, it is possible to highlight attributes of the nodes and edges
that are relevant to the search process. In these visualizations, the size of
nodes and the width of edges are proportional to how many times they were
visited by the algorithms during the aggregation of runs used to extract the
model. The color of nodes and edges also highlight relevant attributes as
indicated in the legends of Figures 1 and 2. Visualisations use _force-
directed_ graph layout algorithms as implemented in R package igraph (Csardi
and Nepusz, 2006).

Here, we extend this approach by using the idea of merging the trajectories of
two or more single-objective algorithms proposed in (Ochoa et al., 2021).
Thus, we combined the STN models of different MOEA/D variants into one single
merged STN model. This allows us to directly visually compare how distinct
variants explore the search space. In the merged models, there is the notion
of shared nodes, which are nodes visited by more than one algorithm and are
indicated in grey colour in the network visualization.

###  3.3. Network and Performance Metrics

We use three STN metrics to assess the global structure of the trajectories
and bring insight into the behaviour of the MOEAs modelled. These metrics are
(1) the number of unique nodes and (2) the number of unique edges, and (3) the
number of shared nodes between vectors. These metrics are summarised in Table
1. We also use the population variance metric.

For reference, we use the following criteria to compare the results of the
different strategies: (a) final approximation hypervolume (HV), the volume of
the n-dimensional polygon formed by reference points and solutions and (2)
inverted generational distance (IGD), the mean distance between reference
points to the nearest solutions. It is worth noting that additional decision
space and MOP metrics could also be considered.

Table 1. Description of decision space metrics Metric | Description
---|---
Nodes | Unique locations visited.
Edges | Unique search transitions
between nodes.
Variance | Dispersion is the population
in the decision space.

##  4\. Designing auto-MOEA/D

In this work, we analyse the components of a MOEA/D instance that were
automatically designed. This design process was done in a component-wise
framework, similar to the protocols used by Bezerra et al. (Bezerra et al.,
2016) and Campelo et al. (Campelo et al., 2020). We extend the MOEADr package
(Campelo and Aranha, 2018) to introduce options for population restart and
partial update of the population (Lavinas et al., 2020, 2022b).

###  4.1. Variable Components Search Space

The configuration search space used in our experiments contains the algorithm
components and numerical parameters of the
MOEA/D framework. These are shown in Table 2.

Special attention is required with the variation operators: Differential
Evolution (DE) mutation and polynomial mutation. They are always performed
sequentially, first DE and then the polynomial mutation. Thus, the order of
the stack of operators is kept fixed, but the parameter values are variable.
Similar attention should be given to the restart strategy, where only the
strategy’s choice is explored.

Table 2. Components search space. Component | Domain
---|---
Decomposition vector generator | Uniform or
Sobol
Population size | 100 or
500
Aggregation function | Weighted Tchebychef or
Adjusted weighted Tchebychef
Update strategy |  Best, $nr=[1,20]$
Restricted, $Tr=[4,20]$
Neighbourhood function | $T=[10,100]$
$Delta=[0.1,1]$
DE mutation | $F=[0.1,1]$
Polynomial mutation | $\eta_{m}=[1,100]$
$prob=[0,1]$
Partial update strategy |  True $n={0.10,0.15,0.20,0.25}$
False, not used
Restart strategy |  True, every $20000$ evaluations
False, not used

We choose to fix some MOEA/D components to reduce the search space for the
irace configurator. The fixed components are the computational budget, the
objective scaling and the constraint handling technique (CHT). These fixed
components are always present in every configuration of the MOEA/D that irace
generates: (1) the number of functions evaluations is set to $100000$ in order
to grasp all possible behaviours of the automatically designed algorithm
during the run; (2) all objectives were linearly scaled at every iteration to
the interval $\left[0,1\right]$; (3) we use the Dynamic CHT (Joines and Houck,
1994), which starts with a small penalty value, increases it across the
iterations to focus on the diversity of feasible solutions, and then later
focus on the convergence of those solutions. It is defined by
$f^{agg}_{penalty}(x)=f^{agg}+(C*t)^{\alpha}*v(x)$, where $C=0.05$ and
$\alpha=2$ are constants we defined based on the following works (Joines and
Houck, 1994; Vaz et al., 2021).

###  4.2. Configurator Setup

We use the irace configurator (López-Ibáñez et al., 2016) to automatically
assemble and design a MOEA/D configuration based on the components available
in the MOEADr package extended with the options for population handling
mentioned above. We run irace with its default settings, except for the number
of elite configurations tested, that we increase from 1 to 7, following
Campelo et al. work (Campelo et al., 2020). We run irace with a budget of
$15000$ runs.

###  4.3. Benchmark Problems

We use the DASCMOP benchmark set (Fan et al., 2020). This set has nine
constrained test functions: DASCMOP1-6, each with eleven constraints, and
DASCMOP7-9, each with seven constraints. The constraints can be modified to
consider three types of difficulties: type-I considers diversity-hardness,
type-II considers feasibility-hardness and type-III consider convergence-
hardness. More information about the problems and these difficulty triplets
can be found in (Fan et al., 2020). We use the implementation of the test
problems available from the Pymoo python package (Blank and Deb, 2020). Since
our work is focused on MOPs with complicated constraints, we select one of the
most challenging difficulty triplets, numbered $16$, which considers all three
types of constraints difficulties.

###  4.4. Evaluation Metrics

Analysing MOP solvers considering only their final approximation provides
limited information related to these algorithms’ performance since any MOP
solver should return a suitable set of solutions at any time during the search
(Zilberstein, 1996; Radulescu et al., 2013b; Dubois-Lacoste et al., 2015;
Tanabe et al., 2017b). Here, we analyse the anytime performance effects in
terms of hypervolume (HV) values to investigate the impact of different
configurations of MOEA/D on their Unbounded External Archive (UEA) (Tanabe et
al., 2017a).

We use the following method to compare the results of the different
strategies: we calculate the accumulative HV over the search progress to
quantify the HV anytime performance. At every $1000$ evaluations, we calculate
the HV of the solutions in the UEA at that iteration, using the reference
point as (11, over the number of objectives), following the work of Bezerra et
al. (Bezerra et al., 2016). Then, we sum all values to have an approximated
evaluation of the anytime HV curve.

Here, we briefly describe the performance of auto-MOEA/D in terms of HV
111higher is better. and inverted generational distance (IGD) 222lower is
better. and variance of the population, and the STNs metrics: number of nodes,
edges and shared nodes. Since we use the reference point of $11$ over the
number of objectives, the maximum HV is $121$ for MOPs with two objectives or
$1331$ for MOPs with three objectives.

Table 3. hypervolume (HV), IGD, Nodes, Edges and population variance of the auto-MOEA/D. MOP | auto-MOEA/D
---|---
| HV/max(HV) | IGD | Nodes | Edges | Var.
DASCMOP1 | 0.27 | 0.23 | 8469 | 10137 | 0.06
DASCMOP2 | 0.58 | 0.27 | 8601 | 10291 | 0.03
DASCMOP3 | 0.52 | 0.32 | 11723 | 13636 | 0.05
DASCMOP4 | 0.01 | 2.72 | 2140 | 2687 | 0.16
DASCMOP5 | 0.00 | 5.23 | 2291 | 2687 | 0.36
DASCMOP6 | 0.09 | 4.03 | 2502 | 3246 | 0.57
DASCMOP7 | 0.01 | 5.17 | 2437 | 3373 | 0.12
DASCMOP8 | 0.00 | 5.03 | 2277 | 3029 | 0.09
DASCMOP9 | 0.14 | 0.57 | 12952 | 16285 | 0.12

The different metrics values for the auto-MOEA/D are shown in Table 3. We can
see that higher HV values and lower IGD values correspond to a high number of
nodes and generally low populational variance values in the DASCMOP1,
DASCMOP2, DASCMOP3 and DASCMOP9 problems. In contrast, the opposite happens
for the other problems (highlighted in light grey).

Thus, we separate these problems into two groups: the easy group, with
DASCMOP1-3 and DASCMOP9, in which MOEA/D performs well; and the hard group,
with DASCMOP4-6, in which MOEA/D performs poorly. This separation is in
agreement with the work of Fan et al. (Fan et al., 2020), where they state
that DASCMOP1-3 and DASCMOP4-6 have similar feasible regions, distance
function and Pareto Fronts when they have the identical difficulty triplets
(number $16$ in our case).

##  5\. Comparison of the Components

((a)) DASCMOP1: the trajectories of the two variants overlap.

((b)) DASCMOP6: the trajectories of the two variants do not overlap.

Figure 1. STNs of auto-MOEA/D and the update strategy on two MOP instances. We
can see that the variants traverse similar regions in the decision space. On
the left, we can see that the update strategy variant explore more areas of
the search but no algorithm is able to find optimal solutions, while on the
right, the opposite happens.

((a)) DASCMOP1: the trajectories of the two variants overlap.

((b)) DASCMOP6: the trajectories of the two variants do not overlap.

Figure 2. STNs of auto-MOEA/D and the no-restart strategy on two MOP
instances. On the left, we can see that the variants traverse similar regions
in the decision space visiting some of the nodes multiple times, while on the
right, the opposite happens.

Here we introduce a methodology for investigating the effects of the final
configuration of a machine-designed multiobjective algorithm. This analysis
aims to measure the differences in the search dynamics among several variants
from the MOEA and, through these measures, identify the most influential
components of the automatically designed algorithm.

Table 4. Auto-MOEA/D setup in this work, and the variants under analysis. For
each variant, only one component is changed, while the other components are
the same as auto-MOEA/D as shown below. Auto-MOEA/D setup, and its Variants
---
auto-MOEA/D | Component variant
Decomposition | Decomposition
$Uniform$ | $SLD$
Population size | Population size
$100$ | $300$
Update | Update
$Restricted$ | $Restricted$
$nr=13$ | $nr=2$
Neighbourhood pars. | Neighbourhood pars.
$T=18$ | $T=20$
$Delta=0.5831$ | $Delta=0.9$
Operators pars. | Operators pars.
$DE:F=0.705$ | $DE:F=0.5$
Polynomial: $\eta_{m}=57.0443$ | Polynomial: $\eta_{m}=20$
Polynomial: $prob=0.303$ | Polynomial: $prob=0.3$
Restart | Restart
$True$ | $False$

To analyse these behavioural effects of the different variants, we compare the
auto-MOEA/D described in Section 4 against variants with at most one single
component altered. We obtain these variants by changing or removing a single
component the auto-MOEA/D at a time. This is done by either (1) removing the
component from the algorithm when possible or (2) changing its parameters to
its counterpart in the traditional MOEA/D. Table 4 lists these differences. We
chose six variants to analyse, which added to auto-MOEA/D itself least to a
total of seven variations of the MOEA/D family. These variations are compared
quantitatively and visually in terms of their STN models to detect which
components affect the most extensive changes.

##  6\. Behavioural dynamics

To quantitatively analyse the dynamics of the search progress of the different
variants of MOEA/D, we mode the search dynamics using STNs for each pair of
auto-MOEA/D and an auto-MOEA/D variant, leading to six different pairs.

We base our quantitative analysis on the traditional multiobjective metrics
hypervolume (HV) and inverted generational distance (IGD) and the number of
nodes, edges and shared nodes of the STN models and the populational variance.
For the HV, we use the reference point of 1.1 over the number of objectives.
We linearly scaled all objectives to the interval $[0,1]$, for a more
straightforward comparison among the algorithms.

Figure 3. Correlation matrix among the different metrics. We find some
correlation among HV and shared nodes; and some correlation among IGD, number
of nodes and edges.

###  6.1. Metrics Analysis

Figure 3 shows the correlation matrix among the different metrics studied,
considering the results of the MOEA/D variants in the DASCMOP set of problems.
Although the HV and IGD metrics are helpful for objective space analysis, we
understand that they provide useful information for the base of the analysis;
thus, we keep them in our analysis.

Since the number of nodes and edges have a high correlation between themselves
and among the IGD, we remove the number of edges metric from our analysis. The
other STN metrics, together with the population variance are on the decision
space analysis; thus, we use them in our following analysis to strengthen the
study. Furthermore, we see a correlation among the IGD metric between the
number of nodes, edges, and shared nodes and the population variance. This
correlation suggests a link between these decision space metrics and IGD
increments of performance.

###  6.2. STNs Extension for Pairs of MOEAs

For creating merged STN models of pairs of MOEAs, we first need to create one
STN for each algorithm. To create the STN of a single algorithm, we follow a
recently proposed methodology (Lavinas et al., 2022a).

#### Basic operations.

The STNs for multiobjective optimization rely on the notions of decomposition
and scalar aggregation function operations (Zhang and Li, 2007):

Decomposition.:

Breaks down a MOP into a set of single objective subproblems, where each
subproblem is a combination of the objectives, characterised by a weight
vector. In this work, we use the Uniform Design (Wang et al., 2013), as it
allows us to choose the number of weight vectors to be generated explicitly.

Scalar aggregation function.:

Takes the objective values of one solution and the weight vector of one
subproblem and calculates a scalar value that represents the quality of that
solution for that particular subproblem. We use the Weighted Tchebycheff
(Miettinen, 1999; Campelo et al., 2020), which is less affected by the shape
of the Pareto front in a given MOP.

#### Basic methodology.

We summarise below the methodology proposed in (Lavinas et al., 2022a).

  1. (1)

Choose the number of decomposition vectors $n$ and generate these vectors
using the decomposition technique. In this study we set $n=5$.

  2. (2)

At every iteration, select a representative solution for each vector, using
the scalar aggregation function. In case of ties, choose the newest solution.

  3. (3)

Map each representative solution as the nodes, with a precision parameter to
portion the space with length $10^{-01}$.

  4. (4)

Edges are given by the sequence of locations of consecutive iterations.

  5. (5)

Each decomposition vector is modelled as an STN trajectory.

  6. (6)

Merge these STNs trajectories by the graph union of these graphs.

This approach allows us to create the STNs of single algorithms. As discussed
(Section 3), we extend this approach by merging the trajectories of two of
this STNs by joining the two STNs graphs. This merged STN model contains the
nodes and edges present in the STN of at least one algorithm. Attributes are
kept for the nodes and edges, indicating whether they were visited by both
algorithms (shared) or by one of them only.

###  6.3. Search Behaviour Dynamics

Table 5. $\Delta$HV; $\Delta$IGD; number of $\Delta$nodes; $\Delta$variance of the population and number of Shared nodes given the different variants of the auto-MOEA/D in terms of components on the constrained problems. | Decomposition variant | Population size variant
---|---|---
|  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared |  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared
DASCMOP1 | 0.02 | -0.01 | 75 | 0.00 | 128 | -0.08 | 0.03 | 264 | -0.04 | 77
DASCMOP2 | 0.01 | 0.00 | 253 | 0.00 | 122 | -0.01 | 0.01 | 284 | -0.01 | 90
DASCMOP3 | 0.00 | 0.02 | 306 | -0.02 | 42 | -0.01 | 0.31 | -1600 | -0.02 | 27
DASCMOP4 | -0.10 | 1.63 | 46 | 0.13 | 11 | -0.01 | 0.24 | 325 | 0.05 | 2
DASCMOP5 | 0.03 | -0.60 | 49 | 0.03 | 12 | 0.13 | -2.58 | 425 | -0.06 | 5
DASCMOP6 | -0.01 | 0.20 | 75 | 0.38 | 12 | 0.08 | -1.27 | 471 | 0.66 | 6
DASCMOP7 | 0.00 | -0.04 | 41 | -0.04 | 2 | 0.11 | -1.30 | 113 | 0.26 | 5
DASCMOP8 | 0.07 | -0.93 | 227 | 0.01 | 5 | -0.01 | 0.17 | 453 | 0.02 | 3
DASCMOP9 | 0.00 | -0.03 | -884 | 0.04 | 3 | -0.02 | 0.03 | -1350 | 0.01 | 6
MOP | Update variant | Neighbourhood parameter variant
|  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared |  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared
DASCMOP1 | -0.08 | 0.01 | -82 | -0.03 | 62 | 0.01 | 0.01 | 116 | -0.03 | 116
DASCMOP2 | -0.01 | -0.04 | -246 | -0.01 | 68 | 0.00 | -0.02 | 66 | -0.01 | 109
DASCMOP3 | 0.00 | -0.02 | -2216 | 0.04 | 35 | 0.00 | 0.03 | -28 | 0.05 | 48
DASCMOP4 | 0.11 | -1.82 | 1196 | 0.16 | 11 | -0.08 | -0.08 | 100 | -0.09 | 11
DASCMOP5 | 0.25 | -4.26 | 1091 | 0.14 | 12 | 0.05 | -0.91 | -75 | 0.24 | 12
DASCMOP6 | 0.20 | -3.26 | 1026 | -0.43 | 13 | 0.02 | 0.08 | 10 | -0.22 | 12
DASCMOP7 | 0.26 | -3.50 | 1006 | 0.32 | 10 | -0.09 | 1.38 | 101 | 0.25 | 10
DASCMOP8 | 0.31 | -3.77 | 1346 | 0.56 | 13 | 0.02 | -0.48 | 37 | 0.05 | 13
DASCMOP9 | -0.05 | -0.01 | -1427 | 0.16 | 19 | 0.03 | -0.05 | -643 | 0.00 | 21
MOP | Operators variant | No-restart variant
|  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared |  $\Delta$HV |  $\Delta$IGD |  $\Delta$nodes |  $\Delta$variance | Shared
DASCMOP1 | 0.09 | -0.06 | 1994 | 0.05 | 139 | 0.20 | -0.08 | -3836 | 0.89 | 129
DASCMOP2 | 0.04 | 0.01 | 1879 | 0.08 | 139 | 0.12 | -0.01 | -2202 | 0.53 | 117
DASCMOP3 | -0.01 | 0.00 | 1606 | 0.01 | 55 | 0.03 | 0.03 | -9962 | 0.15 | 43
DASCMOP4 | -0.05 | 0.27 | -224 | 0.05 | 11 | -0.24 | 4.22 | -1942 | -0.11 | 11
DASCMOP5 | 0.03 | -1.04 | -314 | 0.35 | 12 | -0.08 | 1.36 | -2056 | -0.27 | 12
DASCMOP6 | 0.05 | -1.27 | -323 | 0.39 | 13 | -0.13 | 2.43 | -2178 | -0.5 | 12
DASCMOP7 | 0.00 | -0.09 | -434 | 0.39 | 10 | -0.22 | 3.67 | -2010 | -0.03 | 10
DASCMOP8 | 0.01 | -0.56 | 225 | 0.57 | 13 | -0.19 | 2.99 | -1948 | -0.01 | 13
DASCMOP9 | 0.01 | -0.02 | 60 | 0.11 | 19 | 0.02 | 0.03 | -7303 | -0.06 | 20

Based on the results shown above, we compared the auto-MOEA/D and its variants
in terms of HV, IGD, population variance, and the STNs metrics: number of
nodes and shared nodes. For a more straightforward comparative analysis, we
calculate the difference between the results found by the variants to the
results found by the auto-MOEA/D (Table 3). We show the $\Delta$HV,
$\Delta$IGD, $\Delta$nodes, $\Delta$variance. For all of these metrics,
positive values indicate larger values in relation to the base algorithm,
while negative values indicate the opposite. The only exception in for the IGD
values, where negative values indicate larger values in relation to the base
algorithm. The number of shared nodes is the only absolute metric.

The different metrics for the variants are shown in Table 5. In terms of the
traditional MOP metric HV and IGD, we can see most variants perform the same
as the base algorithm in DASCMOP1, DASCMOP2, DASCMOP3 and DASCMOP9, MOPs that
compose the easy group (as discussed in Section 4). The only exception is the
no-restart variant that generally leads to more positive differences in the
metrics values: high differences in HV, number of nodes, populational variance
(except for DASCMOP9); and a good amount of shared nodes. These results
suggest that not using the restart strategy can enhance the search ability of
MOEA/D in easy problems, leading to HV performance increments, more regions of
the search being visited, and more variety in the population. Interestingly,
changing the restart strategy has little effect on the number of shared nodes
and the IGD values. For the set of hard problems, the performance of the no-
restart variant deteriorates in terms of HV, the number of nodes, and
population variance, indicating that the restart strategy should be avoided in
hard problems but used in easy problems.

For the other problems (shown in light grey in Table 5), there are more
changes in HV and IGD performance, and in this case, the update variant
increases the performance the most. For this group of hard MOPs (Section 4),
the update variant generally leads to more differences in the metrics values:
positive differences in HV in the number of nodes and negative differences in
the IGD values. The populational variance and the number of shared nodes are
similar to the other variants. This result suggests that the update strategy
has a decisive role in the search ability of MOEA/D in hard problems. Contrary
to our expectations, the decomposition variant shows minor differences in all
metrics we analysed here. The other variants also show minor differences in
these metrics.

Moving on to the STNs visualisations, Figures 1 and 2. Within the two MOP
groups, we see minor changes in the STNs visualisations; therefore, we
selected visualisations of a representative problem of each group to show
here: from the easy problem, we select the DASCMOP1, and for the hard group,
we select the DASCMOP6. Considering the colours used in the STN
visualisations, yellow squares indicate the start of trajectories, and black
triangles indicate the end of trajectories. The red colour shows the best
Pareto optimal solutions, and light grey circles show shared locations visited
by both algorithms in that MOP. Finally, the trajectories of each algorithm
are shown in different colours: purple for the auto-MOEA/D and green for the
variant.

Looking at the images of the STNs of auto-MOEA/D and the update strategy, in
the DASCMOP1 and DASCMOP6, Figure 1, and the STNs of auto-MOEA/D and the no-
restart strategy, also in DASCMOP1 and DASCMOP6, Figure 2. For the DASCMOP1,
the trajectories of the STNs of the auto-MOEA/D and each variant overlap; that
is, they visit similar regions in the decision space. We associate this
behaviour with the number of shared nodes for this problem is high: 63 in the
case of the update variant pair and 48 in the case of the no-restart variant
pair (See Table 5). This indicates that the regions visited by both algorithms
tend to be closer to each other. On the other hand, for the harder DASCMOP6,
the trajectories do not overlap, and the number of shared nodes is much
smaller, 14 for both cases. This indicates a high impact of the problem
difficulty on the search ability of the MOEA/D family and that the MOEAs are
visiting unrelated regions in the decision space.

In terms of best Pareto optimal solutions and for the DASCMOP1, auto-MOEA/D
was able to find one Pareto optimal solution while the no-restart variant
found two and the update variant, none. Given the distribution of the nodes in
the STNs, these optimal solutions might not be easy to find. No MOEA/D reached
an optimal solution in the DASCMOP6. This supports our decision of separating
the DASCMOP benchmark into two different groups, according to their
difficulties.

Although we only showed the STNs of these two pairs, an identical trend occurs
for all pairs of MOEAs: the STNs of all pairs of variants for the easy group
are visually similar among themselves and the STNs, but different to the STNs
of the hard group. Finally, looking at Table 5 we see the same results in
terms of shared nodes; in the easy MOPs, there are more shared nodes, while
for the hard MOPs, there are fewer shared nodes.

##  7\. Conclusion

The aim of this work was to introduce a new methodology that investigates the
effects of different configurations from the component-wise point of view of
automatically designed multiobjective algorithms in terms of their decision
space dynamics in constrained MOPs. We contrasted the behaviour of these
configurations in terms of how they explore the decision space by comparing
their Search Trajectory Networks (STNs), their population diversity, and, for
reference, their hypervolume. This analysis allowed us to identify what the
most influential components are.

We studied the auto-MOEA/D, a well-performing MOEA/D designed by the irace
package, and the subsequently derived variants that differ from this machine-
designed MOEA by a single component. The results have shown that the most
influential components are the restart and update strategies. Their relative
influence depends on the problem difficulty: not using the restart strategy
was more influential in problems where MOEA/D performs well. In contrast, the
update strategy was more influential in problems where MOEA/D performs poorly.

We also conduct a brief study on the effects of the decision space metrics. We
found that most of the STN metrics can provide precise information about the
search dynamics of the different MOEAs, with the only exception being the
number of edges. Moreover, we found a high correlation between the IGD metric
and: the number of nodes, edges and shared nodes; and the population variance.
This result indicates that our decision space metrics can provide insightful
information about the dynamics of different MOEAs in the decision space while
also correlating to increments in performance.

Overall, this study strengthens the view that characterizing the effects of
MOEA/D algorithm components could help in developing even more effective
MOEAs. Taken together, these findings suggest a role for improving in
promoting the study of specific components to develop new and better
components, especially in consideration of the restart and update strategy.

We understand that our results are of interest to the broad multiobjective
evolutionary computation community. One limitation of our work is that we only
consider first-order interactions between the MOEA/D variants and their
components. A natural progression includes considering higher-order
interactions and conducting a similar analysis on other multiobjective
metaheuristics, such as the NSGA-II solver.

## Errata

The authors found errors in the scripts for constructing and visualising the
STNs. We have updated the code repository, some tables, figures and
corresponding text with the corrected STNs. The general conclusions of the
paper remain the same.

## References

  * (1)
  * Bezerra et al. (2019) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2019.  Archiver Effects on the Performance of State-of-the-Art Multi- and Many-Objective Evolutionary Algorithms. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Prague, Czech Republic) _(GECCO ’19)_. Association for Computing Machinery, New York, NY, USA, 620–628.  https://doi.org/10.1145/3321707.3321789
  * Bezerra et al. (2015) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2015.  Comparing Decomposition-Based and Automatically Component-Wise Designed Multi-Objective Evolutionary Algorithms. In _Evolutionary Multi-Criterion Optimization_ , António Gaspar-Cunha, Carlos Henggeler Antunes, and Carlos Coello Coello (Eds.). Springer International Publishing, Cham, 396–410.
  * Bezerra et al. (2020a) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2020a.  _Automatic Configuration of Multi-objective Optimizers and Multi-objective Configuration_.  Springer International Publishing, Cham, 69–92.  https://doi.org/10.1007/978-3-030-18764-4_4
  * Bezerra et al. (2020b) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2020b.  Automatically Designing State-of-the-Art Multi- and Many-Objective Evolutionary Algorithms.  _Evolutionary Computation_ 28, 2 (2020), 195–226.  https://doi.org/10.1162/evco_a_00263
  * Bezerra et al. (2016) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2016.  Automatic Component-Wise Design of Multiobjective Evolutionary Algorithms.  _IEEE Transactions on Evolutionary Computation_ 20, 3 (2016), 403–417.  https://doi.org/10.1109/TEVC.2015.2474158
  * Blank and Deb (2020) J. Blank and K. Deb. 2020.  pymoo: Multi-Objective Optimization in Python.  _IEEE Access_ 8 (2020), 89497–89509.
  * Campelo and Aranha (2018) Felipe Campelo and Claus Aranha. 2018.  MOEADr: Component-Wise MOEA/D Implementation.  URL https://cran.R-project.org/package=MOEADr.  R package version 1.2.0.
  * Campelo et al. (2020) Felipe Campelo, Lucas Batista, and Claus Aranha. 2020\.  The MOEADr Package: A Component-Based Framework for Multiobjective Evolutionary Algorithms Based on Decomposition.  _Journal of Statistical Software_ (2020).  In press. Available from: https://arxiv.org/abs/1807.06731.
  * Campelo and Wanner (2020) Felipe Campelo and Elizabeth F. Wanner. 2020.  Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances.  _Journal of Heuristics_ 26, 6 (2020), 851–883.  https://doi.org/10.1007/s10732-020-09454-w
  * Csardi and Nepusz (2006) G. Csardi and T. Nepusz. 2006.  The igraph software package for complex network research.  _InterJournal_ Complex Systems (2006), 1695.
  * Dubois-Lacoste et al. (2015) Jérémie Dubois-Lacoste, Manuel López-Ibáñez, and Thomas Stützle. 2015.  Anytime Pareto local search.  _European Journal of Operational Research_ 243, 2 (2015), 369 – 385.  https://doi.org/10.1016/j.ejor.2014.10.062
  * Fan et al. (2020) Zhun Fan, Wenji Li, Xinye Cai, Hui Li, Caimin Wei, Qingfu Zhang, Kalyanmoy Deb, and Erik Goodman. 2020\.  Difficulty Adjustable and Scalable Constrained Multiobjective Test Problem Toolkit.  _Evolutionary Computation_ 28, 3 (09 2020), 339–378.  https://doi.org/10.1162/evco_a_00259 arXiv:https://direct.mit.edu/evco/article-pdf/28/3/339/1858953/evco_a_00259.pdf
  * Fawcett and Hoos (2016) Chris Fawcett and Holger H Hoos. 2016.  Analysing differences between algorithm configurations through ablation.  _Journal of Heuristics_ 22, 4 (2016), 431–458.
  * Fieldsend and Alyahya (2019) Jonathan E. Fieldsend and Khulood Alyahya. 2019.  Visualising the Landscape of Multi-Objective Problems Using Local Optima Networks. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (Prague, Czech Republic) _(GECCO ’19)_. Association for Computing Machinery, New York, NY, USA, 1421–1429.  https://doi.org/10.1145/3319619.3326838
  * Fonseca and Fleming (1996) Carlos M. Fonseca and Peter J. Fleming. 1996.  On the performance assessment and comparison of stochastic multiobjective optimizers. In _Parallel Problem Solving from Nature — PPSN IV_ , Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 584–593.
  * Joines and Houck (1994) J.A. Joines and C.R. Houck. 1994.  On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA’s. In _Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence_. 579–584 vol.2.  https://doi.org/10.1109/ICEC.1994.349995
  * Kerschke and Grimme (2017) Pascal Kerschke and Christian Grimme. 2017.  An Expedition to Multimodal Multi-objective Optimization Landscapes. In _Evolutionary Multi-Criterion Optimization, EMO_ _(Lecture Notes in Computer Science, Vol. 10173)_. Springer, 329–343.  https://doi.org/10.1007/978-3-319-54157-0_23
  * Lavinas et al. (2020) Yuri Lavinas, Claus Aranha, Marcelo Ladeira, and Felipe Campelo. 2020.  MOEA/D with Random Partial Update Strategy. In _2020 IEEE Congress on Evolutionary Computation (CEC)_. 1–8.
  * Lavinas et al. (2022a) Yuri Lavinas, Claus Aranha, and Gabriela Ochoa. 2022a.  Search Trajectories Networks of Multi-objective Evolutionary Algorithms”. In _International Conference on the Applications of Evolutionary Computation (Part of EvoStar)_. Springer, to appear.
  * Lavinas et al. (2022b) Yuri Lavinas, Marcelo Ladeira, and Claus Aranha. 2022b.  Faster Convergence in Multi-Objective Optimization Algorithms Based on Decomposition.  _Evolutionary Computation_ (02 2022), 1–26.  https://doi.org/10.1162/evco_a_00306
  * Liefooghe et al. (2018) Arnaud Liefooghe, Bilel Derbel, Sébastien Verel, Manuel López-Ibáñez, Hernán Aguirre, and Kiyoshi Tanaka. 2018.  On Pareto Local Optimal Solutions Networks. In _Parallel Problem Solving from Nature – PPSN XV_ , Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, and Darrell Whitley (Eds.). Springer International Publishing, Cham, 232–244.
  * López-Ibáñez et al. (2016) Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. 2016.  The irace package: Iterated racing for automatic algorithm configuration.  _Operations Research Perspectives_ 3 (2016), 43–58.  https://doi.org/10.1016/j.orp.2016.09.002
  * Miettinen (1999) Kaisa Miettinen. 1999\.  Nonlinear Multiobjective Optimization, volume 12 of International Series in Operations Research and Management Science.
  * Nebro et al. (2019) Antonio J. Nebro, Manuel López-Ibáñez, Cristóbal Barba-González, and José García-Nieto. 2019\.  Automatic Configuration of NSGA-II with JMetal and Irace. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (Prague, Czech Republic) _(GECCO ’19)_. Association for Computing Machinery, New York, NY, USA, 1374–1381.  https://doi.org/10.1145/3319619.3326832
  * Ochoa et al. (2020) Gabriela Ochoa, Katherine M. Malan, and Christian Blum. 2020.  Search Trajectory Networks of Population-Based Algorithms in Continuous Spaces. In _Applications of Evolutionary Computation_ , Pedro A. Castillo, Juan Luis Jiménez Laredo, and Francisco Fernández de Vega (Eds.). Springer International Publishing, Cham, 70–85.
  * Ochoa et al. (2021) Gabriela Ochoa, Katherine M. Malan, and Christian Blum. 2021.  Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics.  _Applied Soft Computing_ 109 (2021), 107492.  https://doi.org/10.1016/j.asoc.2021.107492
  * Radulescu et al. (2013a) Andreea Radulescu, Manuel López-Ibáñez, and Thomas Stützle. 2013a.  Automatically Improving the Anytime Behaviour of Multiobjective Evolutionary Algorithms. In _Evolutionary Multi-Criterion Optimization_ , Robin C. Purshouse, Peter J. Fleming, Carlos M. Fonseca, Salvatore Greco, and Jane Shaw (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 825–840.
  * Radulescu et al. (2013b) Andreea Radulescu, Manuel López-Ibáñez, and Thomas Stützle. 2013b.  Automatically Improving the Anytime Behaviour of Multiobjective Evolutionary Algorithms. In _Evolutionary Multi-Criterion Optimization_ , Robin C. Purshouse, Peter J. Fleming, Carlos M. Fonseca, Salvatore Greco, and Jane Shaw (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 825–840.
  * Schäpermeier et al. (2020) Lennart Schäpermeier, Christian Grimme, and Pascal Kerschke. 2020\.  One PLOT to Show Them All: Visualization of Efficient Sets in Multi-objective Landscapes. In _Parallel Problem Solving from Nature – PPSN XVI_ , Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, and Heike Trautmann (Eds.). Springer International Publishing, Cham, 154–167.
  * Tanabe and Ishibuchi (2020) Ryoji Tanabe and Hisao Ishibuchi. 2020.  An easy-to-use real-world multi-objective optimization problem suite.  _Applied Soft Computing_ 89 (2020), 106078.  https://doi.org/10.1016/j.asoc.2020.106078
  * Tanabe et al. (2017a) Ryoji Tanabe, Hisao Ishibuchi, and Akira Oyama. 2017a.  Benchmarking Multi- and Many-Objective Evolutionary Algorithms Under Two Optimization Scenarios.  _IEEE Access_ 5 (2017), 19597–19619.  https://doi.org/10.1109/ACCESS.2017.2751071
  * Tanabe et al. (2017b) Ryoji Tanabe, Hisao Ishibuchi, and Akira Oyama. 2017b.  Benchmarking multi-and many-objective evolutionary algorithms under two optimization scenarios.  _IEEE Access_ 5 (2017), 19597–19619.
  * Vaz et al. (2021) Felipe Vaz, Yuri Lavinas, Claus Aranha, and Marcelo Ladeira. 2021\.  Exploring Constraint Handling Techniques in Real-World Problems on MOEA/D with Limited Budget of Evaluations. In _Evolutionary Multi-Criterion Optimization_ , Hisao Ishibuchi, Qingfu Zhang, Ran Cheng, Ke Li, Hui Li, Handing Wang, and Aimin Zhou (Eds.). Springer International Publishing, Cham, 555–566.
  * Wang et al. (2013) Rui Wang, Tao Zhang, and Bo Guo. 2013.  An enhanced MOEA/D using uniform directions and a pre-organization procedure. In _2013 IEEE Congress on Evolutionary Computation_. 2390–2397.  https://doi.org/10.1109/CEC.2013.6557855
  * Zhang and Li (2007) Qingfu Zhang and Hui Li. 2007.  MOEA/D: A multiobjective evolutionary algorithm based on decomposition.  _IEEE Transactions on evolutionary computation_ 11, 6 (2007), 712–731.
  * Zilberstein (1996) Shlomo Zilberstein. 1996\.  Using anytime algorithms in intelligent systems.  _AI magazine_ 17, 3 (1996), 73–73.