Proceedings of the 54th Annual Conference of the Institute of Systems, Control and Information Engineers (ISCIE), Kyoto. May 19–21, 2010

F34-1
進化ロボティクスにおける多目的 GA に関する一考察

Multiobjective Genetic Algorithms on Evolutionary Robotics
摂南大学○ 片田 喜章

Y. Katada
Setsunan University
Abstract
Evolutionary multiobjective optimization algorithms have attracted much researchinterest in recent years. In robotics, evolutionary techniques also have been applied to design
multiobjective behavior of autonomous robots. However, it has been reported that such problems
as to employ neural networks as a controller for a robot include neutrality in their fitness landscapes.
In this work, we applied a mutiobjective genetic algorithm to design the neural controller for amobile robot in a looping maze problem in order to investigate evolutionary dynamics of them.

1

はじめに適応度関数

3

近年，進化計算分野では進化計算がもつ多点探索の利点を活かし進化型多目的最適化 (EMO) が盛んに研究さ

Floreano ら [1] は自律移動ロボットによる迷路内周回問題を扱い，次の適応度関数を設定している．

れている．一方，自律ロボットの多目的行動獲得に進化f=計算を適用するという研究も以前から行われている．しかし，ロボットの制御器に人工神経回路網 (ANN) を適用した場合，その進化ダイナミクスに多くの中立性を含むことが報告されている．本研究では，移動ロボットの進化に多目的 GA を適用し，その進化ダイナミクスに関して基礎的な考察を行う．

1M axStep

M axStep∑V (1 −√∆V )(1 − smax ) (1)t=1

ここで，V = (|VL |+|VR |)/2Vmax ，∆V = |VL −VR |/Vmax ，smax = max{sj : j = 1, · · · , Ns } (sj : センサー値，Ns :√センサー数)．V はロボットの動き，1 − ∆V はロボッ
トの直進性，1 − smax は障害物からの回避性をそれぞれ表す．文献 [1] では (1) 式を使って図 1 に似た環境で2ロボットが障害物の周囲を回る行動を GA によって獲タスク
本稿では自律移動ロボットによる迷路内周回問題を扱う (図 1)．ロボットに搭載する距離センサは図に示す距
離まで測定が可能であり，物体までの距離と反比例する値を出力するように設定する．ロボットの移動機構を左右二輪独立駆動型と仮定し，その中心位置 (x, y) と姿勢Lθ は次式のように更新する．xt+1 = xt + VR +Vcos θt ,2−VL
Lyt+1 = yt + VR +Vsin θt , θt+1 = θt + VR2R
. ここで，2VR と VL は両車輪の周速度，2R は車輪間隔とする．モー得している．しかし予備実験をしてみると環境の大きさやセンサー配置など環境設定の違いから必ずしも (1) 式を使って障害物の周囲を回るような望ましい行動が獲得できないことがわかった．そこで，本稿では (1) 式の各項を目的関数にとり，多目的最適化問題として定式化す
る．項数から 3 目的にとることも可能であるが，直進移動性と障害物回避性の 2 目的最大化問題とする．

Maximize fi (i = 1, 2)

タ出力は制御器として採用する ANN の出力値 z によっ

f1 =て次のように与えられる: VR,L = Vmax × z. ここで，Vmax は車輪の最大周速度とする．
f2 =1
M axStep
1M axStep

4

計算機実験

4.1

実験設定

M axStep∑V (1 −(2)
√∆V )

(3)

t=1
M axStep∑(1 − smax )

(4)

t=1

ロボットの初期位置を図 1 の位置とする．試行は 200ステップ経過したときに終了する．ロボットの初期姿勢
図 1: 迷路内周回問題における実験環境

θ0 を −45◦ から 45◦ ずつ変えた試行を 3 回行い，(3)(4)式を用いて平均を計算し，目的関数の値とする．

第 54 回 システム制御情報学会研究発表講演会– 609 –

Normarized MaxSum

している短いビットストリングでコーディングされる

