Genetic Algorithm Sample
 ```""" Uses the genetic algorithm (GA) to solve various problems. Run with -turbo for maximum speed as in: cobra -turbo GeneticAlgorithm.cobra Links http://en.wikipedia.org/wiki/Genetic_algorithm http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) http://en.wikipedia.org/wiki/Mutation_(genetic_algorithm) http://en.wikipedia.org/wiki/Travelling_salesman_problem Credit Written by Charles Esterbrook Based in part on http://code.activestate.com/recipes/199121/ TODO [ ] Record with each member the generation it was created in [ ] implement the travelling salesman problem (TSP) [ ] Solve a "minimize/maximize function" problem where bitstring is broken into numeric args """ @number float class BaseObject """ The base class of all other classes in this library/program. Provides basics like serial numbers, .random (shared) and .innerString. """ shared var _nextSerialNum = 1_000 var _random as Random? pro random as Random """ Shared random number generator. """ get if _random is nil, _random = Random() return _random to ! set _random = value cue init base.init __serialNum = _nextSerialNum _nextSerialNum += 1 get serialNum from __serialNum as int def toString as String is override """ Invoke .toString; override .innerString. """ return '[.typeOf.name]([.serialNum][.innerString])' def innerString as String """ Subclasses can override to: return base.innerString + ', foo=[value1], bar=[value2]' """ return '' def dump print this class Params inherits BaseObject """ Contains the parameters for a GA run. """ shared get default as Params p = Params() p.populationSize = 1_000 p.tournamentSize = 5 p.crossoverRate = 0.90 p.mutationRate = 0.03 p.maxGenerations = 100 p.randomSeed = 0 return p invariant .populationSize >= 4 .tournamentSize >= 1 .crossoverRate >= 0 and .crossoverRate <= 1 .mutationRate >= 0 and .mutationRate <= 1 .maxGenerations >= 0 .scoreGoal > 0 cue init base.init _populationSize = 10 _tournamentSize = 2 _scoreGoal = 1.0 pro populationSize from var as int pro tournamentSize from var as int pro crossoverRate from var as number pro mutationRate from var as number pro maxGenerations from var as int pro randomSeed from var as int """ A .randomSeed of zero is ignored in which the stream of random numbers will be different on each run. """ pro memberType from var as Type? """ The type of the members of the population. Used when creating a new members for an initial population. """ pro scoreGoal from var as number """ The score you want to achieve among the population. Once reached, evolution will stop. """ class Population inherits BaseObject """ Holds a population of members and provides population-level operations such as reporting the best and worst member. """ var _members = List() cue init(size as int, memberType as Type) base.init for i in size, _members.add(memberType()) cue init(member as Member) ensure .members.toList == [member] .count == 1 body base.init _members.add(member) get count as int ensure result > 0 return _members.count get members as Member* for m in _members, yield m get best from var as Member? get worst from var as Member? get averageScore from var as number def add(m as Member) _members.add(m) def examine """ Examine the population for the best and worst members as well compute the average score. """ require .count > 0 ensure .best and .best.score >= .averageScore .worst and .worst.score <= .averageScore body total = 0.0 best as Member? worst as Member? for m in .members if best is nil or best.score < m.score, best = m if worst is nil or worst.score > m.score, worst = m total += m.score _averageScore = total / .count _best, _worst = best, worst def randomMember(r as Random) as Member require .count > 0 return _members.random(r) def removeLast _members.removeLast def dump base.dump for i, m in _members.numbered print '[i] ' stop m.dump def report print 'best =', .best print 'worst =', .worst print 'avg =', .averageScore class Member inherits BaseObject is abstract get age from var as int """ Returns the age in number of generations that this member has survived. """ pro score from var as number """ The score represents how well this member performs or how "good" it is. """ def evaluate as number is abstract """ Computes the score of this member. """ ensure .score == result def copy as dynamic ensure result is not this return .memberwiseClone def crossover(other) as List is abstract require other is not this ensure result.count == 2 result.typeOf.isKindOf(.typeOf) result.typeOf.isKindOf(.typeOf) result is not this and result is not other result is not this and result is not other def incAge _age += 1 def mutate(rate as number) as bool is abstract """ Potentially mutates the member. Returns true if member is mutated. """ require rate >= 0 def innerString as String return base.innerString + ', age=[.age], score=[.score]' class DummyMember inherits Member """ A DummyMember does nothing practical on its own, but can be used for simple unit tests. """ def evaluate as number is override return 1 def crossover(other) as List is override t = List() t.add(this) t.add(this) return t def mutate(rate as number) as bool is override return false class BitstringMember inherits Member is abstract """ A member whose genome is comprised of 1s and 0s that are subsequently translated/interpreted as one or more phenotypes. TODO: add util method to convert a range of the bitstring to an integer """ shared def randomBits(length as int) as int[] bits = int[](length) for i in length, bits[i] = .random.next % 2 return bits var _bits as int[] cue init(bits as int[]) require bits.length >= 2 ensure .bits is bits base.init _bits = bits cue init(length as int) """ Initializes the bitstring with `length` random bits. """ require length >= 2 .init(.randomBits(length)) get bits from var get length as int ensure result >= 2 return _bits.length def copy as dynamic and ensure result.bits is not .bits body copy = base.copy to BitstringMember n = .length bits = int[](n) for i in n, bits[i] = _bits[i] copy._bits = bits return copy def crossover(other) as List is override """ Override this method to customize the crossover operation. """ return .twoPointCrossover(other) def mutate(rate as number) as bool is override """ Override this method to customize the crossover operation. """ return .randomMutation(rate) def twoPointCrossover(other as BitstringMember) as List left, right = _pickPivots n = .length a, b = int[](n), int[](n) for i in left a[i], b[i] = _bits[i], other._bits[i] for i in left : right a[i], b[i] = other._bits[i], _bits[i] for i in right : n a[i], b[i] = _bits[i], other._bits[i] list = List() type = .typeOf childA, childB = type(a), type(b) childA.repair(this, other) childB.repair(this, other) list.add(childA) list.add(childB) return list def randomMutation(rate as number) as bool didMutate = false for i in .length if .random.nextDouble < rate _bits[i] = if(_bits[i], 0, 1) didMutate = true return didMutate def _pickPivots as List ensure result.count == 2 result >= result body left = .random.next(1, .length-2) right = .random.next(left, .length-1) return [left, right] def repair(parent1 as BitstringMember, parent2 as BitstringMember) """ Override this method to fix duplicated genes, if necessary. """ pass class MaximizeOnesMember inherits BitstringMember """ A problem-specific member to maximize the number of ones (1s) that appear in the genome. """ cue init base.init(50) cue init(bits as int[]) base.init(bits) cue init(length as int) base.init(length) def evaluate as number is override total = 0 for b in _bits, total += b _score = total return total def innerString as String return base.innerString + ', ' + (for b in .bits get '01'[b]).joined('') class Engine inherits BaseObject """ An engine runs the GA using parameters and a population. It pushes the population from one generation to the next, applying genetic operators. """ var _params as Params? var _pop as Population var _generation as int cue init(params as Params) .init(params, nil) cue init(params as Params, pop as Population?) require params.memberType params.populationSize > 0 or (pop and pop.count > 0) body base.init _params = params BaseObject.random = if(params.randomSeed, Random(params.randomSeed), Random()) _pop = pop ? Population(params.populationSize, params.memberType) .evaluate get generation as int ensure result >= 0 return _generation get params from var get population from _pop def run while not .isDone, .step def isDone as bool return .generation >= .params.maxGenerations or ( .population.best and .population.best.score >= .params.scoreGoal) def evaluate for m in _pop.members, m.evaluate .population.examine def step .generateNextPopulation for member in _pop.members, member.incAge _generation += 1 .population.examine .report def generateNextPopulation thisPop = .population nextPop = Population(.population.best) while nextPop.count < thisPop.count mate1 = .select if _random.nextDouble < .params.crossoverRate while true mate2 = .select if mate2 is not mate1, break offspring = mate1.crossover(mate2) else offspring = [mate1.copy to Member] for member in offspring member.mutate(.params.mutationRate) member.evaluate nextPop.add(member) while nextPop.count > thisPop.count nextPop.removeLast _pop = nextPop def select as Member """ Calls .tournamentSelect by default. A subclass can override this to implement a different selection method. """ return .tournamentSelect def tournamentSelect as Member require .population.count > 0 # This is an interesting method because for quality control, # it's not clear what useful `ensure` could be added to it, # nor is it clear what kind of unit test would prove that # tournament selection was working as expected. # Have ideas? Post them to # http://cobra-language.com/forums/viewforum.php?f=4 best as Member? for i in .params.tournamentSize competitor = .population.randomMember(.random) if best is nil or best.score < competitor.score best = competitor return best to ! def report print 'gen =', .generation .population.report print class Program def main .maximizeOnesExample def maximizeOnesExample params = Params.default params.maxGenerations = 100 params.memberType = MaximizeOnesMember params.scoreGoal = 50 engine = Engine(params) engine.run # testing: assert engine.generation < 100 assert engine.population.best.score == 50 print 'done.' extend Type def isKindOf(t as Type) as bool """ Returns true if this type is the same as or a subclass of the given type. TODO: Should this return true if t is an interface that this type implements? """ return t is this or .isSubclassOf(t) extend IList def joined(sep as String) as String sb = StringBuilder() sep2 = '' for item in this sb.append(sep2) sb.append(CobraCore.printStringMaker.makeString(item)) sep2 = sep return sb.toString ```