# Linkage-Based Distance Metric in the Search Space of Genetic Algorithms

Authors: Yong-Hyuk Kim; Yourim Yoon
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We propose a new distance metric, based on the linkage of genes, in the search space of genetic algorithms. This second-order distance measure is derived from the gene interaction graph and first-order distance, which is a natural distance in chromosomal spaces. We show that the proposed measure forms a metric space and can be computed efficiently. As an example application, we demonstrate how this measure can be used to estimate the extent to which gene rearrangement improves the performance of genetic algorithms.


---

## Body

## 1. Introduction

Distance metrics are fundamental tools for organizing search spaces, because the introduction of a metric is the simplest way to induce a topology [1]. Different metrics produce different topologies and thus change the shape of the search space. When a space is to be searched by a genetic algorithm (GA), a good distance metric facilitates navigation of the space [2–5] and can also improve the effectiveness of search [6–12]. Hamming distance is a popular metric in a discrete space that is to be searched by a GA. Hamming distance has also been widely used in analyses of solution spaces [13–15].Fitness distance correlation (FDC), proposed by Jones and Forrest [14], is a measure of the effectiveness of a distance metric in a space to be searched by a GA. An FDC is obtained by measuring the correlation between fitness and the distance to the nearest global optimum for a number of sample solutions. FDC coefficients range from -
1 to 1, where higher values suggest increased difficulty in maximizing fitness and decreased difficulty in minimizing fitness. When a GA is hybridized with a local optimization, the population consists entirely of local optima, and it is then more useful to determine FDCs of local-optimum spaces.In this paper, we propose a new distance measure which takes account of gene interaction and show that it forms a metric space. We use this metric to compute FDCs of search space and show that FDCs obtained in this way have improved correlation with the improvement in GA performance that can be obtained by gene rearrangement. The remainder of this paper is organized as follows. In Section2, we review gene rearrangement in GAs. In Section 3, we propose a new distance measure for GAs, show that it forms a metric space, and demonstrate an application. Finally, we draw conclusions in Section 4.


## 2. Gene Rearrangement

Holland’s schema theorem [16] shows that schemata (i.e., groups of genes) with high fitness, short defining length, and low order have high probabilities of survival in a standard GA.These durable schemata are calledbuilding blocks. They make a major contribution to fitness and have a high degree of mutual interaction. The performance of a GA is strongly dependent on the survival and reproduction of these building blocks.The survival probability of a gene group through a crossover is strongly affected by the positions of genes in the chromosome. Schemata consisting of genes in scattered positions tend to be too long to survive. Thus, the strategy used for placing genes significantly affects the performance of a GA. Inversion is an operator which changes the location of genes while a GA is running [17], and the process of rearranging genes dynamically to improve performance is calledlinkage learning [18]. Messy GA [19] is an example of a technique that implicitly uses dynamic gene rearrangement.It has been observed that the performance of GAs on problems with a locus-based encoding can be improved by rearranging the indices of the genes before running the GA. Static gene rearrangement was first suggested by Bui and Moon [20, 21], who rearrange genes within a chromosomal representation to improve the quality of schemata and to help the GA to preserve the better schemata. Many studies on the static rearrangement of gene positions [20–24] have showed performance improvements. However, the improvement in performance achieved in this way has been shown to vary greatly between problem instances. This motivated us to develop a distance metric to improve our ability to estimate how much improvement in the performance of a GA on a particular problem instance can be expected through gene rearrangement.


## 3. A Linkage-Based Distance Measure

### 3.1. Second-Order Distance Measure

