Solving the Steiner tree problem in graphs using the chaotic neural network

使用混沌神经网络解决图中的斯坦纳树问题

• 批准号: 18J10671
• 负责人: 藤田 実沙
• 金额: $ 1.22万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-25 至 2020-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18J10671/
• 关键词: カオス; ニューラルネットワーク; タブーサーチ; 組合せ最適化; グラフ的シュタイナー木問題

グラフ的シュタイナー木問題は，電子回路の自動配線や省エネルギーな通信網・電力網の設計などへの応用が期待されている重要な組合せ最適化問題の一つである．グラフ的シュタイナー木問題はNP困難な組合せ最適化問題であり，厳密に最適な解を現実的な時間で求めるのは難しいと考えられている．そこで本研究は，グラフ的シュタイナー木問題に対する効率的な近似解法を開発することを目的とする．近年，巡回セールスマン問題や二次割当問題などの様々な組合せ最適化問題に対して，カオスニューラルネットワークが効率的な解探索を実現できることが知られている．このことから昨年度は，カオスニューラルネットワークを用いたグラフ的シュタイナー木問題の解法を開発した．また，数値実験により，カオスニューラルネットワークが有力な従来手法の一つであるタブーサーチよりもグラフ的シュタイナー木問題に対して高い解探索性能を発揮することを確認した．本年度は，カオスニューラルネットワークのどのような特徴が効率的な解の発見に寄与するのかを明らかにすべく，解探索中の目的関数値の変化の時系列を解析した．カオスニューラルネットワークとタブーサーチの結果を比較したところ，カオスニューラルネットワークのほうが多様な目的関数値の解に移動していることが分かった．このことから，グラフ的シュタイナー木問題の解法としては，様々な目的関数値の解に積極的に移動することが，より良い解の発見に寄与すると考えられる．

图形施工树问题是重要组合优化问题之一，预计将应用于电子电路的自动接线并设计节能通信和电网。图形施塔者树问题是一个难以NP的组合优化问题，被认为很难在现实的时间内找到精确的最佳解决方案。因此，这项研究旨在为图形施塔树问题开发有效的近似解决方案。近年来，众所周知，混乱的神经网络可以有效地寻找解决方案，以解决各种组合优化问题，例如旅行推销员问题和二次分配问题。这就是为什么去年我们使用混乱的神经网络为图形施泰纳树问题开发了解决方案的原因。此外，数值实验证实，混乱的神经网络比图形施泰纳树问题表现出更好的解决方案搜索性能，而这是最强大的常规方法之一。今年，我们分析了解决方案搜索过程中目标函数值变化的时间序列，以阐明混乱的神经网络的特征有助于有效的解决方案发现。在比较混乱的神经网络和禁忌搜索的结果时，发现混乱的神经网络转移到了各种目标函数值的解决方案。因此，人们认为，作为解决图形施泰纳树问题的解决方案，积极地朝着各种目标函数值的解决方案进行运动有助于发现更好的解决方案。

项目成果

Solving the Steiner tree problem in graphs by chaotic search

通过混沌搜索解决图中的斯坦纳树问题

• DOI: 10.1587/nolta.11.90
• 发表时间: 2020
• 期刊: Nonlinear Theory and Its Applications, IEICE
• 作者: Misa Fujita;Takayuki Kimura;and Touru Ikeguchi
• 通讯作者: and Touru Ikeguchi

Solving the Steiner Tree Problem in Graphs Using the Key-Path Based Neighborhood with the kth Shortest Path

使用基于关键路径的邻域和第 k 个最短路径解决图中的 Steiner 树问题

• 发表时间: 2018
• 期刊: Proceedings of the 2018 International Symposium on Nonlinear Theory and its Applications (NOLTA2018)
• 作者: Akiyo Natsubori;Iku Tsustui-Kimura;Hiroshi Nishida;Youcef Bouchekioua;Hiroshi Sekiya;Motokazu Uchigashima;Masahiko Watanabe;Alban de Kerchove d'Exaerde;Masaru Mimura;Norio Takata;and Kenji Tanaka;Misa Fujita，Takayuki Kimura，Kantaro Fujiwara，Tohru Ikeguchi
• 通讯作者: Misa Fujita，Takayuki Kimura，Kantaro Fujiwara，Tohru Ikeguchi

グラフ的シュタイナー木問題に対するタブーサーチとカオスサーチの探索の多様性について

图解斯坦纳树问题的禁忌搜索与混沌搜索的多样性

• 发表时间: 2018
• 作者: 藤田実沙;木村貴幸;池口徹
• 通讯作者: 池口徹

グラフ的シュタイナー木問題に対する複数の最短経路を使用した局所探索法

使用多条最短路径的局部搜索方法解决图形斯坦纳树问题

• 发表时间: 2018
• 作者: 藤田実沙;木村貴幸;藤原寛太郎;池口徹
• 通讯作者: 池口徹

異なる不応性を有するニューラルネットワークによるグラフ的シュタイナー木問題の解探索性能の比較

使用具有不同耐火材料的神经网络对图形 Steiner 树问题的解搜索性能进行比较

• 发表时间: 2018
• 期刊: 電子情報通信学会 技術研究報告
• 作者: Anan M.;K. Yuge;K. Hamada;藤田 実沙，木村 貴幸，池口 徹
• 通讯作者: 藤田 実沙，木村 貴幸，池口 徹