11institutetext: ITIS Software, University of Malaga, Spain
11email<EMAIL_ADDRESS>22institutetext: Colorado State University, USA
22email<EMAIL_ADDRESS>33institutetext: University of Stirling,
Scotland, UK
33email<EMAIL_ADDRESS>44institutetext: University of São Paulo,
Brazil
44email<EMAIL_ADDRESS>
# Generalizing and Unifying Gray-box Combinatorial Optimization Operators

Francisco Chicano 11 0000-0003-1259-2990 Darrell Whitley 22
0000-0002-2752-6534 Gabriela Ochoa 33 0000-0001-7649-5669 Renato Tinós 44
0000-0003-4027-8851

###### Abstract

Gray-box optimization leverages the information available about the
mathematical structure of an optimization problem to design efficient search
operators. Efficient hill climbers and crossover operators have been proposed
in the domain of pseudo-Boolean optimization and also in some permutation
problems. However, there is no general rule on how to design these efficient
operators in different representation domains. This paper proposes a general
framework that encompasses all known gray-box operators for combinatorial
optimization problems. The framework is general enough to shed light on the
design of new efficient operators for new problems and representation domains.
We also unify the proofs of efficiency for gray-box hill climbers and
crossovers and show that the mathematical property explaining the speed-up of
gray-box crossover operators, also explains the efficient identification of
improving moves in gray-box hill climbers. We illustrate the power of the new
framework by proposing an efficient hill climber and crossover for two related
permutation problems: the Linear Ordering Problem and the Single Machine Total
Weighted Tardiness Problem.

###### Keywords:

Gray-box optimization hill climbing partition crossover combinatorial
optimization group theory

##  1 Introduction

In the context of combinatorial optimization with metaheuristics, it is common
to assume that the algorithm does not know anything about the optimization
problem except the quality of the solutions. These values guide the search
towards better solutions. The objective function $f$ is a _black-box_ that
takes a solution $x$ and returns a real value $f(x)$ representing its cost (to
minimize) or quality (to maximize). For real-world applications, we often have
more information than just a black-box evaluation function. During the last 15
years, several proposals used this additional problem information to design
more effective variation operators. This is how operators like Partition
Crossover for the Traveling Salesman Problem (TSP) [17] or the constant time
hill climber for NK landscapes and MAX-$k$-SAT [15] appeared. This line of
research, known as _gray-box optimization_ [16], has produced very efficient
algorithms like DRILS [3] and PRILS [1], and very efficient ways to improve
existing algorithms [2]. Many so-called “black-box” optimization methods are
not black-box optimizers; every modern inexact MAX-SAT or TSP solver exploits
problem structure [6, 7, 8, 11].

In the gray-box optimization literature, we can find examples of hill climbers
that can identify improving moves in constant time and crossover operators
able to explore an exponential number of offspring in linear time. We prove in
this paper that the key ingredient behind the efficiency in both cases is the
same mathematical identity (decomposition theorem). We propose in Section 3 a
mathematical framework that unifies the math behind the efficient gray-box
crossovers and hill climbers. We also show that the results are general and
can be applied to any representation space. To illustrate how to use the
framework for designing new gray-box operators, we propose in Section 5 a new
hill climber and partition crossover based on the same mathematical identity
for the Linear Ordering Problem and the Single Machine Total Weighted
Tardiness, two NP-hard permutation problems.

The new framework allows us to revisit existing gray-box operators (see
Section 4) to find opportunities for improvement that were not obvious in the
original operator formulation. These opportunities appear after analyzing the
framework using the Fourier transform over finite groups. We include in
Section 2 a short introduction to the concepts of group, group representation,
and Fourier transform over finite groups to make the paper as self-contained
as possible.

##  2 Background

A _group_ is a pair $(G,\cdot)$, where $G$ is a set of elements and
$\cdot:G\times G\rightarrow G$ is a binary operator defined over the elements
of the group with the following properties:

  * •

Associative: $g_{1}\cdot(g_{2}\cdot g_{3})=(g_{1}\cdot g_{2})\cdot g_{3}$

  * •

Neutral element: there is an element $e\in G$ such that $e\cdot g=g\cdot e=g$
for all $g\in G$.

  * •

Inverse: for each $g\in G$ there is another element $g^{-1}$ such that $g\cdot
g^{-1}=g^{-1}\cdot g=e$.

Two examples of finite groups relevant in this paper are
$(\mathbb{Z}_{2}^{n},+)$, that is, binary strings with the bitwise exclusive
OR (XOR); and the symmetric group (permutations) $(S_{n},\circ)$ with the
composition operator. When the operation is clear from the context, we will
omit it and simply write $\mathbb{Z}_{2}^{n}$ or $S_{n}$. Observe that while
in the binary case, the operation (the sum) is commutative, in the permutation
case the composition is not commutative. A _group action_ of a group $G$ over
a set $X$ is a homomorphism of the group $G$ into a subgroup of the bijective
functions of $X$ to itself. That is, if $g\in G$, $x\in X$ and $gx\in X$
represents the action of $g$ applied to element $x$, then $(g\cdot h)x=g(hx)$.

###  2.1 Group representation

A _representation_ of a group $G$ is a mapping $\rho:G\rightarrow GL(V)$
between the elements of the group $G$ and the automorphisms of a vector space
$V$ such that $\rho(g_{1}\cdot g_{2})=\rho(g_{1})\circ\rho(g_{2})$. An
_automorphism_ is an invertible linear map from a vector space $V$ to itself.
Without loss of generality, we will assume in the following
$V=\mathbb{C}^{n}$, where the vectors are $n$-tuples of complex numbers and
the automorphisms are non-singular squared complex matrices of size $n\times
n$, that is, matrices with a nonzero determinant. A group representation
translates the group elements into matrices and the group operation into
matrix multiplication.

Not all group representations are equally important. Two representations,
$\rho_{1}$ and $\rho_{2}$ are _equivalent_ if there exists a matrix
$P\in\mathbb{C}^{n\times n}$ such that $\rho_{1}(g)=P\rho_{2}(g)P^{-1}$ for
all $g\in G$. Equivalent representations provide the same information; we will
be interested in a set of _inequivalent_ representations. A representation
$\rho$ is _reducible_ if we can write $\rho(g)$ as a block-diagonal matrix

