著者
黒岩 将 安本 慶一 村田 佳洋 伊藤 実
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.6, no.1, pp.47-56, 2013-03-12

合コン(お見合いパーティ)では,できるだけ多くのカップルを成立させたいという要求が発生する.本論文では,合コン結果から,カップルが成立しやすい男女の属性情報の組(好相性と呼ぶ)を,進化計算を用いて求めることで,理想的な合コンメンバ(合コン参加者名簿)を決定するシステムを提案する.提案システムでは,男女の属性情報の組を進化計算の解集団(初期個体群)としてシステムに持たせ,合コンでのカップル成否を解の評価値(適応度)としてフィードバックしながら,好相性を表現する準最適解集団の獲得を目指す.提案システムの実現には,複数の好相性の同時探索,様々な参加者による多数の合コンの実施が必要である.これらの課題を解決するため,進化計算の新しい選択法,過去の合コン結果の新たな解評価への再利用法を考案した.提案システムを評価するため,カップルになった男女の属性情報を解としてそのまま利用する比較手法を用意し,計算機シミュレーションにより比較を行った.結果,提案手法が,比較手法に比べて,半分の合コン実施回数で,約2倍のカップル成立数を達成できることを確認した.
著者
黒岩 将 安本 慶一 村田 佳洋 伊藤 実
出版者
情報処理学会
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.6, no.1, pp.47-56, 2013-03-12

合コン(お見合いパーティ)では,できるだけ多くのカップルを成立させたいという要求が発生する.本論文では,合コン結果から,カップルが成立しやすい男女の属性情報の組(好相性と呼ぶ)を,進化計算を用いて求めることで,理想的な合コンメンバ(合コン参加者名簿)を決定するシステムを提案する.提案システムでは,男女の属性情報の組を進化計算の解集団(初期個体群)としてシステムに持たせ,合コンでのカップル成否を解の評価値(適応度)としてフィードバックしながら,好相性を表現する準最適解集団の獲得を目指す.提案システムの実現には,複数の好相性の同時探索,様々な参加者による多数の合コンの実施が必要である.これらの課題を解決するため,進化計算の新しい選択法,過去の合コン結果の新たな解評価への再利用法を考案した.提案システムを評価するため,カップルになった男女の属性情報を解としてそのまま利用する比較手法を用意し,計算機シミュレーションにより比較を行った.結果,提案手法が,比較手法に比べて,半分の合コン実施回数で,約2倍のカップル成立数を達成できることを確認した.There is a demand to maximize the number of successful couples in match-making party called Gokon. In this paper, we propose a method to find good affinity patterns between man and woman from resulting matches of Gokon by encoding their attribute information and using evolutionary computation scheme. We also propose a system to assign the best members to each Gokon based on the method. The purpose of the proposed system is to derive good affinity patterns. For this purpose, a specified number of solutions as chromosome of evolutionary computation (EC) are initially prepared in the system. By feeding back the results of Gokon to the solutions as fitness value of EC, semi-optimal solutions are derived. To realize the proposed system, we need simultaneous search of multiple different good affinity patterns and efficient evaluation of solutions through many Gokons with various attribute members. To these challenges, we devise new methods for efficient selection operation and reuse of the past matches to evaluate new solutions. To evaluate the system, we prepared a comparative method which uses attribute information between a man and a woman who made a match as a solution. Through computer simulation, we confirmed that the proposed system achieves twice as many successful couples as the comparative method with about half of evaluation times.
著者
丸山 敦史 柴田 直樹 村田 佳洋 安本 慶一 伊藤 実
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.45, no.12, pp.2678-2687, 2004-12-15
被引用文献数
17

本論文では,観光のためのパーソナルナビゲーションシステム"P-Tour" を提案する.P-Tour は,ユーザが出発地と出発時刻,帰着地と帰着時刻,複数の観光候補地と各地への立ち寄り希望度と時間制約(到着時間帯や滞在時間など)を設定すると,制限時間内で巡回可能かつ最も満足度が高くなるような巡回経路(いくつかの観光地を含む)と各観光地への到着・出発予定時刻を含むスケジュールを算出しユーザに提示する機能を提供する.P-Tour は決定したスケジュールに従い,GPS 機能を備えた携帯端末を介し,ユーザにナビゲーション機能を提供する.提案するナビゲーション機能では,現在地を中心とする地図と次の目的地への経路の表示などの空間的な誘導に加え,各目的地での,滞在可能時間の表示や出発時刻の通知などの,時間的な誘導機能を提供する.遺伝的アルゴリズムを用いて準最適なスケジュールを高速に算出するアルゴリズムを設計・開発し,Java サーブレットとして実装した.PC や携帯端末からウェブインタフェースを介してスケジュールの作成,ナビゲーション機能が利用できる.市販のカーナビゲーションシステム用のデジタル地図を用いた評価実験により,準最適なスケジュールを実用的時間で案内できることなどを確認した.In this paper, we propose a personal navigation system for tourism called P-Tour. In PTour, when a tourist specifies the starting location, the departure time, the returning location, the arrival time and the multiple candidate destinations with relative importance and time restrictions on their arrival and staying time, the nearly best schedule is automatically computed. P-Tour can efficiently navigate the tourist according to the decided schedule through a portable computing device with GPS. In addition to the standard navigation function to guide users to destinations by displaying a graphical map, P-Tour provides temporal guidance for the tourist to follow the schedule. We have developed a route search engine to obtain a semi-optimal solution quickly using techniques of genetic algorithms. The engine has been developed as a Java Servlet and can be used from PCs and portable devices via http protocol. Our experimental results show that our route search engine can compute the nearly best schedule in reasonable time.
著者
黒岩 将 安本 慶一 村田 佳洋 伊藤 実
出版者
一般社団法人情報処理学会
巻号頁・発行日
2013-03-12

