Programowanie ekspresji genów

W programowaniu komputerowym programowanie ekspresji genów (GEP) to algorytm ewolucyjny , który tworzy programy komputerowe lub modele. Te programy komputerowe to złożone struktury drzew , które uczą się i dostosowują, zmieniając swoje rozmiary, kształty i skład, podobnie jak żywy organizm. Podobnie jak żywe organizmy, programy komputerowe GEP są również zakodowane w prostych liniowych chromosomach o ustalonej długości. Zatem GEP jest systemem genotyp-fenotyp , korzystającym z prostego genomu do przechowywania i przekazywania informacji genetycznej oraz złożonego fenotypu do badania środowiska i przystosowania się do niego.

Tło

Algorytmy ewolucyjne wykorzystują populacje osobników, wybierają osobniki zgodnie z przystosowaniem i wprowadzają zmienność genetyczną za pomocą jednego lub więcej operatorów genetycznych . Ich zastosowanie w sztucznych systemach obliczeniowych datuje się na lata pięćdziesiąte XX wieku, kiedy stosowano je do rozwiązywania problemów optymalizacyjnych (np. Box 1957 i Friedman 1959). Ale to wraz z wprowadzeniem strategii ewolucyjnych przez Rechenberga w 1965 roku algorytmy ewolucyjne zyskały popularność. Dobrym przeglądem algorytmów ewolucyjnych jest książka „An Introduction to Genetic Algorithms” autorstwa Mitchella (1996).

Programowanie ekspresji genów należy do rodziny algorytmów ewolucyjnych i jest blisko spokrewnione z algorytmami genetycznymi i programowaniem genetycznym . Z algorytmów genetycznych odziedziczył liniowe chromosomy o ustalonej długości; az programowania genetycznego odziedziczył ekspresyjne drzewa analizy o różnych rozmiarach i kształtach.

W programowaniu ekspresji genów liniowe chromosomy działają jako genotyp, a drzewa analizy jako fenotyp, tworząc system genotyp/fenotyp . Ten system genotyp/fenotyp jest wielogenowy , a zatem koduje wiele drzew analizy w każdym chromosomie. Oznacza to, że programy komputerowe tworzone przez GEP składają się z wielu drzew analizy. Ponieważ te drzewa analizy są wynikiem ekspresji genów, w GEP nazywane są drzewami ekspresji .

Kodowanie: genotyp

Genom programowania ekspresji genów składa się z liniowego, symbolicznego ciągu lub chromosomu o ustalonej długości, złożonego z jednego lub więcej genów o równej wielkości. Geny te, pomimo swojej ustalonej długości, kodują drzewa ekspresyjne o różnych rozmiarach i kształtach. Przykładem chromosomu z dwoma genami, każdy o rozmiarze 9, jest łańcuch (pozycja zero oznacza początek każdego genu):

012345678012345678

L+a-baccd**cLabacd

gdzie „L” reprezentuje funkcję logarytmu naturalnego, a „a”, „b”, „c” i „d” reprezentują zmienne i stałe użyte w zadaniu.

Drzewa ekspresyjne: fenotyp

Jak pokazano powyżej , wszystkie geny programowania ekspresji genów mają ten sam rozmiar. Jednak te ciągi o stałej długości kodują drzewa wyrażeń o różnych rozmiarach. Oznacza to, że wielkość regionów kodujących różni się w zależności od genu, umożliwiając płynną adaptację i ewolucję.

Na przykład wyrażenie matematyczne:

${\ Displaystyle {\ sqrt {(ab) (c + d)}} \,}$

można również przedstawić jako drzewo wyrażeń :

gdzie „Q” reprezentuje funkcję pierwiastka kwadratowego.

Ten rodzaj drzewa ekspresyjnego składa się z fenotypowej ekspresji genów GEP, podczas gdy geny są liniowymi łańcuchami kodującymi te złożone struktury. W tym konkretnym przykładzie ciąg liniowy odpowiada:

01234567

Q*-+abcd

który jest prostym odczytaniem drzewa wyrażeń od góry do dołu i od lewej do prawej. Te ciągi liniowe nazywane są k-wyrażeniami (z notacji Karva).

Przejście od k-wyrażeń do drzew wyrażeń jest również bardzo proste. Na przykład następujące wyrażenie k:

01234567890

Q*b**+baQba

składa się z dwóch różnych końcówek (zmienne „a” i „b”), dwóch różnych funkcji o dwóch argumentach („*” i „+”) oraz funkcji o jednym argumencie („Q”). Jego wyrażenie daje:

K-ekspresje i geny

K-ekspresje programowania ekspresji genów odpowiadają regionowi genów, który ulega ekspresji. Oznacza to, że w genach mogą istnieć sekwencje, które nie ulegają ekspresji, co jest prawdą w przypadku większości genów. Powodem istnienia tych niekodujących regionów jest zapewnienie bufora terminali, tak aby wszystkie k-wyrażenia zakodowane w genach GEP zawsze odpowiadały ważnym programom lub wyrażeniom.

Geny programowania ekspresji genów składają się zatem z dwóch różnych domen – głowy i ogona – z których każda ma inne właściwości i funkcje. Głowa jest używana głównie do kodowania funkcji i zmiennych wybranych do rozwiązania danego problemu, podczas gdy ogon, chociaż jest również używany do kodowania zmiennych, zapewnia zasadniczo rezerwuar terminali, aby zapewnić, że wszystkie programy są wolne od błędów.

Dla genów GEP długość ogona jest określona wzorem:

${\ Displaystyle t = h (n _ {\ maks} -1) + 1}$

gdzie h to długość głowy, a n _max to maksymalna artyczność. Na przykład dla genu utworzonego za pomocą zestawu funkcji F = {Q, +, −, ∗, /} i zestawu końcówek T = {a, b}, n _max = 2. A jeśli wybierzemy długość głowy 15, wtedy t = 15 (2–1) + 1 = 16, co daje długość genu g równą 15 + 16 = 31. Losowo wygenerowany ciąg poniżej jest przykładem jednego takiego genu:

