Ağaç Tabanlı Genetik Programlama (Tree-Based Genetic Programming, GP), genetik algoritmaların bir alt kümesidir ve evrimsel hesaplamanın bir formudur. GP'nin amacı, bir problemi çözmek için belirli bir ifade veya algoritmayı otomatik olarak keşfetmektir. Bir GP algoritması genellikle, popülasyonları ve genetik operatörleri (mutasyon, çaprazlama vb.) kullanarak bireysel çözümlerin bir dizi evrimsel işlemi aracılığıyla zaman içinde evrimleşmesini içerir.

Her birey, bir problemin çözümünü temsil eden bir ifade ağacı olarak temsil edilir. Bu ifade ağaçları, aritmetik işlemler, lojik işlemler, fonksiyonlar, kontrol yapıları ve daha fazlası gibi çeşitli işlemler ve işlevler içerebilir. GP'nin gücü, çözüm arayışında kullanılabilecek karmaşık ve değişken yapıları keşfedebilmesidir.

Aşağıda, basit bir ağaç tabanlı genetik programlama örneği verilmiştir. Bu örnekte, DEAP (Distributed Evolutionary Algorithms in Python) kütüphanesi kullanılmıştır ve sembolik regresyon problemi çözülmüştür. DEAP, genetik algoritmalar ve evrimsel stratejiler de dahil olmak üzere bir dizi evrimsel algoritmayı destekler.

import operator
import random
import math
import numpy

from deap import algorithms
from deap import base
from deap import creator
from deap import tools
from deap import gp

# Define new functions
def protectedDiv(left, right):
    try:
        return left / right
    except ZeroDivisionError:
        return 1

pset = gp.PrimitiveSet("MAIN", 1)
pset.addPrimitive(operator.add, 2)
pset.addPrimitive(operator.sub, 2)
pset.addPrimitive(operator.mul, 2)
pset.addPrimitive(protectedDiv, 2)
pset.addPrimitive(operator.neg, 1)
pset.addPrimitive(math.cos, 1)
pset.addPrimitive(math.sin, 1)
pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
pset.renameArguments(ARG0='x')

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("compile", gp.compile, pset=pset)

def evalSymbReg(individual, points):
    func = toolbox.compile(expr=individual)
    sqerrors = ((func(x) - x**2)**2 for x in points)
    return math.fsum(sqerrors) / len(points),

toolbox.register("evaluate", evalSymbReg, points=[x/10. for x in range(-10,10)])
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)

toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))
toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))

def main():
    random.seed(318)

    pop = toolbox.population(n=300)
    hof = tools.HallOfFame(1)

    stats_fit = tools.Statistics(lambda ind: ind.fitness.values)
    stats_size = tools.Statistics(len)
    mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)
    mstats.register("avg", numpy.mean)
    mstats.register("std", numpy.std)
    mstats.register("min", numpy.min)
    mstats.register("max", numpy.max)

    pop, log = algorithms.eaSimple(pop, toolbox, 0.5, 0.1, 40, stats=mstats,
                                   halloffame=hof, verbose=True)
    return pop, log, hof

if __name__ == "__main__":
    main()

Bu örnekte, verilen x değerlerine karşılık gelen y = x^2 fonksiyonunu bulmayı hedefliyoruz. Sembolik regresyon problemi, bir dizi giriş-veri çifti (x, y) verildiğinde y verilerini üreten en uygun formülü bulmaya çalışır. GP, bu formülü keşfetmek için kullanılır. Bu kod, belirli bir x veri setinde y = x^2 fonksiyonunu keşfetmeye çalışır. Algoritma, formülün bu hedefe ne kadar yakın olduğunu ölçer ve daha iyi bir çözüm bulmak için ağaçları evrimleştirmeye devam eder. Bu örnekte ayrıca bireylerin ağaç boyutlarının 17 düğümle sınırlı olduğunu belirttik.

Programın çalışması sonucunda her iterasyon (nesil) için belirli istatistikler alınır. Bunlar şunları içerir:

avg: Popülasyonun ortalama uygunluğunu gösterir. İdealde, bu değer iterasyonlar boyunca azalmalıdır, çünkü bu bir minimizasyon problemidir ve daha düşük uygunluk skorları genellikle daha iyi çözümlere işaret eder.

std: Popülasyonun uygunluk skorlarının standart sapmasını gösterir. Bu, popülasyondaki çeşitliliği gösterir. Çok yüksek bir standart sapma değeri, popülasyondaki bireylerin uygunluk seviyelerinde büyük bir çeşitlilik olduğunu gösterir. Genellikle bu, popülasyonun geniş bir çözüm alanını araştırdığı anlamına gelir.

min: Popülasyondaki en düşük uygunluk skorunu gösterir. Bu, şimdiye kadar bulunan en iyi çözümün uygunluğunu gösterir. İterasyonlar boyunca bu sayının düşmesi beklenir.

max: Popülasyondaki en yüksek uygunluk skorunu gösterir. Bu, şimdiye kadar bulunan en kötü çözümün uygunluğunu gösterir.

Programın çıktılarına bakarak, genetik programlamanın belirli bir nesil boyunca nasıl performans gösterdiğini ve hangi yönde ilerlediğini anlayabiliriz.

Sonuç olarak, genel olarak uygunluk skorlarının (ortalama ve minimum) azaldığını ve popülasyon çeşitliliğinin (standart sapma) zamanla değiştiğini görmeyi bekleriz. Bu, genetik algoritmanın belirli bir nesil boyunca hedefe doğru ilerlediğini ve yeni ve potansiyel olarak daha iyi çözümler üretmek için popülasyonu evrimleştirdiğini gösterir.

Sonuçların her durumda böyle olacağını garantileyemeyiz çünkü genetik algoritmalar rastgeleliklere dayanır ve bu nedenle her çalıştırma farklı sonuçlar üretebilir. Ancak genel trend, daha iyi bir çözüm arayışında genellikle bu yönde ilerlemektir.