大規模組合せ最適化問題に対する効率的メタ戦略の設計と評価

大规模组合优化问题的有效元策略的设计和评估

基本信息

批准号：
11750350
负责人：
柳浦睦憲
金额：
$ 1.54万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

多くのシステム工学的、情報工学的問題は、組合せ最適化問題として定式化できる。しかし、その多くに対して、取り扱おうとする問題の規模が大きい場合、厳密な最適解を求めることがきわめて困難である。このような問題に現実的に対処するための一手法として、メタ戦略の研究が盛んである。メタ戦略の代表的なものとして、遺伝アルゴリズム、アニーリング法、タブー探索法などがあるが、本研究では、これらを局所探索の一般化と考えることで統一的に捉えて、様々なアイディアを体系的に整理し、そのような視点のもとで、効率的なアルゴリズムを設計するための指針を得るべく研究を行った。メタ戦略アルゴリズムの一つの魅力として、その手軽さが挙げられる。すなわち、多くの問題に対して比較的容易に適用でき、しかもかなりの精度が期待できる点である。この観点から、これまでに1機械スケジューリング問題と最大充足可能性問題に対して計算実験を行い、一定の成果を上げていた。本年度は、最大充足可能性問題に対する計算実験を継続して行うとともに、集合被服問題、一般化時間枠制約つき配送計画問題など、より多くの問題に対して計算実験を行い、「手軽なツール」としてのメタ戦略の設計指針を考察した。その結果、反復局所探索法がこの目的に適しているという結論を得ている。反復局所探索法は、過去の探索で得られたよい解(暫定解など)にランダムな変形を加えたものを局所探索の初期解として、局所探索法を反復する方法で、単純であるが、比較的高性能であることが我々の計算実験を通して確認されたからである。メタ戦略のもう一つの魅力として、様々な工夫を加えることでより性能の高いものを作ることができる点が挙げられる。本研究では、メタ戦略に加える工夫の中でも、とくに、局所探索の基本的な部分にかかわる性能向上・効率化に重点を置いた。本年度は、一般化割当問題や、それをさらに一般化した問題などに対して、単純な近傍をより高度に組み合わせる、排除連鎖法と呼ばれる手法を適用し、高い能力を有するメタ戦略アルゴリズムの設計に成功した。集合被服問題に対しても、近傍の探索効率を大幅に落とすことなくより広い近傍を探索する工夫を加えることにより、性能の向上を図った。研究費により購入した計算機器は、上述の計算実験を遂行し、また、それらの結果を取りまとめるのに利用した。さらには、研究成果を報告するための海外渡航費としても利用した。

许多系统工程和信息工程问题可以作为组合优化问题提出。但是，对于许多其中，当解决问题的规模很大时，很难找到严格的最佳解决方案。对元战略的研究是一种以现实方式处理此类问题的流行方法。代表性的元策略包括遗传算法，退火方法和禁忌搜索方法，但是在这项研究中，我们将其视为以统一的方式对本地搜索的概括，系统地组织了各种思想，并进行了研究以获得从这个角度从这个角度设计有效算法的指南。元战略算法的景点之一是其易用性。也就是说，它可以相对容易地应用于许多问题，并有望具有相当精确的准确性。从这个角度来看，我们已经进行了有关单机调度问题和最大满意度问题的计算实验，从而实现了某些结果。今年，我们继续对最大满意度概率问题进行计算实验，还对更多问题进行了计算实验，例如设置涵盖问题和通过广义时间框架约束的交付计划问题，并将元策略的设计指南作为“简单工具”。结果得出的结论是，迭代局部搜索方法适合此目的。这是因为迭代本地搜索方法是一种使用良好解决方案（例如临时解决方案）重复本地搜索方法的方法，该方法是从过去的搜索中获得的，它是随机变化作为本地搜索的初始解决方案。通过我们的计算实验证实，它是简单但相对较高的性能。元策略的另一个吸引人的特征是，它可以通过增加各种创造力来创造更高的性能。在增加元策略的努力中，这项研究的重点是提高性能和效率，尤其是涉及本地搜索的基本部分。今年，我们通过应用一种称为“ Dublusion Chain方法”的方法成功地设计了一种功能强大的元战略算法，该方法将简单的社区更加高度地结合起来，以概括已概括的问题和问题。除了集体服装问题外，还通过添加一种搜索更广阔社区的方法而不大大降低了社区的搜索效率，从而提高了性能。用于研究资金购买的计算设备用于进行上述计算实验并编译结果。它也被用作海外旅行的旅行费用，以报告研究结果。