0123456789012345678901234567890

*b+a-aQab+//+b+babbabbbbababbaa

Koduje drzewo wyrażeń:

który w tym przypadku wykorzystuje tylko 8 z 31 elementów składających się na gen.

Nietrudno zauważyć, że pomimo ustalonej długości każdy gen ma potencjał do kodowania drzew ekspresji o różnych rozmiarach i kształtach, przy czym najprostszy składa się tylko z jednego węzła (kiedy pierwszym elementem genu jest terminal) i największy złożony z tylu węzłów, ile jest elementów w genie (gdy wszystkie elementy w głowie są funkcjami o maksymalnej arności).

Nietrudno też zauważyć, że wprowadzanie wszelkiego rodzaju modyfikacji genetycznych ( mutacji , inwersji, insercji, rekombinacji itd.) z gwarancją, że całe powstałe potomstwo zakoduje poprawne, wolne od błędów programy, jest trywialne.

Chromosomy wielogenowe

Chromosomy programowania ekspresji genów zwykle składają się z więcej niż jednego genu o równej długości. Każdy gen koduje drzewo subekspresji (sub-ET) lub podprogram. Następnie pod-ET mogą wchodzić w interakcje ze sobą na różne sposoby, tworząc bardziej złożony program. Rysunek przedstawia przykład programu złożonego z trzech podrzędnych ET.

Ekspresja genów GEP jako sub-ET. a) Chromosom trójgenowy z ogonami pokazanymi pogrubioną czcionką. b) Sub-ET kodowane przez każdy gen.

W ostatecznym programie pod-ET można połączyć poprzez dodanie lub inną funkcję, ponieważ nie ma ograniczeń co do rodzaju funkcji łączenia, którą można wybrać. Niektóre przykłady bardziej złożonych łączników obejmują przyjęcie średniej, mediany, środka zakresu, progowanie ich sumy w celu dokonania klasyfikacji dwumianowej, zastosowanie funkcji sigmoidalnej do obliczenia prawdopodobieństwa i tak dalej. Te funkcje łączące są zwykle wybierane a priori dla każdego problemu, ale mogą być również elegancko i wydajnie ewoluowane przez komórkowy system programowania ekspresji genów.

Ponowne wykorzystanie komórek i kodu

W programowaniu ekspresji genów geny homeotyczne kontrolują interakcje różnych pod-ET lub modułów głównego programu. Ekspresja takich genów skutkuje różnymi głównymi programami lub komórkami, to znaczy określają, które geny ulegają ekspresji w każdej komórce i jak sub-ET każdej komórki oddziałują ze sobą. Innymi słowy, geny homeotyczne określają, które pod-ET są wywoływane i jak często w którym głównym programie lub komórce oraz jakiego rodzaju połączenia nawiązują między sobą.

Geny homeotyczne i system komórkowy

Geny homeotyczne mają dokładnie taki sam rodzaj organizacji strukturalnej jak normalne geny i są zbudowane przy użyciu identycznego procesu. Zawierają również domenę głowy i domenę ogona, z tą różnicą, że głowy zawierają teraz funkcje łączące i specjalny rodzaj terminali – terminali genowych – reprezentujących normalne geny. Ekspresja normalnych genów skutkuje jak zwykle różnymi sub-ET, które w systemie komórkowym nazywane są ADF (automatycznie definiowane funkcje). Jeśli chodzi o ogony, zawierają one tylko terminale genowe, czyli cechy pochodne generowane w locie przez algorytm.

Na przykład chromosom na rysunku ma trzy normalne geny i jeden gen homeotyczny i koduje główny program, który w sumie czterokrotnie wywołuje trzy różne funkcje, łącząc je w określony sposób.

Wyrażenie systemu jednokomórkowego z trzema ADF. a) Chromosom złożony z trzech konwencjonalnych genów i jednego genu homeotycznego (pokazany pogrubioną czcionką). b) ADF kodowane przez każdy konwencjonalny gen. c) Główny program lub komórka.

Z tego przykładu jasno wynika, że ​​system komórkowy nie tylko umożliwia nieograniczoną ewolucję funkcji łączących, ale także ponowne wykorzystanie kodu. I nie powinno być trudno zaimplementować rekurencję w tym systemie.

Wiele głównych programów i systemów wielokomórkowych

Systemy wielokomórkowe składają się z więcej niż jednego genu homeotycznego . Każdy gen homeotyczny w tym systemie łączy inną kombinację drzew subekspresji lub ADF, tworząc wiele komórek lub programów głównych.

Na przykład program pokazany na rysunku został utworzony przy użyciu systemu komórkowego z dwiema komórkami i trzema normalnymi genami.

Wyrażenie systemu wielokomórkowego z trzema ADF i dwoma głównymi programami. a) Chromosom złożony z trzech konwencjonalnych genów i dwóch genów homeotycznych (pokazany pogrubioną czcionką). b) ADF kodowane przez każdy konwencjonalny gen. c) Dwa różne programy główne wyrażone w dwóch różnych komórkach.

Zastosowania tych systemów wielokomórkowych są wielorakie i różnorodne i podobnie jak systemy wielogenowe mogą być stosowane zarówno w problemach z jednym wyjściem, jak iw problemach z wieloma wyjściami.

Inne poziomy złożoności

Domena głowa/ogon genów GEP (zarówno normalnych, jak i homeotycznych) jest podstawowym budulcem wszystkich algorytmów GEP. Jednak programowanie ekspresji genów bada również inne organizacje chromosomalne, które są bardziej złożone niż struktura głowy / ogona. Zasadniczo te złożone struktury składają się z jednostek funkcjonalnych lub genów z podstawową domeną głowa/ogon plus jedna lub więcej dodatkowych domen. Te dodatkowe domeny zwykle kodują losowe stałe liczbowe, które algorytm nieustannie dostraja, aby znaleźć dobre rozwiązanie. Na przykład te stałe liczbowe mogą być wagami lub czynnikami w problemie aproksymacji funkcji (patrz algorytm GEP-RNC poniżej); mogą to być wagi i progi sieci neuronowej (patrz algorytm GEP-NN poniżej); stałe numeryczne potrzebne do projektowania drzew decyzyjnych (patrz algorytm GEP-DT poniżej); wagi potrzebne do indukcji wielomianowej; lub losowe stałe liczbowe używane do wykrywania wartości parametrów w zadaniu optymalizacji parametrów.

