An Algebra of Pareto Points

• Autorzy: Geilen M. , Basten T. , Theelen B. , Otten R.
• Języki publikacji: EN

Abstrakty

EN

Multi-criteria optimisation problems occur naturally in many engineering practices. Pareto analysis has proven to be a powerful tool to characterise potentially interesting realisations of a particular engineering problem. It is therefore used frequently for design-space exploration problems. Depending on the optimisation goals, one of the Pareto-optimal alternatives will be the optimal realisation. It often happens however, that partial design decisions have to be taken, leaving other aspects of the optimisation problem to be decided at a later stage, and that Pareto-optimal configurations have to be composed (dynamically) from Pareto-optimal configurations of components. These aspects are not supported by current analysis methods. This paper introduces a novel, algebraic approach to Pareto analysis. The approach is particularly designed to allow for describing incremental design decisions and composing sets of Pareto-optimal configurations. The algebra can be used to study the operations on Pareto sets and the efficient computation of Pareto sets and their compositions. The algebra is illustrated with a case-study based on transmitting an MPEG-4 video stream from a server to a hand-held device.

Słowa kluczowe

EN

Pareto points

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 1
• Strony: 35--74
• Opis fizyczny: bibliogr. 21 poz., tab., wykr.

Twórcy

autor

Geilen M.

autor

Basten T.

autor

Theelen B.

autor

Otten R.

• Information Systems Group, Department of Electrical Engineering, Eindhoven University of Technology, P.O.Box 513, 5600 MB Eindhoven, The Netherlands,

Bibliografia

• [1] Baykasoglu, A., Owen, S., Gindy, N.: A Taboo Search Based Approach to Find the Pareto Optimal Set in Multiple Objective Optimisation, Journ. of Engin. Optimization, 31, 1999, 731-748.
• [2] Bentley, J.: Multidimensional Divide-and-Conquer, Communications of the ACM, 23(4), April 1980, 214-229.
• [3] Blanch, C., de Groot, H., v.d. Stok, P.: Deliverable D1c: Inventory of Competing Video Codecs and a Selection of Codecs, Technical report, IST-004042 project Betsy, February 2005, http://www.hitech-projects.com/euprojects/betsy/results.htm.
• [4] Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, New York, 2001.
• [5] Ehrgott, M., Gandibleux, X.: An Annotated Bibliography of Multi-objective Combinatorial Optimization, Technical Report 62/2000, Fachbereich Mathematik, Universit¨at Kaiserslautern, Kaiserslautern, Germany, 2000.
• [6] Finkel, R., Bentley, J.: Quad Trees: A Data Structure for Retrieval on Composite Keys, Acta Inf., 4, 1974, 1-9.
• [7] Geilen,M., Basten, T., Theelen, B., Otten, R.: An Algebra of Pareto Points, Proc. Application of Concurrency to System Design, 5th International Conference, ACSD 2005, IEEE Computer Society Press, Los Alamitos, CA, USA, 2005.
• [8] Givargis, T., Vahid, F., Henkel, J.: System-Level Exploration for Pareto-optimal Configurations in Parameterized System-on-a-Chip, IEEE Trans. VLSI Syst., 10(4), August 2002, 416-422.
• [9] Glover, F.: Tabu Search: A Tutorial, Interfaces, 20(4), 1990, 74-94.
• [10] Gries, M.: Methods for Evaluating and Covering the Design Space during Early Design Development, Integration, the VLSI Journal, 38(2), 2004, 131-183.
• [11] Kung, H. T., Luccio, F., Preparata, F. P.: On Finding the Maxima of a Set of Vectors, Journal of the ACM, 22(4), 1975, 469-476.
• [12] Mattson, C., Mullur, A., Messac, A.: Minimal Representation ofMultiobjective Design Space Using a Smart Pareto Filter, Proc. 9th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, 2002.
• [13] Pareto, V.: Manuale di Economia Politica, Piccola Biblioteca Scientifica, Milan, 1906, Translated into English by Ann S. Schwier (1971),Manual of Political Economy,MacMillan, London.
• [14] Sun, M., Steuer, R. E.: Quad-Trees and Linear Lists for Identifying Nondominated Criterion Vectors, ORSA Journal on Computing, 8(4), 1996, 367-375.
• [15] Szymanek, R., Catthoor, F., Kuchcinski, K.: Time-Energy Design Space Exploration for Multi-Layer Memory Architectures., Proc. Design Automation and Test in Europe (DATE) 2004, IEEE, 2004.
• [16] Thoen, F., Catthoor, F.: Modeling, Verification and Exploration of Task-Level Concurrency in Real-Time Embedded Systems, Kluwer, 2000.
• [17] Voorneveld, M.: Characterization of Pareto Dominance, Operations Research Letters, 31(1), January 2003, 7-11.
• [18] Yang, P., Catthoor, F.: Pareto-Optimization-Based Run-Time Task Scheduling for Embedded Systems., Proc. Int. Conf. On Hardware/Software Codesign and System Synthesis (CODES+ISSS) 2003, ACM, 2003.
• [19] Yukish,M.: Algorithms to Identify Pareto Points inMulti-DimensionalData Sets, Ph.D. Thesis, Pennsylvania State University, August 2004.
• [20] Zitzler, E., Thiele, L.: Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Trans. on Evolutionary Computation, 3(4), November 1999, 257-271.
• [21] Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C., Fonseca, V. G. D.: Performance Assessment of Multiobjective Optimizers: An Analysis and Review, IEEE Trans. on Evolutionary Computation, 7(2), April 2003, 117-132.