$\rho(g)=\left(\begin{array}[]{c|c}\rho_{1}(g)&0\\\ \hline\cr
0&\rho_{2}(g)\end{array}\right),$ (1)

for all $g\in G$. Reducible representations do not provide more information
than their component representations and we will discard them, focusing on
_irreducible_ representations. When the group is finite there is also a finite
set of _inequivalent irreducible_ representations, called _irreps_ , and the
cardinality of this set is exactly the number of conjugacy classes of the
group [5]. When the group is commutative all the irreps are scalar values
(matrices of size $1\times 1$). This is the case in the group
$\mathbb{Z}_{2}^{n}$, the one we use for pseudo-Boolean optimization. The
irreps of $\mathbb{Z}_{2}^{n}$ are the Walsh functions [14]. However, when the
group is not commutative, some irreps need to be expressed with squared
matrices of size at least 2, as the next example shows.

###### Example 1

We will denote the permutations using the _cycle notation_. A cycle
$(c_{1}\;c_{2}\;\ldots\;c_{k})$ represents a permutation that maps $c_{1}$
into $c_{2}$, $c_{2}$ into $c_{3}$ and so on. Element $c_{k}$ is mapped into
$c_{1}$. The elements missing in the cycle are mapped into themselves. For
example, $(1\;2)$ denotes a permutation in which element 1 is mapped into
element 2 and element 2 is mapped into element 1. The identity permutation,
which maps every element to itself, is commonly denoted with $(1)$. Every
arbitrary permutation can be written as the product of disjoint cycles.

Let’s consider the group $S_{3}$ of permutations of three elements. A
representation $\rho$ for their elements is in Table 1.

Table 1: Example of representation of $S_{3}$ using $2\times 2$ matrices. This is the $\rho_{(2,1)}$ irreducible representation in the Young Orthogonal Representation. $\pi$ | (1) | (2 3) | (1 2) | (1 2 3) | (1 3 2) | (1 3)
---|---|---|---|---|---|---
$\rho(\pi)$ | $\left(\begin{array}[]{rr}1&0\\\ 0&1\end{array}\right)$ | $\left(\begin{array}[]{rr}-\frac{1}{2}&\frac{\sqrt{3}}{2}\\\ \frac{\sqrt{3}}{2}&\frac{1}{2}\end{array}\right)$ | $\left(\begin{array}[]{rr}1&0\\\ 0&-1\end{array}\right)$ | $\left(\begin{array}[]{rr}-\frac{1}{2}&-\frac{\sqrt{3}}{2}\\\ \frac{\sqrt{3}}{2}&-\frac{1}{2}\end{array}\right)$ | $\left(\begin{array}[]{rr}-\frac{1}{2}&\frac{\sqrt{3}}{2}\\\ -\frac{\sqrt{3}}{2}&-\frac{1}{2}\end{array}\right)$ | $\left(\begin{array}[]{rr}-\frac{1}{2}&-\frac{\sqrt{3}}{2}\\\ -\frac{\sqrt{3}}{2}&\frac{1}{2}\end{array}\right)$

∎

###  2.2 Fourier transform over finite groups

Let $f:G\rightarrow\mathbb{C}$ be a complex-valued function defined on group
$G$ and $\rho$ a representation of $G$. The _Fourier transform_ of $f$ at
$\rho$ is defined as

$\hat{f}(\rho)=\sum_{g\in G}f(g)\rho(g).$ (2)

Observe that $\hat{f}(\rho)$ is, in general, a matrix because $\rho(g)$ is a
matrix. In general, the Fourier transform of a function $f$ at a particular
representation does not provide all the information to reconstruct $f$, but
the Fourier transform at a set of irreps does. The inverse Fourier transform
is defined as

$f(g)=\frac{1}{|G|}\sum_{\rho\in\text{irreps}}d_{\rho}\text{Tr}\left(\hat{f}(\rho)\rho(g)^{-1}\right),$
(3)

where $d_{\rho}$ is the dimension of the vector space associated to
representation $\rho$, Tr is the trace of a matrix, and $\rho(g)^{-1}$ denotes
the inverse of $\rho(g)$.

##  3 The unifying framework

In this section, we present a mathematical framework that summarizes in one
single theorem the mathematical background behind some efficient hill climbers
and crossovers in gray-box optimization. In particular, the framework
generalizes the math behind Hamming Ball Hill Climber (HBHC) [4] and Partition
Crossover (PX) [12, 13, 17]. Explaining with a formula the math behind hill
climbers and crossovers yields a unification in gray-box combinatorial
optimization. Moreover, the formula does not assume a concrete representation,
but it is valid for any search space. This yields a generalization of all
gray-box results known up to date. The new framework should be able to open
the door to new efficient gray-box operators in combinatorial optimization
problems We illustrate this generalization by providing two new gray-box
operators in Section 5.

We assume that our search space is a finite set $X$. A _move_ in the solution
space is a function $h:X\rightarrow X$ that maps any solution $x\in X$ to
another solution $h(x)$ that is generated by that move.

###### Example 2

One example of a move is a bit flip in the binary representation. If
$1001\in\mathbb{Z}_{2}^{4}$ is a binary string representing a solution of an
optimization problem, we can flip the first bit to get $0001$. Here, the move
is represented by the function $h(x)=x+1000$ in $\mathbb{Z}_{2}^{4}$. ∎

###### Example 3

One example of a move in the permutation space is an exchange of two positions
in the permutation. The move $h(\sigma)=\sigma\cdot(3\;7)$ represents an
exchange of elements 3 and 7 (we use cycle notation), and the move
$h(\sigma)=(3\;7)\cdot\sigma$ represents an exchange of elements _at
positions_ 3 and 7. ∎

We now define the _delta function_ for a move $h$ and function
$f:X\rightarrow\mathbb{R}$ as

$\displaystyle\left(\Delta_{h}f\right)(x)=f(h(x))-f(x).$ (4)

We denote the composition of two moves $h_{1}$ and $h_{2}$ with $h_{2}\circ
h_{1}$ and we define it as $(h_{2}\circ h_{1})(x)=h_{2}(h_{1}(x))$. This is
equivalent to applying move $h_{1}$ first to $x$ and then applying move
$h_{2}$. Composition is not commutative in general, but we will focus on
commutative moves in this paper.

###### Definition 1

Let $h_{1},h_{2}:X\rightarrow X$ be two moves that commute under function
composition, that is, $h_{1}\circ h_{2}=h_{2}\circ h_{1}$. We say that the
moves are _non-interacting for the set of solutions $Y\subseteq X$_ when

$\left(\Delta_{h_{2}}f\right)(h_{1}(x))=\left(\Delta_{h_{2}}f\right)(x)\;\;\forall
x\in Y.$ (5)

If we omit the reference to the set $Y$, then the moves are non-interacting
for the whole search space $X$.

We can characterize the non-interaction using a different but equivalent
expression, which is more common in the literature.

###### Proposition 1

Let $h_{1},h_{2}:X\rightarrow X$ be two moves that commute, then the moves are
_non-interacting_ for set $Y\subseteq X$ if and only if

$\left(\Delta_{h_{1}\circ
h_{2}}f\right)(x)=\left(\Delta_{h_{1}}f\right)(x)+\left(\Delta_{h_{2}}f\right)(x)\;\;\forall
x\in Y.$ (6)

###### Proof

Let’s transform the equality (6) into the equality (5) using definitions and
algebraic manipulations:

$\displaystyle\left(\Delta_{h_{1}\circ h_{2}}f\right)(x)$
$\displaystyle=\left(\Delta_{h_{1}}f\right)(x)+\left(\Delta_{h_{2}}f\right)(x)$
$\displaystyle f(h_{1}(h_{2}(x)))-f(x)$
$\displaystyle=f(h_{1}(x))-f(x)+f(h_{2}(x))-f(x)\text{ (definition of
$\Delta$)}$ $\displaystyle f(h_{1}(h_{2}(x)))-f(h_{2}(x))$
$\displaystyle=f(h_{1}(x))-f(x)\text{ (reordering terms)}$
$\displaystyle\left(\Delta_{h_{1}}f\right)(h_{2}(x))$
$\displaystyle=\left(\Delta_{h_{1}}f\right)(x)\text{ (definition of
$\Delta$)}.$

∎

The efficiency and efficacy of the gray-box operators are based on the
separability of the delta function when we decompose a move. We prove here a
generalization of this separability that is valid for all representations.

######  Theorem 3.1 (Decomposition)

Let $h_{i}:X\rightarrow X$ with $1\leq i\leq m$ be a family of pairwise
commutative moves and the set $Y\subseteq X$. For each pair of moves $h_{i}$,
$h_{j}$ we also require that they are non-interacting in the sets $H(Y)$ for
all moves $H$ that are compositions of moves $h_{k}$ with $1\leq k\leq m$ that
do not include $h_{i}$ and $h_{j}$. $H$ can also be the identity function
(empty composition of moves). It holds

$\left(\Delta_{\bigcirc_{i=m}^{1}h_{i}}f\right)(x)=\sum_{i=1}^{m}\left(\Delta_{h_{i}}f\right)(x)\;\;\forall
x\in Y.$ (7)

###### Proof

We can prove Eq. (7) using induction over $m$. For $m=1$ the equality is
trivial because we have the same expression on both sides. Let’s assume that
the equality holds for $m$ and let’s prove it for $m+1$. We assume $x\in Y$
and write

$\displaystyle\left(\Delta_{\bigcirc_{i=m+1}^{1}h_{i}}f\right)(x)$
$\displaystyle=f((\bigcirc_{i=m+1}^{1}h_{i})(x))-f(x)$
$\displaystyle=f((\bigcirc_{i=m+1}^{1}h_{i})(x))-f((\bigcirc_{i=m}^{1}h_{i})(x))$
$\displaystyle\qquad+f((\bigcirc_{i=m}^{1}h_{i})(x))-f(x)$
$\displaystyle=(\Delta_{h_{m+1}}f)((\bigcirc_{i=m}^{1}h_{i})(x))+\left(\Delta_{\bigcirc_{i=m}^{1}h_{i}}f\right)(x).$

Since $h_{m+1}$ and all the $h_{i}$ are commutative and non-interacting in
$H(Y)$ for any composition $H$ of the other moves we can apply Eq. (5)
iteratively to get
$(\Delta_{h_{m+1}}f)((\bigcirc_{i=m}^{1}h_{i})(x))=(\Delta_{h_{m+1}}f)(x)$. If
we use the induction hypothesis we can write

$(\Delta_{h_{m+1}}f)((\bigcirc_{i=m}^{1}h_{i})(x))+\left(\Delta_{\bigcirc_{i=m}^{1}h_{i}}f\right)(x)=(\Delta_{h_{m+1}}f)(x)+\sum_{i=1}^{m}\left(\Delta_{h_{i}}f\right)(x),$

proving the result. ∎

######  Corollary 1 (Lattice linear equation)

Let $W\subseteq\\{1,2,\ldots,m\\}$ be a subset of indices for the moves
$h_{i}$. We denote with $H_{W}$ the move created after the composition of the
$h_{i}$ with $i\in W$, $H_{W}=\bigcirc_{i\in W}h_{i}$. Then,

$\left(\Delta_{H_{W}}f\right)(x)=\sum_{i\in
W}\left(\Delta_{h_{i}}f\right)(x)\;\;\forall x\in Y.$ (8)

###### Proof

It is a simple application of Theorem 3.1 to the moves $h_{i}$ with $i\in W$.

Let’s now focus on the moves that are bijections. These moves form a group,
the symmetric group (permutations) over set $X$, denoted here with
$\mathcal{S}_{X}$. This group naturally _acts_ on the search space $X$. That
is, we define the action of a bijective move $h$ over an element $x\in X$ as
$h(x)$. We will be interested in this paper in a subgroup $G$ of
$\mathcal{S}_{X}$ that is _transitive_ , that is, for any pair of elements
$x,y\in X$ we can find a move $g\in G$ such that $g(x)=y$. If we work with
such a group $G$, then we can fix one solution in the search space $x_{0}\in
X$ as a _base solution_ and define a group function
$f^{\prime}:G\rightarrow\mathbb{R}$ based on the objective function $f$ as
$f^{\prime}(g)=f(g(x_{0}))$. Since the group is transitive, any solution $x$
of the search space has at least one move $g$ such that $g(x_{0})=x$.
Optimizing $f^{\prime}$ is equivalent to optimizing $f$, and now the domain of
$f^{\prime}$ is a group. We can represent both, solutions and moves, with
elements of that group.

###### Example 4

In the context of pseudo-Boolean optimization, where the solutions are
elements of $\mathbb{Z}_{2}^{n}$ (binary strings), we can also use binary
strings to represent a move. The element $w\in\mathbb{Z}_{2}^{n}$ acts on
solution $x$ by moving it to $x+w$ (bitwise XOR). In the permutation space, a
move can also be a permutation $\sigma$ that acts on solution $\pi$ by left-
composition, $\sigma\circ\pi$, or right-composition, $\pi\circ\sigma$. ∎

Based on the decomposition theorem (Theorem 3.1) we can propose a method to
potentially develop an efficient hill climber and a general partition
crossover operator.

###  3.1 Efficient hill climber

The idea of the efficient hill climber (Algorithm 1) is to keep in memory the
values $(\Delta_{h}f)(x)$ for the current solution $x$ of a set of moves $h\in
N$. With a little abuse of notation, we will denote the vector of delta
values, also called _score vector_ , with $\Delta f$. Moves are classified
into two classes: improving and non-improving111Alternatively, it is possible
to use multiple classes based on the level of improvement.. Assuming
minimization, a move $h$ is improving if and only if $(\Delta_{h}f)(x)<0$. At
one iteration, the hill climber picks one of the improving moves $h$ and
updates the current solution by applying $h$ to $x$ (see Line 4 in Algorithm
1). It also updates the vector $(\Delta f)$ (Line 3).

1: while $(\Delta_{h}f)(x)<0$ for some $h\in N$ do

2: $h\leftarrow$ selectImprovingMove($\Delta f$);

3: updateDeltas($\Delta f$,$x$,$h$);

4: $x\leftarrow h(x)$;

5: end while

Algorithm 1 Efficient hill climber

The selection of an improving move can be done in constant time. In many
cases, the update of $\Delta f$ can also be done in constant time if the set
of moves $N$ is linear in the size of the problem. This makes it possible to
run one step of the hill climber in constant time. Now, we claim that there is
no need to keep in memory the value $(\Delta_{h_{2}\circ h_{1}}f)(x)$ if
$h_{1}$ and $h_{2}$ are commutative and non-interacting. For the move
$h_{2}\circ h_{1}$ to be improving, we need at least one of $h_{1}$ or $h_{2}$
to be an improving move. Certainly, if $(\Delta_{h_{2}\circ
h_{1}}f)(x)=(\Delta_{h_{1}}f)(x)+(\Delta_{h_{2}}f)(x)<0$ then the two values
$(\Delta_{h_{1}}f)(x)$ and $(\Delta_{h_{2}}f)(x)$ cannot be greater or equal
to zero at the same time. This result generalizes for any number of moves
$h_{i}$ that are commutative and non-interacting. That means that we can
explore a large neighborhood $N(x)$ around a solution by analyzing a much
smaller number of moves. The key point here is to find the set of moves needed
to explore the desired neighborhood. In the context of pseudo-Boolean
optimization, it has been proven that for $k$-bounded pseudo-Boolean functions
where each variable can only appear in a number of subfunctions, it is
possible to explore a ball of constant size $t$ storing only a linear number
of moves in memory [4].

###  3.2 Partition crossover

Corollary 1 also makes it possible to define a very effective crossover
operator, called partition crossover (PX). Let $x_{1},x_{2}\in X$ be two
solutions that are connected by a move $g$, that is, $g(x_{1})=x_{2}$.
Partition crossover is based on the decomposition of $\Delta_{g}f$ for
solution $x_{1}$. Let us write this decomposition as

$\left(\Delta_{g}f\right)(x_{1})=\sum_{i=1}^{q}\left(\Delta_{h_{i}}f\right)(x_{1}),$
(9)

then each $h_{i}$ is called a _component_ in partition crossover. For each
component, we decide if it is included or not in the offspring solution. We
can write this more explicitly evaluating the delta function in $x_{1}$:

$\left(\Delta_{g}f\right)(x_{1})=f(x_{2})-f(x_{1})=\sum_{i=1}^{q}\left(f(h_{i}(x_{1}))-f(x_{1}))\right).$
(10)

If $(\Delta_{h_{i}}f)(x_{1})<0$ then $h_{i}$ is used to form the offspring
solution, otherwise it is not included. We can now define the set $W$ of the
corollary as follows: $W=\\{i\,|\,1\leq i\leq
m,(\Delta_{h_{i}}f)(x_{1})<0\\}$. The offspring is the solution
$x^{*}=H_{W}(x_{1})$. According to Corollary 1, this procedure necessarily
finds the best solution from the set of $2^{m}$ solutions that can be
generated by applying or not each of the $m$ components.

###  3.3 The role of Fourier transforms

Let us consider the case in which the moves are bijections and we can ground
the objective function on a group $G$. We can use the Fourier transform of the
objective function to help identify non-interacting moves to apply Theorem
3.1.

###### Theorem 3.2

Let $G$ be a group, $f:G\rightarrow\mathbb{R}$ a function and $h_{1},h_{2}\in
G$ two moves that commute. Then, the moves are non-interacting if and only if:

$\left(\rho_{\lambda}(h_{1}^{-1})-I\right)\left(\rho_{\lambda}(h_{2}^{-1})-I\right)\hat{f}(\lambda)=0\;\;\;\forall\lambda\in\text{irreps},$
(11)

where $\rho_{\lambda}$ is a representation of $G$ labeled with $\lambda$ and
$\hat{f}(\lambda)$ is the Fourier transform of $f$ in that representation.

###### Proof

Let us apply Eq. (2) (Fourier transform) to $\Delta_{h}f$:

