Solution for 8 (or n) queen problem solved using genetic algorithm

n-queens-problem-genetic_algorithm.kt

import kotlin.math.absoluteValue
import kotlin.random.Random

const val chromosomeSize = 8
const val mutationProbability = 0.05 // each block of chromosome mutates with this probability
const val populationSize = 1000      // this many individuals will be in each generation
const val keepNBest = 200            // this many best individuals will be taken without change to next gen
const val tournamentSize = 3         // this many individuals will fight in tournament

val random = Random(System.currentTimeMillis())

fun randomIndividual() = (0 until chromosomeSize).map { (0 until chromosomeSize).random(random) }
var population = (0 until populationSize).map { randomIndividual() }.sortedBy { it.fitness }

val List<Int>.fitness: Int get() {
    var result = 0
    for (i in 0 until size - 1) {
        for (j in i + 1 until size) {
            if (get(i) == get(j)) result++
            if ((get(i) - get(j)).absoluteValue == j - i) result++
        }
    }
    return result
}

fun mutation(individual: List<Int>) =
    individual.map { if (Math.random() <= mutationProbability) (0 until chromosomeSize).random(random) else it }

fun crossover(individual1: List<Int>, individual2: List<Int>) =
    random.nextInt(chromosomeSize).let { individual1.subList(0, it) + individual2.subList(it, chromosomeSize) }

fun tournament() =
    (1..tournamentSize).map { population.random(random) }.minByOrNull { it.fitness }!!

fun nextPopulation() {
    val best = (0 until keepNBest).map { population[it] }
    val kids = (keepNBest until populationSize).map {
        val individual1 = tournament()
        val individual2 = tournament()
        val child = crossover(individual1, individual2)
        mutation(child)
    }
    population = (best + kids).sortedBy { it.fitness }
}

fun main() {
    var generation = 0
    while (population[0].fitness != 0) {
        println("Generation $generation : fitness = ${population[0].fitness} : best = ${population[0]}")
        nextPopulation()
        generation++
    }
    println("Generation $generation : result : ${population[0]}")
}