GA作为一种机器学习方法，结合了达尔文的进化理论，实际操作与基因组合类似，基本模型的难度不高，比较适合初学者。
简介
遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
基本概念
Genotype (基因型)
基因型，是指某一生物个体全部基因组合的总称。在遗传算法中，可以用一串二进制表示一个染色体，而每一位二进制代表一个基因。（在本文中，用若干个双精度浮点数[碱基]组成一个基因，再由若干基因组成一个染色体。）
Phenotype (表现型)
可以被直观观察到的个体特征，由基因型决定。例如 AaBb 的豌豆代表绿色圆粒，而 aaBb 代表黄色圆粒。
Population (种群)
种群指同一时间生活在一定自然区域内，同种生物的所有个体。种群中的个体并不是机械地集合在一起，而是彼此可以交配，并通过繁殖将各自的基因传给可育后代。
在遗传算法中，由多个个体组成一个种群，每个个体都有它们各自的染色体。
Fitness (适应度)
在基因算法的迭代中，需要有一个衡量个体好坏的标准。对于高适应度的个体，一般认为它更接近实验预期，从而这个个体在种群的自由交配中拥有更高被选中作为父代的概率。
随着算法的迭代，个体的适应度应该会逐渐提高，最后趋近于某个值，当达到实验预期时，即可停止迭代，取出最好的实验结果。
Selection (选择)
在种群的自由交配之前，先计算出每一个个体的适应度，然后计算出被选中的概率 p = 个体适应度 / 所有个体适应度之和。
例如现在有10个个体，它们的适应度分别为 [1, 5, 4, 9, 3, 4, 7, 5, 12, 11]，则它们被选中作为父代的概率分别为 [1/61, 5/61, 4/61, 9/61, 3/61, 4/61, 7/61, 5/61, 12/61, 11/61]
Crossover (交叉)
为了产生一对新个体，通常选择双亲的一部分染色体进行互换。
例如双亲 A 与 B 有如下染色体（5个基因）：
A：0010 0110 0101 0100 1011
B：1101 0001 1010 1001 0011
单点交叉
单点交叉即为随机选择一个基因位置，交换双亲的染色体。
例如在第三基因交换，则产生的一对子代如下（加粗部分来自个体 B）：
子代1：0010 0110 0101 1001 0011
子代2：1101 0001 1010 0100 1011
双点交叉
顾名思义，截取一部分基因进行交换，例如在第一与第三基因交换（加粗部分来自个体 B）：
子代1：0010 0001 1010 1001 1011
子代2：1101 0110 0101 0100 0011
Mutation (突变)
突变是基因组DNA分子发生的突然的、可遗传的变异现象。突变具有不确定性，并且所有染色体都有机会发生基因突变。
在遗传算法中，一般选择染色体上的某个基因进行突变，例如翻转单个或多个二进制位。
Kotlin 语言实现
由于 kotlin 的语言特性，对象都是指针引用，因此需要准备一个深拷贝的接口：
interface DeepCopyable<T> {
fun deepCopy(): T
}基本对象
基因：
基因由多个双精度浮点数组成，称为碱基（Nucelobase）。
class GenePiece : DeepCopyable<GenePiece> {
private val nucleonBases: MutableList<Double> = mutableListOf()
fun addNucleonBases(vararg nucleonBases: Double) {
this.nucleonBases.addAll(nucleonBases.toList())
}
fun setNucleonBase(index: Int, newValue: Double) {
this.nucleonBases[index] = newValue
}
fun getNucleonBases(): List<Double> = this.nucleonBases
infix fun compare(another: GenePiece): Boolean {
if (this.nucleonBases.size != another.nucleonBases.size) {
return false
}
var v = true
for (i in 0..<this.nucleonBases.size) {
val a = this.nucleonBases[i]
val b = another.getNucleonBases()[i]
if (a != b) {
v = false
break
}
}
return v
}
override fun deepCopy(): GenePiece {
val t = GenePiece()
this.nucleonBases.forEach {
t.addNucleonBases(it)
}
return t
}
}染色体：
在遗传算法中，一般认为一条染色体由一个DNA分子组成，而一个DNA分子上可以有多个基因（Gene）。
class Chromosome : DeepCopyable<Chromosome> {
private val genePieces: MutableList<GenePiece> = mutableListOf()
fun addGenes(genePieces: Iterable<GenePiece>) {
addGenes(*genePieces.toList().toTypedArray())
}
fun addGenes(vararg genePiece: GenePiece) {
this.genePieces.addAll(genePiece.toList())
}
fun setGene(index: Int, gene: GenePiece) {
this.genePieces[index] = gene
}
fun getGenePieceSize(): Int = this.genePieces.size
fun getGenes(): List<GenePiece> = this.genePieces.toList()
infix fun compare(another: Chromosome): Boolean {
if (this.genePieces.size != another.genePieces.size) {
return false
}
var v = true
for (i in 0..<this.genePieces.size) {
val a = this.genePieces[i]
val b = another.getGenes()[i]
if (!(a compare b)) {
v = false
break
}
}
return v
}
override fun deepCopy(): Chromosome {
val t = Chromosome()
this.genePieces.forEach {
t.addGenes(it.deepCopy())
}
return t
}
}上面两个类都有一个 compare 方法，用于比较两个对象是否一致，这里主要的目的是判断基因是否一致。
交叉
在双亲交配时，染色体交叉可以有多种方式，先定义一个 CrossoverAlgorithm 抽象类，并且实现多种交叉方式。
abstract class CrossoverAlgorithm {
fun crossover(parentChromosomes: Pair<Chromosome, Chromosome>): Pair<Chromosome, Chromosome> {
val a = parentChromosomes.first
val b = parentChromosomes.second
if (a.getGenePieceSize() == 0 || b.getGenePieceSize() == 0) {
throw IllegalStateException("Length of chromosome cannot be zero")
}
if (a.getGenePieceSize() != b.getGenePieceSize()) {
throw IllegalStateException("Length of chromosome a (${a.getGenePieceSize()}) is not equal to length of chromosome b (${b.getGenePieceSize()})")
}
return crossover(a, b, a.getGenePieceSize())
}
abstract fun crossover(a: Chromosome, b: Chromosome, geneSize: Int): Pair<Chromosome, Chromosome>
}单点交叉
class SinglePointCrossover : CrossoverAlgorithm() {
override fun crossover(a: Chromosome, b: Chromosome, geneSize: Int): Pair<Chromosome, Chromosome> {
val selectedIndex = (1..<geneSize).random()
val offspringAGenes = a.getGenes().take(selectedIndex) + b.getGenes().drop(selectedIndex)
val offspringBGenes = b.getGenes().take(selectedIndex) + a.getGenes().drop(selectedIndex)
val offspringA = Chromosome().apply {
addGenes(offspringAGenes)
}
val offspringB = Chromosome().apply {
addGenes(offspringBGenes)
}
return Pair(offspringA, offspringB)
}
}双点交叉
class TwoPointCrossover : CrossoverAlgorithm() {
override fun crossover(a: Chromosome, b: Chromosome, geneSize: Int): Pair<Chromosome, Chromosome> {
// Ensure there are at least 2 genes for crossover
if (geneSize < 2) {
throw IllegalArgumentException("Gene size must be at least 2 for two-point crossover.")
}
// Randomly select two crossover points, ensuring selectedIndex1 < selectedIndex2
val selectedIndex1 = (0..<geneSize - 1).random() // last valid index for selectedIndex1 is geneSize - 2
val selectedIndex2 = (selectedIndex1 + 1..<geneSize).random() // selectedIndex2 must be greater than selectedIndex1
// Offspring A's genes:
// [0..selectedIndex1) from A, [selectedIndex1..selectedIndex2) from B, [selectedIndex2..geneSize) from A
val offspringAGenes = a.getGenes().take(selectedIndex1) +
b.getGenes().subList(selectedIndex1, selectedIndex2) +
a.getGenes().drop(selectedIndex2)
// Offspring B's genes:
// [0..selectedIndex1) from B, [selectedIndex1..selectedIndex2) from A, [selectedIndex2..geneSize) from B
val offspringBGenes = b.getGenes().take(selectedIndex1) +
a.getGenes().subList(selectedIndex1, selectedIndex2) +
b.getGenes().drop(selectedIndex2)
// Create new chromosomes for the offspring
val offspringA = Chromosome().apply {
addGenes(offspringAGenes)
}
val offspringB = Chromosome().apply {
addGenes(offspringBGenes)
}
// Return the offspring pair
return Pair(offspringA, offspringB)
}
}变异
和交叉一样，定义一个抽象类，并实现多种变异方法。
interface MutationAlgorithm {
fun mutate(chromosome: Chromosome): Chromosome
}单基因突变：
class RandomMutationAlgorithm(val generateMutateValue: () -> Double) : MutationAlgorithm {
override fun mutate(chromosome: Chromosome): Chromosome {
val tChromosome = chromosome.deepCopy()
val mutateGeneIndex = (0..<tChromosome.getGenePieceSize()).random()
val mutateGene = tChromosome.getGenes()[mutateGeneIndex]
val mutateIndex = (0..<mutateGene.getNucleonBases().size).random()
mutateGene.setNucleonBase(mutateIndex, generateMutateValue())
tChromosome.setGene(mutateGeneIndex, mutateGene)
return tChromosome
}
}个体
有了基因和染色体，接下来可以构建个体对象了，一个个体可以拥有多个染色体。
为了拓展性，这里把个体类定义成了抽象类。
abstract class Individual : DeepCopyable<Individual> {
private val chromosomes: MutableList<Chromosome> = mutableListOf()
fun addChromosomes(chromosomes: Iterable<Chromosome>) {
this.chromosomes.addAll(chromosomes.toList())
}
fun addChromosomes(vararg chromosomes: Chromosome) {
this.chromosomes.addAll(chromosomes.toList())
}
fun getChromosomes(): List<Chromosome> = this.chromosomes.toList()
fun setChromosome(index: Int, chromosome: Chromosome) {
this.chromosomes[index] = chromosome
}
abstract fun defineChromosomesCount(): Int
infix fun compare(another: Individual): Boolean {
if (this.chromosomes.size != another.getChromosomes().size) {
return false
}
var v = true
for (i in 0..<this.chromosomes.size) {
val a = this.chromosomes[i]
val b = another.getChromosomes()[i]
if (!(a compare b)) {
v = false
break
}
}
return v
}
}由于个体的染色体数总是确定的，因此由 Individual 的实现类来决定个体拥有多少个染色体，必须实现 defineChromosomesCount() 方法。
种群
首先定义一个种群的接口类，定义一些基本的方法：
interface IPopulation<I: Individual> {
/**
* 计算个体的适应度
*
* @param individual 个体
* @return 个体适应度
*/
fun calculateFitness(individual: I): Double
/**
* 构造新的个体, 用于子代个体对象的构造
*
* @param chromosomes 新个体的染色体
* @return 新个体对象
*/
fun buildNewIndividual(chromosomes: List<Chromosome>): I
/**
* 当发生染色体交叉时, 决定交叉的方式
*
* @param chromosomes 待交叉的两条染色体
* @return 交叉方式
*/
fun determineCrossoverAlgorithm(chromosomes: Pair<Chromosome, Chromosome>): CrossoverAlgorithm
/**
* 当发生染色体交叉时, 决定突变的方式
*
* @param chromosome 待突变的染色体
* @return 突变方式
*/
fun determineMutationAlgorithm(chromosome: Chromosome): MutationAlgorithm
/**
* 获取突变概率, 当新的种群产生后, 所有个体的所有染色体按此概率进行突变
*
* @param chromosome 待突变的染色体
* @return 突变概率
*/
fun getMutationProbability(chromosome: Chromosome): Double
}接下来实现这个接口：
abstract class Population<I: Individual>(
private val populationDelegate: IPopulation<I>
) : IPopulation<I> by populationDelegate {
private val individuals: MutableList<I> = mutableListOf()
/**
* 将当前种群中的所有个体替换成 initIndividuals 中的个体
*
* @param initIndividuals 种群个体
*/
fun initPopulation(initIndividuals: Iterable<I>) {
if (initIndividuals.map { it.defineChromosomesCount() }.toSet().size != 1) {
throw IllegalStateException("Chromosomes count of every individual must be the same")
}
this.individuals.clear()
this.individuals.addAll(initIndividuals)
}
/**
* 计算当前种群所有个体的适应度
*
* @return List<Pair<个体, 个体适应度>>
*/
fun calculateFitness(): List<Pair<I, Double>> {
return this.individuals.zip(this.individuals.map { calculateFitness(it) })
}
/**
* 获取当前种群的精英个体, 即按适应度排名取最高的前几个个体
*
* @param count 数量
* @return 精英个体
*/
fun getElites(count: Int): List<I> {
return calculateFitness().toMutableList()
.sortedByDescending { it.second }
.take(count)
.map { it.first }
}
/**
* 产生由下一代个体组成的新种群
*
* @param elitesCount 需要从上一代保留精英数量
* @param newGenerationIndividualsCount 新一代的总个体数, 一般与最初的种群个体数量相同
*/
fun nextGeneration(elitesCount: Int = 1, newGenerationIndividualsCount: Int = this.individuals.size) {
if (elitesCount > this.individuals.size) {
throw IllegalStateException("Elites count should be less than the size of current individuals")
}
if (elitesCount >= newGenerationIndividualsCount) {
throw IllegalStateException("Meaningless calculation when the elites count larger than the size of next generation")
}
// 选择
val populationFitness = this.individuals.map { calculateFitness(it) }
// 计算种群各个体被选中的概率分子
val populationSelectionProbability = populationFitness.map { ceil(it * 100).toInt() }
// 双亲将在 selection 中随机抽取, 按照 populationSelectionProbability 中的概率分子, 产生对应数量的个体组成 selection 数组
// 例如 populationSelectionProbability 为 [41, 16, 85, 79], 则 selection 数组中应该有 41 个 0, 16 个 1, 85 个 2...
// 若从 selection 中随机抽取, 则 0 号个体被选中的概率为 41 / 221
val selection = mutableListOf<Int>()
populationSelectionProbability.forEachIndexed { index, count ->
for (i in 0..<count) {
selection.add(index)
}
}
// 上一代种群中的精英个体
val elites = getElites(elitesCount)
// 新一代种群的所有个体
val tNewGeneration = mutableListOf<I>()
// 计算需要选出多少对双亲
val parentCount = ceil(newGenerationIndividualsCount / 2.0).toInt()
// 随机选择一定数量的双亲, 产生的一对子代个体放入 tNewGeneration 中
for (i in 0..<parentCount) {
val fatherIndex = randomInt(selection.size)
var motherIndex = randomInt(selection.size)
// 阻止拥有相同染色体以及基因的个体交配
while (individuals[selection[fatherIndex]] compare individuals[selection[motherIndex]]) {
motherIndex = randomInt(selection.size)
}
val (father, mother) = listOf(
this@Population.individuals[selection[fatherIndex]],
this@Population.individuals[selection[motherIndex]]
)
// 交叉
val chromosomesOfChildA = mutableListOf<Chromosome>()
val chromosomesOfChildB = mutableListOf<Chromosome>()
father.getChromosomes().forEachIndexed { index, chromosome ->
val chromosomes = chromosome to mother.getChromosomes()[index]
// 决定染色体交叉方式
val crossoverAlgorithm = determineCrossoverAlgorithm(chromosomes)
val children = crossoverAlgorithm.crossover(chromosomes)
chromosomesOfChildA.add(children.first)
chromosomesOfChildB.add(children.second)
}
// 将产生的新的一对子代个体放入 tNewGeneration 中
tNewGeneration.add(populationDelegate.buildNewIndividual(chromosomesOfChildA))
tNewGeneration.add(populationDelegate.buildNewIndividual(chromosomesOfChildB))
}
val newGeneration = tNewGeneration.sortedBy {
// 按适应度升序排列新的个体
populationDelegate.calculateFitness(it)
}.toMutableList().run {
// 基因突变
this.map {
it.apply {
it.getChromosomes().forEachIndexed { index, chromosome ->
// 如果这条染色体突变事件发生 则将突变的染色体替换原有的染色体
if (Random((1..Int.MAX_VALUE).random()).nextDouble() <= populationDelegate.getMutationProbability(chromosome)) {
// 决定突变方式
val mutationAlgorithm = populationDelegate.determineMutationAlgorithm(chromosome)
// 产生突变染色体
val mutatedChromosome = mutationAlgorithm.mutate(chromosome)
// 替换原有染色体
this.setChromosome(index, mutatedChromosome)
}
}
}
}.toMutableList()
this.toMutableList()
}.run {
// 抛弃适应度最低的 elitesCount 个个体
this.drop(elitesCount).toMutableList()
}.run {
// 将 elitesCount 个精英个体直接复制到新的种群中
this.addAll(elites)
this.toMutableList()
}.run {
// 若新的种群中出现拥有相同染色体与基因的个体 只保留其中一个 其余所有个体的所有染色体强制发生变异
for (i in 0..<this.size) {
val individual = this[i]
for (j in (i + 1)..<this.size) {
val tIndividual = this[j]
if (individual compare tIndividual) {
val newChromosomes = mutableListOf<Chromosome>()
tIndividual.getChromosomes().forEach { chromosome ->
newChromosomes.add(populationDelegate.determineMutationAlgorithm(chromosome).mutate(chromosome))
}
this[j] = buildNewIndividual(newChromosomes)
}
}
}
this
}
// 调试输出信息
val nextGenerationMap = with(newGeneration.sortedByDescending { calculateFitness(it) }) {
this.zip(this.map { populationDelegate.calculateFitness(it) })
}
nextGenerationMap.forEachIndexed { index, (individual, fitness) ->
println("${index}: $fitness : ${individual.getChromosomes().map { it.getGenes().map { it.getNucleonBases() }}}")
}
// 替换当前种群为新产生的种群
initPopulation(newGeneration)
}
}测试
实验简介
定义实验个体的表现型为三种任意RGB颜色。
众所周知，一个RGB颜色由三个[0, 255]的数组成。因此这个个体的应该有三种不同的基因，每个基因由三个碱基组成，一个基因编码一种颜色。
现在为了简化问题，将这三种基因编码在同一条染色体上，即这个个体只有一条染色体。
而基因则扩展到9个，每个基因仅包含一个碱基，而这九个基因按顺序编码三种颜色的RGB值。
现在实验的预期是产生一个颜色按顺序为红绿蓝纯色的个体，即染色体基因为 [255 0 0 0 255 0 0 0 255] 的个体。
个体与种群实现
种群是一个抽象类，一些核心的方法定义在接口中，现在需要实现一个个体类和种群类。
首先实现一个单染色体个体：
class SingleChromosomeIndividual : Individual() {
override fun defineChromosomesCount(): Int {
return 1
}
override fun deepCopy(): SingleChromosomeIndividual {
val t = SingleChromosomeIndividual()
this.getChromosomes().forEach {
t.addChromosomes(it.deepCopy())
}
return t
}
}接着是单染色体个体的种群：
class SingleChromosomePopulation(populationDelegate: IPopulation<SingleChromosomeIndividual>)
: Population<SingleChromosomeIndividual>(populationDelegate)种群比较简单，只需要指定种群的个体泛型即可，相关接口方法委托给使用者。
适应度函数
三种颜色分别计算适应度，下面是单个颜色的适应度函数：
val fxFitness = fun (rgbColor: List<Double>, target: List<Int>): Double {
val r = rgbColor[0]
val g = rgbColor[1]
val b = rgbColor[2]
val tR = target[0]
val tG = target[1]
val tB = target[2]
return (((255 - abs(tR - r)) + (255 - abs(tG - g)) + (255 - abs(tB - b))) / (3 * 255))
}经过上面的公式计算，可以得到对于单个颜色，适应度范围为 [0, 1]。
实验种群创建
有了适应度函数，接下来就可以正式开始创建实验种群了。
随机个体生成
val populationIndividuals = mutableListOf<SingleChromosomeIndividual>()
for (i in 1..10) {
val individual = SingleChromosomeIndividual().apply {
val chromosome = Chromosome().apply {
for (j in 1..9) {
this.addGenes(
GenePiece().apply {
this.addNucleonBases(Random(i * j).nextInt(256).toDouble())
}
)
}
}
this.addChromosomes(chromosome)
}
populationIndividuals.add(individual)
}
println("Initial population:")
populationIndividuals.forEach {
println(it.getChromosomes()[0].getGenes().map { it.getNucleonBases() })
}适应度计算
override fun calculateFitness(individual: SingleChromosomeIndividual): Double {
val c1 = individual.getChromosomes()[0]
val a = c1.getGenes().take(3).map { it.getNucleonBases()[0] }
val b = c1.getGenes().drop(3).take(3).map { it.getNucleonBases()[0] }
val c = c1.getGenes().drop(6).map { it.getNucleonBases()[0] }
val p1 = fxFitness(a, listOf(255, 0, 0))
val p2 = fxFitness(b, listOf(0, 255, 0))
val p3 = fxFitness(c, listOf(0, 0, 255))
return (p1 + p2 + p3) / 3
}分别计算各颜色的适应度并求和平均，最终得到一个 [0, 1] 的数表示个体的适应度。
新个体构建
override fun buildNewIndividual(chromosomes: List<Chromosome>): SingleChromosomeIndividual {
return SingleChromosomeIndividual().apply {
chromosomes.forEach {
this.addChromosomes(it.deepCopy())
}
}
}决定交叉类型
override fun determineCrossoverAlgorithm(chromosomes: Pair<Chromosome, Chromosome>): CrossoverAlgorithm {
return listOf(
SinglePointCrossover(),
TwoPointCrossover()
).random()
}发生染色体交叉时，两种方式的概率各50%。
决定突变类型
override fun determineMutationAlgorithm(chromosome: Chromosome): MutationAlgorithm {
return listOf(
RandomMutationAlgorithm {
Random((0..Int.MAX_VALUE).random()).nextInt(256).toDouble()
}
).random()
}基因突变概率
override fun getMutationProbability(chromosome: Chromosome): Double {
return 0.01
}突变概率不宜过高，突变有很大可能会导致个体的适应度大幅降低，但突变可以提高基因多样性。
然后把上面的override函数组合起来，得到一个种群类：
val population = SingleChromosomePopulation(object : IPopulation<SingleChromosomeIndividual> {
// override funtions
})然后将最初随机生成的个体添加到种群中：
population.initPopulation(populationIndividuals)开始迭代：
val generationsCount = 100
for (i in 1..generationsCount) {
println("========== $i ==========")
population.nextGeneration()
}完整实验代码
class SingleChromosomePopulationTest {
@Test
fun test() {
val populationIndividuals = mutableListOf<SingleChromosomeIndividual>()
for (i in 1..10) {
val individual = SingleChromosomeIndividual().apply {
val chromosome = Chromosome().apply {
for (j in 1..9) {
this.addGenes(
GenePiece().apply {
this.addNucleonBases(Random(i * j).nextInt(256).toDouble())
}
)
}
}
this.addChromosomes(chromosome)
}
populationIndividuals.add(individual)
}
println("Initial population:")
populationIndividuals.forEach {
println(it.getChromosomes()[0].getGenes().map { it.getNucleonBases() })
}
val fxFitness = fun (rgbColor: List<Double>, target: List<Int>): Double {
val r = rgbColor[0]
val g = rgbColor[1]
val b = rgbColor[2]
val tR = target[0]
val tG = target[1]
val tB = target[2]
return (((255 - abs(tR - r)) + (255 - abs(tG - g)) + (255 - abs(tB - b))) / (3 * 255))
}
val population = SingleChromosomePopulation(object : IPopulation<SingleChromosomeIndividual> {
override fun calculateFitness(individual: SingleChromosomeIndividual): Double {
val c1 = individual.getChromosomes()[0]
val a = c1.getGenes().take(3).map { it.getNucleonBases()[0] }
val b = c1.getGenes().drop(3).take(3).map { it.getNucleonBases()[0] }
val c = c1.getGenes().drop(6).map { it.getNucleonBases()[0] }
val p1 = fxFitness(a, listOf(255, 0, 0))
val p2 = fxFitness(b, listOf(0, 255, 0))
val p3 = fxFitness(c, listOf(0, 0, 255))
return (p1 + p2 + p3) / 3
}
override fun buildNewIndividual(chromosomes: List<Chromosome>): SingleChromosomeIndividual {
return SingleChromosomeIndividual().apply {
chromosomes.forEach {
this.addChromosomes(it.deepCopy())
}
}
}
override fun determineCrossoverAlgorithm(chromosomes: Pair<Chromosome, Chromosome>): CrossoverAlgorithm {
return listOf(
SinglePointCrossover(),
TwoPointCrossover()
).random()
}
override fun determineMutationAlgorithm(chromosome: Chromosome): MutationAlgorithm {
return listOf(
RandomMutationAlgorithm {
Random((0..Int.MAX_VALUE).random()).nextInt(256).toDouble()
}
).random()
}
override fun getMutationProbability(chromosome: Chromosome): Double {
return 0.01
}
})
population.initPopulation(populationIndividuals)
val generationsCount = 100
for (i in 1..generationsCount) {
println("========== $i ==========")
population.nextGeneration()
}
}
}实验结果
先看最初的种群，共10个个体：
Initial population:
[[35.0], [216.0], [129.0], [8.0], [175.0], [92.0], [245.0], [172.0], [3.0]]
[[216.0], [8.0], [92.0], [172.0], [248.0], [40.0], [124.0], [52.0], [112.0]]
[[129.0], [92.0], [3.0], [40.0], [213.0], [112.0], [23.0], [20.0], [233.0]]
[[8.0], [172.0], [40.0], [52.0], [192.0], [20.0], [160.0], [70.0], [202.0]]
[[175.0], [248.0], [213.0], [192.0], [187.0], [195.0], [179.0], [102.0], [65.0]]
[[92.0], [40.0], [112.0], [20.0], [195.0], [202.0], [57.0], [254.0], [46.0]]
[[245.0], [124.0], [23.0], [160.0], [179.0], [57.0], [85.0], [222.0], [167.0]]
[[172.0], [52.0], [20.0], [70.0], [102.0], [254.0], [222.0], [180.0], [148.0]]
[[3.0], [112.0], [233.0], [202.0], [65.0], [46.0], [167.0], [148.0], [164.0]]
[[248.0], [192.0], [195.0], [102.0], [162.0], [82.0], [100.0], [12.0], [120.0]]第一子代：
========== 1 ==========
0: 0.7908496732026143 : [[[129.0], [92.0], [3.0], [40.0], [213.0], [112.0], [23.0], [20.0], [233.0]]]
1: 0.7755991285403049 : [[[245.0], [124.0], [23.0], [160.0], [179.0], [57.0], [23.0], [20.0], [233.0]]]
2: 0.6701525054466231 : [[[92.0], [40.0], [112.0], [20.0], [162.0], [82.0], [100.0], [12.0], [120.0]]]
3: 0.6631808278867102 : [[[216.0], [8.0], [92.0], [172.0], [248.0], [40.0], [124.0], [148.0], [112.0]]]
4: 0.6470588235294118 : [[[129.0], [92.0], [3.0], [40.0], [213.0], [112.0], [85.0], [222.0], [167.0]]]
5: 0.5359477124183006 : [[[175.0], [248.0], [213.0], [102.0], [162.0], [82.0], [100.0], [12.0], [120.0]]]
6: 0.5355119825708061 : [[[172.0], [52.0], [20.0], [70.0], [175.0], [92.0], [245.0], [172.0], [3.0]]]
7: 0.44313725490196076 : [[[248.0], [192.0], [195.0], [102.0], [195.0], [202.0], [57.0], [254.0], [46.0]]]
8: 0.42483660130718953 : [[[248.0], [192.0], [195.0], [192.0], [187.0], [195.0], [179.0], [102.0], [65.0]]]
9: 0.4139433551198257 : [[[3.0], [112.0], [233.0], [202.0], [65.0], [46.0], [167.0], [52.0], [164.0]]]观察到第一子代最高的适应度为 0.79085，最低适应度为 0.41394。
第十子代：
========== 10 ==========
0: 0.869281045751634 : [[[245.0], [124.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
1: 0.8605664488017428 : [[[245.0], [124.0], [23.0], [40.0], [248.0], [40.0], [23.0], [31.0], [233.0]]]
2: 0.8305010893246187 : [[[245.0], [124.0], [23.0], [40.0], [179.0], [40.0], [23.0], [31.0], [233.0]]]
3: 0.8191721132897603 : [[[175.0], [8.0], [92.0], [20.0], [162.0], [57.0], [23.0], [20.0], [233.0]]]
4: 0.8091503267973855 : [[[245.0], [124.0], [23.0], [40.0], [248.0], [57.0], [124.0], [31.0], [233.0]]]
5: 0.8030501089324619 : [[[245.0], [124.0], [23.0], [172.0], [248.0], [40.0], [23.0], [31.0], [233.0]]]
6: 0.7978213507625272 : [[[245.0], [124.0], [92.0], [40.0], [179.0], [57.0], [23.0], [20.0], [233.0]]]
7: 0.7790849673202614 : [[[245.0], [124.0], [23.0], [40.0], [179.0], [57.0], [124.0], [31.0], [233.0]]]
8: 0.7790849673202614 : [[[245.0], [124.0], [23.0], [40.0], [162.0], [40.0], [124.0], [31.0], [233.0]]]
9: 0.7712418300653594 : [[[245.0], [124.0], [23.0], [40.0], [179.0], [75.0], [124.0], [31.0], [233.0]]]第三十子代：
========== 30 ==========
0: 0.9002178649237472 : [[[245.0], [53.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
1: 0.8810457516339869 : [[[245.0], [97.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
2: 0.8718954248366013 : [[[245.0], [118.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
3: 0.8675381263616558 : [[[233.0], [97.0], [23.0], [59.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
4: 0.8636165577342049 : [[[245.0], [118.0], [23.0], [59.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
5: 0.8544662309368191 : [[[245.0], [158.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
6: 0.8540305010893247 : [[[245.0], [118.0], [23.0], [40.0], [248.0], [20.0], [64.0], [31.0], [233.0]]]
7: 0.8344226579520697 : [[[245.0], [118.0], [23.0], [40.0], [162.0], [20.0], [23.0], [31.0], [233.0]]]
8: 0.8122004357298475 : [[[245.0], [255.0], [23.0], [40.0], [248.0], [20.0], [23.0], [31.0], [233.0]]]
9: 0.7398692810457517 : [[[245.0], [158.0], [245.0], [40.0], [248.0], [20.0], [64.0], [31.0], [233.0]]]第100代：
========== 100 ==========
0: 0.9542483660130717 : [[[254.0], [5.0], [11.0], [26.0], [248.0], [15.0], [17.0], [1.0], [233.0]]]
1: 0.9533769063180827 : [[[254.0], [5.0], [11.0], [26.0], [248.0], [17.0], [17.0], [1.0], [233.0]]]
2: 0.952069716775599 : [[[254.0], [5.0], [11.0], [26.0], [248.0], [20.0], [17.0], [1.0], [233.0]]]
3: 0.9333333333333332 : [[[254.0], [5.0], [23.0], [26.0], [217.0], [20.0], [17.0], [1.0], [233.0]]]
4: 0.9294117647058823 : [[[254.0], [5.0], [11.0], [78.0], [248.0], [20.0], [17.0], [1.0], [233.0]]]
5: 0.8793028322440087 : [[[254.0], [5.0], [11.0], [26.0], [248.0], [187.0], [17.0], [1.0], [233.0]]]
6: 0.8753812636165578 : [[[254.0], [5.0], [23.0], [190.0], [248.0], [20.0], [17.0], [1.0], [233.0]]]
7: 0.8723311546840958 : [[[254.0], [5.0], [11.0], [26.0], [248.0], [20.0], [17.0], [184.0], [233.0]]]
8: 0.8671023965141612 : [[[254.0], [5.0], [23.0], [26.0], [248.0], [20.0], [17.0], [184.0], [233.0]]]
9: 0.7891067538126362 : [[[254.0], [203.0], [23.0], [190.0], [248.0], [20.0], [17.0], [1.0], [233.0]]]随着种群的迭代，新的种群中个体适应度在逐渐提高，当到达100代时，最高适应度达到了 0.95425，已经很接近最完美的个体了。如果继续迭代下去，一定可以找到适应度为 1.0 的个体。
总结
这次用 kotlin 实现了遗传算法，抽象了个体、种群以及交叉突变的方法，灵活度高，开发者可以自行实现相应的抽象类和接口，以便达到实验目的。
最核心的是 IPopulation<I: Individual> 接口，只要按照实验需要实现这个接口，就可以快速构建一个实验模型。
对于常见的交叉与突变的方式，还有以下几种：
- 多点交叉 (Multi-point Crossover)：随机设定4个或更多交叉点，交换多个基因片段。
- 均匀交叉 (Uniform Crossover)：每个等位基因都以相同的概率发生交换。
- 算数交叉 (Algorithm Crossover)：每个等位基因加权平均产生新的染色体。
- 模拟二进制交叉 (Simulated Binary Crossover)：将两个染色体上的基因进行二进制交叉，和单点交叉类似，但 SBC 交换的是某个位置之后的基因的二进制串。
- 均匀变异 (Uniform Mutation)：以一个较小的概率将一个合理范围内的基因替换原有基因，对原染色体的每个基因都执行这个操作。
- 非均匀突变 (Non-Uniform Mutation)：与均匀变异不同的是，其对每个基因突变发生的概率以及突变幅度是不同的，一般会随着迭代次数的增加，降低突变概率与突变幅度。
- 高斯近似变异 (Gaussian Mutation)：与均匀变异类似，在进行变异时用一个均值μ、方差为σ2的正态分布的一个随机数来替换原有基因值。
感兴趣的朋友可以自己实现一下试试。
请问大佬是做生物信息学的吗
我是学软件的😳