$\displaystyle\sum_{g\in G}\left(\Delta_{h}f\right)(g)\rho_{\lambda}(g)$
$\displaystyle=\sum_{g\in G}\left(f(h\cdot g)-f(g)\right)\rho_{\lambda}(g)$
$\displaystyle=\left(\sum_{g\in G}f(h\cdot
g)\rho_{\lambda}(g)\right)-\left(\sum_{g\in G}f(g)\rho_{\lambda}(g)\right)$
now using the change $g^{\prime}=h\cdot g$
$\displaystyle=\left(\sum_{g^{\prime}\in
G}f(g^{\prime})\rho_{\lambda}(h^{-1}\cdot g^{\prime})\right)-\left(\sum_{g\in
G}f(g)\rho_{\lambda}(g)\right)$ applying $\rho_{\lambda}(h^{-1}\cdot
g^{\prime})=\rho_{\lambda}(h^{-1})\rho_{\lambda}(g^{\prime})$
$\displaystyle=\rho_{\lambda}(h^{-1})\left(\sum_{g^{\prime}\in
G}f(g^{\prime})\rho_{\lambda}(g^{\prime})\right)-\left(\sum_{g\in
G}f(g)\rho_{\lambda}(g)\right)$
$\displaystyle=\rho_{\lambda}(h^{-1})\hat{f}(\lambda)-\hat{f}(\lambda)=\left(\rho_{\lambda}(h^{-1})-I\right)\hat{f}(\lambda).$
(12)

Let us now write Eq. (6) as

$\Delta_{h_{2}\cdot h_{1}}f-\Delta_{h_{2}}f-\Delta_{h_{1}}f=0.$

If we apply Eq. (12) to the previous expression we get for all irreps
$\lambda$

$\displaystyle 0$ $\displaystyle=\left[\rho_{\lambda}\left((h_{2}\cdot
h_{1})^{-1}\right)-I\right]\hat{f}(\lambda)-\left[\rho_{\lambda}(h_{2}^{-1})-I\right]\hat{f}(\lambda)-\left[\rho_{\lambda}(h_{1}^{-1})-I\right]\hat{f}(\lambda)$
$\displaystyle=\left[\rho_{\lambda}\left((h_{2}\cdot
h_{1})^{-1}\right)-I-\rho_{\lambda}(h_{2}^{-1})+I-\rho_{\lambda}(h_{1}^{-1})+I\right]\hat{f}(\lambda)$
$\displaystyle=\left[\rho_{\lambda}\left((h_{2}\cdot
h_{1})^{-1}\right)-\rho_{\lambda}(h_{2}^{-1})-\rho_{\lambda}(h_{1}^{-1})+I\right]\hat{f}(\lambda)$
$\displaystyle=\left[\rho(h_{1}^{-1})\rho(h_{2}^{-1})-\rho_{\lambda}(h_{2}^{-1})-\rho_{\lambda}(h_{1}^{-1})+I\right]\hat{f}(\lambda)$
$\displaystyle=\left(\rho_{\lambda}(h_{1}^{-1})-I\right)\left(\rho_{\lambda}(h_{2}^{-1})-I\right)\hat{f}(\lambda).$

∎

Observe that $\rho_{\lambda}$ is, in general, a matrix, as well as
$\hat{f}(\lambda)$. Having the Fourier transform of $f$ it is possible to find
pairs of commutative moves $h_{1}$ and $h_{2}$ that are non-interacting and
can be used to produce a hill climber or partition crossover tailored to the
particular instance of the problem.

###### Example 5

Since $\mathbb{Z}_{2}^{n}$ is commutative, each solution is a conjugacy class
and the irreps are scalar functions labeled with the elements of
$\mathbb{Z}_{2}^{n}$: the well-known Walsh functions, defined as
$\varphi_{\lambda}(x)=\prod_{i=1}^{n}(-1)^{\lambda_{i}x_{i}}$, which take
values $1$ and $-1$. The moves $h_{1}$ and $h_{2}$ are also elements of
$\mathbb{Z}_{2}^{n}$ (binary strings). We have for this case $h^{-1}=h$ (each
element is its own inverse element) and
$\rho_{\lambda}(x^{-1})=\rho_{\lambda}(x)=\varphi_{\lambda}(x)$. In this
context, Eq. (11) is satisfied, and two moves $h_{1}$ and $h_{2}$ are non-
interacting if for all $\lambda$ for which there is a nonzero Walsh
coefficient in the Fourier transform of $f$, $\hat{f}(\lambda)\neq 0$, we have
that either $\varphi_{\lambda}(h_{1})=1$ or $\varphi_{\lambda}(h_{2})=1$. ∎

##  4 Previous gray-box operators

In this section, we will prove that some gray-box operators previously
published in the literature fit in the framework. In the binary case, the new
framework provides new opportunities to improve the operators.

###  4.1 Partition crossover in the TSP

Let us focus on the Generalized Asymmetric Partition Crossover (GAPX) by Tinós
et al. [13], which was defined for the asymmetric TSP. The basic move we will
need in this case is an _insertion_. We will denote with $h_{i,j}$ with $i\neq
j$ the insertion of city $i$ before city $j$ in the solution.

###### Example 6

In Figure 1 we can see that city $2$ is removed from its position and placed
before city $20$ when we move from Solution 1 to Solution 2. We represent that
move with $h_{2,20}$. Two insertion moves $h_{i,j}$ and
$h_{i^{\prime},j^{\prime}}$ are commutative if the sets $\\{i,j\\}$ and
$\\{i^{\prime},j^{\prime}\\}$ are disjoint. That is, if they “involve” four
different cities. ∎

Let’s follow the working principles of GAPX using the example in Figure 1.
GAPX creates a combined graph with all the arcs of the two parent solutions.
Next, it removes the arcs that are common to both parents (gray in the
figure). Then, it finds the connected components in the graph. In one
connected component, there are entry nodes and exit nodes. The arcs in the
component connect each entry node to one exit node. If the entry-to-exit
connections are the same in both parent solutions, then the decision of which
parent to use for the arcs of that component can be taken independently of the
other components.

Figure 1: Two parent solutions of GAPX in TSP.

###### Example 7

In Figure 1, there are three components and the arcs in the different
components are given different colors (red, blue and green). The entry nodes
of the red component are 10 and 16. The exit nodes of the red component are 12
and 18. Observe that in both parents, 10 is connected to 12 in the component
and 16 is connected to 18. Thus, in Solution 1 we could replace the arcs in
red with the arcs in red in Solution 2 and we still have a valid solution
(potential offspring). We can do this by applying insertion moves $h_{17,12}$
and $h_{11,18}$. These two moves commute but they are _interacting_. We can
easily see this in Table 2, where the arcs $(16,11)$ and $(10,17)$ are only
added by move $h_{17,12}\cdot h_{11,18}$. ∎

