权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Mathematical Analysis for Metaheuristics and its Application

元启发式数学分析及其应用

基本信息

批准号：
22K04593
负责人：
加地太一
金额：
$ 2.41万
依托单位：
Otaru University of Commerce
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

組合せ最適化問題は，スケジューリング問題，配置問題など様々な意思決定問題で利用されている．これらの問題を解くための手法としてメタヒューリスティクスと呼ばれる一群の近似解法がある．そしてメタヒューリスティクスが経験的に良い解を導き出すことは多くの研究でも示されている．しかし，“なぜ，メタヒューリスティクスが良い解を導き出してくれるのか？” は一つの謎でもある．そこで本研究では，組合せ最適化問題の解空間に特徴的な性質が存在する仮定のもと，その解空間および解の探索過程を数理的にモデル化し，求まる近似解のコスト値などを推定する．それによりメタヒューリスティクスの各手法の性能を理論的（数理的）に解析し，その能力の謎を解き明かすことを目指す．そのために，申請者は，組合せ最適化問題の解空間における解のランダムウォークにおいて，現在の解のコスト値が一つ前のコスト値に依存するAR(1)プロセスとなる性質を示した．その性質を利用し解の近傍の解析を行い，近傍の統計量を汎用的に導き出していく．統計量とは，近傍の分布構造を表すパラメータ，近傍の最小コスト値の推定値である. この近傍の統計量が推定できれば，メタヒューリスティクス自体の性能を，近傍の統計量に基づき，問題に依存することなく理論的に導き出すことが可能となるであろう．本年度は，多くの問題に対して解のランダムウォークがこのAR(1)の性質を満足しているか調査し，AR(1)としてモデル化し近傍の統計量を導き出すことが可能であるかの検証をおこなった．この特徴が多くの問題に見出すことが出来れば，特定の問題および近傍に限ることなく多くの問題に利用がはかれることとなる．すなわち，解空間がAR(1)を満足するという前提から，様々な問題に利用可能である数理的モデルが構築され，汎用的に適用可能な理論的解析の世界を築くことが可能となる．

Combinatorial optimization problems are optimization problems, allocation problems, rational decision problems, and utilization problems. A group of approximate solutions to the problem. The best way to solve this problem is to find out how to solve it. "What's wrong with you?"は一つの谜でもある. In this paper, we study the existence of the characteristic properties of the solution space of combinatorial optimization problems, the mathematical transformation of the solution space and the exploration process of the solution, and the estimation of the approximate solution. The performance of each method is analyzed theoretically (mathematically), and the mystery of each method is solved clearly. For example, the applicant may indicate the property of AR(1), which depends on the solution space of the combinatorial optimization problem and the value of the solution before it. The properties of the system can be used to analyze the solution of the problem, and the statistics of the problem can be used to derive the problem. The statistical quantity and the distribution structure of the neighborhood are expressed in terms of the minimum value of the neighborhood and the estimated value. The statistics of the neighborhood are estimated, and the properties of the neighborhood are estimated. The statistics of the neighborhood are based on the problem of dependence. During the year, there were many problems related to the investigation of the properties of AR (1), AR(1) and AR(1), and the statistical quantities of AR(1) and AR(1) were derived. The characteristics of the problem are: see the problem, see the problem. The solution space AR(1) is sufficient to construct a mathematical solution using the possibility, and the solution space AR (1) is generally applicable to the theoretical solution of the problem.