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

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

• 批准号: 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局所探索法を用いることが最も良い結果を得られることを示した。

The purpose of this study is to develop and construct innovative solutions to ultra-large-scale combinatorial optimization problems. This year, we have proposed a maximum diversity problem for the initial proximity search method and the local search method. The maximum diversity problem consists of n elements, m elements, selection of elements, and combination of elements. The optimization problem consists of design and VLSI design. The maximum multiplicity problem consists of m elements, constraints and constraints. This method is used to explore the solution space and explore the solution space. Quadratic Assignment Problem, Opposition-Based Learning, Memetic Aligothm, and Local Discovery are discussed. For example, the second order planning problem, NP difficult problem, group optimization problem, CAD problem, large-scale calculation problem, etc. This study is based on the analysis of the results of the k-opt method.

项目成果

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

方形拼图问题算法的检验

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

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

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

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

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

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

• 发表时间: 2023
• 作者: Rikuto Tazawa;Hiroshi Mori;Fubito Toyama;関航大，高橋慶多，森博志，外山史;星野玲，森博志，外山史
• 通讯作者: 星野玲，森博志，外山史

方形ピースジグソーパズル組み立てアルゴリズムの改良

方块拼图拼装算法的改进

• 发表时间: 2023
• 作者: Rikuto Tazawa;Hiroshi Mori;Fubito Toyama;関航大，高橋慶多，森博志，外山史
• 通讯作者: 関航大，高橋慶多，森博志，外山史

超大規模なバイナリー2 次計画問題に対する初期近傍探索法

超大规模二元二次规划问题的初始邻域搜索方法

• 发表时间: 2022
• 作者: Rikuto Tazawa;Hiroshi Mori;Fubito Toyama;関航大，高橋慶多，森博志，外山史;星野玲，森博志，外山史;我妻達也，森博志，外山史;有田陸人，森博志，外山史
• 通讯作者: 有田陸人，森博志，外山史