初期個体群の生成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)の数だけ出力されます。
次は適合度の評価を行うコードを書く予定です。
