閾値を動的に調整する閾値受理法の二次割当問題への応用

カテゴリ: 研究会(論文単位)

論文No: IIC11123

グループ名: 【D】産業応用部門 産業計測制御研究会

発行日: 2011/03/09

タイトル(英語): Threshold Accepting with dynamically tuning threshold and its application to Quadratic Assignment Problem

著者名: 田邉 恭佑(千葉大学),小圷 成一(千葉大学),岡本 卓(千葉大学),平田 廣則(千葉大学)

著者名(英語): TANABE Kyousuke(Chiba University),KOAKUTSU Seiichi(Chiba University),OKAMOTO Takashi(Chiba University),HIRATA Hironori(Chiba University)

キーワード: 閾値受理法|シミュレーテッドアニーリング|二次割当問題|組合せ最適化|Threshold Accepting|Simulated Annealing|Quadratic Assignment Problem|Combinatorial Optimization

要約(日本語): 閾値受理法は，アニーリング法における状態遷移規則を簡素化した最適化手法で，改悪を許容する閾値を制御することで探索範囲を調整する手法である。閾値受理法では，閾値スケジュールを決めるパラメータを問題に応じて適切に設定する必要がある。本稿では，最適なスケジュールパラメータを探索の途上で推定する手法を提案する。提案手法を二次割当問題に応用し，その有効性を検証する。

要約(英語): Threshold Accepting (TA) is one of efficient iterative improvementmethods for combinatorial optimization problems. In this article, wepropose a new improved TA in which the cooling schedule of threshold isdetermined automatically. We apply the proposed method to QuadraticAssignment Problems and verify its effectiveness.

原稿種別: 日本語

PDFファイルサイズ: 558 Kバイト