GAニューロを用いたエレベータ制御シミュレーション
日大生産工(院) ○高橋 昂大 日大生産工 松田 聖
１ はじめに
ニューラルネットワークを用いたシステム ではニューラルネットワークの出力値に教師 信号を与え、その比較により各ニューロン間 の結合加重を変化させることによりニューラ ルネットワークの学習を行っていく。しかし ながら、正しい教師信号を常に与えられると は限らないため、それに代わるものが必要に なる。本研究ではエレベータの制御をニュー ラルネットワークで行うが、出力値に対する 教師信号を明確に与えることは出来ない。そ こで教師信号を与え結合荷重を修正する代わ
りに、 GAを用いて結合加重自体を修正するこ
とにより、明確な教師信号を与えることなく ニューラルネットワークをGAの世代を重ね ることで学習させ、問題となる環境に最適な モデルに構成することを目的とする。
２ ニューラルネットワーク
ニューラルネットワークとは脳機能の特性 を計算機上のシミュレーションによって表現 した数理モデルである。ニューロン間の結合 加重を修正することにで、より正確な出力値 を出力するモデルへと学習する。本研究では エレベータのメイン制御および、再配置の行 動選択をニューラルネットワークで行う。
メイン制御を行うニューラルネットワーク は、利用客が各階の呼び出しスイッチを押し た場合に『現在のエレベータ配置、乗客の乗 降予定、乗客人数、一定時間後のエレベータ 配置予測状況』を入力とし、呼び出しがあっ た階に対し各エレベータが向かった場合どの
程度適しているかの評価値を出力する。
再配置の選択行動とは、一定時間ごとに実 行され、将来の利用客の呼び出しに対しより 素早い対応を取ることが出来るよう乗客が乗 って居ないエレベータのカゴを事前に移動さ せる行動のことである。
メイン制御ニューラルネットワークの構成 図を以下に示す。
再配置ネットワーク 入力
移動評価出力
入力値 再配置ネットワーク
入力
移動評価出力
入力値
・一定時間後のエレベータ配置予測
・一定時間後の乗客
・現在の乗客 入力値
・各エレベータ選択時の評価値 出力値
Fig1. メインニューラルネットの構成
Optimum Elevator Control By GA-Neural Network
Takahiro TAKAHASHI and Satoshi MATSUDA
次に再配置ニューラルネットワークの構成 図を以下に示す。
・一定時間後のエレベータ配置予測
・一定時間後の乗客
・現在の乗客
入力値
入力値 出力値
・移動選択フラグ
・移動推奨目的階 出力値
・一定時間後のエレベータ配置予測
・一定時間後の乗客
・現在の乗客
入力値
入力値 出力値
・移動選択フラグ
・移動推奨目的階 出力値
Fig2. 再配置ニューラルネット構成図
再配置ニューラルネットワークは一定時間 後にエレベータ３基がどのような配置になっ ているかを入力し、その結果エレベータの配 置に不都合が生じていると判断された場合、
推奨される目的階を出力する。すでに乗客が 乗っている場合は乗客の目的階への移動が優 先されるので再配置は実行されない。実行例 を以下に示す。
ある時刻の各エレベータに対し以下に示す ような移動が決定されているとする。
エレベータ1： 1 2 3 エレベータ1： 1 2 3 エレベータ2： 5 6 7 9 エレベータ2： 5 6 7 9 エレベータ3： 9 7
エレベータ3： 9 7
1 ：乗客降り 1 ：乗客降り
1 ：再配置
1 ：再配置
1 ：乗客呼出 1 ：乗客呼出
Fig3. エレベータの移動
このエレベータの移動を時間軸とともにリ スト化すると以下のようになる。
2 2 2 3 3
1 2 2 2 3 3 3 3 3 3 3 3 3
1 3 3 3 3 3 3 3
エレベータ1：
時間（t）
5 5 6 6 6 7 7 7 8 8 9 9 9 5 5 6 6 6 7 7 7 8 8 9 9 9
エレベータ2：
9 9 9 8 8 7 7 7 7 7 7 7 7 9 9 9 8 8 7 7 7 7 7 7 7 7
エレベータ3：
2 3 4 5 6
1 2 3 4 5 6 7 8 9 10 11 12 13
1 7 8 9 10 11 12 13
Fig4. エレベータ移動予定リスト
時刻t=13においてエレベータは3:9:7階に位 置することが予想される。時刻t=7以降のエレ ベータ1及びエレベータ3の乗客人数は0人な ので再配置が可能である。これら移動リスト と、乗客人数を再配置ニューラルネットワー クに入力し、エレベータを効率の良い位置へ 再配置させる。
再配置後の移動と移動予定リストは以下の 通りである。
エレベータ1： 1 2 3 1 エレベータ1： 1 2 3 1 エレベータ2： 5 6 7 9 エレベータ2： 5 6 7 9 エレベータ3： 9 7 5 エレベータ3： 9 7 5
1 ：乗客降り 1 ：乗客降り
1 ：再配置
1 ：再配置
1 ：乗客呼出 1 ：乗客呼出
Fig5. 再配置後のエレベータ移動
このエレベータの移動をリストとして以下 のように表現する。
2 2 2 3 3
1 2 2 2 3 3 3 2 2 1 1 1 1
1 3 2 2 1 1 1 1
エレベータ1：
時間（t）
5 5 6 6 6 7 7 7 8 8 9 9 9 5 5 6 6 6 7 7 7 8 8 9 9 9
エレベータ2：
9 9 9 8 8 7 7 7 6 6 5 5 5 9 9 9 8 8 7 7 7 6 6 5 5 5
エレベータ3：
2 3 4 5 6
1 2 3 4 5 6 7 8 9 10 11 12 13
1 7 8 9 10 11 12 13
Fig6. 再配置後エレベータ移動リスト
再配置ニューラルネットワークの実行結果 により、再配置移動階としてエレベータ１に1 階、エレベータ３に5階が設定される。この時 再配置フラグを出力することで、メインニュ ーラルネットワークを介することなく直接移 動する。なお、効率の良い配置は時間帯や乗 客の需要により変化することが予測されるの で、一様に決定することは出来ない。そのた め、後述のGAニューロを用いて最適な再配置 ニューラルネットワークを探索する。
最後に２つのニューラルネットワークの全 体図を示す。
移動評価
再配置フラグ
入力
再配置ネットワーク
・・・・・・
移動評価
再配置フラグ
入力
再配置ネットワーク 再配置ネットワーク
・・・・・・
Fig7. ニューラルネット全体構成図
利用客が各階に設置されている呼び出しボ タンを押した場合、メイン制御ネットワーク 及び、再配置ネットワークの両方にデータが 入力される。再配置ネットワークの出力デー タをメイン制御ニューラルネットワークの入 力として用いることにより、再配置の移動評 価を考慮した上で、各エレベータが呼び出し に応じた場合の評価値を得ることができる。
この評価値が最大のエレベータが呼び出しの あった階へ移動することになる。
再配置ネットワークのみを実行する場合は 再配置ネットワークを実行後、再配置フラグ と移動推奨目的階の値が出力され、その値へ とエレベータを移動させることでエレベータ 全体がその時間帯に適した配置へと再配置さ れる。
３ GA ：遺伝的アルゴリズム
GA:遺伝的アルゴリズムとは、近似解を探 索するメタヒューリスティクスアルゴリズム のひとつである。遺伝子で表現した個体を複 数用意し、ある環境における個体の適用度の 計算を行う。その適応度の高い個体を優先的 に選択し、交叉・突然変異などの操作を繰り 返しながら、最適解を探索していく。
各遺伝子のある環境への適応度を算出し、
その結果で降順ソートを行なう。その結果上 位は優秀な特徴を持つエリート遺伝子である として次世代へ保存する。反対に下位の遺伝 子はその特徴を残しても適応度が上がる可能 性は低いので削除する。中位の遺伝子は後述 の交叉や突然変異の操作を行い次世代の遺伝 子を生み出す親遺伝子となる。
0 1 0 0 1
0 1 1 0 1
0 0 0 1 1
1 1 1 0 1
0 0 0 0 0
50
20 80 70
10 0
0 0 1
0 30
エリートとして保存
交叉を行なう
削除 0
1 0 0
1 0 0 1 0 1
0 1 1 0
1 0 1 1 0 1
0 0 0 1
1 1 0 0 0 1
1 1 1 0
1 0 1 1 1 1
0 0 0 0
0 0 0 0 0 0
50
20 80 70
10 0
0 0 1
0 1 0 0 0
0 30
エリートとして保存
交叉を行なう
削除
Fig8. 選択と淘汰
交叉とは遺伝子列から数点を選びその交叉 点において選択した２つの親遺伝子の配列内 容を交換する。この操作により、前世代遺伝 子の特徴が引き継がれた次世代遺伝子が生成 される。
1 1 1 1 1
0 0 0 0 0
1 0 0 1 1
0 1 1 0 0
交叉前 交叉後
1 1 1 1
1 1 1 1 1 1
0 0 0 0
0 0 0 0 0 0
1 0 0 1
1 1 0 0 1 1
0 1 1 0
0 0 1 1 0 0
交叉前 交叉後
Fig9. ２点交叉図
GAの欠点のひとつに世代交代を繰り返して いくと類似した遺伝子ばかりになってしまう ことがある。その状況を打開する手段として 突然変異という操作を行う。交叉とはべつに 一定確率で遺伝子の一部をランダムに書き換 えるもので、この行動により遺伝子の多様性 を保つことが出来る。以下に突然変異の例を 示す。
0 1 1 0 1
突然変異前 突然変移後
0 1 1 0
0 11 00 11 11 00
突然変異前 突然変移後
0 1 1 0
0 0 1 1 0 0
Fig10. 突然変異
また、遺伝子の多様性を保つため一定世代 ごとに遺伝子群の一部を初期化する。これに より今までに無い特徴をもった遺伝子との交 叉が行なわれるため、局所解に陥る可能性を 下げる効果がある。
GA：遺伝的アルゴリズムは上記操作を繰り 返し行なうことにより次第にある環境により 適応した特長を次世代の遺伝子に遺伝され、
世代を重ねるごとにより環境に適した遺伝子 を残すことが可能であるが、結果が初期遺伝 子の生成に強く依存するので、ある環境に最 適な遺伝子を見つけるには複数回の試行が必 要である。
４ GA ニューロ
GA ニューロとはニューラルネットワーク の全結合加重をGAの１つの遺伝子として表 現することで、その遺伝子に対し交叉等の操 作を用いて、進化的に結合加重の修正を行い ニューラルネットワークの学習を行う。
本研究ではニューラルネットワークを用い
て、エレベータ制御のシミュレーションを行
う。前述の通り本来ニューラルネットワーク
の学習を行うためには教師信号が必要となる
が、本研究ではシミュレーションの結果をも
とに現在の遺伝子の評価を行い、それを元に
GAで次世代の遺伝子を生成していく。この方
式の利点は教師信号を使用することなくニュ
ーラルネットワークの学習が行なえるという
ことである
そこで、 GAというメタヒューリスティクスを 用いることにより教師信号を必要とすること なく結合加重を修正することが出来るため、
正しい教師信号を与えることが出来ないよう な問題であったとしても対象となる環境に最 適なニューラルネットワークが構築される。
以下に本研究で構築するGAニューロシス テムの概要を示す。
実験 ニューラルネット
評 価
GA
次 世 代 生 成
結合加重変化 実験 ニューラルネット
評 価
GA
次 世 代 生 成
結合加重変化
Fig11. GAニューロ概要
５ 実験方法
本研究は12階建ての商業ビルディングに 設置されていることを想定した３基のエレベ ータのシミュレーションをおこない、利用客 の平均待ち時間を最小化する。ビルの入口は １階のみとし、利用客の行動選択は複数のパ ターンから時間的に変更することにより、１ 日の利用客の状況変化を表現している。時間 帯ごとに GA を用いて最適な結合加重を探索 し、それを組み合わせることで、一日の時間 変化による利用客の需要変化に対応する。
以下に時間帯変化に対応するニューラルネ ットワークの変化を示す。
結合加重集合
朝に最適化 昼に最適化 夜に最適化
出力 入力
結合加重フラグ
Fig12. 結合加重の選択
現在の時間帯をニューラルネットワークと は別に入力し、ニューラルネットワークに用 いる結合荷重を時間帯により変更する。
本実験のGAに用いる1世代の遺伝子の数は 20で、実験は適応度が収束するか世代数が200 に達するまで行なう。各世代のエリート遺伝 子は上位２遺伝子、淘汰する遺伝子も下位２ 遺伝子と設定した。なお、 20 世代毎に下位遺 伝子の50％を初期化し、新たな遺伝子をラン ダムに生成する。
各時間帯に予測される利用客の『どこの階 へ行くか、どこの階で乗るか』という 2 種類の 行動をポワソン分布により決定する。
( )
k ! k e
N P
λ
k λ−
