Я пытался реализовать генетический алгоритм для сборки фрагментов ДНК в одну последовательность, учитывая только спектр. Мой единственный оператор — Edge Recombination, и я был уверен, что этого достаточно, чтобы получить довольно хороший результат.
Но... я не могу побить 80% (% оптимальной оценки), а экземпляры с 500 фрагментами могут занять до 2 часов (алгоритм останавливается, если за 100 итераций нет улучшения). Я даже реализую это правильно? Я нигде не нашел, что операторы кроссовера должны выбирать элементы, которые лучше соответствуют (перекрытие фрагментов - в большинстве статей это просто случайный выбор), но я реализовал это так, что он выбирает лучший подходящий элемент, и если их много - случайный. Без выбора лучшего он не набирает даже 40%.
Должен ли я реализовать больше кроссоверов? Или это просто не так работает... Или я что-то пропустил? На данный момент я в отчаянии, жду 24 часа для 40 экземпляров, которые простая эвристика (альпинист) может сделать менее чем за 5 секунд...
Вот код (перестановка - это перетасованный спектр - список строк)
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)
