基于遗传算法实现排课系统

遗传算法属于NP完备问题，不确定问题需要大量离散的数据进行线性处理。

遗传算法(genetic algorithm)是受Charles Darwin自然进化理论启发的搜索启发式算法。该算法反映了自然选择的过程，选择最合适的个体进行繁殖，以产生下一代后代。

¶Notion of Natural Selection

自然选择的过程，开始于种群中最适个体的选择。它们产生子代，子代继承父代的特性。如果父代有最适值，子代将有比父代更好机会生存。该选择过程将迭代进行，直到最适值种群个体出现。

分析该问题，可以从DDD方面描述，从种群进化和优胜劣汰方面，我们需要专业术语进行描述。我们考虑遗传进化是多个解决方案对一个抽象问题的描述。

遗传算法考虑5个阶段

1. 初始化种群(population)
2. 适值函数(fitness)
3. 蒙特卡罗选举(selection)
4. 交叉(crossover)
5. 变异(mutate)

¶Initial Population

一个个体(Individual)是一系列基因 的集合，基因组成染色体(Chromosome)的解决方案。

在遗传算法中，一系列基因用字符(char)表示，术语称为alphabet，字母表或基因池。通常用二进制表示(1或0)。如下看到的染色体基因编码：

¶Fitness Function

适值函数决定了一个个体的适应能力(一个个体与其它个体的竞争能力)。每个个体都拥有自身的适值分数(fitness score)。个体被选中作为繁衍基于它自身的适值分数。

¶Selection

选择阶段就是选择最适个体，并将它们的基因传递给下一代。

根据它们的适值分数(fitness score)选择一对个体(父代)。适值数高的，将有更高的机会被选择进行繁衍。

¶Crossover

交叉在遗传算法中是最有成效的阶段。对于每一对被匹配到的父代，交叉点(crossover point)在基因中被随机选取。

例如，从第3个位置开始：

子代的创建，来源于父代基因的交换

新生子代被添加到种群中。子代的产生，都是按照批次出现，不会出现年龄的概念，也不考虑种群数量增多的情况。

¶Mutation

在某些新生代中，它们某些基因可能以一种非常低的概率发生变异(mutation)。这意味着新生代的基因可能会出现反转(flipped)。

基因突变是为了保持种群内的多样性和防止过早收敛。一般有两种情况考虑基因突变的情况：

1. 当种群进化到一定阶段出现无解(种群所有个体基因全部相同，交叉后子代基因和父代基因没有变化；但是所有个体都不满足条件，种群无法再次进化)
2. 过早收敛，得不到一个最优解。特别是多个维度中，收敛出现偏向某一个维度。

¶Termination

终止条件是种群收敛(新生子代和前一代没有明显不同)。这表示遗传算法得出的解已经满足我们的问题。

¶Psuedocode

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP

¶GA

import com.typesafe.scalalogging.LazyLogging
import org.slf4j.Logger

import scala.annotation.tailrec
import scala.collection.immutable.Stream.consWrapper
import scala.language._
import scala.util.Random

object GeneticLayout extends App with LazyLogging {
  // 目标
  val target = "101010"
  // 基因池
  val genePool = Array[Char]('1','0')

  implicit val _: Logger = logger.underlying

  // 统计相等的个数
  def fitness(src: String, tgt: String): Double = src.zip(tgt).count { case (s, t) => s == t }
  // 冲突消除 todo:
  def conflictClear(agents: Seq[String]): Seq[String] = agents

  val testBench = new GeneticExploration[Char, String](0.5, 0.01, 10, genePool, cs => new String(cs.toArray), conflictClear, fitness)
  val (p, g) = testBench.evolution(testBench.newPool(10, target.length), target)
}

/**
  * @param cross crossover probability 交叉概率
  * @param mutation 变异概率
  * @param population 种群数量
  * @param genePool 基因池
  * @param specimenBuilder 个体构造器
  * @param conflictClear   冲突消除 Rm为硬约束条件；Rn为软约束条件；Rx为解保证
  * @param fitnessF 适值函数
  */