For two insertion moves to be non-interacting in a solution they must involve
cities which are _not_ adjacent. In general, the moves that transform the
paths in one component of Solution 1 to the paths in the same component of
Solution 2 are non-interacting for Solution 1, even if we also apply the moves
that transform the other components. Thus, Corollary 1 is applicable.

###### Example 8

Moves $h_{17,12}$, $h_{11,18}$, and $h_{17,12}\cdot h_{11,18}$ are non-
interacting with move $h_{2,20}$, which transforms the blue component from
Solution 1 to Solution 2. ∎

Table 2: Arcs added and removed after applying different moves to Solution 1. Moves |  | Removed arcs |  | Added arcs
---|---|---|---|---
$h_{11,18}$ |  |  $(10,11)$, $(11,12)$, $(17,18)$ |  |  $(10,12)$, $(17,11)$, $(11,18)$
$h_{17,12}$ |  |  $(16,17)$, $(17,18)$, $(11,12)$ |  |  $(11,17)$, $(17,12)$, $(16,18)$
$h_{17,12}\cdot h_{11,18}$ |  |  $(16,17)$, $(17,18)$, $(10,11)$, $(11,12)$ |  |  $(16,11)$, $(11,18)$, $(10,17)$, $(17,12)$

The previous argument shows that the way in which GAPX works produces a set of
moves that are pairwise non-interacting. Thus, if GAPX finds $q$ components in
this way, Corollary 1 can be applied and the best of $2^{q}$ potential
offspring is computed.

###### Example 9

In Figure 1, the pairwise non-interacting moves are $h_{17,12}\cdot h_{11,18}$
(red component), $h_{2,20}$ (blue component), and $h_{14,15}$ (green
component). ∎

###  4.2 Gray-box optimization in pseudo-Boolean functions

In the context of pseudo-Boolean optimization, we can represent solutions and
moves with elements of $\mathbb{Z}_{2}^{n}$, which form a commutative group
under addition. The gray-box operators defined in the literature are based on
the concept of Variable Interaction Graph (VIG). A VIG is an undirected graph
where the set of nodes is the set of Boolean variables and there is an edge
between two variables when they interact. Using the language of our framework,
the nodes of the graph are the moves of size one (bit flip) and the edges
represent interactions among those moves. Let us define
$ones(g)=\\{i\,|\,g_{i}=1,\text{for }1\leq i\leq n\\}$. In terms of the
Fourier (Walsh) transform, there is an interaction among two order-1 moves
$g,h\in\mathbb{Z}_{2}^{n}$ when there is a nonzero Walsh coefficient
$\hat{f}(\lambda)$ with $ones(\lambda)\cap ones(g)\neq\emptyset$ and
$ones(\lambda)\cap ones(h)\neq\emptyset$. This means that the $\lambda$ vector
is 1 in the positions where moves $g$ and $h$ are 1. For higher-order moves
$g,h\in\mathbb{Z}_{2}^{n}$, previous work says that they are non-interacting
when the subgraphs induced by the moves in the VIG are not adjacent. That is,
two moves $g,h\in\mathbb{Z}_{2}^{n}$ are non-interacting if for all
$\lambda\in\mathbb{Z}_{2}^{n}$ at least one of the following three conditions
is true: 1) $\hat{f}(\lambda)=0$, 2) $ones(\lambda)\cap ones(g)=\emptyset$, or
3) $ones(\lambda)\cap ones(h)=\emptyset$. If we denote with $\lambda g$ the
dot product of $\lambda$ and $g$ in $(\mathbb{Z}_{2}^{n},+,\cdot)$, we can
observe that $\lambda g=0$ when $ones(\lambda)\cap ones(g)=\emptyset$; and,
thus, if one of the three previous conditions is true for all $\lambda$, then
Eq. (11) is satisfied. As a consequence, moves $h$ and $g$ are non-
interacting, and all the previous results on gray-box operators for pseudo-
Boolean optimization (including hill climbers and partition crossover) are
explained in the context of our new mathematical framework.

But our framework has more to say. There are cases in which $ones(\lambda)\cap
ones(g)\neq\emptyset$ and still $\lambda g=0$. In particular, this happens
exactly when $|ones(\lambda)\cap ones(g)|$ is even, because the sum in the dot
product is the sum in $\mathbb{Z}_{2}$.

###### Example 10

Let us assume that we have a function $f$ that depends on three variables:
$x_{1}$, $x_{2}$ and $x_{3}$, and let us assume that the Walsh transform
provides nonzero values for $\hat{f}(100)=w_{1}$, $\hat{f}(010)=w_{2}$ and
$\hat{f}(001)=w_{3}$, $\hat{f}(110)=w_{1,2}$ and $\hat{f}(111)=w_{1,2,3}$. Now
we wonder if we can decompose move $h=111$ (all bits changing). A
decomposition based on the VIG would not decompose this move. Thus, a Hamming
Ball Hill Climber [4] with radius 3 would need to store the score for move
$111$ and a partition crossover would only find one component if the two
parents differ in the three bits. This is due to the nonzero value for
$\hat{f}(111)$. However, a detailed analysis based on the Fourier (Walsh)
transform reveals that this move can be decomposed into two moves, $h_{1}=110$
and $h_{2}=001$, as if $w_{1,2,3}$ were zero. The reason is that for move
$h_{1}=110$ we have $\varphi_{111}(h_{1})=(-1)^{111\cdot 110}=1$,
$\varphi_{110}(h_{1})=1$ and $\varphi_{001}(h_{1})=1$; and for move
$h_{2}=001$ we have $\varphi_{100}=1$ and $\varphi_{010}=1$. These are the
only nonzero Walsh coefficients and Eq. (11) is satisfied.

We can interpret this decomposition in another way. According to the inverse
Fourier transform, Eq. (3), we can write $f$ in terms of the Fourier
coefficients as

$\displaystyle f(x)=\frac{1}{8}$
$\displaystyle\left(w_{1}\varphi_{100}(x)+w_{2}\varphi_{010}(x)+w_{3}\varphi_{001}(x)+w_{1,2}\varphi_{110}(x)+w_{1,2,3}\varphi_{111}(x)\right).$

