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

2

Differential Evolution for Permutation − Based

Combinatorial Problems

Godfrey Onwubolu 1 and Donald Davendra 2

1

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

2

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

Abstract. The chapter clarifies the differences between wide-sense combinatorial optimization
and strict-sense combinatorial optimization and then presents a number of combinatorial prob-
lems encountered in practice. Then overviews of the different permutative-based combinatorial
approaches presented in the topic are given. The chapter also includes an anatomy of the differ-
ent permutative-based combinatorial approaches in the topic, previously carried out elsewhere to
show their strengths and weaknesses.

2.1 Introduction

It is first necessary to define what combinatorial problems are. In combinatorial prob-
lems, parameters can assume only a finite number of discrete states, so the number of
possible vectors is also finite. Several classic algorithmic problems of a purely combi-
natorial nature include sorting and permutation generation, both of which were among
the first non numerical problems arising on electronic computers. A permutation de-

scribes an arrangement, or ordering, of parameters that define a problem. Many algo-
rithmic problems tend to seek the best way to order a set of objects. Any algorithm for
solving such problems exactly must construct a series of permutations.

−

[10] classify

wide-sense and strict − sense combinatorial optimization.

2.1.1 Wide-Sense Combinatorial Optimization

Consider switching networks which can be divided into fully connected non-blocking
networks, and fully connected but blocking networks. Non

− blocking switching net-

works can be re arrangeable non-blocking networks, wide-sense non-blocking net-

works, and strictly non-blocking networks. A network is classified as rearrangeable if
any idle input may be connected to any idle output provided that existing connections
are allowed to be rearranged. A strictly non

−

blocking network on the other hand is
always able to connect any idle input to any idle output without interfering with the ex-
isting connections. Wide

−

sense non-blocking network achieves strictly non-blocking
property with the help of an algorithm.

−