Information Technology Reference
In-Depth Information
The results obtained are compared with those produced by GA, Particle Swarm Op-
timisation (
PSO
spv
)DE(
DE
spv
) and DE with local search (
DE
spv
+
exchange
)asin[38].
The results are tabulated in Table 3.35.
It can be observed that EDE compares outstandingly with other algorithms. EDE
basically outperforms GA, PSO and
DE
spv
. The only serious competition comes from
the new variant of
DE
spv
+
exchange
.EDEand
DE
spv
+
exchange
are highly compatible. EDE
outperforms
DE
spv
+
exchange
on the data sets of 20x10, 20x20, 50x5 and 200x5. In the
remainder of the sets EDE performs remarkbly to the values reported by
DE
spv
+
exchange
.
On average EDE displays better standard deviation than that of
DE
spv
+
exchange
.This
validates the consistency of EDE compared to
DE
spv
+
exchange
. It should be noted that
DE
spv
+
exchange
utilises local search routine as its search engine.
A sample generation for the
F 30 x 100
FSS problem is given in Fig 3.15.
3.7
Quadratic Assignment Problem
The second class of problems to be conducted by EDE was the
Quadratic Assignment
Problem
(QAP). QAP is a
NP
-hard optimisation problem [35] which was stated for the
first time by [18]. It is considered as one of the hardest optimisation problems as general
instances of size
n
20 cannot be solved to optimally [10].
It can be described as follows: Given two matrices
≥
A
=(
a
ij
)
(3.11)
B
=(
b
ij
)
(3.12)
π
∗
minimising
find the permutation
n
i
=1
n
j
=1
a
ij
•
b
π(
i
)π(
j
)
min
π
∈
∏
(
n
)
f
(
π
)=
(3.13)
where
(
n
) is a set of permutations of
n
elements.
The problem instances selected for the QAP are from the OR Library [29] and re-
ported in [13]. There are two separate problem modules;
regular
and
irregular
.
The difference between regular and irregular problems is based on the
flow
∏
−
−
dominance
. Irregular problems have a flow
dominance statistics larger than 1.2. Most
of the problems come from practical applications or have been randomly generated with
non-uniform laws, imitating the distributions observed in real world problems.
In order to differentiate among the classes of QAP instances, the flow dominance
fd
is used. It is defined as a coefficient of variation of the flow matrix entries multiplied by
100. That is:
fd
=
100
σ
(3.14)
μ
where:
n
i
=1
n
j
=1
b
ij
1
n
2
•
μ
=
(3.15)
Search WWH ::
Custom Search