Move $h_{1}=110$ will only affect the coefficients $w_{1}$ and $w_{2}$ in the
Fourier transform (it changes sign of $\varphi_{100}(x)$ and
$\varphi_{010}(x)$), while move $h_{2}=001$ will only affect the coefficients
$w_{1,2,3}$ and $w_{3}$. Since the coefficients affected by the moves are
different, then there is no interaction between the moves.

However, this decomposition does not mean we can ignore the Fourier
coefficient $w_{1,2,3}$ for all possible purposes. For example, let us assume
the input for partition crossover are the two solutions $x_{1}=011$ and
$x_{2}=000$. The move $011$ cannot be decomposed in $001$ and $010$ because
these moves both affect the sign of $w_{1,2,3}$. Thus, the decomposition
opportunities depend on the concrete parent solutions. Partition crossover can
find the decomposition opportunities dynamically or we can also statically
pre-compute some opportunities depending on the values of some particular
variables to speed up the process. ∎

##  5 New gray-box operators from the unifying framework

We finish this work by illustrating how the new mathematical framework for
gray-box optimization opens the door to the design of new gray-box operators.
In particular, we focus on two NP-hard permutation problems: the Linear
Ordering Problem (LOP) [10] and Single Machine Total Weighted Tardiness
Problem (SMTWTP) [9]. For LOP the goal is to reorder the columns and rows of a
matrix to minimize the sum of the upper diagonal. The objective function is

$f_{\rm LOP}(\sigma)=\sum_{i=1}^{n}\sum_{j=i+1}^{n}A_{\sigma(i),\sigma(j)},$
(13)

where $A$ is a $n\times n$ real matrix. In SMTWTP the goal is to find an order
for $n$ jobs minimizing the weighted tardiness. The objective function is

$f_{\rm SMTWTP}(\sigma)=\sum_{i=1}^{n}w_{\sigma(i)}\cdot T_{\sigma(i)},$ (14)

where $w_{j}$ and $T_{j}$ is the weight and tardiness of the $j$-th job,
respectively. Each job $j$ also has a due time $d_{j}$ and a processing time
$t_{j}$. The tardiness for job $j$ is $T_{j}=\max\\{0,C_{j}-d_{j}\\}$, where
$C_{j}=\sum_{i=1}^{\sigma^{-1}(j)}t_{\sigma(i)}$ is the completion time for
job $j$, which is the sum of the processing time of job $j$ and the preceding
jobs.

It is easy to see that in both problems re-arranging sets of consecutive
elements in the permutation does not affect the contributions to the fitness
function of the elements below or above the set. Given a solution $\sigma$ for
LOP, if we apply a move that arbitrarily permutes the elements in positions
$i$ to $j$, the term $A_{\sigma(l),\sigma(k)}$ for $i\leq l\leq j$ and $k>j$
will still be part of the value of the objective function for the perturbed
solution. The same happens for the terms $A_{\sigma(k),\sigma(l)}$ with $i\leq
l\leq j$ and $k<i$. In SMTWTP, it is also easy to see that the tardiness of
jobs in positions above $j$ or below $i$ is not affected by an arbitrary
permutation of the elements between positions $i$ and $j$ and, thus, their
contribution to the weighted tardiness (objective function) is unaffected.

This property allows us to confirm that Eq. (7) is fulfilled when $h_{1}$ and
$h_{2}$ are permutations affecting disjoint consecutive elements. More
precisely, if $e(h_{1})$ is the set of elements in the permutation changed by
$h_{1}$ and $e(h_{2})$ is the set of elements changed by $h_{2}$, then we
should have
$[\min(e(h_{1})),\max(e(h_{1}))]\cap[\min(e(h_{2})),\max(e(h_{2}))]=\emptyset$
for Eq. (7) to be true in LOP and SMTWTP.

Based on this decomposition, we can immediately design an efficient hill
climber and a partition crossover. Regarding the hill climber, we only need to
store the values $\Delta_{h}f$ for moves $h$ that permute adjacent elements in
the permutation.

###### Example 11

We could consider the case in which $h$ are swaps (exchange of adjacent
positions). There are $n-1$ possible swaps in a permutation. We could also
consider the case of any arbitrary permutation for three consecutive elements.
There are $n-2$ sets of three consecutive elements and five non-trivial
permutations of three elements, so we have $5(n-2)$ values to store. ∎

In general, this approach will require $O(n)$ memory. If a move is taken
during the hill climbing, then updating the $\Delta_{h}f$ values has to be
done only for _overlapping_ moves, which are a constant number, and can be
done in constant time.

Regarding the construction of a partition crossover operator, given two parent
solutions $\sigma_{1}$ and $\sigma_{2}$, the idea is to compute the
decomposition for $\sigma_{2}\cdot\sigma_{1}^{-1}$. We can find a
decomposition by finding permutations of consecutive elements in
$\sigma_{2}\cdot\sigma_{1}^{-1}$. The pseudo-code for this is in Algorithm 2.

Algorithm 2 Partition crossover for LOP/SMTWTP

1: $\sigma_{*}\leftarrow\sigma_{1}$

2: $i\leftarrow 1$

3: while $i\leq n$ do

4: $h\leftarrow(1)$ // Initialize with identity permutation

5: $l\leftarrow i$

6: $h(l)\leftarrow\sigma_{2}(\sigma_{1}^{-1}(l))$

7: $j\leftarrow h(l)$

8: while $l<j$ do

9: $l\leftarrow l+1$

10: $h(l)\leftarrow\sigma_{2}(\sigma_{1}^{-1}(l))$

11: $j\leftarrow\max(j,h(l))$

12: end while // Component $h$ found between positions $i$ and $j$

13: if $\left(\Delta_{h}f\right)(\sigma_{1})<0$ then

14: $\sigma_{*}\leftarrow h(\sigma_{*})$

15: end if

16: $i\leftarrow i+1$

17: end while

18: return $\sigma_{*}$

