A pattern-based evolving mechanism for genetic algorithm to solve combinatorial optimization problems

The combinatorial optimization problem always is ubiquitous in various applications and has been proved to be well known NP-hard problem that classical mathematical methods cannot solve within the polynomial time. To solve it, many approaches have been developed to find best or near best solutions. As one of such approaches, genetic algorithm is well known as being able to find satisfied solution within acceptable time, it is controlled by evolving mechanism to achieve optimization searching in the solutions space. In this paper, we propose a new evolving mechanism for GA to improve the solution quality and searching efficiency as well. This evolving mechanism can extract a generalized pattern from elite individuals in the whole population. The pattern is used to determine the selection probability to experience the genetic operations such as crossover, mutation, replication, etc. moreover, the evolving mechanism includes a replacement mechanism to substitute the worse individual for the potential excellent individual to expand searching space. The computation results show that the proposed evolving mechanism can work effectively and find satisfactory solutions better than traditional evolving mechanisms, even though the solution space increases with the problem size.

I. Introduction

Combinatorial optimization is lively field of applied mathematics, combining techniques from combinatorics, linear programming, and the theory of algorithms, to solve optimization problems over discrete structures [1]. There are many practical optimization problems to be put under combinatorial optimization, such as operations management and logistics, production planning, resource allocation, scheduling, location and distribution problems, etc. [2], [3]. To solve combinatorial optimization problems, many algorithms or approaches have been developed. It is well known t hat many combinatorial optimization problems are NP-hard, and it is unlikely that we will ever be able to find efficient (i.e. polynomial-time) algorithms for their solution. In such cases it is worth looking for algorithms that always return a feasible solution whose measure is not too far from the optimum [4], such as Genetic Algorithm, Simulated Annealing, Tabu Search, Neural Networks, Ant Algorithm, etc.