Genetic Algorithm Sample
Blind Watch Maker 1
Find Words
Fractal Benchmark
Genetic Algorithm
Gtk Source Editor
Hex Dump
Simple English Parser
Word Count
Uses the genetic algorithm (GA) to solve various problems.

Run with -turbo for maximum speed as in:

    cobra -turbo GeneticAlgorithm.cobra



    Written by Charles Esterbrook
    Based in part on


    [ ] 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.

        var _nextSerialNum = 1_000

        var _random as Random?
        pro random as Random
            Shared random number generator.
                if _random is nil, _random = Random()
                return _random to !
                _random = value

    cue init
        __serialNum = _nextSerialNum
        _nextSerialNum += 1
    get serialNum from __serialNum as int

    def toString as String is override
        """ Invoke .toString; override .innerString. """
        return '[]([.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.

        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

        .populationSize >= 4
        .tournamentSize >= 1
        .crossoverRate  >= 0 and .crossoverRate <= 1
        .mutationRate   >= 0 and .mutationRate <= 1
        .maxGenerations >= 0
        .scoreGoal      >  0
    cue 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<of Member>()

    cue init(size as int, memberType as Type)
        for i in size, _members.add(memberType())

    cue init(member as Member)
            .members.toList == [member]
            .count == 1
    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)

    def examine
        Examine the population for the best and worst members as well compute
        the average score.
            .count > 0
            .best and .best.score >= .averageScore
            .worst and .worst.score <= .averageScore
            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
    def dump
        for i, m in _members.numbered
            print '[i] ' stop

    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<of Member> is abstract
            other is not this
            result.count == 2
            result[0] is not this and result[0] is not other
            result[1] is not this and result[1] 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<of Member> is override
        t = List<of Member>()
        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

        def randomBits(length as int) as int[]
            bits = int[](length)
            for i in length, bits[i] = % 2
            return bits

    var _bits as int[]
    cue init(bits as int[])
        require bits.length >= 2
        ensure .bits is bits
        _bits = bits

    cue init(length as int)
        """ Initializes the bitstring with `length` random bits. """
        require length >= 2

    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
            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<of Member> 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<of Member>
        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<of Member>()
        type = .typeOf
        childA, childB = type(a), type(b), other), other)
        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<of int>
            result.count == 2
            result[1] >= result[0]
            left =, .length-2)
            right =, .length-1)
            return [left, right]

    def repair(parent1 as BitstringMember, parent2 as BitstringMember)
        """ Override this method to fix duplicated genes, if necessary. """

class MaximizeOnesMember inherits BitstringMember
    A problem-specific member to maximize the number of ones (1s)
    that appear in the genome.
    cue init

    cue init(bits as int[])

    cue init(length as int)

    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?)
            params.populationSize > 0 or (pop and pop.count > 0)
            _params = params
            BaseObject.random = if(params.randomSeed, Random(params.randomSeed), Random())
            _pop = pop ? Population(params.populationSize, params.memberType)

    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 (
   and >= .params.scoreGoal)

    def evaluate
        for m in _pop.members, m.evaluate

    def step
        for member in _pop.members, member.incAge
        _generation += 1

    def generateNextPopulation
        thisPop = .population
        nextPop = Population(
        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)
                offspring = [mate1.copy to Member]
            for member in offspring
        while nextPop.count > thisPop.count
        _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
        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

class Program

    def main

    def maximizeOnesExample
        params = Params.default
        params.maxGenerations = 100
        params.memberType = MaximizeOnesMember
        params.scoreGoal = 50
        engine = Engine(params)
        # testing:
        assert engine.generation < 100
        assert == 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<of T>

    def joined(sep as String) as String
        sb = StringBuilder()
        sep2 = ''
        for item in this
            sep2 = sep
        return sb.toString