Scala の勉強を兼ねて作った成果物についての記事です。改善点等ありましたら、ぜひコメントにてご指摘いただければと思います。もちろん、Scala に関することだけでなく、アルゴリズムや設計についてもご指摘頂きたいと思います。

成果物

概要

今回は Scala による遺伝アルゴリズムソルバを実装しました。
こちらで用意した Gene トレイトを継承するクラスを書くことで、任意の問題に対して遺伝アルゴリズムを適用し近似最適解を求めることができます。作成したプログラムの説明に入る前に、遺伝アルゴリズムについてすこし復習をします。ここで説明するアルゴリズムは正確性に書ける部分や実用的でない部分があります。遺伝アルゴリズムについてすでにご存じの方は飛ばしていただければと思います。その後、作成したプログラムの解説と実行の仕方、拡張の仕方を説明します。

遺伝アルゴリズムについて

遺伝アルゴリズム とはなんでしょうか。

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。(Wikipedia から引用)

Wikipedia　に書いてあるように、遺伝アルゴリズムは GA とも呼ばれ、組み合わせ最適化問題における近似解を求めるアルゴリズムの一つになります。このことからわかるように、 遺伝アルゴリズムを用いて計算される結果が最適解（理論上得られる一番いい値）である保証はありません 。むしろ、一般的な問題では局所解に陥ってしまい、最適解を得ることは難しいでしょう。では、なぜ遺伝アルゴリズムを使うのでしょうか。我々が現実世界で直面する問題の中には、「最適解を求めることが難しく、かと言って、解の候補がたくさんあるのですべてを試していては時間がかかりすぎる」という問題が存在します。有名な問題としては、巡回セールスマン問題やナップサック問題があげられます。これらの問題を解くには、最適解を得ることを諦めて、最適解に近い値を効率的に解くことを考える必要があります。遺伝アルゴリズムはそのような手法の一つです。遺伝アルゴリズムでは、その名の通り生物の進化の仕組みからヒントを得ることで、局所解をうまく回避し、すこしでも最適解に近い値を得るための工夫が取り入れられています。これらの工夫に関しては後に少し紹介します。

遺伝アルゴリズムの流れ

遺伝アルゴリズムの流れを具体例を使ってみてみます。遺伝アルゴリズムでは、問題の解の候補をいくつか並べたものを一つの世代として、その世代から次の世代を作り出し、世代交代していくことで徐々にいい解へと近づいていきます。また、世代を構成している解の候補を個体と呼びます。ここでは仮に、以下の様な二次関数の最大値を求める問題を考えます。

最大値を求めたい二次関数

y = -(x - 10)^2 + 20

御存知の通り、このような二次関数は $x = 10$ の時に、最大値 $y = 20$ となります。ここで、$x = 2$ のような値が解の候補であり、ある世代を構成する要素になります。また、$x = 2$ の時の 評価値 が $y = -44$ になります。そして、$x = 10$ が理論上の最適解であり、目指す値です。それでは、一つの世代における個体の数を 4 、総世代数を 10 として場合の例をみてみます。
(※以下で用いる個体の値は適当なものを使っています。)

(1) 初期の世代をランダムに生成します

世代1

x1 = 1.43
x2 = -4.01
x3 = 103.35
x4 = 5.12

(2) 現世代から遺伝子操作(後述)によって新しい世代を生成

世代1

x1 = 1.43
x2 = -4.01
x3 = 103.35
x4 = 5.12

↓ 遺伝的操作

世代2

x1 = 3.23
x2 = 1.43
x3 = 32.3
x4 = 2.46

↓ 遺伝的操作

︙

↓ 遺伝的操作

世代10

x1 = 9.99
x2 = 9.98
x3 = 9.12
x4 = 3.46

(3) 最終世代の個体の中で、一番評価値の高いものを解として選択

世代10

x1 = 9.99 <- 選択
x2 = 9.98
x3 = 9.12
x4 = 3.46

さて、上記のような手順で近似最適解を生成することができました。
上記の流れが遺伝アルゴリズムの大枠になりますが、重要な操作である 遺伝的操作 については省略していました。この遺伝的操作が遺伝アルゴリズムの収束の速さや局所解への陥りにくさを決める重要な要素になります。次はこの操作について見てみます。

遺伝的操作

遺伝アルゴリズムでは下記のような３つの遺伝的操作を個体に適用して新しい個体を生成します。

選択
交叉
突然変異

それぞれに対して先ほどの二次関数の具体例を使って説明します。

選択

この操作では、現世代の個体の中から一つ選び次の世代に加えます。この時、個体の選び方を変えることで、収束性や局所解への陥りやすさが変わります。よく使われる方法には以下の様なものがあります。

ルーレット選択
- 評価値が高いものほど選ばれる確率を高くする方法です。評価値に差がつきやすい場合に、評価値の高い個体ばかりが選ばれてしまい、解に偏りが発生し、局所解に陥りやすくなるので注意が必要です。
ランキング選択
- 評価値を順位づけし、第一位から順に確率をあらかじめ決めておく手法です。ルーレット選択都の違いは、評価値そのものの大きさが考慮されない点にあります。あくまで順位に注目するので、評価値がほとんど変わらない場合でも、選ばれる確率に大きな差がついたりします。
トーナメント選択
- 世代の中から個体を n 個ランダムに選択し、その中で評価値の一番高いものを選択するという手法です。この n のことをトーナメントサイズといいます。トーナメントサイズを変えることで、性能を調整することができます。