Podstawowy algorytm ekspresji genów

Podstawowe kroki podstawowego algorytmu ekspresji genów są wymienione poniżej w pseudokodzie:

1. Wybierz zestaw funkcji;
2. Wybierz zestaw zacisków;
3. Załaduj zestaw danych do oceny sprawności;
4. Twórz losowo chromosomy początkowej populacji;
5. Dla każdego programu w populacji:
   1. Ekspresowy chromosom;
   2. Wykonaj program;
   3. Oceń sprawność;
6. Sprawdź stan zatrzymania;
7. Wybierz programy;
8. Replikuj wybrane programy, aby utworzyć następną populację;
9. Modyfikuj chromosomy za pomocą operatorów genetycznych;
10. Przejdź do kroku 5.

Pierwsze cztery kroki przygotowują wszystkie składniki potrzebne do pętli iteracyjnej algorytmu (kroki od 5 do 10). Spośród tych kroków przygotowawczych kluczowym jest utworzenie populacji początkowej, która jest tworzona losowo przy użyciu elementów funkcji i zbiorów końcowych.

Populacje programów

Jak wszystkie algorytmy ewolucyjne, programowanie ekspresji genów działa na populacjach osobników, które w tym przypadku są programami komputerowymi. Dlatego, aby zacząć, należy stworzyć jakąś populację początkową. Kolejne populacje są potomkami, poprzez selekcję i modyfikację genetyczną , populacji początkowej.

W systemie genotyp/fenotyp programowania ekspresji genów konieczne jest jedynie stworzenie prostych liniowych chromosomów osobników bez martwienia się o strukturalną poprawność programów, które kodują, ponieważ ich ekspresja zawsze skutkuje programami poprawnymi składniowo.

Funkcje sprawnościowe i środowisko selekcyjne

Funkcje sprawności i środowiska selekcji (zwane zestawami danych treningowych w uczeniu maszynowym ) to dwa aspekty sprawności i dlatego są ze sobą misternie powiązane. Rzeczywiście, przydatność programu zależy nie tylko od funkcji kosztu użytej do pomiaru jego wydajności, ale także od danych treningowych wybranych do oceny sprawności

Środowisko selekcji lub dane treningowe

Środowisko selekcji składa się z zestawu rekordów treningowych, które są również nazywane przypadkami dopasowania. Te przypadki dopasowania mogą być zbiorem obserwacji lub pomiarów dotyczących jakiegoś problemu i tworzą tak zwany zbiór danych treningowych.

Jakość danych treningowych ma zasadnicze znaczenie dla ewolucji dobrych rozwiązań. Dobry zestaw uczący powinien być reprezentatywny dla danego problemu, a także dobrze wyważony, w przeciwnym razie algorytm może utknąć w jakimś lokalnym optimum. Ponadto ważne jest również, aby unikać używania niepotrzebnie dużych zbiorów danych do szkolenia, ponieważ niepotrzebnie spowalnia to działanie. Dobrą praktyczną zasadą jest wybranie wystarczającej liczby rekordów do uczenia, aby umożliwić dobre uogólnienie danych walidacyjnych i pozostawienie pozostałych rekordów do walidacji i testowania.

Funkcje fitness

Mówiąc ogólnie, istnieją zasadniczo trzy różne rodzaje problemów w zależności od rodzaju przewidywania:

1. Problemy związane z predykcjami numerycznymi (ciągłymi);
2. Problemy dotyczące prognoz jakościowych lub nominalnych, zarówno dwumianowych, jak i wielomianowych;
3. Problemy związane z przewidywaniami binarnymi lub boolowskimi.

Pierwszy typ problemu nosi nazwę regresji ; druga jest znana jako klasyfikacja , z regresją logistyczną jako szczególnym przypadkiem, w którym oprócz wyraźnych klasyfikacji, takich jak „Tak” lub „Nie”, do każdego wyniku przypisane jest również prawdopodobieństwo; a ostatnia związana jest z algebrą Boole'a i syntezą logiczną .

Funkcje sprawności dla regresji

W regresji odpowiedź lub zmienna zależna jest liczbowa (zwykle ciągła), dlatego dane wyjściowe modelu regresji są również ciągłe. Dlatego dość łatwo jest ocenić przydatność ewoluujących modeli, porównując dane wyjściowe modelu z wartością odpowiedzi w danych treningowych.

Istnieje kilka podstawowych funkcji dopasowania służących do oceny wydajności modelu, z których najczęstsza opiera się na błędzie lub rezydualnej między wartością wyjściową modelu a rzeczywistą wartością. Takie funkcje obejmują średni błąd kwadratowy , pierwiastek błędu średniokwadratowego , średni błąd bezwzględny , względny błąd kwadratowy, pierwiastek względnego błędu kwadratowego, względny błąd bezwzględny i inne.

Wszystkie te standardowe środki zapewniają drobną ziarnistość lub gładkość przestrzeni rozwiązania i dlatego bardzo dobrze sprawdzają się w większości zastosowań. Ale niektóre problemy mogą wymagać bardziej zgrubnej ewolucji, takiej jak określenie, czy prognoza mieści się w określonym przedziale, na przykład mniej niż 10% rzeczywistej wartości. Jednak nawet jeśli ktoś jest zainteresowany tylko zliczaniem trafień (to znaczy prognozą mieszczącą się w wybranym przedziale), tworzenie populacji modeli ewoluujących tylko na podstawie liczby trafień, które uzyskuje każdy program, zwykle nie jest zbyt wydajne ze względu na zgrubne ziarnistość krajobrazu fitness . W związku z tym rozwiązanie zwykle polega na połączeniu tych zgrubnych miar z jakąś gładką funkcją, taką jak standardowe miary błędu wymienione powyżej.

