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
• 作者: 藤田実沙;木村貴幸;藤原寛太郎;池口徹
• 通讯作者: 池口徹

枝媒介中心性を使用したShortest Path Heuristic

使用分支介数中心性的最短路径启发式

• 发表时间: 2019
• 作者: Dragomir N. Nenchev;Atsushi Konno;Teppei Tsujita;山崎 凌，島田 裕，池口 徹;Ryota Nomura，Ying-Zong Liang，Kenji Morita，Kantaro Fujiwara and Tohru Ikeguchi;Tohru Ikeguchi，Yutaka Shimada，Kantaro Fujiwara，Sakura Rai，Toshihiro Kobayashi;池口 徹;藤田 実沙，木村 貴幸，池口 徹
• 通讯作者: 藤田 実沙，木村 貴幸，池口 徹