(57)【要約】【課題】  例えば携帯電話に保持されるプライバシや嗜好情報等を保持したまま、それらを利用した分散組合せ最適化を可能とする。【解決手段】  マスタ計算機２０は、複数の解候補である個体群を生成する解候補生成手段と、前記解候補生成手段により生成された個体群を送信する送信手段と、前記送信手段により送信された各個体について一又は複数の携帯電話３０が適応度を評価した結果を回収する回収手段と、前記回収手段により回収された前記各携帯電話３０による個体群の適応度に基づいて、解を探索する解探索手段とを有する。【選択図】  図５
2006277137.tif 000002
【特許請求の範囲】
【請求項１】
複数の解候補である個体群を生成する解候補生成手段と、
前記解候補生成手段により生成された個体群を送信する送信手段と、
前記送信手段により送信された各個体について一又は複数の第１の外部装置が適応度を評価した結果を回収する回収手段と、
前記回収手段により回収された前記各第１の外部装置による個体群の適応度に基づいて、解を探索する解探索手段とを有することを特徴とする解探索装置。
【請求項２】
前記回収手段により回収された個体の適応度を記憶する記憶手段を更に有し、
前記送信手段は、前記記憶手段に適応度が記憶される個体以外の個体を送信することを特徴とする請求項１に記載の解探索装置。
【請求項３】
前記送信手段は、個体群を保持する第２の外部装置に対して個体群を送信し、前記第１の外部装置は、前記第２の外部装置から個体群を取得し、各個体の適応度を評価することを特徴とする請求項１又は２に記載の解探索装置。
【請求項４】
前記解探索手段は、解が複数の値の組合せから構成される組合せ最適化問題を解くことにより解を求めることを特徴とする請求項１乃至３の何れか１項に記載の解探索装置。
【請求項５】
複数の解候補である個体群を取得する取得手段と、
前記取得手段により取得された各個体の適応度を、当該適応度評価装置内に保持する情報に基づいて評価する評価手段と、
前記評価手段により評価された各個体の適応度を送信する送信手段とを有することを特徴とする適応度評価装置。
【請求項６】
前記取得手段は、第１の外部装置によって生成される個体群を保持する第２の外部装置から当該個体群を取得し、前記送信手段は、前記評価手段により評価された各個体の適応度を前記第２の外部装置に対して送信し、前記第１の計算機は、当該適応度評価装置による各個体の適応度を前記第２の外部装置から取得し、取得した各個体の適応度に基づいて解を探索することを特徴とする請求項５に記載の適応度評価装置。
【請求項７】
当該適応度評価装置内に保持される情報は、電話及びＥメールのうちの少なくとも何れか一つ、電話帳情報、ブックマーク情報、スケジュール情報、嗜好情報、並びに、画像情報のうちの少なくとも何れか一つを含むことを特徴とする請求項５又は６に記載の適応度評価装置。
【請求項８】
複数の解候補から解を探索する解探索装置と、解候補である個体の適応度を評価する適応度評価装置とを有する最適化システムであって、
前記解探索装置は、
複数の解候補である個体群を生成する解候補生成手段と、
前記解候補生成手段により生成された個体群を送信する送信手段と、
前記送信手段により送信された各個体について一又は複数の前記適応度評価装置が適応度を評価した結果を回収する回収手段と、
前記回収手段により回収された前記各適応度評価装置による個体群の適応度に基づいて、解を探索する解探索手段とを有することを特徴とする最適化システム。
【請求項９】
複数の解候補である個体群を生成する解候補生成ステップと、
前記解候補生成手段により生成された個体群を送信する送信ステップと、
前記送信ステップにより送信された各個体について一又は複数の第１の外部装置が適応度を評価した結果を回収する回収ステップと、
前記回収ステップにより回収された前記各第１の外部装置による個体群の適応度に基づいて、解を探索する解探索ステップとを含むことを特徴とする解探索方法。
【請求項１０】
複数の解候補である個体群を取得する取得ステップと、
前記取得ステップにより取得された各個体の適応度を、当該適応度評価装置内に保持する情報に基づいて評価する評価ステップと、
前記評価ステップにより評価された各個体の適応度を送信する送信ステップとを含むことを特徴とする適応度評価方法。
【請求項１１】
請求項９に記載の解探索方法をコンピュータに実行させるためのプログラム。
【請求項１２】
請求項１０に記載の適応度評価方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば携帯電話等の計算資源を利用した分散組合せ最適化方式に好適な技術に関するものである。
【背景技術】
【０００２】
パーソナルコンピュータやワークステーションなどの通常の計算機と比較すると、携帯電話は演算能力や通信速度こそ劣るものの、無線通信能力が高く、個人に最も身近で私的な計算資源とみなすことができる。携帯電話の普及台数と端末の性能向上速度を考慮すると、携帯電話の計算資源としての潜在的な価値は高く、複数の携帯電話を用いて計算を行うことで、大規模な問題解決の実現が期待される。
【０００３】
近年、白血病治療法検証プログラムUD Agentや、ＨＩＶウィルスの化合物テストを行うFight HYPERLINK "mailto:AIDS@homeなど" AIDS@homeなど、一般の計算機ユーザの余剰計算資源の提供をもとに、インターネットを介して大規模な問題解決を行うプロジェクトが行われている。待機状態の携帯電話上で上記のプログラムを実行できれば、膨大な数の携帯電話を社会貢献に用いることができると考えられる。しかし、第３世代携帯電話は、演算プロセッサの高速化やデータ通信速度の改善、データ通信料の定額サービスが開始されるなど、携帯電話の性能の拡充が進んではいるが、バッテリ消費などの観点から、携帯電話ユーザにとって気軽に計算資源を提供できる状況には至っていない。
【０００４】
近年の携帯電話は、電子メール送受信、Ｗｅｂページ閲覧などの情報端末としての機能が進化するとともに、個人の嗜好や私的な情報をより多く含むようになった。以下では、このような情報をプライバシと称す。プライバシを利用することにより、個々のユーザに応じたきめ細やかなサービスの提供や、ユーザの満足度の高い意志決定支援などが期待される。
【０００５】
しかし、プライバシは基本的に、他人に知られたくない情報を含むため、利用する際には情報の漏洩に注意が必要となる。このため近年、モバイルエージェント技術によりプライバシを安全に利用する研究が行われている（例えば、非特許文献１参照）。モバイルエージェントに基づく方式は、会議日程調整にように、求める解が単一または２、３個の値の組合せであれば、移動と交渉を繰り返しながら、実用的な時間内に解を得ることができる。
【０００６】
【非特許文献１】伊藤，新谷："モバイルエージェント間の多重交渉に基づくグループ代替案選択支援システムについて"，情処論，Ｖｏｌ．３９，Ｎｏ１２，ｐｐ．３１６５−３１７６（１９９８）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、求める解が多数の値の組合せからなり、各携帯電話上のプライバシを利用しながら解候補を評価しつつ値の最適な組合せを求める場合、解を構成する変数や値の総数が増加するにつれ代替案の総数が指数関数的に増加し、エージェントの移動回数および交渉回数が増加してしまう。各個人のスケジュールを考慮した時間割編成や、メール送受信、通話記録などの人間関係を表す情報を用いた座席配置など、携帯電話上のプライバシや嗜好情報をもとに組合せ最適化を行うことで、メンバが納得できる合意の形成が期待できる問題は多数存在する。このため、携帯電話上の情報を安全に利用し、実用的な時間内で組合せ最適化を行う方式の実現が望まれている。
【０００８】
そこで、本発明の目的は、例えば携帯電話に保持されるプライバシや嗜好情報等を保持したまま、それらを利用した分散組合せ最適化を可能とすることにある。
【課題を解決するための手段】
【０００９】
本発明の解探索装置は、複数の解候補である個体群を生成する解候補生成手段と、前記解候補生成手段により生成された個体群を送信する送信手段と、前記送信手段により送信された各個体について一又は複数の第１の外部装置が適応度を評価した結果を回収する回収手段と、前記回収手段により回収された前記各第１の外部装置による個体群の適応度に基づいて、解を探索する解探索手段とを有することを特徴とする。
本発明の適応度評価装置は、複数の解候補である個体群を取得する取得手段と、前記取得手段により取得された各個体の適応度を、当該適応度評価装置内に保持する情報に基づいて評価する評価手段と、前記評価手段により評価された各個体の適応度を送信する送信手段とを有することを特徴とする。
本発明の最適化システムは、複数の解候補から解を探索する解探索装置と、解候補である個体の適応度を評価する適応度評価装置とを有する最適化システムであって、前記解探索装置は、複数の解候補である個体群を生成する解候補生成手段と、前記解候補生成手段により生成された個体群を送信する送信手段と、前記送信手段により送信された各個体について一又は複数の前記適応度評価装置が適応度を評価した結果を回収する回収手段と、前記回収手段により回収された前記各適応度評価装置による個体群の適応度に基づいて、解を探索する解探索手段とを有することを特徴とする。
本発明の解探索方法は、複数の解候補である個体群を生成する解候補生成ステップと、前記解候補生成手段により生成された個体群を送信する送信ステップと、前記送信ステップにより送信された各個体について一又は複数の第１の外部装置が適応度を評価した結果を回収する回収ステップと、前記回収ステップにより回収された前記各第１の外部装置による個体群の適応度に基づいて、解を探索する解探索ステップとを含むことを特徴とする。
本発明の適応度評価方法は、複数の解候補である個体群を取得する取得ステップと、前記取得ステップにより取得された各個体の適応度を、当該適応度評価装置内に保持する情報に基づいて評価する評価ステップと、前記評価ステップにより評価された各個体の適応度を送信する送信ステップとを含むことを特徴とする。
本発明のプログラムの第１の態様は、前記解探索方法をコンピュータに実行させることを特徴とする。
本発明のプログラムの第２の態様は、前記適応度評価方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、例えば携帯電話に保持されるプライバシや嗜好情報等を保持したまま、それらを利用した分散組合せ最適化を行うことが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１２】
本実施形態では、大規模な組合せ最適化問題で有効な遺伝的アルゴリズム（Genetic Algorithm:ＧＡ）を、計算機および複数の携帯電話上で分散実行するものである。通常の計算機上で交叉、突然変移などの解候補生成の処理を行い、携帯電話上で解候補の評価を行うことにより、携帯電話上のプライバシを解候補評価に安全に利用しつつ、携帯電話上での計算量を最小限に抑えることができる。
【００１３】
次に、分散ＧＡの２つのモデル、および携帯電話を用いた従来の分散ＧＡについて述べる。
−複数集団型（島モデル）−
図１に示すように、集団をいくつかの部分集団に分割し、それぞれの部分集団に対して独立に遺伝的操作を適用する分散ＧＡを島モデル型分散ＧＡ（Island Genetic Algorithm:ＩＧＡ）と呼ぶ。ＩＧＡは並列性が高いだけでなく、部分集団が独立に進化するので、集団全体としての多様性を高く保つことができる利点がある。
−単一集団型−
ＧＡを最適化計算に応用する場合、各個体の適応度は他の個体の適応度とは独立に計算可能である。この点に注目して、図２に示すような適応度関数の評価を並列処理することにより高速化を図る分散並列ＧＡが提案されている。選択、交叉、突然変移などの遺伝的操作を１つのマスタプロセッサに集中させるため、画像フィルタの自動設計など適応度評価に時間を要する計算に適している。
−携帯電話を用いた島モデル型分散ＧＡ−
柴山、高田、庄野、城："ｉアプリを用いた分散ＧＡの実装"、第９回情報処理学会ＭＰＳシンポジウム、ｐｐ．２１５−２５８（２００３）では、ＩＧＡを複数の携帯電話で実行する方式が提案されている。これはＮＴＴドコモのJava（登録商標）仮想マシン搭載携帯電話上で、ｉアプリとして並列計算プログラムを動作させるものであり、ナップザック問題を複数の携帯電話を用いて解くものである。携帯電話間での直接通信は実現が困難であるため、Ｗｅｂサーバを介して島間での移住処理を行う。この文献では、実際の携帯電話を用いて実験を行っており、組合せ最適化の計算を携帯電話で行えることを示している。しかし、パーソナルコンピュータやワークステーションではなく、携帯電話に並列計算を行わせる利点が不明瞭であり、複数の携帯電話を用いてＩＧＡを実行する必然性が低い。
【００１４】
以下では、本発明の実施形態として、携帯電話上のプライバシを用いて組合せ最適化を行う方式を示す。
【００１５】
本方式では、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（登録商標）が動作可能な計算資源であれば、分散並列処理に容易に参加させることが可能となり、様々なＯＳを搭載した計算機、携帯情報端末、および携帯電話を利用することができる。また、インターネットなどの汎用のネットワークを利用できる。計算資源の動的な参加、離脱にも容易に対応できるなどの特徴を持つため、計算機だけでなく携帯電話を主たる計算資源とする本方式に適している。
【００１６】
Java（登録商標）Spacesを用いた分散並列環境において、容易に分散並列処理を実現できる環境やＡＰＩを提供するJSGrid、および、キーワードを付記するだけで、通常のスタンドアロン型のプログラムを分散並列プログラムへと自動で変換する言語Espaceが提案されている。Java（登録商標）Spacesを利用することにより、将来的にJSGridおよびEspaceの利用が可能となり、分散並列プログラムの開発コストを抑えることが可能となる。
【００１７】
また、本方式では、Java（登録商標）Spacesを介して解候補を送受信することにより、携帯電話上で、個人情報に基づいた解候補の評価を行う。よって、各個人の嗜好や条件を他人の携帯電話、計算機に送信せずに、全員の嗜好、条件を満たす解を生成することが可能である。個人情報や嗜好が他の計算機に送信されないことは、携帯電話のユーザに安心感を与える。このため、より率直な嗜好の入力を促すことができ、結果として満足度の高い解を得ることができる。
【００１８】
本方式が対象とする問題は、各個人の嗜好を充足する離散値の集合を求める組合せ最適化問題であり、ユーザ数が増加するとその探索空間は指数関数的に増加する。このため、大規模な探索空間内において効率的に最適解を発見できる探索アルゴリズムが必要となり、本実施形態では遺伝的アルゴリズムを採用する。
【００１９】
本実施形態で用いる分散並列環境では、インターネットおよび携帯電話事業者のネットワークを利用するため通信コストが大きい。またJava（登録商標）Spacesを用いた分散並列環境では、小さなデータを頻繁に送受信することよりも大きなデータをより低い頻度で送受信することが望ましい。よって、解候補の生成と評価を頻繁に行う必要がある山登り法などの単点探索よりも、集団内の全解候補を一度に生成、評価できる多点探索アルゴリズムである遺伝的アルゴリズムが適している。
【００２０】
なお、ＩＧＡを基本とし、従来の負荷分散や初期収束回避を目的とした、柴山、高田、庄野、城："ｉアプリを用いた分散ＧＡの実装"、第９回情報処理学会ＭＰＳシンポジウム、ｐｐ．２１５−２５８（２００３）に提案される分散ＧＡとは異なり、本実施形態で用いるＧＡは、上述した単一集団型を基本とする。通常の単一集団型分散ＧＡは解候補評価の負荷分散を目的とするが、本実施形態で用いるＧＡは、プライバシを用いた解候補の評価を各携帯電話で行う機能分散型のＧＡである。
【００２１】
ここで提案する分散組合せ最適化方式は、基本的に汎用であり、組合せ最適化問題、制約充足問題などに適用することが可能であるが、理解を容易にするために、以下に示す部屋割問題を用いて本方式の説明および評価実験を行う。
【００２２】
部屋割問題は、個々人の嗜好を満足するように、人を部屋へと割り当てる問題である。部屋割問題は、人数が増加すると探索空間のサイズが指数関数的に増加し、全員の嗜好を満たす解を発見することが困難になる。
【００２３】
部屋割問題の解は、図３に示すような一次元の染色体として表現できる。これは、巡回セールスマン問題（Traveling Salesman Problem:ＴＳＰ）と類似の染色体表現であり、部屋割問題においてもＴＳＰにおいて用いられるPartially Mapped Crossover(ＰＭＸ)やサブツアー交換交叉など、致死遺伝子の発生を抑え、ビルディングブロックをなるべく保持する交叉方式を利用することが可能である。
【００２４】
各個人の嗜好は、図４に示すように、それぞれの人と相部屋になりたい度合い（好悪度）の集合から構成される。本実施形態では、Java（登録商標）2 Micro Edition(J2ME)を用いて携帯電話上のプログラムを実装するが、J2ME単体では小数を扱うことができないため、好悪度の最小を０、最大を１００とする。染色体Ｃiの適応度Ｆ（Ｃi）は、以下の式に従って計算する。
【００２５】
【数１】
2006277137.tif 000003
【００２６】
ここで、ｒは部屋の総数を、ＱRjはＲjの定員数を、ｘjkは部屋Ｒjに割り当てられたk番目の人を、Ｐa（ｂ）は人ａの人ｂに対する好悪度を表す。好悪度同様、適応度も０から１００の間の整数値をとる。
【００２７】
本実施形態における分散組合せ最適化方式の構成とJava（登録商標）Spacesを用いた分散並列処理の概念とを図５に示す。本方式は、ＨＴＴＰサーバとJava（登録商標）Spacesサーバとを兼ねた計算機１０（以下、サーバ計算機１０と称す）、遺伝的操作を行うクライアントプログラム（マスタ）を実行する計算機２０（以下、マスタ計算機２０と称す）、及び、解候補の評価を行うクライアントプログラム（ワーカ）を備える携帯電話３０からなる。他の実施形態としてマスタをサーバ計算機１０上で動作させることや、ワーカをパーソナルコンピュータやＰＤＡ等の携帯情報端末上で動作させることも可能である。
【００２８】
携帯電話３０は、Java（登録商標）Spacesに直接アクセスすることができないため、本方式では、サーバ計算機１０上のサーブレットを介して携帯電話３０とJava（登録商標）Spacesの通信を行う。すなわち、サーブレットと携帯電話３０間はＨＴＴＰ通信によってオブジェクトの送受信を行う。
【００２９】
Java（登録商標）Spacesはエントリと呼ばれる型付けされたオブジェクトを共有する。マスタ計算機２０は処理全体の制御を行い、仕事を分割してそれを内容に持つ仕事エントリをオブジェクト共有空間に書き込む。各携帯電話３０はオブジェクト共有空間を監視し、仕事エントリがマスタ計算機２０により書き込まれたならば、そのエントリを取得する。携帯電話３０は、取得したエントリ内の計算を実行し、計算結果を結果エントリとしてオブジェクト共有空間に書き戻す。マスタ計算機３０はオブジェクト共有空間に書き戻された全ての結果エントリを回収し、最終的な計算結果を出力する。
【００３０】
本実施形態では、上記の処理方式に基づいて、ＧＡによる解候補の評価処理を各携帯電話３０のワーカに実行させる。本方式の処理手順を図６に示す
ステップＳ６０１：マスタ計算機２０において、ランダムに個体を生成し、初期集団とする。
ステップＳ６０２〜Ｓ６０５：各携帯電話３０において、各携帯電話３０上のプライバシを用いて各個体を評価する。
ステップＳ６０６：マスタ計算機２０において、通常のＧＡと同様に、選択、交叉、突然変異などの遺伝的操作を行い、新しい個体群を作成する。
【００３１】
ステップＳ６０２からＳ６０５の処理を１世代とし、閾値以上の適応度を持つ解を発見するか、一定世代数ＴGの間適応度が向上しない場合に探索を終了する。得られた解は、オブジェクト共有空間を介して各携帯電話３０に送信する。
【００３２】
本方式では、携帯電話３０上のワーカが染色体の評価を行うが、マスタ計算機２０に、既に一度評価を行った染色体の適応度を記憶させることで、通信コストの削減を図る。マスタ計算機２０が保持する染色体の適応度の記憶領域をキャッシュと呼ぶ。キャッシュへのデータの読み書きは、ハッシュ法を用いて高速に行う。
【００３３】
本方式における、解候補評価の手順を以下に示す。
ステップＳ６０２：集団内の各個体（染色体）に対し、キャッシュ内に登録されているかを確認する。適応度が登録されていない全ての個体を１つの仕事エントリに格納し、オブジェクト共有空間に書き込む。キャッシュ内に登録されている個体は、キャッシュ内に登録されている適応度を評価結果として用いる。
【００３４】
ステップＳ６０３：各ワーカは、オブジェクト共有空間を監視し、個体群の遺伝子情報が書き込まれた場合には、その情報をワーカ内に取り込む。このとき、通常の単一集団型分散ＧＡでは、ワーカに仕事エントリを取り込んだ時点でオブジェクト共有空間からタスクを消去するが、本方式では、全てのワーカが同じ個体を取り込む必要があるため、オブジェクト共有空間上に残しておく。ワーカは、携帯電話３０内に保持されたプライバシを用いて取り込んだ個体群を評価し、その結果を結果エントリとしてオブジェクト共有空間に書き戻す。
【００３５】
ステップＳ６０４：マスタは、ワーカから書き込まれた仕事エントリをオブジェクト共有空間から回収し、各ワーカによる適応度を平均することで各個体の適応度を得る。全てのワーカからの仕事エントリを回収した時点で、仕事エントリをオブジェクト共有空間から削除する。全ての個体とその評価結果をキャッシュに登録する。
【００３６】
なお、ワーカとJava（登録商標）Spaces間での通信、またはワーカが動作している携帯電話３０で何らかの問題が発生し、結果エントリが一定の時間を越えてもJava（登録商標）Spacesに書き戻されない場合、マスタ側は得られた結果エントリのみを用いて染色体の評価を行う。
【００３７】
本実施形態において、プライバシは、専用のインタフェースを通じてユーザが入力を行う。これは、ＥＺアプリの開発用ライブラリＫＤＤＩ−Ｐや、ｉアプリの開発用ライブラリＤｏＪａ３．０以降など、携帯電話３０内のプライバシを参照可能なＪａｖａ（登録商標）ライブラリの利用が、携帯電話事業者に認定された企業などに限られるためである。本方式においても上記のライブラリを利用することで、電話やＥメールの送受信履歴、電話帳、ブックマーク、スケジュール、搭載されたカメラで撮影した画像情報などをもとに解候補の評価を行える。
【００３８】
本分散組合せ最適化方式を部屋割問題に適用し、携帯電話エミュレータおよび実際の携帯電話（実機）を用いて実験を行った。まず、キャッシュの有無、エミュレータと実機の性能差を比較し、次に、世代数と個体数の関係、問題の規模と計算時間の関係、および嗜好情報送信の有無によるユーザの満足度の変化について実験を行った。
【００３９】
なお、本実験で用いたＧＡでは、選択方法としてルーレット戦略を、交叉方法としてPartially Mapped Crossoverを、突然変異方法として２点交換を用いることとした。また、エリート保存戦略を用い、ジェネレーションギャップを１．０、交叉率、突然変異率は"井庭："遺伝的アルゴリズム"，医学出版（２００２）"および予備実験をもとにそれぞれ、９５％、１０％とした。ＴG＝２５世代の間、最良解の適応度が変化しない場合、または、適応度１．０の最適解が発見できた場合に、探索を終了するものとした。
【００４０】
サーバ計算機１０およびマスタ計算機２０は同一計算機（ＣＰＵ：２．５３ＧＨｚ、メモリ：５１２ＭＢｙｔｅ）上で動作させるものとした。エミュレータを用いる場合は、１台の計算機あたり５台のエミュレータを起動し、サーバ計算機１０とは１００ＭｂｐｓのＬＡＮによって接続した。実機を用いる場合は、表１に示す携帯電話３０を使用し、インターネットおよび携帯電話業者のネットワークによって通信を行うものとした。
【００４１】
【表１】
2006277137.tif 000004
【００４２】
解候補評価におけるキャッシュの効果を検証するために、キャッシュの有無による性能変化を調べた。表２に示す問題Ｐ1を実機を用いて解き、キャッシュの有無の場合についてそれぞれ５回、実験を行った。世代数は４００、個体数は５０とした。
【００４３】
【表２】
2006277137.tif 000005
【００４４】
実験結果を表３に示す。最適解発見率は５回の試行において適応度１．０の解を発見した割合を、平均適応度は５回の試行それぞれにおいて最も適応度が高い解（最良解）の平均適応度を、平均世代数は最良解を発見した世代数の平均を表す。遺伝的操作の処理時間は、図６におけるステップＳ６０１及びＳ６０６の処理時間の合計を表し、解候補評価の処理時間は、図６におけるステップＳ６０２からステップＳ６０５の処理時間の合計を表す。括弧内の数値は信頼度９５％の信頼区間を表す。表３より、最適解発見率、平均適応度、平均世代数などの探索性能は、キャッシュの有無による影響が少なく、キャッシュを利用することにより解候補評価の処理時間を短縮できていることがわかる。なお、本実験における平均キャッシュヒット率は５０％であった。以下に説明する全ての実験では、キャッシュを用いるものとする。
【００４５】
【表３】
2006277137.tif 000006
【００４６】
問題Ｐ1を、実機およびエミュレータを用いて解き、処理時間の比較を行った。実機を用いる場合は、表１に示すｆｏｍａ５台を利用した。実機およびエミュレータでそれぞれ５回の実験を行った結果を表４に示す。ワーカの処理時間は、各ワーカにおける通信時間を含まない総処理時間の平均を表す。表４より、得られた解の適応度や世代数に大きな差はないものの、実機を用いる場合は携帯電話事業者のネットワークを利用するため、時刻による通信状態の変動が激しく、処理時間が安定しないが、エミュレータを用いた場合の１０倍程度の時間を要することがわかる。ワーカにおける総処理時間は、エミュレータが実機よりも１０倍程度高速であるが、解候補評価の処理時間内と比較してごく短時間であるため、ワーカとエミュレータの処理能力の差よりも、ワーカとエミュレータの通信速度の差が全体の処理時間に大きく影響することがわかる。
【００４７】
【表４】
2006277137.tif 000007
【００４８】
ＧＡでは、世代数と個体数との積が解候補の評価を行った回数（探索コスト）である。ここでは、世代数と個体数との積を一定に保つよう、（世代数、個体数）を（２０，（部屋割り対象人数）×２０）、（４０，（部屋割り対象人数）×１０）、（５０，（部屋割り対象人数）×８）、（１００，（部屋割り対象人数）×４）と変化させて、各設定において１０回ずつ実験を行い、最適解の発見率、発見した最良個体の平均適応度、最適解を発見するまでの平均コストおよび平均処理時間を調べた。対象問題として、最適解の適応度が既知（１００）のＰ1、Ｐ2およびＰ4を用いた。安定した通信環境におけるデータを取得するため、エミュレータを用いて実験を行った。表５に実験結果を示す。処理時間は遺伝的操作および解探索評価の双方を含む全体の処理時間を示す。表５より個体数を（部屋割り対象人数）×１０に設定することで、高速に最適解を発見できることがわかる。
【００４９】
【表５】
2006277137.tif 000008
【００５０】
問題サイズと処理時間の関係を調べるため、問題Ｐ1からＰ4を用いて実験を行った。安定した通信環境における実験データを取得するため、エミュレータを用いて実験を行った。世代数、個体数はそれぞれ１００、１００とし、各問題を１０回ずつ解くものとした。表６に結果を示す。表６より、問題サイズが増加するにつれて、世代数および処理時間が増加することがわかる。
【００５１】
【表６】
2006277137.tif 000009
【００５２】
プライバシを携帯電話３０上に保持することの、ユーザへの心理への影響を評価するため、ユーザに「入力された嗜好情報はマスタ計算機に送信され、誰かに参照される可能性がある」と通知した場合（嗜好情報送信）と、「嗜好情報は携帯電話内に保持され、誰にも参照されない」と通知した場合（嗜好情報保護）に、入力された嗜好情報の差および得られた解に対する主観的な満足度を比較した。１０台の実機を用いて１０人のメンバが嗜好情報の入力を行った。世代数、個体数はそれぞれ２００、５０とした。
【００５３】
表７に結果を示す。嗜好情報の送信および保護の場合それぞれについて、各メンバによって入力された好悪度の分散を計算した結果、嗜好情報保護の場合の方が偏差が大きく、各メンバがより率直に好悪度を入力したことがわかる。また、最良解適応度は大差ないものの、主観的な満足度は、嗜好情報保護の場合が高いことがわかる。よって、嗜好情報を携帯電話３０内に保持することによって、ユーザの率直な嗜好の入力を促し、満足度の高い解を得られたことがわかる。一方、探索コストおよび処理時間については、嗜好情報保護の場合が大きくなっている。これは、各ユーザが嗜好情報をより率直に入力した結果、探索空間の地形がより複雑化し、探索に時間がかかるようになったものと考える。
【００５４】
【表７】
2006277137.tif 000010
【００５５】
以上のように、本実施形態によれば、携帯電話を計算資源として分散問題解決に参加させることができるとともに、携帯電話内の個人情報を安全に用いて意志決定支援を行うことが可能となる。従って、ユーザは安心して嗜好情報を入力することができ、満足度の高い解を得ることができる。このように、携帯電話を用いた分散並列環境の普及を促進することにより、携帯電話を用いた社会貢献実現の一助となり得る。
【００５６】
本システムの応用例として、個人の嗜好に基づく部屋割問題に適用した。実験により、個人情報を携帯電話内に保持したままで、全員の嗜好を満たす解を発見することができることを確認した。特に、嗜好をマスタに転送するとユーザに伝えた場合に比べ、プライバシを携帯電話内に保持すると伝えた場合の方が、ユーザの満足度の高い解を得られた。また、問題規模と通信量、計算時間の関係を明らかにし、１５人程度の部屋割問題であれば１５分程度で解を発見できることを確認した。
【００５７】
また、本実施形態に係るシステムは、プライバシを安全に用いた分散組合せ最適化システムであるが、本実施形態において構築される分散並列環境は、基本的に汎用であること、インターネットおよび携帯電話事業者のネットワークを介して通信を行うこと、および、ワーカの動的な参加、離脱を容易に行えることから、 HYPERLINK "mailto:UDAgentやfightAIDS@homeなどのような余剰計算資源提供型分散並列プロジェクトの実行環境に適している" UDAgentやfightAIDS@homeなどのような余剰計算資源提供型分散並列プロジェクトの実行環境に適している。
【００５８】
さらに、タブー探索におけるタブーリストや、免疫アルゴリズムにおける記憶細胞のように、探索における集中化と多様化の制御をキャッシュに反映させることで、より少ない通信コストで解探索が行えるようになる。
【００５９】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。
【００６０】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、プログラムコード自体及びそのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００６１】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【００６２】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ(基本システム或いはオペレーティングシステム)などが実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００６３】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部又は全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【００６４】
【図１】島モデル型分散ＧＡを概念的に示す図である。
【図２】単一集団型分散ＧＡを概念的に示す図である。
【図３】部屋割問題における染色体表現を示す図である。
【図４】部屋割問題における嗜好情報を示す図である。
【図５】本発明の実施形態に係る分散組合せ最適化システムの構成を示す図である。
【図６】本発明の実施形態に係る分散組合せ最適化システムの処理手順を示す図である。
【符号の説明】
【００６５】
１０：サーバ計算機
２０：マスタ計算機
３０：携帯電話
【図１】
2006277137.tif 000011
【図２】
2006277137.tif 000012
【図３】
2006277137.tif 000013
【図４】
2006277137.tif 000014
【図５】
2006277137.tif 000015
【図６】
2006277137.tif 000016