Information Technology Reference
In-Depth Information
4. Mutation.
According to the mutation probability, select certain individuals
and randomly change the permutation vectors
x
and
y
.
5.
2
-opt Exchange.
For permutation vectors
x
and
y
in each individual, exchange
the order of any two elements until no improvement can be found. Note that there
are many other available local search methods, see [21], [22].
5Num lExp imen s
In this section, we test the effectiveness of the proposed 2-approximation algo-
rithm (2-APP) and HGA on different test instances. Numerical experiments are
implemented in Java and run on Intel (R) Xeon (R) CPU E5410.
The test instances are generated as follows: first, we randomly generate
n
points (
x
1
,
···
,x
n
) for the plants and another
n
points (
y
1
,
···
,y
n
)forprod-
ucts; then the link cost is defined by the
p
-norm, i.e.,
d
i,j
=
x
i
−
y
j
p
,where
p
=1
,
2
,
+
. Other parameters are chosen as: population size = 20, mutation
possibility = 0
.
05, crossover possibility = 0
.
1 and if no improvement is made
in two consecutive iterations, then stop HGA. Value of
RP
is used as a lower
bound for the original problem and we define the Relative Error (
RE
)of(
∞
∗
)as
RE
(%) =
Value of
Value of
RP
Value of
RP
∗−
×
100%
.
Table 1 reports the relative error (
RE
(%)) and CPU runtime (
T
(
s
)) of 2-APP,
HGA and CPLEX solver for 10 randomly generated test instances. In this test,
we set
n
= 150,
p
= 2. To compare the solution quality for given time limit,
we set the time limit of CPLEX solver to 600 seconds. From Table 1, 2-App
provides high quality solutions for the test instances and HGA further improves
the solution quality by 1%
3%; however, even given 600 second, CPLEX solver
can't find solution within relative error less than 40%.
−
Tabl e 1.
Performance of 2-APP, HGA and CPLEX when
n
= 150
,p
=2
2-APP HGA CPLEX
No.
RE
(%)
T
(
s
)
RE
(%)
T
(
s
)
RE
(%)
T
(
s
)
1
4.86 0.09
2.41 4.89
109 600
2
2.43 0.06
1.59 4.81
70.8 600
3
1.98 0.06
0.99 4.84
52.1 600
4
4.40 0.05
3.14 4.84
49.1 600
5
5.13 0.06
2.46 4.81
75.9 600
6
4.30 0.08
2.81 4.84
60.8 600
7
5.27 0.06
2.63 4.81
64.0 600
8
3.33 0.09
1.94 4.80
58.3 600
9
1.52 0.11
0.51 4.86
65.2 600
10
4.30 0.06
2.48 4.82
534 600
Search WWH ::
Custom Search