The most usual first-order distance measure in discrete space is the Hamming distance which is also a natural distance in chromosomal space, although there are other first-order distance measures, such as the quotient metric in redundant encoding [11]. We now define a second-order distance measure derived from first-order distance. Given a problem instance p, consider the unweighted undirected graph G
p representing first-order gene interaction [23], which is the pairwise interaction of genes. For convenience, we will assume that each gene has an interaction with itself, so that {
g
,
g
}
∈
E
(
G
p
) for each gene g
∈
V
(
G
p
). Let A
p be the adjacency matrix of G
p and consider A
p as a binary matrix over Z
2 [25–27].Definition 1.
Suppose that the inverse ofA
p exists as a binary matrix over Z
2; that is, A
p
∈
G
L
n
(
Z
2
). One defines the second-order distance measure d
p
(
2
) as follows:
(1)
d
p
(
2
)
(
x
,
y
)
:
=
A
p
-
1
(
x
⊕
y
)
,
where ⊕ is a vector summation operator, which performs a Boolean XOR (i.e., 0
+
0
=
0, 0
+
1
=
1, 1
+
0
=
1, and 1
+
1
=
0) in each coordinate, and · is a norm derived from the first-order distance metric d
(
1
) (i.e., ·
=
d
1
(
·
,
0
)).Theorem 2.
d
p
(
2
) is a metric.Proof.
It is enough to show the following four conditions [1].(i)
Nonnegativity: sinced
p
(
2
)
(
x
,
y
)
=
d
(
1
)
(
A
p
-
1
(
x
⊕
y
)
,
0
) and d
(
1
) is a metric, 0
≤
d
p
(
2
)
(
x
,
y
)
<
∞ for all x and y in X.
(ii)
Identity of indiscernibles: consider(2)
d
p
2
x
,
y
=
0
⟺
A
p
-
1
(
x
⊕
y
)
=
0
⟺
A
p
-
1
(
x
⊕
y
)
=
0
⟺
x
⊕
y
=
0
⟺
x
=
y
.
(iii)
Symmetry: consider(3)
d
p
2
x
,
y
=
A
p
-
1
(
x
⊕
y
)
=
A
p
-
1
y
⊕
x
=
d
p
(
2
)
(
y
,
x
)
.
(iv)
Triangle inequality: consider(4)
d
p
2
x
,
y
+
d
p
2
y
,
z
=
A
p
-
1
(
x
⊕
y
)
+
A
p
-
1
(
y
⊕
z
)
≥
A
p
-
1
(
x
⊕
y
)
⊕
A
p
-
1
(
y
⊕
z
)
=
A
p
-
1
(
(
x
⊕
y
)
⊕
(
y
⊕
z
)
)
=
A
p
-
1
(
(
x
⊕
z
)
⊕
(
y
⊕
y
)
)
=
A
p
-
1
x
⊕
z
=
d
p
(
2
)
(
x
,
z
)
.If the inverse ofA
p does not exist, we can extend the scope of the distance metric using the following well-defined formulation:
(5)
d
p
(
2
)
(
x
,
y
)
:
=
min
⁡
argmin
z
⁡
(
x
⊕
y
)
⊕
A
p
z
.
We note that if the inverse of A
p exists, then z
:
=
A
p
-
1
(
x
⊕
y
), which implies (
x
⊕
y
)
⊕
A
p
z
=
0, and hence argmi
n
z
(
x
⊕
y
)
⊕
A
p
z
=
A
p
-
1
(
x
⊕
y
). Our second-order distance and its extension can be computed in O
(
n
3
) by a variant of Gauss-Jordan elimination [28], where n is the number of genes.


### 3.2. An Application

