最小増加超距離木問題に対する局所探索アルゴリズム (最適化技法の最先端と今後の展開)

Abstract

超距離木とは根から葉までの距離が全て等しいような枝重み付き根付き木のことである. 超距離木(T, l)に対して, D_{(T, l)}[i, j]によって(T, l)の葉i, j間の距離を表す. Lp-最小増加超距離木問題とは, 相違行列M:Stimes Srightarrow mathbb{R}が与えられたときに, 葉集合がSでありかつM[i, j]leq D_{(T, l)}[i, j](i, jin S)を満たすような超距離木(T, l)の中からVert D_{(T, l)}-MVert_{p}を最小化するものを見出す問題である. Lp-最小増加超距離木問題は, p=inftyの場合は線形時問アルゴリズムが存在するが, Pが有限の場合はNP困難であることが知られている. 本研究では2分木の変形操作に基づいて, Pが有限の場合のLp-最小増加超距離木問題に対する局所探索アルゴリズムを開発した. 2分木の変形操作として系統学においてよく知られているSPR操作及びNNI操作に加えて本研究で導入されるSE操作を用いる. さらに数値実験によってこのアルゴリズムの性能を検証した. その結果, NNI操作を用いる局所探索アルゴリズムは非常に高速ではあるもののその解の品質は満足できるものではなかった. その一方で, SPR操作あるいはSE操作を用いる局所探索アルゴリズムの解の品質はNNI操作を用いるそれよりも高いものの計算時間に関しては改良する必要があるということが明らかになった.