-- parent script "GP"
-- max allowed program tree depth
property MAX_DEPTH
-- fixed overall population size
property POPULATION
-- number of best fitting solutions that survive per generation
property SURVIVORS
-- propability that a node mutates in a generation cycle
property PROP_NODE_CHANGE
-- propability that in random programs a node is a function
property PROP_FUNC
-- propability that in random programs a node - if it's not a function - is a param node
property PROP_PARAM
-- lower and upper limit for constant node values
property MIN_CONST
property MAX_CONST
property _arity
property _funcs
property _dataSet
----------------------------------------
-- @constructor
-- @param {integer} arity - number of input arguments of the generated program
-- @param {propList} [params]
----------------------------------------
on new (me, arity, params)
the randomSeed = _system.milliseconds
-- params (arbitrary defaults)
me.MAX_DEPTH = 5
me.POPULATION = 100
me.SURVIVORS = 10
me.PROP_NODE_CHANGE = 0.2
me.PROP_FUNC = 0.5
me.PROP_PARAM = 0.6 -- 1.0 = no constants at all
me.MIN_CONST = 1
me.MAX_CONST = 10
if ilk(params)=#propList then
repeat with i = 1 to params.count
me.setProp(params.getPropAt(i), params[i])
end repeat
end if
me._funcs = [:]
me._arity = arity
return me
end
----------------------------------------
-- Changes a config parameter.
-- @param {symbol} prop
-- @param {any} val
----------------------------------------
on setParam (me, prop, val)
me.setProp(prop, val)
end
----------------------------------------
-- Adds a function to the list of used elementary functions ("genes").
-- @param {string} name
-- @param {integer} arity - number of arguments of the specified function
-- @param {string} code
----------------------------------------
on addFunction (me, name, arity, code)
me._funcs[name] = [#name:name, #arity:arity, #code:code]
end
----------------------------------------
-- Sets the dataset that is used for validating the results.
-- Each element of list <dataSet> must be a list in the form [[list of <me._arity> args], <result value>].
-- @param {list} dataSet
----------------------------------------
on setDataSet (me, dataSet)
me._dataSet = dataSet
end
----------------------------------------
-- Starts the "loop of live". If no 'maxGenerations' argument is specified,
-- the loop will run until it finds a perfect solution (or forever, if there is none).
-- @param {integer} [maxGenerations=0]
-- @return {instance} prog - Either a perfect program or the best found within 'maxGenerations'
----------------------------------------
on run (me, maxGenerations)
if voidP(maxGenerations) then maxGenerations = 0
genCnt = 0
bestDiff = the maxinteger
bestProg = VOID
-- create the first random generation
generation = []
repeat with i = 1 to me.POPULATION
prog = me._makeRandomProg()
generation[i] = prog
end repeat
-- loop of live :-)
repeat while TRUE
put "--------------------"
put "NEW GENERATION"
put "--------------------"
res = [:]
res.sort()
repeat with i = 1 to me.POPULATION
-- evaluate
prog = generation[i]
diff = me._evaluate(prog)
if diff<bestDiff then
bestDiff = diff
put diff
bestProg = prog
if diff=0 then
put "--------------------"
put "SOLUTION FOUND"
put "--------------------"
bestProg.print()
return bestProg
end if
end if
res.addProp(diff, prog)
end repeat
-- show the currently best
bestProg.print()
genCnt = genCnt+1
if maxGenerations and genCnt>=maxGenerations then
return bestProg
end if
-- survival of the fittest and "asexual reproduction" - no breeding yet
repeat with i = 1 to me.POPULATION
generation[i] = me._mutate(res[random(me.SURVIVORS)].clone())
end repeat
end repeat
end
----------------------------------------
-- Returns a random program (tree/node) with max. <depth> tree levels
----------------------------------------
on _makeRandomProg (me, depth)
if voidP(depth) then depth = me.MAX_DEPTH
if me._randf()<=me.PROP_FUNC and depth>0 then
-- get a random function node
f = me._funcs[random(me._funcs.count)]
c = []
repeat with i = 1 to f.arity
c[i] = me._makeRandomProg(depth-1)
end repeat
node = script("Node").new(f.name, f.arity, f.code, c)
else if me._randf()<=me.PROP_PARAM then
-- get a random param node
n = random(me._arity)
name = "param "&n
arity = 0
code = "res=arg["&n&"]"
node = script("Node").new(name, arity, code)
else
-- get a random const node (with const in between me.MIN_CONST and me.MAX_CONST)
n = random(me.MAX_CONST-me.MIN_CONST+1) + me.MIN_CONST -1
name = "const "&n
arity = 0
code = "res="&n
node = script("Node").new(name, arity, code)
end if
return node
end
----------------------------------------
-- Mutates a program (tree/node) based on propability PROP_NODE_CHANGE
----------------------------------------
on _mutate (me, prog)
if me._randf()<=me.PROP_NODE_CHANGE then
return me._makeRandomProg()
else
prog = prog.clone()
children = prog.getChildren()
repeat with i = 1 to children.count
children[i] = me._mutate(children[i])
end repeat
return prog
end if
end
----------------------------------------
-- Evaluates the fitness of a program.
-- Returns accumulated absolute differences to results in <dataSet>.
-- The smaller the return value, the better the program's fitness (0=perfect solution).
----------------------------------------
on _evaluate (me, prog)
diff = 0.0
repeat with row in me._dataSet
v = call(prog, _movie, row[1])
diff = diff + abs(row[2] - v)
end repeat
return diff
end
----------------------------------------
-- Returns a random float value in between 0 and 1
----------------------------------------
on _randf (me, n)
n = random(the maxinteger)-1
r = n / float(the maxinteger-1)
return r
end