Intuitively, our measure of the distance between two chromosomes can be understood as the minimum number of bits that must be changed to transform one chromosome into the other in the genetic process using optimal gene rearrangement.Given an undirected graphG
=
(
V
,
E
) with edge weights (
w
i
j
)
(
i
,
j
)
∈
E, the max-cut problem is that of finding a subset S
⊂
V which maximizes the sum of the edge weights which traverse the cut (
S
,
V
∖
S
) [29–31]. Consider the 6-node max-cut problem instance p, which is to maximize the following expression:
(6)
x
1
⊕
x
2
+
x
2
⊕
x
3
-
x
4
⊕
x
5
-
x
5
⊕
x
6
,
where a vertex v
i belongs to the position x
i
∈
{
0,1
} and ⊕ is the Boolean XOR operator. In this problem instance, edges {
v
1
,
v
2
} and {
v
2
,
v
3
} increase the fitness and edges {
v
4
,
v
5
} and {
v
5
,
v
6
} reduce the fitness. In the max-cut problem, we can consider that the given graph removing edge weights shows the first-order gene interaction (see, e.g., Figure 1(a)). Figure 1(b) shows an example in which the Hamming and second-order distances between two chromosomes x and y are obtained by optimal gene arrangement of the gene interaction graph G
p. In this example,
(7)
A
p
=
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
,
A
p
-
1
=
0
1
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
1
0
,
x
⊕
y
=
1
1
1
0
1
1
T, A
p
-
1
(
x
⊕
y
)
=
0
1
0
0
0
1
T, and hence A
p
-
1
(
x
⊕
y
)
=
2. If we use the normalized Hamming distance (developed for the 2-grouping problem) [32, 33] as the first-order distance measure, the FDC of this problem is -
0.50. But when our second-order distance is used, the FDC becomes -
0.95.Figure 1
(a) An example of a first-order gene interaction graphG
p and (b) distances between two example chromosomes x and y.
(a)
(b)Given a graphG
=
(
V
,
E
) and its adjacency matrix A
=
(
a
i
j
), the graph bipartitioning problem is that of minimizing the following expression:
(8)
1
2
∑
i
=
1
|
V
|
‍
∑
j
=
1
|
V
|
‍
a
i
j
(
x
i
⊕
x
j
)
+
γ
∑
i
=
1
|
V
|
‍
x
i
-
|
V
|
2
2
,
where a
i
j
∈
{
0,1
}, a vertex v
i belongs to the position x
i
∈
{
0,1
}, and γ is a positive constant introduced to penalize unbalanced partitions. If we ignore the second balancing term altogether, we can regard the given graph as the first-order gene interaction graph of the given problem instance. Bui and Moon [21] tried gene rearrangement in a GA for graph bipartitioning and obtained dramatic improvements in performance for some graphs. We hypothesized that FDCs calculated using our second-order distance would help identify graphs that could benefit most from gene rearrangement, in terms of GA performance. Figure 2 shows the relationship between FDC and the performance improvement of a GA on 16 benchmark graphs (8 random graphs and 8 random geometric graphs) that were used in [34–40].Figure 2
Correlation of gene rearrangement with FDC values computed using first- and second-order distance.
(a)
First-order distanced
(
1
)
(b)
Second-order distanced
p
(
2
)Here, the performance improvement means the difference in percentage between the average performances of a GA with and without gene rearrangement (data from [21]). The FDC values were approximated from 10,000 randomly generated local optima. When the first-order (normalized Hamming) distance was used, there was little correlation with the change in performance, but our second-order distance provided a clear correlation (see Figure 2(b) and Table 1).Table 1
Effect of gene rearrangement on FDCs computed using first- and second-order distance.
Graph
FDC withd
(
1
)
FDC withd
p
(
2
)
Improvement(
%
)
† from [21]
G500.2.5
0.369
0.033
3.495
G500.05
0.449
−0.002
−0.487
G500.10
0.221
0.005
2.674
G500.20
0.288
0.004
0.117
G1000.2.5
0.241
0.035
0.469
G1000.05
0.239
0.001
1.167
G1000.10
0.311
0.009
3.362
G1000.20
0.468
0.021
1.201
U500.05
0.297
0.438
82.258
U500.10
0.437
0.416
47.649
U500.20
0.593
0.267
65.198
U500.40
0.860
0.620
67.143
U1000.05
0.188
0.385
97.144
U1000.10
0.344
0.362
50.340
U1000.20
0.582
0.291
45.341
U1000.40
0.765
0.507
80.668
†Change in GA performance obtained by gene rearrangement.


## 3.1. Second-Order Distance Measure