Funkcje fitness oparte na współczynniku korelacji i R-kwadrat również są bardzo płynne. W przypadku problemów z regresją funkcje te działają najlepiej, łącząc je z innymi miarami, ponieważ same w sobie mają tendencję do mierzenia jedynie korelacji , nie dbając o zakres wartości danych wyjściowych modelu. Tak więc, łącząc je z funkcjami, które działają w przybliżeniu zakresu wartości docelowych, tworzą bardzo wydajne funkcje dopasowania do znajdowania modeli o dobrej korelacji i dobrym dopasowaniu między przewidywanymi a rzeczywistymi wartościami.

Funkcje sprawności dla klasyfikacji i regresji logistycznej

Projektowanie funkcji przystosowania dla klasyfikacji i regresji logistycznej wykorzystuje trzy różne cechy modeli klasyfikacyjnych. Najbardziej oczywistym jest po prostu liczenie trafień, to znaczy, jeśli rekord jest poprawnie sklasyfikowany, jest liczony jako trafienie. Ta funkcja dopasowania jest bardzo prosta i dobrze sprawdza się w przypadku prostych problemów, ale w przypadku bardziej złożonych problemów lub bardzo niezrównoważonych zestawów danych daje słabe wyniki.

Jednym ze sposobów poprawy tego typu funkcji sprawności opartej na trafieniach jest rozszerzenie pojęcia poprawnych i niepoprawnych klasyfikacji. W zadaniu klasyfikacji binarnej prawidłowa klasyfikacja może wynosić 00 lub 11. Reprezentacja „00” oznacza, że ​​przypadek negatywny (reprezentowany przez „0”) został poprawnie sklasyfikowany, natomiast „11” oznacza, że ​​przypadek pozytywny (reprezentowany przez „1 ”) została prawidłowo sklasyfikowana. Klasyfikacje typu „00” nazywane są prawdziwymi negatywami (TN) i „11” prawdziwymi pozytywami (TP).

Istnieją również dwa rodzaje błędnych klasyfikacji, które są reprezentowane przez 01 i 10. Nazywa się je fałszywie dodatnimi (FP), gdy rzeczywista wartość wynosi 0, a model przewiduje 1; i wyniki fałszywie ujemne (FN), gdy celem jest 1, a model przewiduje 0. Zliczenia TP, TN, FP i FN są zwykle przechowywane w tabeli znanej jako macierz zamieszania .

Macierz zamieszania dla zadania klasyfikacji dwumianowej.

		Przewidywana klasa
		Tak	NIE
Rzeczywista klasa	Tak	TP	FN
	NIE	FP	TN

Tak więc, licząc TP, TN, FP i FN, a następnie przypisując różne wagi tym czterem typom klasyfikacji, możliwe jest stworzenie płynniejszych, a tym samym bardziej wydajnych funkcji fitness. Niektóre popularne funkcje fitness oparte na macierzy zamieszania obejmują czułość/swoistość , przywołanie/precyzję , miarę F , podobieństwo Jaccarda , współczynnik korelacji Matthewsa oraz macierz kosztów/zysków, która łączy koszty i zyski przypisane do 4 różnych typów klasyfikacji.

Te funkcje oparte na macierzy zamieszania są dość wyrafinowane i są wystarczające do skutecznego rozwiązania większości problemów. Istnieje jednak inny wymiar modeli klasyfikacyjnych, który jest kluczem do wydajniejszego eksplorowania przestrzeni rozwiązań, a tym samym prowadzi do odkrycia lepszych klasyfikatorów. Ten nowy wymiar obejmuje badanie struktury samego modelu, która obejmuje nie tylko dziedzinę i zakres, ale także rozkład danych wyjściowych modelu i margines klasyfikatora.

Eksplorując ten inny wymiar modeli klasyfikacyjnych, a następnie łącząc informacje o modelu z macierzą zamieszania, możliwe jest zaprojektowanie bardzo wyrafinowanych funkcji dopasowania, które pozwalają na płynną eksplorację przestrzeni rozwiązań. Na przykład można połączyć pewną miarę opartą na macierzy zamieszania z błędem średniokwadratowym obliczonym między surowymi wynikami modelu a rzeczywistymi wartościami. Lub połącz miarę F z obliczonym R-kwadratem dla surowego wyniku modelu i wartości docelowej; lub macierz kosztów/zysków ze współczynnikiem korelacji i tak dalej. Bardziej egzotyczne funkcje fitness, które badają ziarnistość modelu, obejmują obszar pod krzywą ROC i miarę rang.

Z tym nowym wymiarem modeli klasyfikacyjnych związana jest również idea przypisania prawdopodobieństw wynikom modelu, co ma miejsce w przypadku regresji logistycznej . Następnie możliwe jest również wykorzystanie tych prawdopodobieństw i oszacowanie błędu średniokwadratowego (lub innej podobnej miary) między prawdopodobieństwami a rzeczywistymi wartościami, a następnie połączenie tego z macierzą zamieszania w celu stworzenia bardzo wydajnych funkcji dopasowania dla regresji logistycznej. Popularne przykłady funkcji dopasowania opartych na prawdopodobieństwach obejmują oszacowanie największej wiarygodności i utratę zawiasów .

Funkcje przystosowania dla problemów boolowskich

W logice nie ma struktury modelu (jak zdefiniowano powyżej dla klasyfikacji i regresji logistycznej) do zbadania: dziedzina i zakres funkcji logicznych obejmuje tylko 0 i 1 lub fałsz i prawdę. Tak więc funkcje dopasowania dostępne dla algebry Boole'a mogą być oparte tylko na trafieniach lub na macierzy zamieszania, jak wyjaśniono w sekcji powyżej .

Selekcja i elitaryzm

