TOP > 国内特許検索 > 最適化システム、解探索方法及びプログラム > 明細書

明細書 :最適化システム、解探索方法及びプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4934800号 (P4934800)
公開番号 特開2006-277137 (P2006-277137A)
登録日 平成24年3月2日(2012.3.2)
発行日 平成24年5月16日(2012.5.16)
公開日 平成18年10月12日(2006.10.12)
発明の名称または考案の名称 最適化システム、解探索方法及びプログラム
国際特許分類 G06N   3/00        (2006.01)
G06N   3/12        (2006.01)
FI G06N 3/00 550C
G06N 3/12
請求項の数または発明の数 5
全頁数 14
出願番号 特願2005-093036 (P2005-093036)
出願日 平成17年3月28日(2005.3.28)
新規性喪失の例外の表示 特許法第30条第1項適用 平成16年9月27日、28日 電気関係学会九州支部連合会主催の「平成16年度 電気関係学会九州支部連合大会(第57回連合大会)」において文書をもって発表
審査請求日 平成19年7月5日(2007.7.5)
特許権者または実用新案権者 【識別番号】504258527
【氏名又は名称】国立大学法人 鹿児島大学
発明者または考案者 【氏名】小野 智司
【氏名】中山 茂
【氏名】片山 公博
個別代理人の代理人 【識別番号】100090273、【弁理士】、【氏名又は名称】國分 孝悦
審査官 【審査官】稲垣 良一
参考文献・文献 特開2000-082055(JP,A)
特開2001-325041(JP,A)
特開2002-170097(JP,A)
特開2004-326201(JP,A)
廣安知之,三木光範,谷村勇輔,PC-Clusterにおける並列分散遺伝的アルゴリズムの実装,同志社大学理工学研究報告,日本,2003年 5月14日,Vol.40, No.2,15-24頁,URL,http://web.archive.org/web/20030514023407/http://www.is.doshisha.ac.jp/academic/papers/pdf/99/9907-1tanimura.pdf
調査した分野 G06N 3/00
G06N 3/12
特許請求の範囲 【請求項1】
サーバ計算機とマスタ計算機と複数の計算機とを有する最適化システムであって、
前記マスタ計算機は、
複数の解候補である個体群を生成する解候補生成手段と、
前記解候補生成手段により生成された前記個体群を前記サーバ計算機に対して送信する第1の送信手段とを有し、
前記複数の計算機は夫々、
前記サーバ計算機が保持する前記個体群の全てを取得する取得手段と、
前記取得手段により取得された前記個体群の各適応度を、当該計算機内に保持され、他の装置に対して送信されない当該計算機のユーザの個人情報に基づいて評価する評価手段と、
前記評価手段により評価された前記個体群の各適応度を前記サーバ計算機に対して送信する第2の送信手段とを有し、
前記マスタ計算機は、
前記複数の計算機による前記個体群の各適応度の評価結果を前記サーバ計算機から回収する回収手段と、
前記回収手段により回収された、前記複数の計算機による前記個体群の各適応度の評価結果に基づいて、解を探索する解探索手段とを有することを特徴とする最適化システム。
【請求項2】
前記マスタ計算機は、
前記回収手段により回収された、前記複数の計算機による前記個体群の各適応度の評価結果を記憶する記憶手段を更に有し、
前記第1の送信手段は、前記記憶手段に適応度の評価結果が記憶される個体以外の個体を送信することを特徴とする請求項1に記載の最適化システム。
【請求項3】
前記解探索手段は、解が複数の値の組み合せから構成される組合せ最適化問題を解くことにより解を求めることを特徴とする請求項1又は2に記載の最適化システム。
【請求項4】
サーバ計算機とマスタ計算機と複数の計算機とを有する最適化システムによって実行される解探索方法であって、
前記マスタ計算機は、
複数の解候補である個体群を生成する解候補生成ステップと、
前記解候補生成ステップにより生成された前記個体群を前記サーバ計算機に対して送信する第1の送信ステップとを有し、
前記複数の計算機は夫々、
前記サーバ計算機が保持する前記個体群の全てを取得する取得ステップと、
前記取得ステップにより取得された前記個体群の各適応度を、当該計算機内に保持され、他の装置に対して送信されない当該計算機のユーザの個人情報に基づいて評価する評価ステップと、
前記評価ステップにより評価された前記個体群の各適応度を前記サーバ計算機に対して送信する第2の送信ステップとを有し、
前記マスタ計算機は、
前記複数の計算機による前記個体群の各適応度の評価結果を前記サーバ計算機から回収する回収ステップと、
前記回収ステップにより回収された、前記複数の計算機による前記個体群の各適応度の評価結果に基づいて、解を探索する解探索ステップとを有することを特徴とする解探索方法。
【請求項5】
請求項に記載の解探索方法をコンピュータに実行させるためのプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、例えば携帯電話等の計算資源を利用した分散組合せ最適化方式に好適な技術に関するものである。
【背景技術】
【0002】
パーソナルコンピュータやワークステーションなどの通常の計算機と比較すると、携帯電話は演算能力や通信速度こそ劣るものの、無線通信能力が高く、個人に最も身近で私的な計算資源とみなすことができる。携帯電話の普及台数と端末の性能向上速度を考慮すると、携帯電話の計算資源としての潜在的な価値は高く、複数の携帯電話を用いて計算を行うことで、大規模な問題解決の実現が期待される。
【0003】
近年、白血病治療法検証プログラムUD Agentや、HIVウィルスの化合物テストを行うFight HYPERLINK "mailto:AIDS@homeなど" AIDS@homeなど、一般の計算機ユーザの余剰計算資源の提供をもとに、インターネットを介して大規模な問題解決を行うプロジェクトが行われている。待機状態の携帯電話上で上記のプログラムを実行できれば、膨大な数の携帯電話を社会貢献に用いることができると考えられる。しかし、第3世代携帯電話は、演算プロセッサの高速化やデータ通信速度の改善、データ通信料の定額サービスが開始されるなど、携帯電話の性能の拡充が進んではいるが、バッテリ消費などの観点から、携帯電話ユーザにとって気軽に計算資源を提供できる状況には至っていない。
【0004】
近年の携帯電話は、電子メール送受信、Webページ閲覧などの情報端末としての機能が進化するとともに、個人の嗜好や私的な情報をより多く含むようになった。以下では、このような情報をプライバシと称す。プライバシを利用することにより、個々のユーザに応じたきめ細やかなサービスの提供や、ユーザの満足度の高い意志決定支援などが期待される。
【0005】
しかし、プライバシは基本的に、他人に知られたくない情報を含むため、利用する際には情報の漏洩に注意が必要となる。このため近年、モバイルエージェント技術によりプライバシを安全に利用する研究が行われている(例えば、非特許文献1参照)。モバイルエージェントに基づく方式は、会議日程調整にように、求める解が単一または2、3個の値の組合せであれば、移動と交渉を繰り返しながら、実用的な時間内に解を得ることができる。
【0006】

