Information Technology Reference
In-Depth Information
Since each value is randomly selected, the value has to be removed from the array
after selection in order to avoid duplication. Through experimentation it was shown that
random mutation was the most effective in solution repairment.
Illustration
:
Following the previous illustrations, assume the same in-feasible solution:
x
=
{
3
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
5
.
The first step is to isolate all repetitive values in the solution. These are highlighted
in the following array:
x
=
}
{
3
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
5
}
. As shown the values 3 and 5 are
repeated in the solution.
A random array is created which sets the default values:
DV
=
{
,.Here,it
shows that the first replicated value which is 3 should be set as default on its second
occurrence. The second replicated value 5 should be set as default on its first occurrence:
x
=
2
,
1
}
{
3
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
5
}
. The in-feasible values are now in index 1 and 10 given
as
x
=
{
1
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
10
}
An array of missing values is now generated as
MV
=
{
8
,
9
}
, since values 8 and 9
are missing from the solution.
An insertion array is now randomly generated, which specifies the position of the in-
sertion of each value:
IA
=
. Since only two values were missing so only two ran-
dom numbers are generated. In this respect, the first value 1 in
IA
, outlines that the value
pointed by index 1 in
MV
which is 8 is to be placed in the first indexed in-feasible so-
lution and likewise for the other missing value given as:
x
=
{
1
,
2
}
{
1
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
10
}
.
3.4.2
Improvement Strategies
Improvement strategies were included in order to improve the quality of the solutions.
Three improvement strategies were embedded into the heuristic. All of these are one
time application based. What this entails is that, once a solution is created each strategy
is applied only once to that solution. If improvement is shown, then it is accepted as the
new solution, else the original solution is accepted in the next population.
3.4.2.1 Standard Mutation
Standard mutation is used as an improvement technique, to explore random regions of
space in the hopes of finding a better solution. Standard mutation is simply the exchange
of two values in the single solution.
Two unique random values are selected
r
1
,
r
2
∈
rand
[1
,
D
],whereas
r
1
=
r
2
.The
exchange
↔
Solution
r
1
and the so-
lution is evaluated. If the fitness improves, then the new solution is accepted in the
population.
values indexed by these values are exchanged:
Solution
r
1
Illustration
:
In Standard Mutation assume a solution given as:
x
=
{
8
,
4
,
2
,
1
,
3
,
5
,
6
,
7
,
10
,
9
}
.Two
random numbers are generated within the bounds:
Rnd
=
{
3
,
8
}
. These are the indexes
Search WWH ::
Custom Search