| 題名 | 最大クリーク問題に対するk-opt局所探索法の枝刈りの検討 |
| 著者 | *岡本 智奈美 (岡山理科大学工学部情報工学科), 渡邉 好幸, 赤木 勇斗 (岡山理科大学大学院工学研究科), 片山 謙吾, 南原 英生, 西原 典孝 (岡山理科大学工学部情報工学科) |
| Page | p. 144 |
| Keyword | 組合せ最適化, 局所探索法, 最大クリーク問題, 枝刈り |
| Abstract | 組合せ最適化問題に対する代表的な局所探索法として，可変深度探索法や(可変)k-opt局所探索法(k-opt local search, KLS)などが知られている．我々の研究グループでは，このアイデアをもとに，最大クリーク問題(maximum clique problem, MCP)等の困難な問題に対してKLSやその変形アルゴリズムを示し，メタ戦略への導入によって，極めて良好な結果が得られることを確認しつつある． 本論文では， MCPに対するKLSを取り上げ，KLSの探索をさらに効率化する，複数の枝刈り法を示し，評価実験を通してそれらの性能について検討する． |
| 題名 | 最大クリーク問題に対する新たなKick法の検討 |
| 著者 | *渡邉 好幸 (岡山理科大学大学院工学研究科), 片山 謙吾, 南原 英生, 西原 典孝 (岡山理科大学工学部情報工学科) |
| Page | p. 145 |
| Keyword | 組合せ最適化, 最大クリーク問題 |
| Abstract | 実用上重要な組合せ最適化問題の一つとして最大クリーク問題がある．この問題に対して我々はメタ戦略の枠組みのもとでk-opt局所探索法（k-opt Local Search, KLS）にもとづく反復k-opt局所探索法（Iterated k-opt Local Search, IKLS）を提案している．IKLSは局所探索法であるKLSと局所解脱出法（Kick）などのオペレータから構成される． MCPにおけるKick法は複数あるがいづれもグラフ上の情報を用いる一般的な考え方のもとで設計されている．そこで本研究では，局所探索中に得られた情報をもとに局所解からの脱出を図る新たなKickについて検討する． |
| 題名 | スーパーパズ の局面が成功不可能であるための十分条件 |
| 著者 | *新谷 敏朗 (福山大学/工学部情報工学科) |
| Page | p. 146 |
| Keyword | ゲーム, スーパーパズ, 成功不可能, 判定条件 |
| Abstract | スーパーパズはトランプの一人遊びの一種である。このゲームでは52枚のカードをシャッフルしてすべて表向きに並べた4行13列の初期局面から初めて，ルールに従ってカードを移動していき，所定の成功局面に至ることが目的である。ある局面が成功可能かどうかは，その局面を根とするゲーム木を作成できれば判定できる。しかし，ゲーム木の節点数が非常に多くなるため，成功可能と予想されるがまだ解が得られていない局面も存在する。本報告では、ある局面が成功可能かどうかをその局面におけるカードの並び方から判断できるかどうかについてのひとつの十分条件が得られたので報告する。 |
| 題名 | 連続行動出力を持つ学習オートマトンの提案 |
| 著者 | *田中 洋平, 原 元司 (松江工業高等専門学校) |
| Page | p. 147 |
| Keyword | 学習オートマトン, 強化法, LR-I強化法, Actor-Critic法, ベイズ推定器 |
| Abstract | 学習オートマトンとは、特性が不明である未知環境下において学習性能を発揮する可変構造確率オートマトンである。 学習オートマトンが動作する環境は、学習オートマトンが選択した行動に対して評価を示す実数値を返すしくみとなっており、学習オートマトンはその情報をもとに自身の状態確率ベクトルを更新する。このように、学習オートマトンは、環境との相互作用を繰り返すことで、最適行動を漸近的に学習していく。しかし、従来の学習オートマトンは有限な行動集合を対象としており、連続的な行動出力を要する環境には直接応用することができない。そこで、本研究では連続的な行動出力のできる新たな学習オートマトンを提案し、実験によって基本的な学習性能を示す。 |