著者

片岡 寛明 原 章 長尾 智晴

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.12, pp.3232-3241, 2003-12-15

参考文献数

12

被引用文献数

5

---

本論文では,遺伝的プログラミング(Genetic Programming; GP)を改良した手法である遺伝的オートマトン(Genetic Automata Generation; GAUGE)を提案し,本手法が不完全知覚をともなうエージェントの行動制御に有効であることを示す.不完全知覚問題に対する従来手法としては,インデックスメモリを用いる手法やGPオートマトンが提案されている.しかし,インデックスメモリは解が複雑になると探索空間が膨大になり最適化が困難になる.また,GPオートマトンの性能はあらかじめ設定した状態数に左右される,といった問題点がある.GAUGEでは,個体は記号間にパスを張りめぐらしたグラフ構造をとり,内部状態の違いによる条件分岐を自動生成することにより問題解決を行う.また,本手法は問題に必要な状態数を進化過程で獲得するため,GPオートマトンのように状態数に対する試行錯誤を必要としない.本論文では,本手法を迷路探索問題やタルタロス問題に適用しその有効性を検証する.実験の結果,本手法は,従来手法と比べて冗長なノード数を抑えつつ,適切に状態数を設定したGPオートマトンと同等の性能を示した.問題解決に必要な状態数が未知の問題に対しては本手法が有効であると考えられる.Generally, it is difficult for Genetic Programming (GP) to solve perceptual aliasing problems. In previous work to solve such problems, Index memory and GP-Automata have been proposed. However both of the methods have problems. Since the search space of an index memory is huge, it is difficult to obtain a well tuned program by GP. The performance of GP-Automata is influenced by the fixed number of states. Moreover, individual structure of both methods is tree structure.Therefore, redundant nodes will increase and search efficiency will get worse.In order to solve such a problem, we propose a new method, Genetic Automata Generation; GAUGE.Individuals in GAUGE have structure like an automata. Our method automatically obtains the adequate number of states for solving a given task.Several experiments to investigate the performance of our method were executed using Map Search Problems and Tartarus Problems. These experimental results showed that GAUGE was applicable to perceptual aliasing problems. And GAUGE showed the performance equivalent to a well tuned GP-Automaton.