11. 進化的プログラミング

最終課題にします

詳細は後日

進化とは

https://gyazo.com/f6be137f6fd653e0dc69d3fa9232e9bb

進化的プログラミング

進化の原理を利用してプログラムを自動的に生成する

進化的アルゴリズム

プログラムやパラメタを人為的に「進化」させる

「淘汰圧」をかけて良いものを残していく

遺伝的アルゴリズムが代表例

遺伝的アルゴリズム

生物進化を計算機上でシミュレーション

解を「ゲノム」にコーディング

世代交替により良い解を残していく

Genetic algorithm

https://www.amazon.co.jp/dp/4782851367 https://gyazo.com/ea4c69edd397947a61121ccbf2df4263

遺伝的アルゴリズム

code:GAalgorithm

ランダムに生成したN個の個体を用意

while(1){

現世代の各個体の適応度を計算

確率的に以下の動作を行い結果を次世代に保存

個体を二つ選択して交叉を行う

個体を一つ選択して突然変異を行う

個体を一つ選択してそのままコピーする

現世代の個体を次世代のもので置き換える

}

世代交替における遺伝子操作

交叉

突然変異

一点交叉

http://gyazo.com/fc41eca4275cac628ded90bc347ad1f5.png

二点交叉

http://gyazo.com/88c894a29d5c22e1b59b711ffe42ad5b.png

一様交叉

http://gyazo.com/77ea3c2cbc95253934ff55e49b5fab5a.png

例: 8-Queens

縦/横/斜めに「Queen」が並ばないように配置

12種類の答

http://gyazo.com/72040da65f9db0160756e01ca233abee.png

8-Queenプログラム例

code:8queen.rb

class Queens

def initialize(nqueens = 8)

@col = []

@qpos = []

@up = []

@down = []

@nqueens = nqueens

