Local Search Operators Based on Linear-Quadratic Approximations for Multiobjective Problems on a Budget Scenario

This paper presents three local search procedures based on linear-quadratic approximations for multiobjective problems, which consider a goal attainment model. The approximation is constructed for each objective using a current solution, a queue of evaluated solutions, and a nearest neighborhood algorithm. The operators differ by the approximation technique: linear regression, linear programming or linear matrix inequalities. Depending on the size of the queue, the approximation is done using a linear, a quadratic with diagonal or full symmetric Hessian function. In order to compare the local searches, an experimental procedure is applied using two benchmarks. For this, each local search operator is coupled with NSGA-II for solving problems on a limited budget scenario. The quality of the final solutions via the hypervolume indicator is assessed as well as the runtime for each method. A statistical test reveals that the version with local search based on linear regression produces superior nondominated sets.