权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

組合せ最適化問題に対するメタ戦略の総合的評価とハイブリッド型戦略の構築

组合优化问题的元策略的综合评估和混合策略的构建

基本信息

批准号：
10780270
负责人：
加地太一
金额：
$ 1.22万
依托单位：
Otaru University of Commerce
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

项目摘要

近年、計算困難な問題である組合せ最適化問題に対してGenetic Algorithm、Simulated Annealing、Tabu Searchなどに代表されるメタヒューリスティックにより有効な手法が種々提案されている。しかし、これらの手法の各問題に対する優劣は明確ではなく、各応用分野で利用するための総合的な評価分析と効果的な手法の検討が望まれている。そこで、グラフ分割問題、巡回セールスマン問題など試金石とされている代表的な組合せ最適化問題をターゲットとしメタヒューリスティックアルゴリズムの性能を分析する。まず、以上の問題に対して標準的なGenetic Algorithm、Simulated Annealing、Tabu Searchおよびアントシステムアルゴリズム等を構成する。以上の各算法について数値実験を行い、各問題に対する特性と、アルゴリズムの優劣を判定する。それによると、グラフの多分割問題ではSimulated AnnealingがTabu Searchをやや上回り、Genetic Algorithmにおいてはこの問題に対してはLocal Searchにも及ばない劣勢な解を求めるのにとどまった。最後に、実験によって得られた各アルゴリズムの特性より、より有効な戦略を結合したハイブリッド型のアルゴリズムを提案する。巡回セールスマン問題ではアントシステムアルゴリズムのフェロモン強化とTabuのハイブリッドによる改良型が有効な結果をもたらし、新たなメタヒューリスティックアルゴリズムの展開が期待される。また、並列計算パラダイムをメタヒューリスティックアルゴリズムに組み込んだ並列Tabu Searchアルゴリズムの構築を行い、その結果、従来のアルゴリズムに対して大幅な改善が示され、新たなメタヒューリスティックの計算パラダイムへの基盤となるものと考える。

In recent years, computational difficulty problems, combinatorial optimization problems, Genetic Algorithm, Simulated Annealing, Tabu Search, etc. have been proposed. The advantages and disadvantages of each method are clear, the advantages and For example, a combination optimization problem represented by a touchstone for analyzing the performance of a mobile phone is a problem of segmentation and rotation. The above problems are related to the standard Genetic Algorithm, Simulated Annealing, Tabu Search, and Search System. The above algorithms are used to determine the quality of each problem. The problem of multi-partition is solved by Simulated Annealing, Tabu Search and Genetic Algorithm. Finally, we can get the characteristics of each group and propose a combination of them. The results of the improved version of the game are expected to be released in the future. In addition, the parallel calculation of the table Search is carried out in the construction of the table search, and the results of the table search are greatly improved.