平均コストを用いたスイッチ型ブール制御ネットワークの無限水平最適制御.効率的なグラフ理論的アプローチ

Infinite-Horizon Optimal Control of Switched Boolean Control Networks With Average Cost: An Efficient Graph-Theoretical Approach.

• Shuhua Gao
• Changkai Sun
• Cheng Xiang
• Kairong Qin
• Tong Heng Lee

抄録

本研究では、平均コスト基準を持つスイッチドブール制御ネットワークの無限水平最適制御(IHOC)問題を研究しています。この問題の主要な課題は、大規模なネットワークを扱う場合、計算コストが非常に高くなることである。我々は、新しいグラフ理論の観点から、より効率的なアプローチを開発することを試みる。まず、最適状態遷移グラフ(OSTG)と呼ばれる重み付き有向グラフ構造を確立し、そのエッジは、様々な制約条件の下で、与えられた初期状態から到達可能な状態間の各許容状態遷移に対する最適な動作をコード化する。次に、IHOC問題をOSTGにおける最小平均周期(MMC)問題に削減する。最後に、グラフ理論におけるカープのアルゴリズムを用いて、特定のMMCを迅速に見つけることができるアルゴリズムを開発し、状態フィードバックに基づいて最適なスイッチング制御則を構築する。時間複雑性解析の結果、指数関数的な時間で実行されるにもかかわらず、時間効率の点で既存のすべての手法を凌駕することが示された。白血病における16ステート3入力シグナルネットワークをベンチマークとして、その有効性を検証した。その結果、提案されたグラフ理論的アプローチは計算効率が高く、既存の手法に比べて数百倍、数千倍の速度で実行され、実行時間を劇的に短縮できることが示された。このアルゴリズムのPython実装は、https://github.com/ShuhuaGao/sbcn_mmc から入手できます。

This study investigates the infinite-horizon optimal control (IHOC) problem for switched Boolean control networks with an average cost criterion. A primary challenge of this problem is the prohibitively high computational cost when dealing with large-scale networks. We attempt to develop a more efficient approach from a novel graph-theoretical perspective. First, a weighted directed graph structure called the optimal state transition graph (OSTG) is established, whose edges encode the optimal action for each admissible state transition between states reachable from a given initial state subject to various constraints. Then, we reduce the IHOC problem into a minimum-mean cycle (MMC) problem in the OSTG. Finally, we develop an algorithm that can quickly find a particular MMC by resorting to Karp's algorithm in the graph theory and construct an optimal switching control law based on state feedback. The time complexity analysis shows that our algorithm, albeit still running in exponential time, can outperform all the existing methods in terms of time efficiency. A 16-state-3-input signaling network in leukemia is used as a benchmark to test its effectiveness. Results show that the proposed graph-theoretical approach is much more computationally efficient and can reduce the running time dramatically: it runs hundreds or even thousands of times faster than the existing methods. The Python implementation of the algorithm is available at https://github.com/ShuhuaGao/sbcn_mmc.