Relative Position Indexing Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 80

4

Relative Position Indexing Approach

Daniel Lichtblau

Wolfram Research, Inc., 100 Trade Center Dr., Champaign, IL 61820, USA
[e-mail]

Abstract. We introduce some standard types of combinatorial optimization problems, and indi-
cate ways in which one might attack them using Differential Evolution. Our main focus will be on
indexing by relative position (also known as order based representation ); we will describe some
related approaches as well. The types of problems we will consider, which are abstractions of
ones from engineering, go by names such as knapsack problems , set coverings , set partitioning ,
and permutation assignment . These are historically significant types of problems, as they show
up frequently, in various guises, in engineering and elsewhere. We will see that a modest amount
of programming, coupled with a sound implementation of Differential Evolution optimization,
can lead to good results within reasonable computation time. We will also show how Differential
Evolution might be hybridized with other methods from combinatorial optimization, in order to
obtain better results than might be found with the individual methods alone.

4.1 Introduction

The primary purpose of this chapter is to introduce a few standard types of combina-
torial optimization problems, and indicate ways in which one might attack them using
Differential Evolution. Our main focus will be on indexing by relative position (also
known as order based representation ); we will describe some related approaches as
well. We will not delve much into why these might be regarded as “interesting” prob-
lems, as that would be a chapter- or, more likely, topic- in itself. Suffice it to say that
many problems one encounters in the combinatorial optimization literature have their
origins in very real engineering problems, e.g. layout of hospital wings, electronic chip
design, optimal task assignments, boolean logic optimization, routing, assembly line
design, and so on. The types of problems we will consider, which are abstractions of
the ones from engineering, go by names such as knapsack problems , set coverings , set
partitioning ,and permutation assignment . A secondary goal of this chapter will be to
introduce a few ideas regarding hybridization of Differential Evolution with some other
methods from optimization.
I will observe that, throughout this chapter at least, we regard Differential Evolu-
tion as a soft optimization tool. Methods we present are entirely heuristic in nature. We
usually do not get guarantees of result quality; generally this must be assessed by in-
dependent means (say, comparison with other tactics such as random search or greedy
algorithms, or a priori problem-specific knowledge). So we use the word optimization
a bit loosely, and really what we usually mean is improvement . While this may seem to
be bad from a theoretical point of view, it has advantages. For one, the field is relatively