Scalaで遺伝的アルゴリズム入門
遺伝的アルゴリズムとは
遺伝的アルゴリズムというと抽象的な問題や計算量の多い問題を、解のモデルを生物と置いて生物の進化と同等の処理を施すことでいい解を得ようというもの。
様々な手法や応用があって数学徒ではない初~中級者プログラマもどきである自分みたいな人には名前を聞いただけで難しそうだと投げ捨ててしまうものだと思う。
簡単な例だと方程式の解やセールスマン巡回問題を解かせるものがあったが、評価が面倒だったので純粋に狙った数値が遺伝で出せるのか簡単にやってみた
方法
意外とシンプル、あとからごちゃごちゃ説明してるほうが今回実装する方
- 初期個体を作る
- 単純に乱数で生成
- 優越をつける
- 目標の数値にどれだけ近いか
- 後世を作る
- 適当な点でビットを入れ替える
これだけ。割りとできそうな気がしてきた。深いことを言えば初期個体の作り方、優越の付け方、交配方法、突然変異などがあるのだがスルー*1
実装
Scalaでやった。ここまで読めばどんな言語でもできると思う。
abstract class Cell[T] {
var self:T
val seed:Random
def show()
def make()
def eval(target:T):Int
def +(target:T) : (Cell[T],Cell[T])
def copy() : Cell[T]
}
まぁとりあえず定義。今更だが乱数のseedは外で出して初期個体はまとめて生成したほうが早かったな
交配
bit演算するだけ
AAAAAAAAとBBBBBBBBを適当な点pivotで入れ替えて
AAABBBBBとBBBAAAAAとするだけ
override def +(target:Int) = {
val l = if(target > self) target.toBinaryString.length else self.toBinaryString.length
val pivot = seed.nextInt(l)
val a = copy
val b = copy
a.self = (self & (~0 << pivot)) | (target & ~(~0 << pivot))
b.self = (self & ~(~0 << pivot)) | (target & (~0 << pivot))
(a,b)
}
その後に {初期個体生成, 次世代生成, 交配リスト生成}をToolとして定義し、無限リストとすることで欲しい世代をtakeするだけで好きな世代まで進化させられるようautoGenを定義。初期個体数は初期個体生成したものも無限リストなのでそこからいくつ使うか最初に決めることとした。
使ってみる
メインをできるだけ少なくするのは宗教上の理由から
def main(ars:Array[String]) : Unit = {
val range = 1000
val target = (new Random).nextInt(range)
val t = new IntCellTool(target,range)
val first = t.makeFirst take 50
val processed = t.autoGen(first) take 20
println("target," + target)
print("generate,")
for(p <- processed) print(p(0).self + ",")
}
グラフには ccchart を使用しました。綺麗で使いやすいです。
計算速度もそこそこ。いい感じだけど課題は結構残る感じ。これから発展していろんなものに使っていく所存
*1:解がうまく収束しなかったり、局所解に陥りやすくなる。今回の場合も交配方法があまり適当ではなかったせいか世代数を多く重ねると答えが収束しにくくなってしまった
