大規模組合せ最適化問題に対する効率的メタ戦略の設計と評価
大规模组合优化问题的有效元策略的设计和评估
基本信息
- 批准号:11750350
- 负责人:
- 金额:$ 1.54万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Encouragement of Young Scientists (A)
- 财政年份:1999
- 资助国家:日本
- 起止时间:1999 至 2000
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
多くのシステム工学的、情報工学的問題は、組合せ最適化問題として定式化できる。しかし、その多くに対して、取り扱おうとする問題の規模が大きい場合、厳密な最適解を求めることがきわめて困難である。このような問題に現実的に対処するための一手法として、メタ戦略の研究が盛んである。メタ戦略の代表的なものとして、遺伝アルゴリズム、アニーリング法、タブー探索法などがあるが、本研究では、これらを局所探索の一般化と考えることで統一的に捉えて、様々なアイディアを体系的に整理し、そのような視点のもとで、効率的なアルゴリズムを設計するための指針を得るべく研究を行った。メタ戦略アルゴリズムの一つの魅力として、その手軽さが挙げられる。すなわち、多くの問題に対して比較的容易に適用でき、しかもかなりの精度が期待できる点である。この観点から、これまでに1機械スケジューリング問題と最大充足可能性問題に対して計算実験を行い、一定の成果を上げていた。本年度は、最大充足可能性問題に対する計算実験を継続して行うとともに、集合被服問題、一般化時間枠制約つき配送計画問題など、より多くの問題に対して計算実験を行い、「手軽なツール」としてのメタ戦略の設計指針を考察した。その結果、反復局所探索法がこの目的に適しているという結論を得ている。反復局所探索法は、過去の探索で得られたよい解(暫定解など)にランダムな変形を加えたものを局所探索の初期解として、局所探索法を反復する方法で、単純であるが、比較的高性能であることが我々の計算実験を通して確認されたからである。メタ戦略のもう一つの魅力として、様々な工夫を加えることでより性能の高いものを作ることができる点が挙げられる。本研究では、メタ戦略に加える工夫の中でも、とくに、局所探索の基本的な部分にかかわる性能向上・効率化に重点を置いた。本年度は、一般化割当問題や、それをさらに一般化した問題などに対して、単純な近傍をより高度に組み合わせる、排除連鎖法と呼ばれる手法を適用し、高い能力を有するメタ戦略アルゴリズムの設計に成功した。集合被服問題に対しても、近傍の探索効率を大幅に落とすことなくより広い近傍を探索する工夫を加えることにより、性能の向上を図った。研究費により購入した計算機器は、上述の計算実験を遂行し、また、それらの結果を取りまとめるのに利用した。さらには、研究成果を報告するための海外渡航費としても利用した。
Multi-disciplinary engineering, information engineering problems, combination optimization problems, and formalization There are many problems, the scale of the problem is large, and the optimal solution is difficult to find. A method of solving problems is proposed. This study aims to explore the generalization of the system and the efficiency of the system. The charm and charm of the game are different from those of the game. Easy to apply, easy to compare, easy to understand, easy to understand. The problem of maximum sufficiency is the problem of calculation and implementation. This year, the calculation of maximum adequacy problems, the collection of clothing problems, the generalized time constraints of distribution planning problems, the calculation of multiple problems, and the design of "manual" problems were examined. The result, the repeated exploration method, the purpose, the conclusion, the result, the result, the result. Iterative local search method is simple, simple, and high performance compared to previous search methods. The charm of the game, the time of the game, the performance of the game This study focuses on the fundamental aspects of performance and efficiency. This year, we have generalized problems, pure problems, highly organized problems, excluded linkage methods, and successful design. Set up a search engine and search engine. The research fee was paid for the acquisition of computing machines, and the calculations were carried out and the results obtained were utilized. The results of the study were reported on and used for overseas navigation.
项目成果
期刊论文数量(22)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
柳浦睦憲, 茨木俊秀: "組合せ最適化-メタ戦略を中心として-"朝倉書店. 237 (2001)
Mutsunori Yanagura、Toshihide Ibaraki:“组合优化 - 聚焦元策略 -”朝仓书店 237 (2001)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
M.Yagiura and T.Ibaraki: "Analyses on the 2 and 3-flip neighborhoods for the MAX SAT"Journal of Combinatorial Optimization. Vol.3. 95-114 (1999)
M.Yagiura 和 T.Ibaraki:“MAX SAT 的 2 和 3 翻转邻域分析”组合优化杂志。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
T.Uno and M.Yagiura: "Fast Algorithms to Enumerate All Common Intervals of Two Permutations"Algorithmica. Vol.26,No.2. 290-309 (2000)
T.Uno 和 M.Yagiura:“枚举两个排列的所有常见区间的快速算法”算法。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
M.Yagiura and T.Ibaraki: "Efficient 2 and 3-Flip Neighborhood Algorithms for the MAX SAT : Experimental Evaluation"Journal of Heuristics. (掲載予定).
M.Yagiura 和 T.Ibaraki:“MAX SAT 的高效 2 和 3-Flip 邻域算法:实验评估”启发式杂志(待出版)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
E.Boros,T.Horiyama,T.Ibaraki,K.makino and M.Yagiura: "Finding Essential Attributes in Binary Data"Proceedings of the Second International Conference on Intelligent Data Engineering and Automated Learning. 133-138 (2000)
E.Boros、T.Horiyama、T.Ibaraki、K.makino 和 M.Yagiura:“在二进制数据中寻找基本属性”第二届智能数据工程和自动化学习国际会议论文集。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
柳浦 睦憲其他文献
Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (数理最適化から見た「凸性の深み、非凸性の魅惑」研究集会報告集)
给定数量不同模式的二维下料问题的局部搜索算法(数学优化角度凸性深度与非凸性魅力研究会报告)
- DOI:
- 发表时间:
2004 - 期刊:
- 影响因子:0
- 作者:
今堀 慎治;柳浦 睦憲;足達 信也;茨木 俊秀;梅谷 俊治 - 通讯作者:
梅谷 俊治
柳浦 睦憲的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('柳浦 睦憲', 18)}}的其他基金
物流を支える基盤技術としての数理最適化とメタ戦略
数学优化和元策略作为支持物流的基础技术
- 批准号:
23K20268 - 财政年份:2024
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
物流を支える基盤技術としての数理最適化とメタ戦略
数学优化和元策略作为支持物流的基础技术
- 批准号:
20H02388 - 财政年份:2020
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
大規模ゲノムデータ処理に対する高速高精度アルゴリズムの開発
开发用于大规模基因组数据处理的高速、高精度算法
- 批准号:
18017015 - 财政年份:2006
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research on Priority Areas
大規模組合せ最適化問題に対するハイブリッドメタ戦略アルゴリズムの開発と評価
针对大规模组合优化问题的混合元策略算法的开发和评估
- 批准号:
17700016 - 财政年份:2005
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
大規模ゲノム情報の高度な検索・比較に関する基礎技術開発とデータマイニングへの応用
大规模基因组信息高级搜索、比对基础技术开发及其在数据挖掘中的应用
- 批准号:
17018023 - 财政年份:2005
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research on Priority Areas
大規模かつ複雑な組合せ最適化問題に対する効率的かつ汎用的メタ戦略の開発と応用
针对大规模复杂组合优化问题的高效通用元策略的开发和应用
- 批准号:
14750333 - 财政年份:2002
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する実験的解析
大规模组合优化问题元策略鲁棒性的实验分析
- 批准号:
09750453 - 财政年份:1997
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する研究
大规模组合优化问题元策略的鲁棒性研究
- 批准号:
08750479 - 财政年份:1996
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
相似海外基金
物流を支える基盤技術としての数理最適化とメタ戦略
数学优化和元策略作为支持物流的基础技术
- 批准号:
23K20268 - 财政年份:2024
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
物流を支える基盤技術としての数理最適化とメタ戦略
数学优化和元策略作为支持物流的基础技术
- 批准号:
20H02388 - 财政年份:2020
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
可変深度探索に基づく高性能メタ戦略アルゴリズムの開発
基于变深度搜索的高性能元策略算法开发
- 批准号:
19K12166 - 财政年份:2019
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
硫化水素分解生物とメタ戦略を組合せた広域下水管網長寿命化技術開発
硫化氢分解生物与元策略相结合,开发延长广域污水管网使用寿命的技术
- 批准号:
21656115 - 财政年份:2009
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Challenging Exploratory Research
メタ戦略に基づく3次元物体の最適配置を求めるフレームワークの構築
构建一个框架以基于元策略找到 3D 对象的最佳放置
- 批准号:
07J01821 - 财政年份:2007
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for JSPS Fellows
大規模かつ複雑な組合せ最適化問題に対する効率的かつ汎用的メタ戦略の開発と応用
针对大规模复杂组合优化问题的高效通用元策略的开发和应用
- 批准号:
14750333 - 财政年份:2002
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
汎用カッティングストック問題に対するメタ戦略を用いた近似解法の研究
通用下料问题元策略近似求解方法研究
- 批准号:
00J03095 - 财政年份:2000
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for JSPS Fellows
組合せ最適化問題に対するメタ戦略の総合的評価とハイブリッド型戦略の構築
组合优化问题的元策略的综合评估和混合策略的构建
- 批准号:
10780270 - 财政年份:1998
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する実験的解析
大规模组合优化问题元策略鲁棒性的实验分析
- 批准号:
09750453 - 财政年份:1997
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
大規模組合せ最適化問題に対するメタ戦略のロバスト性に関する研究
大规模组合优化问题元策略的鲁棒性研究
- 批准号:
08750479 - 财政年份:1996
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)