The most usual first-order distance measure in discrete space is the Hamming distance which is also a natural distance in chromosomal space, although there are other first-order distance measures, such as the quotient metric in redundant encoding [11]. We now define a second-order distance measure derived from first-order distance. Given a problem instance p, consider the unweighted undirected graph G
p representing first-order gene interaction [23], which is the pairwise interaction of genes. For convenience, we will assume that each gene has an interaction with itself, so that {
g
,
g
}
∈
E
(
G
p
) for each gene g
∈
V
(
G
p
). Let A
p be the adjacency matrix of G
p and consider A
p as a binary matrix over Z
2 [25–27].Definition 1.
Suppose that the inverse ofA
p exists as a binary matrix over Z
2; that is, A
p
∈
G
L
n
(
Z
2
). One defines the second-order distance measure d
p
(
2
) as follows:
(1)
d
p
(
2
)
(
x
,
y
)
:
=
A
p
-
1
(
x
⊕
y
)
,
where ⊕ is a vector summation operator, which performs a Boolean XOR (i.e., 0
+
0
=
0, 0
+
1
=
1, 1
+
0
=
1, and 1
+
1
=
0) in each coordinate, and · is a norm derived from the first-order distance metric d
(
1
) (i.e., ·
=
d
1
(
·
,
0
)).Theorem 2.
d
p
(
2
) is a metric.Proof.
It is enough to show the following four conditions [1].(i)
Nonnegativity: sinced
p
(
2
)
(
x
,
y
)
=
d
(
1
)
(
A
p
-
1
(
x
⊕
y
)
,
0
) and d
(
1
) is a metric, 0
≤
d
p
(
2
)
(
x
,
y
)
<
∞ for all x and y in X.
(ii)
Identity of indiscernibles: consider(2)
d
p
2
x
,
y
=
0
⟺
A
p
-
1
(
x
⊕
y
)
=
0
⟺
A
p
-
1
(
x
⊕
y
)
=
0
⟺
x
⊕
y
=
0
⟺
x
=
y
.
(iii)
Symmetry: consider(3)
d
p
2
x
,
y
=
A
p
-
1
(
x
⊕
y
)
=
A
p
-
1
y
⊕
x
=
d
p
(
2
)
(
y
,
x
)
.
(iv)
Triangle inequality: consider(4)
d
p
2
x
,
y
+
d
p
2
y
,
z
=
A
p
-
1
(
x
⊕
y
)
+
A
p
-
1
(
y
⊕
z
)
≥
A
p
-
1
(
x
⊕
y
)
⊕
A
p
-
1
(
y
⊕
z
)
=
A
p
-
1
(
(
x
⊕
y
)
⊕
(
y
⊕
z
)
)
=
A
p
-
1
(
(
x
⊕
z
)
⊕
(
y
⊕
y
)
)
=
A
p
-
1
x
⊕
z
=
d
p
(
2
)
(
x
,
z
)
.If the inverse ofA
p does not exist, we can extend the scope of the distance metric using the following well-defined formulation:
(5)
d
p
(
2
)
(
x
,
y
)
:
=
min
⁡
argmin
z
⁡
(
x
⊕
y
)
⊕
A
p
z
.
We note that if the inverse of A
p exists, then z
:
=
A
p
-
1
(
x
⊕
y
), which implies (
x
⊕
y
)
⊕
A
p
z
=
0, and hence argmi
n
z
(
x
⊕
y
)
⊕
A
p
z
=
A
p
-
1
(
x
⊕
y
). Our second-order distance and its extension can be computed in O
(
n
3
) by a variant of Gauss-Jordan elimination [28], where n is the number of genes.


## 3.2. An Application

