Differential Evolution for Permutation-Based Combinatorial Problems - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 13

Let us consider another example. In this case we consider nuts having pitch diameters
which are expressed in decimal places such as 2.5 mm, 3.6 mm,..., 5.3 mm, 6.2 mm, etc.
These nuts are grouped into classes so that Class A nuts belong to those nuts whose pitch
diameters lie between 2.5 mm − 3.6 mm, Class B nuts belong to those nuts whose pitch

−

diameters lie between 3.65 mm 4.8 mm, etc. In this case the classes are wide sense but

the actual dimensions are continuous in nature. Therefore picking nuts based on their
classes could be viewed as a wide

−

sense combinatorial problem because dimensional
properties of a nut are continuous variables.

2.1.2 Strict-Sense Combinatorial Optimization

There are a number of strict-sense combinatorial problems, such as the traveling sales-
man problem, the knapsack problem, the shortest-path problem, facility layout problem,
vehicle routing problem, etc. These are strict-sense combinatorial problems because
they have no continuous counterpart [10]. These strict-sense combinatorial problems
require some permutation of some sort. The way the objects are arranged may affect the
overall performance of the system being considered. Arranging the objects incorrectly
may affect the overall performance of the system. If there is a very large number of
the object, then the number of ways of arranging the objects introduces another dimen-
sion of problem known as combinatorial explosion. Classical DE was not designed to
solve this type of problem because these problems have hard constraints. Strong con-
straints like those imposed in the traveling salesman problem or facility layout problem
make strict-sense combinatorial problems notoriously difficult for any optimization al-
gorithm. It is this class of problems that this topic is aimed at solving. A number of
techniques have been devised to stretch the capabilities of DE to solve this type of hard
constraint-type problems.

2.1.3 Feasible Solutions versus “Repairing” Infeasible Solutions for Strict-Sense
Combinatorial Optimization
In DE s case, the high proportion of infeasible vectors caused by constraints prevents the
population from thoroughly exploring the objective function surface. [10] concluded
that in order to minimize the problems posed by infeasible vectors, algorithms can either
generate only feasible solutions, or “repair” infeasible ones.
The opinion expressed in this topic is that all good heuristics are able to transform a
combinatorial problem into a space which is amenable for search, and that there is no
such thing as an “all-cure” algorithm for combinatorial problems. For example, particle
swarm optimization (PSO) works fairly well for combinatorial problems, but only in
combination with a good tailored heuristic (see for example, [8]). If such a heuristic is
used, then PSO can locate promising regions. The same logic applies to a number of
optimization approaches.

2.2 Combinatorial Problems

A wide range of strict-sense combinatorial problems exist for which the classical
DE approach cannot solve because these problems are notoriously difficult for any