Summary
We consider a class of optimization problems wherein the quality of candidate solutions is estimated by their performance on a number of tests. Classifier induction, function regression, and certain types of reinforcement learning, including problems often attacked with coevolutionary algorithms, can all be seen as members of this class. Traditional approaches to such test-based problems use a single objective function that aggregates the scores obtained on the tests. Recent work, by contrast, argues that useful finer-grained distinctions between candidate solutions are obtained when each test is treated as a separate objective, and that algorithms employing such multiobjective comparisons show favourable behaviour relative to those which do not. Unfortunately, the number of tests can be very large. Since it is well-known that high-dimensional multiobjective optimization problems are difficult to handle in practice, the question arises whether the multiobjective treatment of test-based problems is feasible. To begin addressing this question, we examine a method for reducing the number of dimensions without sacrificing the favorable properties of the multiobjective approach. Our method, which is a form of dimension extraction, finds underlying objectives implicit in test-based problems. Essentially, the method proceeds by placing the tests along the minimal number of coordinate axes that still preserve ordering information among the candidate solutions. Application of the method to the strategy set for several instances of the game of Nim suggest the technique has significant practical benefits: a type of compression of the set of objectives is observed in all tested instances. Surprisingly, we also find that the information contained in the arrangement of tests on the coordinate axes reveals important information about the structure of the underlying problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bouton, C. L. (1901–1902). Nim, a game with a complete mathematical theory. The Annals of Mathematics, 2nd Ser., 3(1-4):35–39.
Bucci, A. and Pollack, J. B. (2003). Focusing versus intransitivity: Geometrical aspects of coevolution. In Erick Cantú-Paz et al., editor, Genetic and Evolutionary Computation Conference - GECCO 2003, volume 2723 of Lecture Notes in Computer Science, pages 250–261. Springer.
Bucci, A. and Pollack, J. B. (2005). On identifying global optima in cooperative coevolution. In Hans-Georg Beyer et al., editor, GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 1, pages 539–544, Washington DC, USA. ACM Press.
Bucci, A., Pollack, J. B., and De Jong, E. D. (2004). Automated extraction of problem structure. In Kalyanmoy Deb et al., editor, Genetic and Evolutionary Computation Conference – GECCO 2004, volume 3102 of Lecture Notes in Computer Science, pages 501–512. Springer.
De Jong, E. and Bucci, A. (2006). DECA: Dimension extracting coevolutionary algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-06, pages 313–320.
De Jong, E. D. and Pollack, J. B. (2004). Ideal evaluation from coevolution. Evolutionary Computation, 12(2):159–192.
Deb, K. and Saxena, D. K. (2006). Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 3353–3360. IEEE Press.
Ficici, S. G. and Pollack, J. B. (2001). Pareto optimality in coevolutionary learning. In Kelemen, J. and Sosík, P., editors, Sixth European Conference on Artificial Life (ECAL 2001), pages 316–325. Springer.
Goldman, S. A. and Kearns, M. J. (1995). On the complexity of teaching. Journal of Computer and System Sciences, 50(1):20–31.
Grundy, P. M. (1939). Mathematics and games. Eureka, 2:6–8. Reprinted in Eureka 27 (1964) 9-11.
Hillis, D. W. (1990). Co-evolving Parasites Improve Simulated Evolution in an Optimization Procedure. Physica D, 42:–234.
Knowles, J. D., Watson, R. A., and Corne, D. W. (2001). Reducing Local Optima in Single-Objective Problems by Multi-objectivization. In Zitzler, E., Deb, K., Thiele, L., Coello, C. C., and Corne, D., editors, First International Conference on Evolutionary Multi-Criterion Optimization, volume 1993 of LNCS, pages 268–282. Springer, Berlin.
Noble, J. and Watson, R. A. (2001). Pareto Coevolution: Using Performance Against Coevolved Opponents in a Game as Dimensions for Pareto Selection. In L. Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pages 493–500, San Francisco, CA. Morgan Kaufmann Publishers.
Potter, M. A. and Jong, K. A. D. (2000). Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1–29.
Saxena, D. K. and Deb, K. (2007). Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: Employing correntropy and a novel maximum variance unfolding. In Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., and Murata, T., editors, Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization, volume 4403 of Lecture Notes in Computer Science, pages 772–787.
Singmaster, D. (1996). Chronology of recreational mathematics. http://anduin.eldar.org/problemi/singmast/recchron.html.
Sprague, R. P. (1935–1936). Über mathematische kampfspiele. Tôhoku Mathematical Journal, 41:–444.
Watson, R. and Pollack, J. B. (2001). Coevolutionary dynamics in a minimal substrate. In L. Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, San Francisco, CA. Morgan Kaufmann Publishers.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jong, E.D.d., Bucci, A. (2008). Objective Set Compression. In: Knowles, J., Corne, D., Deb, K. (eds) Multiobjective Problem Solving from Nature. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72964-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-72964-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72963-1
Online ISBN: 978-3-540-72964-8
eBook Packages: Computer ScienceComputer Science (R0)