The operators here defined for LOP and SMTWTP can also be applied with a
slight variation to the TSP. First, we need to consider that the TSP has a
rotational symmetry and, thus, we need to consider that element $n$ is
adjacent to element $1$. And second, in TSP if $h_{1}$ touches element $i$ and
$h_{2}$ touches element $i+1$, then $h_{1}$ and $h_{2}$ will interact (they
both affect edge $(\sigma(i),\sigma(i+1))$). Thus, we need to ensure that this
does not happen. It is not enough that $e(h_{1})\cap e(h_{2})=\emptyset$, we
also need that no element in $e(h_{1})$ is adjacent to an element in
$e(h_{2})$.

##  6 Conclusions

This paper proposes a mathematical framework that unifies two gray-box
operators defined in the literature: Hamming Ball Hill Climber (HBHC) and
Partition Crossover (PX). The framework also generalizes the results in the
literature and provides a mathematical background to define particular
versions of these operators in search spaces different from the ones used in
the past, which are permutations and binary strings. With the help of the
Fourier transform over finite groups we can identify opportunities to design
more effective operators.

This paper opens a new research line in gray-box optimization, allowing faster
development of new gray-box operators and a new re-design of the old ones to
make them more effective. There are some open questions that can be explored
in future work, like the extension of the framework to sets of non-commutative
moves or the research for the most appropriate representation of a problem to
get profit from the efficient gray-box operators. In practice, it would be
interesting to re-design the operators HBHC and PX for pseudo-Boolean
optimization taking into account the new opportunities for decomposition
revealed by Theorem 3.2. New gray-box operators can be designed for
combinatorial optimization problems for which it was not clear how to apply
the existing gray-box operators.

####  6.0.1 Acknowledgements

This research is partially funded by project PID 2020-116727RB-I00 (HUmove)
funded by MCIN/AEI/ 10.13039/501100011033; TAILOR ICT-48 Network (No 952215)
funded by EU Horizon 2020 research and innovation programme; Junta de
Andalucia, Spain, under contract QUAL21 010UMA; and the University of Malaga
(PAR 4/2023). This work is also partially funded by a National Science
Foundation (NSF) grant to D. Whitley, Award Number: 1908866.

####  6.0.2

The authors have no competing interests to declare that are relevant to the
content of this article.

## References

  * [1] Canonne, L., Derbel, B., Chicano, F., Ochoa, G.: To combine or not to combine graybox crossover and local search? In: Silva, S., Paquete, L. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, Lisbon, Portugal, July 15-19, 2023. pp. 257–265. ACM (2023). https://doi.org/10.1145/3583131.3590466
  * [2] Chen, W., Whitley, L.D., Tinós, R., Chicano, F.: Tunneling between plateaus: improving on a state-of-the-art MAXSAT solver using partition crossover. In: Aguirre, H.E., Takadama, K. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, July 15-19, 2018. pp. 921–928. ACM (2018). https://doi.org/10.1145/3205455.3205482
  * [3] Chicano, F., Whitley, L.D., Ochoa, G., Tinós, R.: Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search. In: Bosman, P.A.N. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15-19, 2017. pp. 753–760. ACM (2017). https://doi.org/10.1145/3071178.3071285
  * [4] Chicano, F., Whitley, L.D., Sutton, A.M.: Efficient identification of improving moves in a ball for pseudo-boolean problems. In: Arnold, D.V. (ed.) Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, Canada, July 12-16, 2014. pp. 437–444. ACM (2014). https://doi.org/10.1145/2576768.2598304
  * [5] Fulton, W., Harris, J.: Representation theory. A first course. Springer (2004)
  * [6] Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research 126(1), 106–130 (2000)
  * [7] Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufman (2004)
  * [8] Hoos, H.H., Smyth, K., Stützle, T.: Search space features underlying the performance of stochastic local search algorithms for MAX-SAT. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN 8). pp. 51–60. Springer, Birmingham, UK (September 2004)
  * [9] Lenstra, J., Rinnooy Kan, A., Brucker, P.: Complexity of machine scheduling problems. In: Hammer, P., Johnson, E., Korte, B., Nemhauser, G. (eds.) Studies in Integer Programming, Annals of Discrete Mathematics, vol. 1, pp. 343–362. Elsevier (1977). https://doi.org/https://doi.org/10.1016/S0167-5060(08)70743-X
  * [10] Martí, R., Reinelt, G.: The Linear Ordering Problem. Exact and Heuristic Methods in Combinatorial Optimization, vol. 175. Springer Berlin Heidelberg (2011). https://doi.org/10.1007/978-3-642-16729-4
  * [11] Nagata, Y., Kobayashi, S.: A Powerful Genetic Algorithms Using Edge Assemble Crossover the Traveling Salesman Problem. INFORMS Journal on Computing 25(2), 346–363 (2013)
  * [12] Tinós, R., Whitley, L.D., Chicano, F.: Partition crossover for pseudo-Boolean optimization. In: He, J., Jansen, T., Ochoa, G., Zarges, C. (eds.) Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17 - 20, 2015. pp. 137–149. ACM (2015). https://doi.org/10.1145/2725494.2725497
  * [13] Tinós, R., Whitley, L.D., Ochoa, G.: Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP. In: Arnold, D.V. (ed.) Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, Canada, July 12-16, 2014. pp. 501–508. ACM (2014). https://doi.org/10.1145/2576768.2598245
  * [14] Walsh, J.L.: A closed set of normal orthogonal functions. American Journal of Mathematics 45(1), 5 (1923)
  * [15] Whitley, L.D., Chen, W.: Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In: Soule, T., Moore, J.H. (eds.) Genetic and Evolutionary Computation Conference, GECCO 2012, Philadelphia, PA, USA, July 7-11, 2012. pp. 1357–1364. ACM (2012). https://doi.org/10.1145/2330163.2330351
  * [16] Whitley, L.D., Chicano, F., Goldman, B.W.: Gray box optimization for Mk landscapes (NK landscapes and MAX-kSAT). Evol. Comput. 24(3), 491–519 (2016). https://doi.org/10.1162/EVCO_A_00184
  * [17] Whitley, L.D., Hains, D., Howe, A.E.: Tunneling between optima: partition crossover for the traveling salesman problem. In: Rothlauf, F. (ed.) Genetic and Evolutionary Computation Conference, GECCO 2009, Proceedings, Montreal, Québec, Canada, July 8-12, 2009. pp. 915–922. ACM (2009). https://doi.org/10.1145/1569901.1570026