Selekcja na kole ruletki jest prawdopodobnie najpopularniejszym schematem selekcji stosowanym w obliczeniach ewolucyjnych. Polega na odwzorowaniu sprawności każdego programu na wycinku koła ruletki proporcjonalnym do jego przydatności. Następnie ruletka jest obracana tyle razy, ile jest programów w populacji, aby utrzymać stałą wielkość populacji. Tak więc programy selekcji na kole ruletki są wybierane zarówno w zależności od kondycji, jak i szczęścia w losowaniu, co oznacza, że ​​czasami najlepsze cechy mogą zostać utracone. Jednak łącząc selekcję na kole ruletki z klonowaniem najlepszego programu każdej generacji, gwarantuje się, że przynajmniej najlepsze cechy nie zostaną utracone. Ta technika klonowania najlepszego programu generacji jest znana jako prosty elitaryzm i jest używana przez większość stochastycznych schematów selekcji.

Reprodukcja z modyfikacją

Reprodukcja programów obejmuje najpierw selekcję, a następnie reprodukcję ich genomów. Modyfikacja genomu nie jest wymagana do reprodukcji, ale bez niej adaptacja i ewolucja nie będą miały miejsca.

Replikacja i selekcja

Operator wyboru wybiera programy do skopiowania przez operatora replikacji. W zależności od schematu wyboru, liczba kopii tworzonych przez jeden program może się różnić, przy czym niektóre programy są kopiowane więcej niż raz, podczas gdy inne są kopiowane tylko raz lub wcale. Ponadto selekcja jest zwykle ustawiona w taki sposób, aby wielkość populacji pozostawała stała z pokolenia na pokolenie.

Replikacja genomów w przyrodzie jest bardzo złożona i naukowcom zajęło dużo czasu odkrycie podwójnej helisy DNA i zaproponowanie mechanizmu jej replikacji. Ale replikacja strun jest trywialna w sztucznych systemach ewolucyjnych, gdzie wystarczy tylko instrukcja kopiowania strun, aby przekazać wszystkie informacje w genomie z pokolenia na pokolenie.

Replikacja wybranych programów jest fundamentalnym elementem wszystkich sztucznych systemów ewolucyjnych, ale aby mogła zajść ewolucja, musi być realizowana nie ze zwykłą precyzją instrukcji kopiowania, ale raczej z kilkoma dodanymi błędami. Rzeczywiście, różnorodność genetyczna jest utworzone za pomocą operatorów genetycznych, takich jak mutacja , rekombinacja , transpozycja , inwersja i wiele innych.

Mutacja

W programowaniu ekspresji genów mutacja jest najważniejszym operatorem genetycznym. Zmienia genomy, zmieniając jeden element na inny. Nagromadzenie wielu małych zmian w czasie może stworzyć wielką różnorodność.

W programowaniu ekspresji genów mutacja jest całkowicie nieograniczona, co oznacza, że ​​w każdej domenie genowej dowolny symbol domeny można zastąpić innym. Na przykład w głowach genów dowolną funkcję można zastąpić terminalem lub inną funkcją, niezależnie od liczby argumentów w tej nowej funkcji; a terminal można zastąpić funkcją lub innym terminalem.

Rekombinacja

Rekombinacja zwykle obejmuje dwa chromosomy rodzicielskie w celu utworzenia dwóch nowych chromosomów poprzez połączenie różnych części z chromosomów rodzicielskich. I dopóki chromosomy rodzicielskie są wyrównane, a wymieniane fragmenty są homologiczne (to znaczy zajmują tę samą pozycję w chromosomie), nowe chromosomy powstałe w wyniku rekombinacji zawsze będą kodować programy poprawne składniowo.

Różne rodzaje krzyżowania można łatwo wdrożyć, zmieniając liczbę zaangażowanych rodziców (nie ma powodu, aby wybierać tylko dwóch); liczba punktów podziału; lub sposób, w jaki ktoś wybiera wymianę fragmentów, na przykład losowo lub w jakiś uporządkowany sposób. Na przykład rekombinację genów, która jest szczególnym przypadkiem rekombinacji, można przeprowadzić poprzez wymianę genów homologicznych (genów zajmujących tę samą pozycję w chromosomie) lub przez wymianę genów wybranych losowo z dowolnej pozycji w chromosomie.

Transpozycja

Transpozycja polega na wprowadzeniu sekwencji insercyjnej gdzieś w chromosomie. W programowaniu ekspresji genów sekwencje insercyjne mogą pojawić się w dowolnym miejscu chromosomu, ale są wstawiane tylko w głowach genów. Ta metoda gwarantuje, że nawet sekwencje wstawiania z ogonów dają programy wolne od błędów.

Aby transpozycja działała prawidłowo, musi zachować długość chromosomu i strukturę genu. Tak więc w programowaniu ekspresji genów transpozycję można zaimplementować przy użyciu dwóch różnych metod: pierwsza tworzy przesunięcie w miejscu insercji, po którym następuje usunięcie na końcu głowy; druga zastępuje lokalną sekwencję w miejscu docelowym i dlatego jest łatwiejsza do wdrożenia. Obie metody można zaimplementować do działania między chromosomami lub w obrębie chromosomu, a nawet w obrębie pojedynczego genu.

Inwersja

Inwersja jest interesującym operatorem, szczególnie przydatnym w optymalizacji kombinatorycznej . Polega na odwróceniu małej sekwencji w obrębie chromosomu.

W programowaniu ekspresji genów można go łatwo zaimplementować we wszystkich domenach genów i we wszystkich przypadkach wyprodukowane potomstwo jest zawsze poprawne składniowo. W przypadku dowolnej domeny genowej sekwencja (od co najmniej dwóch elementów do wielkości samej domeny) jest wybierana losowo w obrębie tej domeny, a następnie odwracana.

Inni operatorzy genetyczni

Istnieje kilka innych operatorów genetycznych, aw programowaniu ekspresji genów, z różnymi genami i domenami genów, możliwości są nieograniczone. Na przykład operatory genetyczne, takie jak rekombinacja jednopunktowa, rekombinacja dwupunktowa, rekombinacja genów, rekombinacja jednolita, transpozycja genu, transpozycja korzenia, mutacja specyficzna dla domeny, inwersja specyficzna dla domeny, transpozycja specyficzna dla domeny itd. wdrożony i szeroko stosowany.

