DNAアセンブリのための適切なエッジ組換えクロスオーバー

Question

私は、スペクトルのみを与えられた1つのシーケンスにDNAフラグメントを組み立てるための遺伝的アルゴリズムを実装しようとしていました。私の唯一の演算子はEdge Recombinationであり、かなり良い結果を得るには十分だと私は確信していました。

しかし、私は80％（最適スコアの％）を上回ることはできません。また、500個のフラグメントを持つインスタンスは2時間までかかることがあります（100回の反復で改善がない場合、アルゴリズムは停止します）。私はそれを正しく実装していますか？クロスオーバ演算子がよりよく一致する要素（フラグメントの重なり - ほとんどの論文では私たちが選んだもの）を選択すべきところは見つけられませんでしたが、最もマッチするものを選んで実装しました。ランダムなもの。最高のものを選ぶことなく、それは40％も得点しません。

さらにクロスオーバーを実装する必要がありますか？それはどういう仕組みではないのですか...何かが欠けていますか？

- 私は（文字列のリストの順列がシャッフルスペクトルである）のコードがあります...簡単なヒューリスティック（ヒルクライマー）が5秒の下で行うことができます40個のインスタンスの24時間を待って、この時点で

かなり絶望的です

def crossover(g1, g2, arr, ind): # edge recombination operator 
    neigh_list = {} # adjacency list 
    length = len(g1.permutation) # expected length of a child 
    for i, base in enumerate(g1.permutation): # create nodes 
     neigh_list[base] = {g1.permutation[i - 1], g1.permutation[(i + 1) % length]} 
    for i, base in enumerate(g2.permutation): # add neighbours to each node 
     neigh_list[base].add(g2.permutation[i - 1]) 
     neigh_list[base].add(g2.permutation[(i + 1) % length]) 

    # a starting point of a child is a starting point of one of the parents 
    neigh_chosen = [g1.permutation[0], g2.permutation[0]][random.randint(0, 1)] 
    child = [neigh_chosen] 

    while len(child) < length: # run until child has desired length 
     min_length = 5 # each list has lower length than 5 
     min_neigh_list = [] 
     for k in neigh_list: # for every node 
      if neigh_chosen in neigh_list[k]: # remove a chosen fragment from the node 
       neigh_list[k].remove(neigh_chosen) 
     for k in neigh_list[neigh_chosen]: # if a node is a neighbour of previously chosen 
      if len(neigh_list[k]) < min_length: # remember nodes with the fewest neighbours 
       min_length = len(neigh_list[k]) 
       min_neigh_list = [k] 
      elif len(neigh_list[k]) == min_length: 
       min_neigh_list.append(k) 
     del neigh_list[neigh_chosen] # delete list of the chosen node 
     if len(min_neigh_list) > 0: # if the chosen node has any neighbours 
      # get the best match out of neighbours as next 
      max_overlap = overlap(neigh_chosen, max(min_neigh_list, key=lambda x: overlap(neigh_chosen, x))) 
      possibilities = list(filter(lambda x: overlap(neigh_chosen, x) == max_overlap, min_neigh_list)) 
      neigh_chosen = possibilities[random.randint(0, len(possibilities) - 1)] 
     else: 
      # get the best match out of every node as next 
      max_overlap = overlap(neigh_chosen, max(neigh_list, key=lambda x: overlap(neigh_chosen, x))) 
      possibilities = list(filter(lambda x: overlap(neigh_chosen, x) == max_overlap, neigh_list)) 
      neigh_chosen = possibilities[random.randint(0, len(possibilities) - 1)] 
     child.append(neigh_chosen) # add the node to the solution 
    arr[ind] = Gene(child) 

Answer 1

[OK]を、私は非常に簡単なトリックを行うこの1つを解決することができました。問題は、このオペレータが実際に何を行うのか、どこで使うのかを理解することでした。それはDNAアセンブリの問題をやって助けるようにするには、単にそれが動作する理由は、私たちは隣人の最小数のフラグメントを探してされていないので（それが上で重要であるかもしれないです

min_neigh_list = neigh_list[neight_chosen] 
    del neigh_list[neigh_chosen] 

で

for k in neigh_list[neigh_chosen]: # if a node is a neighbour of previously chosen 
     if len(neigh_list[k]) < min_length: # remember nodes with the fewest neighbours 
      min_length = len(neigh_list[k]) 
      min_neigh_list = [k] 
     elif len(neigh_list[k]) == min_length: 
      min_neigh_list.append(k) 
    del neigh_list[neigh_chosen] 

を置き換えます他の種類のグラフ関連の問題！）しかし、最もマッチしたネイバー！

これはかなりの専門家であるので、あなたがここで私は思う（または任意の場所に）答えを得るのに苦労します。この単純な変更:)