Я учусь, как использовать генетические алгоритмы.Я нашел это (довольно четко) простое упражнение, которое научило меня, как это сделать (https://blog.sicara.com/getting-started-genetic-algorithms-python-tutorial-81ffa1dd72f9).
). Цель этого упражнения - взломать «пароль», который указан взатем выполняет весь алгоритм. Сначала он делает набор случайных строк символов длиной «пароля».
def generateOrganism(length):
possible_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
i = 0
result = ""
while i < length:
i += 1
character = random.choice(possible_chars)
result += character
return result
def generatePopulation(sizePopulation, password):
population = []
print('Starting Algorithm')
i = 0
while i < sizePopulation:
population.append(generateOrganism(len(password)))
i += 1
return population
Затем пригодность (определяется тем, насколько близко слово кзатем проверяется пароль каждого слова, как показано:
def fitness (password, test_word):
if (len(test_word) != len(password)):
print("taille incompatible")
return
else:
score = 0
i = 0
while (i < len(password)):
if (password[i] == test_word[i]):
score+=1
i+=1
return score * 100 / len(password)
И это вызывается функцией computePerfPopulation, которая составляет словарь слова и его пригодность.
def computePerfPopulation(population, password):
populationPerf = {}
for individual in population:
populationPerf[individual] = fitness(password, individual)
if fitness(password, individual) == 100:
print("EUREKA, WE HAVE CRACKED THE PASSWORD. IT'S '", individual, "'")
return 'Done'
print(populationPerf)
return sorted(populationPerf.items(), key = operator.itemgetter(1), reverse = True)
Тогдаэтот словарь передается в функцию selectFromPopulation, которая выбирает слова с наилучшей пригодностью и несколько случайных слов для «размножения».
def selectFromPopulation(populationSorted, best_sample, lucky_few):
nextGen = []
for i in range(best_sample):
nextGen.append(populationSorted[i][0])
for i in range(lucky_few):
nextGen.append(random.choice(populationSorted)[0])
random.shuffle(nextGen)
return nextGen
Затем слова объединяются с помощью следующих функций. Этогде возникает проблема.
def createChildren(breeders, num_of_children):
nextPopulation = []
for i in range(0, len(breeders) // 2):
for j in range(0, num_of_children):
nextPopulation.append(createChild(breeders[i], breeders[len(breeders) -1 -i]))
print(nextPopulation)
print(len(nextPopulation))
return nextPopulation
def createChild(individual1, individual2):
child = ""
for i in range(len(individual1)):
if (int(100) * random.random()) < 50:
child += individual1[i]
else:
print(i)
print(individual2)
child += individual2[i]
return child
Тогда некоторые случайные слова могут быть видоизменены с помощью функции ниже, но это не совсемВАЖНО.Затем все это повторяется до тех пор, пока пароль не будет получен
def mutatePopulation(population, chance_mutate): # population is a list
for i in range(len(population)):
if int(random.random() * 100) < chance_mutate:
population[i] = mutateWord(population[i])
return population
def mutateWord(word):
possible_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
index_mods = int(random.random() * len(word))
if index_mods == 0:
word = random.choice(possible_chars) + word[1:]
print(word)
else:
word = random.choice(possible_chars) + word[index_mods+1:]
return word
Иногда весь проект работает так, как предполагалось, и «пароль» не найден.Но иногда я получаю следующую ошибку:
Traceback (most recent call last):
File "main.py", line 146 in <module>
project(100, 'lol' 10, 10, 5, 5)
File "main.py", line 137 in projcet
remakePopulation = createChildren(newBreeders, num_of_child)
File "main.py", line 33 in createChildren
nextPopulation.append(createChild(breeders[i], breeders[len(breeders) - 1 - 1]))
File "main.py", line 49, in createChild
child += individual2[i]
IndexError: string index out of range
Когда я исследовал проблему, я начал распечатывать список, созданный функцией createChildren, так как она делала это (я приведу полный код проекта ниже) и заметил, что иногда (во втором цикле или выше, никогда в первом) некоторые слова будут один или два символа. Я подозреваю, что это потому, что когда язацикливаясь снова, я вставляю новую популяцию в функцию computePerfPopulation, и новая популяция не имеет такой же размер, как исходная, отбрасывая индексы?(Надеюсь, это имело смысл)
Я понятия не имею, что вызывает проблему, и был бы очень признателен, если бы кто-то мог сказать мне, что происходит.(Я знаю, что это давно затянуто, но терпите меня) Кроме того, если у вас есть какие-либо указания по улучшению этого кода, и если бы вы могли дать мне хороший ресурс для реализации генетического алгоритма, я был бы очень признателен.
(Если вы возьмете весь этот код здесь и запустите его, после нескольких попыток он должен показать вам ошибку и т.п.) Вот полный код проекта:
import random
import operator
def mutatePopulation(population, chance_mutate): # population is a list
for i in range(len(population)):
if int(random.random() * 100) < chance_mutate:
population[i] = mutateWord(population[i])
return population
def mutateWord(word):
possible_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
index_mods = int(random.random() * len(word))
if index_mods == 0:
word = random.choice(possible_chars) + word[1:]
print(word)
else:
word = random.choice(possible_chars) + word[index_mods+1:]
return word
def createChildren(breeders, num_of_children):
nextPopulation = []
for i in range(0, len(breeders) // 2):
for j in range(0, num_of_children):
nextPopulation.append(createChild(breeders[i], breeders[len(breeders) -1 -i]))
print(nextPopulation)
print(len(nextPopulation))
return nextPopulation
def createChild(individual1, individual2):
child = ""
for i in range(len(individual1)):
if (int(100) * random.random()) < 50:
child += individual1[i]
else:
print(i)
print(individual2)
child += individual2[i]
return child
def selectFromPopulation(populationSorted, best_sample, lucky_few):
nextGen = []
for i in range(best_sample):
nextGen.append(populationSorted[i][0])
for i in range(lucky_few):
nextGen.append(random.choice(populationSorted)[0])
random.shuffle(nextGen)
return nextGen
def computePerfPopulation(population, password):
populationPerf = {}
for individual in population:
populationPerf[individual] = fitness(password, individual)
if fitness(password, individual) == 100:
print("EUREKA, WE HAVE CRACKED THE PASSWORD. IT'S '", individual, "'")
return 'Done'
print(populationPerf)
return sorted(populationPerf.items(), key = operator.itemgetter(1), reverse = True)
def generateOrganism(length):
possible_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
i = 0
result = ""
while i < length:
i += 1
character = random.choice(possible_chars)
result += character
return result
def generatePopulation(sizePopulation, password):
population = []
print('Starting Algorithm')
i = 0
while i < sizePopulation:
population.append(generateOrganism(len(password)))
i += 1
return population
def fitness(password, test_word): # fitness function of the algorithm
if len(test_word) != len(password):
badFit = 0.0
return badFit
else:
score = 0
i = 0
while i < len(password):
if password[i] == test_word[i]:
score += 1
i += 1
if test_word == password:
print("SUCCESS")
fit = (score * 100) / len(password)
return fit
def project(population_size, password, best_sample, lucky_few, num_of_child, chance_of_mutation):
password = str(password)
population = generatePopulation(population_size, password)
populationSorted = computePerfPopulation(population, password)
#print(computePerfPopulation(population, password))
breeders = selectFromPopulation(populationSorted, best_sample, lucky_few)
nextPopulation = createChildren(breeders, num_of_child)
nextGeneration = mutatePopulation(nextPopulation, chance_of_mutation)
while True:
i = 1
newPopulationSorted = computePerfPopulation(nextGeneration, password)
if newPopulationSorted == 'Done':
break
newBreeders = selectFromPopulation(newPopulationSorted, best_sample, lucky_few)
remakePopulation = createChildren(newBreeders, num_of_child)
nextGeneration = mutatePopulation(remakePopulation, chance_of_mutation)
print(nextGeneration)
print(len(nextGeneration))
input('Press enter to continue')
i += 1