regress.py

#!/usr/local/bin/python3

# can run a regresion on a set of points

from collections import namedtuple
from random import random, choice

identity = lambda x: x
average = lambda values, key=identity: sum(key(value) for value in values) / len(values)
median = lambda values, key=identity: sorted(values, key=key)[len(values) // 2] # close enough

# points are declared here
Point = namedtuple("Point", ["x", "y"])
points = [
    Point(10, 10),
    Point(11, 12),
    Point(12, 14),
    Point(13, 16),
]
n = 1 # degree e.g. 0 for constant, 1 for linear, 2 for quadratic, etc.

# survivability is a probability in [0, 1) that says if an organism will survive a generation
class Regresion:
    # linear follows: [m, b]
    # quadratic follows: [a, b, c]
    # etc.
    def __init__(self, coefficients):
        self.coefficients = coefficients

        # the indexes of the powers are in the wrong order
        # normally, the front coefficient should have a power of N, but here it has an index of 0
        # thus, it has a power of 0
        # we flip the order so that the first element (the constant) has an index & power of 0
        self.coefficients.reverse()

        self.survivability = self.r_squared()
        self.coefficients.reverse() # put it back now

    def __getitem__(self, x):
        return sum(coefficient * x ** n for n, coefficient in enumerate(self.coefficients))

    def r_squared(self):
        mean_y = average(points, key=lambda point: point.y)
        ssres = sum((point.y - self[point.x]) ** 2 for point in points)
        sstot = sum((point.y - mean_y) ** 2 for point in points)
        return 1 - ssres / sstot

    def __repr__(self):
        string = ""
        for index, coefficient in enumerate(self.coefficients):
            coef = None
            if coefficient == 0:
                continue
            elif coefficient == 1:
                coef = ""
            elif coefficient == -1:
                coef = "-"
            else:
                coef = str(coefficient)

            n = len(self.coefficients) - index - 1
            power = "" if n == 0 or n == 1 else str(n)

            string += coef
            if n != 0:
                string += "x"
            if power != "":
                string += "^" + power

            if index != len(self.coefficients) - 1: # if not the last
                string += " + "
        return string

generation = []
initial_population = 10
number_of_generations = 1000
for _ in range(initial_population):
    generation.append(Regresion([0 for _ in range(n + 1)]))

# all organisms are hermaphrodites
def breed(father, mother):
    assert len(father.coefficients) == len(father.coefficients)
    n = len(father.coefficients)
    coefficient_at = lambda i: average([father.coefficients[i], mother.coefficients[i]])
    mutation = lambda coeff: 10 ** (random() - 0.5) * coeff + (random() - 0.5)
    coefficients = [mutation(coefficient_at(i)) for i in range(n)]
    return Regresion(coefficients)

for n in range(number_of_generations):
    # kill off some organisms
    median_survival = median(generation, key=lambda organism: organism.survivability).survivability
    generation = [organism for organism in generation if organism.survivability >= median_survival]

    # now breed them to make some more organisms
    children = []
    for organism in generation:
        partner = choice(generation)
        children.append(breed(organism, partner))
    generation += children

best = max(generation, key=lambda org: org.survivability)
coefficients = [int((coeff * 10000)+0.5) / 10000 for coeff in best.coefficients]
print("Regressed to:", Regresion(coefficients))