複数の種(taxon)の遺伝子の塩基列もしくはアミノ酸列をデータとして、そこから系統樹(phylogenetic tree)を構築するアルゴリズムは、距離行列法と、与えられたデータのもとでの各二分木のコストを定義してコスト最小の二分木を求める、という2つのタイプに大別できる。距離行列法(Pairwise Distance Method)としては、UPGMA/WPGMA法(実用にはあまり用いられてない)、及び近隣結合法(Neighbour Joining Method, NJ法)などが知られている。それに対して、初期解から局所探索、つまり受刑探索を繰り返して最適器を求めるときの目的関数の取り方として、最小二乗法、最小進化法、最大節約法(Parsimony)、最尤法(Maximum Likelihood Method)などが知られている。一般に組み合わせ最適化の理論では、これらの樹形探索のような局所探索を繰り返すときには、適当なメタヒューリスティックアルゴリズムを使うとより効率的なアルゴリズムが得られることが知られている。実際には、組み合わせ最適化の分野でメタヒューリスティックアルゴリズムの名の下に以下の3つが知られている(1)遺伝的アルゴリズム(Genetic Algorithm)(2)タブー探索(Tabu Search)(3)進化的アルゴリズムこれらの戦略を系統樹アルゴリズムの樹形探索の部分に適用し、シミュレーションを繰り返してみた結果、タブー探索がもっとも効果的であるという知見を得た。
1 0 0 0 OA ブロッキング型及びアンチブロッキング型整数多面体の類似性についての研究
①:Cornuejols, Guenin and Margotの予想を解くためのスキームを提示し、Cornuejols,Guenin and TuncelのOpen Problemの類似を証明した。当該論文は、Springer monograph(Indean Statistical Institute Series)として出版予定である。②:コードダイアグラムの展開式を用いてTutte polynomialの(x,y)=(2,-1)における値の組合せ論的意味付けを与えた。③:グラフにおける新しいパラメータである安全数を定義し、その様々なグラフ理論的性質および計算量的評価について明らかにした。
- 著者
- 中村 政隆
- 出版者
- 公益社団法人日本オペレーションズ・リサーチ学会
- 雑誌
- 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集
- 巻号頁・発行日
- vol.1999, pp.190-191, 1999-09-20