並列タイトル等最適化問題への動力学系アプローチ:分岐による最適化
タイトル(掲載誌)航空宇宙技術研究所特別資料 = Special Publication of National Aerospace Laboratory
一般注記航空宇宙技術研究所 17-19 Jan. 2000 東京 日本
National Aerospace Laboratory 17-19 Jan. 2000 Tokyo Japan
システム設計の計算理論は、最適化理論である。最適化問題は、制約のある目的関数を最小にするとして定式化される。最適化問題の発見的方法の基本的考えは、目的関数と制約式からなるエネルギー関数の勾配ベクトル場として変数の動力学系が導かれる。近似解は、この動力学系の平衡点として得られる。著者は最適化問題の決定法についての1つのモデルを提案した。動力学系として、勾配系の代わりに反復系を用いた。アニーリング・スケジュールを、反復方程式の分岐特性に基づいて決定した。本稿では、反復方程式の基本的特徴を簡単に説明し、最適化について提案した方法を数値例により説明した。反復方程式は、変数の微分が状態変数に比例する。ここでは、この反復方程式の分岐特性を用いた最適化法を、組み合わせ最適化問題1つの例である2次割当て問題に関して説明した。この方法は、また、非線形最適化問題についても適用できるものである。
The computational theory of system design is a theory of optimization. The optimization problem is formulated as the minimization of the function in question subject to constraints. The basic heuristic method is that a dynamic system of variables is constructed in the form of a gradient vector field of an energy function from the function in question and its constraints. The approximate solution of the problem is then obtained as an equilibrium point of the dynamic system. A different model is proposed for characterizing dynamic system optimization problems. As the dynamic system, a recurrent system was adopted instead of a gradient system. The annealing schedule is determined based on the bifurcation characteristics of the recurrent equations. In this paper, the basic characteristics of the recurrent equation are briefly explained and the proposed method of optimization is explained by giving numerical examples. The recurrent equation is one where the derivative of the variables describing a situation is proportional to those variables themselves. Here the proposed method utilizing the bifurcation characteristics of a recurrent equation is applied to the quadratic assignment problem, an example of the combinatorial optimization problem. The method, however, can be also applied to a nonlinear optimization problem.
資料番号: AA0028638009
レポート番号: NAL SP-49T
一次資料へのリンクURLhttps://jaxa.repo.nii.ac.jp/?action=repository_action_common_download&item_id=41425&item_no=1&attribute_id=31&file_no=1
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース(IRDB)(機関リポジトリ)
提供元機関・データベース宇宙航空研究開発機構 : 宇宙航空研究開発機構リポジトリ