Cost to Evaluate Versus Cost to Learn? Performance of Selective Evaluation Strategies in Multiobjective Optimization

摘要

Population based stochastic algorithms have long been used for the solution of multiobjective optimization problems. In the event the problem involves computationally expensive analysis, the existing practice is to use some form of surrogates or approximations. Surrogates are either used to screen promising solutions or approximate the objective functions corresponding to the solutions. In this paper, we investigate the effects of selective evaluation of promising solutions and try to derive answers to the following questions: (a) should we discard the solution right away relying on a classifier without any further evaluation? (b) should we evaluate its first objective function and then decide to select or discard it? (c) should we evaluate its second objective function instead and then decide its fate or (d) should we evaluate both its objective functions before selecting or discarding it? The last form is typically an optimization algorithm in its native form. While evaluation of solutions generate information that can be potentially learned by the optimization algorithm, it comes with a computational cost which might still be insignificant when compared with the cost of actual computationally expensive analysis. In this paper, a simple scheme, referred as Combined Classifier Based Approach (CCBA) is proposed. The performance of CCBA along with other strategies have been evaluated using five well studied unconstrained bi-objective optimization problems (DTLZ1-DTLZ5) with limited computational budget. The aspect of selective evaluation has rarely been investigated in literature and we hope that this study would prompt design of efficient algorithms that selectively evaluate solutions on the fly i.e. based on the trade-off between need to learn/evaluate and cost to learn.