Discrete Set Handling - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 162

7

Discrete Set Handling

Ivan Zelinka

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

Abstract. Discrete Set Handling and its application to permutative problems is presented in this
chapter. Discrete Set is applied to Differential Evolution Algorithm, in order to enable it to solve
strict-sence combinatorial problems. In addition to the theoretical framework and description,
benchmark Flow Shop Scheduling and Traveling Salesman Problems are solved. The results are
compared with published literature to illustrate the effectiveness of the developed approach. Also,
general applications of Discrete Set Handling to Chaotic, non-linear and symbolic regression
systems are given.

7.1 Introduction

In recent years, a broad class of algorithms has been developed for stochastic optimiza-
tion, i.e. for optimizing systems where the functional relationship between the indepen-
dent input variables x and output (objective function) y of a system S is not known.
Using stochastic optimization algorithms such as Genetic Algorithms (GA), Simulated
Annealing (SA) and Differential Evolution (DE), a system is confronted with a random
input vector and its response is measured. This response is then used by the algorithm
to tune the input vector in such a way that the system produces the desired output or
target value in an iterative process.
Most engineering problems can be defined as optimization problems, e.g. the find-
ing of an optimal trajectory for a robot arm, the optimal thickness of steel in pressure
vessels, the optimal set of parameters for controllers, optimal relations or fuzzy sets
in fuzzy models, etc. Solutions to such problems are usually difficult to find, since
their parameters usually include variables of different types, such as floating point or
integer variables. Evolutionary algorithms (EAs), such as the Genetic Algorithms and
Differential Evolutionary Algorithms, have been successfully used in the past for these
engineering problems, because they can offer solutions to almost any problem in a sim-
plified manner: they are able to handle optimizing tasks with mixed variables, including
the appropriate constraints, and they do not rely on the existence of derivatives or aux-
iliary information about the system, e.g. its transfer function.
Evolutionary algorithms work on populations of candidate solutions that are evolved
in generations in which only the best individuals are likely to

survive. This article introduces Differential Evolution, a well known stochastic opti-
mization algorithm. It explains the principles of permutation optimization behind DE
and demonstrates how this algorithm can assist in solving of various permutation opti-
mization problems.

− suited − or fittest −