例）
今回の実装ではトーナメント選択を使っています。前述の二次関数の例で言うと下記のような選択が起こります。

トーナメント選択1

x1 = 1.43
x2 = -4.01
x3 = 103.35
x4 = 5.12

ここから例えばランダムに２つの個体を選びます。

トーナメント選択2

x1 = 1.43
x4 = 5.12

そして、この中から評価値の一番高いものを選択します。

トーナメント選択2

x1 = 1.43
x4 = 5.12 ← 選択

交叉

現世代の中から個体を２つ（ランダムに）選び、それらを混ぜあわせて新しい個体を生成します。
これは生物が交配によって子孫を残す仕組みを取り入れたもので、遺伝アルゴリズムにおいて特に重要な操作になります。

例）
二次関数での例です。交叉の実装は様々な方法が考えられますが、操作の特徴として選ばれた２つの個体から新しい個体を作り進化させていくということがあるので、２つの個体の特徴を受け継ぐような実装をするのが一般的です。今回は２つの個体の $x$ の値の平均を取るという交叉方法を考えてみます。

まず世代からランダムに個体を２つ選択します。

交叉1

x1 = 1.43
x2 = -4.01 ← 選択1
x3 = 103.35 
x4 = 5.12 ← 選択2

次に、選ばれた２つの個体の平均値をとって、新しい個体とします。

交叉2

new_x = (-4.01 + 5.12) / 2

突然変異

この操作は個体の生成にランダム性を入れることによって、局所解に陥りにくくします。
これは生物の進化の上でみられる遺伝子の突然変異の仕組みを取り入れた操作になります。

例）
突然変異では現世代の個体にランダム要素を加えることで多様性を確保します。今回の例では単に $x$ の値をランダムに生成するなどが考えられます。

これらの遺伝的操作を用いて現世代から次世代を作る場合を考えます。一世代あたり $n$ の個体があるとします。
まず、現世代に対して遺伝的操作を一つ適用し、それによって生成された個体を次世代に追加します。ポイントは、３つの遺伝的操作をすると必ず新しい個体が一つ生まれるという部分です（もちろん、２つ以上の個体を生成する実装もありえますが...）。つまり、この操作を $n$ 回繰り返すと現世代の個体数が $n$ になり、完了します。どの遺伝的操作を適用するかは 交叉率 や 突然変異率 によって操作されます。これらの確率を変えることで収束の速さや局所解への陥りにくさが変化します。特に、突然変異率を高くするとランダム探索に近くなります。

Scala でつくった遺伝アルゴリズムソルバ

前置きが長くなりましたが、今回作った遺伝アルゴリズムソルバについての説明です。
まず、個体を表すインターフェースである Gene トレイトを定義します。

個体の定義

Gene.scala

trait Gene {
  def newRandomGene: Gene         // ランダムに新規個体を生成
  def mutation: Gene              // 突然変異処理
  def crossover(that: Gene): Gene // 交叉処理
  def eval: Double                // 評価値の計算
}

この Gene トレイトを継承した独自のクラスを定義することで、任意の問題に対して遺伝アルゴリズムを適用できます。本記事では二次関数の最適化を例に説明しましたが、多項式関数の個体を定義すると下記のようになります。ただし、この実装はあくまで一例であり、実際にナイーブな実装になっています。よりよい遺伝的操作が考えられます。

PolynominalFunctionGene.scala

import scala.util.Random

/**
* 多項式関数の個体
* func は "y = x * x * x + 2 * x - 17" のような多項式が入る（実際には scala の lambda 式で書く）
*/
class PolynominalFunctionGene(func: Double => Double, val x: Double) extends Gene {

  /**
  * コンストラクタ
  * -100 ~ 100 の範囲の実数をランダムに生成し x の値とする
  */  
  def this(func: Double => Double) = this(func, (Random.nextInt(200) - 100) + Random.nextDouble())

  def newRandomGene = new PolynominalFunctionGene(func)

  /**
  * 値の評価
  * 今回の場合は func で x を評価すると評価値である y が計算される
  */  
  def eval: Double = func(x)

  /**
  * 突然変異
  * 自身の x から ±4 の範囲でランダムに個体を生成し、それを突然変異とする
  */  
  def mutation = {
    val random = new Random
    val plus = random.nextInt(4)
    val minus = random.nextInt(4)
    new PolynominalFunctionGene(func, x + plus - minus)
  }

  /**
  * 交叉
  * 二個体間の x の平均を新たな個体とする
  */  
  def crossover(that: Gene): Gene = {
    val newX =  (this.x + that.asInstanceOf[PolynominalFunctionGene].x) / 2
    new PolynominalFunctionGene(func, newX)
  }
}

