Cellular genetic local search for multi-objective optimization
Tadahiko Murata, Hisao Ishibuchi, Mitsuo Gen · 2000
In this paper, we show how cellular structures can be combined with multi-objective genetic local search (MOGLS) algorithms for improving their search ability to find Pareto-optimal solutions of multi-objective optimization problems. We propose two ideas for implementing a cellular MOGLS algorithm: assignment of a different local search direction to each cell, and relocation of individuals based on their objective values. In our cellular MOGLS algorithm, every individual in each population exists in a cell of a spatially structured space (e.g., two-dimensional grid-world) where each cell has a different local search direction. Such a local search direction corresponds to weights in a scalar fitness function defined by the weighted sum of multiple objectives. The selection of parents for generating a new individual in a cell is performed within the neighborhood of that cell based on its local search direction. A local search procedure is applied to new individuals generated by genetic operations for maximizing the fitness function. It should be noted that each cell has its own local search direction, which is used in the selection as well as in the local search. Newly generated individuals are relocated into cells according to their locations in the multi-dimensional objective space.