| 講演名 | 2015-12-19 希望順位を反映したリソース割当て問題における効率的な割当てアルゴリズムの提案 齋藤 健吾(早大), 菅原 俊治(早大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では、希望順位を反映したリソース割当て問題を定式化し、準最適解を求める効率的なアルゴリズムを複数提案する。リソース割当ては基本的で応用の広い問題形式であり多くの研究が存在する。特にAIの分野ではマルチエージェトシステムで社会余剰や効用値の最大化に焦点を当てた研究が行われている。しかし、各エージェントの希望を反映した研究はほとんどない。ここで提案するリソース割当て問題では、エージェントに割当てられるリソースは1つであるが、エージェントはリソースに希望順位付きで複数指定できるものとしている。リソースを各エージェントに割当てる際には、希望順位を反映させ不満を最小に抑えながらも価値の総和を最大化する。最適解の求解は基本的に組み合わせ問題であるためコストは大きい。そこで、エージェントの希望を最大限に考慮した準最適解を効率的に求める手法を複数提案する。そして、それらの解の性質と処理時間をCPLEXで求めた最適解と比較し分析する。実験により提案手法が極めて効率的であり、解の質も高いことを示す。 |
| 抄録(英) | This paper introduces a resource allocation problem with agents'preference orders and proposes efficient algorithms for semi-optimal allocations. A numberof studies are dedicated to resource allocation problems because it isa fundamental problem solving framework in computer science, but they have rarely taken into account agents' individual preferential orders. Our proposed framework allocates one unit of resources to eachagent but allows them to declare multiple resources with their ownpreferential orders. It then tries to allocate a resource to eachagent by not only maximizing total value but also considering theagent's preference. Finally, we analyze the quality of solutions bycomparing them with the optimal solutions obtained by CPLEX. |
| キーワード(和) | リソース割当て問題 / オークション / 多目的最適化 / 整数計画問題 |
| キーワード(英) | Resource Allocation Problem / Auction / Multi-objective optimization / Integer programming |
| 資料番号 | AI2015-46 |
| 発行日 | 2015-12-11 (AI) |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 2015/12/18(から2日開催) |
| 開催地（和） | 那覇市ぶんかテンブス館 |
| 開催地（英） | |
| テーマ（和） | 「コンテキストを意識した知識の利用」および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 菅原 俊治(早大) |
| 委員長氏名（英） | Toshiharu Sugawara(Waseda Univ.) |
| 副委員長氏名（和） | 峯 恒憲(九大) / 片上 大輔(東京工芸大) |
| 副委員長氏名（英） | Tsunenori Mine(Kyushu Univ.) / Daisuke Katagami(Tokyo Polytechnic Univ.) |
| 幹事氏名（和） | 服部 宏充(京大) / 福田 直樹(静岡大) |
| 幹事氏名（英） | Hiromitsu Hattori(Kyoto Univ.) / Naoki Fukuda(Shizuoka Univ.) |
| 幹事補佐氏名（和） | 清 雄一(電通大) |
| 幹事補佐氏名（英） | Yuichi Sei(Univ. of Electro-Comm.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Artificial Intelligence and Knowledge-Based Processing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 希望順位を反映したリソース割当て問題における効率的な割当てアルゴリズムの提案 |
| サブタイトル（和） | |
| タイトル（英） | Resource Allocation with Preference Order and Effective Allocation Methods |
| サブタイトル（和） | |
| キーワード(1)（和/英） | リソース割当て問題 / Resource Allocation Problem |
| キーワード(2)（和/英） | オークション / Auction |
| キーワード(3)（和/英） | 多目的最適化 / Multi-objective optimization |
| キーワード(4)（和/英） | 整数計画問題 / Integer programming |
| 第 1 著者 氏名（和/英） | 齋藤 健吾 / Kengo Saito |
| 第 1 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 2 著者 氏名（和/英） | 菅原 俊治 / Toshiharu Sugawara |
| 第 2 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 発表年月日 | 2015-12-19 |
| 資料番号 | AI2015-46 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | AI-381 |
| ページ範囲 | pp.119-124(AI), |
| ページ数 | 6 |
| 発行日 | 2015-12-11 (AI) |