題名 | ノード配置問題に対するk-opt局所探索法の枝刈りによる効率化 |
著者 | *赤木 勇斗, 渡邉 好幸, 片山 謙吾, 南原 英生, 西原 典孝 (岡山理科大学) |
Page | pp. 259 - 260 |
Keyword | 最適化 |
Abstract | 組合せ最適化問題に対する重要な局所探索法として,Lin とKernighan によるLin-Kernighan 法(LK 法)または可変深 度探索法(Variable DepthSearch, VDS) が知られている.これは"単純な近傍操作" を連鎖的に適用することで生成される 解集合を改めて大きな近傍として捉える近傍探索のアイデア である.これまでに我々の研究グループでは,VDS のアイデアにもとづくk-opt 局所探索法(k-opt LocalSearch, KLS) を,最大クリーク問題,2 次割当問題,バイナリー2 次計画問題,最大多様性問題,ノード配置問題(NodePlacement Problem, NPP) などの困難な問題 に対して示し,メタ戦略 である反復局所探索法やMemetic アルゴリズム等の枠組みに導入することで,極めて高い探索性能が得られることを示している.しかしながら,KLS の探索効率をさらに向上させる枝刈りに関しては検討の余地が残されており,この種の効率化によって,KLS を導入するメタ戦略全体の効率化が可能になると考えられる.そこで,NPP に対するKLS を取り上げ,その標準形および変形アルゴリズムにおける枝刈りについて検討する. |
題名 | 類似画像検索手法Spectral Hashingの実現 |
著者 | *小室 翼 (島根大学) |
Page | p. 261 |
Keyword | Spectral Hashing, 機械学習 |
題名 | スーパーパズの成功率 |
著者 | *新谷 敏朗 (福山大学工学部情報工学科) |
Page | p. 262 |
Keyword | スーパーパズ, 探索, 深さ優先, ゲーム情報学 |
Abstract | スーパーパズはトランプの一人遊びである。52枚のカードをシャッフルして表向きに並べた4行13列の初期局面からルールに従ってカードを移動していき,所定の成功局面に至ることが目的である。ルール上列数を減らしてもプレイが可能である。フルサイズの13列ではゲーム木の節点数が非常に多くなるため,解を得るためには多くのメモリを必要とする。このゲームの成功率は82%以上あると予想されているが,詳しい検討はほとんどされていない。4列から13列までの場合について成功率を計算した結果,成功率が列数の増加に対して単調減少ではなく,下に凸の曲線状になることと13列の場合の成功率が約85%程度であることを明らかにした。 |
題名 | 相関ルールとGPを用いたポートフォリオ戦略木の最適化 |
著者 | *足立 真仁 (鳥取大学大学院工学研究科), 木村 周平, 松村 幸輝 (鳥取大学) |
Page | p. 263 |
Keyword | 遺伝的アルゴリズム, 遺伝的プログラミング, 相関ルール, ポートフォリオ |
Abstract | 本研究は,進化計算手法と相関ルールに基づいたポートフォリオ戦略の最適化に関する新しい手法を提案する。先ず,遺伝的アルゴリズム(以下,GA)により最適なポートフォリオを作成する(1)。そして,相関ルールに基づいて有効なテクニカル指標を見出し,これらで構成する戦略木を遺伝的プログラミング(以下,GP)で最適化する。以下,本システムの仕様と実験結果から有用性を検討する。 |
題名 | 遺伝的アルゴリズムによるオプション裁定取引の最適化モデル |
著者 | *伊藤 義浩, 松村 幸輝, 木村 周平 (鳥取大学/工学研究科) |
Page | p. 264 |
Keyword | GA, 裁定取引 |
Abstract | オプションはデリバティブの一種で,原資産株を将来の一定の日において,一定の価格で取引を行うコールオプションとプットオプションがある。このオプションの売りと買いでポートフォリオを組んだ場合,オプションの権利行使価格とプレミアム価格との関係からオプション特有の裁定機会が発生することが知られている。本研究は,このようなオプションの裁定機会を捉えて自動的にプログラム売買する裁定取引システムを,遺伝的アルゴリズムを用いて構築する新しい手法を提案する。 |