Graphics Reference
In-Depth Information
where
n
is the number of instances in
TR
,
s
is the number of instances in
S
, and
x
defines the number of badly classified instances (basing on S).
is the number of
classes in the classification task.
F
is the cost of encoding which
s
instances
if the
n
available are retained, and is defined as:
(
s
,
n
)
⎛
⎞
s
n
!
log
∗
⎝
⎠
F
(
s
,
n
)
=
(8.7)
j
!
(
n
−
j
)
!
j
=
0
log
∗
n
2
F
(
i
−
1
)
.
The
ELH
algorithm starts from the empty set and adds instances only if the cost
function is minimized.
ELGrow
additionally tries to remove instances if it helps to minimize the cost func-
tion.
Explore
extends ELGrow by 1000 mutations to try to improve the classifier.
Each mutation tries adding an instance to
S
, removing one from
S
, or swapping
one in
S
with one in
TR
-
S
, and keeps the change if it does not increase the cost
of the classifier.
=
arg min
k
F
(
k
)
≥
n
,
k
is integer, and
F
(
0
)
=
1
,
F
(
i
)
=
•
CHC (CHC)
[
19
]—During each generation the CHC develops the following steps.
1. It uses a parent population of size
N
to generate an intermediate population
of
N
individuals, which are randomly paired and used to generate
N
potential
offsprings.
2. Then, a survival competition is held where the best
N
chromosomes from the
parent and offspring populations are selected to form the next generation.
CHC also implements a form of heterogeneous recombination using HUX, a spe-
cial recombination operator. HUX exchanges half of the bits that differ between
parents, where the bit position to be exchanged is randomly determined. CHC
also employs a method of incest prevention. Before applying HUX to two par-
ents, the Hamming distance between them is measured. Only those parents who
differ from each other by some number of bits (mating threshold) are mated. The
initial threshold is set at
L
4, where
L
is the length of the chromosomes. If no
offspring are inserted into the new population then the threshold is reduced by
one.
No mutation is applied during the recombination phase. Instead, when the popula-
tion converges or the search stops making progress, the population is reinitialized
to introduce new diversity to the search. The chromosome representing the best
solution found over the course of the search is used as a template to reseed the
population. Reseeding of the population is accomplished by randomly changing
35 % of the bits in the template chromosome to form each of the other
N
/
−
1
new chromosomes in the population. The search is then resumed.
•
Steady-state memetic algorithm (SSMA)
[
62
]—The SSMA was proposed to
cover a drawback of the conventional evolutionary PS methods that had appeared
before: their lack of convergence when facing large problems. SSMA makes use
of a local search or meme specifically developed for this PS problem. This inter-