【非特許文献1】伊藤,新谷:"モバイルエージェント間の多重交渉に基づくグループ代替案選択支援システムについて",情処論,Vol.39,No12,pp.3165-3176(1998)
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかしながら、求める解が多数の値の組合せからなり、各携帯電話上のプライバシを利用しながら解候補を評価しつつ値の最適な組合せを求める場合、解を構成する変数や値の総数が増加するにつれ代替案の総数が指数関数的に増加し、エージェントの移動回数および交渉回数が増加してしまう。各個人のスケジュールを考慮した時間割編成や、メール送受信、通話記録などの人間関係を表す情報を用いた座席配置など、携帯電話上のプライバシや嗜好情報をもとに組合せ最適化を行うことで、メンバが納得できる合意の形成が期待できる問題は多数存在する。このため、携帯電話上の情報を安全に利用し、実用的な時間内で組合せ最適化を行う方式の実現が望まれている。
【0008】
そこで、本発明の目的は、例えば携帯電話に保持されるプライバシや嗜好情報等を保持したまま、それらを利用した分散組合せ最適化を可能とすることにある。
【課題を解決するための手段】
【0009】
本発明の最適化システムは、サーバ計算機とマスタ計算機と複数の計算機とを有する最適化システムであって、前記マスタ計算機は、複数の解候補である個体群を生成する解候補生成手段と、前記解候補生成手段により生成された前記個体群を前記サーバ計算機に対して送信する第1の送信手段とを有し、前記複数の計算機は夫々、前記サーバ計算機が保持する前記個体群の全てを取得する取得手段と、前記取得手段により取得された前記個体群の各適応度を、当該計算機内に保持され、他の装置に対して送信されない当該計算機のユーザの個人情報に基づいて評価する評価手段と、前記評価手段により評価された前記個体群の各適応度を前記サーバ計算機に対して送信する第2の送信手段とを有し、前記マスタ計算機は、前記複数の計算機による前記個体群の各適応度の評価結果を前記サーバ計算機から回収する回収手段と、前記回収手段により回収された、前記複数の計算機による前記個体群の各適応度の評価結果に基づいて、解を探索する解探索手段とを有することを特徴とする。
本発明の解探索方法は、サーバ計算機とマスタ計算機と複数の計算機とを有する最適化システムによって実行される解探索方法であって、前記マスタ計算機は、複数の解候補である個体群を生成する解候補生成ステップと、前記解候補生成ステップにより生成された前記個体群を前記サーバ計算機に対して送信する第1の送信ステップとを有し、前記複数の計算機は夫々、前記サーバ計算機が保持する前記個体群の全てを取得する取得ステップと、前記取得ステップにより取得された前記個体群の各適応度を、当該計算機内に保持され、他の装置に対して送信されない当該計算機のユーザの個人情報に基づいて評価する評価ステップと、前記評価ステップにより評価された前記個体群の各適応度を前記サーバ計算機に対して送信する第2の送信ステップとを有し、前記マスタ計算機は、前記複数の計算機による前記個体群の各適応度の評価結果を前記サーバ計算機から回収する回収ステップと、前記回収ステップにより回収された、前記複数の計算機による前記個体群の各適応度の評価結果に基づいて、解を探索する解探索ステップとを有することを特徴とする。
本発明のプログラムは、前記解探索方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【0010】
本発明によれば、例えば携帯電話に保持されるプライバシや嗜好情報等を保持したまま、それらを利用した分散組合せ最適化を行うことが可能となる。
【発明を実施するための最良の形態】
【0011】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【0012】
本実施形態では、大規模な組合せ最適化問題で有効な遺伝的アルゴリズム(Genetic Algorithm:GA)を、計算機および複数の携帯電話上で分散実行するものである。通常の計算機上で交叉、突然変移などの解候補生成の処理を行い、携帯電話上で解候補の評価を行うことにより、携帯電話上のプライバシを解候補評価に安全に利用しつつ、携帯電話上での計算量を最小限に抑えることができる。
【0013】
次に、分散GAの2つのモデル、および携帯電話を用いた従来の分散GAについて述べる。
-複数集団型(島モデル)-
図1に示すように、集団をいくつかの部分集団に分割し、それぞれの部分集団に対して独立に遺伝的操作を適用する分散GAを島モデル型分散GA(Island Genetic Algorithm:IGA)と呼ぶ。IGAは並列性が高いだけでなく、部分集団が独立に進化するので、集団全体としての多様性を高く保つことができる利点がある。
-単一集団型-
GAを最適化計算に応用する場合、各個体の適応度は他の個体の適応度とは独立に計算可能である。この点に注目して、図2に示すような適応度関数の評価を並列処理することにより高速化を図る分散並列GAが提案されている。選択、交叉、突然変移などの遺伝的操作を1つのマスタプロセッサに集中させるため、画像フィルタの自動設計など適応度評価に時間を要する計算に適している。
-携帯電話を用いた島モデル型分散GA-
柴山、高田、庄野、城:"iアプリを用いた分散GAの実装"、第9回情報処理学会MPSシンポジウム、pp.215-258(2003)では、IGAを複数の携帯電話で実行する方式が提案されている。これはNTTドコモのJava(登録商標)仮想マシン搭載携帯電話上で、iアプリとして並列計算プログラムを動作させるものであり、ナップザック問題を複数の携帯電話を用いて解くものである。携帯電話間での直接通信は実現が困難であるため、Webサーバを介して島間での移住処理を行う。この文献では、実際の携帯電話を用いて実験を行っており、組合せ最適化の計算を携帯電話で行えることを示している。しかし、パーソナルコンピュータやワークステーションではなく、携帯電話に並列計算を行わせる利点が不明瞭であり、複数の携帯電話を用いてIGAを実行する必然性が低い。
【0014】
以下では、本発明の実施形態として、携帯電話上のプライバシを用いて組合せ最適化を行う方式を示す。
【0015】
本方式では、GelernterらによるLindaモデル(D.Gelernter:"Generative Communication in Linda",ACM Trans.on Programming Languages and Systems,Vol.7,NO.1,pp.80-112(1985))に基づく分散並列環境を、オブジェクト共有空間Java(登録商標)Spacesを用いて実現する。Java(登録商標)Spacesを用いることにより、Java(登録商標)が動作可能な計算資源であれば、分散並列処理に容易に参加させることが可能となり、様々なOSを搭載した計算機、携帯情報端末、および携帯電話を利用することができる。また、インターネットなどの汎用のネットワークを利用できる。計算資源の動的な参加、離脱にも容易に対応できるなどの特徴を持つため、計算機だけでなく携帯電話を主たる計算資源とする本方式に適している。
【0016】
Java(登録商標)Spacesを用いた分散並列環境において、容易に分散並列処理を実現できる環境やAPIを提供するJSGrid、および、キーワードを付記するだけで、通常のスタンドアロン型のプログラムを分散並列プログラムへと自動で変換する言語Espaceが提案されている。Java(登録商標)Spacesを利用することにより、将来的にJSGridおよびEspaceの利用が可能となり、分散並列プログラムの開発コストを抑えることが可能となる。
【0017】
また、本方式では、Java(登録商標)Spacesを介して解候補を送受信することにより、携帯電話上で、個人情報に基づいた解候補の評価を行う。よって、各個人の嗜好や条件を他人の携帯電話、計算機に送信せずに、全員の嗜好、条件を満たす解を生成することが可能である。個人情報や嗜好が他の計算機に送信されないことは、携帯電話のユーザに安心感を与える。このため、より率直な嗜好の入力を促すことができ、結果として満足度の高い解を得ることができる。
【0018】
本方式が対象とする問題は、各個人の嗜好を充足する離散値の集合を求める組合せ最適化問題であり、ユーザ数が増加するとその探索空間は指数関数的に増加する。このため、大規模な探索空間内において効率的に最適解を発見できる探索アルゴリズムが必要となり、本実施形態では遺伝的アルゴリズムを採用する。
【0019】
本実施形態で用いる分散並列環境では、インターネットおよび携帯電話事業者のネットワークを利用するため通信コストが大きい。またJava(登録商標)Spacesを用いた分散並列環境では、小さなデータを頻繁に送受信することよりも大きなデータをより低い頻度で送受信することが望ましい。よって、解候補の生成と評価を頻繁に行う必要がある山登り法などの単点探索よりも、集団内の全解候補を一度に生成、評価できる多点探索アルゴリズムである遺伝的アルゴリズムが適している。
【0020】
なお、IGAを基本とし、従来の負荷分散や初期収束回避を目的とした、柴山、高田、庄野、城:"iアプリを用いた分散GAの実装"、第9回情報処理学会MPSシンポジウム、pp.215-258(2003)に提案される分散GAとは異なり、本実施形態で用いるGAは、上述した単一集団型を基本とする。通常の単一集団型分散GAは解候補評価の負荷分散を目的とするが、本実施形態で用いるGAは、プライバシを用いた解候補の評価を各携帯電話で行う機能分散型のGAである。
【0021】
ここで提案する分散組合せ最適化方式は、基本的に汎用であり、組合せ最適化問題、制約充足問題などに適用することが可能であるが、理解を容易にするために、以下に示す部屋割問題を用いて本方式の説明および評価実験を行う。
【0022】
部屋割問題は、個々人の嗜好を満足するように、人を部屋へと割り当てる問題である。部屋割問題は、人数が増加すると探索空間のサイズが指数関数的に増加し、全員の嗜好を満たす解を発見することが困難になる。
【0023】
部屋割問題の解は、図3に示すような一次元の染色体として表現できる。これは、巡回セールスマン問題(Traveling Salesman Problem:TSP)と類似の染色体表現であり、部屋割問題においてもTSPにおいて用いられるPartially Mapped Crossover(PMX)やサブツアー交換交叉など、致死遺伝子の発生を抑え、ビルディングブロックをなるべく保持する交叉方式を利用することが可能である。
【0024】
各個人の嗜好は、図4に示すように、それぞれの人と相部屋になりたい度合い(好悪度)の集合から構成される。本実施形態では、Java(登録商標)2 Micro Edition(J2ME)を用いて携帯電話上のプログラムを実装するが、J2ME単体では小数を扱うことができないため、好悪度の最小を0、最大を100とする。染色体Ciの適応度F(Ci)は、以下の式に従って計算する。
【0025】
【数1】
JP0004934800B2_000002t.gif

