E-ISSN: 2587-0351 | ISSN: 1300-2694
Estimating the difficulty of Tartarus instances [Pamukkale Univ Muh Bilim Derg]
Pamukkale Univ Muh Bilim Derg. Ahead of Print: PAJES-00515 | DOI: 10.5505/pajes.2020.00515

Estimating the difficulty of Tartarus instances

Kaya Oğuz
Izmir University of Economics

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.

Keywords: Tartarus problem, difficulty estimation, general linear model

Tartarus örneklerinin zorluklarının tahminlenmesi

Kaya Oğuz
İzmir Ekonomi Üniversitesi

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.

Anahtar Kelimeler: Tartarus problemi, zorluk tahmini, genel doğrusal model



Corresponding Author: Kaya Oğuz, Türkiye
LookUs & Online Makale