ANN を用いる．ここで各ノードは全結合されている．
これらの結合荷重を決定変数とし，{−1, 1} のいずれかの値をとる．入力ノード数は Ns = 7，中間ノード数は240160220150200180160140
uniform
1point12010001，出力ノード数は 2(モータ数) とする．
進化手法として今日最も広く利用されている EMO の1 つであり，Deb ら [2] によって提案されている NSGA-II

Normarized Range

ロボットの制御器として，我々の研究グループで提案

100200300
Generation

140130120110

uniform
1point100400500(a) MaxSum

0100200300
Generation

400500(b) Range

図 3: 世代数に対する収束性と多様性の尺度の推移を用いる．個体数を 50，文献 [2] に従い交叉確率 0.9(一様交叉・1 点交叉)，突然変異確率は 1/L(L は遺伝子長)，終了世代数を 500 と設定する．NSGA-II の実行回数を10 とし，得られた非劣解集合に関しては 10 回のうち典型例を，後述する統計量に関しては 10 回の平均値を示す．
実験結果

4.2

図 4: 最終世代で得られた非劣解の振舞い

図 2(a), 2(b) に 200, 500 世代で得られた非劣解を示す．
存在する．したがって，この場合 MaxSum が選好解へ

NSGA-II の探索終盤では集団内のほとんどの個体はランク 1 になるため，個体の優劣は主に混雑度に依存するの収束性を表すと考えられる．一様交叉を用いて得られと考えられる．このため，個体数を 50 としたこともあた選好解の振舞いを図 4 に示す．

りパレートフロントに対し解が均等に分布していない．
また，200 世代と 500 世代の間に一部分ランクの逆転が5おわりに見られる．はじめにで述べたように本問題には多くの中

本稿では，移動ロボットの進化に多目的 GA を適用し，立性を含むと考えられるが各目的関数で値が等しい個体その進化ダイナミクスに関して考察を行った．実問題の群は目的関数空間で距離が近くなるため混雑度を考慮しため解の精度は議論しづらく，最終世代で得られた非劣た選択により間引かれ，部分的にしか観察されない．

解集合は多様性を十分にもつとは言えないがパレートフ

次に本問題で適用した 2 つの交叉の影響を比較するた

ロントの形状を概ね把握できていると考えられる．

め，パレートフロントの中心方向への収束性を表す尺度

今後は局所パレート最適解を乗り越えるための手法やである MaxSum[3] および目的関数空間での個体群の多パレートフロント上で多様性のある解集合を導出する手様性を表す尺度である Range[3] の世代数に対する推移法の適用を行う予定である．本問題の選好解は目的関数を図 3(a)，3(b) に示す．一様交叉を用いた方が MaxSum空間である限定された領域内に存在する可能性があるこが高くなることがわかる．Range は進化の初期および終とから，本問題の特徴を精査し選好情報を利用した手法

盤で一様交叉を用いた方が少し高くなっている．本問題の導入も行いたい．また，中立性が EMO に与える影響における選好解は障害物に接触せずできるだけ直進すをさらに調べたい．

る，つまり周回行動を示すものである．図中には示していないがこれらはほぼ f1 > 0.1 かつ f2 > 0.15 の領域に

0.3

g=500
g=200Maximize f2

Maximize f2

0.3

0.2

0.1

0.0

[1] S. Nolfi and D. Floreano: Evolutionary Robotics: The
Biology, Intelligence, and Technology of Self-Organizing
Machines; MIT Press, (2000)

g=500
g=200

[2] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan:
A Fast Elitist Multi-Objective Genetic Algorithm:
NSGA-II; IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 182–197 (2000)

0.2

0.1

0.0
0.0

0.1

0.2Maximize f10.3(a) 一様交叉

図 2: 非劣解集合

参考文献

0.00.10.2
Maximize f1(b) 1 点交叉

0.3[3] 塚本, 能島, 石渕: 多数目的最適化問題における進化型多目的最適化アルゴリズムの問題点とその改良手法に関する考察; システム制御情報学会論文誌 Vol. 22，No. 6，
pp. 220–228 (2009)– 610 –