A Fast Algorithm for Finding the non Dominated Set in Multiobjective Optimization

The working of single objective optimization algorithm and multi objective optimization algorithm is quite different. This difference is due to number of optimal solution approached by both the algorithms. In single objective optimization problem there will be a single optimal solution, even though in multi model optimization there may be more than one solution but we are interested in only one optimal solution, where as in multi objective optimization problem, there will be many set of optimal solutions. These sets are called different non dominated front, and every non dominated front will contain a set of non dominated solutions thus there are two tasks of an ideal multi objective optimization algorithm (i) To find multiple non dominated fronts (or to identify different set of non dominated solutions). (ii) To seek for Pareto optimal solutions with a good diversity in objective and decision variable values. In this paper, we explain a new algorithm for finding non dominated set of a multi objective optimization problem. In literature many algorithms are used for this task like naive and slow method [2], fast and efficient method [3] and Kung et al method [7]. Recently two new algorithms are proposed by Ding [4] and Jun Du[1].The worst case time complexity of all algorithm(including recently proposed algorithm) is (OM(N)),Previously Kung’s algorithm was best in its average and best case time complexity but Jun du in 2007 proved that his algorithm is best in comparison of kung’s algorithm. While we were unable to reduce worst case time complexity, The best case time complexity of proposed algorithm is O(NLog(N))( for any number of objective functions )which is a improvement as compared to othere algorithms. Also it follows a simple approach, no hectic summation and production method. The paper is organized into four sections. Section 2 presents some background detail of Different Preexisting Algorithms and specifies the necessary definition related to non dominated set. Section 3 describes the proposed approach and stepwise algorithm also difference between Kung’s algorithm and proposed algorithm is presented; In Section 4, an experimental analysis and complexity of the proposed algorithm are presented. Finally, Section 5 concludes the paper.