|
First, the solutions of the population have to be
divided into niches, using an identification
technique of cluster kind (the process is focused on
establishing the radius of each identified niche),
and once niches are created the fitness sharing
method is applied.
Process for the niche
identification technique
1.
The solution of the population with a higher
quality is the first centre of the first niche (k
= 1).
2. Calculating the distance
of the rest of the solutions of the population
regarding this centre and sorting from lowest to
highest with respect to this distance.
3. Calculating value βj+1
= (Fj+1 x Fi
) / (Fmax- Fmin),
being Fj the quality of the
individual j, Fj+1 the
quality of the individual whose distance is the
next highest to individual j in the
sorted list, Fmax and Fmin
the maximum and minimum quality of the
population respectively.
4. Comparing βj+1
with a maximum permitted value called
β*.
-If βj+1
< β*
individual j+1 is marked as
belonging to niche k, repeating step 3
with the following individual in the list.
-If βj+1
> β*
individual j will be the border of
the niche establishing the radius of this
niche (the distance between individual j
and the centre k). Individual j+1
will belong to different niche. Go to step
5.
5. Sorting out according to
the quality of the population of unmarked
individuals. The best unmarked individual will
be the centre of the following niche (k+1).
Go to step 2.
Using
βj
instead of quality permits removing problems when
identifying the limits of the niches. Once niches
are identified, those that do not have a suitable
size established by authors in 10% of the total size
of the population are dismissed (parameter N*).
And finally, a study on niche interferences is
performed. In a graphic way, both possible
interferences are represented in the following
figure.
It is important to consider that in the original
niche interference the problems are defined in
continuous space and it is possible to define niches
as hyperspheres (hyperspheric). The job shop problem
is not continuous and the defined interferences must
be reviewed.
First
interference happens whenever the centre of one of
the niches is inside the geographic area defined for
other niche. In this case, the presented solution is
the union of both niches in one whose radius is
Rnew=R1
x (R2/R1)1/3.
The new centre will be displaced a value L*
:
L* = (L x R2)/(R1+R2),
where L is the distance between the centres.
In second interference, the radiio of both niches are external
but share a common area. In this case both niches
are kept but reducing their radii to achieve that
the intersection of both niches be the empty set.
The value of the new radii will be given by:
Ri-new= (L x Ri)/(R1+R2)
with i=1, 2
In the
case of the job shop, it is possible to maintain the
interference of the second type, as there is no
problem in the new definition. However, the solution
of the first type has to be modified as in this case
the space between solutions is not continuous but
discreet and, as a result it is not possible to
identify a new centre at an L*
distance from one that exists. The adaptation we
suggest is to maintain one of the niches, the one
with centre with higher quality and modify its radii
in order it covers all the identified solutions:
Rnew =
Rworst + L.
Once niches are identified,
removed those do not reach a minimum size and being
the interferences studied we get a set of
niches.
With this information we apply
the selection with the sharing system.
-For
individuals i identified as belonging to a
niche k its quality will be the original
between the size of the niche it belongs to.
-For
individuals j unidentified in any niche its
quality will be the original between the average
size of the existing niches.
In the reproduction process
a mating restriction strategy is implemented in
order only individuals of the same niche can
reproduce. Lastly, a modified elitism is applied in
the substitution. All the centres of the identified
niches are reserved for the next generation.
|
