超大規模組合せ最適化問題における新パラダイムの構築とその応用

超大规模组合优化问题新范式构建及其应用

基本信息

批准号：
21K12044
负责人：
外山史
金额：
$ 2.58万
依托单位：
Utsunomiya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K12044/
关键词：
メタ戦略組合せ最適化ソフトコンピューティング

项目摘要

本研究の目的は、従来扱うことができなかった超大規模な組合せ最適化問題に対する革新的なアルゴリズムを開発し、様々な問題に適用することでこの分野における新しいパラダイムを構築することである。本年度は、我々が提案した最大多様性問題(Maximum Diversity Problem)に対する初期近傍探索法における、局所探索法についての検討を行った。最大多様性問題は、与えられたn個の要素からm個の要素を選ぶとき、できるだけ多様性を有するように要素を選択する組み合わせ最適化問題であり、ネットワーク設計やVLSI設計など応用範囲の広い問題として知られている。最大多様性問題にはｍ個の要素を選択するという制約条件があるが、本手法ではこの制約条件を満たさない解空間の探索も行うことで、これまでとは別の探索経路で解探索を行うことができ、従来手法よりもより評価値の良い解を発見できることを示した。また、バイナリー２次計画問題(Quadratic Assignment Problem)に対して、Opposition-Based Learningを組み入れたMemetic Aligotithmにおける局所探索法についての検討を行った。バイナリー2次計画問題は、NP困難な問題に含まれる組み合わせ最適化問題の一つであり、マシンスケジューリング問題やCAD問題など大規模な計算を要する問題の応用例として知られている。本研究では、制約付き近傍やk-opt局所探索法など様々な局所探索を組み入れることにつての検討を行い、k-opt局所探索法を用いることが最も良い結果を得られることを示した。

本研究的目的是为传统无法处理的超大规模组合优化问题开发创新算法，并通过将其应用于各种问题来构建该领域的新范式。今年，我们研究了我们提出的最大多样性问题的初始邻域搜索方法中的局部搜索方法。最大多样性问题是一种组合优化问题，在从给定的n个元素中选择m个元素时，选择的元素具有尽可能多的多样性，在网络设计、VLSI设计等方面有着广泛的应用。称为问题。最大多样性问题有一个必须选择 m 个元素的约束，但我们的方法也会搜索不满足此约束的解空间，这使我们能够使用不同的搜索路径来搜索解，结果表明可以找到。比传统方法具有更好评估值的解决方案。我们还研究了模因算法中的局部搜索方法，该方法结合了针对二元二次规划问题（二次分配问题）的基于反对的学习。二元二次规划问题是NP难问题中包含的组合优化问题之一，被称为需要大规模计算的问题的应用示例，例如机器调度问题和CAD问题。在本研究中，我们研究了结合各种局部搜索（例如约束邻域和 k-opt 局部搜索方法），并表明使用 k-opt 局部搜索方法可以获得最佳结果。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

方形ピースジグソーパズル問題に対するアルゴリズムの検討

方形拼图问题算法的检验

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Rikuto Tazawa;Hiroshi Mori;Fubito Toyama;関航大，高橋慶多，森博志，外山史;星野玲，森博志，外山史;我妻達也，森博志，外山史;有田陸人，森博志，外山史;大島一輝，森博志，外山史;蒋利楠，森博志，外山史;仲谷歩む，高橋慶多，森博志，外山史
通讯作者：
仲谷歩む，高橋慶多，森博志，外山史

超大規模な最大多様性問題に対する初期近傍探索法の改良

超大规模最大多样性问题初始邻域搜索方法的改进

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Rikuto Tazawa;Hiroshi Mori;Fubito Toyama;関航大，高橋慶多，森博志，外山史;星野玲，森博志，外山史;我妻達也，森博志，外山史;有田陸人，森博志，外山史;大島一輝，森博志，外山史
通讯作者：
大島一輝，森博志，外山史

最大多様性問題に対する実行不可能解を用いた局所探索法の検討

最大分集问题不可行解的局部搜索方法研究