合コン(お見合いパーティ)では,できるだけ多くのカップルを成立させたいという要求が発生する.本論文では,合コン結果から,カップルが成立しやすい男女の属性情報の組(好相性と呼ぶ)を,進化計算を用いて求めることで,理想的な合コンメンバ(合コン参加者名簿)を決定するシステムを提案する.提案システムでは,男女の属性情報の組を進化計算の解集団(初期個体群)としてシステムに持たせ,合コンでのカップル成否を解の評価値(適応度)としてフィードバックしながら,好相性を表現する準最適解集団の獲得を目指す.提案システムの実現には,複数の好相性の同時探索,様々な参加者による多数の合コンの実施が必要である.これらの課題を解決するため,進化計算の新しい選択法,過去の合コン結果の新たな解評価への再利用法を考案した.提案システムを評価するため,カップルになった男女の属性情報を解としてそのまま利用する比較手法を用意し,計算機シミュレーションにより比較を行った.結果,提案手法が,比較手法に比べて,半分の合コン実施回数で,約2倍のカップル成立数を達成できることを確認した.
著者
永田 宗伸 村田 佳洋 柴田 直樹 安本 慶一 伊藤 実
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.48, no.6, pp.23-31, 2007-03-15
参考文献数
9
被引用文献数
2

今日の観光において,団体ツアーなどのグループ観光は,個人旅行に比べて費用などの点においての利点を持つ.しかし団体ツアーは,参加メンバの細かな嗜好や制約の違いを反映させることが難しい.本論文では,訪れたい観光地が少しずつ異なる複数のメンバがグループで観光する際に,メンバそれぞれの希望を満たしつつ,希望の合致する部分を共有するようなスケジュールを算出する問題を定義し,それを実用時間で計算する遺伝的アルゴリズム(以下,GA)を用いた近似アルゴリズムを提案する.取り扱う問題においては,メンバの数や巡回候補地の数に応じて,スケジュール中の単独行動とグループ行動の間の分離・合流地点の組合せが爆発的に増える.提案手法におけるGA の解のコーディングでは,分離・合流地点を"参照遺伝子" と呼ばれる遺伝子で表し,解候補の評価値を計算する際に,複数メンバのスケジュールをこの遺伝子を介して結合するという手法を採用した.これにより,広大な解空間を効率良く探索することが可能となり,評価実験を行った結果,メンバ数3~9 程度のグループ観光に対し,高速に準最適な解を得られることを確認した.Group tour is popular in recent years because of its reasonable cost. In group tour, however, members must follow the same schedule, and there is little flexibility to reflect preferences of the members. In this thesis, we propose a GA-based approximation algorithm to find the minimum cost schedule (including routes and stay time at each spot) for a flexible group tour with members who have different preferences. In this problem, the number of combinations of leaving and joining points exponentially increases. In the proposed algorithm, we used the gene called "reference gene". This gene means point where members leave or join in the schedule. With this coding of chromosome, efficient searching in the vast search space is achieved. We implemented and evaluated the proposed algorithm. We confirmed that our algorithm can find efficient schedules within reasonable time for group tours with practical size, 3 to 9 members.
著者
高島 栄一 村田 佳洋 柴田 直樹 伊藤 実
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
巻号頁・発行日
vol.2003, no.91, pp.65-68, 2003-09-18

