Skip to content

Instantly share code, notes, and snippets.

@valtih1978

valtih1978/1.sequence_generator.py

Last active September 17, 2017 08:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save valtih1978/c55a1cb4a757a6150744 to your computer and use it in GitHub Desktop.
Save valtih1978/c55a1cb4a757a6150744 to your computer and use it in GitHub Desktop.
Download ZIP
Sequence Generator - generates some C (or Java?) programs
Raw
1.sequence_generator.py
# There were multiple goals: to implement AI for my game, to inject bugs ino VHDL and prove that sexual demorphims
# where boys have much higher mutation rate ' Сперматозоидов у мужчины за всю его жизнь вырабатывается гораздо больше, чем яйцеклеток у женщины. Это значит, что предшественники мужских половых клеток делятся гораздо интенсивнее и, следовательно, у них больше риск возникновения мутаций.'
#, is advantageous.
# Inspired by http://eli.thegreenplace.net/2010/01/28/generating-random-sentences-from-a-context-free-grammar
from collections import defaultdict
import random
def weighted_choice(weights):
rnd = random.random() * sum(weights)
for i, w in enumerate(weights):
rnd -= w
if rnd < 0:
return i
def rnd(prefix, high):
return prefix + str(int(random.random()*high)) + ' '
class CFG(object):
def __init__(self):
self.prod = defaultdict(list)
indent = ''
for_scope = 0
def add_prod(self, lhs, rhs):
""" Add production to the grammar. 'rhs' can
be several productions separated by '|'.
Each production is a sequence of symbols
separated by whitespace.
Usage:
grammar.add_prod('NT', 'VP PP')
grammar.add_prod('Digit', '1|2|3|4')
"""
prods = rhs.split('|')
for prod in prods:
self.prod[lhs].append(tuple(prod.split()))
def gen_random_convergent(self,
symbol,
cfactor=0.25,
pcount=defaultdict(int)
):
""" Generate a random sentence from the
grammar, starting with the given symbol.
Uses a convergent algorithm - productions
that have already appeared in the
derivation on each branch have a smaller
chance to be selected.
cfactor - controls how tight the
convergence is. 0 < cfactor < 1.0
pcount is used internally by the
recursive calls to pass on the
productions that have been used in the
branch.
"""
global indent
sentence = ''
# The possible productions of this symbol are weighted
# by their appearance in the branch that has led to this
# symbol in the derivation
#
weights = []
for prod in self.prod[symbol]:
if prod in pcount:
weights.append(cfactor ** (pcount[prod]))
else:
weights.append(1.0)
rand_prod = self.prod[symbol][weighted_choice(weights)]
def body():
sentence = '{\n'
self.indent += ' '
for i in range (1 + int(random.random()*10)):
sentence += self.indent + self.gen_random_convergent(
'statement', cfactor, pcount) + ';\n'
self.indent = self.indent[1:]
sentence += self.indent + '}'
return sentence
# pcount is a single object (created in the first call to
# this method) that's being passed around into recursive
# calls to count how many times productions have been
# used.
# Before recursive calls the count is updated, and after
# the sentence for this call is ready, it is rolled-back
# to avoid modifying the parent's pcount.
#
pcount[rand_prod] += 1
#print " rand_prod = " + str(rand_prod)
for sym in rand_prod:
# for non-terminals, recurse
if sym == 'num':
sentence += rnd('', 10000)
elif sym == 'for':
name = 'i' + str(self.for_scope)
l = name,
high = rnd('', 100)#self.gen_random_convergent('arith')
self.prod['arith'].append(l)
bool = self.gen_random_convergent('bool')
breakSt = 'if( '+bool+' ) break',
if (self.for_scope == 0): self.prod['statement'].append(breakSt)
self.for_scope += 1
sentence += "for (int {0} = 0 ; {0} != {1} ; {0}++) ".format(name, high) + body()
self.for_scope -= 1
self.prod['arith'].remove(l)
if (self.for_scope == 0): self.prod['statement'].remove(breakSt)
elif sym == 'body':
sentence += body()
elif sym == 'arith_reg':
sentence += rnd('r', 32)
elif sym == 'bool_reg':
sentence += rnd('b', 32)
elif sym in self.prod:
sentence += self.gen_random_convergent(
sym, cfactor, pcount)
else:
sentence += sym + ' '
# backtracking: clear the modification to pcount
pcount[rand_prod] -= 1
return sentence
cfg2 = CFG()
cfg2.add_prod('main', 'body')
cfg2.add_prod('statement', 'if | assign | setMem | while( bool ) body | for ')
cfg2.add_prod('if', 'if( bool ) body')
cfg2.add_prod('assign', 'arith_reg = arith | bool_reg = bool')
cfg2.add_prod('setMem', 'mem[ arith ] = arith')
cfg2.add_prod('getMem', 'mem[ arith ]')
cfg2.add_prod('arith', ' 0 | 1 | (-1) | num | arith_reg | getMem | arith + arith | arith - arith') #| arith * arith')
cfg2.add_prod('bool', 'true | false | bool_reg | ( bool or bool ) | ( bool and bool ) | ( arith > arith ) | ( arith == arith ) ')
print str(int())
print cfg2.gen_random_convergent('main')
Raw
2.prog_gen.sc
// Scala is less perspecitve, IMO since it prohibits dynamic class generation. Yet we need
// real tree of class instances (genetic representation) rather simple phenotype for evolution.
// On the other hand, Scala allows to define types, which can be useful for describing
// syntax right in Scala.
// Here is an outline of simple, not converting entence generator
object ProgGenSketch {
val grammar = Map(
"S" -> "void main() body",
"statement" -> "println( int ) | println( int ) | if ( bool ) body",
"int" -> "byte-literal | byte-literal | int int",
"bool" -> "true | false | true | false | not bool | bool and bool | bool or bool | int > int | int == int"
// Parse into LHS => List[List[String]], where RHS is list of alternaitves
// and every alternative is a seq of tokens
).mapValues(_.split('|').map(alternative => alternative.trim.split("\\s+")))
//> grammar : scala.collection.immutable.Map[String,Array[Array[String]]] = Ma
//| p(S -> Array(Array(void, main(), body)), statement -> Array(Array(println(,
//| int, )), Array(println(, int, )), Array(if, (, bool, ), body)), int -> Arr
//| ay(Array(byte-literal), Array(byte-literal), Array(int, int)), bool -> Arra
//| y(Array(true), Array(false), Array(true), Array(false), Array(not, bool), A
//| rray(bool, and, bool), Array(bool, or, bool), Array(int, >, int), Array(int
//| , ==, int)))
def rnd(len: Int, start: Int = 0): Int = (math.random() * len toInt) + start
//> rnd: (len: Int, start: Int)Int
def choose[T](alternatives: T*): T = alternatives(rnd(alternatives.length))
//> choose: [T](alternatives: T*)T
(1 to 10) map (_ => choose("one", "two", "three"))
//> res0: scala.collection.immutable.IndexedSeq[String] = Vector(one, three, th
//| ree, two, one, two, one, one, two, one)
def gen(acc: StringBuilder, lhs: String = "S", indent: String = ""): StringBuilder = lhs match {
case "byte-literal" => acc append ' ' append "%+d".format(rnd(256, -128))
case "body" => acc append " {\n" ; val indent2 = indent + ' '
(1 to rnd(3)) map (_ => gen(acc append indent2, "statement", indent2) append "\n")
acc append indent2 append ("}") // extra space cause statements have it, i.e. we output " if" nad " print" instead of if and print.
case _ if grammar contains (lhs) => val alternatives = grammar(lhs)
val alternative = choose(alternatives: _*)
alternative.foldLeft(acc){(acc, sym) => gen(acc, sym, indent)}
case lhs => acc append " " append lhs
} //> gen: (acc: StringBuilder, lhs: String, indent: String)StringBuilder
(1 to 16).map {i => val sb = new StringBuilder("program " + i + ":")
try {gen(sb)} catch {case _: StackOverflowError => }
}.mkString("\n") //> res1: String = program 1: void main() {
//| println( -32 )
//| }
//| program 2: void main() {
//| if ( false or +70 -126 > +19 ) {
//| println( -71 )
//| println( -48 -46 -126 )
//| }
//| }
//| program 12: void main() {
//| if ( false ) {
//| if ( not -24 -20 +127 == -43 ) {
//| }
//| println( -81 )
//| }
//| println( -65 )
//| }
}
Raw
3.converging_prog_gen.sc
// This generates text programs. However we need online tree structures to modify them.
// Python can be more perspective since it can instantiate structures dynamically.
// However, Scala supports types, which can describe the structures right in scala.
object ProgGen {
val cfactor = 1.0/2 //> cfactor : Double = 0.5
val memSize = 100 //> memSize : Int = 100
val grammar = Map(
// we could place while and if into STATEMENT because they have no alternatives.
// Yet, we need separate productions for them to account the weights
"S" -> "void main() body",
"statement" -> "println ( INT ) | if ( bool ) body | MEM = INT | WHILE",
"INT" -> "byte-literal | INT INT | MEM",
"MEM" -> "mem[ memSize ]",
"IF" -> "if ( bool ) body else body",
"WHILE" -> "while ( bool ) body",
"bool" -> "true | bool and bool | not bool"
).mapValues (_.split('|').map(_.trim.split("\\s+"))).toArray.toMap // toArray toMap is necessary to make a stable map. Without it, grammar != grammar because mapValues creates a dynamic view and we cannout count productions.
//> grammar : scala.collection.immutable.Map[String,Array[Array[String]]] = Map
//| (statement -> Array(Array(println, (, INT, )), Array(if, (, bool, ), body),
//| Array(MEM, =, INT), Array(WHILE)), bool -> Array(Array(true), Array(bool, an
//| d, bool), Array(not, bool)), MEM -> Array(Array(mem[, memSize, ])), INT -> A
//| rray(Array(byte-literal), Array(INT, INT), Array(MEM)), IF -> Array(Array(if
//| , (, bool, ), body, else, body)), WHILE -> Array(Array(while, (, bool, ), bo
//| dy)), S -> Array(Array(void, main(), body)))
def rnd(len: Int, start: Int = 0): Int = (math.random() * len toInt) + start
//> rnd: (len: Int, start: Int)Int
//def choose[T](alternatives: T*): T = alternatives(rnd(alternatives.length))
def gen(acc: StringBuilder, lhs: String = "S", indent: String = "", weights: Map[Array[String], Int] = Map()): StringBuilder = lhs match {
case "memSize" => acc append ' ' append rnd(memSize)
case "byte-literal" => acc append ' ' append "%+d".format(rnd(256, -128))
case "body" => (1 to rnd(10)).foldLeft(acc append " {\n"){(acc, _) =>
gen(acc append indent, "statement", indent + ' ', weights) append "\n"
} . append(indent + "}")
case _ if grammar contains lhs => val alternatives = grammar(lhs)
//val alternative = choose(alternatives: _*)
def wGetOrElse0(alternative: Array[String]) = weights.getOrElse(alternative, 0)
val roulette = alternatives.map(wGetOrElse0).map(count => Math.pow(cfactor, count))
def drop(n: Int, sum: Double): Int = if (sum < 0) n-1 else drop(n+1, sum - roulette(n))
val ball = Math.random * roulette.sum
val alternative = alternatives(drop(0, ball))
//println ("%.3f".format(ball) + ":"+ alternatives.zipWithIndex.map{case(a,i) => s"$a:" + a.mkString(",") -> roulette(i)}.mkString(";") + " => " + drop(0, ball) + "/" + roulette.length)
val w2 = weights updated (alternative, wGetOrElse0(alternative) + 1)
//val roulette2 = alternatives.map(alt => w2.getOrElse(alt, 0)).map(count => Math.pow(cfactor, -count))
//println(s"$alternative:" + alternative.mkString(",") + ":" +alternatives.zipWithIndex.map{case(a,i) => a.mkString(",") -> roulette2(i)}.mkString(";"))
//println(s"w1=$weights, w2=$w2")
alternative.foldLeft(acc){(acc, sym) => gen(acc, sym, indent, w2)}
case lhs => acc append ' ' append lhs
} //> gen: (acc: StringBuilder, lhs: String, indent: String, weights: Map[Array[S
//| tring],Int])StringBuilder
gen(new StringBuilder) //> res0: StringBuilder = void main() {
//| if ( true and true and true and not not true and true and not not true ) {
//|
//| mem[ 81 ] = mem[ 90 ]
//| mem[ 10 ] = mem[ 31 ]
//| if ( true ) {
//| if ( not true ) {
//| mem[ 88 ] = mem[ 40 ] -111
//| while ( not not not true and true and true and true ) {
//| while ( not true and true and true ) {
//| println ( mem[ 65 ] -98 +21 )
//| println ( mem[ 0 ] mem[ 8 ] -23 )
//| mem[ 12 ] = +52 +99 mem[ 58 ]
//| println ( +18 )
//| println ( -117 )
//| }
//| println ( mem[ 66 ] -30 )
//| mem[ 72 ] = +70
//| }
//| println ( mem[ 70 ] )
//| println ( -52 )
//| println ( mem[ 30 ] )
//| while ( true ) {
//| mem[ 97 ] = mem[ 44 ]
//| println ( mem[ 67 ] )
//| }
//| println ( mem[ 68 ] )
//| }
//| mem[ 84 ] = -87 +34 mem[ 67 ] -28
//| }
//| println ( +25 -115 )
//| mem[ 29 ] = +105
//| println (
//| Output exceeds cutoff limit.
gen(new StringBuilder) //> res1: StringBuilder = void main() {
//| println ( mem[ 3 ] mem[ 78 ] )
//| if ( not true ) {
//| mem[ 5 ] = -66 +79 -15
//| println ( -28 )
//| if ( not true and true and true and not true and true and true and not tr
//| ue and true ) {
//| println ( mem[ 61 ] )
//| while ( true ) {
//| println ( mem[ 41 ] )
//| mem[ 50 ] = +124
//| mem[ 64 ] = mem[ 12 ]
//| if ( true ) {
//| mem[ 71 ] = +126 mem[ 25 ]
//| mem[ 38 ] = mem[ 19 ]
//| if ( true ) {
//| println ( +61 )
//| println ( +25 )
//| while ( true ) {
//| mem[ 33 ] = -93 +120 mem[ 71 ]
//| println ( -27 )
//| mem[ 44 ] = mem[ 17 ]
//| println ( mem[ 28 ] )
//| println ( mem[ 13 ] -107 )
//| }
//| if ( true ) {
//| println ( -12 +92 -101 )
//| println ( +88 )
//| println ( mem[ 52 ] -105 )
//| mem[ 95 ] = mem[ 66 ]
//| while ( true and not true ) {
//|
//| Output exceeds cutoff limit.
gen(new StringBuilder)
}
Raw
4-2017 simple_tree.sc
object RandomTree extends App {
// Expr -> Byte | Sum Expr Expr
def intRnd(len: Int, start: Int = 0): Int = (math.random * len toInt) + start
def byteRnd = intRnd(256, -128)
case class Value[A](value: A, parent: Type) /*extends Type*/ {
//def gen = this
override def toString = value + ":" + parent
}
trait Type {
//def gen: Type
def gen: Value[_]
override def toString = getClass.getSimpleName
}
class OR/*oneOf Enum*/(alternatives: Type*) extends Type {
def gen = alternatives(intRnd(alternatives.length)).gen
}
//class AND/*Tuple*/(items: Type*) extends Type { // alternatives are nulls https://stackoverflow.com/a/46071889
class AND/*Tuple*/(items: => Array[Type]) extends Type {
def gen = new Value(items.map(_.gen), this) {
override def toString = value.mkString("(", ",", ")") + ":" + parent
}
}
object Expr extends OR(Sum, Byte) {
override def gen = Value(super.gen, this)
}
object Sum extends AND(Array(Expr, Expr))
object Byte extends Type {
def gen = Value(byteRnd, this)
}
(1 to 10) foreach { i=> println(Expr.gen) }
}
>scala RandomTree
-101:Byte$:Expr$
-28:Byte$:Expr$
-109:Byte$:Expr$
((18:Byte$:Expr$,80:Byte$:Expr$):Sum$:Expr$,-32:Byte$:Expr$):Sum$:Expr$
(-55:Byte$:Expr$,112:Byte$:Expr$):Sum$:Expr$
(((((((-68:Byte$:Expr$,((31:Byte$:Expr$,43:Byte$:Expr$):Sum$:Expr$,(-62:Byte$:Expr$,(31:Byte$:Expr$,(-78:Byte$:Expr$,-15:Byte$:Expr$):Sum$:Expr$):Sum$:Expr$):Sum$:Expr$):Sum$:Expr$):Sum$:Expr$,((-84:Byte$:Expr$,-66:Byte$:Expr$):Sum$:Expr$,98:Byte$:Expr$):Sum$:Expr$):Sum$:Expr$,-93:Byte$:Expr$):Sum$:Expr$,(-90:Byte$:Expr$,((87:Byte$:Expr$,-108:Byte$:Expr$):Sum$:Expr$,(((49:Byte$:Expr$,83:Byte$:Expr$):Sum$:Expr$,106:Byte$:Expr$):Sum$:Expr$,-105:Byte$:Expr$):Sum$:Expr$):Sum$:Expr$):Sum$:Expr$):Sum$:Expr$,42:Byte$:Expr$):Sum$:Expr$,-43:Byte$:Expr$):Sum$:Expr$,112:Byte$:Expr$):Sum$:Expr$
-7:Byte$:Expr$
68:Byte$:Expr$
-75:Byte$:Expr$
Raw
4.simple_tree.sc
// Randomly constructs tree like
// INT -> NUM | SUM INT INT
// This is more advantageous compared with direct text gen because allows
// to manipulate the tree, which is important for program evolution.
// For toText conversion, you need to create toC/toPython/etc methods,
// which would ouput only values according to target language syntax since
// current toString outputs both values and types.
// For convenience, current random value "floats" in the wrapper of
// type, which tells which alternative values the value can be replaced
// with, not only the type that variable belongs to. For instance
// 10 belongs to type Num, a 256-value range. The num (range) is nested into
// the node Enum, which means that num can be replaced for Sum.
// The following fails is Eclipse Worksheet. I thus turned it into app.
object sentence_gen extends App {
abstract class Value(val t: Type) {
def valstr: String
override def toString = "(" + t.getName + f"$valstr)"
}
trait Type { me =>
def rnd: Value
def getName: String = getClass.getSimpleName
}
def iRnd(rangeLen: Int, from: Int = 0) = (Math.random * rangeLen).toInt + from
case class Enum(alternatives: Type*) extends Type {
case class Val(ref: Value) extends Value(this) { def valstr = ref.toString}
def rnd = {
val picked = iRnd(alternatives.length)
new Val(alternatives(picked).rnd)
}
}
val iExpr = new Enum(new Num(-128, 256), IntSum)
case class Num(from: Int, len: Int) extends Type() {
case class Val(n: Int) extends Value(this) { def valstr = n.toString}
override def getName = f"[$from,${from + len}] "
def rnd = new Val(iRnd(len, from))
}
case object IntSum extends Type() {
case class Val(left: Value, right: Value) extends Value(this) { def valstr = left + "," + right}
def rnd: Value = new Val(iExpr.rnd, iExpr.rnd)
}
// generate some example trees
(1 to 10) foreach { i=> println(iExpr.rnd) }
// result looks like
/*
(Enum(IntSum$(Enum(IntSum$(Enum([-128,128] 119)),(Enum(IntSum$(Enum(IntSum$(Enum([-128,128] -58)),(Enum([-128,
28,128] -25)))))),(Enum([-128,128] -103))))))
(Enum(IntSum$(Enum([-128,128] 103)),(Enum([-128,128] 47))))
(Enum(IntSum$(Enum(IntSum$(Enum([-128,128] -59)),(Enum(IntSum$(Enum(IntSum$(Enum([-128,128] -40)),(Enum(IntSum
,(Enum(IntSum$(Enum([-128,128] -105)),(Enum(IntSum$(Enum(IntSum$(Enum(IntSum$(Enum(IntSum$(Enum(IntSum$(Enum(I
8] 17)),(Enum([-128,128] 103)))))),(Enum(IntSum$(Enum([-128,128] 88)),(Enum(IntSum$(Enum([-128,128] 110)),(Enu
,128] -87)))))))),(Enum([-128,128] 102)))),(Enum(IntSum$(Enum([-128,128] 68)),(Enum(IntSum$(Enum([-128,128] -5
num([-128,128] 74)),(Enum([-128,128] -91)))))))),(Enum([-128,128] -6))))
(Enum([-128,128] -95))
(Enum([-128,128] 113))
(Enum([-128,128] -33))
(Enum([-128,128] 29))
(Enum(IntSum$(Enum([-128,128] -35)),(Enum([-128,128] 46))))
(Enum([-128,128] 26))*/
}
Raw
5-2017 converging_tree.sc
object RandomTree extends App {
val cfactor = 2
// Expr -> Byte | Sum Expr Expr
def intRnd(len: Int, start: Int = 0): Int = (math.random * len toInt) + start
def byteRnd = intRnd(256, -128)
case class Value[A](value: A, parent: Type) /*extends Type*/ {
//def gen(weights: Weights) = this
override def toString = formatValue + ":" + parent
def formatValue = value.toString
}
trait Type {
//def gen(weights: Weights): Type
def gen(weights: Weights): Value[_]
override def toString = getClass.getSimpleName
}
type Weights = Map[Type, Int]
class OR/*Enum*/(alternatives: Type*) extends Type {
def gen(weights: Weights) = {
def getWeightOrElse0(alternative: Type) = weights.getOrElse(alternative, 0)
val roulette = alternatives.map(getWeightOrElse0).map(count => Math.pow(cfactor, -count))//.toArray
val ball = Math.random * roulette.sum
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
//println(roulette + ":" + ball)
val alternative = alternatives(drop(0, ball))
val uw = weights updated (alternative, getWeightOrElse0(alternative) + 1)
alternative.gen(uw)
}
}
//class AND/*Tuple*/(items: Type*) extends Type { // alternatives are nulls https://stackoverflow.com/a/46071889
class AND/*Tuple*/(items: => Array[Type]) extends Type {
def gen(weights: Weights) = new Value(items.map(_.gen(weights)), this) {
override def formatValue = value.mkString("(", ",", ")")
}
}
object Expr extends OR(Sum, Byte) {
override def gen(weights: Weights) = Value(super.gen(weights), this)
}
object Sum extends AND(Array(Expr, Expr))
object Byte extends Type {
def gen(weights: Weights) = Value(byteRnd, this)
}
(1 to 10) foreach { i=> println(Expr.gen(Map.empty)) }
}
>scala RandomTree
((91:Byte$:Expr$,25:Byte$:Expr$):Sum$:Expr$,1:Byte$:Expr$):Sum$:Expr$
(-99:Byte$:Expr$,-70:Byte$:Expr$):Sum$:Expr$
6:Byte$:Expr$
(52:Byte$:Expr$,-117:Byte$:Expr$):Sum$:Expr$
68:Byte$:Expr$
(-4:Byte$:Expr$,-123:Byte$:Expr$):Sum$:Expr$
(-122:Byte$:Expr$,58:Byte$:Expr$):Sum$:Expr$
100:Byte$:Expr$
(72:Byte$:Expr$,16:Byte$:Expr$):Sum$:Expr$
((16:Byte$:Expr$,-17:Byte$:Expr$):Sum$:Expr$,48:Byte$:Expr$):Sum$:Expr$
Raw
5.converging_tree.sc
val cfactor = 2
abstract class Value(val t: Type) {
def valstr: String
override def toString = "(" + t.getName + f"$valstr)"
}
type Weights = Map[Type, Int]
trait Type { me =>
def rnd(path: Weights): Value// call this method
def getName: String = getClass.getSimpleName
}
def iRnd(rangeLen: Int, from: Int = 0) = (Math.random * rangeLen).toInt + from
case class Enum(alternatives: Type*) extends Type {
class Val(ref: Value) extends Value(this) { def valstr = ref.toString}
def rnd(weights: Weights) = {
// val picked = iRnd(alternatives.length) // simply random
val roulette = alternatives.map {weights get _ match {
case Some(count) => Math.pow(cfactor, -count)
case None => 1
}}.toArray
val ball = Math.random * roulette.sum
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
val picked = alternatives(drop(0, ball))
val uw = weights updated (picked, weights.getOrElse(picked, 0) + 1)
new Val(picked.rnd(uw))
}
}
class Num(from: Int, len: Int) extends Type() {
class Val(n: Int) extends Value(this) { def valstr = n.toString}
override def getName = f"[$from,${from + len}] "
def rnd(weights: Weights) = new Val(iRnd(len, from))
}
object Byte extends Num(-128, 256)
val ByteExpr: Enum = new Enum(Byte, IntSum(ByteExpr))
case class IntSum(expr: => Type) extends Type() { // need call by name to "tie the knot" val ByteExpr => Sum(ByteExpr)
class Val(left: Value, right: Value) extends Value(this) { def valstr = left + "," + right}
def rnd(weights: Weights): Value = new Val(expr.rnd(weights), expr.rnd(weights))
}
(1 to 70) foreach {i=> println(ByteExpr.rnd(Map.empty))}
Raw
5.converging_tree_any_expr.sc
object prog_gen extends App {
val cfactor = 20
case class IO(val indent: String, val out: java.io.PrintWriter) {
def indented = IO(indent + " ", out)
def write(s: String) = out.write(s)
def writeAll(seq: Any*) { seq foreach { _ match {
case v:Value => v.write(this)
case subseq: Seq[Any] => writeAll(subseq:_*)
case o => write(o.toString)
}}}
}
abstract class Value(val t: Type) {
def write(io: IO)
override def toString = "value of " + t.name
}
type Weights = Map[Type, Int]
trait Type { me =>
def name: String = getClass.getSimpleName
def rnd(path: Weights): Value// call this method
}
def iRnd(rangeLen: Int, from: Int = 0) = (Math.random * rangeLen).toInt + from
// We cannot make match call-by-name with variable argument list
class Enum(alternatives: => Seq[Type]) extends Type {
def format(io: IO, ref: Value) = {io.writeAll(name, ":", ref)}
class Val(ref: Value) extends Value(this) {def write(io: IO) {format(io, ref)}}
def rnd(weights: Weights) = {
// val picked = iRnd(alternatives.length) // simply random
val roulette = alternatives.map {weights get _ match {
case Some(count) => Math.pow(cfactor, -count)
case None => 1
}}.toArray
val ball = Math.random * roulette.sum
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
val picked = alternatives(drop(0, ball))
val uw = weights updated (picked, weights.getOrElse(picked, 0) + 1)
new Val(picked.rnd(uw))
}
}
object Bool extends Enum(List(BoolLit, OR, AND, GT, EQ))
val ByteExpr: Enum = new Enum(List(Byte, Plus, MemGet))
object Statement extends Enum(List(If, While, MemSet)) {
override def format(io: IO, ref: Value) = {io.writeAll(io.indent, ref)}
}
class Range(min: Int, max: Int, format: Int => String) extends Type() {
class Val(val n: Int) extends Value(this) {def write(io: IO) = io.write(format(n)) }
//override def getName = f"[$from,${from + len}] "
def rnd(weights: Weights) = new Val(iRnd(max, min))
}
object MemGet extends Range(0, 100, (n: Int) => "mem[" + n + "]" )
object Byte extends Range(-128, 256, (n: Int) => "b" + n )
object BoolLit extends Range(0, 2, (n: Int) => n match {case 0 => "false" ; case 1 => "true" ; case _ => ???})
case class Separators(mid: String, left: String = "(", right: String=")")
implicit def sepConstr(tuple: Tuple3[String, String, String]) = Separators(tuple._1, tuple._2, tuple._3)
implicit def sepConstr(sep: String) = Separators(sep)
class FixedLenSeq(syntax: => Seq[Type], sep: Separators = " ") extends Type {
def format(io: IO, values: Seq[Value]) = {
val separatedValues = values.flatMap{List(_, sep.mid)}.init
io.writeAll(name, sep.left, separatedValues, sep.right)
}
class Val(values: Seq[Value]) extends Value(this) {def write(io: IO) = format(io, values)}
def rnd(weights: Weights) = { new Val(syntax map {_.rnd(weights)})}
}
object If extends FixedLenSeq(List(Bool, Body))
object While extends FixedLenSeq(List(Bool, Body))
object MemSet extends FixedLenSeq(List(MemGet, ByteExpr), (" = ", "", ""))
class BinOp(exprType: => Type, override val name: String) extends FixedLenSeq(List(exprType, exprType)) {
def write(io: IO, values: Seq[Value]) = {// infix binary ops
io.writeAll("(", values(0), " ", name, " ", values(1), ")")
}
}
object GT extends BinOp(Byte, "<")
object EQ extends BinOp(Byte, " == ")
class VarLenExpr(min: Int, max: Int, elemSyntax: Type, sep: Separators) extends Type {
class Val(ref: FixedLenSeq#Val) extends Value(this) {def write(io: IO) = io.writeAll(name, ":", ref) }
//override def getName = f"[$from,${from + len}] "
def rnd(weights: Weights) = {
val list = List.fill(iRnd(max, min))(elemSyntax)
new Val( new FixedLenSeq(list, sep).rnd(weights))
}
}
object Plus extends VarLenExpr(1, 10, Byte, " + ") //BinOp(Byte)
object OR extends VarLenExpr(1, 10, Bool, " OR ") //BinOp(Byte)
object AND extends VarLenExpr(1, 10, Bool, " AND ") //BinOp(Byte)
object Body extends Type {
class Val(ref: VarLenExpr#Val) extends Value(this) {def write(io: IO) {
io.indented.writeAll(name, ":", ref, "\n", io.indent, "}") // all nested statements are printed indented
}}
def rnd(weights: Weights) = new Val(new VarLenExpr(4, 10, Statement, ("\n", "{\n", "")).rnd(weights))
}
val io = IO("", new java.io.PrintWriter(System.out, true))
(1 to 1) foreach {i=>
Body.rnd(Map.empty).write(io)
io.out.println()
}
}
Raw
6.Complete_prog_gen.sc
/*
* Implementation enables to describe the tree with BNF text and builds random trees according to it.
* Resulting trees can be either saved to file (for evaluation) or evolved (to be done).
*/
object prog_gen extends App { Generator.generate(System.out) }
object Generator {
val cfactor = 20 // convergence factor
val MEM_SIZE = 2
val productions = List(
// Below, | creates alternatives using enum type
// Every alternative is a sequence type
// Sequence or alternative type is created for every non-terminal type
// EOL, INDENT, INDENT++, RANGE and * symbols have obvious, built-in meaning
// Otherwise, constant type is used for terminals.
// First symbol (upper left corner) is the start one
"PROGRAM -> HEAD void autogenerated() BODY TAIL",
"HEAD -> #include <stdio.h> EOL char mem[ MEM_SIZE ]; ",
"BODY -> { INDENT++ EOL STATEMENT_LN* INDENT-- INDENT }",
"STATEMENT_LN -> INDENT STATEMENT ; EOL",
"STATEMENT -> ; | MEM = INT | while ( BOOL ) BODY | if ( BOOL ) BODY else BODY",
"INT -> RANGE_-128_127 | INT + INT | MEM",
"MEM -> mem[ RANGE_0_MEM_SIZE ]",
"BOOL -> 0 | 1 | BOOL && BOOL | !( BOOL ) | INT == INT | INT < INT",
"TAIL -> int main() { autogenerated() ; int i; for(i = 0; i < 2; i++) printf(\"%d \", mem[i]); }"
//"E -> Int | Int + " // fails
)
// Parse into LHS => List[List[String]], where RHS is list of alternaitves
// and every alternative is a seq of tokens
. map {production =>
val rhsStart = production.indexOf("->")
val lhs = production.substring(0, rhsStart).trim
val rhs = production.replaceAll("MEM_SIZE", MEM_SIZE+"").substring(rhsStart+2).split('|')
(lhs, rhs.toList map (_.trim.split("\\s+").toList map {_.trim}) )
}
val syntax = productions.toMap
syntax foreach {case (x,y) => println(x + " -> " + y)}
val instantiatedTypes = scala.collection.mutable.Map[Any, Type]()
abstract class Type(val symKey: Any) { me =>
println("instantiated " + this + " for " + symKey) // keep report here to see that no classes are created after initialization, during value generation, which is possible due to lazy call-by-value
instantiatedTypes.update(symKey, this)
def rnd(path: Weights): Value// call this method
}
new Const("EOL") { override def format(io: IO) = io.write("\n") }
new Const("INDENT") { override def format(io: IO) = io.write(io.indent) }
new Const("INDENT++") { override def format(io: IO) = io.indent += " " }
new Const("INDENT--") { override def format(io: IO) = io.indent = io.indent.drop(1)}
val startSymbolSyntax = productions(0) match {case (lhs, rhs) => parseEnum(lhs, rhs)}
println("Start sym = " + startSymbolSyntax)
def generate(out: java.io.OutputStream) = {
val io = IO("", new java.io.PrintWriter(out, true))
startSymbolSyntax.rnd(Map.empty).write(io)
io.out.println()
}
case class IO(var indent: String = "", val out: java.io.PrintWriter = new java.io.PrintWriter(System.out, true)) {
def write(s: String) = out.write(s)
def writeAll(seq: Any*) { seq foreach { _ match {
case v:Value => v.write(this)
case subseq: Seq[Any] => writeAll(subseq:_*)
case o => write(o.toString)
}}}
}
abstract class Value(val t: Type) {
def write(io: IO)
override def toString = "value of " + t.symKey
}
type Weights = Map[Type, Int] // during value generation, weights limit the growth with convergence factor
def rand(rangeLen: Int, from: Int = 0) = (Math.random * rangeLen).toInt + from
def lazyCreate(key: Any, ctor: => Type): Type = instantiatedTypes.getOrElse(key, ctor)
def parseSymSequence(sequence: Seq[String]): Type = {
//println("parseSymSequence " + sequence)
val children = sequence.map {sym =>
def ifdoesnotexist = if (sym.startsWith("RANGE_")) {
val range = sym.split('_');
new Range(sym, range(1).toInt, range(2).toInt)
} else if (sym.endsWith("*")) {
val subSym: String = sym.dropRight(1)
val subExpr = parseSymSequence(List(subSym)) // this can either be a const or enum
new VarLenExpr(sym, 3, 5, subExpr)
} else syntax.get(sym) match {
case Some(rhs) => parseEnum(sym, rhs)
case None => new Const(sym)
}
lazyCreate(sym, ifdoesnotexist)
}
if (children.length == 1) children(0) else {
lazyCreate(children, new FixedLenSeq(children))
}
}
def parseEnum(lhs: String, rhs: Seq[Seq[String]]): Type = {
println("parseEnum " + lhs)
if (rhs.length == 1) println("info: production " + lhs + " produced a single-option alternative. This makes no sense.")
lazyCreate(lhs, new Enum(lhs, rhs map {seq => parseSymSequence(seq)}))
}
class Const(val s: String) extends Type(s) {
def format(io: IO) = io.write(s + " ")
def rnd(weights: Weights) = new Value(this) {
def write(io: IO) = format(io)
}
override def toString = s
}
case class Range(sym: String, val min: Int, val max: Int) extends Type(sym) {
// class Val extends Value(this) -- it might be better to declare new Value this way
// because anonymous class refers the weights in the context of rnd, which is unnecessary
// But overhead is small since we won't generate huge programs. So, let's leave it here.
def rnd(weights: Weights) = new Value(this) {
val child = rand(max-min, min)
def write(io: IO) = io.write("%+d".format(child) + " ")
}
}
//Initially, I have determined that I need to defer the argument with =>
// to "tie the knot" when modelled syntax describing classes in scala
// `A => a A`. Yet, later, I had to have remove it later here
// because of the bug https://issues.scala-lang.org/browse/SI-9223
class FixedLenSeq(syntax: Seq[Type]) extends Type(syntax) {
def rnd(weights: Weights) = new Value(this) {
val children = syntax map {_.rnd(weights)}
def write(io: IO) = io.writeAll(children)
}
}
class VarLenExpr(sym: String, min: Int, max: Int, elemSyntax: => Type) extends Type(sym) {
def rnd(weights: Weights) = {
val list = List.fill(rand(max-min, min))(elemSyntax)
new Value (this) {
val ref = lazyCreate(list, new FixedLenSeq(list)).rnd(weights)
def write(io: IO) = ref.write(io)
}
}
}
// Call-by-name to prevent stackoverflow. Fortunately it does not happen if I
// call-by-value in the FixedLenSeq.
// I do not know why we need call-by-name in one case but not the other and
// why there is a bug there.
class Enum(lhs: String, alternatives: => Seq[Type]) extends Type(lhs) {
def rnd(weights: Weights) = {
// val picked = iRnd(alternatives.length) // simply random
val roulette = alternatives.map {weights get _ match {
case Some(count) => Math.pow(cfactor, -count)
case None => 1
}}.toArray
val ball = Math.random * roulette.sum
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
val pickedType = alternatives(drop(0, ball))
val uw = weights updated (pickedType, weights.getOrElse(pickedType, 0) + 1)
val child = pickedType.rnd(uw)
new Value(this) {def write(io: IO) = child.write(io)}
}
}
def println(a: Any*) = System.err.println(a)
}
Example output is
#include <stdio.h>
char mem[ 2 ]; void autogenerated() {
; ;
if ( mem[ +1 ] == +79 ) {
; ;
while ( 0 ) {
mem[ +0 ] = mem[ +0 ] ;
; ;
mem[ +1 ] = -31 + mem[ +0 ] ;
; ;
} ;
mem[ +1 ] = mem[ +0 ] ;
} else {
mem[ +1 ] = mem[ +1 ] + -90 ;
while ( +38 == -122 ) {
mem[ +0 ] = -76 + +34 ;
; ;
mem[ +0 ] = +34 + +87 ;
; ;
} ;
; ;
} ;
; ;
} int main() { autogenerated() ; int i; for(i = 0; i < 2; i++) printf("%d ", mem[i]); }
Raw
6.ComplileAndRun.bat
: Above can be runned with batch
@echo on
:echo Rebuilding the grammar, specified in scala file
call scalac prog_gen.sc
echo generating a random prog
call scala prog_gen > prog.c
rm prog.exe
cat prog.c
echo compiling generated prog
gcc prog.c -o prog -lm
echo and, finally, running it (this may hang)
prog.exe
Raw
7.Evaluating.sc
// 1. Here is a bit more advanced syntax (allows indirect operations on memory, not only mem[ int_value] = mem[addr] + int_expr
// but also mem[ int_value + mem[ int_expr ] ]
// 2. Generated program is executed and its output is captured so that it can be evaluated.
// 3. Experiment suggests that minimal execution time is 150 msec. Also, it is mostly compilation rather
// than execution. Probably we need to calibrate it on start using some good programs to see what is good
// run time at specific PC and make timout twice as large.
object prog_gen extends App {
(1 to 1) foreach {i =>
Generator.generate(new java.io.FileOutputStream("prog.c"))
import scala.sys.process._, scala.concurrent._, ExecutionContext.Implicits.global
import scala.util.{Try, Success, Failure}
val procLogger = ProcessLogger(line => {println ("out line: " + line)},
line => {println ("err line: " + line)})
val exe = new java.io.File("prog.exe")
exe.delete ; assert(!exe.exists, exe + " exists after delete!")
def runProg(timeout: Int, goodTimeout: Int = -1): Int = {
println("runProg " + timeout)
val p = ("cat prog.c" #&& "gcc prog.c -o prog -lm" #&& "echo running, this may hang" #&& "prog.exe").run(procLogger) // start asynchronously
val f = Future(blocking(p.exitValue())) // wrap in Future
try {
Await.result(f, duration.Duration(timeout, "millis"))
println("exitCode = " + p.exitValue())
if (timeout == 2) timeout else runProg(timeout/2, timeout)
} catch {
case _: TimeoutException =>
println("TIMEOUT!")
p.destroy()
goodTimeout
//println("exitCode = " + p.exitValue()) // p.exitCode throws exceptoin here
}
}
println ("timeout = " + runProg(1000))
}
}
object Generator {
val cfactor = 20 // convergence factor
val MEM_SIZE = 20
val productions = List(
// Below, | creates alternatives using enum type
// Every alternative is a sequence type
// Sequence or alternative type is created for every non-terminal type
// EOL, INDENT, INDENT++, RANGE and * symbols have obvious, built-in meaning
// Otherwise, constant type is used for terminals.
// First symbol (upper left corner) is the start one
"PROGRAM -> HEAD BODY TAIL",
"BODY -> { INDENT++ EOL STATEMENT_LN* INDENT-- INDENT }",
"STATEMENT_LN -> INDENT STATEMENT ; EOL",
"STATEMENT -> | setMem( INT , INT ) | while ( BOOL ) BODY | if ( BOOL ) BODY else BODY | setMem( INT , INT ) | setMem( INT , INT )",
"INT -> RANGE_-100_100 | INT + INT | getMem( INT ) | getArg( RANGE_1_10 )",
"BOOL -> 0 | 1 | BOOL && BOOL | !( BOOL ) | INT == INT | INT < INT",
"""HEAD -> #include <stdio.h> EOL INDENT++
|int range(int min, int max, int value) { EOL
| INDENT if (value < min) return min; EOL
| INDENT if (value > max) return max; EOL
| INDENT return value; EOL
|} EOL INDENT--
|int mem[ MEM_SIZE ]; int getMem(int addr) {return mem[range(0, MEM_SIZE, addr)];} EOL
|void setMem(int addr, int value) { mem[range(0, MEM_SIZE, addr)] = range(-199999999, 199999999, value);} EOL EOL
|void autogenerated()
""".stripMargin,
"""TAIL -> EOL EOL int ac; char **av; int getArg(int addr) { atoi(av[range(1, ac-1, addr)]); } EOL
|int main(int argc, char *argv[]) { EOL INDENT++
| INDENT ac = argc; av = argv; EOL
| INDENT autogenerated() ; EOL
| INDENT int i; for(i = 0; i < MEM_SIZE; i++) printf("%d ", mem[i]); printf("\n"); EOL
|return 0;} EOL INDENT-- """.stripMargin
//"E -> Int | Int + " // fails
)
// Parse into LHS => List[List[String]], where RHS is list of alternaitves
// and every alternative is a seq of tokens
. map {production =>
val rhsStart = production.indexOf("->")
val lhs = production.substring(0, rhsStart).trim
val rhs = production.replaceAll("MEM_SIZE", MEM_SIZE+"").substring(rhsStart+2).split('|')
(lhs, rhs.toList map (_.trim.split("\\s+").toList map {_.trim}) )
}
val syntax = productions.toMap
syntax foreach {case (x,y) => println(x + " -> " + y)}
val instantiatedTypes = scala.collection.mutable.Map[Any, Type]()
abstract class Type(val symKey: Any) { me =>
println("instantiated " + this + " for " + symKey) // keep report here to see that no classes are created after initialization, during value generation, which is possible due to lazy call-by-value
instantiatedTypes.update(symKey, this)
def rnd(path: Weights): Value// call this method
}
new Const("EOL") { override def format(io: IO) = io.write("\n") }
new Const("INDENT") { override def format(io: IO) = io.write(io.indent) }
new Const("INDENT++") { override def format(io: IO) = io.indent += " " }
new Const("INDENT--") { override def format(io: IO) = io.indent = io.indent.drop(1)}
val startSymbolSyntax = productions(0) match {case (lhs, rhs) => parseEnum(lhs, rhs)}
println("Start sym = " + startSymbolSyntax)
def generate(out: java.io.OutputStream) = {
val io = IO("", new java.io.PrintWriter(out, true))
startSymbolSyntax.rnd(Map.empty).write(io)
io.out.println()
}
case class IO(var indent: String = "", val out: java.io.PrintWriter = new java.io.PrintWriter(System.out, true)) {
Raw
8.Multithreaded_evaluate.sc
Using fixed length expr to back up variable length expr type is troublesome. At least,
it should not create register fixed length seq sockets in the table because muitating
crates new fixed len objects after parsing, at runtime. But updating the table,
shared by multiple threads is troublesome. At the same time, table exists to
tie the knots, appearing due to circular references in the parsed grammar and
we do not need to use table for creating fixed length types after parsing it.
Furthermore, population uses only sequences of limited length whereas the number
of such sequnces is infinite and the benefit of Flyweight can be very low during
long runtime, which inflates the table with useless sequences, only tiny fraction
of which is used in the population. We therefore do not store the varlen-induced
fixed len sequences in the type table.
No, since our variation range is not large, I have chosen to instantiate fixed-length types in advance.
In this implementation, best individual is selected and evolved. Other qualities are lost.
By virtue of that, evaluation climbs some hills and stucks. Namely, my responce strings are
tuples of integers, like "0 0 0 100 -200 0 0 0", optimized for length. I have however
noticed that I am stuck at several positions only being optimized. Others remain zero.
I guess that because only tiny mutations are enabled and only one of them passes the generation
bottleneck, you need many generations to discover a new position to optimize.
Probably, we need to select many individuals and start mixing them with others if they
discover a new feature even at the cost of failure in all other respects. This means
that crossover operator is needed. That is actually what sex is for. It stands for
recombination (in contrast to single-sex replication that we currently exploit)
, which enables "if you and me have apples then we both have apples" and standing on
the shoulders of each other. We can evolve good feature ortagonally and combine them.
My example problem enables this very well.
Starting to move into that direction, I did
roulette-selection of the parent to mutate 100 times, to recreate a new population of
the original size. But result seems not different from using single best. Alternative
qualities never appear. We need higher mutation rates for some individuals that will
destroy existing fine-tuned, very complex features but give rise to the new ones.
We can however explore variable mutation rate for the replication instead of sexual recombination.
But fitness must be corrected anyway. New random solutions will likely to have less
fitness and yet we should qualify them higher, despite shorter total length.
This is a contradiction. It can be resolved if we reduce the weight of feature contri-
bution once a parent with such feature was selected.
In the future, I would like to explore
1. Valuing rare features
2. Direct Communication. Make it primary means of communication. State/memory must be secondary. Also
QUOTE BEGIN
Push is a stack-based language which maintains separate stacks for data of different types. Functions, whilst generic, operate
upon arguments at the top of whichever stack is currently identified by the system's TYPE stack; a special stack which contains
type references. Programs comprise a linear sequence of arguments and functions. Because the stack system de-couples arguments
from the functions which use them, it is no longer possible to apply incorrectly-typed arguments to a function
END QUOTE
says that in place of memory we could stack all produced results in typed memory or update the set of variables and next
statements could use those initialized memories. However, reading uninitalized makes sense also. 'Uninitialized' means sta-
tically initialized.
3. Sexual Recombination
4. Genome constraints,
5. parser may be needed for resume possibility. I may want to evelve something then stop
the process, fix something and continue. We have elready specefied syntax anyway.
6. We could express the syntax in DSL but we need to exploit the reflection http://docs.scala-lang.org/overviews/reflection/symbols-trees-types.html and scalacheck lib
anyway for mutation. Consider this opportunity instead of custom type system.
It allows to instantiate new types at runtime http://docs.scala-lang.org/overviews/quasiquotes/type-details.html,
generate arbitrary instances and traverse the parse trees. It is surprising how Reactive Generators
(Coursera 002) map to mine classes: reactive single <-> Const, reactive choose(lo, hi) <-> Range
and reactive oneOf <-> mine Enum).
import java.io._, java.nio.file._, Paths.get
import scala.sys.process._, scala.concurrent._, ExecutionContext.Implicits.global
import scala.annotation.tailrec, scala.collection._
object UserFitness {
def compute(programId: String, programFunc: String => Option[String]): Option[Long] =
programFunc("1 2 3 4 5 6 7 8 9").map{response =>
val value = response.length
println(programId + " responds " + response + " with value = " + value)
value
} // program produces string output and we take its length if success
}
object Framework extends App {
val WORKER_THREADS = Runtime.getRuntime().availableProcessors() *2
val POPULATION_SIZE = 100; val exeTimeout = 100 // 150 msec takes the compilation + execution. Make pure exectime proportional
val dump_C_files = false
val cfactor = 20 // convergence factor
val MEM_SIZE = 20
val productions = List(
// Below, | creates alternatives using enum type. Every alternative is a sequence type.
// Sequence or alternative type is created for every non-terminal type.
// EOL, INDENT, INDENT++, RANGE and * symbols have obvious, built-in meaning.
// Otherwise, constant type is used for terminals on-the-fly.
// First symbol (upper left corner) is the start one.
"PROGRAM -> HEAD BODY TAIL",
"BODY -> { INDENT++ EOL STATEMENT_LN* INDENT-- INDENT }",
"STATEMENT_LN -> INDENT STATEMENT ; EOL",
"STATEMENT -> | setMem( INT , INT ) | while( BOOL ) BODY | if( BOOL ) BODY else BODY | setMem( INT , INT ) | setMem( INT , INT )",
"INT -> RANGE_-100_100 | INT + INT | getMem( INT ) | getArg( RANGE_1_10 )",
"BOOL -> 0 | 1 | BOOL && BOOL | !( BOOL ) | INT == INT | INT < INT"
//"E -> Int | Int + " // fails
)
// Parse into LHS => List[List[String]], where RHS is list of alternaitves
// and every alternative is a seq of tokens
. map {production =>
val rhsStart = production.indexOf("->")
val lhs = production.substring(0, rhsStart).trim
val rhs = production.substring(rhsStart+2).split('|')
(lhs, rhs.toList map (_.trim.split("\\s+").toList map {_.trim}) )
}
val syntax = productions.toMap
syntax foreach {case (x,y) => println(x + " -> " + y)}
var instantiatedTypes = mutable.Map[Any, Type]() ; var initialized = false// table is updated during load and then locked
import Framework.{Value, IO, Weights, rint}
//Type is a pattern, which defines a range of values. The patterns are also sometimes called 'functions'
// in some GP frameworks and 'individuals' are used instead of 'values'.
abstract class Type(val symKey: Any) { me =>
println(Thread.currentThread.getName + " instantiated " + this + " for " + symKey) // keep report here to see that no classes are created after initialization, during value generation, which is possible due to lazy call-by-value
if (initialized) throw new RuntimeException("Attempted to register " + this + " for " + symKey + " after initialization")
instantiatedTypes.update(symKey, this)
def rnd(path: Weights): Value// call this method
}
new Const("HEAD") { override def format(io: IO) = io.write("""
#include <stdio.h>
int range(int min, int max, int value) {
if (value < min) return min;
if (value > max) return max;
return value;
}
int rangeScaling(int start1, int stop1, int value1, int start2, int stop2) {
float fraction = (value1 - stop1) / (stop1 - start1) ;
// fraction is also equal to fraction = (value2 - stop2) / (stop2 - start2)
// threfore
return fraction * (stop2 - start2) + stop2 ; // this is value2
}
int mem[ MEM_SIZE ]; int getMem(int addr) {return mem[range(0, MEM_SIZE, addr)];}
void setMem(int addr, int value) { mem[range(0, MEM_SIZE, addr)] = range(-199999999, 199999999, value);}
void autogenerated() """.replaceAll("MEM_SIZE", MEM_SIZE+""))}
new Const("TAIL") { override def format(io: IO) = io.write("""
int ac; char **av; int getArg(int addr) { atoi(av[range(1, ac-1, addr)]); }
int main(int argc, char *argv[]) {
ac = argc; av = argv;
autogenerated();
int i; for(i = 0; i < MEM_SIZE; i++) printf("%d ", mem[i]); printf("\n");
return 0;
}""".replaceAll("MEM_SIZE", MEM_SIZE+""))}
new Const("EOL") { override def format(io: IO) = io.write("\n") }
new Const("INDENT") { override def format(io: IO) = io.write(io.indent) }
new Const("INDENT++") { override def format(io: IO) = io.indent += " " }
new Const("INDENT--") { override def format(io: IO) = io.indent = io.indent.drop(1)}
val startSymbolSyntax = productions(0) match {case (lhs, rhs) => parseEnum(lhs, rhs)}
println("Start sym = " + startSymbolSyntax)
def makeIo(out: OutputStream): IO = IO("", new PrintWriter(out, true))
def generate = startSymbolSyntax.rnd(Map.empty)
def lazyCreate(key: Any, ctor: => Type): Type = instantiatedTypes.getOrElse(key, ctor)
def parseSymSequence(sequence: Seq[String]): Type = {
//println("parseSymSequence " + sequence)
val children = sequence.map {sym =>
def ifdoesnotexist = if (sym.startsWith("RANGE_")) {
val range = sym.split('_');
new Range(sym, range(1).toInt, range(2).toInt)
} else if (sym.endsWith("*")) {
val subSym: String = sym.dropRight(1)
val subExpr = parseSymSequence(List(subSym)) // this can either be a const or enum
new VarLenExpr(sym, 3, 5, () => subExpr)
} else syntax.get(sym) match {
case Some(rhs) => parseEnum(sym, rhs)
case None => new Const(sym)
}
lazyCreate(sym, ifdoesnotexist)
}
if (children.length == 1) children(0) else {
lazyCreate(children, new FixedLenSeq(children))
}
}
def parseEnum(lhs: String, rhs: Seq[Seq[String]]): Type = {
println("parseEnum " + lhs)
if (rhs.length == 1) {
println("info: production " + lhs + " produced a single-option alternative. This makes no sense.")
parseSymSequence(rhs(0))
}
else lazyCreate(lhs, new Enum(lhs, () => rhs map {seq => parseSymSequence(seq)}))
}
class Const(val s: String) extends Type(s) {
val value = new Value(this) {
def phenotype(io: IO) = format(io)
}
def format(io: IO) = io.write(s + " ")
def rnd(weights: Weights) = value
override def toString = s
}
case class Range(sym: String, val min: Int, val max: Int) extends Type(sym) {
// class Val extends Value(this) -- it might be better to declare new Value this way
// because anonymous class refers the weights in the context of rnd, which is unnecessary
// But overhead is small since we won't generate huge programs. So, let's leave it here.
//def rnd(weights: Weights) = new Value(this) {
// val child = rint(max-min, min)
// def phenotype(io: IO) = io.write("%+d".format(child) + " ")
//}
// No, we still need the inner class for analyzing the structure of individual.
// Specific Value subtype connects the Type (socked) with implementation type (instance/individual/value)
case class Val(val child: Int) extends Value(this) {
def phenotype(io: IO) = io.write("%+d".format(child) + " ")
}
def rnd(weights: Weights) = new Val(rint(max-min, min))
}
//Initially, I have determined that I need to defer the argument with =>
// to "tie the knot" when modelled syntax describing classes in scala
// `A => a A`. Yet, later, I had to have remove it later here
// because of the bug https://issues.scala-lang.org/browse/SI-9223
class FixedLenSeq(val syntax: Seq[Type]) extends Type(syntax) {
case class Val(val children: Seq[Value]) extends Value(this) {
def phenotype(io: IO) = io.writeAll(children)
}
def rnd(weights: Weights) = new Val(syntax map {_.rnd(weights)})
}
class VarLenExpr(val sym: String, val min: Int, val max: Int, val elemSyntax: () => Type) extends Type(sym) {
case class Val(val fixedLenSeq: Value) extends Value(this) {
def phenotype(io: IO) = fixedLenSeq.phenotype(io)
}
/*
Here, we created and registered new fixed length type. However, variabillity implies that
new type is created for every new individual, which result in too many table
records whereas only small fraction of types is used by population. Furthermore,
updating the table after boot time, during runtime, impedes multithreading.
Yes, adding new entries into the table when other threads use it is an obtacle.
It is therefore better not to register new fixed length types produced by
this variable-length expression.*/
/*def rnd(weights: Weights) = {
val list = List.fill(rint(max-min, min))(elemSyntax())
new Val(lazyCreate(list, new FixedLenSeq(list)).rnd(weights))
}*/
lazy val cache = elemSyntax()
def makeFixed(length: Int) = {
val list = List.fill(length)(cache)
val t = lazyCreate(list, new FixedLenSeq(list))
t.asInstanceOf[FixedLenSeq]
}
def rnd(weights: Weights) = new Val(makeFixed(rint(max-min, min)).rnd(weights))
}
// Call-by-name to prevent stackoverflow. Fortunately it does not happen if I
// call-by-value in the FixedLenSeq.
// I do not know why we need call-by-name in one case but not the other and
// why there is a bug there.
class Enum(lhs: String, val alternatives: () => Seq[Type]) extends Type(lhs) {
lazy val cached = alternatives()
case class Val(val child: Value) extends Value(this) {
def phenotype(io: IO) = child.phenotype(io)
}
def rnd(weights: Weights) = {
// val picked = iRnd(alternatives.length) // simply random
val roulette = cached.map {weights get _ match {
case Some(count) => Math.pow(cfactor, -count)
case None => 1
}}.toArray
val ball = Math.random * roulette.sum
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
val pickedType = cached(drop(0, ball))
val uw = Framework.enter(pickedType, weights)
new Val(pickedType.rnd(uw))
}
}
// Some types may be not loaded after start symbol parse. I tried to complete
// type loading here. Otherwise, worker threads will update the
// type map concurrently.
// This did not help however -- variable length type is created afterwards
// anyway. We therefore create a separate Generator for every thread.
{
val visited = mutable.Set[Type]()
def load(t: Type) {
if (visited.contains(t)) return
visited += t
t match {
case t: Enum => t alternatives() foreach load
case t: FixedLenSeq => t.syntax foreach load
case t: VarLenExpr => load(t.elemSyntax()) ; (t.min to t.max) map {t.makeFixed(_)}
case _ =>
}}
load(startSymbolSyntax)
initialized = true
}
case class IO(var indent: String = "", val out: PrintWriter = new PrintWriter(System.out, true)) {
def write(s: String) = out.write(s)
def finalWrite(individual: Value) = {individual.phenotype(this) ; out.close ; individual}
def writeAll(seq: Any*) { seq foreach { _ match {
case v:Value => v.phenotype(this)
case subseq: Seq[Any] => writeAll(subseq:_*)
case o => write(o.toString)
}}}
}
def rint(rangeLen: Int, from: Int = 0) = (Math.random * rangeLen).toInt + from
abstract class Value(val t: Type) {
List(1,2,3).map{identity}
def phenotype(io: IO) // converts into string amenable for evaluation
override def toString = "value of " + t.symKey
}
def corruptedCopy(self: Value, weights: Weights = Map()): Value = {
def descend(child: Value) = corruptedCopy(child, enter(self.t, weights))
def perturbeInt(title: String, cur: Int, min: Int, max: Int) = {
if (Math.random > 0.99) {
val desired = cur + rint(max-min, min)
val constrainedUpper = if (desired > max) max else desired ;
val result = if (constrainedUpper < min) min else constrainedUpper
//println (f"$title $cur => " + result) ;
result
} else cur
}
def perturbeArray(children: Seq[Value]) = children.map{child => descend(child)}
self.t match {
case _ : Const => self
case t : Range => t.Val(perturbeInt(t.sym, self.asInstanceOf[Range#Val].child, t.min, t.max))
case t : FixedLenSeq =>
new t.Val(perturbeArray(self.asInstanceOf[FixedLenSeq#Val].children))
case t : Enum => if (Math.random > .999) t.rnd(weights) else new t.Val(descend(self.asInstanceOf[Enum#Val].child))
case t : VarLenExpr =>
val children = self.asInstanceOf[VarLenExpr#Val].fixedLenSeq.asInstanceOf[FixedLenSeq#Val].children.toList
// here, we can either corrupt existing sequence, as fixed length or add/remove some elements.
// We can do the latter by injecting new random elements or copying other children
val desiredSize = perturbeInt(t.sym, children.size, t.min, t.max)
def drop[A](list: List[A], at: Int) = list.take(at) ++ list.drop(at+1)
def inject[A](list: List[A], item: A, at: Int) = list.take(at) ::: (item :: list.drop(at))
def resizeRandom(list: List[Value]): List[Value] = Math.signum(list.size compare desiredSize) match {
/*case 1 => resizeRandom{ val victim = rint(list.length);
//list.zipWithIndex.filter{case (a, i) => i != victim}.unzip._1
}*/
case 1 => resizeRandom{drop(list, at = rint(list.length))}
case -1 => val newEl = t.cache.rnd(weights)// instead of random we could take some parallel statement
resizeRandom(inject(list, newEl, at = rint(list.length) ))
case 0 => list
}
val copied = perturbeArray(resizeRandom(children)) // or corrupt first then resize?
t.Val(t.makeFixed(desiredSize).Val(copied))
}
}
type Weights = Map[Type, Int] // during value generation, weights limit the growth with convergence factor
def enter(picked: Type, weights: Weights) =
weights updated (picked, weights.getOrElse(picked, 0) + 1)
trait Visitor[Acc] {
def visit(weights: Weights, v: Value, acc: Acc): Acc = {
val sub: Acc = v.t match {
case _ : Const => acc
case _ : Range => acc
case _ : Enum => visit(weights, v.asInstanceOf[Enum#Val].child, acc)
case _ : VarLenExpr => visit(weights, v.asInstanceOf[VarLenExpr#Val].fixedLenSeq, acc)
case _ : FixedLenSeq => val weights2 = enter(v.t, weights)
v.asInstanceOf[FixedLenSeq#Val].children.foldLeft(acc){(acc, child) => visit(weights2, child, acc)}
}
visited(sub, v)
}
def visited(acc: Acc, v: Value): Acc
}
def crossOver(mother: Value, father: Value) {
val parent = if (Math.random < 0.5) mother else father
val flattened = new Visitor[Set[Value]] {
override def visited(acc: Set[Value], v: Value) = acc + v
}.visit(Map(), parent, Set())
val picked = flattened.toList(Math.random * flattened.size toInt)
println (flattened.mkString("\n"))
}
implicit def toPath(filename: String) = get(filename)
if (args.length < 2) {
/**
args(0) is a temp folder, where random programs are written before executed.
Makeing it ram saves the disk and ears. This does not improve performance though
http://stackoverflow.com/questions/354254/ramdrive-for-compiling-is-there-such-a-thing#comment46523768_354315
*/
println("Specify the temp folder and num of generations. Temp folder can be Ramdrive for speed.")
sys.exit(1)
}
val tempFolder = args(0) + "/"; new File(tempFolder).mkdir()
class EfficientBaos extends ByteArrayOutputStream(1024) {
def writeOut(out: OutputStream) {writeTo(out); out.close}
override def toString = new String(buf, 0, count)
}
class LogFile(name: String) {
def write(contents: String) = {
println(contents)
Files.write(Paths.get(name), (contents + "\n").getBytes(java.nio.charset.StandardCharsets.UTF_8), StandardOpenOption.APPEND)
}
println(name + " must be reset !!!!!")
Files.write(Paths.get(name), Array[Byte](), StandardOpenOption.TRUNCATE_EXISTING) // truncate on init
}
/* def assertFile[A](fn: String, ref: String) = {
val source = scala.io.Source.fromFile(fn) ; try assert(source.mkString.equals(ref), "invalid contents in " + fn) finally source.close()
}*/
val logFile = new LogFile("generations.txt")
var generation = 0
class Generator(generate: => Value) {
case class EvaluationRecord(val id: Int, val individual: Value, value: Long)
val population = mutable.MutableList[EvaluationRecord]()
var evaluation = 0
def nextEvaluationTask(report: Option[EvaluationRecord]) = synchronized {
report map { population += _}
if (population.size < POPULATION_SIZE) {evaluation += 1 ; Some(evaluation)} else None
}
object DeleteFinishedExecutablesDaemon extends java.util.Timer(true) {
def delete(file: File) = schedule(new java.util.TimerTask() { override def run() { file.delete }}, 1000)
}
case class Worker(i: Int) extends Thread("Worker_" + i) {
def sleep = Thread.sleep(10);
implicit def s2f(s: String) = new File(s)
@tailrec //bug https://github.com/scala-ide/scala-worksheet/issues/215 prevents execution
final def ensureRemove(f: File) {
f.delete
if (f.exists) { sleep ; ensureRemove(f); }
}
def evaluate(executable: String, baos: EfficientBaos) = {
@tailrec def compile {
ensureRemove(executable)
case class OutPrinter(title: String, in: InputStream) {
val br = new BufferedReader(new InputStreamReader(in))
def loop() {val read = br.readLine(); if (read != null) {
println(title + ": " + read)
loop}} ; loop
}
val io = new ProcessIO(
in => {baos.writeOut(in)}, // runs in separate thread
out => {OutPrinter("out", out)}, err => {OutPrinter("err", err)}
)
if (dump_C_files) baos.writeOut(new FileOutputStream(executable + ".c"))
//println("creating " + executable)
//val result = "gcc prog.c -o p.exe -lm" !
val cmd = "gcc -o "+executable+" -xc -"
val result = Process(cmd).run(io).exitValue()
if (result != 0) {
println("compiler '"+cmd+"' terminated with " + result + ". Retrying."); sleep ; compile
}
}
compile
val evalID = executable + " evaluated by " + getName +"/"+ iteration
val compiled = (arguments: String) => { // compiled can compute the fitness
val sb = new StringBuilder()
val p = Process(executable + " " + arguments).run(ProcessLogger(
line => sb.append(line).append('\n'),
line => {println("err: "+ line)})
) // start asynchronously
val f = Future(blocking(p.exitValue())) // wrap in Future
try {
//println("running")
Await.result(f, duration.Duration(exeTimeout, "millis"))
val response = sb.toString.replace("\n", "")
Some(response)
} catch {
case _: TimeoutException =>
println(evalID + " failed with TIMEOUT!")
p.destroy()
None
} finally {
//executable.delete // This has only 50% chance of success because exe file seems blocked
executable.deleteOnExit // ensure delete on java exit
DeleteFinishedExecutablesDaemon.delete(executable)
}
}
UserFitness.compute (evalID, compiled)
}
var iteration = 0
def continue(completedReport: Option[EvaluationRecord]) { nextEvaluationTask(completedReport) map { evalID => // map result will be empty in case of no more tasks
val individual = generate
val baos = new EfficientBaos ; makeIo(baos).finalWrite(individual)
val nextReport = evaluate(tempFolder +"gen" + generation + "-ind" + evalID + ".exe", baos) map {
case (value) => EvaluationRecord(evalID, individual, value)
}
iteration += 1 ; continue(nextReport)
}
}
override def run = continue(None)
}
val startTime = System.currentTimeMillis()
val threads = (1 to WORKER_THREADS) map {new Worker(_)}
threads foreach {_.start} ; threads foreach {_.join}
val best = population.reduceLeft((x,y) => if (x.value > y.value) x else y)
val evaluated = threads.map(_.iteration).sum
def variance(samples: Seq[Long]) = {
val avg = samples.sum / samples.length
val variance = samples.foldLeft(0.0) {(acc, x) => acc + Math.pow(x-avg,2)} / (samples.length-1)
(avg + " ±" + variance)
}
logFile.write("Generation " + generation + " has finished in " + (System.currentTimeMillis() - startTime) + " msec, " +
"evaluated " + evaluated + ", succeeded " + population.size
+ ", avg score " + (variance(population.map{_.value})) + ", id " + best.id + " got best score " + best.value)
makeIo(new FileOutputStream(tempFolder + "gen" + generation + "_best.c")).finalWrite(best.individual)
generation += 1
}
object Generation0 extends Generator(Framework.generate)
def nextGen(parents: Generator, finalGen: Int): Generator = if (generation < finalGen) {
//generate population by mutating a single best parent
//val picked = parents.best
val sorted = parents.population.sortWith(_.value < _.value)
val roulette = sorted.map{p => Math.pow(2, p.value)}
def picked = {
def drop(n: Int, sum: Double): Int = if (sum > 0) drop(n+1, sum-roulette(n)) else n-1
sorted(drop(0, Math.random * roulette.sum))
}
/*
println("parents " + sorted.map{_.value}) //; println (" roulette = "+roulette)
val selected = (1 to sorted.size) map {_ => picked.value}
println("selected for next generation: " + selected.sorted + " with variance " + parents.variance(selected))
*/
val generated = new Generator( Framework.corruptedCopy(picked.individual) )
nextGen(generated, finalGen)
} else parents
nextGen(Generation0, args(1).toInt)
}
output looks like
PROGRAM -> List(List(HEAD, BODY, TAIL))
BODY -> List(List({, INDENT++, EOL, STATEMENT_LN*, INDENT--, INDENT, }))
INT -> List(List(RANGE_-100_100), List(INT, +, INT), List(getMem(, INT, )), List(getArg(, RANGE_1_10, )))
BOOL -> List(List(0), List(1), List(BOOL, &&, BOOL), List(!(, BOOL, )), List(INT, ==, INT), List(INT, <, INT))
STATEMENT -> List(List(), List(setMem(, INT, ,, INT, )), List(while(, BOOL, ), BODY), List(if(, BOOL, ), BODY, else, BODY), List(setMem(, INT, ,,
STATEMENT_LN -> List(List(INDENT, STATEMENT, ;, EOL))
main instantiated HEAD for HEAD
main instantiated TAIL for TAIL
main instantiated EOL for EOL
main instantiated INDENT for INDENT
main instantiated INDENT++ for INDENT++
main instantiated INDENT-- for INDENT--
parseEnum PROGRAM
info: production PROGRAM produced a single-option alternative. This makes no sense.
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
main instantiated { for {
parseEnum STATEMENT_LN
info: production STATEMENT_LN produced a single-option alternative. This makes no sense.
parseEnum STATEMENT
main instantiated Framework$Enum@10d3326 for STATEMENT
main instantiated ; for ;
main instantiated Framework$FixedLenSeq@55dd0c for List(INDENT, Framework$Enum@10d3326, ;, EOL)
main instantiated Framework$VarLenExpr@455848 for STATEMENT_LN*
main instantiated } for }
main instantiated Framework$FixedLenSeq@1bd0f3b for List({, INDENT++, EOL, Framework$VarLenExpr@455848, INDENT--, INDENT, })
main instantiated Framework$FixedLenSeq@b5174b for List(HEAD, Framework$FixedLenSeq@1bd0f3b, TAIL)
Start sym = Framework$FixedLenSeq@b5174b
main instantiated for
main instantiated setMem( for setMem(
parseEnum INT
main instantiated Framework$Enum@1912c99 for INT
main instantiated , for ,
main instantiated ) for )
main instantiated Framework$FixedLenSeq@10ee7e5 for List(setMem(, Framework$Enum@1912c99, ,, Framework$Enum@1912c99, ))
main instantiated while( for while(
parseEnum BOOL
main instantiated Framework$Enum@19b2141 for BOOL
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
main instantiated Framework$FixedLenSeq@974e45 for List(while(, Framework$Enum@19b2141, ), Framework$FixedLenSeq@1bd0f3b)
main instantiated if( for if(
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
main instantiated else for else
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
main instantiated Framework$FixedLenSeq@ad3bc1 for List(if(, Framework$Enum@19b2141, ), Framework$FixedLenSeq@1bd0f3b, else, Framework$FixedLenSeq
main instantiated Range(RANGE_-100_100,-100,100) for RANGE_-100_100
main instantiated + for +
main instantiated Framework$FixedLenSeq@1af006c for List(Framework$Enum@1912c99, +, Framework$Enum@1912c99)
main instantiated getMem( for getMem(
main instantiated Framework$FixedLenSeq@132bc4a for List(getMem(, Framework$Enum@1912c99, ))
main instantiated getArg( for getArg(
main instantiated Range(RANGE_1_10,1,10) for RANGE_1_10
main instantiated Framework$FixedLenSeq@114a4c0 for List(getArg(, Range(RANGE_1_10,1,10), ))
main instantiated 0 for 0
main instantiated 1 for 1
main instantiated && for &&
main instantiated Framework$FixedLenSeq@46293d for List(Framework$Enum@19b2141, &&, Framework$Enum@19b2141)
main instantiated !( for !(
main instantiated Framework$FixedLenSeq@13be5ca for List(!(, Framework$Enum@19b2141, ))
main instantiated == for ==
main instantiated Framework$FixedLenSeq@1654521 for List(Framework$Enum@1912c99, ==, Framework$Enum@1912c99)
main instantiated < for <
main instantiated Framework$FixedLenSeq@1990a0c for List(Framework$Enum@1912c99, <, Framework$Enum@1912c99)
main instantiated Framework$FixedLenSeq@102f94e for List(Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c)
main instantiated Framework$FixedLenSeq@148a640 for List(Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c,
main instantiated Framework$FixedLenSeq@683a3e for List(Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c, Framework$FixedLenSeq@55dd0c,
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
parseEnum BODY
info: production BODY produced a single-option alternative. This makes no sense.
z:/1.exe evaluated by Worker_1/0 responds -69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/9.exe evaluated by Worker_9/0 responds 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/10.exe evaluated by Worker_10/0 responds 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/3.exe evaluated by Worker_3/0 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/16.exe evaluated by Worker_16/0 responds -45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/13.exe evaluated by Worker_13/0 responds -60 0 102 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 44
z:/14.exe evaluated by Worker_14/0 responds 1 0 0 0 0 0 0 -44 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/4.exe evaluated by Worker_7/0 responds 0 0 0 12 0 0 0 96 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/22.exe evaluated by Worker_4/1 responds 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/20.exe evaluated by Worker_12/1 responds -83 0 0 0 0 0 62 0 -83 0 0 0 0 0 0 0 0 0 0 0 with value = 45
z:/17.exe evaluated by Worker_1/1 responds -38 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/18.exe evaluated by Worker_9/1 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/24.exe evaluated by Worker_5/1 responds 0 8 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/29.exe evaluated by Worker_2/1 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/28.exe evaluated by Worker_14/1 responds 0 6 0 0 0 36 0 -4 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/31.exe evaluated by Worker_7/1 responds 71 0 -88 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/23.exe evaluated by Worker_3/1 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/30.exe evaluated by Worker_6/1 responds 6 0 104 0 6 0 20 -68 0 0 0 0 0 0 0 0 0 0 0 0 with value = 45
z:/35.exe evaluated by Worker_1/2 responds 61 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -75 0 0 with value = 43
z:/45.exe evaluated by Worker_3/2 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/33.exe evaluated by Worker_4/2 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/41.exe evaluated by Worker_7/2 responds 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/43.exe evaluated by Worker_11/2 responds 65 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/44.exe evaluated by Worker_8/2 responds 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/42.exe evaluated by Worker_15/2 responds 4 0 0 0 43 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/38.exe evaluated by Worker_10/2 responds -6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/40.exe evaluated by Worker_14/2 responds 0 -85 0 0 0 -69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 44
z:/47.exe evaluated by Worker_13/2 responds 50 0 0 0 0 0 0 0 0 0 0 0 0 0 -86 0 0 0 0 0 with value = 43
z:/48.exe evaluated by Worker_16/2 responds 68 0 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/51.exe evaluated by Worker_3/3 responds 0 0 0 0 0 0 0 0 0 -30 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/53.exe evaluated by Worker_7/3 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 with value = 40
z:/52.exe evaluated by Worker_4/3 responds -51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/46.exe evaluated by Worker_6/2 responds 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/49.exe evaluated by Worker_12/3 responds 0 0 -94 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/54.exe evaluated by Worker_5/3 responds 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/55.exe evaluated by Worker_11/3 responds 4 0 0 0 56 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/58.exe evaluated by Worker_9/3 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/57.exe evaluated by Worker_15/3 responds 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/66.exe evaluated by Worker_4/4 responds 8 0 -10 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/61.exe evaluated by Worker_13/3 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/59.exe evaluated by Worker_10/3 responds 0 0 73 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/65.exe evaluated by Worker_7/4 responds 8 0 0 0 0 0 0 0 -56 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/63.exe evaluated by Worker_2/3 responds -98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/62.exe evaluated by Worker_16/3 responds 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/64.exe evaluated by Worker_3/4 responds 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/68.exe evaluated by Worker_6/3 responds 7 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/70.exe evaluated by Worker_5/4 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/69.exe evaluated by Worker_12/4 responds 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/67.exe evaluated by Worker_1/4 responds 2 51 0 0 -47 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/71.exe evaluated by Worker_11/4 responds -36 0 0 0 0 0 0 1 0 0 0 66 0 0 0 0 0 0 0 0 with value = 43
z:/75.exe evaluated by Worker_13/4 responds 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/72.exe evaluated by Worker_9/4 responds -93 0 0 0 0 0 0 -93 0 0 0 0 0 0 0 0 0 0 0 0 with value = 44
z:/73.exe evaluated by Worker_15/4 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/79.exe evaluated by Worker_2/4 responds 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/80.exe evaluated by Worker_8/4 responds 12 0 0 0 0 0 0 0 0 0 0 0 60 0 0 0 0 0 0 0 with value = 42
z:/77.exe evaluated by Worker_14/4 responds 62 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/81.exe evaluated by Worker_16/4 responds 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/89.exe evaluated by Worker_9/5 responds 76 0 0 0 0 90 0 0 0 1 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/86.exe evaluated by Worker_1/5 responds 39 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/92.exe evaluated by Worker_8/5 responds 0 0 0 5 0 0 0 0 39 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/91.exe evaluated by Worker_2/5 responds 9 0 -98 0 0 0 0 0 6 0 0 0 0 0 2 0 0 0 0 0 with value = 42
z:/87.exe evaluated by Worker_11/5 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 with value = 40
z:/83.exe evaluated by Worker_6/4 responds -52 0 0 0 0 0 0 0 55 -40 0 0 0 0 0 0 0 0 0 0 with value = 45
z:/96.exe evaluated by Worker_3/6 responds 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/95.exe evaluated by Worker_16/5 responds 59 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/99.exe evaluated by Worker_7/6 responds 0 0 0 0 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/97.exe evaluated by Worker_10/5 responds -81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/103.exe evaluated by Worker_12/6 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/100.exe evaluated by Worker_1/6 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/104.exe evaluated by Worker_11/6 responds 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/101.exe evaluated by Worker_8/6 responds -34 -8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/109.exe evaluated by Worker_3/7 responds 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/106.exe evaluated by Worker_6/5 responds 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/107.exe evaluated by Worker_13/6 responds 3 0 0 -52 3 -63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 44
z:/108.exe evaluated by Worker_5/6 responds 35 0 0 88 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/115.exe evaluated by Worker_12/7 responds -20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/116.exe evaluated by Worker_14/6 responds 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/121.exe evaluated by Worker_16/7 responds 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/118.exe evaluated by Worker_1/7 responds 2 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/119.exe evaluated by Worker_11/7 responds -8 0 0 0 0 0 0 0 0 -43 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/125.exe evaluated by Worker_13/7 responds 8 0 0 0 0 0 0 0 1 7 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/129.exe evaluated by Worker_12/8 responds 11 0 -59 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/120.exe evaluated by Worker_8/7 responds 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/130.exe evaluated by Worker_14/7 responds 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/135.exe evaluated by Worker_6/7 responds 105 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/128.exe evaluated by Worker_9/8 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/136.exe evaluated by Worker_11/8 responds 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/127.exe evaluated by Worker_7/8 responds 6 0 -69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/133.exe evaluated by Worker_1/8 responds 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/131.exe evaluated by Worker_16/8 responds 0 0 0 0 -43 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/139.exe evaluated by Worker_12/9 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/147.exe evaluated by Worker_4/9 responds -78 0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/141.exe evaluated by Worker_2/8 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/148.exe evaluated by Worker_7/9 responds 4 5 0 0 59 0 0 0 0 0 0 0 0 0 0 -52 0 0 0 103 with value = 45
z:/140.exe evaluated by Worker_8/8 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/145.exe evaluated by Worker_3/9 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/150.exe evaluated by Worker_5/8 responds 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/151.exe evaluated by Worker_16/9 responds 7 54 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/144.exe evaluated by Worker_9/9 responds 15 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/153.exe evaluated by Worker_12/10 responds 10 0 0 -59 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 43
z:/155.exe evaluated by Worker_13/9 responds 0 0 0 0 0 0 0 0 31 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/149.exe evaluated by Worker_1/9 responds 9 0 0 0 0 0 0 0 0 96 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/158.exe evaluated by Worker_14/9 responds 2 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 41
z:/156.exe evaluated by Worker_4/10 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/157.exe evaluated by Worker_2/9 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/161.exe evaluated by Worker_3/10 responds 0 0 0 0 7 0 5 0 6 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/162.exe evaluated by Worker_5/9 responds 0 0 0 0 0 0 0 0 0 -68 0 0 0 0 0 0 0 0 0 0 with value = 42
z:/164.exe evaluated by Worker_16/10 responds 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/163.exe evaluated by Worker_11/10 responds 0 8 0 3 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 with value = 40
z:/165.exe evaluated by Worker_9/10 responds 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 with value = 40
finished in 5906 msec, evaluated 165, succeeded 110, avg score 255, best = (148,value of List(HEAD, Framework$FixedLenSeq@1bd0f3b, TAIL),45)
Generation 0 has finished in 5001 msec, evaluated 165, succeeded 112, avg score 41 ±1.8738738738738738, id 150 got best score 46
Generation 1 has finished in 2771 msec, evaluated 115, succeeded 115, avg score 45 ±1.4210526315789473, id 115 got best score 46
Generation 2 has finished in 2846 msec, evaluated 115, succeeded 115, avg score 45 ±1.1491228070175439, id 113 got best score 46
Generation 3 has finished in 2739 msec, evaluated 115, succeeded 115, avg score 45 ±1.0087719298245614, id 114 got best score 46
Generation 4 has finished in 2859 msec, evaluated 115, succeeded 115, avg score 45 ±1.0789473684210527, id 115 got best score 48
Generation 5 has finished in 2749 msec, evaluated 115, succeeded 115, avg score 47 ±1.0526315789473684, id 6 got best score 49
Generation 6 has finished in 2746 msec, evaluated 115, succeeded 115, avg score 48 ±1.2017543859649122, id 101 got best score 51
Generation 7 has finished in 2817 msec, evaluated 115, succeeded 115, avg score 50 ±1.3596491228070176, id 113 got best score 51
Generation 8 has finished in 2843 msec, evaluated 115, succeeded 115, avg score 50 ±1.0087719298245614, id 114 got best score 51
Generation 9 has finished in 2856 msec, evaluated 115, succeeded 115, avg score 50 ±1.131578947368421, id 115 got best score 51
Generation 10 has finished in 2914 msec, evaluated 115, succeeded 115, avg score 50 ±1.2017543859649122, id 115 got best score 51
Generation 11 has finished in 2758 msec, evaluated 115, succeeded 115, avg score 50 ±1.4736842105263157, id 89 got best score 52
Generation 12 has finished in 2824 msec, evaluated 115, succeeded 115, avg score 51 ±1.1491228070175439, id 73 got best score 53
Generation 13 has finished in 3018 msec, evaluated 116, succeeded 115, avg score 52 ±1.7543859649122806, id 116 got best score 53
Generation 14 has finished in 2891 msec, evaluated 115, succeeded 115, avg score 52 ±1.0263157894736843, id 113 got best score 54
Generation 15 has finished in 2783 msec, evaluated 115, succeeded 115, avg score 53 ±1.0175438596491229, id 115 got best score 54
Generation 16 has finished in 2963 msec, evaluated 115, succeeded 115, avg score 53 ±1.412280701754386, id 40 got best score 56
Generation 17 has finished in 2807 msec, evaluated 116, succeeded 115, avg score 55 ±1.0263157894736843, id 116 got best score 56
Generation 18 has finished in 2979 msec, evaluated 115, succeeded 115, avg score 55 ±1.9298245614035088, id 114 got best score 56
Raw
scoring_features.sc
/**
Scoring more features more than total sum of feature values. Individual
with one more, no matter how poorly developed, feature is scored more than
any other individual with well-developed features, which are known among
population.
It seems that new score has dramatically improved performance. Initially
fast progress slows down now exponentially, however, as more features
are discoveried. Experiment1 discovered 8 of 10 slots very quickly and
stuck. Here are best results after 100 generations
109 100 -100 107 -100 0 -105 0 -100 -100 with value = 328
106 100 -100 0 -100 0 -108 107 -100 -100 with value = 328
106 0 -100 107 -100 100 -108 0 -100 -100 with value = 328
It demonstrates that sexual recombination could transfer successful
features. to all alleles. However, _exhaustive scan_ could also
be successful.
Still to do: reduce feature weight once its carrier was selected
(made parent).
Regarding recombination,
One way would be to shuffle the pieces of genome. It would maintain the mess whereas we know that
the order (alleles) ismaintained in the human genome. On the other hand, we could maintain the
alleles by recombining corresponding pieces of the tree. We could identify correspondence traversing
both trees. This however will make distant creatures incompaible, if their trees mismatch
right away from the root. Order is destroyed in this case also and you will have to choose between
head and legs, likewise evolution is asexual.
Michael Lanes puts it this way: Since it is unlikely that sub-tree crossover will exchange sub-trees with similar position, size,
shape, or behaviour, most GP sub-tree crossovers will lead to child programs which are considerably less fit than their parents.
In essence, this happens because a component's context is recorded in terms of its position within a parse tree; and because sub-tree
crossover does not preserve the positions of components. Later in this thesis it will be argued that this failing is as much the
fault of the program's representation as it is the fault of the sub-tree crossover operator.
Replication can mix statements of single individual. But to produce statement list we must
crossover two of them. Everything seems fine: recombine single values (enum children, integer
ranges and constants) by choosing one of them or recombine sequences by crossingover.
The difficulty is however to crossover the children of the sequence. You loose the correspon-
dence between the children.
*/
object Framework extends App {
def userFitness(programId: String, programFunc: String => Option[String]): Option[Long] =
programFunc("0 1 2 3 4 5 6 7 8 9").map{response =>
val nonZeroes = response.split(' ').filterNot{_.equals("0")}.length
val value = response.length * nonZeroes
println(programId + " responds " + response + " with value = " + value)
value
} // program produces string output and we take its length if success
// the progress
Generation 0 has finished in 5209 msec, evaluated 146, succeeded 110, avg score 29 ±694.9357798165138, id 62 got best score 135
Generation 1 has finished in 3415 msec, evaluated 111, succeeded 111, avg score 132 ±162.0909090909091, id 55 got best score 140
Generation 2 has finished in 3610 msec, evaluated 111, succeeded 110, avg score 135 ±14.779816513761467, id 102 got best score 140
Generation 3 has finished in 3548 msec, evaluated 112, succeeded 111, avg score 138 ±28.28181818181818, id 108 got best score 140
Generation 4 has finished in 3571 msec, evaluated 111, succeeded 111, avg score 138 ±80.30909090909091, id 87 got best score 180
Generation 5 has finished in 3639 msec, evaluated 112, succeeded 111, avg score 177 ±153.51818181818183, id 108 got best score 180
Generation 6 has finished in 3548 msec, evaluated 112, succeeded 111, avg score 178 ±53.67272727272727, id 102 got best score 186
Generation 7 has finished in 3519 msec, evaluated 111, succeeded 111, avg score 181 ±137.37272727272727, id 107 got best score 186
Generation 8 has finished in 3744 msec, evaluated 113, succeeded 111, avg score 184 ±36.04545454545455, id 112 got best score 186
Generation 9 has finished in 3836 msec, evaluated 111, succeeded 111, avg score 183 ±266.04545454545456, id 107 got best score 186
Generation 10 has finished in 3883 msec, evaluated 111, succeeded 111, avg score 183 ±149.71818181818182, id 108 got best score 186
Generation 11 has finished in 4256 msec, evaluated 114, succeeded 111, avg score 183 ±231.14545454545456, id 112 got best score 186
Generation 12 has finished in 4272 msec, evaluated 113, succeeded 111, avg score 183 ±117.91818181818182, id 112 got best score 186
Generation 13 has finished in 4347 msec, evaluated 111, succeeded 111, avg score 185 ±3.190909090909091, id 69 got best score 192
Generation 14 has finished in 4837 msec, evaluated 111, succeeded 111, avg score 187 ±33.3, id 108 got best score 192
Generation 15 has finished in 4618 msec, evaluated 112, succeeded 111, avg score 189 ±85.35454545454546, id 112 got best score 192
Generation 16 has finished in 4876 msec, evaluated 112, succeeded 111, avg score 191 ±20.89090909090909, id 112 got best score 192
Generation 17 has finished in 5100 msec, evaluated 113, succeeded 111, avg score 191 ±17.59090909090909, id 61 got best score 198
Generation 18 has finished in 5675 msec, evaluated 111, succeeded 111, avg score 192 ±40.91818181818182, id 110 got best score 198
Generation 19 has finished in 5368 msec, evaluated 112, succeeded 111, avg score 193 ±335.8090909090909, id 109 got best score 198
Generation 20 has finished in 5529 msec, evaluated 111, succeeded 111, avg score 197 ±37.32727272727273, id 107 got best score 198
Generation 21 has finished in 5409 msec, evaluated 111, succeeded 111, avg score 196 ±56.25454545454546, id 56 got best score 204
Generation 22 has finished in 6551 msec, evaluated 112, succeeded 111, avg score 199 ±89.88181818181818, id 47 got best score 238
Generation 23 has finished in 6023 msec, evaluated 112, succeeded 111, avg score 236 ±45.945454545454545, id 45 got best score 245
Generation 24 has finished in 6350 msec, evaluated 111, succeeded 111, avg score 238 ±136.0909090909091, id 111 got best score 245
Generation 25 has finished in 6733 msec, evaluated 112, succeeded 111, avg score 242 ±91.50909090909092, id 34 got best score 252
Generation 26 has finished in 7043 msec, evaluated 111, succeeded 111, avg score 247 ±78.91818181818182, id 111 got best score 252
Generation 27 has finished in 6675 msec, evaluated 112, succeeded 111, avg score 249 ±111.31818181818181, id 112 got best score 252
Generation 28 has finished in 6581 msec, evaluated 112, succeeded 110, avg score 249 ±97.80733944954129, id 112 got best score 252
Generation 29 has finished in 8057 msec, evaluated 111, succeeded 111, avg score 250 ±49.11818181818182, id 109 got best score 252
Generation 30 has finished in 7211 msec, evaluated 113, succeeded 111, avg score 250 ±73.47272727272727, id 103 got best score 252
Generation 31 has finished in 7244 msec, evaluated 113, succeeded 111, avg score 248 ±358.3545454545455, id 111 got best score 252
Generation 32 has finished in 7738 msec, evaluated 112, succeeded 111, avg score 249 ±79.45454545454545, id 81 got best score 259
Generation 33 has finished in 7591 msec, evaluated 112, succeeded 111, avg score 252 ±174.8909090909091, id 112 got best score 259
Generation 34 has finished in 8530 msec, evaluated 114, succeeded 111, avg score 254 ±416.06363636363636, id 114 got best score 259
Generation 35 has finished in 7870 msec, evaluated 111, succeeded 111, avg score 254 ±202.55454545454546, id 100 got best score 259
Generation 36 has finished in 8357 msec, evaluated 114, succeeded 111, avg score 255 ±359.42727272727274, id 111 got best score 259
Generation 37 has finished in 8734 msec, evaluated 113, succeeded 111, avg score 257 ±82.01818181818182, id 92 got best score 304
Generation 38 has finished in 9275 msec, evaluated 112, succeeded 111, avg score 299 ±256.9, id 111 got best score 304
Generation 39 has finished in 9713 msec, evaluated 112, succeeded 111, avg score 300 ±186.1, id 88 got best score 312
Generation 40 has finished in 10248 msec, evaluated 111, succeeded 111, avg score 306 ±151.8272727272727, id 104 got best score 312
Generation 41 has finished in 10025 msec, evaluated 113, succeeded 111, avg score 303 ±1106.909090909091, id 110 got best score 312
Generation 42 has finished in 10659 msec, evaluated 111, succeeded 111, avg score 306 ±515.4272727272727, id 111 got best score 312
Generation 43 has finished in 9551 msec, evaluated 111, succeeded 111, avg score 303 ±1129.6545454545455, id 109 got best score 312
Generation 44 has finished in 10315 msec, evaluated 111, succeeded 111, avg score 310 ±68.9090909090909, id 87 got best score 320
Generation 45 has finished in 12383 msec, evaluated 113, succeeded 111, avg score 312 ±246.21818181818182, id 113 got best score 320
Generation 46 has finished in 10353 msec, evaluated 111, succeeded 111, avg score 319 ±29.154545454545456, id 111 got best score 320
Generation 47 has finished in 11621 msec, evaluated 114, succeeded 111, avg score 314 ±295.6090909090909, id 114 got best score 320
Generation 48 has finished in 12337 msec, evaluated 112, succeeded 111, avg score 314 ±260.1363636363636, id 112 got best score 320
Generation 49 has finished in 12271 msec, evaluated 114, succeeded 111, avg score 315 ±350.59090909090907, id 112 got best score 320
Generation 50 has finished in 12454 msec, evaluated 112, succeeded 111, avg score 312 ±1000.709090909091, id 109 got best score 320
Generation 51 has finished in 12688 msec, evaluated 112, succeeded 111, avg score 313 ±359.4909090909091, id 112 got best score 320
Generation 52 has finished in 11872 msec, evaluated 111, succeeded 111, avg score 314 ±529.5272727272727, id 111 got best score 320
Generation 53 has finished in 12514 msec, evaluated 112, succeeded 111, avg score 314 ±514.9636363636364, id 109 got best score 320
Generation 54 has finished in 13183 msec, evaluated 112, succeeded 111, avg score 316 ±236.92727272727274, id 18 got best score 328
Generation 55 has finished in 12311 msec, evaluated 112, succeeded 111, avg score 318 ±401.6454545454545, id 111 got best score 328
Generation 56 has finished in 11401 msec, evaluated 112, succeeded 111, avg score 321 ±370.56363636363636, id 110 got best score 328
Generation 57 has finished in 12167 msec, evaluated 111, succeeded 111, avg score 321 ±404.08181818181816, id 111 got best score 328
Generation 58 has finished in 11402 msec, evaluated 112, succeeded 111, avg score 318 ±776.5545454545454, id 108 got best score 328
Generation 59 has finished in 12237 msec, evaluated 114, succeeded 111, avg score 323 ±222.15454545454546, id 114 got best score 328
Generation 60 has finished in 19012 msec, evaluated 113, succeeded 111, avg score 323 ±233.79090909090908, id 111 got best score 328
Generation 61 has finished in 12529 msec, evaluated 111, succeeded 111, avg score 319 ±472.8818181818182, id 111 got best score 328
Generation 62 has finished in 14718 msec, evaluated 111, succeeded 111, avg score 320 ±650.7, id 110 got best score 328
Generation 63 has finished in 14273 msec, evaluated 113, succeeded 111, avg score 321 ±442.8909090909091, id 112 got best score 328
Generation 64 has finished in 14766 msec, evaluated 117, succeeded 111, avg score 317 ±577.8272727272728, id 117 got best score 328
Generation 65 has finished in 13962 msec, evaluated 112, succeeded 111, avg score 318 ±509.3545454545455, id 112 got best score 328
Generation 66 has finished in 14781 msec, evaluated 113, succeeded 110, avg score 318 ±850.743119266055, id 108 got best score 328
Generation 67 has finished in 14441 msec, evaluated 113, succeeded 111, avg score 321 ±458.6727272727273, id 113 got best score 328
Generation 68 has finished in 13639 msec, evaluated 112, succeeded 110, avg score 319 ±677.3394495412844, id 110 got best score 328
Generation 69 has finished in 13775 msec, evaluated 115, succeeded 111, avg score 322 ±284.73636363636365, id 114 got best score 328
Generation 70 has finished in 13586 msec, evaluated 113, succeeded 111, avg score 322 ±303.6181818181818, id 111 got best score 328
Generation 71 has finished in 14029 msec, evaluated 113, succeeded 111, avg score 321 ±320.1545454545454, id 111 got best score 328
Generation 72 has finished in 26056 msec, evaluated 114, succeeded 110, avg score 319 ±449.5596330275229, id 112 got best score 328
Generation 73 has finished in 15070 msec, evaluated 118, succeeded 110, avg score 319 ±852.0642201834862, id 116 got best score 328
Generation 74 has finished in 15267 msec, evaluated 114, succeeded 111, avg score 325 ±134.38181818181818, id 114 got best score 328
Generation 75 has finished in 17750 msec, evaluated 119, succeeded 111, avg score 321 ±327.4, id 119 got best score 328
Generation 76 has finished in 19013 msec, evaluated 123, succeeded 108, avg score 321 ±387.1588785046729, id 121 got best score 328
Generation 77 has finished in 14986 msec, evaluated 116, succeeded 110, avg score 318 ±971.9357798165138, id 110 got best score 328
Generation 78 has finished in 14885 msec, evaluated 114, succeeded 111, avg score 324 ±211.04545454545453, id 103 got best score 328
Generation 79 has finished in 16143 msec, evaluated 115, succeeded 110, avg score 321 ±365.2201834862385, id 113 got best score 328
Generation 80 has finished in 16218 msec, evaluated 116, succeeded 110, avg score 322 ±375.697247706422, id 116 got best score 328
Generation 81 has finished in 15601 msec, evaluated 113, succeeded 111, avg score 317 ±1109.0727272727272, id 113 got best score 328
Generation 82 has finished in 17352 msec, evaluated 115, succeeded 111, avg score 316 ±1299.9454545454546, id 112 got best score 328
Generation 83 has finished in 16663 msec, evaluated 116, succeeded 110, avg score 321 ±444.5045871559633, id 111 got best score 328
Generation 84 has finished in 15785 msec, evaluated 113, succeeded 111, avg score 318 ±1102.418181818182, id 110 got best score 328
Generation 85 has finished in 17770 msec, evaluated 115, succeeded 111, avg score 319 ±977.5818181818182, id 113 got best score 328
Generation 86 has finished in 17460 msec, evaluated 114, succeeded 110, avg score 320 ±479.48623853211006, id 114 got best score 328
Generation 87 has finished in 16527 msec, evaluated 113, succeeded 109, avg score 320 ±518.9166666666666, id 111 got best score 328
Generation 88 has finished in 18250 msec, evaluated 116, succeeded 111, avg score 322 ±386.08181818181816, id 112 got best score 328
Generation 89 has finished in 24639 msec, evaluated 124, succeeded 111, avg score 321 ±870.9636363636364, id 122 got best score 328
Generation 90 has finished in 21538 msec, evaluated 120, succeeded 111, avg score 320 ±698.1545454545454, id 120 got best score 328
Generation 91 has finished in 20942 msec, evaluated 117, succeeded 109, avg score 317 ±816.7870370370371, id 113 got best score 328
Generation 92 has finished in 19662 msec, evaluated 113, succeeded 109, avg score 320 ±424.64814814814815, id 112 got best score 328
Generation 93 has finished in 21899 msec, evaluated 120, succeeded 111, avg score 323 ±255.6909090909091, id 119 got best score 328
Generation 94 has finished in 22920 msec, evaluated 121, succeeded 111, avg score 320 ±389.4, id 119 got best score 328
Generation 95 has finished in 23886 msec, evaluated 128, succeeded 111, avg score 320 ±429.5181818181818, id 126 got best score 328
Generation 96 has finished in 26102 msec, evaluated 127, succeeded 109, avg score 319 ±461.037037037037, id 125 got best score 328
Generation 97 has finished in 24644 msec, evaluated 132, succeeded 111, avg score 322 ±344.8, id 132 got best score 328
Generation 98 has finished in 24668 msec, evaluated 125, succeeded 111, avg score 320 ±1109.2636363636364, id 125 got best score 328
Generation 99 has finished in 23591 msec, evaluated 120, succeeded 111, avg score 322 ±333.07272727272726, id 120 got best score 328
@valtih1978
Copy link
Author

Instead of

get _ match {
			case Some(count) => Math.pow(cfactor, -count)
			case None => 1
		}

getOrElse(_, 0) map (count => Math.pow(cfactor, -count)) can be used.

@valtih1978
Copy link
Author

Instead of

List(
		"statement, println ( int ) | if ( bool ) body ",
		"int, intLiteral | int int",
		"bool, true | false | bool and bool | not bool | int == int | int < int"
		)
		
		// Parse into LHS => List[List[String]], where RHS is list of alternaitves
		// and every alternative is a seq of tokens
		. map {production =>
			val firstComma = production.indexOf(',')
			val lhs = production.substring(0, firstComma).trim
			val rhs = production.substring(firstComma+1).split('|')
			(lhs, rhs.toList map (_.trim.split("\\s+").toList map {_.trim}) )
		} toMap

use

Map(
	
		"S" -> "void main() body",
		"statement" -> "println ( int ) | if ( bool ) body ",
		"int" -> "byte-literal | byte-literal | int int",
		"bool" -> "true | false | bool and bool | not bool | int == int | int < int"
		
	).mapValues (_.split('|').map(_.trim.split("\\s+")))

@valtih1978
Copy link
Author

Don't use nested cases like

	lhs match {
		case "intLiteral" => acc append ' ' append "%+d".format(rnd(256, -128))
		case "body" =>
			val indent = path.map {_ => ' '} mkString ""
			(0 to rnd(10)).foldLeft(acc append "{\n"){case(acc, _) => gen(path, acc append indent append ' ', "statement") append "\n"} append indent append "}"
		case _ => syntax get (lhs) match {
			case Some(rhs) => {
				val picked = rnd(rhs.length)
				rhs(picked).foldLeft(acc){case (acc, lhs) => gen(lhs :: path, acc, lhs)}
			}
			case None => acc append ' ' append lhs
		}

	}

Instead, use

lhs match {
		case "byte-literal" => acc append ' ' append "%+d".format(rnd(256, -128))
		case "body" =>
			val indent2 = indent + ' '
			(1 to rnd(3)).foldLeft(acc append " {\n"){(acc, _) =>
				gen(acc append indent, "statement", indent2) append "\n"
			} . append(indent + "}")
			
		case _ if grammar contains lhs => val alternatives = grammar(lhs)
			val alternative = choose(alternatives: _*)
			alternative.foldLeft(acc){(acc, sym) => gen(acc, sym, indent)}
		case lhs => acc append ' ' append lhs
	}

This will lookup the syntax map twice, once for contains and, secondly, for get but performance is not paramaout here.

@valtih1978
Copy link
Author

valtih1978 commented Sep 17, 2017 •
edited

In 8.multithreaded, probably move individual generation into nextEvaluationTask. Individual = generate is called right after nexEvaluationTask.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment