遺伝アルゴリズムによる制約付きマルコフ決定過程の解法

遺伝 アル ゴ リズム による制約付 きマル コフ決定過程 の解法

平 山

克己

*・

河合

・社会開発工学専攻 。社会開発 システムエ学科

(1995年8月29日受理)

A SOlvingn/fёthod of a h/1DP with COnstraint by Genetic Algorithm

by

Katsumi HIRAYAMAl)・ Hajime KAWA12)

1)Course in Engiheering of Social Development 2)Departlnent of Social Systems Engineering

(Received August 29,1995)

ヽ￨「e cOnsider discrete time larkov decision prOcess(MDP)with finite state space,

finite action space and two kinds ofimmediate re、 vards The problem is to maximi3e time average reward generated by on reward ttream,subiect tO that the cther reward

is nOt〔Inaller than a prescribed value The probelin is analyzed in the range of pure stationary policies MDP、vith One optinaalty criteriOn and no constraint can be solved by usual poHcy improvement method,MDP ttrith One reward constraint can be solved by linear prograHュ Ining,in the range of■ 1lxed pOHcies On the other hand,hOwever, when都たe restrict the p01icies to pure polices the problem is some conbinatrial prOblenl,

fOr which any sOlving methOd has■ ot been discovered ln this paper,ve propose an approach applying Genetic Algorithm in Order to carry On a search process effectively and to obtain a near optilnal pure stationary pOlicy A numerical example is given tO examine he effeciency of the apprOach propOsed here.

1

は じめに

本論文では、有限状 態 空間 、有限決 定空間 、及び2極 類の直接利 得を持 つ離 散時 間マル コフ決定過程 (ヽ1村 kO、 D∝ にion Procζ馬:略して

MDP)を

取 り扱 い、一方 の利得か ら生 じる時間平均利得 をある与 え られ た値以上に保護す る純定常政策の中で,他方 の利得か ら生 じる時間平均利 得を最大 にす る政策 を定 める制約付

MDP問

題 について 考える。

一制約 を持つ

MDPは

,既にBculicr alid Ross l)によ り 混合戦略 の範囲で考察 され,最適政 策は、せいぜ い 二つ の純政策 の泥合政策 に よ り与 え られ なこ とが示 され てい る。ただ し,混合政 策の下では 各決定 を毎期FFf率的 に選 択す ることにな り,管理上面倒な点が多 く,純政策の範lll 内で最適政 策を求 め るこ とは現 実的な意味で重要な問題 であると思われ る。 しか し,純政策 に限定す ると、組合せ 的問題 とな り、厳密解 の導 出が非花に旺難 とな る墜 そ こで、本研究では制約付マル コフ決定過程 に対 して、 道伝アルゴ リズムに政策改善法を加味 しだ新 しいアプロー チを提案す る。

2

制 約 つ き

MDP

は じめに以下の記号 を定義す る。

r=(o,11…

,Ar) :状

態空間 Di=(1,2,…

:ri),状

態をにお ける状態空間 ?与 :状態万で決定々を選択 した ときの推移確率

_

。与ib与 :状態1で決定浄を選択 した ときに生 じる利得

F:純

政策の集合,すなわ ち S=Dlx,D2X,…・,X Di ●:純_{政策,すなわ ち}

,scS

ここです べての純政 策 に対 し,マル コフ決定過程 は完 全エル ゴティクであるとす る。す なわち,定常分布を持つ。 ′(d):政 策dを採 用 した ときの利得c与か ら生 じる 時間平均利得 ん(d):政 策,を採用 した ときの利得b与か ら生 じる 時間平均 利得 ■::政策,を 採用 した ときの定常分布 なお,表 現の簡潔化のため.Tと,cと,bとをそれぞれ,政 策,採用したときの推移確率および.状 態こに発ける利得 を表 す とす る。 ′(,),ん(d)は それ ぞれ,,(,).4(,)および ん(d),ri(,)('Cr) を未 知 数 とす る次 の連 立 方 程 式

(箪

イ

=∵咄時 中 ω

(Ⅲ

穂と

伊

=岬

申

_{n‥ ポ。}

の解 として与え られ る。あるいは,定常分布 を用 い

メ→=Σ

T!暉

0

ん

●

)=Σ

T,呼

律

)

々=Σ

TF?と,ブ

Cr

“

)

Σ

T,こ

と

い

) で 与 え られ る。 以 上 の 記 号 を 用 い る と我 々の 問題 は 3C(引

ん

(1)告In,,c♂}θ