筆者らが以前提案した自己適応島GAは,各島のパラメータをやりとりする際に全ての島が同期して動作しなければならず,島を担当する計算機の能力に違いがある場合に待ち時間が発生していた.本手法では,アルゴリズムに改良を加え,同期を取る必要をなくすることにより性能を向上させた.また,比較実験を通して,計算機の能力に違いがある場合に,従来アルゴリズムよりも時間あたりの探索性能が改善されていることを確認した.また,一定評価回数での探索性能を比較し,解の探索能力が若干改善されていることを確認した.We have previously proposed SAIGA(self adaptive island GA), but it requires all islands to be synchronized when exchanging parameters between islands. In this paper, we propose a technique to avoid this synchronization. We also confirmed that our new algorithm largely outperforms our previous algorithm if there are large differences between processing power of each island. Through experiments, we confirmed that there is slight improvement of search performance from our previous algorithm if both of algorithm uses same number of evaluations.
著者
加藤 宏和 村田 佳洋
出版者
一般社団法人情報処理学会
雑誌
研究報告ソフトウェア工学(SE)
巻号頁・発行日
vol.2012, no.1, pp.1-6, 2012-10-25

近年,パーソナルナビゲーションシステムに関する研究が数多くなされており,観光スケジュール立案のためのナピゲーションシステムも研究されている観光スケジュールは天候の影響を受けるしかし、天候を完壁に予測することは不可能であるそのため,天候に応じたスケジュール群立案手法が必要となるそこで我々は,この手法のための天候変化パターンを生成するアルゴリズムを提案したこのアルゴリズムは,時間帯に応じた降水確率を与えることで,その時間に起こりうる天候をシミュレートするものであるシミュレートして得られた天候変化パターンから確率通りの降水の割合が得られているかを調査するため,与えた降水確率と比較した.その結果,最大 14% の誤差があるものの,ほぼ元の降水確率通りの割合が得られることがわかった.Recently, personal navigation systems and tour scheduling systems are studied. Tour schedule is af fected by weather conditions. But, it is impossible to predict accurate weather. Therefore, schedules are required for according to the weather conditions. So, we have proposed weather change pattern generation algorithm. This algorithm is given probability of precipitation according to the time zone, it simulates possible weather conditions at that time. To evaluate proposed algorithm, we compared the probability of precipitation with the rate of rainfall of weather change patterns generated by simulating. As a result, there is an error of no more than 1.4%, it was found that the obtained rate is similar to the original probability of precipitation.
著者
山本 眞也 村田 佳洋 安本 慶一 伊藤 実
出版者
一般社団法人情報処理学会
巻号頁・発行日
2006-02-15

本論文では,ネットワークゲーム向け分散型イベント配送方式を提案する.本方式は,ロビーサーバを用いたHybrid P2P の環境で多人数参加型ネットワークゲームを実現することを目的としている.これを実現するため,ゲームで発生するイベントの登録・通知をゲーム領域の分割によってできた部分領域ごとにゲーム参加者の計算機に担当させ,分散処理させる.各領域のプレイヤ数が増加してイベント通知を担当する計算機の負荷が高くなると,複数の計算機からなる負荷分散木を動的に構築し,イベント通知を負荷分散木を経由して行うことで1台あたりの負荷を軽減する.また,負荷分散木上のノードの動的入れ替えによる,エンド・エンドのイベント配送遅延の短縮法,各プレイヤの視界が複数の部分領域にまたがる場合のイベント配送法を提案する.LAN環境で動作するプロトタイプシステムによる実験と,ns-2によるシミュレーション実験を行い,提案手法が現実のネットワークゲームを実現するうえで,実用的な性能を達成できることを確認した.In order to achieve multi-party networked games with lobby server in Hybrid P2P enviroments, we propose a publish/subscribe based distributed event delivery method. In our method, a shared game space is divided into multiple sub-areas and some nodes are selected from all players to deliver game events occurring in their responsible areas to player nodes. This method also includes a load balancing mechanism which allows each responsible node for the crowded area to dynamically construct a tree of multiple nodes and deliver events along the tree to reduce event forwarding overhead per node. We also propose techniques (1) to reduce end-to-end event delivery latency by dynamically replacing nodes in the tree, and (2) to efficiently deliver events to players who have visible areas over multiple sub-areas. Experiments in LAN using our prototype system and through simulations with ns-2, we have confirmed that the proposed method can achieve practical performance for MMORPG.
著者
橘 達弘 村田 佳洋 柴田 直樹 安本 慶一 伊藤 実
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.49, no.1, pp.381-392, 2008-01-15
参考文献数
19
被引用文献数
1

