A MULTIOBJECTIVE GENETIC LOCAL SEARCH ALGORITHM AND ITS APPLICATION TO FLOWSHOP SCHEDULING

In this paper, we propose a hybrid algorithm for finding a set of nond ominated solutions of a multi-objective optimization problem. In the p roposed algorithm, a local search procedure is applied to each solutio n (i.e., each individual) generated by genetic operations. Our algorit hm uses a weighted sum of multiple objectives as a fitness function. T he fitness function is utilized when a pair of parent solutions are se lected for generating a new solution by crossover and mutation operati ons. A local search procedure is applied to the new solution to maximi ze its fitness value. One characteristic feature of our algorithm is t o randomly specify weight values whenever a pair of parent solutions a re selected. That is, each selection (i,e,, the selection of two paren t solutions) is performed by a different weight vector. Another charac teristic feature of our algorithm is not to examine all neighborhood s olutions of a current solution in the local search procedure, Only a s mall number of neighborhood solutions are examined to prevent the loca l search procedure from spending almost all available computation time in our algorithm. High performance of our algorithm is demonstrated b y applying it to multi-objective flowshop scheduling problems.