Forward Backward Transformation - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 77

definite conclusions can be made on this aspect, apart from the advise for simulations
for tuning.
Another important feature of EDE is the level of stochasticity. DE has two levels;
first the initial population and secondly the crossover. EDE has five; in addition to the
two mentioned, the third is repairment, the fourth is mutation and fifth is crossover. All
these three are embedded on top of the DE routine, so the DE routines are a directive
search guide with refinement completed in the subsequent routines.
Local search was included in EDE because permutative problems usually require
triangle inequality routines. TSP is notorious in this respect, and most heuristics have
to employ local search in order to find good solutions. ACS [11], Scatter Search [14]
apply local search on each and every solution. This increases computational time and
reduces effectiveness of the heuristic for practical applications. The idea of EDE was to
only employ local search when stagnation is detected, and to employ the simplest and
time economical one.
In terms of produced results, EDE is effective, and more so since it was left in non-
altered form for all the problem classes. This is a very important feature since it negates
re-programming for other problem instances. Another important feature is that EDE
is fairly fast for these problems. Naturally, the increase in problem size increases the
execution time, however EDE does not employ any analytical formulation within its
heuristic, which keeps down the execution time while producing the same results as
with other heuristics.
It is hoped that the basic framework of this approach will be improved to include
more problem instances, like Job Shop Scheduling and other manufacturing scheduling
problems.
References
1. Battitti, R., Tecchiolli, G.: The reactive tabu search. ORCA Journal on Computing 6, 126-
140 (1994)
2. Burkard, R., Rendl, F.: A thermodynamically motivated simulation procedure for combina-
torial optimisation problems. Eur. J. Oper. Res. 17, 169-174 (1994)
3. Carlier, J.: Ordonnancements a Contraintes Disjonctives. RAIRO. Oper. Res. 12, 333-351
(1978)
4. Chen, C., Vempati, V., Aljaber, N.: An application of genetic algorithms for the flow shop
problems. Eur. J. Oper. Res. 80, 359-396 (1995)
5. Connolly, D.: An improved annealing scheme for the QAP. Eur. J. Oper. Res. 46, 93-100
(1990)
6. Davendra, D.: Differential Evolution Algorithm for Flow Shop Scheduling, Bachelor Degree
Thesis, University of the South Pacific (2001)
7. Davendra, D.: Hybrid Differential Evolution Algorithm for Discrete Domain Problems. Mas-
ter Degree Thesis, University of the South Pacific (2003)
8. Davendra, D., Onwubolu, G.: Flow Shop Scheduling using Enhanced Differential Evolu-
tion. In: Proceeding of the 21st European Conference on Modelling and Simulation, Prague,
Czech Republic, June 4-5, pp. 259-264 (2007)
9. Davendra, D., Onwubolu, G.: Enhanced Differential Evolution hybrid Scatter Search for
Discrete Optimisation. In: Proceeding of the IEEE Congress on Evolutionary Computation,
Singapore, September 25-28, pp. 1156-1162 (2007)