IEEE Computational Intelligence Magazine - November 2021 - 87

fitness of the genome is a sum of all separate
fitness values of each gene, normalized
by N.
To examine the evolutionary dynamics
and properties of the NK model, we
use a mutation-based hill-climbing algorithm
(in accordance with [23]). There,
the single point in the fitness space represents
a converged species, i.e., the size
of the population is one and it evolves
by randomly changing one randomly
chosen gene per generation. If the fitness
of the mutated " population "
increases, it keeps the new genetic configuration.
If the fitness is equal, the
selection is made at random. All results
presented in this paper, acquired with
the NK model, are averaged over 10
runs (random start points) on each of 10
randomly produced NK functions
for every one combination of the given
parameters (N and K), i.e., 100 runs, for
20,000 generations. Here six values are
chosen from
01K ,5## for N = 20
and N = 100.
Some results of running the standard
NK model with different parameters to
demonstrate the characteristic behavior
of evolution depending upon the ruggedness
of the fitness landscape are presented
in Fig. 2. When K = 0 all gene
fitness contributions are independent
and randomly chosen within a range of
[0,1]. As a result, based on order statistics,
the average fitness is equal to 0.66.
For small values of K (up to K = 8),
regardless of N, the ruggedness of the
landscape increases, as does the height
of the better optima found. For values
of K higher than 8, the increasing
entanglement of gene dependencies
that define their fitness contributions
causes an increasing number of low fitness
local optima. Note that for high K
values relative to N, the central limit
theorem indicates that optima will average
around 0.5. The decrease in the
finally found fitness when K tends
towards N is an incident known as the
" complexity catastrophe " . The fittest
individuals found for tests with K > 6
and N = 20 (as depicted in Fig. 2) are
statistically significantly lower from
those with N = 100, when tested under
T-test (p < 0.05).
III Genome Growth in
the NK Model
In order to investigate the behavior of
variable-length genomes throughout
evolution under the abstract NK model,
the mutation operator is extended. In
addition to varying an arbitrarily picked
gene, the operator can now also add a
random number (G) of new arbitrarily
generated genes to the rightmost part
of the available genome NN G=+l^h
(for more details refer to the Supplementary
Material). Since it is generally
assumed that this new functionality
assigns new dependencies on the fitness
contributions, the first connection
of a randomly determined gene of the
pre-existing ones is assigned to the
newly added ones (for K 1$ ). In addition,
the newly added genes obtain K
dependencies throughout the entire
genome for their fitness contribution.
Thus, the extension to the genome has
a two-way influence on the fitness of
an individual.
As an initial trial, we investigate the
case of G = 1, shown in Fig. 3. In the
same fashion as before, the parameter N
is set to two values, N = 20 and N =
100. In the first case, with the initial
parameter N = 20 and for values of K >
10, the resulting fitness (Fig. 3(a)) is
enhanced compared with the static
genome length (Fig. 2), with the difference
statistically significant (T-test, p <
0.05). Here, the genome length increases
by approximately three genes (or up to
N 23=l
as depicted in Fig. 3(b)). As a
result, the occurrence of the complexity
catastrophe is no longer evident, at least
for the K values explored. The final
achieved genome lengths depicted in
Fig. 3(b) outline a high discrepancy
between maximum and minimum values;
however, for lower values of K (i.e.,
K < 4), the final genome lengths are
marginally smaller. Whereas, in all cases
with N = 100, the final fitness (Fig. 3(c))
is not statistically significantly different
(T-test,
p 005$ ) from the standard case
.
without genome growth. Nonetheless,
the amount of added genes (Fig. 3(d)) is
substantial, even double the amount
that is observed with N = 20 (Fig. 3(b))
and K > 4.
As the ruggedness of the fitness
landscape increases, the number of local
optima increases and their typical
height decreases. Hence, the increase of
ruggedness provides a larger window
for arbitrarily generated and added
genes to make a positive fitness contribution.
On the contrary, on landscapes
with lower ruggedness, high fitness
optima can be expected to be located
during the early stages of the search,
reducing the window of opportunity
for added genes to make a positive fitness
contribution. This is depicted in
Fig. 4, which shows the generations
(y-axis) needed for the search methodology
to converge to a peak for different
K parameters, with G = 0 (no
genome growth) and G = 1 (genome
growth with one gene per step). The
generation at which the genome
growth stops is also indicated. It can be
observed that for every K studied, the
evolutionary search continues for a longer
period when growth is included.
01 1
01 2
K0 K1
1
1
N = 3 K = 1
(a)
1
1
f(0)
0.76
0.23
0.56
0.98
f(1)
0.02
0.34
0.38
0.86
Fitness = 1/N ∑ f(n)
Fitness = (0.23 + 0.38 + 0.53)/3 = 0.38
(b)
FIGURE 1 An example NK model with parameters N = 3 and K = 1, where arrows indicate each
arbitrarily chosen dependent gene (left). The table with 2 K 1+^
h rows containing the fitness contributions
of each gene is shown (right), along with the fitness calculation for the example genome.
f(2)
0.99
0.82
0.53
0.19
NOVEMBER 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 87
IEEE Computational Intelligence Magazine - November 2021

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - November 2021