【0026】
ここで、rは部屋の総数を、QRjはRjの定員数を、xjkは部屋Rjに割り当てられたk番目の人を、Pa(b)は人aの人bに対する好悪度を表す。好悪度同様、適応度も0から100の間の整数値をとる。
【0027】
本実施形態における分散組合せ最適化方式の構成とJava(登録商標)Spacesを用いた分散並列処理の概念とを図5に示す。本方式は、HTTPサーバとJava(登録商標)Spacesサーバとを兼ねた計算機10(以下、サーバ計算機10と称す)、遺伝的操作を行うクライアントプログラム(マスタ)を実行する計算機20(以下、マスタ計算機20と称す)、及び、解候補の評価を行うクライアントプログラム(ワーカ)を備える携帯電話30からなる。他の実施形態としてマスタをサーバ計算機10上で動作させることや、ワーカをパーソナルコンピュータやPDA等の携帯情報端末上で動作させることも可能である。
【0028】
携帯電話30は、Java(登録商標)Spacesに直接アクセスすることができないため、本方式では、サーバ計算機10上のサーブレットを介して携帯電話30とJava(登録商標)Spacesの通信を行う。すなわち、サーブレットと携帯電話30間はHTTP通信によってオブジェクトの送受信を行う。
【0029】
Java(登録商標)Spacesはエントリと呼ばれる型付けされたオブジェクトを共有する。マスタ計算機20は処理全体の制御を行い、仕事を分割してそれを内容に持つ仕事エントリをオブジェクト共有空間に書き込む。各携帯電話30はオブジェクト共有空間を監視し、仕事エントリがマスタ計算機20により書き込まれたならば、そのエントリを取得する。携帯電話30は、取得したエントリ内の計算を実行し、計算結果を結果エントリとしてオブジェクト共有空間に書き戻す。マスタ計算機30はオブジェクト共有空間に書き戻された全ての結果エントリを回収し、最終的な計算結果を出力する。
【0030】
本実施形態では、上記の処理方式に基づいて、GAによる解候補の評価処理を各携帯電話30のワーカに実行させる。本方式の処理手順を図6に示す
ステップS601:マスタ計算機20において、ランダムに個体を生成し、初期集団とする。
ステップS602~S605:各携帯電話30において、各携帯電話30上のプライバシを用いて各個体を評価する。
ステップS606:マスタ計算機20において、通常のGAと同様に、選択、交叉、突然変異などの遺伝的操作を行い、新しい個体群を作成する。
【0031】
ステップS602からS605の処理を1世代とし、閾値以上の適応度を持つ解を発見するか、一定世代数TGの間適応度が向上しない場合に探索を終了する。得られた解は、オブジェクト共有空間を介して各携帯電話30に送信する。
【0032】
本方式では、携帯電話30上のワーカが染色体の評価を行うが、マスタ計算機20に、既に一度評価を行った染色体の適応度を記憶させることで、通信コストの削減を図る。マスタ計算機20が保持する染色体の適応度の記憶領域をキャッシュと呼ぶ。キャッシュへのデータの読み書きは、ハッシュ法を用いて高速に行う。
【0033】
本方式における、解候補評価の手順を以下に示す。
ステップS602:集団内の各個体(染色体)に対し、キャッシュ内に登録されているかを確認する。適応度が登録されていない全ての個体を1つの仕事エントリに格納し、オブジェクト共有空間に書き込む。キャッシュ内に登録されている個体は、キャッシュ内に登録されている適応度を評価結果として用いる。
【0034】
ステップS603:各ワーカは、オブジェクト共有空間を監視し、個体群の遺伝子情報が書き込まれた場合には、その情報をワーカ内に取り込む。このとき、通常の単一集団型分散GAでは、ワーカに仕事エントリを取り込んだ時点でオブジェクト共有空間からタスクを消去するが、本方式では、全てのワーカが同じ個体を取り込む必要があるため、オブジェクト共有空間上に残しておく。ワーカは、携帯電話30内に保持されたプライバシを用いて取り込んだ個体群を評価し、その結果を結果エントリとしてオブジェクト共有空間に書き戻す。
【0035】
ステップS604:マスタは、ワーカから書き込まれた仕事エントリをオブジェクト共有空間から回収し、各ワーカによる適応度を平均することで各個体の適応度を得る。全てのワーカからの仕事エントリを回収した時点で、仕事エントリをオブジェクト共有空間から削除する。全ての個体とその評価結果をキャッシュに登録する。
【0036】
なお、ワーカとJava(登録商標)Spaces間での通信、またはワーカが動作している携帯電話30で何らかの問題が発生し、結果エントリが一定の時間を越えてもJava(登録商標)Spacesに書き戻されない場合、マスタ側は得られた結果エントリのみを用いて染色体の評価を行う。
【0037】
本実施形態において、プライバシは、専用のインタフェースを通じてユーザが入力を行う。これは、EZアプリの開発用ライブラリKDDI-Pや、iアプリの開発用ライブラリDoJa3.0以降など、携帯電話30内のプライバシを参照可能なJava(登録商標)ライブラリの利用が、携帯電話事業者に認定された企業などに限られるためである。本方式においても上記のライブラリを利用することで、電話やEメールの送受信履歴、電話帳、ブックマーク、スケジュール、搭載されたカメラで撮影した画像情報などをもとに解候補の評価を行える。
【0038】
本分散組合せ最適化方式を部屋割問題に適用し、携帯電話エミュレータおよび実際の携帯電話(実機)を用いて実験を行った。まず、キャッシュの有無、エミュレータと実機の性能差を比較し、次に、世代数と個体数の関係、問題の規模と計算時間の関係、および嗜好情報送信の有無によるユーザの満足度の変化について実験を行った。
【0039】
なお、本実験で用いたGAでは、選択方法としてルーレット戦略を、交叉方法としてPartially Mapped Crossoverを、突然変異方法として2点交換を用いることとした。また、エリート保存戦略を用い、ジェネレーションギャップを1.0、交叉率、突然変異率は"井庭:"遺伝的アルゴリズム",医学出版(2002)"および予備実験をもとにそれぞれ、95%、10%とした。TG=25世代の間、最良解の適応度が変化しない場合、または、適応度1.0の最適解が発見できた場合に、探索を終了するものとした。
【0040】
サーバ計算機10およびマスタ計算機20は同一計算機(CPU:2.53GHz、メモリ:512MByte)上で動作させるものとした。エミュレータを用いる場合は、1台の計算機あたり5台のエミュレータを起動し、サーバ計算機10とは100MbpsのLANによって接続した。実機を用いる場合は、表1に示す携帯電話30を使用し、インターネットおよび携帯電話業者のネットワークによって通信を行うものとした。
【0041】
【表1】
JP0004934800B2_000003t.gif

