###### Abstract

A mixed tree is a tree in which both directed arcs and undirected edges may
exist. Let $T$ be a mixed tree with $n$ vertices and $m$ arcs, where an
undirected edge is counted twice as arcs. Let $A$ be the adjacency matrix of
$T$. For $\alpha\in[0,1]$, the matrix $A_{\alpha}$ of $T$ is defined to be
$\alpha D^{+}+(1-\alpha)A$, where $D^{+}$ is the the diagonal out-degree
matrix of $T$. The $A_{\alpha}$-spectral radius of $T$ is the largest real
eigenvalue of $A_{\alpha}$. We will give a sharp upper bound and a sharp lower
bound of the $A_{\alpha}$-spectral radius of $T$.

Sharp bounds of the $A_{\alpha}$-spectral radii of mixed trees

Yen-Jen Cheng

Department of Applied Mathematics,

National Yang Ming Chiao Tung University,

1001 Ta Hsueh Road, Hsinchu, Taiwan.

Email addresses<EMAIL_ADDRESS>
Louis Kao

(Corresponding author)

Department of Applied Mathematics,

National Yang Ming Chiao Tung University,

1001 Ta Hsueh Road, Hsinchu, Taiwan.

Email addresses<EMAIL_ADDRESS>
Chih-Wen Weng

Department of Applied Mathematics,

National Yang Ming Chiao Tung University,

1001 Ta Hsueh Road, Hsinchu, Taiwan.

Email addresses<EMAIL_ADDRESS>
Mathematics Subject Classification: 05C05, 05C50, 15A42

Keywords: mixed tree, $A_{\alpha}$-spectral radius, Kelmans transformation

##  1 Introduction

A mixed graph is a graph in which directed and undirected edges between two
distinct vertices may exist at most once. To distinguish, we refer an arc to
as a directed edge in a mixed graph. An undirected graph is a mixed graph
without arcs. For a mixed graph $G$ of order $n$, let the vertex set of $G$ be
$V(G)=[n]=\\{1,2,\ldots,n\\}$, and the set $E(G)$ collects all arcs
$\overrightarrow{ij}$ and all undirected edges $ij$ in $G$, where $i,j\in
V(G)$ are distinct. The size of a mixed graph $G$ is defined to be the number
of arcs plus twice the number of undirected edges in $G$. The adjacency matrix
$A=(a_{ij})$ of $G$ is a square $01$-matrix of order $n$ defined by $a_{ij}=1$
if and only if $\vv{ij}$ or $ij$ in $E(G)$. The diagonal matrix $D^{+}={\rm
diag}(d^{+}_{1},d^{+}_{2},\ldots,d^{+}_{n})$ is called the out-degree matrix
of $T$, where $d^{+}_{i}=|\\{j~{}:~{}\vv{ij}\in E(G){~{}\rm or~{}}ij\in
E(G)\\}|$. For real number $\alpha\in[0,1]$, the matrix $A_{\alpha}(G)$ of $G$
is defined to be $\alpha D^{+}+(1-\alpha)A$. The concepts of $A_{\alpha}$
matrix of graphs were first introduced by Nikiforov[11] in 2017 and then liu
et al.[10] start to consider the $A_{\alpha}$ matrix for digraphs. Since
$A_{\alpha}$ is nonnegative and it is well known that a nonnegative matrix has
a real eigenvalue, let $\rho_{\alpha}(G)$ denote the largest real eigenvalue
$\rho(A_{\alpha}(G))$ of the $A_{\alpha}$ matrix $A_{\alpha}(G)$ of $G$, and
refer $\rho_{\alpha}(G)$ to as the $A_{\alpha}$-spectral radius, or
$\alpha$-index of $G$. For the previous studies on $A_{\alpha}$-spectral radii
of undirected graphs and mixed graphs, see [5, 6, 9, 12, 13, 14].

The underlying graph of a mixed graph $G$ is the undirected graph obtained
from $G$ by removing the directions on arcs. The distance $\partial(a,b)$ for
vertices $a,b$ in $G$ is their distance in the underlying graph of $G$. The
diameter of $G$ is defined to be $\max_{a,b\in V(G)}\partial(a,b)$. Similarly
the mixed tree, mixed path, mixed star are defined as mixed graphs whose
underlying graphs are tree, path, and star, respectively, where a star is a
tree of diameter at most $2$. We denote the mixed path of order $k$ and size
$2k-2$ by $P_{k}$. The main goal of this paper is to find the sharp upper
bound and sharp lower bound of the $A_{\alpha}$-spectral radii of mixed trees
of order $n$ and size $m$, where $n-1\leq m\leq 2n-2$. The following two
theorems are our main results.

######  Theorem 1.1.

If $\alpha\in[0,1]$ and $T$ is a mixed tree of order $n$ and size $m$, then

$\rho_{\alpha}(T)\leq\frac{1}{2}\left(\alpha
n+\sqrt{\alpha^{2}n^{2}-4\alpha^{2}(n-1)+4(1-\alpha)^{2}(m-n+1)}\right).$

Moreover, every mixed star of order $n$ and size $m$ with maximum out-degree
$n-1$ attains the upper bound.

######  Theorem 1.2.

If $T$ is a mixed tree of order $n$ and size $m$, and set
$k=\lceil\frac{n}{2n-m-1}\rceil$ then

$\rho_{\alpha}(T)\geq\rho_{\alpha}(P_{k}).$

Moreover, the lower bound is attained when $T=P_{n}$.

It worths mentioning that in the special case $m=2n-2$, Theorem 1.1 and
Theorem 1.2 are proved in [12]. The main tool in the proof of Theorem 1.1 is
the Kelmans transformation for matrices [8] which will be introduced in
Section 2. A partially ordered set (poset) $\mathcal{G}(n,m)$ of mixed graphs
of order $n$ and size $m$ that respects the order of $A_{\alpha}$-spectral
radii is introduced and the maximal elements in $\mathcal{G}(n,m)$ are
characterized in Section 3. The maximal elements in the subposet
$\mathcal{T}(n,m)$ of $\mathcal{G}(n,m)$ induced on the mixed trees are
determined in Section 4. Theorem 1.1 will be proven in Section 5. Theorem 1.2
is essentially a consequence of [12]. We mention this in Section 6.

##  2 Preliminaries

To compare the $A_{\alpha}$-spectral radii of mixed graphs, we first
introduced a useful tool called the Kelmans transformation. The Kelmans
transformation, of an undirected graph, or called graph compression, was
defined by A.K. Kelmans in 1981[7]. The authors Kao and Weng have generalized
it into a matrix version in [8], and here we will further generalize the
transformation to fit the $A_{\alpha}$ matrix.

Let $C=(c_{ij})$ be a nonnegative square matrix of order $n$. Fix a $2$-subset
$\\{a,b\\}$ of $[n]$, and assume that $c_{ab}=c_{ba}$. Choose $k$ such that

$\max(0,c_{bb}-c_{aa})\leq k\leq c_{bb}$ (1)

and for $i\in[n]-\\{a,b\\}$, choose $t_{i}$ and $s_{i}$ such that

$\max(0,c_{ib}-c_{ia})\leq t_{i}\leq c_{ib},\quad\max(0,c_{bi}-c_{ai})\leq
s_{i}\leq c_{bi}.$ (2)

We define a new matrix $C_{b}^{a}=C_{b}^{a}(t_{i};s_{i};k)$ of order $n$ from
$C$ by shifting the portion $k$ from $c_{bb}$ to $c_{aa}$, the portion $t_{i}$
of $c_{ib}$ to $c_{ia}$ and the portion $s_{i}$ of $c_{bi}$ to $c_{ai}$ such
that in the new matrix $C_{b}^{a}=(c^{\prime}_{ij})$ we have
$c^{\prime}_{aa}\geq c^{\prime}_{bb}$, $c^{\prime}_{ia}\geq c^{\prime}_{ib}$,
and $c^{\prime}_{ai}\geq c^{\prime}_{bi}$, for all $i\in[n]-\\{a,b\\}$. The
following is an illustration of $C_{b}^{a}$:

