kotlin genetic

main.kt

import kotlinx.coroutines.experimental.CommonPool
import kotlinx.coroutines.experimental.launch
import kotlinx.coroutines.experimental.runBlocking
import kotlinx.coroutines.experimental.sync.Mutex
import java.util.*
import kotlin.system.measureTimeMillis

// BY peheje@github

fun stringToIntArray(str: String): IntArray {
    return IntArray(str.length, { i -> str[i].toInt() })
}

fun intArrayToString(ints: IntArray): String {
    return Array(ints.size, { i -> ints[i].toChar() }).joinToString("")
}

class Specimen {
    private var data = IntArray(0)
    private var target = IntArray(0)
    var fitness: Long = 0

    constructor(target: IntArray) {
        this.target = target
        this.data = IntArray(target.size, { randomchar() })
        calcfitness()
    }

    private constructor(characters: IntArray, fitness: Long, target: IntArray) {
        this.data = characters
        this.fitness = fitness
        this.target = target
    }

    fun calcfitness() {
        fitness = data.indices.count { target[it] == data[it] }.toLong()
        fitness *= fitness
        fitness *= fitness
    }

    override fun toString(): String {
        return "Specimen(data='${intArrayToString(data)}' fitness=$fitness)"
    }

    fun copy(): Specimen {
        return Specimen(this.data.copyOf(), this.fitness, this.target)
    }

    fun mutate(mutatefreq: Double) {
        for (i in data.indices) if (Math.random() < mutatefreq)
            data[i] = randomchar()
    }

    fun crossover(pool: Array<Specimen>, crossoverfreq: Double) {
        val mate = pool[(Math.random() * pool.size).toInt()]
        for (i in 0 until data.size) if (Math.random() < crossoverfreq)
            data[i] = mate.data[i]
    }

    companion object {
        private val chars = ('a'..'z') + ' '
        private fun randomchar(): Int {
            return chars[(Math.random() * chars.size).toInt()].toInt()
        }

        fun pick(arr: Array<Specimen>): Specimen {
            var sum = 0L
            val wheel = LongArray(arr.size, { i -> sum += arr[i].fitness; sum })

            val r = (Math.random() * sum).toLong()
            var idx = wheel.binarySearch(r)
            if (idx < 0) {
                idx = -idx - 1
            }

            return arr[idx].copy()
        }
    }
}

suspend fun multipick2(pool: Array<Specimen>): Array<Specimen> {
    val mutex = Mutex()
    val picks = mutableListOf<Specimen>()
    val jobs = List(pool.size) {
        launch(CommonPool) {
            val pick = Specimen.pick(pool)  // Computationally expensive operation
            mutex.lock()
            try { picks.add(pick) }
            finally { mutex.unlock() }
        }
    }
    jobs.forEach { it.join() }
    return picks.toTypedArray()
}

suspend fun multipick(pool: Array<Specimen>): Array<Specimen> {
    val picks = Collections.synchronizedList(ArrayList<Specimen>())
    pool.toList().parallelStream().forEach { picks.add(Specimen.pick(pool)) }
    return picks.toTypedArray()
}

fun main(args: Array<String>) = runBlocking {

    val mutateprop = 0.1    // Prop that specimen will mutate
    val mutatefreq = 0.1    // Prop that character will mutate

    val crossoverprop = 0.4 // Prop that specimen will crossover
    val crossoverfreq = 0.4 // Prop that character will crossover

    val target = stringToIntArray("the time when the computer was a gray and tiresome box on the floor is a long time ago a longer time ago than far far away in a galaxy of the guardians")
    val size = 1_000         // Poolsize
    val iter = 5_000

    // Algorithm go
    val ms = measureTimeMillis {
        var pool = Array(size, { Specimen(target) })
        for (i in 0 until iter) {
            //pool = Array(size, { Specimen.pick(pool) })   // Single threaded version
            pool = multipick(pool)                          // Multi threaded version
            if (i % 100 == 0) println("$i: " + pool.maxBy { it.fitness })
            pool.forEach { if (Math.random() < mutateprop) it.mutate(mutatefreq) }
            pool.forEach { if (Math.random() < crossoverprop) it.crossover(pool, crossoverfreq) }
            pool.forEach { it.calcfitness() }
        }
        println(pool.maxBy { it.fitness })
    }
    println("time $ms ms")
}