【0042】
解候補評価におけるキャッシュの効果を検証するために、キャッシュの有無による性能変化を調べた。表2に示す問題P1を実機を用いて解き、キャッシュの有無の場合についてそれぞれ5回、実験を行った。世代数は400、個体数は50とした。
【0043】
【表2】
JP0004934800B2_000004t.gif

【0044】
実験結果を表3に示す。最適解発見率は5回の試行において適応度1.0の解を発見した割合を、平均適応度は5回の試行それぞれにおいて最も適応度が高い解(最良解)の平均適応度を、平均世代数は最良解を発見した世代数の平均を表す。遺伝的操作の処理時間は、図6におけるステップS601及びS606の処理時間の合計を表し、解候補評価の処理時間は、図6におけるステップS602からステップS605の処理時間の合計を表す。括弧内の数値は信頼度95%の信頼区間を表す。表3より、最適解発見率、平均適応度、平均世代数などの探索性能は、キャッシュの有無による影響が少なく、キャッシュを利用することにより解候補評価の処理時間を短縮できていることがわかる。なお、本実験における平均キャッシュヒット率は50%であった。以下に説明する全ての実験では、キャッシュを用いるものとする。
【0045】
【表3】
JP0004934800B2_000005t.gif

【0046】
問題P1を、実機およびエミュレータを用いて解き、処理時間の比較を行った。実機を用いる場合は、表1に示すfoma5台を利用した。実機およびエミュレータでそれぞれ5回の実験を行った結果を表4に示す。ワーカの処理時間は、各ワーカにおける通信時間を含まない総処理時間の平均を表す。表4より、得られた解の適応度や世代数に大きな差はないものの、実機を用いる場合は携帯電話事業者のネットワークを利用するため、時刻による通信状態の変動が激しく、処理時間が安定しないが、エミュレータを用いた場合の10倍程度の時間を要することがわかる。ワーカにおける総処理時間は、エミュレータが実機よりも10倍程度高速であるが、解候補評価の処理時間内と比較してごく短時間であるため、ワーカとエミュレータの処理能力の差よりも、ワーカとエミュレータの通信速度の差が全体の処理時間に大きく影響することがわかる。
【0047】
【表4】
JP0004934800B2_000006t.gif