(0...@nqueens).each { |i|

(-@nqueens...@nqueens).each { |i|

}

end

def out(block)

if block then

block.call(@qpos)

else

end

end

def expand(n,block)

(0...@nqueens).each { |c|

if n+1 >= @nqueens then

out(block)

else

expand(n+1,block)

end

end

}

end

def run(&block)

while true do

expand(0,block)

end

end

end

if __FILE__ == $0 then

Queens.new.run

end

8-QueensをGAで解く

code:8queenga.txt

queens = Queens.new

while true do

queens.evaluate

queens.dump

queens.calc

break if queens.solution

end

Queenの位置の表現

http://gyazo.com/6db282eb3171606d0351cdecc04928db.png

突然変異

http://gyazo.com/cae1c0d0a907f0f01fa6f813d8f054ce.png

交叉

http://gyazo.com/887cf5d84c267a4d7168ca38a24809e4.png

GAによる8-Queensプログラム

code:8queenGA.rb

# -*- coding: utf-8 -*-

#

# Solving 8-Queen by GA

#

class Queens

POPULATION = 1000

attr_reader :solution

def randomgene

(0...8).collect {

rand(8)

}

end

def initialize

@genes = []

POPULATION.times {

@genes << randomgene

}

File.delete("average.log") if File.exist?("average.log")

File.delete("best.log") if File.exist?("best.log")

end

def evaluateone(gene)

collisions = 0

v = {}

(0...8).each { |i|

}

v = {}

(0...8).each { |i|

}

v = {}

(0...8).each { |i|

}

if collisions == 0 then

@solution = gene

end

# 1.0 / (1.0 + collisions)

collisions

end

def evaluate

@val = []

@totalval = 0.0

totalcollisions = 0.0

best = 100.0

(0...POPULATION).each { |i|

totalcollisions += collisions

best = collisions if collisions < best

}

File.open("average.log","a"){ |f|

f.puts totalcollisions.to_f / POPULATION

}

File.open("best.log","a"){ |f|

f.puts best.to_f

}

end

def selectone

r = rand(10000) / 10000.0

v = 0.0

(0...POPULATION).each { |i|

end

}

end

def dump

(0..10).each { |i|

}

end

def calc

newgenes = []

while newgenes.length < POPULATION do

if rand(10000) < 6000 then # mutation

a = selectone

b = selectone

p1 = rand(8)

p2 = rand(8)

if p2 < p1 then

tmp = p2

p2 = p1

p1 = tmp

end

(p1..p2).each { |i|

}

newgenes << a

newgenes << b

elsif rand(10000) < 600 then # mutation

a = selectone

newgenes << a

else

newgenes << selectone

end

end

@genes = newgenes

end

end

queens = Queens.new

while true do

queens.evaluate

queens.dump

queens.calc

break if queens.solution

end

(0...8).each { |i|

s = (0...8).collect { '.' }

puts s.join(' ')

}

Demo: 8-Queen計算

成功例

http://gyazo.com/31fc922b2e4c91dc553b85e1fa8605e2.png

失敗例

局所解に落ち込んでいる

http://gyazo.com/ccda781e488ab681acb08e3121666f68.png

様々なバリエーション

交叉率, 突然変異率

子孫の残し方

良い結果の「子孫」を沢山残すようにする

最高の子孫をキープ (Elitist戦略)

駄目な子孫も一応残す

計算対象の選び方

重みの計算法

交叉の手法

遺伝子として木構造のプログラムを利用する

物理法則を「発見」させることもできる

John R. Koza

「Genetic Programming」(GP)

http://gyazo.com/8b6838e3edaa7f03197ce6970ce3ffb2.png

Genetic programming

https://www.youtube.com/watch?v=xIoytwJWJP8

プログラムの木構造表現

交叉操作の例

http://gyazo.com/1dda0879c9119387954fd6f443f8c824.png

進化的画像処理 (長尾)

処理前の画像と目標画像を与える

目標画像を生成するフィルタの組み合わせを自動生成

フィルタは標準的なものをいろいろ用意する

進化的画像処理システム

http://gyazo.com/657094f428bca4644b01c8b6abe2d4ff.png

画像処理例

http://gyazo.com/fb0055f4430460914c787f97dbe88579.png

画像処理例

http://gyazo.com/b308e19010915fb5e39e3e94a7634cc1.png

遺伝的アルゴリズムの応用

あらゆる最適化問題に適用可能

計算機で評価可能なものは何でも最適化可能!

遺伝的アルゴリズムの限界

自動評価不能なものは駄目

e.g. 「ヒット曲の自動生成」

ヒットするかどうかは評価不可能

評価を計算しにくい場合

評価関数がはっきりしているとは限らない

曲の良さ

配置の美しさ

配置制約と評価関数の関係が自明でない

対話的な遺伝的アルゴリズム

遺伝的アルゴリズムのループに人間が介入

解に制約を与える

評価を人間が行なう

介入の例

http://gyazo.com/ed2e829e648f00311f8538290d078aff.png

c.f. 人工育種

人間の選抜、交配による品種改良

美顔を作るAndroidアプリ by 荒川@明治大

http://gyazo.com/c684db9fa5f0b9178fd367a4ed99b5ac.png

確率的手法(GA, SAなど)を用いた図形配置システムでは評価関数の選択が重要

配置の好みをユーザが指定することにより、ユーザと同じ判断を行なう評価関数を遺伝的プログラミングで自動生成

確率的手法

配置のよしあしを反映する評価関数を最適化することにより徐々に良い解を求める

前の解をもとに次の解を計算する

手続きを用いずに良い解を得ることが可能

代表的なアルゴリズム

遺伝的アルゴリズム (GA)

焼きなまし法 (SA)

Simulated Annealing

https://gyazo.com/c94e159fbb06cb60a1e1199ca06f6eed

Annealing = 焼きなまし

解候補にランダムに雑音を加えて評価

ランダムさを表現する「温度」を少しずつ下げていく

確率的手法の例

GA(GASP)とSA(TimberWolf)によるVLSI配置

http://gyazo.com/d552207ae20dbed910c518d59e48e1ea.png

確率的手法のグラフ描画への適用

美しさの基準を示す評価関数を最適化する

http://gyazo.com/8a28ce95b25c9fe78d8f583114577fc6.png

確率的手法の問題点

遅い

最適に近い解が得られるとは限らない

評価関数がはっきりしているとは限らない

配置制約と評価関数の関係が自明でない

例: 三角形の中の適当な位置に別の点を配置

なんらかの評価関数の最適化によりその点の位置が定まるようにしたい

https://gyazo.com/2894ed46ce8ecac8be0ae56a83b50470

http://gyazo.com/d03154eeb529d6cbddf7862010e7fc8a.png

http://gyazo.com/bf06f4b7382f172adc55fea9f02350ef.png

例示によるアプローチ

例示により評価関数を作成する

ユーザはシステムに好みを伝えるだけ

遺伝的プログラミングによりユーザの与えた例から評価関数を自動生成

手法

良い配置例と悪い配置例の組をシステムに与える

遺伝的プログラミングにより配置の良否を決定する評価関数を抽出

与えた例における評価基準にもとづいて良い配置を生成することが可能

システムに与える配置例

http://gyazo.com/c203269a8abf8cd58ea730b9c119fe4f.png

得られた評価関数

code:result.lisp

(ADD (SUB (ADD (MUL (MUL (MUL (ADD (ADD (ADD SUM(diry) SUM(minangle)) (ADD 44.00 69.00)) (MUL 43.00 MIN(diry))) 5.00) (ADD (ABS MAX(minangle) MIN(dist)) (ADD (ABS 74.00 MIN(dirx)) (ABS 15.00 SUM(locx))))) SUM(minangle)) (MUL 12.00 (CMP (DIV 57.00 MIN(locx)) (CMP 94.00 MIN(intersec))))) (DIV (ABS (MUL (SUB SUM(locy) 27.00) (CMP 28.00 65.00)) 62.00) SUM(dirx))) (CMP (ABS (DIV 67.00 SUM(locy)) (CMP (ABS (ABS 73.00 (CMP 67.00 SUM(dist))) MIN(intersec)) (ABS MIN(dist) MIN(diry)))) MIN(diry)))</code>

得られた評価関数を使って得られた配置

http://gyazo.com/bb72e5ebf630d30e1ddc8fff69b13a74.png

対話的進化計算によるアート作品生成

システムに作品をいくつか自動生成させ、良いと思われるものを選択することにより進化させる

Biomorph (Richard Dawkins)

Galapagos (Karl Sims)

sbart (畝見)

Biomorph

「利己的な遺伝子」「Blind Watchmaker」のRichard Dawkinsの作品

「遺伝子」をもつ「虫」を進化させる

ランダムに遺伝子を交配させて作った子孫の中から最も気に入ったものを選ぶという行為を繰り返す

Richard Dawkins

http://gyazo.com/34b3ba70545c4f303aaaed62d194a3ac.png

Biomorphの進化過程

https://gyazo.com/189863961ab4de620dab6d570ac8dfd9

https://gyazo.com/e3f6ae493a794e677aaad40336b691a3

進化結果

https://gyazo.com/de14f13a1dd76fa0be7187acdbae83a1

NTT Intercommunication Center(初台オペラシティ)に展示された

9個の進化例の中から好みのものを選ぶことを繰り返す

http://gyazo.com/922ac4cc0136595f718209c81e6d4874.png

進化した「生物」例

http://gyazo.com/3ffc4dfce6ee255512e690f4939d3306.png

http://gyazo.com/356252a15a0243c5915b83662c2047a0.png

http://gyazo.com/06cb5d773b1add3e24775950e0fa5ab3.png

まとめ

様々な進化的アルゴリズムが存在

最適化計算に有用

試行錯誤が必要

対話的な進化的アルゴリズムも可能

進化的手法でアート作品を生成可能かも