Information Technology Reference
In-Depth Information
Ta b l e 2 . 6 .
Anatomy of four permutation-based combinatorial DE approaches
+
Approach
Observations
Permutation Matrix
In practice, this approach tends to stagnate because moves derived
from the permutation matrix are seldom productive. In addition, this
method is unable to distinguish rotated but otherwise equal tours.
Because they display a unique binary signature, equal tours can be
detected by other means, although this possibility is not exploited
in the algorithm described in Fig 2.8.
Adjacency Matrix
(1) This scheme preserves good sections of the tour if the popu-
lation has almost converged, i.e., if most of the TSP matrices in
the population contain the same sub
tours. When the population
is almost converged, there is a high probability that the difference
matrix will contain just a few ones, which means that there are only
a few cities available for a 2
−
−
exchange.
Relative Position Indexing
(1) This approach resembles traditional DE because they both use
vector addition, although their ultimate effect is to shuffle values
between parameters, i.e., generate permutations.
(2) This approach impedes DE
s self-steering mechanism because
it fails to recognize rotated tours as equal.
(3) A closer look, however, reveals that DE
s mutation scheme
together with the forward and backward transformations is, in
essence, a shuffling generator.
(4) In addition, this approach does not reliably detect identical
tours because the difference in city indices has no real signifi-
cance. For example, vectors with rotated entries, e.g.,
(
2
3
4
5
1
)
,
,
,
,
and
(
1
2
3
4
5
)
, are the same tour, but
their difference, e.g.,
,
,
,
,
(
1
1
1
1
,
−
4
)
, is not zero.
,
,
,
Forward/backward Transfor-
mation
(1) This approach resembles traditional DE because they both use
vector addition, although their ultimate effect is to shuffle values
between parameters, i.e., generate permutations.
(2) This approach impedes DE
s self
steering mechanism because
it fails to recognize rotated tours as equal.
(3) In addition, Onwubolu
s method usually generates invalid tours
that must be repaired. Even though competitive results are reported
in Onwubolu there is reason to believe that the success of this ap-
proach is primarily a consequence of prudently chosen local heuris-
tics and repair mechanisms, not DE mutation.
−
+
Described in Price et al. (2005).
2.4
Conclusions
There has been some reservation that although DE has performed well on wide
sense
combinatorial problems, its suitability as a combinatorial optimizer is still a topic of
considerable debate and a definitive judgment cannot be given at this time. Moreover, it
is said that although the DE mutation concept extends to other groups, like the permuta-
tion group, there is no empirical evidence that such operators are particularly effective.
The opinion expressed in this topic is similar to that of [18] that all good heuristics are
−
Search WWH ::
Custom Search