【0048】
GAでは、世代数と個体数との積が解候補の評価を行った回数(探索コスト)である。ここでは、世代数と個体数との積を一定に保つよう、(世代数、個体数)を(20,(部屋割り対象人数)×20)、(40,(部屋割り対象人数)×10)、(50,(部屋割り対象人数)×8)、(100,(部屋割り対象人数)×4)と変化させて、各設定において10回ずつ実験を行い、最適解の発見率、発見した最良個体の平均適応度、最適解を発見するまでの平均コストおよび平均処理時間を調べた。対象問題として、最適解の適応度が既知(100)のP1、P2およびP4を用いた。安定した通信環境におけるデータを取得するため、エミュレータを用いて実験を行った。表5に実験結果を示す。処理時間は遺伝的操作および解探索評価の双方を含む全体の処理時間を示す。表5より個体数を(部屋割り対象人数)×10に設定することで、高速に最適解を発見できることがわかる。
【0049】
【表5】
JP0004934800B2_000007t.gif

【0050】
問題サイズと処理時間の関係を調べるため、問題P1からP4を用いて実験を行った。安定した通信環境における実験データを取得するため、エミュレータを用いて実験を行った。世代数、個体数はそれぞれ100、100とし、各問題を10回ずつ解くものとした。表6に結果を示す。表6より、問題サイズが増加するにつれて、世代数および処理時間が増加することがわかる。
【0051】
【表6】
JP0004934800B2_000008t.gif