Intuitively, our measure of the distance between two chromosomes can be understood as the minimum number of bits that must be changed to transform one chromosome into the other in the genetic process using optimal gene rearrangement.Given an undirected graphG
=
(
V
,
E
) with edge weights (
w
i
j
)
(
i
,
j
)
∈
E, the max-cut problem is that of finding a subset S
⊂
V which maximizes the sum of the edge weights which traverse the cut (
S
,
V
∖
S
) [29–31]. Consider the 6-node max-cut problem instance p, which is to maximize the following expression:
(6)
x
1
⊕
x
2
+
x
2
⊕
x
3
-
x
4
⊕
x
5
-
x
5
⊕
x
6
,
where a vertex v
i belongs to the position x
i
∈
{
0,1
} and ⊕ is the Boolean XOR operator. In this problem instance, edges {
v
1
,
v
2
} and {
v
2
,
v
3
} increase the fitness and edges {
v
4
,
v
5
} and {
v
5
,
v
6
} reduce the fitness. In the max-cut problem, we can consider that the given graph removing edge weights shows the first-order gene interaction (see, e.g., Figure 1(a)). Figure 1(b) shows an example in which the Hamming and second-order distances between two chromosomes x and y are obtained by optimal gene arrangement of the gene interaction graph G
p. In this example,
(7)
A
p
=
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
,
A
p
-
1
=
0
1
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
1
0
,
x
⊕
y
=
1
1
1
0
1
1
T, A
p
-
1
(
x
⊕
y
)
=
0
1
0
0
0
1
T, and hence A
p
-
1
(
x
⊕
y
)
=
2. If we use the normalized Hamming distance (developed for the 2-grouping problem) [32, 33] as the first-order distance measure, the FDC of this problem is -
0.50. But when our second-order distance is used, the FDC becomes -
0.95.Figure 1
(a) An example of a first-order gene interaction graphG
p and (b) distances between two example chromosomes x and y.
(a)
(b)Given a graphG
=
(
V
,
E
) and its adjacency matrix A
=
(
a
i
j
), the graph bipartitioning problem is that of minimizing the following expression:
(8)
1
2
∑
i
=
1
|
V
|
‍
∑
j
=
1
|
V
|
‍
a
i
j
(
x
i
⊕
x
j
)
+
γ
∑
i
=
1
|
V
|
‍
x
i
-
|
V
|
2
2
,
where a
i
j
∈
{
0,1
}, a vertex v
i belongs to the position x
i
∈
{
0,1
}, and γ is a positive constant introduced to penalize unbalanced partitions. If we ignore the second balancing term altogether, we can regard the given graph as the first-order gene interaction graph of the given problem instance. Bui and Moon [21] tried gene rearrangement in a GA for graph bipartitioning and obtained dramatic improvements in performance for some graphs. We hypothesized that FDCs calculated using our second-order distance would help identify graphs that could benefit most from gene rearrangement, in terms of GA performance. Figure 2 shows the relationship between FDC and the performance improvement of a GA on 16 benchmark graphs (8 random graphs and 8 random geometric graphs) that were used in [34–40].Figure 2
Correlation of gene rearrangement with FDC values computed using first- and second-order distance.
(a)
First-order distanced
(
1
)
(b)
Second-order distanced
p
(
2
)Here, the performance improvement means the difference in percentage between the average performances of a GA with and without gene rearrangement (data from [21]). The FDC values were approximated from 10,000 randomly generated local optima. When the first-order (normalized Hamming) distance was used, there was little correlation with the change in performance, but our second-order distance provided a clear correlation (see Figure 2(b) and Table 1).Table 1
Effect of gene rearrangement on FDCs computed using first- and second-order distance.
Graph
FDC withd
(
1
)
FDC withd
p
(
2
)
Improvement(
%
)
† from [21]
G500.2.5
0.369
0.033
3.495
G500.05
0.449
−0.002
−0.487
G500.10
0.221
0.005
2.674
G500.20
0.288
0.004
0.117
G1000.2.5
0.241
0.035
0.469
G1000.05
0.239
0.001
1.167
G1000.10
0.311
0.009
3.362
G1000.20
0.468
0.021
1.201
U500.05
0.297
0.438
82.258
U500.10
0.437
0.416
47.649
U500.20
0.593
0.267
65.198
U500.40
0.860
0.620
67.143
U1000.05
0.188
0.385
97.144
U1000.10
0.344
0.362
50.340
U1000.20
0.582
0.291
45.341
U1000.40
0.765
0.507
80.668
†Change in GA performance obtained by gene rearrangement.


## 4. Concluding Remarks

In most previous work, distances among chromosomes in GAs have usually been first-order distances, and in particular Hamming distance. We have proposed a second-order distance measure for GAs, which we consider to be more meaningful. We have showed that this distance measure forms a metric space and that it can be computed efficiently.Using second-order distance allows us to see problem spaces from a different viewpoint. We have demonstrated its value in predicting the effectiveness of gene rearrangement, and we envisage it providing further understanding of the working mechanism of GAs.



---

*Source: 680624-2015-03-16.xml*