上記のような Gene トレイトを継承したクラスを書くことで多項式関数を最適化するための個体を用意できました。同様に巡回セールスマン問題やナップサック問題も定義することができるでしょう。個体の定義（つまりは解きたい問題の定義）ができたので、実際に遺伝アルゴリズムによって解く部分を見てみます。

ソルバ

GASolver.scala

import scala.util.Random

object GASolver {
  def solve(
      gene: Gene,
      generationSize: Int = 1000,
      geneSize: Int = 100,
      crossoverRate: Double = 0.3,
      mutationRate: Double = 0.05,
      tournamentSizeRate: Double = 0.1): Gene = {

    def isTrue(rate: Double) = (rate >= Random.nextDouble)
    def isCrossover = isTrue(crossoverRate)
    def isMutation = isTrue(mutationRate)

    def alternation(genes: Seq[Gene], generation: Int): Seq[Gene] = {
      if(generation == 0) return genes
      
      val nextGeneration = for(_ <- 1 to genes.size) yield {
        if(isMutation) {
          mutation(genes)
        } else if(isCrossover) {
          crossover(genes)
        } else {
          selection(genes)
        }
      }
      alternation(nextGeneration, generation - 1)
    }
    
    def mutation(genes: Seq[Gene]): Gene = genes(Random.nextInt(genes.size)).mutation
    def crossover(genes: Seq[Gene]): Gene = {
      val gene1 = genes(Random.nextInt(genes.size))
      val gene2 = genes(Random.nextInt(genes.size))
      gene1.crossover(gene2)
    }
    def selection(genes: Seq[Gene]): Gene = {
      val selectedTounament = Random.shuffle(genes).take((genes.size * tournamentSizeRate).toInt)
      selectTopGene(selectedTounament)
    }
    def selectTopGene(genes: Seq[Gene]): Gene = genes.sortWith((g1, g2) => g1.eval > g2.eval)(0)
    
    
    // Solver start
    val genes = for(_ <- 1 to geneSize) yield gene.newRandomGene
    val lastGenerationGene = alternation(genes, generationSize)
    
    return selectTopGene(lastGenerationGene)
  }
}

GASolver.solve() を実行することで遺伝アルゴリズムを計算します。solve() の引数には、

gene : 個体
generationSize : 計算する世代数
geneSize : 一世代あたりの個体数
crossoverRate : 交叉する確率
mutationRate : 突然変異率
tournamentSizeRate : トーナメントサイズを geneSize に対してどのくらいの割合にするか（geneSize が 10 の時、トーナメントサイズを 2 にしたければ、tournamentSizeRate = 0.2）

を渡します。ただし、gene 以外は省略可能です。パラメータを省略した場合はデフォルト値が使用されます。
次に、GASolver.solve() の詳細を見てみます。
まず、初期の世代を生成します。

初期世代

val genes = for(_ <- 1 to geneSize) yield gene.newRandomGene

そして、この初期世代 genes を alternation() に渡すことで、generationSizes で指定した数の世代を経た最後の世代を取得します。

最後の世代

val lastGenerationGene = alternation(genes, generationSize)

alternation は世代交代の意であり、再帰的に次の世代を生成します。alternation() は単純な再帰関数で構成されています。

alternation()

    def alternation(genes: Seq[Gene], generation: Int): Seq[Gene] = {
      if(generation == 0) return genes
      
      val nextGeneration = for(_ <- 1 to genes.size) yield {
        if(isMutation) {
          mutation(genes)
        } else if(isCrossover) {
          crossover(genes)
        } else {
          selection(genes)
        }
      }
      alternation(nextGeneration, generation - 1)
    }

この中で、交叉率や突然変異率を用いて遺伝的操作を適用し、次世代を生成しているのが分かります。

ソルバの実行方法

では、多項式関数個体である PolynominalFunctionGene を使って遺伝アルゴリズムを実行する方法をみてみます。

実行

scala> val p = new PolynominalFunctionGene(x => - (x - 10) * (x - 10) + 20)
p: com.github.aidy1991.scala_ga.PolynominalFunctionGene = com.github.aidy1991.scala_ga.PolynominalFunctionGene@8dd496f

scala> val result = GASolver.solve(p);
result: com.github.aidy1991.scala_ga.Gene = com.github.aidy1991.scala_ga.PolynominalFunctionGene@3facd782

scala> result.eval
res0: Double = 19.999999999999243

$x => - (x - 10) * (x - 10) + 20$ の部分が解きたい多項式関数になっています。
個体の定義さえしてしまえば、GASolver を使うととても簡単に遺伝アルゴリズムを計算できることが分かります。

おわりに

本記事で説明したのはナイーブな遺伝アルゴリズムの説明とその実装です。アルゴリズムの説明では書ききれなかった部分や正確性に書ける部分があります。また、実装については、効率の点でも改善の余地があると思います。一度並列処理をしようとしたのですが、かえって遅くなってしまった経緯があります。もし、「こうすると早くなる」「こういう風に並列処理を書くといい」というのがありましたらぜひ教えていただきたいです。また、クラス設計や継承の使い方など、手探りで作りましたので、ご指摘いただければ幸いです。