Я изучаю алгоритмы geneti c и, чтобы лучше понять концепции, я попытался построить алгоритм geneti c с нуля, используя python без использования какого-либо внешнего модуля (только стандартная библиотека и немного из numpy)
Цель состоит в том, чтобы найти целевую строку, поэтому, если я передам ей строку привет и определю 26 символов + пробел, есть 26 ^ 5 возможностей, которые огромны. Таким образом, необходимо использовать GA для решения этой проблемы.
Я определил следующие функции:
Генерируем популяцию : мы генерируем популяцию с заданным размером n и целевым объектом мы генерируем n строку, имеющую len(target) случайных символов, мы вернуть население в виде списка чисел
. Вычислить фитнес-оценку : если символ в позиции i равен символу в позиции i цели, мы увеличиваем счет, вот код:
def fitness(indiv,target):
score = 0
#print(indiv," vs ",target)
for idx,char in enumerate(list(target)):
if char == indiv[idx]:
score += 1
else:
score = 0
return score
Выбор родителей, скрещивание между родителями и формирование новой популяции детей
Вот функция, ответственная за это:
from numpy.random import choice
def crossover(p1,p2):
# we define a crossover between p1 and p2 (single point cross over)
point = random.choice([i for i in range (len(target))])
#print("Parents:",p1,p2)
# C1 and C2 are the new children, before the cross over point they are equalt to their prantes, after that we swap
c = [p1[i] for i in range(point)]
#print("Crossover point: ",point)
for i in range(point,len(p1)):
c.append(p2[i])
#print("Offsprings:", c1," and ", c2)
c = "".join(c)
# we mutate c too
c = mutate(c)
return c
def mutate(ind):
point = random.choice([i for i in range (len(target))])
new_ind = list(ind)
new_ind[point] = random.choice(letters)
return "".join(new_ind)
def select_parent(new_pop,fit_scores):
totale = sum(fit_scores)
probs = [score/totale for score in fit_scores]
parent = choice(new_pop,1,p=probs)[0]
return parent
Я выбираю родителей, вычисляя вероятности каждого индивидуума (индивидуальный балл / общий балл населения), а затем использую взвешенный случайный выбор , чтобы выбрать родителя (это numpy функция ).
Для кроссовера я создаю дочерний элемент c и случайную точку разделения, все символы до этой случайной точки являются первыми родительскими символами, а все символы после точки разделения - это символы родителя.
Кроме того, я определил функцию под названием should_stop, которая проверяет, нашли ли мы цель, и print_best, которая выбирает лучших людей из популяции (самый высокий показатель пригодности).
Затем я создал поиск функция, которая использует все функции, определенные выше:
def find(size,target,pop):
scores = [fitness(ind,target) for ind in pop]
#print("len of scores is ", len(scores))
#good_indiv = select_individuals(pop,scores)
#print("Length of good indivs is", len(good_indiv))
new_pop = []
# corssover good individuals
for ind in pop:
pa = select_parent(pop,scores)
pb = select_parent(pop,scores)
#print(pa,pb)
child = crossover(pa,pb)
#print(type(child))
new_pop.append(child)
best = print_best(new_pop,scores)
print("********** The best individual is: ", best, " ********")
return (new_pop,best)
n = 200
target = "hello"
popu = generate_pop(n,target)
#find(n,target,popu)
for i in range(1000):
print(len(popu))
data = find(n,target,popu)
popu = data[0]
print("iteration number is ", i)
if data[1] == target:
break
Проблема Проблема в том, что для создания приветствия требуется слишком много итераций (чем 200 итераций, большинство время), хотя в этом примере это занимает всего несколько итераций: https://jbezerra.github.io/The-Shakespeare-and-Monkey-Problem/index.html
Конечно, проблема не закодирована таким же образом, я использовал python и процедурный способ код вещи, но логика c то же самое. Так что я делаю не так?