適合度近似方法その２

次のようなツリーがあったとき，遺伝子が1010を検索したい場合，



まず，101まで探索を進めてNULLとなる．前回の探索同様に，その場合には失敗したビットの逆を探索する．


100に探索を進め，最後に1010とハミング距離の近い1000を選択し，適合度50を返す．

次に2つ目の個体の探索を行う．探索は知りたい遺伝子を中心にして選択された遺伝子とツリーの反対の位置を目指す．
1010に対して
1000が見つかったので探す目標は
1110となる．



したがってこのツリーの場合は赤の線をたどることになる．



近似値の求め方は得た適合度とハミング距離によって行う．
1010と1000はハミング距離が1
1010と1110もハミング距離は1となるので計算式は

50×1/2 + 90×1/2 = 70

となる．

計算式は

である．
先ほどの場合は簡単に適合度が見つかったが，2つ目の目標とする遺伝子が見つからなかった場合は1つ目の適合度を見つけるの同じ方法で検索を進めていくことになる．具体的に次のようなツリーの場合には，



まず，1つ目は同様なので50が見つかる．2つ目を探す際に，11から先のノードが無いため，探索を2つ上に上げて，0の方向の探索を始める．この場合でもハミング距離が近くなるように探索を進めるので，まずは001を探索する．



001が見つからないので，000を検索しこちらも失敗する．
そこで探索を1つ上に上げて，



01のノードのたんさくを行う．ノードがあるため順調に探索が進み，0110が見つかる．適合度は30であった．



この場合の近似値は
1010に対し1000でハミング距離1
1010に対し0110でハミング距離2なので，
50×2/3+ 30×1/3 = 43.33333となる．

さらにこの場合でも2つ目の適合度が見つけられない場合は，
以下のようになる．ツリーは下図であるとする．



まず適合度50が見つかる．



次に2つ目の探索を行うがすべて失敗する．







すべて失敗した場合は，1つ目の遺伝子情報のそばで探索を行えていない部分の検索を行う．
まず，はじめに探索を行った部分は検索したい遺伝子を中心にして見つけた遺伝子と対象になる部分から検索を開始したため，探していない部分が残っている．
先ほどの場合であると，適合度が60となっている1001の部分がそうなる．




これにより
1010に対し1000でハミング距離1
1010に対し1001でハミング距離2で
適合度は
50×2/3 + 60×1/3 = 53.333･･･となる．