- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on June 30, 2025】Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Reducing Crossovers in Reconciliation Graphs with Extremal Optimization
Bibliographic Information
- Other Title
-
- Extremal Optimization による調停グラフの交差数減少
- Extremal Optimization ニ ヨル チョウテイ グラフ ノ コウサスウ ゲンショウ
Search this article
Description
系統樹を比較する手法の1 つとして調停が提案されている.調停では,系統樹を順序木と見なし,2 つの順序木を向き合わせた調停グラフを作成する.調停を潤滑に進めるためには,順序木の葉節点間に交差がないか,もしくはできるだけ交差が少ない調停グラフを作成する必要がある.本論文では,Extremal Optimization(EO)による調停グラフの交差減少を提案する.EO を適用するにあたり,EO に対して,(1)ルーレット選択により状態遷移の候補となる構成要素を選択する,(2)複数の近傍解中の最良解を次世代の解とする,という2 つの改良を加えた.評価実験の結果,提案手法による調停グラフの交差数減少の方がEO と比較して優れていることを確認した.また,タブーサーチ,SA や遺伝的プログラミングを使用した手法よりも良い結果を求めることができることを確認できた.
The reconciliation is a one of techniques for comparing phylogenetic trees. In the reconciliation,a phylogenetic tree is considered to be an ordered tree, order trees are made to be opposite, and the reconciliation graph is made. There is no intersection between leaf nodes to advance reconciliation to lubrication or it is necessary to make reconciliation graph where intersection is a little. This paper proposes the reducing crossovers in reconciliation graphs with Extremal Optimization (EO). There are two characteristics in the proposed method. The construct which serves as a candidate of a change state by roulette selecting is chosen. The best solution in two or more neighborhoods is chosen as the next solution. The experimental results show that the proposed method is excellent as compared with EO, tabu search, SA and GP.
Journal
-
- 情報処理学会論文誌数理モデル化と応用(TOM)
-
情報処理学会論文誌数理モデル化と応用(TOM) 49 (SIG4(TOM20)), 105-116, 2008-03-15
情報処理学会
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050845762821857664
-
- NII Article ID
- 110006684622
-
- NII Book ID
- AA11464803
-
- ISSN
- 18827780
- 03875806
-
- NDL BIB ID
- 9421124
-
- Text Lang
- ja
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- NDL Search
- CiNii Articles
- KAKEN