Algorytm GEP-RNC

Stałe liczbowe są istotnymi elementami modeli matematycznych i statystycznych, dlatego ważne jest, aby umożliwić ich integrację w modelach projektowanych przez algorytmy ewolucyjne.

Programowanie ekspresji genów bardzo elegancko rozwiązuje ten problem, wykorzystując dodatkową domenę genu – Dc – do obsługi losowych stałych numerycznych (RNC). Łącząc tę ​​domenę ze specjalnym symbolem zastępczym terminala dla RNC, można stworzyć bogaty w ekspresję system.

Strukturalnie Dc występuje po ogonie, ma długość równą rozmiarowi ogona t i składa się z symboli używanych do reprezentowania RNC.

Na przykład poniżej pokazano prosty chromosom składający się tylko z jednego genu o wielkości głowy 7 (Dc rozciąga się na pozycjach 15–22):

01234567890123456789012

+?*+?**aaa??aaa68083295

gdzie terminal „?” reprezentuje symbol zastępczy dla RNC. Ten rodzaj chromosomu jest wyrażony dokładnie tak, jak pokazano powyżej , dając:

Następnie znaki ? w drzewie wyrażeń są zastępowane od lewej do prawej i od góry do dołu symbolami (dla uproszczenia reprezentowanymi przez cyfry) w Dc, co daje:

Wartości odpowiadające tym symbolom są przechowywane w tablicy. (Dla uproszczenia liczba reprezentowana przez cyfrę wskazuje kolejność w tablicy.) Na przykład dla następującej 10-elementowej tablicy RNC:

C = {0,611, 1,184, 2,449, 2,98, 0,496, 2,286, 0,93, 2,305, 2,737, 0,755}

powyższe drzewo wyrażeń daje:

Ta elegancka struktura do obsługi losowych stałych liczbowych jest sercem różnych systemów GEP, takich jak sieci neuronowe GEP i drzewa decyzyjne GEP .

Podobnie jak podstawowy algorytm ekspresji genów , algorytm GEP-RNC jest również wielogenowy, a jego chromosomy są dekodowane w zwykły sposób poprzez ekspresję jednego genu po drugim, a następnie łączenie ich wszystkich razem za pomocą tego samego rodzaju procesu łączenia.

Operatory genetyczne stosowane w systemie GEP-RNC są rozszerzeniem operatorów genetycznych podstawowego algorytmu GEP (patrz wyżej ) i wszystkie można bezpośrednio zaimplementować w tych nowych chromosomach. Z drugiej strony w algorytmie GEP-RNC wykorzystywane są również podstawowe operatory mutacji, inwersji, transpozycji i rekombinacji. Ponadto specjalne operatory specyficzne dla Dc, takie jak mutacja, inwersja i transpozycja, są również wykorzystywane do pomocy w wydajniejszym obiegu RNC między poszczególnymi programami. Ponadto istnieje również specjalny operator mutacji, który pozwala na stałe wprowadzanie zmienności w zbiorze RNC. Początkowy zestaw RNC jest tworzony losowo na początku cyklu, co oznacza, że ​​dla każdego genu w początkowej populacji generowana jest losowo określona liczba stałych liczbowych wybranych z określonego zakresu. Wtedy ich krążenie i mutacje umożliwiają operatorzy genetyczni.

Sieci neuronowe

Sztuczna sieć neuronowa (ANN lub NN) to urządzenie obliczeniowe, które składa się z wielu prostych połączonych jednostek lub neuronów. Połączenia między jednostkami są zwykle ważone wagami o wartościach rzeczywistych. Wagi te są podstawowym sposobem uczenia się w sieciach neuronowych, a algorytm uczenia się jest zwykle używany do ich dostosowania.

Strukturalnie sieć neuronowa ma trzy różne klasy jednostek: jednostki wejściowe, jednostki ukryte i jednostki wyjściowe. Wzorzec aktywacji jest prezentowany w jednostkach wejściowych, a następnie rozprzestrzenia się w kierunku do przodu od jednostek wejściowych przez jedną lub więcej warstw jednostek ukrytych do jednostek wyjściowych. Aktywacja przychodząca do jednej jednostki z drugiej jednostki jest mnożona przez ciężary na łączach, na których się rozprzestrzenia. Wszystkie przychodzące aktywacje są następnie sumowane, a jednostka zostaje aktywowana tylko wtedy, gdy przychodzący wynik przekracza próg jednostki.

Podsumowując, podstawowymi składnikami sieci neuronowej są jednostki, połączenia między jednostkami, wagi i progi. Tak więc, aby w pełni zasymulować sztuczną sieć neuronową, należy w jakiś sposób zakodować te składniki w liniowym chromosomie, a następnie móc wyrazić je w znaczący sposób.

W sieciach neuronowych GEP (sieci GEP-NN lub GEP) architektura sieci jest zakodowana w zwykłej strukturze domeny head/tail. Głowa zawiera specjalne funkcje/neurony, które aktywują jednostki ukryte i wyjściowe (w kontekście GEP wszystkie te jednostki są bardziej odpowiednio nazywane jednostkami funkcjonalnymi) oraz terminale reprezentujące jednostki wejściowe. Ogon, jak zwykle, zawiera tylko terminale/jednostki wejściowe.

Oprócz głowy i ogona te geny sieci neuronowej zawierają dwie dodatkowe domeny, Dw i Dt, do kodowania wag i progów sieci neuronowej. Strukturalnie Dw występuje po ogonie, a jego długość dw _jest zależy od rozmiaru głowy h i maksymalnej arności n _{max i} obliczana według wzoru:

${\ Displaystyle d_ {w} = hn_ {\ max}}$

Dt występuje po Dw i ma długość d _t równą t . Obie domeny składają się z symboli reprezentujących wagi i progi sieci neuronowej.

