Uczę się o algorytmach genetycznych i aby lepiej zrozumieć koncepcje próbowałem zbudować algorytm genetyczny od podstaw w Pythonie bez użycia zewnętrznego modułu (tylko standardowa biblioteka i trochę numpy)

Celem jest znalezienie ciągu docelowego, więc jeśli dam mu ciąg hello i zdefiniuję 26 znaków + spacja, istnieje 26 ^ 5 możliwości, co jest ogromne. Stąd potrzeba użycia AH do rozwiązania tego problemu.

Zdefiniowałem następujące funkcje:

Generuj populację : generujemy populację o rozmiarze n i cel generujemy n ciąg zawierający len(target) losowych znaków, zwracamy populację jako listę str

Oblicz wynik sprawności : jeśli znak na pozycji i jest równy znakowi na pozycji i celu, zwiększamy wynik, oto kod:

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

Wybierz rodziców, krzyżuj rodziców i generuj nową populację dzieci

Oto funkcja za to odpowiedzialna:

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

Wybieram rodziców, obliczając prawdopodobieństwa każdej osoby (indywidualny wynik / całkowity wynik populacji), a następnie używając funkcji ważonego wyboru losowego , aby wybrać rodzica (jest to funkcja numpy).

W przypadku skrzyżowania generuję dziecko c i losowy punkt podziału, wszystkie znaki przed tym losowym punktem są pierwszymi znakami nadrzędnymi, a wszystkie znaki po punkcie podziału są znakami rodzica.

Poza tym zdefiniowałem funkcję o nazwie should_stop, która sprawdza, czy znaleźliśmy cel oraz print_best, która pobiera najlepsze osobniki z populacji (najwyższy wynik sprawności).

Następnie utworzyłem funkcję wyszukiwania, która korzysta ze wszystkich funkcji zdefiniowanych powyżej:

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

Problem Problem polega na tym, że generowanie hello wymaga zbyt wielu iteracji (przez większość czasu ponad 200 iteracji), podczas gdy w tym przykładzie wystarczy kilka iteracji: https://jbezerra.github.io/The-Shakespeare-and-Monkey -Problem / index.html

Oczywiście problem nie jest kodowany w ten sam sposób, użyłem Pythona i procedury proceduralnej do kodowania rzeczy, ale logika jest taka sama. Więc co robię źle?

1
Souames 31 marzec 2020, 17:49

3 odpowiedzi

Najlepsza odpowiedź

Mutujesz w 100%. Wybierasz „odpowiednich” rodziców, którzy prawdopodobnie dadzą sprawne potomstwo, ale następnie stosujesz mutację, która prawdopodobnie „wyrzuci”. Przykładowy link, który podałeś, zachowuje się tak samo, jeśli zwiększysz współczynnik mutacji do 100%.

Celem mutacji jest „popchnięcie” wyszukiwania w innym kierunku, jeśli wydaje się, że utknąłeś w lokalnym optimum. Stosowanie go przez cały czas zmienia to z algorytmu ewolucyjnego w coś znacznie bliższego wyszukiwaniu losowemu.

1
yurib 31 marzec 2020, 14:58

Proponuję zdefiniować ciągi znaków w słowniku i podać im liczbę, a następnie przeanalizować ten przykład tablic

Mój słownik is.

I: 1 jeść: 23 chcę: 12 do: 2

Więc chcę jeść przekonwertować na [1, 12, 2, 23], więc losowość jest zmniejszona o czynnik. tutaj słowa są wywnioskowane ze słownika, więc jedyną zmienną jest kolejność i to, które słowa występują w ciągu.

Przepisz swój algorytm ze słownikiem, twój czas działania algo poprawi się o czynnik. w odniesieniu do teja

-2
V Gajulavarthy 31 marzec 2020, 15:05

Idea algorytmów genetycznych pomaga przetrwać i stworzyć nowe pokolenia

Przede wszystkim powinieneś zachować najlepsze w każdym pokoleniu na następne pokolenie (na przykład najlepsze 40% każdego pokolenia żyje z następnego pokolenia) i powinieneś rozmnażać te 40% ze sobą i mutować tylko ograniczoną liczbę osobników w w każdym pokoleniu te liczby powinny być niskie, np. niższe niż 5% mutacji osobników. Uważam, że zmniejszy to liczbę pokoleń

1
K.Doruk 31 marzec 2020, 15:19