(d) (7)

で表現 され る。

2.1

混 合 政 策 と 純 政 策 本研究では触れ ていないが、例えば図1のよ うに制約付 き

MDPを

混合政策 の範囲で考 える と、理論的に厳 密解 が得 られ るこ とが示 され てい る り。 しか し、混合政策 は 決定を確定的 には選 ばず、確率的に選ぶ政策である。 した がつて、意思決定者 に とっては純政策の範囲で考 える方が 現実的であ り、取 り扱 い易い と考 え られ る。 また、図1のよ うに混合政策 では端点 を結ぶ直線 ど時 間平均利得hの制約値oが 交わ る点が最適解 となる。 しか し、純政策 に限定す る と実行可能解 は離散的な点上 に存 在 し、時間平均利 得bの 制約 値αに よっては最適解 は端点 を結ぶ直線上にあるとは限 らず、組合せ 的問題 となってい る。そのため、理論的 に厳密解 を得 る手段 が現在 では存 在 しない。

3

遺伝 アル ゴ リズムの概要

遺伝 アル ゴ リズムは、1960年代にアメ リカのホー ラン ドによって基本的な考 え方が提唱 され た。自然界の生物集 回の中で、長 い進化 の歴 史 を通 じて予測 不可能な環境変 化に対応 できた個体のみが現在 に至っている と考 え られ る。生物 は、生 きつづ けるた めに優れ た親 の性質 を遺伝 子 として子に伝 える。 この よ うな、生物進化 の法則 と遺伝 の メカニズム を工 学的に取 り入れ 、近年はモダン とュー リステックス3)と_し て、最適化アル ゴ リズム として構成す る ものである4)。

3.1

遺 伝 ア ル ゴ リズ ム の 概 念 生物の各個体 は、それ ぞれ 固有 の染色体 を持 ち、染色 体は遺伝子 の配 列で構成 され てい る。ここで、決定変数″ を染色体に対応 させ て、次式の よ うな記号列で表丸

画 耐 章 罹 鳥 取 大 学 工 学 部 研 究 報 告 第

26巻

図1:混合政策 と純正策での最適化 ここに、れ は遺伝子に対応 し、遺伝子が置かれている 位置 を遺伝子座 と呼ぶ。また、各遺伝子が取 り得 る値 を 対立遺伝子を呼ぶ。その値は、0か1の整数、1か ら

Mま

での整数など、問題に応 じて定義 される。 上式のような記号列の表現 を遺伝子型 と呼び、その遺 伝子によって定まる個体の性質を表現型 と呼ぶ。 自然界における生物の進化過程では、ある世代 を形成 している個体の集合 (個体群)を考え、この個体の中で 環境への適応度の高い価体が多 く生 き残 るように洵汰 さ れる。そ して、交叉や突然変異が生 じて、次の世代が構成 される。これを最適化問題を解 く繰返 し過程に対応 させ る。すなわち、問題の解の候補 を複数個選んでお き、第t 回目の繰 り返 し計算における解集合 を次式のように構成 する5)Ol。 ズ(1)={21(1),″2(1),…:,α s(ι

)) (9)

ここで、Sは個体群 のサ イズ を表す。S個の解 の集合であ る個体群 は、洵汰、交又、お よび突然変異 とい う操作 (遺 伝演算子)を受 けて、次世代の個体群 を生 み出す。この よ うな操作 を繰 り返 して、世代 を十 分経 た後の個体群 は最 適解 の近傍 に収束す る と考 え られてい る。 stepl 世代 をι

=oと