Dla każdego genu NN wagi i progi są tworzone na początku każdego przebiegu, ale ich krążenie i adaptacja są gwarantowane przez zwykłe operatory genetyczne mutacji , transpozycji , inwersji i rekombinacji . Ponadto stosowane są również specjalne operatory umożliwiające stały przepływ zmienności genetycznej w zestawie wag i progów.

Na przykład poniżej pokazano sieć neuronową z dwoma jednostkami wejściowymi ( i ₁ i i ₂ ), dwoma jednostkami ukrytymi ( h ₁ i h ₂ ) oraz jedną jednostką wyjściową ( o ₁ ). Ma w sumie sześć połączeń z sześcioma odpowiadającymi im wagami reprezentowanymi przez cyfry 1–6 (dla uproszczenia wszystkie progi są równe 1 i są pomijane):

Ta reprezentacja jest kanoniczną reprezentacją sieci neuronowej, ale sieci neuronowe mogą być również reprezentowane przez drzewo, które w tym przypadku odpowiada:

gdzie „a” i „b” reprezentują dwa wejścia i ₁ i i ₂ , a „D” reprezentuje funkcję z łącznością 2. Ta funkcja dodaje wszystkie ważone argumenty, a następnie ustala próg aktywacji w celu określenia przekazanego wyjścia. To wyjście (zero lub jeden w tym prostym przypadku) zależy od progu każdej jednostki, to znaczy, jeśli całkowita przychodząca aktywacja jest równa lub większa od progu, wtedy wyjście wynosi jeden, w przeciwnym razie zero.

Powyższe drzewo NN można zlinearyzować w następujący sposób:

0123456789012

DDDabab654321

gdzie struktura w pozycjach 7–12 (Dw) koduje wagi. Wartości każdej wagi są przechowywane w tablicy i pobierane w razie potrzeby do wyrażenia.

Jako bardziej konkretny przykład, poniżej pokazano gen sieci neuronowej dla wyłączności lub problemu. Ma rozmiar głowy 3 i rozmiar Dw 6:

0123456789012

DDDabab393257

Jego wyrażenie skutkuje następującą siecią neuronową:

co dla zestawu odważników:

W = {-1,978, 0,514, -0,465, 1,22, -1,686, -1,797, 0,197, 1,606, 0, 1,753}

to daje:

który jest idealnym rozwiązaniem dla funkcji wyłącznej lub.

Oprócz prostych funkcji boolowskich z wejściami i wyjściami binarnymi, algorytm GEP-nets może obsługiwać wszystkie rodzaje funkcji lub neuronów (neuronów liniowych, neuronów tanh, neuronów atan, neuronów logistycznych, neuronów granicznych, neuronów o podstawie radialnej i trójkątnej, wszelkiego rodzaju neurony krokowe i tak dalej). Interesujące jest również to, że algorytm GEP-nets może wykorzystywać wszystkie te neurony razem i pozwolić ewolucji zdecydować, które z nich działają najlepiej, aby rozwiązać dany problem. Tak więc sieci GEP mogą być używane nie tylko w problemach boolowskich, ale także w regresji logistycznej , klasyfikacji i regresji . We wszystkich przypadkach sieci GEP mogą być realizowane nie tylko z systemami wielogenowymi , ale także z systemami komórkowymi , zarówno jednokomórkowymi, jak i wielokomórkowymi. Co więcej, wielomianowe problemy z klasyfikacją mogą być rozwiązywane za jednym zamachem przez sieci GEP, zarówno z systemami multigenicznymi, jak i systemami wielokomórkowymi.

Drzewa decyzyjne

Drzewa decyzyjne (DT) to modele klasyfikacyjne, w których serie pytań i odpowiedzi są odwzorowywane za pomocą węzłów i skierowanych krawędzi.

Drzewa decyzyjne mają trzy typy węzłów: węzeł główny, węzły wewnętrzne oraz węzły liściowe lub końcowe. Węzeł główny i wszystkie węzły wewnętrzne reprezentują warunki testowe dla różnych atrybutów lub zmiennych w zbiorze danych. Węzły liści określają etykietę klasy dla wszystkich różnych ścieżek w drzewie.

Większość algorytmów indukcji drzew decyzyjnych polega na wybraniu atrybutu dla węzła głównego, a następnie podjęciu tego samego rodzaju świadomej decyzji dotyczącej wszystkich węzłów w drzewie.

Drzewa decyzyjne można również tworzyć za pomocą programowania ekspresji genów, z tą zaletą, że wszystkie decyzje dotyczące wzrostu drzewa są podejmowane przez sam algorytm bez jakiegokolwiek udziału człowieka.

Zasadniczo istnieją dwa różne typy algorytmów DT: jeden do indukowania drzew decyzyjnych tylko z atrybutami nominalnymi, a drugi do indukowania drzew decyzyjnych z atrybutami zarówno numerycznymi, jak i nominalnymi. Ten aspekt indukcji drzewa decyzyjnego dotyczy również programowania ekspresji genów i istnieją dwa algorytmy GEP do indukcji drzewa decyzyjnego: algorytm ewolucyjnych drzew decyzyjnych (EDT) do radzenia sobie wyłącznie z atrybutami nominalnymi i EDT-RNC (EDT z losowymi stałymi liczbowymi) do obsługują zarówno atrybuty nominalne, jak i liczbowe.

W drzewach decyzyjnych indukowanych przez programowanie ekspresji genów atrybuty zachowują się jak węzły funkcyjne w podstawowym algorytmie ekspresji genów , podczas gdy etykiety klas zachowują się jak terminale. Oznacza to, że węzły atrybutów mają również powiązaną z nimi określoną liczbę lub liczbę gałęzi, które będą determinować ich wzrost, a ostatecznie wzrost drzewa. Etykiety klas zachowują się jak terminale, co oznacza, że ​​dla k -klas używany jest zestaw terminali z k terminalami reprezentującymi k różnych klas.

