Thoughts on solution concepts

ABSTRACT

This paper explores connections between Ficici's notion of solution concept and order theory. Ficici postulates that algorithms should ascend an order called weak preference; thus, understanding this order is important to questions of designing algorithms. We observe that the weak preference order is closely related to the pullback of the so-called lower ordering on subsets of an ordered set. The latter can, in turn, be represented as the pullback of the subset ordering of a certain powerset. Taken together, these two observations represent the weak preference ordering in a more simple and concrete form as a subset ordering. We utilize this representation to show that algorithms which ascend the weak preference ordering are vulnerable to a kind of bloating problem. Since this kind of bloat has been observed several times in practice, we hypothesize that ascending weak preference may be the cause. Finally, we show that monotonic solution concepts are convex in the order-theoretic sense. We conclude by speculating that monotonic solution concepts might be derivable from non-monotonic ones by taking convex hull. Since several intuitive solution concepts like average fitness are not monotonic, there is practical value in creating monotonic solution concepts from non-monotonic ones.

REFERENCES

• 1: Michael Barr , Charles Wells, Category theory for computing science, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: A. Bucci and J. B. Pollack. A Mathematical Framework for the Study of Coevolution. In K. De Jong, R. Poli, and J. Rowe, editors, FOGA 7: Proceedings of the Foundations of Genetic Algorithms Workshop, pages 221--235, San Francisco, CA, 2003. Morgan Kaufmann Publishers.
• 3: E. D. De Jong. Towards a Bounded Pareto-Coevolution Archive. In Proceedings of the Congress on Evolutionary Computation CEC'2004, volume 2, pages 2341--2348. IEEE Service Center, 2004.
• 4: Edwin D. De Jong , Jordan B. Pollack, Ideal Evaluation from Coevolution, Evolutionary Computation, v.12 n.2, p.159-192, June 2004 [doi>10.1162/106365604773955139]
• 5: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, Brandeis University, Waltham, MA, 2004
• 6: Sevan G. Ficici , Jordan B. Pollack, Pareto Optimality in Coevolutionary Learning, Proceedings of the 6th European Conference on Advances in Artificial Life, p.316-325, September 10-14, 2001
• 7: C. M. Fonseca and P. J. Fleming. An Overview of Evolutionary Algorithms in Multiobjective Optimization. Evolutionary Computation, 3(1):1--16, 1995.
• 8: W. Daniel Hillis, Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, v.42 n.1-3, p.228-234, June 1990
• 9: German A. Monroy , Kenneth O. Stanley , Risto Miikkulainen, Coevolution of neural networks using a layered pareto archive, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144058]
• 10: J. Noble and R. A. Watson. 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, 2001. Morgan Kaufmann Publishers.
• 11: Mitchell A. Potter , Kenneth A. De Jong, A Cooperative Coevolutionary Approach to Function Optimization, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.249-257, October 09-14, 1994
• 12: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 13: Edward R. Scheinerman, Mathematics: A Discrete Introduction, Brooks/Cole Publishing Co., Pacific Grove, CA, 2000
• 14: K. Sims. Evolving 3D Morphology and Behavior by Competition. In R. Brooks and P. Maes, editors, Artificial Life IV, pages 28--39, Cambridge, MA, 1994. The MIT Press.
• 15: P. Taylor. Practical Foundations of Mathematics. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, UK, 1st edition, 1999.
• 16: Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1998
• 17: Rudolf Paul Wiegand , Kenneth A. Jong, An analysis of cooperative coevolutionary algorithms, George Mason University, Fairfax, VA, 2004

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, Theory

Keywords:
bloat, coevolution, coevolutionary algorithm, later is better, pareto coevolution, solution concepts