Probabilistic Analysis of Meta-heuristics Algorithm from theViewpoint of Theoretical Approach

理论方法视角下元启发式算法的概率分析

• 批准号: 17510113
• 负责人: KAJI Taichi
• 金额: $ 2.42万
• 依托单位: Otaru University of Commerce
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17510113/
• 关键词: メタヒューリスティックス; 組合せ最適化問題; 確率的解析; AR(1)プロセス; 近傍構造; Local Search; 最適化問題; コーシー分布; ant system; Simulated Annealing; Tabu Search; アルゴリズム; メタヒューリステイックス; 理論的解析; N-Kモデル; Local search

組合せ最適化問題は利用価値の高い問題であるが計算困難な問題でもある。これらの問題に対して、近似解を実用時間内で求める遺伝アルゴリズムなどのメタヒューリスティックスアプローチが有効な結果をもたらしている。しかし、これらのアルゴリズムの優劣などは数値実験などにより判別され経験的な評価の域をでていない。そこで、本研究では確率モデルを構成し理論的かつ客観的に評価、分析を可能とする手法に関して研究を行った。

组合优化问题非常有用，但也很难计算。对于这些问题，在实际时间内找到近似解决方案的遗传学方法（例如遗传算法）提供了有效的结果。但是，这些算法的优越性和自卑是通过数值实验等确定的，而不是经验评估。因此，在这项研究中，我们对构建概率模型的方法进行了研究，并实现了理论和客观评估和分析。

项目成果

組合せ最適化問題における近傍集合の特性

组合优化问题中邻域集的特征

• 发表时间: 2006
• 期刊: オペレーションズ・リサーチ学会秋季研究発表会
• 作者: Kaji;T.;加地太一;加地太一;加地;加地太一;加地;加地
• 通讯作者: 加地

組合せ最適化問題に対する近傍集合の解析

组合优化问题的邻域集分析

• 发表时间: 2007
• 期刊: 商学討究(小樽商科大学) Vol.58, No.1
• 作者: Kaji;T.;加地太一
• 通讯作者: 加地太一

メタヒューリスティクスと応用

元启发法及其应用

• 发表时间: 2007
• 作者: 相吉英太郎;安田恵一郎編著
• 通讯作者: 安田恵一郎編著

情報学入門

信息学导论

• 发表时间: 2006
• 作者: 大内;岡部;栗原編;加地共著
• 通讯作者: 加地共著

連続最適化問題に対するコーシー分布型SA によるアプローチ

柯西分布式 SA 方法解决连续优化问题

• 发表时间: 2009
• 期刊: 情報処理学会研究報告(アルゴリズム研究会) Vol.2009, No.18
• 作者: 川田泰章;加地太一
• 通讯作者: 加地太一