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

3

Forward Backward Transformation

Donald Davendra 1 and Godfrey Onwubolu 2

1

Tomas Bata University in Zlin, Faculty of Applied Informatics, Nad Stranemi 4511,
Zlin 76001, Czech Republic
[e-mail]

2

Knowledge Management & Mining, Inc., Richmond Hill, Ontario, Canada
onwubolu − [e-mail]

Abstract. Forward Backward Transformation and its realization, Enhanced Differential Evo-
lution algorithm is one of the permutative versions of Differential Evolution, which has been
developed to solve permutative combinatorial optimization problems. Novel domain conversions
routines, alongside special enhancement routines and local search heuristic have been incorpo-
rated into the canonical Differential Evolution in order to make it more robust and effective.
Three unique and challenging problems of Flow Shop Scheduling, Quadratic Assignment and
Traveling Salesman have been solved, utilizing this new approach. The promising results obtained
have been compared and analysed against other benchmark heuristics and published work.

3.1 Introduction

Complexity and advancement of technology have been in synch since the industrial
revolution. As technology advances, so does the complexity of formulation of these
resources.
Current technological trends require a great deal of sophisticated knowledge, both
hardware and software supported. This chapter discusses a specific notion of this knowl-
edge, namely the advent of complex heuristics of problem solving.
The notion of evolutionary heuristics is one which has its roots in common surround-
ing. Its premise is that co-operative behavior between many agents leads to better and
somewhat faster utilisation of the provided resources in the objective of finding the op-
timal solution to the proposed problem. The optimal solution here refers to a solution,
not necessarily the best, but one which can be accepted given the constraints.
Agent based heuristics are those which incorporate a multitude of solutions (unique
or replicated) which are then processed using some defined operators to yield new so-
lutions which are presumably better then the previous solutions. These solutions in turn
form the next generation of solutions. This process iterates for a distinct and predefined
number of generations .
One of the most prominent heuristic in the scope of real domain problems in Dif-
ferential Evolution (DE) Algorithm proposed by [31]. Real domain problems are those
whose values are essentially real numbers, and the entire solution string can have repli-
cated values. Some of the prominent problems are “De Jong” and “Shwafel” problems
which are multi − dimensional.