class GeneticExploration[Gene, Specimen](val cross: Double,
                                         val mutation: Double,
                                         val population: Int,
                                         genePool: Array[Gene],
                                         specimenBuilder: Iterable[Gene] => Specimen,
                                         conflictClear: Seq[Specimen] => Seq[Specimen],
                                         fitnessF: (Specimen, Specimen) => Double)(implicit ev$1: Specimen => Iterable[Gene], logger: Logger) {
  type Pool = Seq[Specimen]
  type MatePool = Seq[(Specimen, Double)]

  def randomGenes: Stream[Gene] = genePool(Random.nextInt(genePool.length)) #:: randomGenes
  def newSpecimen(len: Int): Specimen = specimenBuilder(randomGenes.take(len))
  def newPool(size: Int, len: Int): Pool = (1 to size).map(_ => newSpecimen(len))

  def matePool(pool: Pool, tgt: Specimen): MatePool = {
    val fitnesses: Seq[Double] = pool.map(fitnessF(_, tgt))
    pool.zip(renormalize(fitnesses))
  }

  /** 每个个体被选中的概率 */
  def renormalize(vector: Iterable[Double]): Iterable[Double] = {
    val sum = vector.sum
    vector.map(_ / sum)
  }

  /** 蒙特卡罗选举，伪随机生成个体 */
  @tailrec final def monteCarloSelection(matePool: MatePool): Specimen = {
    val (specimen, fitness) = matePool(Random.nextInt(matePool.length))
    // 子代适值大于父代适值？Y 替换 N 保持
    if (fitness > Random.nextFloat()) specimen else monteCarloSelection(matePool)
  }

  /** 产生新生代 */
  def popReproduction(matePool: MatePool): Pool =
    (1 to population)
      .par
      .map(_ => crossover(monteCarloSelection(matePool), monteCarloSelection(matePool)))
      .map(mutate)
      ./:(Seq[Specimen]())(conflictDetection)
      .seq

  /** 进行交叉操作，交叉概率 Pc */
  def crossover(a: Specimen, b: Specimen): Specimen = specimenBuilder(a.zip(b).map(gene => if (Random.nextFloat > cross) gene._1 else gene._2))
  /** 进行变异操作，变异概率 Pm */
  def mutate(s: Specimen): Specimen = specimenBuilder(s.map(gene => if (mutation > Random.nextFloat) randomGenes.head else gene))
  /**
    * 新生成的种群需要做 '''冲突检测与消除操作'''
    * 例如：
    * 001,001   =>  (a,α)
    * 001,010   =>  (a,β)
    * 010,110   =>  (b,ζ)
    * 随机检测发现 '''(a,α)''' 和 '''(a,β)'''冲突。随机获取冲突之外的任意值 '''(b,ζ)'''，替换为：
    * 001,001   =>  (a,α)
    * 010,010   =>  (b,β)
    * 001,110   =>  (a,ζ)
    *
    * 依次循环，直到cursor等于种群大小。确保每次进化种群个体不重复。方便快速收敛
    */
  def conflictDetection(z: Pool, b: Specimen): Pool = {
    @tailrec def _conflictRif(e: Specimen): Specimen =
      if (!z.contains(e)) e
      else {
        val x = mutate(e)
        if (z.contains(x)) _conflictRif(e)
        else x
      }
    conflictClear(z :+ _conflictRif(b))
  }

  /** 遗传进化操作，将适值较高的个体选择出来，并将其优秀的基因传递给下一代 */
  @tailrec final def evolution(pool: Pool, target: Specimen, generation: Int = 0): (Pool, Int) = {
    val newGeneration = popReproduction(matePool(pool, target))

    // ===========================================
    logger.debug(s"第${Console.RED}[{}]${Console.RESET}代 向 第${Console.RED}[{}]${Console.RESET}代进化: ", generation, generation + 1)
    logger.debug("")
    pool.zip(newGeneration).collect{ case (s, t) =>
      if (t.equals(target))
        logger.debug(s"${s.mkString} -> ${Console.BLACK_B}${Console.GREEN}$t${Console.RESET}")
      else
        logger.debug(s"${s.mkString} -> ${t.mkString}")
    }
    // ===========================================
    if (newGeneration.contains(target)) (newGeneration, generation)
    else evolution(newGeneration, target, generation + 1)
  }
}

¶遗传算法实现自动排课

点击这里获取源码。