する。S個の個体 (政策)をランダムに生 成 して、初期 個体群 χ(o)、 ズ(0)=(,1(0),T2(Ol,…・,Ts(0)) を設定 す る。(但し、各 個体 の遺伝子 は1穐κ の 10進 数 表示。) ste,2 各個体の表現型 を考慮 して、適応度 を決 め る。この適応 度に依存 した一定のルールで個体 の洵 汰 を行 な う。(ルー レット戦略、エ リー ト保存戦 略、ランク戦略) stcp3 」定の確率で交叉、突然変異 を行い、新 しい個体 を生成。 子 は親 と置 き変わ り新 しい世代 ズ(ι+1)、 ズ(ι+1)=(,1(t+1),τ2(tキ 1),・・・,2S(tキ1)} が形成される。 stepl 終了条件により終了 もしくはι

=t+1と

してstep2へ戻る。 このアルゴリズムの主要部分は、適応度設定 と適応度 の高い個体 を残す手続 き、お よび新 しい個体 を生成する 手続 きである。すなわち、洵汰により良質な個体を重点的 に固執 して探索 し、同時に交叉や突然変異により、解の探 索空間を広げているのである。これ らの手続 きが有効に 働 く時遺伝アルゴリズムは効力を発揮するのである09。

3.2

遺 伝 アル ゴ リズ ム の適 用 法 この節では、制約付 きマルコフ決定過程の遺伝 アルゴ リズムヘの導入、各パラメータの設定、及び設定 した3 ケースの適応度について説明す る。前節における記号列 で表される個体νlM2・…乃町°…拗vがマルコフ決定過程に おける釉政策にあた り、遺伝子Art力 f状態 をにおける決定 にあたる。また個体の長さⅣ は状態数 とな り、個体の遺 伝子座tに入ることができる遺伝子の数が、状態 tで 選択 できる決定の数である。 以下に、本研究における遺伝アルゴ リズムの適用手順 について述べる。 現個体群 をyと し、対象 とする個体 (政策)をpと す る。ま抹 (5)、 (6)よリゼ を求め、(3)、 (4)よ りG(pl、 打(p) を計算 し、表現型(んP,ダ)と する。主 な、ア｀ラメータを以 下に示す。 個体 (政策)Pct/の表現型:(ん ',♂ p) 個体の長さ(状態数):Ⅳ 個体群数 :J 個体P(ct/)の適応度:∬ また、適応度については次の3つのケースを設定 し、数 値実験 を行った。

<CASEl>政

策改善法 を考慮 しない場合

CASElは

CAだ

けの探索で、時間平均利得 んの制約 値。を満たさない個体に対 しては、ペナルテイー として適 応度を0にし、次世代の遺伝子 としてHf承しないように した。ペナルテイーとして んとaの乖離度に応 じて適応度 を減少 さすこともで きるが、今回は

CAの

みの探索で ど

こまで制約付 き

MDPに

適用で きるか を検証するために 今回は適応度を0と した。 t)ん '≧oのとき

Fp=プ

ウけ ん″

<oの

とき

Fp=0

<CASE2>政

策改善法

+ghの

傾 きを用いた適応度

CASE2は

GAと

政策改善法 とのハイブ リット型であ り、Hの制約oを満たさない個体に対 しては、政策改善法 によ り新 しい政策 を探索する。そ して、探索 した新 しい 政策の評価指標 をhg平面の傾 き(gの増分

/hの

増分) としている。 t)ん_'≧。の とき Fp=プ tt)θp<。の とき

れ

_'+ttl:=暉

+Σ

守

み立

ザ

ゴ を満たすん″_{、プを求める。次に}

(<CASE

応度

b:+Σ

?み J を最 大 にす る た'を求 め 、 Fp=(θ・ ―♂え p)/(んた°_一んフ )

3>政

策改善法+ペナルティーを用いた適

CASE3も

GAと

政策改善法 とのハ イプリット型であ る。

CASE3で

は、政策改善法により目的関数の値であ るGの値が改善 された ときだけ新 しい政策 を次世代の個 体 として採用 し、hの値が制約値oを満たさない場合、も しくは、Gの値が減少 した場合には次世代の個体 として 採用 しない。 しか も、政策改善法によって も制約値oを満 た していない個体に対 してはペナルテイーを課 し、次世代 では洵汰 されるように した。これによ り効率の悪い探索 空間を選けて通ることが可能 となる。 t)ん_'≧oの とき FP=θ

p

― tt)ん

_'<oの

とき

ん

_'+ぱ

=b子

+Σ

嗚可

ゴ を満たすんp、 ω子を求める。次に

b:+Σ

_嗚

ゴ を最 大 に す る た°を求 め 、 ftc)ん た°≧oかつ _す°_≧ゴ pをた・、(プ,ん_')を(θえ ・ ,れた°)に 置換 え Fp=θん° tib)んた°≧oかつ _すた°<♂P ″_=θ″ /β 加_)打た°<o Fp=0

4

数値計算例

図2∼図12は,個体数i20,状態数,10,決 定数;5,制約値 o=20,25,30,40,β =2.0直接利得a,直接利得b,推移確 率を以下の表 として

,2種

類の時間平均利得(h,g)をxy平 面上に示 したものである。政策1での直接利得a,直接利 1/1∞0) i=ユ 8 0 0 0 ∪ i=2 :J 2貿 0 0 0 0 i=4 2 0 1盛 ,7C 0 0 i=5 2 0 128 0 0 i=6 lf 0 0 0 0 0 i=8 0 0 0 0 0 3 l 0 0 0 0 政策2での直接利得a,