【0052】
プライバシを携帯電話30上に保持することの、ユーザへの心理への影響を評価するため、ユーザに「入力された嗜好情報はマスタ計算機に送信され、誰かに参照される可能性がある」と通知した場合(嗜好情報送信)と、「嗜好情報は携帯電話内に保持され、誰にも参照されない」と通知した場合(嗜好情報保護)に、入力された嗜好情報の差および得られた解に対する主観的な満足度を比較した。10台の実機を用いて10人のメンバが嗜好情報の入力を行った。世代数、個体数はそれぞれ200、50とした。
【0053】
表7に結果を示す。嗜好情報の送信および保護の場合それぞれについて、各メンバによって入力された好悪度の分散を計算した結果、嗜好情報保護の場合の方が偏差が大きく、各メンバがより率直に好悪度を入力したことがわかる。また、最良解適応度は大差ないものの、主観的な満足度は、嗜好情報保護の場合が高いことがわかる。よって、嗜好情報を携帯電話30内に保持することによって、ユーザの率直な嗜好の入力を促し、満足度の高い解を得られたことがわかる。一方、探索コストおよび処理時間については、嗜好情報保護の場合が大きくなっている。これは、各ユーザが嗜好情報をより率直に入力した結果、探索空間の地形がより複雑化し、探索に時間がかかるようになったものと考える。
【0054】
【表7】
JP0004934800B2_000009t.gif

