Chapter 1: Introduction
CHAPTER 1
Combinatorial optimization is a potential field for application in real world problems including scheduling, timetabling and vehicle route planning problems. A good survey of the state of the art is provided by [1] and [2]. But as far as real world decision making is concerned, it is also well known, that decision makers have to deal with more than one objective. The growth in the interest of theory and methodology of multi-criteria decision making (MCDM) over the last thirty years[3] [4] is well aware.
Although, combinatorial optimization ….., the main difficulty is that most of the literatures focus on continuous optimization, and they often restrict their attention to the optimization problem characterized by ad hoc test functions, such as the “spherical” objective function. On the other hand, when discrete optimization problems are considered, experiments are often restricted to the “onemax bit-counting” or “trap” functions, which can be regarded as the counterpart of the spherical objective function in binary search spaces.
There are not many standard benchmarks for combinatorial optimization. Many works use the real world applications of their interest, which is restricted to only in one single class of problems such as TSPs. Moreover, most of the literatures focus on one single metaheuristics, which is compared either to variants of the same metaheuristics, or to the simple heuristics which are problem-specific, or to exact methods. Only a very small number of papers perform benchmarks among different metaheuristics.
Surprisingly, multi-criteria or multi-objective combinatorial optimization (MOCO) has not been widely studied. Unfortunately, many methods use either problem-specific or ad-hoc representation encodings and operators. Moreover, the performance has not been sufficiently tested on hard problems, leaving the question of how to scales up open[].
Apart from the problem-specific solvers, most of the researches rely on either population-based methods (GAs and EAs) or methods of local search (SA, TS and GRASP) or hybridization methods. The population-based methods have an advantage over the local search methods as they usually produce more diversity of solutions whereas the local optimization methods have advantage on the quality of solutions.
The weakness of population-based methods is that the recombination operators are inefficient. Due to the decision space is discrete and the continuity of the permutation space is complex, simple operators are ineffective as they might produce the infeasible solutions. In order to recombine the potential solutions, we need to prevent or repair the infeasible solutions[5]. There are attempts to redesign the GAs specialized for the permutation problems including fmGA[6], and OmeGA[7] to be able to solve various types of the ordering problems. These algorithms are later extended to use in multi-objective ordering problems [8].
This paper develops a new evolutionary algorithm based on probabilistic model called Coincidence Algorithm (COIN). This algorithm is designed specialized for permutation problems based on Markov Chain. The proposed algorithm adopts the negative knowledge to enhance the search by bounding the undesired solutions.
The structure of the paper is as follows. The motivations of the work are discussed in Section II. The proposed algorithm, Combinatorial Optimization with Coincidence, is explained in Section III. Section IV introduces the multi-objective version of COIN. The experiments are reported in Section V. Section VI concludes the work. The potential future works are discussed in the final Section VII.
This chapter provides some necessary knowledge on both single and multi-objective combinatorial problems and review of the available both exact and heuristic solution methodologies. However, this thesis focuses only on the methods which apply to the permutation representation, which is naturally more suitable with combinatorial problems. The solution methodologies involving the transformation of representations are not in the scope of the review.
Chapter 1: Introduction
Combinatorial and Multi-objective Combinatorial Optimization
Negative Knowledge
Summary