7 8 9 0 0 0 0 0 0 8 0 0 0 0 i=3 1( 1〔 0 0 り 0 0 0 0 i=5 1( 0 0 υ 0 0 0 i=G 5 0 0 0 0 U り 0 i=8 3 3t 0 0 0 0 0 0 0 0 0 0 U 0 327 鳥 取 大 学 工 学 部 研 究 報 告 第

26巻

政策4での直接オUtt a,直 接利得b,推移確率(1/10∞) 政策5での直接利得a,直接利得b,推移確率(1/101Xl) 図&CASEl(た >25)での(工,8)の変化

GA(h≧ 25)

閉 禾鴨

h

︲９ ︲６ И ︲２ ︲０ ８ ８ ｍ 叶 ゝ 脂 4 2 0

12

3

b l 2 3 4 5 i=1 6 0 0 0 i=2 6 0 0 0 0 0 i=3 0 0 0 i=4 l` 0 0 i=も 0 0 0 0 0 0 i=7 2( 0 i=8 11 0 0 0 0 0 i=9 1( 0 0 0 0 0 0

GA(h≧ 20)

嘲 齢 当 ト 18 18 14 12 10 8 6 4 2 0 囲 禾嘱畢h

255

1

狩

ｔ

GA(h≧ 30)

18 16 14 12 10 8 8 4 2 0

254

劉 禾γtth 40 図 雰CASEl(ん >20)での(h,8)の変化 図 4 CASEl(ん >30)での(■,8)の変 化

GAtts hの

1頃き

(h≧

20)

18 18 14 12

m 10

普 ₈ 6 4 2 0 閉 禾呼畢

h

40

0

図a cASE2(ん >20)で の(h,Dの変化 _{図 れ CASE2(ん>30)で}の(h,8)の変化

GA+ghの

1頃き

(h≧

30)

10 20 30 40 禾y早

h

︲８ ︲６ Ｍ ︲２ ︲０ ９ ８ ４ ２ ０ ｍ 叶 導 性

232

93

0

GA+shの

傾き

(h≧

25)

19 16 14 12

m 10

撃 干ぐ ₈ 6 4 2 0 閉 米彎早

h

GA+shの

1頃き

(h≧

40)

19

0

3

10 20 30 40 50 禾町尋

h

12 10 8 8 4 2 0 ｍ 叶 導 κ 図6・ CASE2(ん >25)での_(h,g)の変化 _{図&CASE2(ん >40)での} (h,g)の変化

鳥 取 大 学 工 学 部 研 究 報 告 第

26巻

政簾改善法十ペナルテ ィー付き適応度

(h≧

20)

18 18 14 12 10 8 6 4 2 0

96

23

0

禾町尋

h

政策改善法十ペナルテ ィー付き適応度

(h≧

30)

亜 叶 当 催 18 18 14 12 10 8 6 4 2 0 10 20 30 40 禾呼尋

h

政策改善法

+ペ

ナルテ ィー付き適応度

(h≧

25)

ｍ 齢 導 ト 19 16 14 12 10 8 8 4 2 0 図 観 CASE3(ん>20)での(h,glの変化 図1■ CASE3(ん>30)での_(h,g)の変化 政菊改善法

+ペ

ナルテ ィー付き適応度

(h≧

40)

12 10 8 8 4 2 0 閉 30 示町尋

h

63

０

導

１

2

図 lo cASE3(ん >25)での(11,g)の変化 _{図1み cASE3(ん>40)での} (h,g)の変化

前飾で提案 した3つの

CASEに

ついて、時間平均利 得bの 制約値αを変化 させて、数値計算 を行ったのでその 結果 を示す。これ らの数値計算は全て同 じ初期解でいず れも

300世

代 まで計算 した結果である。図2∼図4はoが 20、 25、 30、

40の

ときの

CASElで

の世代推移 における(h,g)の値の変化を示 したものである。図中の数 字は世代数を示 している。図5∼図8は

CASE2で

の世 代推移における(h,8)の値の変化を示 したものである。図 9∼図12は

CASE3で

の世代推移における(h,3)の値の 変化 を示 した ものである。

5

考察

CASElの

CAだ

けの探索では予想以上の効果があっ た0■ラか し、制約値oの値が大きくなるにつれ、制約を満た した解 を見つけるまでに時間がかかっている。また

o=40

の時には

300世

代で も制約 を満た した解 を探索するこ とがで きなかった。

CASE2の

GAと

政策改善法のハイプリッド型では、

CASElよ

りも早期 に制約 を満た した解を探索 してい る ことが判る。また、

CASElで

は探索不可能であった

o=40の

時でもわずか

18世

代で最適解に到達 している。

CASE3の

ハイブリット型+適応度にペナルテイーを 与 える

CAで

は、

CASElの

約半分の世代で

CASE

l同等 もしくはそれ以上の探索能力 を発揮 している。ま た、

o=20の

時には

CASE2の

方が早 く最適解に到達 しているように見えるが実は

CASE2は

最適解には到 達 してはお らずgの 値 は167で あつた。しか し、

CASE

3では最適解g=10,8(a=25の時 と同 じ)に達 していた。 また、

300世

代以内で

CASE3は

oの値がいずれの時 も最適解に達 していた。 これらのことか ら、

CAだ

けのランダム探索 よりもG Aと政策改善法のハ イブリット型で構成 した探索法の方 が効率的な探索が実現で きていることが判る。 時間平均利得hの制約値。1よ大 きくなるほど、探索空間 は小 さ くな り、実行可能解で さえ探索 は困難 になる。逆 に、制約値。が小 さくなるほど、探索空間は広が り、実行 可能解の中か ら最適解 を探索することが困難 となる。今 回の数値実験ではどちらの場合で も政策改善法 と

GAの

ハイプリット型が

GAだ

けの探索 よりも有効であること が確認 された。 また、前者の場合には

CASE彦

の適応度を政策改善 法によって更新 されるCの増分とした方が有効であ り後者 では

CASE3の

_{適応度にペナルティーを与える方が有効} であろう。これは、制約 を満た していない個体(政策)の 適応度にペナルティーを与えることにより、個体群内に無 駄な探索 となる個体を留めないためであると考えられる。

6

おわりに

本研究では制約付 き

MDP問

題について、

GAと

政策 改善法のハイブリット型を提案 したが、非常に良い結果が 得られた考える。今回は政策改善法は各個体(政策)に 1 回しか行っていないが、繰 り返 し行えば必ず制約を満たす 個体を生成することも可能である。これは次回の課題 と したい。 適応度の設定方法の速いによって、同 じハイブリットJ」 でも

CASE2,CASE3の

ように探索週裡が異なつて くることは興味深い。また、適応度の設定方法は今回の数 値実験 を行った方法以外にも、様々な方法が考えられる。 制約についても、今回は 1つ であったが

GAで

は複数の 制約 も取扱 うことが可能である。 しか し、その際には適 応度の設定方法をよく考慮 しておかない と効率的な探索 は行えないであろう。 今後、これらの課題についても研究 を継続 してい きた Vヽ。

参考 文 献

1)BOude与 F.J,and RossiK,W.:Optim』Pdたies ror

Controlled MalkOv Chains with a Constrttnt,

J Math.Anal.Appl.,Vol.112,PP 236-252,1985

2)H.Kalval,N.KatohiVariatIIcc COnStrained Malkov Dicision Proco欝_{, Journa1 0r Operauons Rkさ erch Society oF} JapmiVo30 Nol Marcr1 1987

3)北川敏夫:マル ヨフ過程、共立 出版

4)茨木俊秀 :組 合せ最適化法 をめ ぐる最近 の話題、 モ ダ ンヒュー リスティックスの新展 開 一Cenctic A!go rithm,Simulated Anncaling,Tabu Search,Neural Net法 は 本当に有効か ?― 、日本オペ レー ションズ・リサ ーチ学 会 第

30回

シンポジウム、pp.卜10(1993). 5)北野宏明:遺伝 アルゴリズ ム、産業 図書、(1993) 6)樋口哲也、北野宏明:遺伝 アル ゴ リズム とその応用、情 報処理Jllly 1993 Voi 34 N07 p 871∼p.883 7)三宮信夫:遺伝アル ゴリズムに よる最適化問題の解法、 第

36回

システム制4av情報学会研 究発表公 演 会P,9∼ p.18

8)BrankO,SOucek,and The IRIS GЮ

up:DYNAMIC,

GENETIC,AND CHAOTIC,PROGRAMING,WILEY IN― TER SCIENCE.

9)Da d.E,Goldberg:Genetic Algorithms in Scarcl1 0pti‐

■■zation and Mtthine Learning,ヽ ￨にもlcy Publshing COm‐