Created
March 20, 2022 13:31
-
-
Save VizGhar/d59d47423360195f6723a48dc62666d3 to your computer and use it in GitHub Desktop.
Solution for 8 (or n) queen problem solved using genetic algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]}") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment