PLS Algorithm And Auxiliary Function Method For Multi-objective Optimization

Multi-objective optimization has become an important research topic in economics, management, engineering, etc. Nowadays, lots of multi-objective optimization problems are NP-hard. With the wide application of multi-objective optimization, it has been highly anticipated to seek efficient algorithms for the problem.The Pareto Local Search (PLS) algorithm is a novel method in multi-objective combinatorial optimization, which searches for a multi-objective local optimal solution set from an initial solution. To improve the algorithm, we take the solutions in a multi-objective local optimal solution set as initial solutions, and further search for a multi-objective local optimal solution set, until a stopping criterion is satisfied. The new local search algorithms are named PLS I algorithm and PLS II algorithm. Comparing with the PLS algorithm, PLS I algorithm and PLS II algorithm expand the scope of the search with parallel local search. The obtained Pareto local optimal solutions are not dependent on the initial solutions.PLS I algorithm takes O(|N(S) ∩VT∩VF|2) steps at each iteration. Finally PLS I algorithm gets a bigger Pareto local optimum solution set than PLS algorithm, and PLS II algorithm has the same nature with PLS I algorithm. Computational tests on several instances demonstrate the effectiveness of the improved algorithm.Our next research is to find a Pareto optimal solution for solving bi-objective continuous optimization problems. A lot of preparatory work has been developed: constructing the Pareto local search algorithm, finding the relationship of descent directions and gradients of the objective functions, and determination of the step lengths of line searches. Furthermore, to find a better Pareto local optimal solution, we construct an auxiliary global minimization problem T(x, k, p). Research shows that:when pis large enough, T(x,k,p)and problem (P) have the same Pareto optimal solutions; Moreover, increasing the value of k, the minimization of T(x,k,p) can escape from the previous Pareto local optimal solution. So we can get a better Pareto local optimal solution. At last, the proposed algorithm has convergence property.