Czy ten fragment kodu jest algorytmem genetycznym? - python, algorytm, python-3.x, algorytm genetyczny

Próbuję nauczyć się genetycznego algorthms i rozwoju AI i skopiowałem ten kod z książki, ale nie wiem, czy jest to właściwy algorytm genetyczny. Oto kod (main.py):

import random

geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,1234567890-_=+!@#$%^&*():"[]""
target = input()

def generate_parent(length):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
parent = ""
for i in genes:
parent += i
return parent

def get_fitness(guess):
total = 0
for i in range(len(target)):
if target[i] == guess[i]:
total = total + 1
return total
"""
return sum(1 for expected, actual in zip(target, guess)
if expected == actual)
"""

def mutate(parent):
index = random.randrange(0, len(parent))
childGenes = list(parent)
newGene, alternate = random.sample(geneSet, 2)
if newGene == childGenes[index]:
childGenes[index] = alternate
else:
childGenes[index] = newGene
child = ""
for i in childGenes:
child += i

return child

random.seed()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
print(bestParent)

while True:
child = mutate(bestParent)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
print(str(child) + "t" + str(get_fitness(child)))
if childFitness >= len(bestParent):
break
bestFitness = childFitness
bestParent = child

Widziałem, że ma funkcję fitness ifunkcja mutacji, ale nie generuje populacji i nie rozumiem dlaczego. Zrozumiałem, że algorytm genetyczny wymaga generacji populacji i przejścia od najlepszych członków populacji do nowego pokolenia. Czy to właściwy algorytm genetyczny?

Odpowiedzi:

Chociaż istnieje wiele niejednoznacznych definicji w dziedzinie sztucznej inteligencji, rozumiem, że:

1. Na algorytm ewolucyjny (AE) jest algorytmem, który ma rozwiązanie (zestawy) i jakoś je mutuje (krzyżowanie jest tutaj również postrzegane jako „mutujące”), ostatecznie otrzymujesz lepsze rozwiązanie (rozwiązania).

2. ZA algorytm genetyczny (GA) popiera koncepcję a crossover gdzie dwa lub więcej „rozwiązań” tworzy nowe rozwiązania.

Ale terminy są czasami mieszane. Pamiętaj jednak, że zwrotnica z pewnością nie jest jedynym sposobem na tworzenie nowych osób (istnieje więcej sposobów niż lepsze algorytmy genetyczne do tworzenia lepszych rozwiązań), takich jak:

• Symulowane wyżarzanie (SA);
• Tabu Search (TS);
• ...

Ale, jak powiedziano wcześniej, zawsze jest wiele dyskusji na temat tego, co naprawdę oznaczają terminy, a większość prac dotyczących probabilistycznej optymalizacji kombinatorycznej jasno określa, co one oznaczają.

Więc zgodnie z powyższą definicją, twojaprogram jest algorytmem ewolucyjnym, ale nie genetycznym: zawsze ma populację jednego po każdej iteracji. Ponadto twój program akceptuje tylko nowe dziecko, jeśli jest lepsze niż jego rodzic, co czyni go nowym Lokalne wyszukiwanie (LS) algorytm. Problem z lokalnymi algorytmami wyszukiwania polega na tym, że - jeśli przestrzeń mutacji niektórych / wszystkich rozwiązań jest podzbiorem przestrzeni rozwiązania - lokalne algorytmy wyszukiwania mogą utknąć na zawsze w lokalnym optimum. Nawet jeśli tak nie jest, mogą utknąć w lokalnym optymale na bardzo długi czas.

Tutaj nie ma problemu, ponieważ są Nie lokalne optima (ale jest to oczywiście łatwy problem). Bardziej trudne (i interesujące) problemy zwykle mają (wiele) lokalnych optymów.

Lokalne wyszukiwanie nie jest złą technikąwspółpracuje z innymi technikami, które pomagają ponownie wydostać system z lokalnego optimum. Inne techniki ewolucyjne, takie jak symulowane wyżarzanie, przyjmą gorsze rozwiązanie z małym prawdopodobieństwem (w zależności od tego, o ile gorsze jest rozwiązanie i jak daleko jesteśmy w procesie ewolucyjnym).