Objective reduction using a feature selection technique

ABSTRACT

This paper introduces two new algorithms to reduce the number of objectives in a multiobjective problem by identifying the most conflicting objectives. The proposed algorithms are based on a feature selection technique proposed by Mitra et. al. [11]. One algorithm is intended to determine the minimum subset of objectives that yields the minimum error possible, while the other finds a subset of objectives of a given size that yields the minimum error. To validate these algorithms we compare their results against those obtained by two similar algorithms recently proposed. The comparative study shows that our algorithms are very competitive with respect to the reference algorithms. Additionally, our approaches require a lower computational time. Also, in this study we propose to use the inverted generational distance to evaluate the quality of a subset of objectives.

REFERENCES

• 1: P. J. Bentley and J. P. Wakefield. Finding Acceptable Solutions in the Pareto-Optimal Range using Multiobjective Genetic Algorithms. In P. K. Chawdhry, R. Roy, and R. K. Pant, editors, Soft Computing in Engineering Design and Manufacturing, Part 5, pages 231--240, London, June 1997. Springer Verlag London Limited. (Presented at the 2nd On-line World Conference on Soft Computing in Design and Manufacturing (WSC2)).
• 2: D. Brockhoff and E. Zitzler. Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization. In Parallel Problem Solving from Nature IX, pages 533--542. Springer-Verlag, 2006.
• 3: D. Brockhoff and E. Zitzler. Offline and Online Objective Reduction in Evolutionary Multiobjective Optimization Based on Objective Conflicts. TIK Report 269, Institut für Technische Informatik und Kommunikationsnetze, ETH Zürich, Apr. 2007.
• 4: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Kalyanmoy Deb , Samir Agrawal , Amrit Pratap , T. Meyarivan, A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.849-858, September 18-20, 2000
• 6: K. Deb and D. K. Saxena. Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In 2006 IEEE Congress on Evolutionary Computation (CEC'2006), pages 3353--3360, Vancouver, BC, Canada, July 2006. IEEE.
• 7: F. di Pierro. Many-Objective Evolutionary Algorithms and Applications to Water Resources Engineering. PhD thesis, School of Engineering, Computer Science and Mathematics, UK, August 2006.
• 8: M. Farina and P. Amato. On the Optimal Solution Definition for Many-criteria Optimization Problems. In Proceedings of the NAFIPS-FLINT International Conference'2002, pages 233--238, Piscataway, New Jersey, June 2002. IEEE Service Center.
• 9: E. J. Hughes. Evolutionary Many-Objective Optimisation: Many Once or One Many? In 2005 IEEE Congress on Evolutionary Computation (CEC'2005), volume 1, pages 222--227, Edinburgh, Scotland, September 2005. IEEE Service Center.
• 10: V. Khare. Performance Scaling of Multi-Objective Evolutionary Algorithms. Master's thesis, School of Computer Science, The University of Birmingham, Edgbaston, Birmingan, UK, September 2002.
• 11: Pabitra Mitra , C. A. Murthy , Sankar K. Pal, Unsupervised Feature Selection Using Feature Similarity, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.301-312, March 2002 [doi>10.1109/34.990133]
• 12: A. Sülflow, N. Drechsler, and R. Drechsler. Robust Multi-objective Optimization in High Dimensional Spaces. In S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, and T. Murata, editors, Evolutionary Multi-Criterion Optimization, 4th International Conference, EMO 2007, pages 715--726, Matshushima, Japan, March 2007. Springer. Lecture Notes in Computer Science Vol. 4403.
• 13: David Allen Van Veldhuizen , Gary B. Lamont, Multiobjective evolutionary algorithms: classifications, analyses, and new innovations, Air Force Institute of Technology, Wright Patterson AFB, OH, 1999
• 14: T. Wagner, N. Beume, and B. Naujoks. Pareto-, Aggregation-, and Indicator-Based Methods in Many-Objective Optimization. In S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, and T. Murata, editors, Evolutionary Multi-Criterion Optimization, 4th International Conference, EMO 2007, pages 742--756, Matshushima, Japan, March 2007. Springer. Lecture Notes in Computer Science Vol. 4403.
• 15: Eckart Zitzler , Lothar Thiele, Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.292-304, September 27-30, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
feature selection, many-objective problems, multiobjective optimization, nonessential objectives, objective reduction