【0055】
以上のように、本実施形態によれば、携帯電話を計算資源として分散問題解決に参加させることができるとともに、携帯電話内の個人情報を安全に用いて意志決定支援を行うことが可能となる。従って、ユーザは安心して嗜好情報を入力することができ、満足度の高い解を得ることができる。このように、携帯電話を用いた分散並列環境の普及を促進することにより、携帯電話を用いた社会貢献実現の一助となり得る。
【0056】
本システムの応用例として、個人の嗜好に基づく部屋割問題に適用した。実験により、個人情報を携帯電話内に保持したままで、全員の嗜好を満たす解を発見することができることを確認した。特に、嗜好をマスタに転送するとユーザに伝えた場合に比べ、プライバシを携帯電話内に保持すると伝えた場合の方が、ユーザの満足度の高い解を得られた。また、問題規模と通信量、計算時間の関係を明らかにし、15人程度の部屋割問題であれば15分程度で解を発見できることを確認した。
【0057】
また、本実施形態に係るシステムは、プライバシを安全に用いた分散組合せ最適化システムであるが、本実施形態において構築される分散並列環境は、基本的に汎用であること、インターネットおよび携帯電話事業者のネットワークを介して通信を行うこと、および、ワーカの動的な参加、離脱を容易に行えることから、 HYPERLINK "mailto:UDAgentやfightAIDS@homeなどのような余剰計算資源提供型分散並列プロジェクトの実行環境に適している" UDAgentやfightAIDS@homeなどのような余剰計算資源提供型分散並列プロジェクトの実行環境に適している。
【0058】
さらに、タブー探索におけるタブーリストや、免疫アルゴリズムにおける記憶細胞のように、探索における集中化と多様化の制御をキャッシュに反映させることで、より少ない通信コストで解探索が行えるようになる。
【0059】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ(またはCPUやMPU)が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。
【0060】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、プログラムコード自体及びそのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【0061】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、CD-ROM、CD-R、磁気テープ、不揮発性のメモリカード、ROM等を用いることができる。
【0062】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているOS(基本システム或いはオペレーティングシステム)などが実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【0063】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるCPU等が実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【0064】
【図1】島モデル型分散GAを概念的に示す図である。
【図2】単一集団型分散GAを概念的に示す図である。
【図3】部屋割問題における染色体表現を示す図である。
【図4】部屋割問題における嗜好情報を示す図である。
【図5】本発明の実施形態に係る分散組合せ最適化システムの構成を示す図である。
【図6】本発明の実施形態に係る分散組合せ最適化システムの処理手順を示す図である。
【符号の説明】
【0065】
10:サーバ計算機
20:マスタ計算機
30:携帯電話
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5