Research Article
BibTex RIS Cite

Estimating the difficulty of Tartarus instances

Year 2021, Volume: 27 Issue: 2, 114 - 121, 04.04.2021

Abstract

Tartarus is a commonly used benchmark problem for genetic programming. However, it has never been fully explored for its difficulty tuning property. Using the data from a previous study in which we have executed millions of Tartarus instances, we contribute to the literature with an equation to estimate their difficulty. Our approach uses four metrics that are embedded into the equation. These metrics are related to the number of clusters and clusters sizes, the distances of boxes to the edges of the board grid, the number of boxes around the agent, and the minimum number of actions for the agent to reach the largest cluster. The coefficients of these metrics have been fit to the data using the general linear model and a mean residual error of ~0.1 has been achieved. This is the first study that can estimate the difficulty of a Tartarus board without modifying the problem in any way.

References

  • [1] Teller A. The Evolution of Mental Models. Editors: Kinnear Jr KE. Advances in Genetic Programming, 199-217, Cambridge MA, USA, MIT Press, 1994.
  • [2] Griffiths TD, Ekárt A. Improving the Tartarus Problem as a Benchmark in Genetic Programming. Editors: McDermott J, Castelli M, Sekanina L, Haasdijk E, García-Sánchez P. Genetic Programming, 278-293, Cham, Springer, 2017.
  • [3] Ashlock D, Willson S, Leahy N. “Coevolution and Tartarus”. Proceedings of the 2004 Congress on Evolutionary Computation, Portland, OR, USA, 19-23 June 2004.
  • [4] McDermott J, White DR, Luke S, Manzoni L, Castelli M, Vanneschi L, Jaskowski W, Krawiec K, Harper R, De Jong KA, O'Reilly UM. “Genetic programming needs better benchmarks”. GECCO '12: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, Philadelphia, USA, 07-11 July 2012.
  • [5] Oğuz K. “True scores for Tartarus with adaptive GAs that evolve FSMs on GPU”. Information Sciences, 525, 1-15, 2020.
  • [6] Dick G. “A true finite-state baseline for Tartarus”. GECCO '13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Amsterdam, Netherlands, 6-10 July 2013.
  • [7] Ashlock D, Freeman J. “A pure finite state baseline for Tartarus”. Proceedings of the 2000 Congress on Evolutionary Computation, La Jolla, CA, USA, 16-19 July 2000.
  • [8] Ashlock D, Warner E. “The geometry of Tartarus fitness cases”. 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), Hong Kong, China, 1-6 June 2008.
  • [9] Dick G. “An effective parse tree representation for Tartarus”. GECCO '13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Amsterdam, Netherlands, 6-10 July 2013.
  • [10] Mardia K, Kent J, Bibby J. Multivariate Analysis. 1st ed. London, UK, Academic Press, 1979.

Tartarus örneklerinin zorluklarının tahminlenmesi

Year 2021, Volume: 27 Issue: 2, 114 - 121, 04.04.2021

Abstract

Tartarus genetik programlamada sıkça kullanılan bir kıyaslama problemidir. Fakat zorluk ayarı özelliği henüz tam olarak araştırılmamıştır. Literatüre milyonlarca Tartarus örneği çalıştırdığımız önceki bir çalışmanın verilerini kullanarak zorluklarını tahmin edebilen bir denklemle katkıda bulunuyoruz. Yaklaşımımız denklemin içinde yer alan dört yeni metrik kullanıyor. Bu metrikler küme sayıları ve büyüklüklerine, kutuların kenarlardan uzaklığına, yazılım etmeninin etrafındaki kutuların sayısına ve etmenin en büyük kümeye varması için gereken hareket sayısına bağlıdır. Metriklerin katsayıları veriye genel doğrusal model ile uyarlanmış ve ortalama ~0.1 kadar bir hata başarısına ulaşılmıştır. Bu çalışma Tartarus probleminde bir değişiklik yapmadan problemin zorluğunu tahmin edebilen ilk çalışmadır.

References

  • [1] Teller A. The Evolution of Mental Models. Editors: Kinnear Jr KE. Advances in Genetic Programming, 199-217, Cambridge MA, USA, MIT Press, 1994.
  • [2] Griffiths TD, Ekárt A. Improving the Tartarus Problem as a Benchmark in Genetic Programming. Editors: McDermott J, Castelli M, Sekanina L, Haasdijk E, García-Sánchez P. Genetic Programming, 278-293, Cham, Springer, 2017.
  • [3] Ashlock D, Willson S, Leahy N. “Coevolution and Tartarus”. Proceedings of the 2004 Congress on Evolutionary Computation, Portland, OR, USA, 19-23 June 2004.
  • [4] McDermott J, White DR, Luke S, Manzoni L, Castelli M, Vanneschi L, Jaskowski W, Krawiec K, Harper R, De Jong KA, O'Reilly UM. “Genetic programming needs better benchmarks”. GECCO '12: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, Philadelphia, USA, 07-11 July 2012.
  • [5] Oğuz K. “True scores for Tartarus with adaptive GAs that evolve FSMs on GPU”. Information Sciences, 525, 1-15, 2020.
  • [6] Dick G. “A true finite-state baseline for Tartarus”. GECCO '13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Amsterdam, Netherlands, 6-10 July 2013.
  • [7] Ashlock D, Freeman J. “A pure finite state baseline for Tartarus”. Proceedings of the 2000 Congress on Evolutionary Computation, La Jolla, CA, USA, 16-19 July 2000.
  • [8] Ashlock D, Warner E. “The geometry of Tartarus fitness cases”. 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), Hong Kong, China, 1-6 June 2008.
  • [9] Dick G. “An effective parse tree representation for Tartarus”. GECCO '13: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Amsterdam, Netherlands, 6-10 July 2013.
  • [10] Mardia K, Kent J, Bibby J. Multivariate Analysis. 1st ed. London, UK, Academic Press, 1979.
There are 10 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Research Article
Authors

Kaya Oğuz

Publication Date April 4, 2021
Published in Issue Year 2021 Volume: 27 Issue: 2

Cite

APA Oğuz, K. (2021). Estimating the difficulty of Tartarus instances. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 27(2), 114-121.
AMA Oğuz K. Estimating the difficulty of Tartarus instances. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. April 2021;27(2):114-121.
Chicago Oğuz, Kaya. “Estimating the Difficulty of Tartarus Instances”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 27, no. 2 (April 2021): 114-21.
EndNote Oğuz K (April 1, 2021) Estimating the difficulty of Tartarus instances. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 27 2 114–121.
IEEE K. Oğuz, “Estimating the difficulty of Tartarus instances”, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, vol. 27, no. 2, pp. 114–121, 2021.
ISNAD Oğuz, Kaya. “Estimating the Difficulty of Tartarus Instances”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 27/2 (April 2021), 114-121.
JAMA Oğuz K. Estimating the difficulty of Tartarus instances. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2021;27:114–121.
MLA Oğuz, Kaya. “Estimating the Difficulty of Tartarus Instances”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, vol. 27, no. 2, 2021, pp. 114-21.
Vancouver Oğuz K. Estimating the difficulty of Tartarus instances. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2021;27(2):114-21.

ESCI_LOGO.png    image001.gif    image002.gif        image003.gif     image004.gif