Algorytm genetyczny: Różnice pomiędzy wersjami
Z Encyklopedia Zarządzania
m (→Bibliografia: Clean up, replaced: →) |
m (cleanup bibliografii i rotten links) |
||
| (Nie pokazano 9 wersji utworzonych przez 2 użytkowników) | |||
| Linia 1: | Linia 1: | ||
'''[[Algorytm]] genetyczny''' - Algorytm oparty na mechanizmach dziedziczności i doboru naturalnego. Łączy w sobie zasadę przeżycia najlepiej przystosowanych jednostek i zasadę losowej wymiany informacji. Takie połączenie skutkuje metodą poszukiwania obdarzoną dozą pomysłowości właściwej dla umysłu człowieka. W każdym kolejnym pokoleniu ''powstaje nowy [[zespół]] sztucznych organizmów (ciągów bitowych), utworzonych z połączenia fragmentów najlepiej przystosowanych przedstawicieli poprzedniego pokolenia'' (David E. Goldberg 1995 s. 17). Mimo losowości, algorytmy genetyczne nie są przypadkowe, a wykorzystują doświadczenia z przeszłości do najlepszego określenia nowego obszaru poszukiwań o spodziewanej, wyższej wydajności. | '''[[Algorytm]] genetyczny''' - Algorytm oparty na mechanizmach dziedziczności i doboru naturalnego. Łączy w sobie zasadę przeżycia najlepiej przystosowanych jednostek i zasadę losowej wymiany informacji. Takie połączenie skutkuje metodą poszukiwania obdarzoną dozą pomysłowości właściwej dla umysłu człowieka. W każdym kolejnym pokoleniu ''powstaje nowy [[zespół]] sztucznych organizmów (ciągów bitowych), utworzonych z połączenia fragmentów najlepiej przystosowanych przedstawicieli poprzedniego pokolenia'' (David E. Goldberg 1995 s. 17). Mimo losowości, algorytmy genetyczne nie są przypadkowe, a wykorzystują doświadczenia z przeszłości do najlepszego określenia nowego obszaru poszukiwań o spodziewanej, wyższej wydajności. | ||
| Linia 20: | Linia 5: | ||
==Historia powstania algorytmu genetycznego== | ==Historia powstania algorytmu genetycznego== | ||
Podstawą powstania algorytmu genetycznego była chęć zrobienia tego samego, co robi natura. Naśladuje on krok po kroku [[proces]] mutacji genetycznych u zwierząt - przeżywają najsilniejsze osobniki, a u kolejnych pokoleń nasilają się mocne cechy przodków. W latach 1957-1962 Barricelli, Fraser, Martin, Cockerham rozpoczęli proces powstawania algorytmu genetycznego modelując procesy genetyczne. W roku 1960 profesor John Holland z Uniwersytetu w Michigan w swojej książce ''Adaptation in Natural and Artificial Systems'' wyjaśnił i opisał istoty procesów adaptacyjnych występujących w przyrodzie. Stworzył również oprogramowanie, które odtwarzało podstawowe mechanizmy rządzące systemami biologicznymi. Holland wraz ze współpracownikami z uniwersytetu mieli dwa [[cele]] badań: | |||
Podstawą powstania algorytmu genetycznego była chęć zrobienia tego samego, co robi natura. Naśladuje on krok po kroku [[proces]] mutacji genetycznych u zwierząt - przeżywają najsilniejsze osobniki, a u kolejnych pokoleń nasilają się mocne cechy przodków. W latach 1957 - 1962 Barricelli, Fraser, Martin, Cockerham rozpoczęli proces powstawania algorytmu genetycznego modelując procesy genetyczne. W roku 1960 profesor John Holland z Uniwersytetu w Michigan w swojej książce ''Adaptation in Natural and Artificial Systems'' wyjaśnił i opisał istoty procesów adaptacyjnych występujących w przyrodzie. Stworzył również oprogramowanie, które odtwarzało podstawowe mechanizmy rządzące systemami biologicznymi. Holland wraz ze współpracownikami z uniwersytetu mieli dwa [[cele]] badań: | |||
# Opisanie i wyjaśnienie w ścisły sposób istoty procesów adaptacyjnych w świecie przyrody, | # Opisanie i wyjaśnienie w ścisły sposób istoty procesów adaptacyjnych w świecie przyrody, | ||
# Stworzenie oprogramowania, które mogłoby odtwarzać podstawowe mechanizmy rządzące systemami biologicznymi. | # Stworzenie oprogramowania, które mogłoby odtwarzać podstawowe mechanizmy rządzące systemami biologicznymi. | ||
Postawienie problemu w ten sposób skutkowało ważnymi odkryciami w badaniach systemowych. | Postawienie problemu w ten sposób skutkowało ważnymi odkryciami w badaniach systemowych. | ||
<google>n</google> | |||
==Podstawowe pojęcia związane z algorytmem genetycznym== | ==Podstawowe pojęcia związane z algorytmem genetycznym== | ||
{| border="1" style="border-collapse:collapse" | {| border="1" style="border-collapse:collapse" | ||
| '''Biologia (genetyka)''' | | '''Biologia (genetyka)''' | ||
| Linia 66: | Linia 50: | ||
[[Plik:Schemat algorytmu genetycznego.png|300px|right|thumb|Rys. 1 - Model przebiegu klasycznego algorytmu genetycznego. Opracowanie własne.]] | [[Plik:Schemat algorytmu genetycznego.png|300px|right|thumb|Rys. 1 - Model przebiegu klasycznego algorytmu genetycznego. Opracowanie własne.]] | ||
Klasyczny algorytm z kodowaniem binarnym składa się z następujących etapów: | Klasyczny algorytm z kodowaniem binarnym składa się z następujących etapów: | ||
#'''Etap wstępny - kodowanie problemu.''' Zakodowanie wszystkich możliwych rozwiązań w języku binarnym. Długość łańcuchów kodujących ustalamy z góry. Skonstruowanie funkcji. | # '''Etap wstępny - kodowanie problemu.''' Zakodowanie wszystkich możliwych rozwiązań w języku binarnym. Długość łańcuchów kodujących ustalamy z góry. Skonstruowanie funkcji. | ||
#'''Konstrukcja populacji początkowej''' z całkowicie losowych N osobników. Liczba N zależy od czasu oraz stopnia złożoności problemu. Najczęściej wybierana [[wartość]] to 20-50 osobników. | # '''Konstrukcja populacji początkowej''' z całkowicie losowych N osobników. Liczba N zależy od czasu oraz stopnia złożoności problemu. Najczęściej wybierana [[wartość]] to 20-50 osobników. | ||
#'''Zastosowanie operatorów genetycznych''' - mutacja (zamiana jednego bitu danego osobnika na przeciwną) lub krzyżowanie (zamiana fragmentów ciągu kodowego). | # '''Zastosowanie operatorów genetycznych''' - mutacja (zamiana jednego bitu danego osobnika na przeciwną) lub krzyżowanie (zamiana fragmentów ciągu kodowego). | ||
#'''Obliczenie wartości funkcji celu osobników.''' [[Ocena]] rozwiązania funkcją celu. | # '''Obliczenie wartości funkcji celu osobników.''' [[Ocena]] rozwiązania funkcją celu. | ||
#'''[[Selekcja]]''' - Zamiana wartości obliczonej poprzednio funkcji na wartość przystosowania. Wybór spośród N osobników populacji pośredniej N osobników populacji końcowej za pomocą algorytmu "koło ruletki". Obliczenie sumy wartości funkcji celu, wkład każdego osobnika w sumę i potraktowanie obliczeń jako rozkład prawdopodobieństwa. | # '''[[Selekcja]]''' - Zamiana wartości obliczonej poprzednio funkcji na wartość przystosowania. Wybór spośród N osobników populacji pośredniej N osobników populacji końcowej za pomocą algorytmu "koło ruletki". Obliczenie sumy wartości funkcji celu, wkład każdego osobnika w sumę i potraktowanie obliczeń jako rozkład prawdopodobieństwa. | ||
#'''Potraktowanie populacji końcowej jako populacji bieżącej.''' Powrót do punktu 3. | # '''Potraktowanie populacji końcowej jako populacji bieżącej.''' Powrót do punktu 3. | ||
Algorytm można zatrzymać na żądanie użytkownika. Brak gwarancji na znalezienie optymalnego rozwiązania z powodu losowych działań mutacji, krzyżowania i selekcji. | Algorytm można zatrzymać na żądanie użytkownika. Brak gwarancji na znalezienie optymalnego rozwiązania z powodu losowych działań mutacji, krzyżowania i selekcji. | ||
| Linia 94: | Linia 78: | ||
''Występujące w realnym świecie problemy charakteryzują się zwykle bardzo dużą liczbą zmiennych (dyskretnych lub ciągłych), dużą złożonością przestrzeni poszukiwań (wiele ograniczeń i celów, które na dodatek mogą być ze sobą sprzeczne). Problemy te mogą się zmieniać w czasie (być dynamiczne), co pociąga za sobą konieczność szybkiego otrzymywania dobrych rozwiązań.'' (E. Figielska ''Algorytmy ewolucyjne i ich zastosowania'' s. 89-90). | ''Występujące w realnym świecie problemy charakteryzują się zwykle bardzo dużą liczbą zmiennych (dyskretnych lub ciągłych), dużą złożonością przestrzeni poszukiwań (wiele ograniczeń i celów, które na dodatek mogą być ze sobą sprzeczne). Problemy te mogą się zmieniać w czasie (być dynamiczne), co pociąga za sobą konieczność szybkiego otrzymywania dobrych rozwiązań.'' (E. Figielska ''Algorytmy ewolucyjne i ich zastosowania'' s. 89-90). | ||
[[Planowanie]] i harmonogramowanie procesów produkcyjnych jest ważnym zastosowaniem algorytmów genetycznych. W większości zastosowania algorytmów genetycznych, [[harmonogram]] jest kodowany jako chromosom, który określa kolejność wykonywania poszczególnych czynności. To wymaga zastosowania operatorów genetycznych, które są odpowiednio zaprojektowane. Odpowiednie zakodowanie chromosomów i zaprojektowanie operatorów genetycznych reprezentują rozwiązania dopuszczalne. Kolejnym zastosowaniem algorytmu genetycznego jest [[przemysł]] chemiczny. ''[[Optymalizacja]] w zakładach chemicznych polega na modyfikacji struktury parametrów operacyjnych tak, aby znaleźć globalne optimum w celu wykonania pewnego zadania chemicznego'' (E. Figielska ''Algorytmy ewolucyjne i ich zastosowania'' s. 90). Algorytmy stosuje się także w medycynie, zwłaszcza jako pomoc przy leczeniu nowotworów. Pomaga podejmować decyzję o sposobie leczenia, jak również optymalizuje czas pacjenta i wykorzystanie aparatury. | [[Planowanie]] i harmonogramowanie procesów produkcyjnych jest ważnym zastosowaniem algorytmów genetycznych. W większości zastosowania algorytmów genetycznych, [[harmonogram]] jest kodowany jako chromosom, który określa kolejność wykonywania poszczególnych czynności. To wymaga zastosowania operatorów genetycznych, które są odpowiednio zaprojektowane. Odpowiednie zakodowanie chromosomów i zaprojektowanie operatorów genetycznych reprezentują rozwiązania dopuszczalne. Kolejnym zastosowaniem algorytmu genetycznego jest [[przemysł]] chemiczny. ''[[Optymalizacja]] w zakładach chemicznych polega na modyfikacji struktury parametrów operacyjnych tak, aby znaleźć globalne optimum w celu wykonania pewnego zadania chemicznego'' (E. Figielska ''Algorytmy ewolucyjne i ich zastosowania'' s. 90). Algorytmy stosuje się także w medycynie, zwłaszcza jako pomoc przy leczeniu nowotworów. Pomaga podejmować decyzję o sposobie leczenia, jak również optymalizuje czas pacjenta i wykorzystanie aparatury. | ||
{{infobox5|list1={{i5link|a=[[Typizacja]]}} — {{i5link|a=[[Permutacja]]}} — {{i5link|a=[[System ekspercki]]}} — {{i5link|a=[[Algorytm przetwarzania]]}} — {{i5link|a=[[Komputery kwantowe]]}} — {{i5link|a=[[Algorytm ewolucyjny]]}} — {{i5link|a=[[Metoda Blocha-Schmigalli]]}} — {{i5link|a=[[Projektowanie eksperymentów]]}} — {{i5link|a=[[Backlog produktu]]}} }} | |||
==Bibliografia== | ==Bibliografia== | ||
<noautolinks> | <noautolinks> | ||
* E | * Figielska E. (2006), ''[https://zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt1/Algorytmy_Ewolucyjne_I_Ich_Zastosowania.pdf Algorytmy ewolucyjne i ich zastosowania]'', Zeszyty naukowe , Warszawska Wyższa Szkoła Informatyki, Warszawa | ||
* Goldberg E. (1989), ''Algorytmy genetyczne i ich zastosowania'', Wydawnictwa Naukowo-Techniczne | |||
* Michalewicz Z. ( | * Michalewicz Z. (1996), ''Algorytmy Genetyczne+Struktury Danych=Programy Ewolucyjne'', Wydawnictwa Naukowo-Techniczne, Warszawa | ||
* Różanowski K. | * Różanowski K. (2007), ''[https://zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt2/Sztuczna_Inteligencja_Rozwoj_Szanse_I_Zagrozenia.pdf Sztuczna inteligencja: rozwój, szanse i zagrożenia]'', Zeszyty naukowe 109-135 | ||
* Wieleba R. | * Wieleba R. (2011), ''[https://zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt5/Inzynieria_Wiedzy_W_Systemach_Ekspertowych.pdf Inżynieria wiedzy w systemach ekspertowych]'', Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki, nr 5(5) | ||
</noautolinks> | </noautolinks> | ||
{{a|Julia Witana}} | {{a|Julia Witana}} | ||
[[Kategoria:Algorytmy]] | |||
[[Kategoria: | |||
{{#metamaster:description|Algorytm genetyczny to metoda poszukiwania oparta na przeżyciu najlepiej przystosowanych jednostek i losowej wymianie informacji. Pozwala na odkrywanie nowych rozwiązań i doskonalenie się w kolejnych pokoleniach.}} | {{#metamaster:description|Algorytm genetyczny to metoda poszukiwania oparta na przeżyciu najlepiej przystosowanych jednostek i losowej wymianie informacji. Pozwala na odkrywanie nowych rozwiązań i doskonalenie się w kolejnych pokoleniach.}} | ||
Aktualna wersja na dzień 18:20, 16 sty 2024
Algorytm genetyczny - Algorytm oparty na mechanizmach dziedziczności i doboru naturalnego. Łączy w sobie zasadę przeżycia najlepiej przystosowanych jednostek i zasadę losowej wymiany informacji. Takie połączenie skutkuje metodą poszukiwania obdarzoną dozą pomysłowości właściwej dla umysłu człowieka. W każdym kolejnym pokoleniu powstaje nowy zespół sztucznych organizmów (ciągów bitowych), utworzonych z połączenia fragmentów najlepiej przystosowanych przedstawicieli poprzedniego pokolenia (David E. Goldberg 1995 s. 17). Mimo losowości, algorytmy genetyczne nie są przypadkowe, a wykorzystują doświadczenia z przeszłości do najlepszego określenia nowego obszaru poszukiwań o spodziewanej, wyższej wydajności.
TL;DR
Algorytm genetyczny to metoda sztucznej inteligencji, która naśladuje procesy dziedziczenia i doboru naturalnego. Polega na tworzeniu nowych sztucznych organizmów poprzez kombinację najlepiej przystosowanych cech poprzednich generacji. Algorytmy genetyczne mają wiele zastosowań, m.in. w planowaniu procesów produkcyjnych, przemyśle chemicznym i medycynie. Mają wiele zalet, takich jak uniwersalność i zdolność do poradzenia sobie z problemami o wysokiej złożoności. Jednak mają też wady, takie jak wolniejsza wydajność w porównaniu do innych metod optymalizacji.
Historia powstania algorytmu genetycznego
Podstawą powstania algorytmu genetycznego była chęć zrobienia tego samego, co robi natura. Naśladuje on krok po kroku proces mutacji genetycznych u zwierząt - przeżywają najsilniejsze osobniki, a u kolejnych pokoleń nasilają się mocne cechy przodków. W latach 1957-1962 Barricelli, Fraser, Martin, Cockerham rozpoczęli proces powstawania algorytmu genetycznego modelując procesy genetyczne. W roku 1960 profesor John Holland z Uniwersytetu w Michigan w swojej książce Adaptation in Natural and Artificial Systems wyjaśnił i opisał istoty procesów adaptacyjnych występujących w przyrodzie. Stworzył również oprogramowanie, które odtwarzało podstawowe mechanizmy rządzące systemami biologicznymi. Holland wraz ze współpracownikami z uniwersytetu mieli dwa cele badań:
- Opisanie i wyjaśnienie w ścisły sposób istoty procesów adaptacyjnych w świecie przyrody,
- Stworzenie oprogramowania, które mogłoby odtwarzać podstawowe mechanizmy rządzące systemami biologicznymi.
Postawienie problemu w ten sposób skutkowało ważnymi odkryciami w badaniach systemowych.
Podstawowe pojęcia związane z algorytmem genetycznym
| Biologia (genetyka) | Algorytm genetyczny |
| Gen | Bit |
| Chromosom | Ciąg bitów |
| Osobnik | Punkt w przestrzeni rozwiązań |
| Populacja | Zbiór punktów |
| Krzyżowanie | Wymiana ciągu bitów |
| Mutacja | Negacja bitów |
Tabela 1 - Odpowiedniki biologiczne podstawowych pojęć algorytmu genetycznego.
Odpowiedniki biologiczne podstawowych pojęć algorytmu genetycznego
- Gen - Najmniejsza część chromosomu. Decyduje o dziedziczności jednej lub kilku cech.
- Chromosom - Inaczej łańcuch lub ciąg kodowy. Jest to uporządkowany ciąg genó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.
Klasyczny algorytm genetyczny
Klasyczny algorytm z kodowaniem binarnym składa się z następujących etapów:
- Etap wstępny - kodowanie problemu. Zakodowanie wszystkich możliwych rozwiązań w języku binarnym. Długość łańcuchów kodujących ustalamy z góry. Skonstruowanie funkcji.
- Konstrukcja populacji początkowej z całkowicie losowych N osobników. Liczba N zależy od czasu oraz stopnia złożoności problemu. Najczęściej wybierana wartość to 20-50 osobników.
- Zastosowanie operatorów genetycznych - mutacja (zamiana jednego bitu danego osobnika na przeciwną) lub krzyżowanie (zamiana fragmentów ciągu kodowego).
- Obliczenie wartości funkcji celu osobników. Ocena rozwiązania funkcją celu.
- Selekcja - Zamiana wartości obliczonej poprzednio funkcji na wartość przystosowania. Wybór spośród N osobników populacji pośredniej N osobników populacji końcowej za pomocą algorytmu "koło ruletki". Obliczenie sumy wartości funkcji celu, wkład każdego osobnika w sumę i potraktowanie obliczeń jako rozkład prawdopodobieństwa.
- Potraktowanie populacji końcowej jako populacji bieżącej. Powrót do punktu 3.
Algorytm można zatrzymać na żądanie użytkownika. Brak gwarancji na znalezienie optymalnego rozwiązania z powodu losowych działań mutacji, krzyżowania i selekcji.
Zalety i wady algorytmu genetycznego
Zalety
- Uniwersalność. Możliwość użycia tego samego schematu przy zmianie jedynie funkcji celu.
- Możliwość poradzenia sobie w warunkach, gdzie optymalizowana funkcja jest zaszumiona, zmienna w czasie lub ma wiele ekstremów lokalnych.
- Brak wymaganej wiedzy na temat optymalizowanej funkcji.
- Brak wymaganej funkcji celu - 'możemy wykorzystywać algorytmy genetyczne nawet wtedy, gdy jedyną rzeczą, jaką potrafimy powiedzieć o punktach przestrzeni stanów jest to, który z dwóch punktów jest lepszy (selekcja turniejowa).' (P. Rembelski, Wykład 10 - Algorytmy Ewolucyjne)
- Szybkość metody.
- Możliwość powtarzania obliczeń wielokrotnie.
Wady
- Uniwersalność, metoda nie jest tak skuteczna jak metody specjalizowane.
- Metoda jest wolniejsza niż proste heurystyki (na przykład: metoda zachłanna).
- Możliwość osiągnięcia sukcesu wyłącznie przy prawidłowym zakodowaniu problemu i odpowiednim dobraniu fukcji celu.
- Brak jednoznacznej metody kodowania problemu i dobrania funkcji celu. Potrzebne jest odpowiednie doświadczenie.
- Brak pewności, czy znalezione rozwiązanie jest poprawne.
Zastosowanie algorytmu genetycznego
Występujące w realnym świecie problemy charakteryzują się zwykle bardzo dużą liczbą zmiennych (dyskretnych lub ciągłych), dużą złożonością przestrzeni poszukiwań (wiele ograniczeń i celów, które na dodatek mogą być ze sobą sprzeczne). Problemy te mogą się zmieniać w czasie (być dynamiczne), co pociąga za sobą konieczność szybkiego otrzymywania dobrych rozwiązań. (E. Figielska Algorytmy ewolucyjne i ich zastosowania s. 89-90). Planowanie i harmonogramowanie procesów produkcyjnych jest ważnym zastosowaniem algorytmów genetycznych. W większości zastosowania algorytmów genetycznych, harmonogram jest kodowany jako chromosom, który określa kolejność wykonywania poszczególnych czynności. To wymaga zastosowania operatorów genetycznych, które są odpowiednio zaprojektowane. Odpowiednie zakodowanie chromosomów i zaprojektowanie operatorów genetycznych reprezentują rozwiązania dopuszczalne. Kolejnym zastosowaniem algorytmu genetycznego jest przemysł chemiczny. Optymalizacja w zakładach chemicznych polega na modyfikacji struktury parametrów operacyjnych tak, aby znaleźć globalne optimum w celu wykonania pewnego zadania chemicznego (E. Figielska Algorytmy ewolucyjne i ich zastosowania s. 90). Algorytmy stosuje się także w medycynie, zwłaszcza jako pomoc przy leczeniu nowotworów. Pomaga podejmować decyzję o sposobie leczenia, jak również optymalizuje czas pacjenta i wykorzystanie aparatury.
| Algorytm genetyczny — artykuły polecane |
| Typizacja — Permutacja — System ekspercki — Algorytm przetwarzania — Komputery kwantowe — Algorytm ewolucyjny — Metoda Blocha-Schmigalli — Projektowanie eksperymentów — Backlog produktu |
Bibliografia
- Figielska E. (2006), Algorytmy ewolucyjne i ich zastosowania, Zeszyty naukowe , Warszawska Wyższa Szkoła Informatyki, Warszawa
- Goldberg E. (1989), Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne
- Michalewicz Z. (1996), Algorytmy Genetyczne+Struktury Danych=Programy Ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa
- Różanowski K. (2007), Sztuczna inteligencja: rozwój, szanse i zagrożenia, Zeszyty naukowe 109-135
- Wieleba R. (2011), Inżynieria wiedzy w systemach ekspertowych, Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki, nr 5(5)
Autor: Julia Witana
