初期個体群の生成2
【内部主要記事】
【本文】
なんとか、0世代目の個体*20を作成してベクターに格納するコードをschemeに移植して解釈してみました。
基本的な動きは、それだけなのですが *method-of-generation* 状態(full, grow, ramped-half-and-half)によって出力プログラム(構文木)の深さを調整している箇所がかなりの部分を占めます。にもかかわらずこのコードの中では *method-of-generation* を更新していません。より上位のどこかで更新するか固定値として実行するものだと推測されます。
;; (注)
;; 終端記号：引数
;; 非終端記号：関数
(define nth
(lambda (n ls)
(if (eq? n 0)
(car ls)
(nth (- n 1) (cdr ls)))))
(define-syntax incf
(syntax-rules ()
((_ x) (begin (set! x (+ x 1)) x))
((_ x i) (begin (set! x (+ x i)) x))))
(define size-of-population 20)
(define seeded-programs (list '(cons 'a 'b) '(cons 'd 'e)))
(define make-individual #t)
(define *max-depth-for-new-individuals* 6)
(define *method-of-generation* 'grow) ;or full or ramped-half-and-half
(define *generation-0-uniquifier-table* ()) ;0世代目のテーブル
;let の値、暫定テスト用
(define minimum-depth-of-trees 1)
(define attempts-at-this-individual 0) ;同一個体が既にあった場合の個体作成再試行回数
(define full-cycle-p #f)
(define individual-index 0)
; 初期個体群を作成します。コレは size-of-population の大きさの配列です。
; この配列は個体群を記録するために初期化されてます。各固体のプログラム
; スロットは適切な任意のプログラムに初期化されます。これらの最初のN固体は
; seeded-program によってそれぞれ初期化されます。
; この seeded-program はデバッグに役に立ちます。
(define create-population
(lambda
(size-of-population
seeded-programs)
(let ((population (make-vector size-of-population))
(minimum-depth-of-trees 1)
(attempts-at-this-individual 0) ;; 同じランダムプログラムがあったとき作成し直した回数
(full-cycle-p #f))
;; for(individual-index = 0; individual-index >= size-of-population; ;)
(do ((individual-index 0))
((>= individual-index size-of-population))
;; individual-index が5の倍数なら
(if (eq? 0 (modulo individual-index
(max 1 (- *max-depth-for-new-individuals* ;6
minimum-depth-of-trees)))) ;1
;; full-cycle-p の真偽値を反転させる
(set! full-cycle-p (not full-cycle-p)))
(let ((new-program
;; 作成済みの個体より seeded-program が多ければ
(if (< individual-index (length seeded-programs))
;; あらかじめ用意した種となる個体の選択
(nth individual-index seeded-programs)
;; でなければ、構文木の深さが 1 〜 5 の新しいランダムプログラム作成
(create-individual-program
;;* allowble-depth
;; 木の深さが、0以下なら終端記号を選ぶ
(case *method-of-generation*
((full grow) *max-depth-for-new-individuals*) ;6
((ramped-half-and-half)
;; 1 〜 5
(+ minimum-depth-of-trees ;1
; individual-indexを5で割った余り 0 〜 4
(modulo individual-index
; 5
(- *max-depth-for-new-individuals* ;6
minimum-depth-of-trees))))) ;1
;;* top-node-p
;; #fなら終端記号か非終端記号をランダムに選ぶ
;; #tなら非愁嘆記号をランダムに選ぶ
#t
;;* full-p
;; #fなら終端記号か非終端記号をランダムに選ぶ
;; #tなら非愁嘆記号をランダムに選ぶ
(case *method-of-generation*
((full) #t)
((grow) #f)
;; individual-index が5の倍数なら
;; full-cycle-p の真偽値を反転している
((ramped-half-and-half) full-cycle-p))))))
(cond
;; あらかじめ用意した種となる個体を population に格納
((< individual-index (length seeded-programs))
(set! (vector-ref population individual-index) new-program)
(incf individual-index))
;; 作成した個体と同じものが存在しなければ
((not (assq new-program *generation-0-uniquifier-table*))
;; ソレを population に格納
(set! (vector-ref population individual-index) new-program)
(set! attempts-at-this-individual 0)
(incf individual-index))
;; 個体作成の試みが可能ならループしてそれを行う。
((> attempts-at-this-individual size-of-population)
;; ramped-half-and-half以外の引数で、個体が作られた可能性が高いので、
;; 作られた個体の tree の深さは *max-depth-for-new-individuals* (最深)
;; になった。深さ決定カウンター (minimum-depth-of-trees) を増加。
(incf minimum-depth-of-trees)
;; 新しい最小の状態 (minimum-depth-oftree) を保持するため
;; 最大の深さ (*max-depth-for-mew-individuals) を更新。
(set! *max-depth-for-new-individuals*
(max *max-depth-for-new-individuals*
minimum-depth-of-trees)))
;同一個体が既にあった場合の個体作成再試行回数を増加
(else (incf attempts-at-this-individual)))))
;; uniquifierテーブルをクリアし、0世代の個体を維持しなくする。
(set! *generation-0-uniquifier-table* ())
;; たった今作成した個体群を返す。
population)))【実行方法】
-
- 構文木が文法的に正しく出力されるようにする3のコードをrandom-tree.scmと言う名前で保存する。
- この記事(初期個体群の生成2)のコードをcreate-population.scmと言う名前で保存する。
- gaucheを起動する。
- (load "./random-tree.scm")
- (load "./create-population.scm")
- (create-population size-of-population seeded-programs)
アルファベット小文字のリストを作成するランダムなコードが初期個体群(20)の数だけ出力されます。
次は適合度の評価を行うコードを書く予定です。
大域変数はアスタリスクで囲う
http://www.h7.dion.ne.jp/~matsu/feature/common-lisp/basic/variable.html
- 大域変数名は前後を*で囲うのがLispでの習慣らしい.
":" (キーワード)
http://openspace.timedia.co.jp/~nyama/wiliki/ghg.cgi?p=gauche.h%3AKeyword&c=e
- Common Lispでは、':' で始まるシンボルは常に自分自身を値とする特別なシンボル で、「キーワード」と呼ばれます。Gaucheでは、キーワードはシンボルとは異なるオブジェクトで、主としてキーワード引数を実現するために使っています。R5RSに出てくるメタ変数としてのkeywordとは異なります。独立したキーワードオブジェクトを持つSchemeとしては、stklos、Guile、それからDSSSL XSLTの元祖みたいなやつ) 等があります。表記は微妙に異なっていて、stklosは '':keyword''、Guileは ''#:keyword''、DSSSLでは ''keyword:'' です。パッケージの問題があるCommon Lispと違って、Schemeではキーワードを持つべき本質的な理由というのは実はありません。キーワード引数はクオートしたシンボルで実現できます。メリットは単にコード上で若干見やすいというくらいですね。
http://flex.ee.uec.ac.jp/texi/canlisp/node28.html
- キーワードパッケージシンボルを評価するとそのシンボル自身になる。
:user 評価→ :user :abcd 評価→ :abcd
incf
CLISPの (nicf x) は
schemeの (set! x (+ x 1)) に等しい。
schemeのマクロで実現
http://www.shido.info/lisp/scheme_syntax.html
- syntax-rules には複数の変換パターンを定義することができます。例えば、変数の値を増加させるマクロ incf を考えて見ましょう。変数名だけ与えられたときは 1 増やし、変数名と増分が与えら得れたときには増分だけ増やすようにします。 [code 4] のように複数の変換パターンを記述することによって対応することができます。
(define-syntax incf
(syntax-rules ()
((_ x) (begin (set! x (+ x 1)) x))
((_ x i) (begin (set! x (+ x i)) x))))以下の2つはCなどの"++"インクリメントと同様
正式なやり方（？）
(define-syntax incf
(syntax-rules ()
((_ var)
(set! var (+ var 1)))))http://www.ksky.ne.jp/~sakae/sicp/read-sicp2.html
古いやり方(？)
(define-macro (incf form) `(set! ,form (+ ,form 1)))
nth
http://www.bookshelf.jp/texi/elisp-intro/jp/emacs-lisp-intro_9.html
(nth 0 '("one" "two" "three"))
=> "one"
(nth 1 '("one" "two" "three"))
=> "two"http://www5a.biglobe.ne.jp/~sasagawa/MLEdit/Scheme/scheme9.html
(define nth
(lambda (n ls)
(if (= n 1)
(car ls)
(nth (- n 1) (cdr ls)))))CLISPのnthではリストを0から数え始める。
[1]> (nth 1 '(a b)) B [2]> (nth 0 '(a b)) A
schemeのリストも以下のように配列同様0から数える仕様に変更
(define nth
(lambda (n ls)
(if (= n 0)
(car ls)
(nth (- n 1) (cdr ls)))))