Zasady kodowania drzewa decyzyjnego w liniowym genomie są bardzo podobne do zasad używanych do kodowania wyrażeń matematycznych (patrz wyżej ). Tak więc, dla indukcji drzewa decyzyjnego, geny mają również głowę i ogon, przy czym głowa zawiera atrybuty i końcówki, a ogon zawiera tylko końcówki. To ponownie zapewnia, że ​​wszystkie drzewa decyzyjne zaprojektowane przez GEP są zawsze poprawnymi programami. Ponadto rozmiar ogona t jest również podyktowany rozmiarem głowy h i liczbą gałęzi atrybutu z większą liczbą gałęzi n _max i jest obliczany za pomocą równania:

${\ Displaystyle t = h (n _ {\ max} -1) + 1 \,}$

Rozważmy na przykład poniższe drzewo decyzyjne, aby zdecydować, czy bawić się na zewnątrz:

Można to zakodować liniowo jako:

01234567

JAK baaba

gdzie „H” reprezentuje atrybut Humidity, „O” atrybut Outlook, „W” reprezentuje Windy, a „a” i „b” oznaczają klasy odpowiednio „Tak” i „Nie”. Należy zauważyć, że krawędzie łączące węzły są właściwościami danych, określającymi typ i liczbę rozgałęzień każdego atrybutu, a zatem nie muszą być kodowane.

Proces indukcji drzewa decyzyjnego wraz z programowaniem ekspresji genów zaczyna się, jak zwykle, od początkowej populacji losowo utworzonych chromosomów. Następnie chromosomy są wyrażane jako drzewa decyzyjne, a ich przydatność oceniana jest w zestawie danych szkoleniowych. Zgodnie z przydatnością są następnie wybierane do reprodukcji z modyfikacją. Operatory genetyczne są dokładnie takie same jak w konwencjonalnym systemie unigenicznym, na przykład mutacja , inwersja , transpozycja i rekombinacja .

powyżej struktury dotyczącej losowych stałych liczbowych. Architektura chromosomalna zawiera dodatkową domenę do kodowania losowych stałych liczbowych, które są używane jako progi do dzielenia danych w każdym rozgałęzionym węźle. Na przykład poniższy gen o rozmiarze głowy 5 (Dc zaczyna się na pozycji 16):

012345678901234567890

WOTHabababbbabba46336

koduje drzewo decyzyjne pokazane poniżej:

W tym systemie każdy węzeł w nagłówku, niezależnie od jego typu (atrybut liczbowy, atrybut nominalny lub końcowy), jest powiązany z losową stałą liczbową, która dla uproszczenia w powyższym przykładzie jest reprezentowana przez cyfrę 0–9. Te losowe stałe liczbowe są zakodowane w domenie Dc, a ich wyrażenie odbywa się według bardzo prostego schematu: od góry do dołu i od lewej do prawej elementy w Dc są przypisywane jeden po drugim do elementów w drzewie decyzyjnym. Tak więc dla następującej tablicy RNC:

C = {62, 51, 68, 83, 86, 41, 43, 44, 9, 67}

powyższe drzewo decyzyjne skutkuje:

które można również przedstawić bardziej kolorowo jako konwencjonalne drzewo decyzyjne:

Krytyka

GEP był krytykowany za to, że nie jest znaczącym ulepszeniem w stosunku do innych technik programowania genetycznego . W wielu eksperymentach nie działał lepiej niż istniejące metody.

Oprogramowanie

Aplikacje komercyjne

GeneXproTools

GeneXproTools to pakiet do analizy predykcyjnej opracowany przez firmę Gepsoft. Ramy modelowania GeneXproTools obejmują regresję logistyczną , klasyfikację , regresję , przewidywanie szeregów czasowych i syntezę logiczną . GeneXproTools implementuje podstawowy algorytm ekspresji genów i algorytm GEP-RNC , oba używane we wszystkich ramach modelowania GeneXproTools.

Biblioteki open-source

GEP4J – projekt GEP for Java

Stworzony przez Jasona Thomasa, GEP4J to implementacja typu open source do programowania ekspresji genów w Javie . Implementuje różne algorytmy GEP, w tym ewoluujące drzewa decyzyjne (z atrybutami nominalnymi, numerycznymi lub mieszanymi) oraz automatycznie definiowane funkcje . GEP4J jest hostowany w Google Code .

PyGEP — programowanie ekspresji genów w języku Python

Stworzony przez Ryana O'Neila w celu stworzenia prostej biblioteki odpowiedniej do akademickich badań nad programowaniem ekspresji genów w języku Python , mającej na celu łatwość użycia i szybkie wdrożenie. Implementuje standardowe chromosomy wielogenowe oraz mutację, krzyżowanie i transpozycję operatorów genetycznych. PyGEP jest hostowany w Google Code .

jGEP — zestaw narzędzi Java GEP

Stworzony przez Matthew Sottile w celu szybkiego tworzenia prototypowych kodów Java wykorzystujących GEP, które można następnie napisać w języku takim jak C lub Fortran z prawdziwą szybkością. jGEP jest hostowany w SourceForge .

Dalsza lektura

•   Ferreira, C. (2006). Programowanie ekspresji genów: modelowanie matematyczne przez sztuczną inteligencję . Springer-Verlag. ISBN 3-540-32796-7 .
•   Ferreira, C. (2002). Programowanie ekspresji genów: modelowanie matematyczne przez sztuczną inteligencję . Portugalia: Angra do Heroismo. ISBN 972-95890-5-4 .

Zobacz też

• Regresja symboliczna
• Sztuczna inteligencja
• Drzewa decyzyjne
• Algorytmy ewolucyjne
• Algorytmy genetyczne
• Programowanie genetyczne
• Ewolucja gramatyczna
• Liniowe programowanie genetyczne
• Narzędzia GeneXpro
• Nauczanie maszynowe
• Programowanie wielu wyrażeń
• Sieci neuronowe

Linki zewnętrzne

• Strona główna GEP , prowadzona przez wynalazcę programowania ekspresji genów.
• GeneXproTools , komercyjne oprogramowanie GEP.