Exact And Representative Algorithms For Multi Objective Optimization

In most real-life problems, the decision alternatives are evaluated with multiple conflicting criteria. The entire set of non-dominated solutions for practical problems is impossible to obtain with reasonable computational effort. Decision maker generally needs only a representative set of solutions from the actual Pareto front. First algorithm we present is for efficiently generating a well dispersed non-dominated solution set representative of the Pareto front which can be used for general multi objective optimization problem. The algorithm first partitions the criteria space into grids to generate reference points and then searches for non-dominated solutions in each grid. This grid-based search utilizes achievement scalarization function and guarantees Pareto optimality. The results of our experimental results demonstrate that the proposed method is very competitive with other algorithms in literature when representativeness quality is considered; and advantageous from the computational efficiency point of view. Although generating the whole Pareto front does not seem very practical for many real life cases, sometimes it is required for verification purposes or where DM wants to run his decision making structures on the full set of Pareto solutions. For this purpose we present another novel algorithm. This algorithm attempts to adapt the standard branch and bound approach to the multi objective context by proposing to branch on solution points on objective space. This algorithm is proposed for multi objective integer optimization type of problems. Various properties of branch and bound concept has been investigated and explained within the multi objective optimization context such as fathoming, node selection, heuristics, as well as some multi objective optimization specific concepts like filtering, non-domination probability, running in parallel. Potential of this approach for being used both as a full Pareto generation or an approximation approach has been shown with experimental studies