$C_{b}^{a}=~{}~{}\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle~{}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
j$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle a$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle b\\\$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle~{}~{}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\i$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
c_{ij}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle c_{ia}+t_{i}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle c_{ib}-t_{i}\\\$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\a$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
c_{aj}+s_{j}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle c_{aa}+k$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle c_{ab}\\\b$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
c_{bj}-s_{j}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle c_{ba}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle c_{bb}-k\\\$\hfil\kern
5.0pt\crcr}}}}\right]$}}\qquad\left\\{\begin{array}[]{l}i,j\in[n]-\\{a,b\\},\\\
c_{ab}=c_{ba},\\\ \max(0,c_{ib}-c_{ia})\leq t_{i}\leq c_{ib},\\\
\max(0,c_{bj}-c_{aj})\leq s_{j}\leq c_{bj},\\\ \max(0,c_{bb}-c_{aa})\leq k\leq
c_{bb}.\end{array}\right.$

Formally, the matrix $C_{b}^{a}=(c^{\prime}_{ij})$ is defined from
$C=(c_{ij})$ by setting

$c^{\prime}_{ij}=\left\\{\begin{array}[]{ll}c_{ij},&\hbox{if
$i,j\in[n]-\\{a,b\\}$ or $(i,j)\in\\{(a,b),(b,a)\\}$;}\\\
c_{ia}+t_{i},&\hbox{if $j=a$ and $i\in[n]-\\{a,b\\}$;}\\\
c_{ib}-t_{i},&\hbox{if $j=b$ and $i\in[n]-\\{a,b\\}$;}\\\
c_{aj}+s_{j},&\hbox{if $i=a$ and $j\in[n]-\\{a,b\\}$;}\\\
c_{bj}-s_{j},&\hbox{if $i=b$ and $j\in[n]-\\{a,b\\}$;}\\\ c_{aa}+k,&\hbox{if
$i=j=a$;}\\\ c_{bb}-k,&\hbox{if $i=j=b$.}\\\ \end{array}\right.$ (3)

The matrix $C_{b}^{a}$ is referred to as the Kelmans transformation of $C$
from $b$ to $a$ with respect to $(t_{i};s_{i};k)$. In the above setting, if
$C=(c_{ij})$ is the adjacency matrix of an undirected graph of order $n$ and
assume that $C_{b}^{a}$ is also a symmetric binary matrix, then by the
assumptions in (1)-(2),
$t_{i}=\max(0,c_{ib}-c_{ia})=\max(0,c_{bi}-c_{ai})=s_{i}\in\\{0,1\\}$ and
$k=0$ are uniquely determined from $C$. In this situation, we don’t need to
mention $(t_{i};s_{j};k)$ and the Kelmans transformation $C_{b}^{a}$ of $C$
from $b$ to $a$ is the adjacency matrix of the graph obtained by the Kelmans
transformation of an undirected graph defined by A.K. Kelmans [7].

P. Csikvári proved that the largest real eigenvalues of adjacency matrices
will not be decreased after a Kelmans transformation of an undirected graph
[4]. The following theorem is a generalization of this result to a nonnegative
matrix which is not necessary to be symmetric.

######  Theorem 2.1.

[8] Let $C=(c_{ij})$ denote a nonnegative square matrix of order $n$ such that
$c_{ab}=c_{ba}$ for some $1\leq a,b\leq n$. Choose $k,t_{i},s_{i}$ for
$i\in[n]-\\{a,b\\}$ that satisfy (1),(2). Let
$C_{b}^{a}=C_{b}^{a}(t_{i};s_{i};k)$ be the Kelmans transformation from $b$ to
$a$ with respect to $(t_{i};s_{j};k)$. Then $\rho(C)\leq\rho(C_{b}^{a}).$ ∎

It worths mentioning that Theorem 2.1 appearing in [8] has the additional
assumption $c_{aa}=c_{bb}$. The interested reader might trace the proof in [8]
and find that the same proof works fine for this slightly more general
situation here.

As in the case of undirected graph, if $C$ in Theorem 2.1 is the adjacency
matrix of a mixed graph $G$ and assume that $C_{b}^{a}$ is also an adjacency
matrix of some mixed graph, then $t_{i},s_{i}\in\\{0,1\\}$ and $k=0$ are
uniquely determined from $C$. We use $G_{b}^{a}$ to denote the mixed graph
whose adjacency matrix is $C_{b}^{a}$ and called $G_{b}^{a}$ the Kelmans
transformation of mixed graph $G$ from $b$ to $a$. Notice that when the
notation $G_{b}^{a}$ appears, we always assume that $a,b\in V(G)$ are distinct
and have no arc, i.e. $\vv{ab}\notin E(G)$ and $\vv{ba}\notin E(G)$. Figure 1
shows how the Kelmans transformation on mixed graph works.

$b$$a$$b$$a$$G$$G_{b}^{a}$ Figure 1: Kelmans transformation on mixed graph
$G$.

For a mixed graph $G$, let $N^{+}_{G}(u):=\\{v\colon\vv{uv}\in E(G)~{}{\rm
or~{}}uv\in E(G)\\}$ be the set of out-neighbors of $u$,
$N^{-}_{G}(u):=\\{v\colon\vv{vu}\in E(G)~{}{\rm or~{}}uv\in E(G)\\}$ be the
set of in-neighbors of $u$, and $N_{G}(u):=N^{+}_{G}(u)\cup N^{-}_{G}(u)$ be
the set of neighbors of $u$. The number $d^{+}_{G}(u):=|N^{+}_{G}(u)|$ is
called the out-degree of $u$ in $G$, and the number
$d_{G}(u):=|N^{+}_{G}(u)|+|N^{-}_{G}(u)|$ is called the degree of $u$ in $G$.
The sequence $d(G):=(d_{G}(u))_{u\in V(G)}$ in descending order is called the
degree sequence of $G$. In the rest of this paper, the order of degree
sequences are considered in dictionary order, that is,
$(a_{1},a_{2},\ldots,a_{n})>(b_{1},b_{2},\ldots,b_{n})$ if for the minimum $i$
with $a_{i}\not=b_{i}$, we have $a_{i}>b_{i}$. The (i) of the following lemma
in mixed graph is generalized from its undirected graph version [7].

######  Lemma 2.2.

Let $G$ be a mixed graph and distinct $a,b\in V(G)$ have no arc. Then the
following (i)-(ii) hold.

  1. (i)

The involution $f:V(G_{b}^{a})\rightarrow V(G_{a}^{b})$ defined by

$f(x)=\left\\{\begin{array}[]{ll}a,&\hbox{if $x=b$;}\\\ b,&\hbox{if $x=a$;}\\\
x,&\hbox{otherwise}\end{array}\right.$

is a graph isomorphism from $G_{b}^{a}$ to $G_{a}^{b}$.

  2. (ii)

In dictionary order, $d(G_{b}^{a})\geq d(G)$. Moreover, the following (a)-(c)
are equivalent.

    1. (a)

$d(G_{b}^{a})=d(G)$;

    2. (b)

$G$ is isomorphic to $G_{b}^{a}$;

    3. (c)

$N^{+}_{G}(a)-\\{b\\}\subseteq N^{+}_{G}(b)-\\{a\\}$ and
$N^{-}_{G}(a)-\\{b\\}\subseteq N^{-}_{G}(b)-\\{a\\}$; or
$N^{+}_{G}(b)-\\{a\\}\subseteq N^{+}_{G}(a)-\\{a\\}$ and
$N^{-}_{G}(b)-\\{a\\}\subseteq N^{-}_{G}(a)-\\{b\\}$.

###### Proof.

Excluding the two vertices $a,b$ which are either with an undirected edges or
without any directed arcs by the assumption, we have the following three
observations of neighbor sets from the definition of Kelmans transformation on
$G$ from $b$ to $a$. (1) the set of out-neighbors (resp. in-neighbors) of $b$
in $G_{b}^{a}$ is the union of the set of out-neighbors (resp. in-neighbors)
of $a$ in $G$ and the set of out-neighbors (resp. in-neighbors) of $b$ in $G$;
(2) the set of out-neighbors (resp. in-neighbors) of $a$ in $G_{b}^{a}$ is the
intersection of set of the out-neighbors (resp. in-neighbors) of $a$ in $G$
and the set of out-neighbors (resp. in-neighbors) of $b$ in $G$; (3) the set
of out-neighbors (resp. in-neighbors) of $x\not=a,b$ in $G_{b}^{a}$ is the
same as that in $G$. From the above three observations, we find that vertices
$a,b,x$ in $G_{b}^{a}$ play the role of $b,a,x$ respectively in $G_{a}^{b}$.
This proves (i).

(ii) In the proof of (i), we also have $d_{G}(x)=d_{G_{b}^{a}}(x)$ for $x\in
V(G)-\\{a,b\\}$ and in dictionary order
$(d_{G_{b}^{a}}(a),d_{G_{b}^{a}}(b))\geq(\max(d_{G}(a),d_{G}(b)),\min(d_{G}(a),d_{G}(b)))$,
together implying $d(G_{b}^{a})\geq d(G)$. Next we prove that (a), (b) and (c)
are equivalent.

((b) $\Rightarrow$ (a)) This is clear.

((a) $\Rightarrow$ (c)) Suppose $d(G_{b}^{a})=d(G)$. From the proof of (ii)
above, we have
$\\{d_{G}(a),d_{G}(b)\\}=\\{d_{G_{b}^{a}}(a),d_{G_{b}^{a}}(b)\\}$. If
$d_{G}(a)=d_{G_{b}^{a}}(b)$ then $d_{G}(b)=d_{G_{b}^{a}}(a)\geq
d_{G_{b}^{a}}(b)=d_{G}(a)$, which implies $N^{+}_{G}(a)-\\{b\\}\subseteq
N^{+}_{G}(b)-\\{a\\}$ and $N^{-}_{G}(a)-\\{b\\}\subseteq
N^{-}_{G}(b)-\\{a\\}$. If $d_{G}(a)=d_{G_{b}^{a}}(a)$ then
$d_{G}(b)=d_{G_{b}^{a}}(b)$, which implies $N^{+}_{G}(b)-\\{a\\}\subseteq
N^{+}_{G}(a)-\\{b\\}$ and $N^{-}_{G}(b)-\\{a\\}\subseteq
N^{-}_{G}(a)-\\{b\\}$.

((c) $\Rightarrow$ (b)) If $N^{+}_{G}(a)-\\{b\\}\subseteq
N^{+}_{G}(b)-\\{a\\}$ and $N^{-}_{G}(a)-\\{b\\}\subseteq N^{-}_{G}(b)-\\{a\\}$
then $G=G_{a}^{b}$ and the latter is isomorphic to $G_{b}^{a}$ by (i). If
$N^{+}_{G}(b)-\\{a\\}\subseteq N^{+}_{G}(a)-\\{b\\}$ and
$N^{-}_{G}(b)-\\{a\\}\subseteq N^{-}_{G}(a)-\\{b\\}$ then $G=G_{b}^{a}$. ∎

For a square matrix $M$, let ${\rm char}(M):={\rm det}(\lambda I-M)$ denote
the characteristic polynomial of $M$. The following lemma is immediate from
the definition of characteristic polynomial of $M$.

######  Lemma 2.3.

For an $n\times n$ nonnegative matrix $M$, if

$M=\begin{pmatrix}M_{1}&M_{2}\\\
0&M_{3}\end{pmatrix}\quad{\rm~{}or~{}}\quad\begin{pmatrix}M_{1}&0\\\
M_{2}&M_{3}\end{pmatrix}$

where $M_{1},M_{3}$ are square matrices, then ${\rm char}(M)={\rm
char}(M_{1})\cdot{\rm char}(M_{2})$.∎

For an $n\times n$ matrix $M$ and a partition
$\Pi=\\{\pi_{1},\pi_{2}\ldots,\pi_{\ell}\\}$ of $[n]$, the $\ell\times\ell$
matrix $\Pi(M)=(m^{\prime}_{ij})$, where

$m^{\prime}_{ab}=\frac{1}{|\pi_{a}|}\sum_{i\in\pi_{a},j\in\pi_{b}}m_{ij}\qquad(1\leq
a,b\leq\ell),$

is called the quotient matrix of $M$ with respect to $\Pi$. Furthermore, if
for all $1\leq a,b\leq\ell$ and $i\in\pi_{a}$,
$\sum_{j\in\pi_{b}}m_{ij}=m^{\prime}_{ab}$, then $\Pi(M)$ is called the
equitable quotient matrix of $M$ with respect to $\Pi$. The following well-
known lemma is useful on the calculating of spectral index. See [1, 3] for
recent proofs.

######  Lemma 2.4.

If $\Pi(M)$ be the equitable quotient matrix of a nonnegative matrix $M$, then
$\rho(M)=\rho(\Pi(M))$. ∎

The following is a well-known consequence of Perron–Frobenius theorem [2].

######  Lemma 2.5.

If $N$ is a nonnegative square matrix and $M$ is a nonnegative matrix of the
same size with $M\leq N$, or $M$ is a nonnegative submatrix of $N$ then
$\rho(M)\leq\rho(N)$. ∎

##  3 The poset $\mathcal{G}(n,m)$ of mixed graphs

For a mixed graph $G$ of order $n$ and size $m$, let $[G]$ denote the set of
mixed graphs that are isomorphic to $G$. Let

$\mathcal{G}(n,m):=\\{[G]~{}\colon~{}G~{}\hbox{is a mixed graph of order $n$
and size $m$}\\}.$ (4)

We will define a reflexive and transitive relation $\leq$ in
$\mathcal{G}(n,m)$ as follows.

######  Definition 3.1.

Let $\leq$ be the relation in $\mathcal{G}(n,m)$ such that for all
$[G],[H]\in\mathcal{G}(n,m)$, $[G]\leq[H]$ if and only if $H$ is isomorphic to
$G$, or $H$ is isomorphic to a graph which is obtained from $G$ by a finite
sequence of Kelmans transformations.

######  Lemma 3.2.

$(\mathcal{G}(n,m),\leq)$ is a partially ordered set (poset).

###### Proof.

The relation $\leq$ is reflexive and transitive from its definition, so we
only need to prove the anti-symmetric property. Suppose $[G]\leq[H]$ and
$[H]\leq[G]$, where $[G],[H],\in G(n,m)$. Then $d(G)\leq d(H)\leq d(G)$ by
Lemma 2.2(ii). Hence $d(G)=d(H)$. By Lemma 2.2(ii)(a)$\Rightarrow$(b), we have
$[G]=[H]$. ∎

######  Lemma 3.3.

Let $\alpha\in[0,1]$, $[G]\in\mathcal{G}(n,m)$ with distinct vertices $a,b\in
V(G)$ having no arc, adjacency matrix $A=(c_{ij})$ and $A_{\alpha}$ matrix
$A_{\alpha}(G)$ of $G$. Set $k:=\alpha|N^{+}_{G}(b)-N^{+}_{G}(a)|$,
$t_{i}=(1-\alpha)\max(0,c_{ib}-c_{ia})$ and
$s_{i}=(1-\alpha)\max(0,c_{bi}-c_{ai})$ for $i\in V(G)-\\{a,b\\}$. Then the
Kelmans transformation matrix $A_{\alpha}(G)_{b}^{a}$ of $A_{\alpha}(G)$ from
$b$ to $a$ with respect to $(t_{i};s_{i};k)$ is the $A_{\alpha}$ matrix
$A_{\alpha}(G_{b}^{a})$ of $G_{b}^{a}$, i.e.,

$A_{\alpha}(G)_{b}^{a}=A_{\alpha}(G_{b}^{a}).$

###### Proof.

We only need to check that the $ij$ entries in matrices
$A_{\alpha}(G)_{b}^{a}$ and $A_{\alpha}(G_{b}^{a})$ are equal for one of $i,j$
in $\\{a,b\\}$. Indeed they are equal from the setting listed in the order
$aa$, $bb$, $ia$, $ib$, $aj$ and $bj$ below:

$\displaystyle\alpha d^{+}_{G}(a)+k=$ $\displaystyle\alpha
d^{+}_{G_{b}^{a}}(a),$ $\displaystyle\alpha d^{+}_{G}(b)-k=$
$\displaystyle\alpha d^{+}_{G_{b}^{a}}(b),$
$\displaystyle(1-\alpha)c_{ia}+t_{i}=$
$\displaystyle(1-\alpha)(c_{ia}+\max(0,c_{ib}-c_{ia})),$
$\displaystyle(1-\alpha)c_{ib}-t_{i}=$
$\displaystyle(1-\alpha)(c_{ib}-\max(0,c_{ib}-c_{ia})),$
$\displaystyle(1-\alpha)c_{ia}+s_{j}=$
$\displaystyle(1-\alpha)(c_{aj}+\max(0,c_{bj}-c_{aj}),$
$\displaystyle(1-\alpha)c_{ib}-s_{j}=$
$\displaystyle(1-\alpha)(c_{bj}-\max(0,c_{bj}-c_{aj}),$

where $i,j\in V(G)-\\{a,b\\}$. ∎

######  Proposition 3.4.

If $\alpha\in[0,1]$, and $[G],[H]\in G(n,m)$ such that $[G]\leq[H]$, then
$\rho_{\alpha}(G)\leq\rho_{\alpha}(H).$

###### Proof.

We might assume $H=G_{b}^{a}$ by Lemma 3.2. Applying Theorem 2.1 and Lemma
3.3, we have

$\rho_{\alpha}(G)=\rho(A_{\alpha}(G))\leq\rho(A_{\alpha}(G)_{b}^{a})=\rho(A_{\alpha}(G_{b}^{a}))=\rho_{\alpha}(H).$

∎

##  4 The poset $\mathcal{T}(n,m)$ of mixed trees

Let $n,m\in\mathbb{N}$ with $n-1\leq m\leq 2n-2$,

$\mathcal{T}(n,m):=\\{[T]\in\mathcal{G}(n,m)\colon T\hbox{~{}is a mixed
tree}\\}.$

The set $\mathcal{T}(n,m)$ is not closed under Kelmans transformations. We
need the following lemma.

######  Lemma 4.1.

Let $[T]\in\mathcal{T}(n,m)$ with distinct $a,b\in V(T)$ having no arc. Then
$[T_{b}^{a}]\in\mathcal{T}(n,m)$ if and only if $ab\in E(G)$ or
$\partial(a,b)=2$ and the unique vertex $x\in V(G)$ with
$\partial(a,x)=\partial(x,b)=1$ satisfying one of (i) $ax\in E(G)$ is an
undirected edge, (ii) $xb\in E(G)$ is an undirected edge, (iii)
$\overrightarrow{ax},\overrightarrow{bx}\in E(G)$ are arcs or (iv)
$\overrightarrow{xa},\overrightarrow{xb}\in E(G)$ are arcs.

###### Proof.

The assumption implies $\partial(a,b)\geq 1$ and if $\partial(a,b)=1$ then
$ab\in E(G)$ is an undirected edge. If $\partial(a,b)=2$ and the necessary
condition about $x$ fails then $a,b$ belong to different components of the
underlying graph of $T_{b}^{a}$, so $T_{b}^{a}$ is not a mixed tree. If
$\partial(a,b)\geq 3$ then the underlying graph of $T_{b}^{a}$ contains a
cycle of order $\partial(a,b)$, so $T_{b}^{a}$ is not a mixed tree.

On the other hand, it is straightforward to observe that
$[T_{b}^{a}]\in\mathcal{T}(n,m)$ when $a,b$ satisfy the conditions. ∎

We use the notation $a-b$, $a-x\rightarrow b$, $a-x\leftarrow b$, $a\leftarrow
x-b$, $a\rightarrow x-b$, $a\rightarrow x\leftarrow b$ and $a\leftarrow
x\rightarrow b$ to denote the seven situations in the necessary condition of
Lemma 4.1. We then give $\mathcal{T}(n,m)$ a poset structure by extending
$[T]\leq[T_{b}^{a}]$ for any $[T]\in\mathcal{T}(n,m)$ and any $a,b\in V(T)$
that satisfy one of the seven situations.

######  Proposition 4.2.

Let $[T]\in\mathcal{T}(n,m).$ Then $[T]$ is a maximal element in
$\mathcal{T}(n,m)$ if and only if $T$ is a mixed star or $T$ is a mixed tree
without undirected edges (i.e. $m=n-1$) and whenever the subgraph
$a\rightarrow x\leftarrow b$ or $a\leftarrow x\rightarrow b$ appears in $T$,
one of $a$ and $b$ is a leaf.

###### Proof.

$(\Leftarrow)$ If $T$ is a mixed star, and one of $a-b$, $a-x\rightarrow b$,
$a-x\leftarrow b$, $a\leftarrow x-b$, $a\rightarrow x-b$, $a\rightarrow
x\leftarrow b$ and $a\leftarrow x\rightarrow b$ appearing in $T$, then one of
$a$ or $b$ is a leaf, so Lemma 2.2(iic) with $G=T$ holds, which implies that
$T_{b}^{a}$ is isomorphic to $T$. If $T$ is a mixed tree without undirected
edges, then we only need to consider $a\rightarrow x\leftarrow b$ and
$a\leftarrow x\rightarrow b$ in $T$. By the assumption $a$ or $b$ is a leaf
and by the same reason as above, $T_{b}^{a}$ is isomorphic to $T$. Hence in
both cases, $[T]$ is a maximal element in $\mathcal{T}(n,m)$.

$(\Rightarrow)$ Let $[T]$ be a maximal element in $\mathcal{T}(n,m)$ such that
$T$ is not a mixed star, so $T$ has diameter at least $3$. Keeping in mind
that the maximality of $[T]$ implies that Lemma 2.2(iic) with $G=T$ holds for
$a,b\in V(T)$ satisfying the necessary conditions $a-b$, $a-x\rightarrow b$,
$a-x\leftarrow b$, $a\leftarrow x-b$, $a\rightarrow x-b$, $a\rightarrow
x\leftarrow b$ or $a\leftarrow x\rightarrow b$ of Lemma 4.1, thus at least one
of $a$ or $b$ is a leaf. To exclude the situations $a-b$, $a-x\rightarrow b$,
$a-x\leftarrow b$, $a\leftarrow x-b$ and $a\rightarrow x-b$, on the contrary,
suppose that $T$ contains an undirected edge $uv$ with leaf $u$. Since
diameter of $T$ at least $3$, we have another two vertices $y,z\in V(T)$ such
that $\partial(v,y)=\partial(y,z)=1$ and $\partial(u,z)=3$. Since $v,y$ are
not leafs in $T$, they have an arc, say $v\rightarrow y$ (similar for
$v\leftarrow y$) in $E(T)$. Hence $T_{y}^{u}\in\mathcal{T}(n,m)$ is well-
defined, $v\in(N^{+}_{T}(v)-\\{y\\})-(N_{T}(y)-\\{u\\})$, and $z\in
N_{T}(y)-N_{T}(u)$, a contradiction to the maximality of $[T]$. Thus $T$ has
no undirected edges. ∎

##  5 The upper bound of $\rho_{\alpha}(T)$

If an arc in a mixed tree $T$ is deleted then we have two mixed trees. Thus if
the arcs in a mixed tree $T$ of order $n$ and size $m$ are all removed, then
the remaining is an undirected graph without cycles with $2n-m-1$ components.
We call these $2n-m-1$ components the components of $T$.

######  Lemma 5.1.

If $\alpha\in[0,1]$ and $[T]\in\mathcal{T}(n,m)$ and $T$ has components
$C_{1}$, $C_{2}$, $\ldots$, $C_{t}$, then

${\rm char}(A_{\alpha}(T))=\prod_{i\in[t]}{\rm char}(A_{\alpha}(T)[C_{i}]),$

where $A_{\alpha}(T)[C_{i}]$ is the principal submatrix of $A_{\alpha}(T)$
restricted to $C_{i}$.

###### Proof.

If $\overrightarrow{ij}\in E(T)$ is deleted to obtained two mixed trees with
vertex sets $V$ and $W$, then besides $\overrightarrow{ij}$ there is no arcs
or undirected edges between a vertex in $V$ and a vertex in $W$. With
$M=A_{\alpha}(T)$, $M_{1}=M[V]$, $M_{2}=M[W]$, we find $M$ satisfies the
assumption of Lemma 2.3. Hence ${\rm char}(M)={\rm char}(M_{1})\times{\rm
char}(M_{2})$. We have the lemma by use this process on $M_{1}$ and $M_{2}$,
and repeating again until each matrix is corresponding to a component of $T$.
∎

Note that $A_{\alpha}(T)[C_{i}]$ in Lemma 5.1 is not the $A_{\alpha}$ matrix
of the component $C_{i}$ in $T$.

######  Corollary 5.2.

If $\alpha\in[0,1]$ and $[T]\in\mathcal{T}(n,n-1)$, then

${\rm char}(A_{\alpha}(T))=\prod_{i\in[n]}(\lambda-\alpha d_{i}^{+}).$

###### Proof.

For $[T]\in\mathcal{T}(n,n-1)$, each vertex forms a component. Since
$A_{\alpha}(T)[\\{i\\}]$ is an $1\times 1$ matrix with entries $\alpha
d_{i}^{+}$, the result is straightforward from Lemma 5.1. ∎

######  Proposition 5.3.

Let $S$ be mixed star of order $n$, size $m$ and maximum out-degree $m-n+k+1$
for some $0\leq k\leq 2n-m-2$. Then for $\alpha\in[0,1]$, the
$A_{\alpha}$-spectral radius $\rho_{\alpha}(S)$ of $S$ is the maximal root of
the following quadratic polynomial in $\lambda$:

$(\lambda-\alpha)(\lambda-\alpha(m-n+k+1))-(1-\alpha)^{2}(m-n+1).$ (5)

###### Proof.

Note that there are $m-n+1$ undirected edges in $S$. For convenience, assume
that $1$ has the maximum degree $n-1$, $N^{+}_{S}(1)=[m-n+k+2]-\\{1\\}$ and
$N^{-}_{S}(1)=([m-n+2]-\\{1\\})\cup\\{m-n+k+3,m-n+k+4,\ldots,n\\}$.

$\pi_{1}$$\pi_{2}$$\pi_{4}$$\pi_{3}$ Figure 2: The partition $\Pi$ of the
vertices of a mixed star.

Set $\pi_{1}=\\{1\\},$ $\pi_{2}=\\{2,3,\ldots,m-n+2\\},$
$\pi_{3}=\\{m-n+3,m-n+4,\ldots,m-n+k+2\\},$ and
$\pi_{4}=[n]-\pi_{1}-\pi_{2}-\pi_{3}$ as illustrated in 2. With respect to the
partition $\Pi=\\{\pi_{1},\pi_{2},\pi_{3},\pi_{4}\\}$ of $[m]$, the adjacency
matrix $A$ and the diagonal out-degree matrix $D^{+}$ of $T$ have equitable
quotient matrices

$\Pi(A)=\begin{pmatrix}0&m-n+1&k&0\\\ 1&0&0&0\\\ 0&0&0&0\\\
1&0&0&0\end{pmatrix}\mbox{ and }\Pi(D^{+})=\begin{pmatrix}m-n+k+1&0&0&0\\\
0&1&0&0\\\ 0&0&0&0\\\ 0&0&0&1\end{pmatrix},$

respectively, which implies that the $A_{\alpha}$ matrix of $T$ has equitable
quotient

$\Pi(A_{\alpha})=\begin{pmatrix}\alpha(m-n+k+1)&(1-\alpha)(m-n+1)&(1-\alpha)k&0\\\
1-\alpha&\alpha&0&0\\\ 0&0&0&0\\\ 1-\alpha&0&0&\alpha\end{pmatrix}.$

Since the characteristic polynomial of $\Pi(A_{\alpha})$ is

$\lambda(\lambda-\alpha)((\lambda-\alpha)(\lambda-\alpha(m-n+k+1))-(1-\alpha)^{2}(m-n+1)),$

and the zero in (5) is at least $\alpha,$ we complete the proof. ∎

Proof of Theorem 1.1. By Proposition 3.4, it suffices to show that for each
maximal element $[T]\in\mathcal{T}(n,m)$ characterized in Proposition 4.2,
$\rho_{\alpha}(T)$ is at most the upper bound appearing in Theorem 1.1.
Suppose $T=S$ is a mixed star with maximal out-degree $m-n+k+1$. Since the
largest root of the quadratic polynomial in (5) increases as lone as $k$
increases, we might assume $k=2n-m-2$, and find (5) becomes

$\lambda^{2}-\alpha n\lambda+\alpha^{2}(n-1)-(1-\alpha)^{2}(m-n+1),$

which has largest root as the upper bound appearing in Theorem 1.1. For the
remaining mixed trees $T\in\mathcal{T}(n,n-1)$, from Corollary 5.2 we know
that the $A_{\alpha}$ matrix of $T$ has characteristic polynomial
$\prod_{i\in[n]}(\lambda-\alpha d_{i}^{+})$, so
$\rho_{\alpha}(T)=\alpha\cdot(\max_{i\in[n]}d_{i}^{+})\leq\alpha(n-1)$, where
the equality holds when $T$ is the star with $n-1$ leaves being out-neighbor
of a vertex. Moreover, $\alpha(n-1)$ is equal to the upper bound appearing in
Theorem 1.1 when $m=n-1$. ∎

##  6 The lower bound of $\rho_{\alpha}(T)$

The following theorem was proved in [12].

######  Theorem 6.1.

([12]) If $T$ is a tree of order $n$ and $\alpha\in[0,1]$, then

$\rho_{\alpha}(T)\geq\rho_{\alpha}(P_{n}).$

Equality holds if and only if $G=P_{n}$. ∎

Proof of Theorem 1.2. Let $T$ be a mixed tree of order $n$ and size $m$. Then
$T$ has $2n-m-1$ components, and there exists a components of order at least
$k=\lceil\frac{n}{2n-m-1}\rceil$. If $m=2n-2$ then $k=n$ and
$\rho_{\alpha}(T)\geq\rho_{\alpha}(P_{k})$ by Theorem 6.1 where the equality
holds when $T=P_{n}$. For $m<2n-2$, let $C_{1}$ be a component of $T$ with
maximum size $t$. Then $t\geq k\geq 2$ and $A_{\alpha}(T)[C_{1}]\geq
A_{\alpha}(C_{1})$. Hence by Lemma 2.5, Lemma 5.1 and Theorem 6.1,

$\rho_{\alpha}(T)\geq\rho(A_{\alpha}(T)[C_{1}])\geq\rho(A_{\alpha}(C_{1}))=\rho_{\alpha}(P_{t})\geq\rho_{\alpha}(P_{k}).$

∎

Acknowledgements. This research is supported by the Ministry of Science and
Technology of Taiwan under the project MOST 109-2115-M-009 -007 -MY2.

## References

  * [1] F. Atik, P. Panigrahi, On the distance and distance signless Laplacian eigenvalues of graphs and the smallest Gerŝgorin disc, Electron. J. Linear Algebra, 34 (2018) 191–204.
  * [2] A.E. Brouwer, W.H. Haemers, Spectra of graphs, Springer, 2012.
  * [3] Y.-J. Cheng, C.-A. Liu, C.-W. Weng, Counterexamples of the Bhattacharya-Friedland-Peled conjecture, arXiv:2112.01124 [math.CO].
  * [4] P. Csikvári, On a conjecture of V. Nikiforov, Discrete Math. 309 (2009) 4522–4526.
  * [5] H.A. Ganie, M. Baghipur, on the generalized adjacency spectral radius of digraphs, Linear Multilinear Algebra. DOI: 10.1080/03081087.2020.1844614.
  * [6] H. Guo, B. Zhou, On the $\alpha$-spectral radius of graphs, Appl. Anal. Discrete Math. 14 (2020) 431–458.
  * [7] A.K. Kelmans, On graphs with randomly deleted edges, Acta Math. Hungar 37 (1981) 77–88.
  * [8] L. Kao, C.-W. Weng, A note on the largest real eigenvalue of a nonnegative matrix, Appl. Math. Sci. 15(12) (2021) 553–557.
  * [9] D. Li, Y. Chen, J. Meng, $A_{\alpha}$-spectral radius of trees and unicyclic graphs with given degree sequence, Appl. Math. Comput. 363 (2019) 124622.
  * [10] J. Liu, X. Wu, J. Chen, B. Liu, The $A_{\alpha}$-spectral radius characterization of some digraphs, Linear Algebra Appl. 563 (2019) 63–74.
  * [11] V. Nikiforov, Merging the $A$\- and $Q$-spectral theories, Appl. Anal. Discrete Math. 11 (1) (2017) 81–107.
  * [12] V. Nikiforov, G. Pastén, O. Rojo, R.L. Soto, On the $A_{\alpha}$-specra of trees, Linear Algebra Appl. 520 (2017) 286–306.
  * [13] O. Rojo, The maximal $\alpha$-index of trees with $k$ pendent vertices and its computation, eletronic J. Linear algebra. 36 (2020) 38–48.
  * [14] W. Xi, W, So, L. Wang, On the $A_{\alpha}$ spectral radius of digraphs with given parameters, Linear Multilinear Algebra. DOI: 10.1080/03081087.2020.1793879.


# GARA: A novel approach to Improve Genetic Algorithms’ Accuracy and
Efficiency by Utilizing Relationships among Genes

Zhaoning Shi1,*, Mengxiang2,*, Zhaoyang Hai1, Xiabi Liu1,${\dagger}$, Yan
Pei2,${\dagger}$ *: Equal contributions${\dagger}$: Corresponding author 1 Z.
Shi, Z. Hai and X. Liu are with School of Computer Science and Technology,
Beijing Institute of Technology, Beijing, China, 100081. (e-mail:{3220235133,
haizhaoyang, liuxiabi}@bit.edu.cn)2 X. Meng and Y. Pei are with School of
Computer Science and Engineering, University of Aizu, Aizuwakamatsu, Japan,
965-8580. (e-mail:{d8242104, peiyan}@u-aizu.ac.jp)Manuscript received April
19, 2021; revised August 16, 2021.

###### Abstract

Genetic algorithms (GA) have played an important role in engineering
optimization. Traditional GAs treat each gene separately. However, biophysical
studies of gene regulatory networks revealed direct associations between
different genes. It inspires us to propose an improvement to GA in this paper,
Gene Regulatory Genetic Algorithm (GRGA), which, to our best knowledge, is the
first time to utilize relationships among genes for improving GA’s accuracy
and efficiency. We design a directed multipartite graph encapsulating the
solution space, called RGGR, where each node corresponds to a gene in the
solution and the edge represents the relationship between adjacent nodes. The
edge’s weight reflects the relationship degree and is updated based on the
idea that the edges’ weights in a complete chain as candidate solution with
acceptable or unacceptable performance should be strengthened or reduced,
respectively. The obtained RGGR is then employed to determine appropriate loci
of crossover and mutation operators, thereby directing the evolutionary
process toward faster and better convergence. We analyze and validate our
proposed GRGA approach in a single-objective multimodal optimization problem,
and further test it on three types of applications, including feature
selection, text summarization, and dimensionality reduction. Results
illustrate that our GARA is effective and promising.

###### Index Terms:

genetic algorithms, evolutionary computing algorithms, gene regulatory,
crossover loci, mutation locus.

##  I Introduction

Since the appearance of the genetic algorithm (GA) [1], it has provided great
help for the optimization of many engineering problems, and the improvement of
GA has always been an important research direction. There are two categories
of improvement. The first category focuses on the key operations of GA, such
as coding [2], population [3], selection [4], crossover [5], and mutation [6],
[7]. The second category tries to develop new frameworks, such as parallel
genetic algorithms through the parallel iteration of individuals [8], chaotic
genetic algorithms by adding a chaotic system [9], and hybrid genetic
algorithms through combining with other types of optimization methods [10].

One shortcoming of GAs and their advanced extensions is the lack of
consideration for the relationships among different solution components, i.e.,
each gene in a solution is independent. This is reflected in the fact that the
loci of crossover and mutation operations are randomly selected, which could
incur the unreasonable disruption of local interactive gene sequences,
reducing the effectiveness of gene search [11]. In fact, biological gene
segments do not work independently of each other; instead, they interact with
each other in various ways [12]. We illustrate two cases in Fig. 1(a). The
first case is that one gene could regulate the expression of another. As shown
in Fig. 1(a), in Arabidopsis floral organ development, the expression product
of the LEAFY (LFY) gene, which has the characteristics of a pioneer
transcription factor, binds directly to chromatin condensation zones and
alters the chromatin state of its target genes, regulating the expression of
APETALA1 (AP1) [13]. The second case is that the product of one gene
expression requires the product of another gene expression to act before it
can act. As shown in Fig. 1(b), the process of the human body finally
synthesizes adrenaline from tyrosine through the sequential process:
L-Tyrosine → L-DOPA → Dopamine → Noradrenaline → Adrenaline, which suggests
that there is a sequential effect of gene fragments on the whole regulatory
process.

Figure 1: Interactions between genes. a. The expression product of the LEAFY
(LFY) gene regulates APETALA1 (AP1) expression. b.The sequential process from
tyrosine input to the final production of adrenaline.

Drawing inspiration from gene regulatory networks in biophysics, this paper
proposes a novel genetic algorithm through the consideration of sequential
interactions of genetic codes, thereby enhancing performance and improving
efficiency. We name this approach the Gene Regulatory Genetic Algorithm
(GRGA). The core of GRGA is a directed Relationship Graph representing Gene
Regulation (RGGR). Each directed chain in RGGR corresponds to a gene
regulatory process. The larger the weight of an edge in the chain, the more
reasonable the interaction between the two nodes is, and vice versa.
Therefore, if the fitness of the individuals containing an edge tends to be
promising, the weight of this edge will be gradually increased with the
evolution process. In this way, the RGGR is updated. Then it is employed to
guide gene crossover and mutation operations for reducing unreasonable
disruption of interactive gene segments and finally improving the
effectiveness and efficiency of searching. We evaluate the proposed GRGA on
single-objective multimodal optimization problems and three applications
including feature selection, text summarization, and dimension reduction,
where GRGA is compared with the most advanced GAs.

The main contributions of this paper are listed as follows:

  * (1)

To our best knowledge, this is the first genetic algorithm to consider the
sequential interaction between genes to alleviate unreasonable disruption of
local structures, which aligns with the mechanism of gene regulatory networks
in biophysics.

  * (2)

We introduce a relationship graph representing gene regulation, called RGGR,
and design a method to update RGGR in the evolution process for measuring
interaction degrees between genes.

  * (3)

The RGGR is used to perform more reasonable crossover and mutation operations
to improve the effectiveness and efficiency of searching.

  * (4)

The proposed GRGA can be widely applied to extend and improve various genetic
algorithms. Careful experiments prove the advantages of our approach.

##  II Related Work

###  II-A New frameworks of GA

Our GRGA can be regarded as a new framework of genetic algorithms (GAs).
Previous research in this direction mainly includes parallel, chaotic, and
hybrid GAs. Parallel GAs can be further categorized into master-slave
parallel, fine-grained parallel, and coarse-grained parallel [8]. The master-
slave parallel GA is primarily used for parallel fitness calculation. The
fine-grained parallel GA does not exchange individuals between subpopulations,
and genetic operations are only performed on topologically adjacent
subpopulations, while the coarse-grained parallel GA exchanges individuals
between subpopulations. Chaotic GA addresses the premature convergence problem
by introducing a chaotic system into the genetic algorithm [9], where
crossover and mutation operations are replaced by chaotic maps. Hybrid GAs
[10] combine GA with other optimization methods, such as Simulated Annealing
(SA) [14], Grey Wolf Optimizer (GWO) [15], and Tabu Search (TS) [16], to
improve performance.

In summary, these frameworks primarily incorporate genetic algorithms
alongside other optimization techniques, rather than fundamentally altering
the genetic algorithm itself.

###  II-B Crossover and mutation operators

The intuitive role of our GRGA in improving traditional GAs is that the
crossover and mutation loci are replaced by new ones from GRGA. Determining
appropriate crossover and mutation positions by GRGA helps avoid unnecessary
search space and concentrates the search in regions that may contain better
solutions, thereby enhancing the search capability of genetic algorithms.
Recent efforts in designing new crossover and mutation operators are briefly
introduced below. Xue [17] used an adaptive operator selection mechanism and
five crossover operators with different search characteristics to improve the
performance of GAs in feature selection tasks. Hvattum [18] proposed an
improved operator based on the OX crossover operator for hybrid genetic
search, and enhanced the efficiency of the algorithm on the capacitated
vehicle routing problem by filling the remaining part of the new solution into
a specific location. Manzoni [19] proposed and studied a variety of balanced
crossover and recombination operators that maintain the Hamming weight of bit
strings to improve the effectiveness of GAs in combination optimization
problems. Yi [20] introduced an adaptive mutation operator to improve the
performance of the standard NSGA-III algorithm. By designing a variable
mutation rate, they improved its performance on multi-objective optimization
problems.

Although many improved crossover and mutation operators have been proposed,
the problem of deciding reasonable loci of crossover and mutation remains
unexplored.

##  III The Proposed Method

###  III-A The principle of GRGA

Figure 2: The working principle of our GRGA. a. Relationship graph
representing gene regulation (RGGR), where the weight value in the edge
represents the relationship degree between each part of the solution is
updated from the fitnesses of individuals. b. Crossover loci were selected by
RGGR. c. Mutation locus was selected by RGGR.

Let the alphabet set for coding the genes of a solution sequence to a problem
be $\chi=\\{1,2,\ldots,n\\}$.

Then a solution is represented as $G:2-1-3-4-7$.

The working principle of our GRGA is illustrated in Fig. 2 Taking the solution
sequences with a length of 5 as an example, the solution space with the
relationship between adjacent genes is represented by our RGGR as shown in
Fig. 2(a)). Based on RGGR, the appropriate loci in the solution sequence for
performing crossover and mutation are inferred in Fig. 2(b) and Fig. 2(c).
Details are given in the following subsections.

###  III-B RGGR Calculation

In RGGR, each node corresponds to a gene in the solution sequence, and the
edges represent the relationship between two adjacent nodes. We can analogize
the process of searching for a solution to a gene regulatory pathway, in which
each node unfolds in turn, with one node triggering the next node to occur.
The complete chain in RGGR is a single solution. To simplify the problem, we
assume a first-order Markov process, i.e., a node is only affected by its
previous node. The weight of an edge reflects the transition probability
between adjacent nodes. We dynamically compare and adjust the transition
probabilities between genes to guide the population to evolve toward a more
favorable solution.

Let $n_{i}^{k}$ and $n_{j}^{k+1}$ represent the $i$-th node in the $k$-th
column and the $j$-th node in the $(k+1)$-th column in RGGR, respectively. Let
$W_{(i,j)}^{(k,k+1)}$ denote the weight of the edge between these two nodes,
where $W_{(i,j)}^{(k,k+1)}\geq 0$. The larger $W_{(i,j)}^{(k,k+1)}$ is, the
stronger the correlation between $n_{i}^{k}$ and $n_{j}^{k+1}$ is.

Initially, all $W_{(i,j)}^{(k,k+1)}$ are set to 1. They are then updated based
on the quality of candidate solutions. To do this, we introduce a threshold
value $\lambda$ to determine whether a solution is acceptable. Let $\Delta$
represent the difference between the fitness value of the considered
individual and the average fitness value of the current population.

If $\Delta\geq\lambda$, the individual as a complete chain in RGGR, exhibits
sufficiently desirable performance. Consequently, each component of the
solution is considered reasonable. Therefore, we can reinforce the weights of
each local structure within the solution, facilitating more precise guidance
for the genetic algorithm to alleviate unreasonable structures in subsequent
iterations. This implies that the weights of the corresponding edges appearing
in this chain in the RGGR should be strengthened. Formally,

$\begin{cases}W_{(i,j)}^{(k,k+1)}\neq 0:\quad\quad\quad\text{(1-1)}\\\ \quad
W_{(i,j)}^{(k,k+1)}=\max\left\\{W_{(i,j)}^{(k,k+1)}+\frac{\Delta}{\Delta+\rho}\cdot
V\left(W_{(i,j)}^{(k,k+1)}\right),0\right\\};\\\
W_{(i,j)}^{(k,k+1)}=0:\quad\quad\quad\text{(1-2)}\\\ \quad
W_{(i,j)}^{(k,k+1)}=W_{(i,j)}^{(k,k+1)}+\mu\Delta\end{cases}$ (1)

In Eq. 1, $V(W_{(i,j)}^{(k,k+1)})>0$ serves as a control function to prevent a
certain $W_{(i,j)}^{(k,k+1)}$ from increasing excessively before receiving
sufficient updates. The function $V$ is a function that varies with the
problem and can also be a constant. It needs to be designed according to
specific applications. We provide examples in the experiment section. $\rho>0$
is a control coefficient for the update rate. By introducing $\rho$, the
influence of fitness $\Delta$ on the weight update can be limited within the
range [0, 1], and $\mu$ within the range $(0,1)$.

In order to enhance the diversity of the population and improve the global
search capability, we propose a fixed strategy to increase the competitiveness
of nodes with $W_{(i,j)}^{(k,k+1)}=0$. This strategy promotes the
participation of these nodes in reproduction and gene exchange, thus enhancing
population diversity and global search capability.

If $\Delta<\lambda$, indicating that there are unreasonable local structures
in the solution sequence, the weight of the corresponding edges appearing in
this chain in the RGGR can be reduced.

Reversing Eq. 1, we obtain

$\begin{cases}W_{(i,j)}^{(k,k+1)}\neq 0:\quad\quad\quad\text{(2-1)}\\\ \quad
W_{(i,j)}^{(k,k+1)}=\max\left\\{W_{(i,j)}^{(k,k+1)}-\frac{\Delta}{\Delta+\rho}\cdot
V\left(W_{(i,j)}^{(k,k+1)}\right),0\right\\};\\\
W_{(i,j)}^{(k,k+1)}=0:\quad\quad\quad\text{(2-2)}\\\ \quad
W_{(i,j)}^{(k,k+1)}=\max\left\\{W_{(i,j)}^{(k,k+1)}-\mu\Delta,0\right\\},\end{cases}$
(2)

When an edge appears in multiple individuals simultaneously, its weight
undergoes repeated adjustments using Eq. 1 and Eq. 2.

To make it less confusing, for the rest of this section, we use
$W_{n}^{(k,k+1)}$ instead of $W_{n,(i,j)}^{(k,k+1)}$, $n$ stands for the
$n-th$ individual share two same genetic loci.

As shown in Fig. 3, we have two individuals, “Individual 1 and Individual 2”,
which individuals possess two loci, $n_{1}^{1}$ and $n_{1}^{2}$. $n_{1}^{1}$
and $n_{1}^{2}$ are connected by $W_{(1,1)}^{(1,2)}$, so this
$W_{(1,1)}^{(1,2)}$ has to be updated twice:
$W_{1}^{(1,2)}=W_{(1,1)}^{(1,2)}+\frac{\Delta}{\Delta+\rho}V(W_{(1,1)}^{(1,2)})$
$W_{2}^{(1,2)}=W_{1}^{(1,2)}+\frac{\Delta}{\Delta+\rho}V(W_{1}^{(1,2)}$

Figure 3: We give an example showing that when two gene loci are shared by two
individuals, this is how the edges connected by these two individuals
calculate the value of W.

We define that when an edge is shared by N individuals in the population(Eq.
3), the weight $W_{n}^{(k,k+1)}$ requires recalculation and updating,
resulting in N updates corresponding to the number of individuals sharing the
edge.

$W_{n+1}^{(k,k+1)}=W_{(i,j)}^{(k,k+1)}+\sum_{n=1}^{N}\left(\frac{\Delta}{\Delta+\rho}\cdot
V\left(W_{n}^{(k,k+1)}\right)\right)$

(3)

When $n=0$, $W_{0}^{(k,k+1)}=W_{(i,j)}^{(k,k+1)}$,When $n=0$,
$W_{0}^{(k,k+1)}=W_{(i,j)}^{(k,k+1)}$ implies that no two or more individuals
share two same genetic loci.

These adjustments occur separately for each instance of the edge in different
individuals, leading to multiple updates. This approach helps maintain
population diversity and enhances the algorithm’s exploration of the solution
space, reducing the chances of encountering local optima.

Figure 4: How to choose crossover and mutation loci. We provide an example to
illustrate the crossover and mutation processes of GRGA in detail.

###  III-C Inferring Crossover Loci and Mutation Locus based on RGGR

After the RGGR is updated as above, we use it to guide the crossover and
mutation operators. Reasonable crossover and mutation loci can make the
offspring evolve towards the optimal solution more accurately. We calculate
the following formula

$s_{(i,j)}^{(k,k+1)}=\frac{1}{C_{1}+C_{2}W_{(i,j)}^{(k,k+1)}}$ (4)

as the basis of selecting crossover and mutation loci. In Eq. 4, the
introduction of $C_{1}$ and $C_{2}$ in the equation is intended to regulate
the effect of $W_{(i,j)}^{(k,k+1)}$. $C_{1}$ ensures that calculations can be
performed even if $W_{(i,j)}^{(k,k+1)}=0$, while $C_{2}$ serves to adjust the
influence of $W_{(i,j)}^{(k,k+1)}$. The crossover process initiates with the
computation of the selection probability for each gene locus to potentially
act as a crossover locus. This computation relies on the strength values
attributed to the genes within the individuals’ genomes. We calculate the sum
of $s_{i,j}^{(k,k+1)}$ for alleles of the two parent chains, like
$S_{i,j_{1}j_{2}}^{(k,k+1)}=s_{i,j_{1}}^{(k,k+1)}+s_{i,j_{2}}^{(k,k+1)}$.

As shown in Fig. 4, we compute $S_{i,j_{1}j_{2}}^{(k,k+1)}$, such as
$S_{1,34}^{(1,2)}=s_{1,3}^{(1,2)}+s_{1,4}^{(1,2)}$.

Suppose the results are $s_{i,j}^{(k,k+1)}$ and $S_{i,j_{1}j_{2}}^{(k,k+1)}$,
based on which we calculate the probability $p_{k}$ of selecting the $k-th$
locus for performing crossover and mutation by Eq. 5 and Eq. 6, respectively,
where $K=length$ $of$ $gene$ $sequence-1$ and is the number of possible loci.

$P_{crossover}=\frac{S_{i,j_{1}j_{2}}^{(k,k+1)}}{\sum_{k=0}^{K}S_{i,j_{1}j_{2}}^{(k,k+1)}}\times
100\%$ (5)

$P_{mutation}=\frac{s_{i,j}^{(k,k+1)}}{\sum_{k=0}^{K}s_{i,j}^{(k,k+1)}}\times
100\%$ (6)

To sum up, we give the pseudo code of our GRGA in Algorithm 1.

Algorithm 1 Gene Regulatory Genetic Algorithm (GRGA)

1:$Parents\leftarrow$ Random initialization population

2:$Child\leftarrow\emptyset$

3:while not (Termination conditions) do

4: Gene sequence expressed as genetic representation

5: Generate the solution from the representation, calculate the effectiveness
of the solution as the fitness

6: Update the genetic representation action diagram according to Eq. 1 and Eq.
2 above: $W_{(i,j)}^{(k,k+1)}$

7: Update the new RGGR according to Eq. 4

8: Dynamically adjust the probability of selecting crossover loci by balancing
the relationship between individual similarities and maintaining population
diversity as described in Eq. 5.

9: Dynamically adjust the probability of selecting mutation locus by
considering individual mutation frequencies as described in Eq. 6.

10: $Child\leftarrow$ survival selection

11:end while

12:return solution

###  III-D Apply the proposed method

GRGA does not require specific selection, crossover, or mutation operations,
we can easily extend traditional GAs into GRGA strengthened ones as follows:

  * •

Design the RGGR according to the search space of the problem.

  * •

After obtaining the fitness of individuals, update RGGR according to the
method described in Section 3.B.

  * •

In crossover and mutation operations, replace randomly selected loci with RGGR
selected loci.

##  IV Experiments

We first validate and analyze our GRGA by conducting function evaluations
using a benchmark from Competitive Evolutionary Computation (CEC), then we
test it in three typical applications of genetic algorithm, including feature
selection, text summarization, and dimension reduction. The proposed GRGA is
embedded into the latest and most advanced GAs for these three applications.

###  IV-A Verification and Analysis of GRGA

We opt for the Shubert(3 dimensions) function from the CEC2013 test function
set as our experimental subject. This choice stems from the function’s
inherent multimodal characteristics, which present challenges in navigating
intricate solution spaces with multiple peaks.

The expression for Shubert is given by:

$F(x)=-\prod_{i=1}^{D}\sum_{j=1}^{5}j\cos[(j+1)x_{i}+j]$ (7)

This function has a total of 81 peaks, with the maximum value being 2709.0935.
We configured the parameters of GRGA with a population size of 200, mutation
rate of 0.05, evolution generations of 30, and a scaling factor (f) of 0.3. We
conducted a comprehensive analysis through 100 Monte Carlo experiments. To
ensure consistency with the comparison, we set GA parameters identical to
those of GRGA.

We aim to rigorously assess GRGA’s effectiveness in simultaneously exploring
and converging to diverse peaks, highlighting its robustness and adaptability
in handling complex optimization landscapes.

Figure 5: The evolution of maximum and average fitness of GRGA and original GA
over 100 experiments with evolving generations.

Fig. 5 illustrates the evolution of average maximum fitness and population
average fitness over 100 experiments with evolving generations. The results
showed that the difference between GRGA and original GA was not significant in
the first 5 generations of population average fitness. However, after the 10th
generation, the population average fitness of GRGA began to significantly
exceed that of the original GA. GRGA’s ascent rate and final convergence
performance surpass those of the original GA.

As the RGGR structure in GRGA currently only applies to discrete genes, we
discretized the three variables of Shubert function within the interval
[-10,10] into 60 integers from 0 to 59. The values of nodes in the RGGR
displayed in Fig. 6 correspond to these discrete values. In RGGR, determine
the top five most weighted values for each gene sequence in the last
generation.

As depicted in Fig. 6, the peak weight for $x_{1}$ is observed at the 7th
interval, with a value of 72.20. Considering the function’s solution space
spans from $(-10,10)$, and each dimension is subdivided into 60 intervals, the
computation of $x_{1}$ is performed as follows:

$W_{0,7}^{(0,1)}:x_{1}=\left(\frac{[10-(-10)]\times
7}{60}\right)+(-10)=\frac{-23}{3};$

Similarly, we can derive that:

$\max(W_{(i,j)}^{(1,2)})=W_{7,9}^{(1,2)}=191.33$,

$W_{7,9}^{(1,2)}:x_{2}=\left(\frac{[10-(-10)]\times 9}{60}\right)+(-10)=-7;$

$\max(W_{(i,j)}^{(2,3)})=W_{9,9}^{(2,3)}=193.61$.

$W_{9,9}^{(2,3)}:x_{3}=\left(\frac{[10-(-10)]\times 9}{60}\right)+(-10)=-7.$

The points($\frac{-23}{3},-7,-7$), which as shown in the red circle in Fig. 7
represent the global optimal solutions found by GRGA.

Figure 6:  TOP5 weighted heatmap. Each row represents a dimension of the
solution space. In the figure, the colors indicate the top five genetic loci
with the highest weights in each dimension. The depth of color reflects the
magnitude of the weight value, where a darker color signifies a larger weight
value.

Through in-depth analysis of the experimental results, we focus on the key
component of GRGA, i.e., RGGR, and reveal its function and role in the
optimization process.

##### Local structure guidance

In RGGR, the weight reflects the quality of each local structure, indicating
the potential effectiveness of specific combinations of independent variables.
As depicted in Fig. 7, each line represents the fitness function’s variation
with $x_{1}$ and $x_{2}$ held constant, while $x_{3}$ varies within the range
of -10 to 10. It is notable that only the blue line corresponds to the
instance where the maximum fitness value is achieved. This observation
underscores RGGR’s capacity to autonomously select local structures, guiding
the overall evolution process.

##### Global optimization capability

In the experiment, RGGR enables GRGA to rapidly and effectively search for and
converge to optimal solutions within fewer generations. Specifically, the
combination $x_{1}=\frac{-23}{3}$, $x_{2}=-7$, and $x_{3}=-7$ emerged as
optimal. By dynamically adjusting the weights of local structures, RGGR
enhances GA’s search efficiency, facilitating quicker convergence towards
global optimal solutions.

##### Interaction between independent variables

Fig. 7 vividly illustrates the impact of $x_{3}$ on the function value,
emphasizing the interplay between independent variables. Notably, the
selection of $x_{1}$ and $x_{2}$ significantly influences achieving higher
function values. This showcases RGGR’s capability to capture intricate
relationships among independent variables, thereby enhancing the likelihood of
discovering potential global optimal solutions.

Overall, RGGR plays a key role in self-selected crossover and mutation
operations through its weight structure. This allows GRGA to selectively
emphasize the self-selection of structures with higher potential fitness,
thereby achieving a more efficient global search throughout the optimization
process.

Figure 7: After fixing the combination relationship of $x_{1}$ and $x_{2}$,
the impact of the value of $x_{3}$ on the fitness of the function. The
independent variable value represented by the structure with the largest
weight can obtain a higher peak value. The notation $x_{1}$-$x_{2}$ in the
legend represents $x_{1}$ taken from the $n_{1}$-th interval in the first
dimension of the solution space, and $x_{2}$ taken from the $n_{2}$-th
interval in the second dimension. The curves in the graph illustrate the
variation of $x_{3}$ across the third dimension of the solution space,
corresponding to changes in the Shubert function’s values.

###  IV-B Application Evaluation

In three application tests, the GRGA parameters are set as follows based on
experiments. In Eq. 1-1 and Eq. 2-1, $\rho$ is set to 0.1 of the average
fitness of the contemporary population. $\mu$ in Eq. 1-2 and Eq. 2-2 is set to
0.8. $C_{1}$ and $C_{2}$ in Eq. 4 are taken as 1 and 0.1, respectively. For
Eq. 1-1 and Eq. 2-1, if $k=0$, the update value is multiplied by 0.5. The
termination condition is set such that the best fitness of the population
remains unchanged for ten consecutive generations.

####  IV-B1 Feature Selection

##### Problem Description

To address the feature selection problem, Altarabichi et al [21] proposed a
new fast genetic algorithm (CHCqx). To verify the advantages of our algorithm
in feature selection, we conducted experiments with our algorithm (GRGA-CHCqx)
on this problem and compared it with CHCqx.

##### Result Analysis

We recorded the running time of the original method and the method extended by
our GRGA. The results are presented in Table I. The average running time of
the original method and our extended method is 39.92 seconds and 27.07
seconds, respectively. Efficiency has increased by more than 32.19%.
Additionally, the effectiveness of feature selection has slightly improved, as
shown in Table I.

TABLE I: The running time of GAs in feature selection. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | mean
---|---|---|---|---|---|---|---|---|---|---|---
CHCqx | 45.13 | 39.78 | 34.19 | 30.08 | 30.99 | 28.11 | 32.36 | 69.98 | 43.25 | 45.36 | 39.92
GRGA-CHCqx | 23.12 | 32.35 | 37.28 | 29.59 | 16.68 | 28.74 | 31.13 | 16.49 | 27.5 | 27.8 | 27.07
TABLE II: The score (accuracy) of feature selection. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Mean
---|---|---|---|---|---|---|---|---|---|---|---
CHCqx | 94.93 | 94.81 | 94.93 | 94.9 | 94.94 | 94.94 | 94.94 | 94.94 | 94.9 | 94.94 | 94.917
GRGA-CHCqx | 94.92 | 94.89 | 94.94 | 94.95 | 94.95 | 94.92 | 94.92 | 94.93 | 94.94 | 94.94 | 94.93
TABLE III: Operation Time (s)

| DUC2005 | DUC2007
---|---|---
MTSQIGA | 278.75 | 123.48
| 283.96 | 116.83
| 282.61 | 126.22
mean | 281.7733 | 122.1767
GRGA-MTSQIGA | 277.98 | 110.14
| 283.4 | 124.25
| 287.91 | 123.18
mean | 283.0967 | 119.19

####  IV-B2 Text Summary

##### Problem Description

In the task of automatically generating text summaries, the quantum heuristic
genetic algorithm (MTSQIGA) [22] has achieved good results on DUC 2005 and
2007 benchmark datasets. We conducted experiments with our algorithm (GRGA-
MTSQIGA) on this problem and compared it with the original method.

TABLE IV: ROUGE scores on DUC 2005. | MTSQIGA | GRGA-MTSQIGA
---|---|---
| ROUGE-1 | ROUGE-2 | ROUGE-SU4 | ROUGE-1 | ROUGE-2 | ROUGE-SU4
Average F-Score | 0.354247 | 0.08112 | 0.13746033 | 0.3595 | 0.081011 | 0.141524
Average Recall | 0.349966 | 0.080165 | 0.136083 | 0.355823 | 0.080181 | 0.139995333
Average Precision | 0.358736 | 0.082108 | 0.13889133 | 0.363382 | 0.081873 | 0.14311
TABLE V: ROUGE scores on DUC 2007. | MTSQIGA | GRGA-MTSQIGA
---|---|---
| ROUGE-1 | ROUGE-2 | ROUGE-SU4 | ROUGE-1 | ROUGE-2 | ROUGE-SU4
Average F-Score | 0.447365 | 0.120771 | 0.18251333 | 0.453382 | 0.124821 | 0.186347667
Average Recall | 0.445665 | 0.120547 | 0.182943 | 0.453013 | 0.124667 | 0.187198667
Average Precision | 0.449274 | 0.121048 | 0.182166 | 0.453983 | 0.125036 | 0.185615667

Figure 8:  Result of accuracy changing with generations.

##### Result Analysis

We recorded the change of average in accuracy of 10 outputs on the data of
d438g in DUC 2005. The results are shown in Fig. 8. Given that the original
algorithm may terminate at different generations, we selected the shortest
duration, which comprised 21 generations, for comparison. This choice was
based on our termination criterion, which stipulated that termination occurs
when the fitness remains unchanged for ten consecutive generations. It can be
seen that the accuracy of GRGA-MTSQIGA improves faster than that of MTSQIGA.
This indicates that RGGR provides a better search direction by guiding
crossover and mutation, which improves the search efficiency of the algorithm.
In terms of convergence effects, in F-score, recall, and precision, the GRGA-
MTSQIGA is significantly better than the original method, as shown in Table IV
and Table V. We also tested the algorithm’s computing efficiency. As shown in
Table III, it can be observed that the addition of our approach has little
effect on the overall computational speed of the algorithm. In addition,
MTSQIGA adopts quantum encoding, which indicates that our algorithm is robust
to the encoding form.

####  IV-B3 Dimensionality Reduction

##### Problem Description

In the task of data dimensionality reduction, literature [23] provides a
genetic algorithm GDR for transparent dimensionality reduction of numerical
data. We incorporate our GRGA into the GDR algorithm (GDR_GRGA).

TABLE VI: Comparative experimental results in dimensionality reduction

Dataset | GDR PostF1 | GDR PostPrec | GDR PostRecall | GDR_GRGA PostF1 | GDR_GRGA PostPrec | GDR_GRGA PostRecall
---|---|---|---|---|---|---
bank_marketing | 0.427 | 0.465 | 0.438 | 0.437 | 0.468 | 0.460
blood_trans | 0.374 | 0.524 | 0.297 | 0.439 | 0.544 | 0.394
Breast cancer | 0.897 | 0.906 | 0.888 | 0.951 | 0.923 | 0.980
Credit g | 0.795 | 0.719 | 0.893 | 0.775 | 0.721 | 0.843
bioresponse | 0.352 | 0.638 | 0.374 | 0.741 | 0.745 | 0.737
ionosphere | 0.896 | 0.891 | 0.902 | 0.870 | 0.907 | 0.837
sonar | 0.734 | 0.728 | 0.744 | 0.775 | 0.718 | 0.844
christine | 0.610 | 0.609 | 0.619 | 0.637 | 0.644 | 0.630
hyperplane | 0.643 | 0.673 | 0.616 | 0.660 | 0.614 | 0.719
diabetes | 0.629 | 0.680 | 0.588 | 0.593 | 0.614 | 0.576
madelon | 0.640 | 0.635 | 0.646 | 0.665 | 0.652 | 0.679
guillermo | 0.437 | 0.615 | 0.369 | 0.397 | 0.536 | 0.342

##### Result Analysis

We recorded the average of 5 Monte Carlo experiments as the final result to
show in Table VI. Firstly, in most issues, GDR_GRGA outperforms GDR in
F-score, precision, and recall. Especially in the bioesponse problem, GDR_GRGA
has achieved much better performance than the original algorithm. The cases in
which GDR_GRGA may not be suitable for higher-order Markov models, resulting
in the performance of RGGR based on first-order Mar-kov processes is not good
enough. For the cases in which GDR_GRGA’s performance is not good enough,
maybe we need to extend RGGR through cosidering higher-order Markov chains.

##  V Conclusions

Inspired by the gene regulatory networks in biophysics, this paper has
proposed a Gene Regulatory Genetic Algorithm (GRGA) that models the
relationship between genes and uses it to guide crossover and mutation
operations, thereby improving the efficiency and effectiveness of GAs. We
demonstrated the effectiveness of GRGA and the role of RGGR through a test
function in CEC2013. GRGA further shows promising results in three
applications. In the feature selection task, the speed of convergence
increased 32.19% than the most advanced GA for this problem while maintaining
the accuracy. We increase average score by more than 0.5% on text summary
tasks. The effect is superior to state-of-the-art GA in over 66% of
dimensionality reduction tasks. We only consider the first-order Markov
relationship in this work, introducing higher-order Markov relationship could
further improve the performance of our approach, which will be explored in our
future work.

## Acknowledgments

This should be a simple paragraph before the References to thank those
individuals and institutions who have supported your work on this article.

## References

  * [1] J. Holland, “adaptation in natural and artificial systems, university of michigan press, ann arbor,”,” _Cité page_ , vol. 100, p. 33, 1975.
  * [2] R. W. Doran, “The gray code,” _Journal of Universal Computer Science_ , vol. 13, no. 11, pp. 1573–1597, 2007.
  * [3] I. Korejo, S. Yang, K. Brohi, and Z. Khuhro, “Multi-population methods with adaptive mutation for multi-modal optimization problems,” 2013.
  * [4] C. Reeves and J. E. Rowe, _Genetic algorithms: principles and perspectives: a guide to GA theory_. Springer Science & Business Media, 2002, vol. 20.
  * [5] C. Qian, Y. Yu, and Z.-H. Zhou, “An analysis on recombination in multi-objective evolutionary optimization,” in _Proceedings of the 13th annual conference on Genetic and evolutionary computation_ , 2011, pp. 2051–2058.
  * [6] T. D. Pham and W.-K. Hong, “Genetic algorithm using probabilistic-based natural selections and dynamic mutation ranges in optimizing precast beams,” _Computers & Structures_, vol. 258, p. 106681, 2022.
  * [7] F. Xie, Q. Sun, Y. Zhao, H. Du _et al._ , “An improved directed crossover genetic algorithm based on multilayer mutation,” _Journal of Control Science and Engineering_ , vol. 2022, 2022.
  * [8] T.-P. Hong, Y.-C. Lee, and M.-T. Wu, “An effective parallel approach for genetic-fuzzy data mining,” _Expert Systems with Applications_ , vol. 41, no. 2, pp. 655–662, 2014.
  * [9] M. Javidi and R. Hosseinpourfard, “Chaos genetic algorithm instead genetic algorithm.” _International Arab Journal of Information Technology (IAJIT)_ , vol. 12, no. 2, 2015.
  * [10] T. A. El-Mihoub, A. A. Hopgood, L. Nolle, and A. Battersby, “Hybrid genetic algorithms: A review.” _Eng. Lett._ , vol. 13, no. 2, pp. 124–137, 2006\.
  * [11] M. Srinivas and L. M. Patnaik, “Adaptive probabilities of crossover and mutation in genetic algorithms,” _IEEE Transactions on Systems, Man, and Cybernetics_ , 1994.
  * [12] M. Remm, C. E. Storm, and E. L. Sonnhammer, “Automatic clustering of orthologs and in-paralogs from pairwise species comparisons,” _Journal of molecular biology_ , vol. 314, no. 5, pp. 1041–1052, 2001.
  * [13] X. Lai, R. Blanc-Mathieu, L. GrandVuillemin, Y. Huang, A. Stigliani, J. Lucas, E. Thévenon, J. Loue-Manifel, L. Turchi, H. Daher _et al._ , “The leafy floral regulator displays pioneer transcription factor properties,” _Molecular Plant_ , vol. 14, no. 5, pp. 829–837, 2021.
  * [14] M. S. Islam and M. R. Islam, “A hybrid framework based on genetic algorithm and simulated annealing for rna structure prediction with pseudoknots,” _Journal of King Saud University-Computer and Information Sciences_ , vol. 34, no. 3, pp. 912–922, 2022.
  * [15] K. Yadav, B. Kumar, J. M. Guerrero, and A. Lashab, “A hybrid genetic algorithm and grey wolf optimizer technique for faster global peak detection in pv system under partial shading,” _Sustainable Computing: Informatics and Systems_ , vol. 35, p. 100770, 2022.
  * [16] W. Xu, Y. Hu, W. Luo, L. Wang, and R. Wu, “A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and tabu search considering operation outsourcing and carbon emission,” _Computers & Industrial Engineering_, vol. 157, p. 107318, 2021.
  * [17] Y. Xue, H. Zhu, J. Liang, and A. Słowik, “Adaptive crossover operator based multi-objective binary genetic algorithm for feature selection in classification,” _Knowledge-Based Systems_ , vol. 227, p. 107218, 2021.
  * [18] L. M. Hvattum, “Adjusting the order crossover operator for capacitated vehicle routing problems,” _Computers & Operations Research_, vol. 148, p. 105986, 2022.
  * [19] L. Manzoni, L. Mariot, and E. Tuba, “Balanced crossover operators in genetic algorithms,” _Swarm and Evolutionary Computation_ , vol. 54, p. 100646, 2020\.
  * [20] J.-H. Yi, S. Deb, J. Dong, A. H. Alavi, and G.-G. Wang, “An improved nsga-iii algorithm with adaptive mutation operator for big data optimization problems,” _Future Generation Computer Systems_ , vol. 88, pp. 571–585, 2018\.
  * [21] M. G. Altarabichi, S. Nowaczyk, S. Pashami, and P. S. Mashhadi, “Fast genetic algorithm for feature selection — a qualitative approximation approach,” _Expert Systems with Applications_ , vol. 211, p. 118528, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0957417422016049
  * [22] M. Mojrian and S. A. Mirroshandel, “A novel extractive multi-document text summarization system using quantum-inspired genetic algorithm: Mtsqiga,” _Expert systems with applications_ , vol. 171, p. 114555, 2021.
  * [23] N. Radeev, “Transparent dimension reduction by feature construction with genetic algorithm,” _Authorea Preprints_ , 2023.