多目的モデルに基づくインタラクティブ遺伝的アルゴリズムに関する研究
廣安 知之
研究期間 平 成 20年 度 ～ 平 成22年 度
概要：
遺伝的アルゴリズム（Genetic Algorithm: GA）は生物の遺伝と進化を模倣した確率的多点探索手法の一つである．インタラクティブGA（interactive GA: iGA）は，GAの評価部分を人間が評価することにより，人間の感性や嗜好といった数量化できない問題に対応することが可能である．本研究では，これまで単一目的のモデルとして定式化されてきたiGAに対して多目的モデルを提案し，多目的モデルに拡張する際の問題点の整理，検討，システム構築を行うことを目的とする．これにより，よりユーザーの嗜好に沿った解選択が可能となる．本研究のサブ目的として，設定された目的を構成する複数目的の抽出および相反する目的関数の評価方法の検討などがあげられる．
研究目的：
GAは定式化の際の柔軟性が非常に高く，多くのタイプへの問題の適応が可能である．さらに，近年の計算機能力の爆発的な向上を背景に多くの問題に適用され数多くの成果をあげている．GAでは複数の探索点を生成し，それらの適合度値，および設計変数の情報を基に，交叉，突然変異，選択といった遺伝的操作を行うことで，次の探索点群を生成する．これらの操作を繰り返すことで最終的に良い解を得ることが可能となる．iGAはこれらの適合度値の計算を行う際に，人間（ユーザー）が点数付けを行うことにより，システムやシミュレーションが行うことのできない，完成や嗜好情報を取り扱うことを可能とするシステムである．iGAは多くの分野で利用されており，多くの成果が上がっている．
本研究では，Web上でのネットショッピングシステムなどでユーザーがショッピングを行う際に，ユーザーの嗜好情報を基に膨大な商品候補の中から購入する候補を絞り込むようなシステムの構築を念頭に置いている．例えば，ユーザーがTシャツを購入することを想定した場合，非常に多くの色や形，柄などを組み合わせ，ユーザーの好みのTシャツを提示することは，非常に有効である．また，このようなシステムはTシャツだけでなく多くのショッピングサイトで利用でき他の分野にも応用可能である．このようなシステムを構築する際には，iGAは非常に強力なアルゴリズムの一つであると考えられる．研究代表者のグループでは，iGAのシステムを構築し，ウェブ上でのショッピングサイトへの応用を検討している．
さて，従来のiGAでは単一目的を取り扱っている場合がほとんどである．上記のTシャツの例で言えば，「ユーザーの好みにあうTシャツ」であるとか「夏らしいTシャツのデザイン」などといった目的がそれである．このモデルでは基本的には，一つの解をユーザーが決定することを想定している．この場合，システムが提示する解候補は，探索前半では多様性のある解が提示され，探索後半では次第に解が収束し，ユーザーが解を決定することとなる．しかしながら，研究代表者の行った予備実験では，商品選択などを行う際には，ユーザーは常に多くの多様な解候補の中から解を選択することを希望していることが明らかとなった．しかしながら，一方で，ランダムな解候補をユーザーに提示することで解候補の多様性の維持を図るだけでは不十分であった．さらに，得られているベスト解の近傍のいわゆる準最適解もしくは，局所解を提示しても，ユーザーは解候補に多様性を十分に認識しなかった．また，探索過程においては，ある解の近傍をベストな解として選択していたユーザーがあるステップで突然，別の解をベストとして選択することも多々見られた．これらのことから，従来のiGAで用いられている単一目的のモデルでは不十分であると考えられる．そこで，本研究では，これらの問題に対応するために，多目的モデルによるiGAを検討する．
従来のiGAでは，問題の決定変数xを定式化し，人間（ユーザー）の中に求めたい解の適合度関数がΦが一つ存在するものと仮定し，Φ(x)が決定変数xから構成されるのが単一目的モデルである．一方で，人間（ユーザー）の中に適合度関数がΦが一つ存在するところは同様であるが，Φ(f1, f2)といったように複数の目的関数から適合度関数Φが構成され，それぞれの目的関数f1(x), およびf2(x)がそれぞれ決定変数xで構成されるのが多目的モデルである．単一目的では，適合度関数Φの値が類似した解を表示することが，多様性のある解の提示になるのに対して，多目的モデルでは，複数の目的が相反する場合，そのパレート解集合を提示することで，ユーザーに多様性のある解集合の提示が可能である．さらに，複数の目的から構成されているため，着目していたベストな解とはかけ離れた解候補へユーザーの嗜好が変化することも，このモデルであれば説明がつけやすい．すなわち，単一目的モデルよりも多目的モデルのほうが，商品選択などで見られる行動にあったモデルであるといえる．
本研究では，iGAにおけるこの多目的モデルの検討を行い，システムの構築を行う．
研究成果：
2010年度
対話型遺伝的アルゴリズム（interactive Genetic Algorithm:iGA）は，人の感性情報を用いて最適化を行う手法の一つである．iGA では，人間が遺伝的アルゴリズム（Genetic Algorithm:GA）における評価の部分を人間が行うことで，ユーザの嗜好や勘といったこれまで数値化できなかった対象に対しても最適解を求めることが可能である.
本年度は，iGAの多目的モデルへの適用において，iGAを利用してトレードオフ関係にある複数の判断要素を自動的に抽出するアルゴリズムについて検討を行った．これを行うことにより，単一目的の最適化問題として対象となる問題を設定し，その単一目的が複数のトレードオフ関係を有するサブ目的から構成される場合においてもiGAを対応させることが可能となる．
提案アルゴリズムでは，一対比較を行い，それらの結果をAHPで分析し，矛盾点を探る．この矛盾点を解消する判断要素を見つけることで，その解候補が各判断要素に沿っている度合いを抽出した．また，それらの判断基準を基に最適化を行う場合，評価部において世代間の評価値の問題が存在する．その問題を解決するため，世代間の評価値スケールを調整する改良アルゴリズムも提案を行っている．
以上の提案アルゴリズムの有効性を検討するため，前者では評価エージェントを用いてシミュレーション実験を行い，後者は被験者実験により提案手法の有効性の検討を行った．これらの実験の結果から，複数の判断要素が抽出できる可能性とその結果を基に最適化が可能であることが明らかとなった．
2009年度
2009年度は，インタラクティブ遺伝的アルゴリズム（対話型遺伝的アルゴリズム）の多目的モデルへの適用において下記の2点の検討および開発を行った．
１）多目的遺伝的アルゴリズムのインタフェースおよび適合度の検討：昨年度に引き続きインタラクティブ遺伝的アルゴリズムを多目的最適化問題に適用するためのインタフェースの検討を行った．本研究では，優越関係を陽に取り扱う方法を検討しているが，世代毎に評価が異なるという問題が発生し，その問題に対応する必要がある．成果は22年度に開催される国際会議へ投稿を行った．および論文などで発表する予定である．
２）インタラクティブ遺伝的アルゴリズムのための解探索空間の生成方法の検討：これまでインタラクティブ遺伝的アルゴリズムにおいては，設計変数空間を定義しそこに解候補を生成，ユーザの評価を行ってきた．一方，ウェブ上の商品の推薦システムなどにおいてインタラクティブ遺伝的アルゴリズムを利用する場合，解候補がすでに存在し，それに対応する解探索空間を生成する必要がある．その自動生成アルゴリズムの開発と検討を行った．商品の関連性から自動的に解探索空間を生成する方法を提案した．
2008年度
2008年度は，インタラクティブ遺伝的アルゴリズム（対話型遺伝的アルゴリズム）の多目的モデルへの適用において下記の4点の検討および開発を行った．
１）多目的遺伝的アルゴリズムのインタフェースおよび適合度の検討： これまで複数の目的関数を陽に取り扱った対話型遺伝的アルゴリズムの研究はほとんど行われていない．まず，解候補の表示方法について検討し，得られているパレート解集合を陽に取り扱う手法を検討した．また，探索のステップ間で適合度値の絶対的評価が異なるため，スケーリングを行うことにより絶対的評価を近づける方法を提案した．これらの結果は21年度の国際会議および論文などで発表する予定である．
２）対話型遺伝的アルゴリズムにおける多峰性関数に適した交叉手法の開発：人間の嗜好のランドスケープは単峰性ではなく，多峰性であると考えられる．これに適した交叉手法を開発した．
３）対話型遺伝的アルゴリズムにおける汎用的な問題に対する設計変数の自動生成手法の開発：対話型遺伝的アルゴリズムのシステム構築において，大きな問題となるのが，対象問題の設計変数空間を一から構築する必要があることである．これは実用化においては障害となる．ウェブ上の情報から対象問題の設計変数空間を自動的に抽出する手法を提案した．
４）対話型遺伝的アルゴリズムを利用したシステム構築：浴衣のデザインやサインオンの生成に対話型遺伝的アルゴリズムを利用するシステムを構築した．
プロジェクト関連論文
査読有りの学術論文および国際会議：
- 2011年度
- 2010年度
- Classified-Chime Sound Generation Support System using an Interactive Genetic Algorithm, Noriko Okada, Mitsunori MIKI, Tomoyuki HIROYASU and Masato Yoshimi, Artificial Intelligence and Soft Computing, Lecture Notes in Computer Science, Volume 6114/2010, pp.173-180, (2010)
- The Effects of Button Arrangement on Evaluations in Interactive Genetic Algorithms, Tomoyuki HIROYASU, Yuusuke YONEDA, Misato TANAKA, Yasunari SASAKI and Mitsunori MIKI, IEEE Proceedings of 2010 IEEE World Congress on Computational Intelligence, (2010)
- 対話型遺伝的アルゴリズムにおける表現型空間の自動生成手法の提案， 田中 美里， 廣安 知之， 三木 光範， 佐々木 康成， 吉見 真聡， 横内 久猛， 日本知能情報ファジイ学会 論文誌, Vol.22, NO.6， pp.720-732， (2010)
- Discussion of Evaluation Methods for Multiobjective Interactive Genetic Algorithm, Tomoyuki HIROYASU, Yusuke KOBAYASHI, Yasunari Sasaki, Misato TANAKA, Mitsunori MIKI and Masato YOSHIMI, Proceedings of World Automation Congress, 2010, CD-Rom, (2010)
- Automatic Generation Method to derive for the design variable spaces for interactive Genetic Algorithms, Misato TANAKA, Tomoyuki HIROYASU, Mitsunori MIKI, Yasunari SASAKI and Masato YOSHIMI, IEEE Proceedings of World Congress on Computational Intelligence 2010 (WCCI 2010), pp.1256-1263, (2010)
- The effects of button arrangement on evaluations in interactive genetic algorithms., Tomoyuki HIROYASU, Yuusuke YONEDA, Yasunari SASAKI, Mitsunori MIKI and Hisatake YOKOUCHI, IEEE Proceedings of 2010 3rd International Conference on Biomedical Engineering and Informatics, CD-Rom, (paper, No2160), (2010)
- 2009年度
- Application of MOGA Search Strategy to SVM Training Data Selection, Tomoyuki HIROYASU, Masashi Nishioka, Mitsunori MIKI and Hisatake YOKOUCHI,
Evolutionary Multi-Criterion Optimziation, Lecture Notes in Computer Science, Springer, LNCS 5467, pp.125-139, (2009)
- 多数目的最適化における進化的探索の問題点， 廣安 知之， 石田 裕幸， 三木 光範， 横内 久猛， 同志社大学 理工学研究報告, Vol.50, No.1， pp.24-33， (2009)
- ユーザの嗜好に基づく初期個体生成を行う対話型遺伝的アルゴリズム， 雨宮明日香， 三木光範， 廣安知之， 同志社大学 理工学研究報告, Vol.50, No.1， pp.34-45， (2009)
- Extraction of Design Variables using Collaborative Filtering for interactive Genetic Algorithms, Tomoyuki HIROYASU, Misato TANAKA, Mitsunori MIKI and Hisatake YOKOUCHI, IEEE Proceedings of International Conference on Fuzzy Systems, pp.1579-1584, (2009)
- 多数目的最適化を利用したパラメータチューニング， 廣安 知之， 石田 裕幸， 三木 光範， 横内 久猛， 情報処理学会 論文誌:数理モデル化と応用(TOM), Vol.2, No.3， pp.14-26， (2009)
- 2008年度
- Discussion of a Crossover Method using a Probabilistic Model for interactive Genetic Algorithm, Tomoyuki HIROYASU, Misato TANAKA, Fuyuko ITO, Mitsunori MIKI and Hisatake YOKOUCHI, SCIS & ISIS2008 Proceedings of Joint 4th International Conference on Soft Computing and Intelligent Systems and 9th International Symposium on advanced Intelligent Systems, CD-Rom, pp.1055-1060, (2008)
- Design of Japanese Kimono using Interactive Genetic Algorithm, Maiko Sugahara, Mitsunori MIKI and Tomoyuki HIROYASU, IEEE 2008 International Conference on Systems, Man, and Cybernetics, pp.185-190, (2008)
- Discussion of Offspring Generation Method for interactive Genetic Algorithms with Consideration of Multimodal Preference, Fuyuko Ito, Tomoyuki Hiroyasu, Mitsunori Miki and Hisatake Yokouchi, Simulated Evolution And Learning, Lecture Notes in Computer Science, Springer, LNCS 5361, pp.349-359, (2008)
- 対話型遺伝的アルゴリズムにおける嗜好の多峰性に対応可能な個体生成方法の検討， 伊藤 冬子， 廣安 知之， 三木 光範， 横内 久猛， 人工知能学会 論文誌, Vol.24, No.1， pp.127-135， (2009)
講演：
- 2011年度
- 2010年度
- 商品探索時におけるユーザの嗜好のモデルの変化の獲得， 松村 冬子， 廣安 知之， 三木 光範， 佐々木 康成， 大向 一輝， 武田 英明， 情報処理学会 第78回情報処理学会数理モデル化と問題解決(MPS)研究会 研究報告， (2010)
- 多視点的思考を向上させるインタラクティブな情報提示の検討， 田中 美里， 廣安 知之， 三木 光範， 吉見 真聡， 横内 久猛， 人工知能学会 第11回AI若手の集い (MYCOM2010) 講演論文集， pp.52， (2010)
- 対話型遺伝的アルゴリズムにおける設計変数間の依存関係に基づく交叉手法の基礎， 田中 美里， 廣安 知之， 三木 光範， 吉見 真聡， 佐々木 康成， 横内 久猛， 人工知能学会 第５回進化計算フロンティア研究会(SIG-ECF)予稿集， pp.57-60， (2010)
- 多目的対話型遺伝的アルゴリズムを利用した人の嗜好軸の抽出， 小林 祐介， 廣安 知之， 田中 美里， 佐々木 康成， 三木 光範， 進化計算学会 進化計算シンポジウム 2010 講演論文集， pp.59-65， (2010)
- クラスタリングと主成分分析を用いた対話型遺伝的アルゴリズムの交叉手法の検討， 田中 美里， 廣安 知之， 三木 光範， 佐々木 康成， 吉見 真聡， 横内 久猛， 進化計算学会 進化計算シンポジウム 2010 講演論文集， pp.215-218， (2010)
- 視線追跡を用いた対話型遺伝的アルゴリズムにおける ユーザの興味偏向の検証， 米田 有佑， 田中 美里， 廣安 知之， 佐々木 康成， 吉見 真聡， 進化計算学会 進化計算シンポジウム 2010 講演論文集， pp.271-274， (2010)
- 2009年度
- 多目的最適化問題における対話型遺伝的アルゴリズムの検討， 小林 祐介， 廣安 知之， 三木 光範， 横内 久猛， 人工知能学会 第23回全国大会講演論文集 session-， pp.154-154， (2009)
- 商品推薦のための対話型遺伝的アルゴリズムの設計変数の導出， 田中 美里， 廣安 知之， 三木 光範， 横内 久猛， 人工知能学会 第10回AI若手の集い (MYCOM2009) 講演論文集， (2009)
- 対話型遺伝的アルゴリズムを用いたチャイム音生成支援システム， 三木 光範， 岡田 典子， 廣安 知之， 吉見 真聡， ヒューマンインタフェース学会 ヒューマンインタフェースシンポジウム2009 予稿集， pp.405-408， (2009)
- 多目的対話型遺伝的アルゴリズムにおける評価部の検討， 廣安 知之， 小林 祐介， 佐々木 康成， 田中 美里， 三木 光範， 情報処理学会 研究報告, Vol.2009-MPS-76 No.8 ， pp.1-8， (2009)
- 多目的最適化問題における個体群構造の違いによる解性能の評価， 野田 徹， 廣安 知之， 三木 光範， 吉見 真聡， 横内 久猛， 情報処理学会 研究報告, Vol.2009-MPS-76 No.41 ， (2009)
- 2008年度
- 好みのカラーイメージに基づく初期個体を生成させる対話型遺伝的アルゴリズム， 菅原 麻衣子， 三木 光範， 廣安 知之， 人工知能学会 2008年度全国大会（第22回）論文集2B1-2, CD-ROM， (2008)
- 対話型遺伝的アルゴリズムにおけるサポートベクターマシンを用いた初期個体生成， 雨宮明日香， 三木光範， 廣安知之， 人工知能学会 第22回全国大会論文集２Ｂ１－１, CD-ROM， (2008)
- 対話型遺伝的アルゴリズムにおける確率モデル構築による子個体生成の検討， 田中美里， 伊藤冬子， 廣安知之， 三木光範， 人工知能学会 第22回全国大会論文集3H2-1, CD-ROM， (2008)
- 対話型遺伝的アルゴリズムにおける嗜好の多峰性および依存関係を考慮した個体生成方法の検討， 伊藤 冬子， 田中 美里， 廣安 知之， 三木 光範， 横内 久猛， 日本機械学会 No.08-35 第8回最適化シンポジウム2008 講演会論文集， pp.103-108， (2008)
- 協調フィルタリングを用いた対話型遺伝的アルゴリズムのための設計変数の抽出， 田中 美里， 廣安 知之， 三木 光範， 横内 久猛， 情報処理学会 研究報告2008-MPS-72, Vol.2008 No.126， pp.175-176， (2008)
- 訪問者に応じたチャイム音生成支援システムの構築， 三木 光範， 廣安 知之， 岡田 典子， 情報処理学会 情報処理学会第71回全国大会講演論文集, 3M-6， (2009)
本：
キーワード
謝辞
本プロジェクトは平 成 20年 度 ～ 平 成22年 度の間，科学研究費補助金（課題番号 ２０５００１４６）の補助を受けている．