第 3 章 最適なノード遷移の選択を行う学習進化型 GNP 27
3.4 進化フェーズ
Fig. 3.4は学習と進化の流れを示している。
進化フェーズは，すべての個体がタスクを終了した後，選択，交叉，突然変異を通じ て，すべてのノード遷移の中から，複数の候補を選択することが目的である。学習フェー
第3章 最適なノード遷移の選択を行う学習進化型GNP 29
node i Ki IDi di Qi1 A
...
di1
Ni1A A Qin-1
A
din-1 Nin-A1 A
0
1 2
3 4
start node d1
d12
P1
P2 J1
J2
0 2 1 1 2
2 1 00 10 10
1 5
5 2 1 1
0 0 10 00 00 00
10 00 00
00 00 10
10 00 10
Q12 A
A B
A B
A
1.0
0.1 0.1 0.5
0.0 0.8
0.0 0.0
0.3 0.0 2.0
0.6 0.3 0.0 3.1 0.7
00 0 0 10
1 0 1 0 00
1.3 0.1 0.0
0.0 4.0 0.8 node 0
node 1 node 2 node 3 node 4
...
Qi1 B
di1
Ni1B B Qin-1
B
din-1 Nin-B1 B
...
Node gene Connetion gene
A B
Q31 B
Q32 B
A
Fig. 3.1 Basic Structure of GNP with Learning and Evolution for selecting appropriate node transitions
Ni1A Ni2
Nin-1
...
A
A
1 0 Ni3A 0
1 Ni4
A
1
Ni1B Ni2
Nin-1
B
B
1 1 Ni3B 0
1 Ni4B 1
Ni1C Ni2
Nin-1
C
C
0 1 Ni3C 0
0 Ni4C 1
... ...
state siA state siB state siC
Fig. 3.2 An example of a setting of Nij
第3章 最適なノード遷移の選択を行う学習進化型GNP 30
Judgement/Processing/Start classification of node i
judge process
judgment result
...
A B
Judgement
Processing
i 0 (start node) start
Q-learning
Yes
Trial ends ?
No
stop
step 1:
select transition(s)
A
step 1:
select transition(s)
B
with Nij=1 step2:
select one transition among the ones selected
QAij in step 1 using and ε-greedy
step2:
select one transition among the ones selected
QBij in step 1 using and ε-greedy
step 1:
select the transition(s) with NijA=1
step2:
select one transition among the ones selected
QAij in step 1 using and ε-greedy with Nij=1
Start
(Ki=1) (Ki=0)
(Ki=2)
i j
Fig. 3.3 Flowchart of node transition
第3章 最適なノード遷移の選択を行う学習進化型GNP 31
start
generate an initial population
Judgement/Processing
reproduction
mutation crossover
last generation ? stop No Yes
Trial ends ?
No
ind 1
ind=the number of individuals?
Yes No
ind ind+1
Evolution phase Learning phase
Yes
Reinforcement Learning
ind : individual number
Fig. 3.4 Flowchart of Learning and Evolution
第3章 最適なノード遷移の選択を行う学習進化型GNP 32 ズは，タスク実行中に与えられる報酬を基にして，最適なノード遷移を選択することが 目的である。次節では遺伝的オペレータの適用法について述べ，3.5節でQ値の学習法に ついて述べる。
学習進化型GNPは交叉，突然変異を用いてプログラムの進化を実現する。各世代ごと に前世代の個体数と同数の個体を生成し，入れ替えを行う。各世代で交叉および突然変 異によって生成される個体数を，それぞれ交叉個体数，突然変異個体数と呼び，常に一 定数の新しい個体を生成する。また，適合度の高い個体を優先的に残す，エリート保存 選択も用いている。
3.4.1 交叉
交叉は2個の親個体間で行われ，2個の子個体を生成する[Fig. 3.5]。交叉のアルゴリ ズムを以下に示す。
1.トーナメント選択を2回行い，親となる2個体を選択する。
2.各ノードを確率Pcで交叉ノードとして選択する。
3. 2個体間において，2. で選択された交叉ノード（同ノード番号）の遺伝子を交換する。
4.生成された2個体を次世代の個体とする。
Fig. 3.5は簡単のため処理ノード3個のみのグラフ構造の例であるが，判定ノードでの交
叉を考える場合は，判定結果，B，C，· · · に関する遺伝子も同時に交換する。また，交 叉を行う場合，交換されるノードに付随するQ値は保持し，次世代の初期値として使用 する。
3.4.2 突然変異
突然変異は1個体で行われ，1個の子個体を生成する[Fig. 3.6]。突然変異オペレータ の作用する遺伝子はNij である。
1.トーナメント選択を1回行い，親となる個体を選択する。
第3章 最適なノード遷移の選択を行う学習進化型GNP 33
parent1 parent2
1 1
2 3 2 3
crossover
offspring1 offspring2
1 1
2 3 2 3
N31=0
N31=1 *
N31=1 N31*=0
N32=1 N32=0
N32=0 N32*=1
*
Crossover node is selected with the probability of Pc
d32
d32
d32
d32
*
*
d31 d31
d31* d31
*
d3 d3
d3 d3
*
*
A A
A A
A A
A
A
A A
A
A A
A
A
A A
A A
A
Q31A * QA32*
Q32 A
QA32 QA32*
feasible transition unfeasible QA31
Q31 A
QA31*
Fig. 3.5 Crossover of GNP with Learning and Evolution
1
2 3
mutation
Mutation node is selected with the probability of Pm
1
2 3
"Nij" are set at 0 or 1 based on the setting rule.
N32=0 N32=1
N31=0 N31=1
feasible transition unfeasible
A
A A
A
Fig. 3.6 Mutation of GNP with Learning and Evolution
第3章 最適なノード遷移の選択を行う学習進化型GNP 34 2.各ノードを確率Pmで突然変異ノードとして選択する。
3.各突然変異ノードのすべてのNijA, NijB, NijC. . . について0または1に，決められた規 則注1にしたがって変更する。
4.生成された個体を次世代の個体とする。
Fig. 3.6も簡単のため処理ノード3個のみのグラフ構造の例を表しているが，判定ノー
ドでの突然変異を考える時は，判定結果A, B，C，· · · に関してそれぞれ同様の操作を行 う。また，新たに発生したノード遷移（Nij = 0からNij = 1に変化した場合）に対応す るQijは0に設定する。