|
his is
based on dividing population into species and
locating the best solution from each of them based
of its quality (seed), and distributing the rest
based on their proximity. Later, substitution
depends on this distribution.
The general structure of the SCGA
is very similar to a simple GA, and can be
summarized in the following steps:
-
Initialize P(t)
-
Evaluate P(t)
-
Identify species seeds Xs
-
Select P(t+1)
-
Crossover and Mutate
P(t+1)
-
Evaluate P(t+1)
-
Conserve species form Xs
in P(t+1)
-
t
= t+1, go back to step 3.
Differences are focused on steps
3 and 7 which are the ones that permit to form and
make to evolve the species identified in the
population. Now we will focus on these processes.
Firstly species
need to be identified as well as their seeds (the
dominant individual of the subset). For this, the
original population P(t) is arranged from
higher to lower, and the first individual is the
seed of the first species, and therefore the first
component of set Xs. From here
onwards the process becomes iterative, the next
individual in the arrangement is taken and it is
verified if the distance is longer than
sshare/2
from all the seeds contained to the moment in Xs,
if this is so this individual will be a new seed and
therefore will be joined to Xs.
With Xs
population is classified into the different
identified species. An individual j will
belong to a species which seed is xi
if its distance d(j, xi) is
smaller than
sshare/2.
As no restriction is set to the belonging to the
species there will be different ways to divide the
population.
The other
difference with a simple GA is the process of
species conservation, that consists of dividing the
population P(t+1) into species using the
seeds of Xs. With each seed of
Xs individuals of P(t+1) are
marked which are at a distance shorter than
sshare/2.
In the end, a series of individuals belonging to
species is obtained and consequently marked as such,
as well as another set of individuals that do not
belong to any of the species detected, and therefore
will be unmarked. The same way, in Xs
there will be seeds with species in P(t+1)
and others where this correspondence has not been
produced. Finally, in each species the seed will
replace the solution with worst quality. And seeds
without species will replace the individuals with a
worst quality among the unmarked ones.
|
