系列分割問題に対する確率的複合移動によるSimulated Annealing法の適用

• Item type: Journal(1)
• 公開日: 1997-12-15
• タイトル: 系列分割問題に対する確率的複合移動によるSimulated Annealing法の適用
• タイトル / 言語: en
• タイトル: A Simulated Annealing Approach Using Random Compound Move for Sequential Partitions Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: オペレーションズリサーチ
• 著者所属: 小樽商科大学商学部社会情報学科
• 著者所属: 北海道大学工学部システム情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information and Management Science, Faculty of Commerce, Otaru University of Commerce
• 著者所属(英): en
• 著者所属(英): Division of Systems and Information Engineering, Faculty of Engineering, Hokkaido University
• 著者名: 加地, 太一; 大内, 東
• 著者名(英): Taichi, Kaji; Azuma, Ohuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では無閉路有向グラフの系列分割問題に対するSimulated Annealing法の適用とその有効性について検討している．本問題はその特徴として，解の成分集合の個数，各成分集合の要素数がともに不定であり，これが解の近傍処理などの操作を複雑にし探索法の構成を難しくしている．そのため，通常の近傍移動のみでは近似度のより良い結果は望めない．これに対して，本論文では一列化グラフとブレイク・ポイントの集合を用いたデータ構造を利用し，グラフ分割問題における従来の近傍移動であるleft?to?right移動，right?to?left移動の組織的で多重的な適用と，部分的な最適化を取り入れ，複合的な処理方法を用い効果的な近傍移動を実現した．さらに，通常のSimulated Annealing法の採択基準と異なる局部的なコスト差による新たな基準を設け効果をはかっている．以上の複合的な近傍移動により解に大きな変化をほどこしSimulated Annealing法の性能をより強く引き出し，その特徴も維持する結果となった．さらに，今回考案した確率的複合移動の効果を数値実験により示し，Tabu Search法による解法と比較し本算法の性能を明らかにした．それによると，提案する算法はTabu Search法により求まる解より良質な解を導き，また，その計算時間もほぼ頂点数に線形に増加する傾向が示された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents an approach based on simulated annealing algorithm for finding a minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size,subject to the constraint that the precedence relationship are satisfied.The simulated annealing algorithm imposes different randomized search and acceptance criteria on local search method in order to escape poor quality local minima.The method generally can obtain solutions arbitrarily close to an optimum.But a standard simulated annealing approach can't find good solutions for this problem,because the problem is complex multiple partitioning problems in which the number of subsets and the number of nodes in each subset are unsettled.For this problem,we use appropriate data structure for this method,and develop effective neighbourhood structure and new acceptance criterion.And,we assess the effectiveness of the developed algorithm.The results show that this algorithm outperform the algorithm using tabu search in solution quality and computational time.It is effective in obtaining near-optimal solution to this problem.The running time of the procedure is proportional to the number of nodes in the graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 38, 号 12, p. 2411-2418, 発行日 1997-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764