1. 概要

遺伝的アルゴリズムは生物の進化過程にヒントを得たアルゴリズムであり、工学の分野では特に最適化問題に用いられる。ここでは類似画像検索パラメータの最適化に遺伝的アルゴリズムを応用しており、さらに対話的遺伝的アルゴリズムへの応用や、新たな遺伝的アルゴリズムへの発展なども研究の対象である。

2. 対話型遺伝的アルゴリズムを用いた画像散策

遺伝的アルゴリズムとは生物進化の原理に着想を得たアルゴリズムであり、進化的な発送に基づいた新たな最適化の枠組として注目を集めている。このアルゴリズムは必ずしも生物の進化過程を忠実に再現したものではないが、遺伝的操作と遺伝子の選択過程を繰り返すことで、試行錯誤的に最適解を探索することが可能である。この性質ゆえに遺伝的アルゴリズムは、特に従来の手法では適用が困難な非線形探索空間を探索する応用に力を発揮する。

本研究でこの遺伝的アルゴリズムを適用するのは、検索パラメータの最適化という問題である。画像検索システムをより高度なものとするためには、ユーザが検索時に重視する画像特徴に対して的確に大きな重みづけを付与して検索を行う必要がある。ただしこのような重みづけの付与をユーザに任せる方法は、重み係数の数が多くなるにつれて困難となるため、何らかの方法で自動的に最適化する必要がある。

そこで本研究では対話型の遺伝的アルゴリズム、一般的には模擬育種法や人為選択法と呼ばれる手法、を用いて類似画像検索のパラメータを最適化する方法を研究する。このような対話型の遺伝的アルゴリズムは、生物の進化過程と人間の評価過程とを有機的に統合する方法論に特徴があり、ヒューマンインタフェース技術として有望な技術である。この方法では、ユーザは画像空間を散策しながら、検索画像に評価を与えるという形でシステムにフィードバック(評価点)を返す。するとシステムは、そのフィードバックを個々の遺伝子に対する適応度に変換するので、遺伝的アルゴリズムの枠組を用いて適切な検索パラメータを持つ遺伝子を進化させていくことができる。こうして、ユーザが画像空間を散策するうちに、徐々にユーザが所望する画像を検索することが可能となる。

このような遺伝的アルゴリズムの応用に適したアルゴリズムとして、「待ち行列型遺伝的アルゴリズム」を提案し、このアルゴリズムの探索性能評価やパイプライン的分散処理による高速化などについて検討している。このアルゴリズムは非同期的な遺伝的操作を行うために世代という概念が希薄であり、したがって世代あたりの個体数などの制限がない。また適切な構成とすることにより、探索性能が優れていることもわかってきた。このアルゴリズムについては今後はさらに追究していく考えである。

3. 関連するトピック

4. 参考文献(全リスト

  1. 北本 朝展, "領域・空間情報を表現するグラフ構造を用いた類似画像検索", 東京大学工学系研究科電子工学専攻博士論文, 1997年03月 [ 概要 ]
  2. 北本 朝展, 高木 幹雄, "待ち行列型遺伝的アルゴリズムを用いた対話的な画像散策法", 人工知能学会誌, Vol. 13, No. 5, pp. 728-738, 1998年09月 [ 概要 ]
  3. 北本 朝展, 高木 幹雄, "進化的計算論に基づく対話的な画像散策法", 第4回知能情報メディアシンポジウム, pp. 173-180, 1998年12月 [ 概要 ] [ PDF ]
  4. 北本 朝展, 高木 幹雄, "パイプライン型遺伝的アルゴリズムを用いた対話的な画像散策", ワークショップ「インタラクティブ進化的計算論」, pp. 31-36, 1998年03月 [ 概要 ] [ PDF ]
  5. 北本 朝展, 高木 幹雄, "パイプライン型遺伝的アルゴリズムによる模擬育種法を用いた類似画像検索規準の学習", 電子情報通信学会技術報告, Vol. HIP96-4, pp. 17-22, 1996年06月 [ 概要 ]

5. 参考文献について

さらに勉強したい方には、以下の文献が出発点となるでしょう。

H. Takagi, Interactive Evolutionary Computation: Fusion of the Capacities of EC Optimization and Human Evaluation, Proceedings of the IEEE, Vol. 89, No. 9, pp. 1275-1296, 2001.

また未発表でやりかけの研究としては、以下のものがあります。あまり参考にはならないと思いますが、誰かの役にたつかもしれませんので、ここに置いておきます。

  1. Kitamoto, A., "A Queue-Based Genetic Algorithm (QGA)", Unpublished manuscript, pp.1-9, available at http://agora.ex.nii.ac.jp/~kitamoto/research/ec/unpublished.pdf, Jan. 1999. [ PDF ]