Zagadnienia związane ze sztuczną inteligencją stają się coraz bardziej popularne. Nie dość, że wiele osób o nich mówi, to nieść mogą za sobą worki wypchane pieniędzmi – i nie ma się co dziwić. AI (ang. artificial intelligence) potrafi rozwiązywać problemy z którymi dotąd nie umieliśmy sobie poradzić, a przynajmniej nie w satysfakcjonującym czasie. Ten wpis będzie właśnie o sztucznej inteligencji. Nie będę się jednak skupiał na sztucznych sieciach neuronowych, ale napiszę o podejściu, które moim zdaniem stoi trochę w ich cieniu, a mianowicie o algorytmach genetycznych.
Zacznijmy od tego, czym sztuczna inteligencja jest, a czym nie jest. W programowaniu tradycyjnym piszemy kod, który znajduje rozwiązanie problemu. Przykładowo jeśli chcemy sprawdzić, czy na danym obrazku jest kot, możemy w mniej lub bardziej mądry sposób analizować piksele. W przypadku sztucznej inteligencji nie napiszemy kodu, który będzie analizował obrazek, tylko zdefiniujemy, że dany obrazek przedstawia kota. Wówczas AI „nauczy się” jak wygląda kot, a co za tym idzie, będzie mogło sprawdzić czy na innych obrazach, które mu podamy, również znajdziemy kota. Zauważ proszę że podejście do problemu jest trochę inne – w programowaniu tradycyjnym definiujemy drogę do rozwiązania problemu a w przypadku sztucznej inteligencji – nie definiujemy tej drogi, ale dokładnie ta droga jest wynikiem procesu nauki AI.
Przykład, który wyżej opisałem, to problem klasyfikacji rozmytej, czyli sytuacji kiedy coś „w jakimś procencie jest podobne do wzorca, a więc pewnie nim jest”. Jeśli podamy AI (w przypadku sieci neuronowych) sporą liczbę zdjęć kotów, to nauczymy ją jak „wygląda” kot. Wynikiem tej nauki będą pewne liczby, które na pierwszy rzut oka mówią tyle co nic. I teraz, jeśli użyjemy tych liczb, a więc wiedzy zdobytej na etapie uczenia, ale na INNYM obrazku, to dostaniemy informację w jakim procencie nowy obrazek jest kotem. Czyli czy możemy zaklasyfikować go jako kota.
Przygotowując się do tego artykułu, natknąłem się na podział na słabą i silną sztuczną inteligencję. Słabą, czyli rozwiązującą konkretny problem, opisałem powyżej. Silna to ta do której dążymy, czyli taka, która nie ustępowałaby inteligencji ludzi.
Nim przejdziemy do głównego tematu wpisu, nie mogę odmówić sobie przyjemności, by podzielić się z Wami własnym zdaniem na temat sztucznej inteligencji, mitycznego buntu robotów czy bardziej przyziemnych rzeczy, takich jak kierunek rozwoju oprogramowania czy wpływ na sposób pracy programistów.
Zatem czy sztuczna inteligencja może kiedyś sprawić, że roboty zawładną światem? Bardzo sceptycznie podchodzę do tego tematu. AI jest nadal bardzo „głupiutkie”. Oglądając serię „Z tymi co się znają” natrafiłem na wywiad, w którym dr Aleksandra Przegalińska, nazywa AI „głupolkiem”. I ja się pod tym podpisuję! AI świetnie działa w bardzo wąskich segmentach i nim zacznie być „generyczne” to miną jeszcze długie lata. Jeśli w ogóle do tego dojdzie.
Czy AI zmieni sposób pracy programistów? Sądzę, że w pewnym stopniu tak, ale nie sądzę, by zmiana była drastyczna. Raczej po prostu nasze IDE zacznie być trochę mądrzejsze, podobnie jak statyczna analiza kodu, czy inne podobne elementy, ale core naszej pracy, czyli analiza i implementacja nowych elementów oprogramowania – pozostanie po naszej stronie.
Skoro mamy za sobą już wstęp to czas przejść do sedna tego artykułu.
Algorytm genetyczny to jeden z algorytmów sztucznej inteligencji. Genezą tego pomysłu jest myśl, której autorem jest John Henry Holland, dotycząca tego, jak ewolucja uczy człowieka coraz to lepszego przystosowania się do panujących warunków. Efektem tej refleksji jest właśnie algorytm genetyczny, który jest naprawdę ciekawym narzędziem optymalizacyjnym. Nim przejdę do zagłębienia się w ideę, ustalmy słownictwo.
Prowadząc Was po labiryntach tego arcyciekawego tematu będę używał słów które są dla niego właściwe i jako dobry przewodnik, zostawiam słowniczek :)
Gen – Najmniejsza część chromosomu.
Chromosom – Uporządkowany ciąg genów.
Genotyp – Zbiór chromosomów.
Osobnik – Najprostsza jednostka podlegająca ewolucji.
Populacja – Zbiór osobników zamieszkujących jedno środowisko.
Krzyżowanie – Losowe przecięcie dwóch chromosomów w jednym punkcie i zamiana podzielonych części między chromosomami.
Mutacja – Nagła zmiana materiału genetycznego.
Wiemy już mniej więcej czym jest Algorytm Genetyczny, znamy słownictwo, więc nie ma co czekać, czas na sam algorytm:
Proste, prawa?
Skoro tak, to czas na kod.
Aby móc ładnie pokazać jak działa Algorytm Genetyczny napiszemy bardzo prosty mini AI framework, który ułatwi nam napisanie właściwego programu. Zaczynamy.
Najpierw utwórzmy klasę reprezentującą osobnika. Będzie ona klasą abstrakcyjną i służyć ma wymuszaniu implementacji kilku metod potrzebnych w procesie działania algorytmu – specyficznych dla danego problemu. Może ona wyglądać tak:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | from abc import abstractmethod, ABC class Element(ABC): def __init__(self): self.fitness = self.evaluate_function() def mutation(self): self._perform_mutation() self.fitness = self.evaluate_function() @abstractmethod def _perform_mutation(self): pass @abstractmethod def crossover(self, element2: 'Element' ) -> 'Element': pass @abstractmethod def evaluate_function(self): pass |
Jak widać wymaga ona implementacji 3 metod:
Skoro mamy już naszego osobnika, to czas na właściwe przetwarzanie! Możemy to zrobić np. tak:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class GeneticAlgorithm: def __init__(self, first_population_generator: callable, selection_model: callable, stop_condition: callable, mutation_probability: float = 0.1): self.first_generation_func = first_population_generator self.selection_model = selection_model self.stop_condition = stop_condition self.mutation_probability = mutation_probability def run(self): population = self.first_generation_func() population.sort(key=lambda x: x.fitness) population_len = len(population) i = 0 while True: selected = self.selection_model(population) new_population = selected.copy() while len(new_population) != population_len: child = choice(population).crossover(choice(population)) if random() <= self.mutation_probability: child.mutation() new_population.append(child) population = new_population the_best_match = min(population, key=lambda x: x.fitness) print("Generation: {} S: {} fitness: {}".format(i, the_best_match, the_best_match.fitness)) i += 1 if self.stop_condition(the_best_match, the_best_match.fitness, i): break |
Konstruktor przyjmuje:
Pierwsze trzy elementy są jasne, a co do prawdopodobieństwa mutacji to zgodnie z ewolucją – mutacja jest zjawiskiem rzadkim, ale nie jest nieoczekiwana, wręcz przeciwnie, zgodnie z założeniem jest pewne, że wystąpi, tylko nie wiadomo kiedy. Standardowo przyjmuje się że prawdopodobieństwo mutacji w zadanym kroku wynosi 10%. Mutacja jest elementem który pozwala algorytmowi obrać dobry kierunek na początku, natomiast w trakcie przetwarzania zdarza się że ona przeszkadza. Czasem stosuje się zmniejszanie szansy mutacji wraz z ilością pokoleń.
Najważniejszym elementem tego kodu jest oczywiście funkcja o dźwięcznej nazwie run.
Ten element:
1 2 3 4 5 6 7 | selected = self.selection_model(population) new_population = selected.copy() while len(new_population) != population_len: child = choice(population).crossover(choice(population)) if random() <= self.mutation_probability: child.mutation() new_population.append(child) |
odpowiada za:
wybranie z populacji najlepszych osobników (zgodnie ze strategią przekazaną w funkcji selekcji) oraz stworzenie nowej populacji z tych wybranych plus dopełnienie do liczności populacji poprzez krzyżowanie oraz ewentualną mutację :)
Czyli jeszcze raz:
Po tej pętli już tylko wybieramy najlepszego osobnika z aktualnej populacji i sprawdzamy czy spełnia warunek stopu.
Z każdego pokolenia wybieramy najlepszych jej przedstawicieli. Sposób w jaki ich wybieramy nazywa się strategią selekcji.
Modelowych sposobów selekcji jest kilka. Sposób w jaki przekazujemy strategię do algorytmu pozwala użytkownikowi na napisanie własnej strategii, ale że nasz framework jest dobrym kawałkiem kodu to wraz z nim dostarczamy implementację jednej z nich. Będzie można sobie ją zaimportować i przekazać po prostu w konstruktorze.
Ta właśnie strategia jest dostępna w naszym frameworku i jej implementacja wygląda tak:
1 2 3 4 | def elite_selection_model(generation): max_selected = int(len(generation) / 10) sorted_by_assess = sorted(generation, key=lambda x: x.fitness) return sorted_by_assess[:max_selected] |
czyli po prostu wybieramy 10% najlepiej przystosowanych.
Ale istnieje jeszcze kilka innych!
Dzielimy osobników na grupy i przeprowadzamy „turniej”. Wówczas osobnik, który w danej podgrupie jest najlepszy, przechodzi do kolejnego pokolenia.
Dzielimy koło ruletki na wycinki odpowiadające osobnikom w populacji. Wielkość wycinka jest zależna od tego jak bardzo osobnik jest przystosowany – czyli jak dobry jest wynik funkcji przystosowania. Gdy już podzielimy koło ruletki, wybieramy losowo n osobników. Im większy wycinek ma dany osobnik, tym większa szansa że zostanie wylosowany. Ten sam osobnik może być wylosowany więcej niż raz :)
Strategii jest więcej, ale nie ma sensu ich tu wszystkich opisywać.
Dobra, czas na coś działającego!
Napiszemy program, który wykorzystując algorytm genetyczny, będzie dążył do stworzenia zadanego tekstu – może brzmi to w tym momencie dziwnie, ale w trakcie się wyjaśni, tak jak reszta elementów algorytmu.
Najpierw będziemy potrzebować kilku importów i tekstu do którego dążymy:
1 2 3 4 5 6 | from genetic_library import GeneticAlgorithm, Element from genetic_library.selection_models import elite_selection_model from random import randint, choice TARGET = "Czesc, tu Mateusz z mmazurek.dev :D" |
Czyli bierzemy naszą bibliotekę, strategię selekcji, dwie funkcje z random (zaraz okaże się po co) oraz docelowy tekst. Mamy uzyskać zdanie „Czesc, tu Mateusz z mmazurek.dev :D”.
Zacznijmy od najprostszej rzeczy, czyli od warunku stopu:
1 2 | def stop_condition(string, current_fitness, i): return current_fitness == 0 |
który sprawdza po prostu czy dobrneliśmy do 100% zgodności.
Dalej tworzymy funkcję generującą pierwsze, losowe pokolenie:
1 2 | def first_population_generator(): return [Text(''.join(choice(Text.POSSIBILITIES) for _ in range(len(TARGET)))) for _ in range(100)] |
Tworzymy tu sto obiektów typu Text, przekazując każdemu losowy string o długości równej docelowemu tekstowi. Ten losowy string jest wytworem losowych elementów z pola POSSIBILITIES.
I teraz najważniejszy element – czyli klasa Text, jak się pewnie domyślacie – rozszerzająca klasę Element, którą omówiliśmy wcześniej:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Text(Element): POSSIBILITIES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}''' def __init__(self, text): self.text = text super().__init__() def _perform_mutation(self): random_index = randint(0, len(self.text) - 1) text_as_list = list(self.text) text_as_list[random_index] = choice(self.POSSIBILITIES) self.text = "".join(text_as_list) def crossover(self, element2: 'Element' ) -> 'Element': length = int(randint(0, len(self.text) - 1)) new_text = self.text[:length] + element2.text[length:] return Text(new_text) def evaluate_function(self): diff = 0 for letter1, letter2 in zip(self.text, TARGET): if letter1 != letter2: diff += 1 return diff def __repr__(self): return self.text |
Oczywiście trzeba tu przyjrzeć się metodom które musimy zaimplementować. Lecimy więc od góry:
1 2 3 4 5 | def _perform_mutation(self): random_index = randint(0, len(self.text) - 1) text_as_list = list(self.text) text_as_list[random_index] = choice(self.POSSIBILITIES) self.text = "".join(text_as_list) |
Tutaj implementujemy sposób mutacji. Mutacja to nagła zmiana materiału genetycznego. W tym przypadku materiałem genetycznym są litery z określonego zakresu. Więc mutacją takiego osobnika to po prostu zmiana losowej litery na inną losowa literę.
Dalej mamy krzyżowanie:
1 2 3 4 5 | def crossover(self, element2: 'Element' ) -> 'Element': length = int(randint(0, len(self.text) - 1)) new_text = self.text[:length] + element2.text[length:] return Text(new_text) |
Bierzemy dwa osobniki, w tym przypadku dwa stringi. Losujemy indeks przecięcia się i bierzemy litery od początku do tego indeksu z pierwszego osobnika i łączymy go z literami od drugiego osobnika, wycinając z niego litery od wylosowanego indeksu do końca. Mamy zaimplementowane krzyżowanie!
Następnie ocena przystosowania:
1 2 3 4 5 6 | def evaluate_function(self): diff = 0 for letter1, letter2 in zip(self.text, TARGET): if letter1 != letter2: diff += 1 return diff |
czyli po prostu liczymy na ilu miejscach aktualny string różni się od docelowego.
Pisząc ten przykład funkcję oceny miałem na początku zaimplementowaną z użyciem algorytmu levensteina – czyli sposobu na określenie odległości pomiędzy jednym stringiem a drugim. Brzmi idealnie? No prawie…
Algorytm ten okazał się bardzo zawodny i spędziłem sporo czasu zanim odkryłem, że program nigdy nie znajdował rozwiązania zadanego problemu właśnie z powodu niepoprawnej funkcji oceny.
Problem z tym algorytmem polegał na tym że on liczy ile operacji zmiany znaku, usunięcia znaku lub dodania znaku dzieli jeden string od innego. Natomiast My w całym procesie przetwarzania nie mamy możliwości ani dodania znaku ani usunięcia, więc wynik był niemiarodajny. Po prostu ocenialiśmy go nie dając mu możliwości wypaść pod względem tej oceny, dobrze.
Dobre kilka godzin nad tym spędziłem :)
Przebieg przykładowego uruchomienia programu (po wycięciu pokoleń, które nie wnoszą zmiany) wyglądać może tak:
Generation: 0 S: e0@7@ qmIPXbN-@{zQ(Rm4[zqD)j 1eC5fC fitness: 31
Generation: 5 S: 4,h}cxf ]d@qreE,Me1#m4[zqD)j 1eC5fC fitness: 30
Generation: 9 S: :76M[K].S [# XILzQ(Rm4[zqD;.6eev:Oe fitness: 29
Generation: 14 S: 4,h}cxf WkoTceQKzQ(Rm4[zqD;.6eev:Oe fitness: 28
Generation: 20 S: UvzJcK].S [# eQKzQ(Rm4[zqD;.6eev:Oe fitness: 27
Generation: 31 S: 4,h}cK .S [WVeQKzQ(Rm4[zqD)jJ-ev:Oe fitness: 26
Generation: 36 S: 47&JcK .S [WreE,zQ(Rm4[zqD)j dev:Oe fitness: 25
Generation: 42 S: 47&JcK .S [WreQKzQzRm4[zqD)j devLOe fitness: 24
Generation: 78 S: 4,hsc? .S nWreQKzQzRm4[zqD)j dev:Oe fitness: 23
Generation: 93 S: C,hsc? .S nWreQKzQzRm4[zqD)j devLOe fitness: 22
Generation: 102 S: C,hsc? .S nWteQKzQzRm4[z/D)j devLOe fitness: 21
Generation: 122 S: C,hsc? .S [WteQszQzRm4[zqD)j devLOe fitness: 20
Generation: 141 S: C,hsc? .S nWteQszVzRm4azqD)j devL=e fitness: 19
Generation: 184 S: C,hsc? .S MWteQszVzRm4azqD)j devLOe fitness: 18
Generation: 212 S: C,hsc? tS MWteQszVzRm4azqD)j devLOe fitness: 17
Generation: 250 S: C,hsc? tS MateGszVzRm4azqD)j devLOe fitness: 16
Generation: 304 S: Czhsc? tS MateGszVzRm4azqD)j devLOe fitness: 15
Generation: 432 S: Czhsc? tS MateGszVz m4azqD)j=devLOe fitness: 14
Generation: 439 S: Czesc? tS Mate szVz m4azqD)j=devLOe fitness: 13
Generation: 456 S: Czesc? tS MateGsz z m4azqD)jddevLOe fitness: 12
Generation: 508 S: Czesc? tS MateGsz z m4azqD)kddevLOe fitness: 11
Generation: 512 S: Czesc? tS MateGsz z mmazqD)kddevLOe fitness: 10
Generation: 518 S: Czesc? tS MateGsz z mmazqr)kddevLOe fitness: 9
Generation: 575 S: Czesc? tS MateGsz z mmazqr)kddev Oe fitness: 8
Generation: 587 S: Czesc? t8 MateGsz z mmazur)kddev Oe fitness: 7
Generation: 594 S: Czesc? tu MateGsz z mmazur)kddev Oe fitness: 6
Generation: 661 S: Czesc? tu MateGsz z mmazurekddev Oe fitness: 5
Generation: 792 S: Czesc? tu Mateusz z mmazurekddev Oe fitness: 4
Generation: 1052 S: Czesc? tu Mateusz z mmazurekddev OD fitness: 3
Generation: 1272 S: Czesc? tu Mateusz z mmazurekddev :D fitness: 2
Generation: 1339 S: Czesc? tu Mateusz z mmazurek.dev :D fitness: 1
Generation: 1497 S: Czesc, tu Mateusz z mmazurek.dev :D fitness: 0 Oczywiście jest on zależny od losowych elementów całego algorytmu, więc każde jego uruchomienie na pewno da inny wynik.
Jak każde rozwiązanie i to nie jest wolne od wad. Jedną z nich jest uniwersalność – i oczywiście mimo że jest ona jednocześnie zaletą, to sprawia, że metoda ta będzie mniej wydajna od wyspecjalizowanych rozwiązań. Dodatkowo ten dział AI jest bardzo wrażliwy na jakość funkcji oceny oraz na sposób zakodowania rozwiązywanego problemu. Oczywiście algorytm genetyczny nie zawsze znajdzie najlepsze rozwiązanie, ale zazwyczaj efekt jego działania będzie satysfakcjonujący.
W zaletach warto wymienić, że algorytm ten jest odporny na na zmiany, które następują w czasie jego działania np. na zmianę funkcję oceny, która może wynikać ze zmiany wariantu który optymalizujemy, albo po prostu ze zmian środowiska, które trzeba w tej funkcji odwzorować.
W ramach tematu Algorytmów Genetycznych pojawi się jeszcze jeden wpis, który będzie po prostu kolejnym przykładem użycia kawałka kodu, który napisaliśmy. Aktualny przykład jak i ten mały framework wrzuciłem na GitHuba – https://github.com/mmazurekdev/genetic-algorithm
Ciąg dalszy nastąpił, zapraszam – https://mmazurek.dev/algorytmy-genetyczne-w-pythonie-ciag-dalszy/
Oj daaawnoo mnie tu nie było. Ale wakacje to był czas dużej liczby intensywnych wyjazdów i tak naprawdę, dopiero jakoś… Read More
Cześć! Zapraszam na krótkie podsumowanie kwietnia. Wyjazd do Niemiec A dokładniej pod granicę z Francją. Chrześnica miała pierwszą komunię. Po… Read More
Ostatnio tygodnie były tak bardzo wypełnione, że nie udało mi się napisać nawet krótkiego podsumowanie. Więc dziś zbiorczo podsumuję luty… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W styczniu przeczytałem "Homo Deus: Historia jutra". Książka łudząco podoba do wcześniejszej książki tego… Read More
Cześć! Zapraszam na podsumowanie roku 2023. Książki Zacznijmy od książek. W tym roku cel 35 książek nie został osiągnięty. Niemniej… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W grudniu skończyłem czytać Mein Kampf. Nudna książka. Ciekawsze fragmenty można by było streścić… Read More
Pokaż komentarze
Dobry wpis, który przyjemnie się czyta. :) Algorytm, który użyłeś do funkcji oceny to po prostu odległość Hamminga. Odległość Levenshteina, o której pisałeś, jest jej uogólnieniem i w Twoim przykładzie zadziała tylko w pewnych (losowych) przypadkach, więc nie dziwię się Twojemu wielogodzinnemu debugowaniu. :D Na dodatek złożoność czasowa jest znacznie gorsza.
Dzięki za pozytywny feedback! :D
Co do Levenshteina - wydawał się idealny wręcz! A tu taki psikus. I było dokładnie tak jak napisałeś:) zachodziłem w głowę gdzie jest błąd. Olśnienie przyszło jak zobaczyłem że ta sama para stringów dla Levenshteina i Hamminga zwraca inny wynik;)
Po pierwsze - jeśli kodowanie nie jest zero-jedynkowe, to należy mówić/pisać o algorytmach ewolucyjnych, a nie genetycznych.
Po drugie - znaczenie mutacji jest bardziej złożone. Z założenia mutacja powinna ułatwiać "wyjście" z lokalnego optimum, wokół którego skupia się całość lub część populacji. Z tego względu nie można stwierdzać, że ma znaczenie tylko na początku. Wprost przeciwnie - jeśli będzie silny nacisk selekcyjny, to populacja może szybko skupić się wokół jakiegoś lokalnego minimum. W takiej sytuacji tylko mutacja może pomóc opuścić ten obszar - i nastąpi to (jeśli w ogóle, bo mutacja jest losowa) raczej w końcowej (albo "przedkońcowej) fazie działania algorytmu.
W materiałach które pomagały mi zrozumieć ten temat nazwy te były używane wymiennie, ale faktycznie zaznaczone było, że to skrót myślowy. A co do "po drugie" całkowicie się zgadzam - lokalne minima to sytuacja kiedy algorytm myśli że znalazł rozwiązanie i kręci się trochę w kółko, impas może przerwać tak jak napisałeś - mutacja. Dzięki za komentarz, nie chciałem nigdzie zabrzmieć tak, jakbym uważał, że mutacja ma znaczenie tylko na początku:) jeszcze raz, dzięki za wyprostowanie mojego przekazu:)
Czy w poniższym fragmencie krzyżowanie nie powinno zachodzić między osobnikami z selekcji a nie z całej populacji ?
Cześć! Artykuł ma swoje lata, więc nie pamiętam go dokładnie, ale to co piszesz ma sens :D