多目的遺伝的アルゴリズム(Multi-Objective Genetic Algorithms,MOGA)は,多目的最適化問題を解くために単一目的遺伝的アルゴリズムを拡張した最適化手法である.MOGA では複数の個体群の多様性を維持するための手法であるニッチ法やランク戦略がよく用いられるため,単一目的GA よりさらに計算量が大きくなる傾向がある.本論文では,多目的最適化問題を高速に解くことを目的とし,ハードウェア化のためのMOGA のアーキテクチャを提案する.提案方式では,世代交代モデルとしてハードウェア化に適したMinimal Generation Gap モデルを採用する.既存のニッチ法やランク戦略をパイプライン処理で実装することは困難なため,パイプライン処理に適した多様性を維持する手法を設計,採用した.また,解探索能力の向上のために,島モデル型GA の各島の目的関数を改変した並列GA モデルに即した並列実行方式を設計し,提案アーキテクチャに採用した.実験の結果,提案アーキテクチャによるMOGA 回路はNSGA-II より優れた探索能力を持つことを確認した.Multi-Objective Genetic Algorithms (MOGAs) are enhancement of Single-Objective Genetic Algorithms (SOGAs) to solve multi-objective optimization problems. Since MOGAs require a special selection mechanism such as ranking strategy and niching method to preserve diversity of individuals, MOGAs require larger computation power than SOGAs. In order to improve calculation speed of MOGAs, we propose a new method to easily implement MOGAs as high performance hardware circuits. In the proposed method, we adopt a simple minimal generation gap model as the generation model, which is easy to be pipelined. Since it is difficult to implement niching method and ranking strategy as pipelined circuits, we developed a new selection mechanism which is suitable for hardware implementation. In order to improve search efficiency, our method also includes a parallel execution architecture based on island GA. In this architecture, we use different objective function for each island. Through experiments, we confirmed that our method has higher search efficiency than NSGA-II.
著者
松田 大樹 村田 佳洋
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.57, no.5, pp.1452-1463, 2016-05-15

近年,移動の快適性を考慮した経路探索システムが積極的に取り入れられている.たとえば,交通渋滞や道幅を考慮した経路探索システムがある.本研究では,西日の眩しさを考慮した経路探索アルゴリズムを提案する.このアルゴリズムはダイクストラ法に基づいており,そして,時刻に対する道路網グラフの眩しさの変化を考慮しながら経路探索を行う.また,提案アルゴリズムでは建物の影を考慮する.計算コストを抑えるために,建物データは東西に伸びる長方形のグリッド単位で管理されている.提案アルゴリズムの性能を評価するため,広島市内の地図を用いて実験した.
著者
加藤 宏和 村田 佳洋
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス (ISSN:09135685)
巻号頁・発行日
vol.112, no.275, pp.1-6, 2012-10-25

近年,パーソナルナビゲーションシステムに関する研究が数多くなされており,観光スケジュール立案のためのナビゲーションシステムも研究されている.観光スケジュールは天候の影響を受ける.しかし,天候を完璧に予測することは不可能である.そのため,天候に応じたスケジュール群立案手法が必要となる.そこで我々は,この手法のための天候変化パターンを生成するアルゴリズムを提案した.このアルゴリズムは,時間帯に応じた降水確率を与えることで,その時間に起こりうる天候をシミュレートするものである.シミュレートして得られた天候変化パターンから確率通りの降水の割合が得られているかを調査するため,与えた降水確率と比較した.その結果,最大1.4%の誤差があるものの,ほぼ元の降水確率通りの割合が得られることがわかった.
著者
武兵 孫為華 村田 佳洋 安本 慶一 伊藤 実
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌 (ISSN:18827764)
巻号頁・発行日
vol.54, no.3, pp.1141-1152, 2013-03-15

観光においては,ユーザの好む観光スポットをより多く回るスケジュールを立案することが望ましい.しかし各観光スポットにつき,観光方式や観光時間によって必要な体力が異なり,ユーザの体力がスケジュールを遂行できない場合がある.本論文では,観光中に休憩を適宜に行うことで体力の範囲内で最も満足度が高くなる観光スケジュールを求める問題を取り扱う.本問題はNP困難であり,問題例の規模が大きいときには,実用時間で最適解を算出することは困難である.実用時間で準最適解を得るため,ヒューリスティックな探索法である捕食法に基づいて複数の観光スポットを回る休憩なしのスケジュールを求めたうえ,局所探索を用いて適宜に休憩を差し挟むことで解を求める.提案手法を評価するため,異なる観光地候補数を有する複数のインスタンスを用いてシミュレーション実験を行った.その結果,候補数10の場合,提案手法は全探索で得られた解の95.65%の満足度を有するスケジュールを13秒で得られることを確認した.Tour schedules are required to include multiple sightseeing spots taking into account the user's preference, but the stamina of tourists may be depleted during sightseeing. In this paper, we formulate the sightseeing scheduling problem to maximize the user's satisfaction taking stamina into account. In this problem, break times are allocated in schedules to hold constraint of stamina. This problem is NP-hard, and thus it is difficult to be solved in practical time. In order to obtain a semi-optimal solution in practical time, we propose a method that derives a schedule visiting multiple sightseeing spots with no break times based on a predatory search technique and then allocates the break times in the schedule using a local search technique. To evaluate the proposed method, we compared our method with conventional methods through computer simulations for several different instances containing 10 sightseeing spots. As a result, the proposed method composed the schedule whose expected satisfaction is 95.65% of the optimum solution in 13 sec.