Мутация быстрого эволюционного алгоритма: мутация n случайных генов вместо оценки каждого гена - PullRequest
Новая
       54

Мутация быстрого эволюционного алгоритма: мутация n случайных генов вместо оценки каждого гена

0 голосов
/ 17 июня 2019

Я пытаюсь оптимизировать код для моего генетического алгоритма. ДНК в настоящее время представляет собой словарь для увеличения скорости поиска для расчетов пригодности, но его можно легко заменить на массив.

Предполагается, что скорость мутации составляет 1 / л, L - длина ДНК.

Это решение работает, но довольно медленно: 

# Iterate through genome, flip a gene with a probability of 1/L
def mutate(self):
      self.dna = dict(
        [(i, flip(self.dna[i])) if random.randint(0,num_genes) < 1 
        else (i, self.dna[i]) for i in range(num_genes)]
        )

Это решение примерно в два раза быстрее, но по некоторым причинам оно дает гораздо худшие результаты: 

# Select n number of genes calculated by 1/L, then change n random genes
def mutate(self):
      num_mutations = sum(np.random.choice([0,1], num_genes, p=[(num_genes-1)/num_genes, 1/num_genes]))
      for i in np.random.choice(num_genes-1, num_mutations):
        self.dna[i] = flip(self.dna[i])

Насколько я могу судить, они мутируют одинаковое количество генов, и результат должен быть одинаковым. 10 прогонов обоих с набором случайных семян показывают, что последний подход, однако, приводит к гораздо худшим результатам.

Почему второй подход приводит к ухудшению работоспособности днк? Как эти подходы отличаются по своему результату?

Спасибо за любую помощь.

Ответы [ 2 ]

1 голос
/ 18 июня 2019

Сначала: векторизация

Нет смысла использовать dict, когда ваши индексы являются целыми числами - поиск целочисленного индекса всегда быстрее, чем использование хеш-таблицы. Также вы можете векторизовать это используя numpy - сделайте ваш self.dna массив numpy вместо списка или dict, что может привести к ускорению в 10-100 раз. 

def flip(x):  # x is a vector of genes, lets a binary array here
    return ~x
mutation_mask = np.random.rand(n_genes)<1./len(self.dna)
self.dna[mutation_mask] = flip(dna[mutation_mask])

Секунд: почему ваши два алгоритма отличаются:

Не знаю, похоже, они должны быть одинаковыми по статистике. Единственное, что я могу подумать, это то, что во втором случае вы изменяете self.dna вместо self.dna[i]=... вместо того, чтобы переназначать self.dna=..., поэтому любая другая область в коде, имеющая старый self.dna, будет иметь свои копия изменилась тоже во втором случае. Вы можете исправить это, вставив self.dna = self.dna.copy() перед циклом for во втором примере.

1 голос
/ 17 июня 2019

Сложность связана с несколькими случайными вызовами: вы вызываете его для каждого гена.

Ваш второй пример делает то же самое, но на этот раз они все вызываются в одной и той же функции.

Способ радикально улучшить производительность - уменьшить количество случайных вызовов. Для этого вы можете использовать некоторую математику, чтобы заранее узнать, сколько мутаций получит геном, формула следующая 

P(L, n, p) # probability of modifying n-times a genome of size L with a succes p (here p is 1/L)
P(L, n, p) = binomial(n, L) * p**n * (1-p)**(L-n)

Если вы не слишком знакомы с математикой, вот функция python, которая сделает это за вас: 

def binomial(n, k):
    if 0 <= k <= n:
        ntok = ktok = 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n; ktok *= t; n -= 1
        return ntok // ktok
    else: return 0

def P(L, n, p): return binomial(L, n) * p**n * (1-p)**(L-n)

И теперь вы можете предварительно рассчитать это и сохранить его в списке: 

proba = [P(L, i, 1/L) for i in range(0, L+1)]

Также я рекомендую частично суммировать его для более легкого использования случайных чисел 

probaS = [sum(proba[:k]) for k in range(0, L+1)] + [1]

Теперь вы можете генерировать только одно случайное число, и вы будете напрямую знать, сколько мутаций вам нужно для этого генома: 

r = random()
i = 0
while r > probaS[i]: i += 1

В конце цикла i-1 сообщит вам, сколько требуется мутаций.

Теперь вам просто нужно случайным образом выбрать другую часть генома, и это сделано! Вы перешли от L случайных звонков в среднем до 2 или 3.

В базовом тесте, который я провел, сложность времени для L = 50 и 100 000 геномов возросла с 5,74 до 196 мс, так что примерно в 30 раз быстрее.

Мой ответ немного технический, поэтому не стесняйтесь спрашивать, если он не был ясен.

...