安定結婚問題における男女平等解のGAによる探索
スポンサーリンク
概要
- 論文の詳細を見る
安定結婚問題は1962年にGale&Shapleyによって提案された計算機科学の基礎的な問題の一つである.文献において,彼等は一つの安定なマッチングを見つける多項式時間アルゴリズムを提案した.これを基本アルゴリズムと呼ぶ.安定なマッチングの数は最悪の場合問題のサイズの指数オーダーになることが知られている.Gale&Shapleyの基本アルゴリズムが見つける安定なマッチングは,数あるマッチングの中ですべての男性が最良のパートナーと結ばれるようなマッチングである.このとき,すべての女性は最悪のパートナーとマッチングすることになる.本稿では,男女間に満足度の片寄りのないマッチング,すなわち,男女平等解について議論し,それを求める遺伝的アルゴリズムを提案する.2節において安定マッチングと男女平等解について概説し,3節では,遺伝的アルゴリズムによる男女平等解の探索法とその実験結果を示す.
- 電子情報通信学会の論文
- 1994-09-26
著者
関連論文
- 分散安定マッチング問題とネットアプリケーションの検討
- CST2000-14 並列分散GAにおける階層リング型染色体交換方式の実装の検討
- 配送経路問題における自律分散解法
- 配送経路問題における自律分散解法
- モバイルGISにおける最適空間データ転送
- SA-6-2 エージェント技術を用いた分散安定マッチングのネットアプリケーション
- 琉球大学HDL・デザイン・コンテスト2000結果報告
- 沖縄県マルチメディア・アイランド構想と琉球大学SOC設計教育
- ナップザック問題における遺伝的アルゴリズムの改良
- GA空間の階層化
- 安定結婚問題における男女平等解のGAによる探索
- A-5 GA空間の階層化(A-1. 回路とシステムA,一般講演)
- A-3 安定結婚問題における男女平等解のGAによる探索(A-1. 回路とシステムA,一般講演)
- インターネット遠隔計測系とバッテリーレス太陽光発電システムに基づく自律的ITファームの研究開発
- 分散安定結婚問題とその自律行動ロボットの充電問題への応用
- 分散安定結婚問題を解くGale-Shapley基本解に基づくアルゴリズム
- 複数の近傍探索法を遺伝子化した遺伝的アルゴリズム
- 世界のDAGを利用した投機的makeの実現
- 粗粒度投機的処理を支援するオペレーティング・システムにおけるファイル・システム
- 投機的処理を支援するオペレーティング・システムにおける世界とプロセスの操作
- 投機的処理を支援するオペレーティング・システムにおける世界とプロセスの操作
- A-12-3 広域分散環境におけるメタヒューリスティクスの並列処理手法(A-12.コンカレント工学,一般講演)
- A-12-2 プログレッシブマルチプルアラインメントの並列化と再計算の効率化(A-12.コンカレント工学,一般講演)
- 遺伝的アルゴリズムによる優先順位リストの一構成法
- 自律分散並列機械スケジューリングの拡張ペトリネットによる表現
- マルチハイブリッド発電システムのための自然エネルギー予測に基づく自律分散制御
- 連結可能ウィンドウ・オブジェクト
- リアルタイムシステム設計におけるUML相互作用図のペトリネット表現
- SA-6-5 分散地理情報システムとコンカレント工学
- 進化ツリーベース法によるマルチプルアライメント問題の解法(コンカレントシステム, 一般)
- 創業マインド教育は地方の未来エンジンとなりうるか
- オブジェクトの堆積モデルに基づく高機能ディレクトリ・オブジェクト
- オブジェクトの堆積モデルに基づく高機能ディレクトリ・オブジェクト
- オブジェクトの堆積モデルに基づく間接オブジェクトの実現
- イレギュラー・ネットワークトポロジーにおける並列分散遺伝的アルゴリズム
- 社会システムに新たな研究テーマを求めて : コンカーレント技術適用の視野拡大を
- A-12-3 位置ベースアドホックルーティングプロトコルにおける経路修復手法(A-12.システム数理と応用,一般セッション)