Research on A New Multiobjective Combinatorial Optimization Algorithm

An real world engineering design problem is usually with multiple conflicting objectives, and it is easily lead to the difficulty to optimize these objectives at the same time. Multiobjective combinatorial optimization is not only an open theory problem, but also with an important practical significance. After modeling the constrained multiobjective combinatorial optimization problem, a new optimization algorithm is presented in detail. The algorithm is different from existing multiobjective evolutionary algorithms in three aspects. The first is the two-layer encoding method. The second is that it hybrids the simulated annealing algorithm with the genetic algorithm to improve the global searching ability while maintaining the parallel computing ability. The third is the decision making mechanism to evaluate candidate solutions with several design objectives. A numerical example study shows that the proposed algorithm is capable of dealing with multiobjective combinatorial optimization problems.

I. Introduction

Multiobjective combinatorial optimization problem is ubiquitous in various applications, such as operation management and logistics, production planning and scheduling, resource allocation, location and distribution problems, etc. [1], [2]. A lot of algorithms has been developed to solve combinatorial optimization problems. Because of the computing complexity, it is well known that a feasible way is to find a feasible solution or solution set whose measure is not too far from the optimum, especially for multiple objective problems. Multiobjective evolutionary optimization is a lively research field and arouses much interest. Genetic algorithms (GA) are often applied to solve the combinatorial optimization problems. Weighted-sum method is a common method to transfer the multiobjective problem to single objective problem. In order to solve combinatorial optimization problems in an acceptable timeframe, specific multiobjective evolutionary algorithms (MOEAs) were initially developed in the mid-eighties in twentieth century [3].