Programowanie ekspresji genów - Gene expression programming

W programowaniu komputerowym , programowanie ekspresji genów (GEP) to ewolucyjny algorytm , który tworzy programy lub modeli komputerowych. Te programy komputerowe to złożone struktury drzewiaste, które uczą się i przystosowują, zmieniając swoje rozmiary, kształty i skład, podobnie jak żywy organizm. I podobnie jak żywe organizmy, programy komputerowe GEP są również zakodowane w prostych liniowych chromosomach o ustalonej długości. GEP jest zatem systemem genotyp-fenotyp , korzystającym z prostego genomu do przechowywania i przekazywania informacji genetycznej oraz złożonego fenotypu do badania środowiska i adaptacji 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ę od lat 50. XX wieku, kiedy służyły do ​​rozwiązywania problemów optymalizacyjnych (np. Box 1957 i Friedman 1959). Ale dopiero wraz z wprowadzeniem strategii ewolucyjnych przez Rechenberga w 1965 roku algorytmy ewolucyjne zyskały popularność. Dobrym przeglądowym tekstem na temat 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 ściśle związane z algorytmami genetycznymi i programowaniem genetycznym . Z algorytmów genetycznych odziedziczył chromosomy liniowe o ustalonej długości; a z programowania genetycznego odziedziczył ekspresyjne drzewa parsowania o różnych rozmiarach i kształtach.

W programowaniu ekspresji genów chromosomy liniowe działają jako genotyp, a drzewa analizują jako fenotyp, tworząc system genotyp/fenotyp . Ten system genotyp/fenotyp jest wielogenowy , kodując w ten sposób wiele drzew 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 łańcucha lub chromosomu o ustalonej długości, składającego się z jednego lub więcej genów o jednakowej wielkości. Te geny, pomimo ich stałej 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 ciąg (pozycja zero wskazuje 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 , geny programowania ekspresji genów mają wszystkie te same rozmiary. 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że być również reprezentowany jako drzewo wyrażeń :

gdzie „Q” reprezentuje funkcję pierwiastka kwadratowego.

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

01234567

Q*-+abcd

czyli prosty odczyt drzewa wyrażeń od góry do dołu i od lewej do prawej. Te ciągi liniowe nazywane są wyrażeniami k (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 terminali (zmiennych „a” i „b”), dwóch różnych funkcji dwuargumentowych („*” i „+”) oraz funkcji jednego argumentu („Q”). Jej wyraz daje:

K-ekspresje i geny

Ekspresja k programowania ekspresji genów odpowiada regionowi genów, które ulegają ekspresji. Oznacza to, że w genach mogą znajdować się sekwencje, które nie ulegają ekspresji, co jest prawdą w przypadku większości genów. Powodem tych niekodujących regionów jest zapewnienie bufora terminali, tak aby wszystkie wyrażenia k zakodowane w genach GEP zawsze odpowiadały prawidłowym 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łowica służy 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 określa wzór:

${\ Displaystyle t = h (n_ {\ max}-1) + 1}$

gdzie h to długość głowy, a n _max to maksymalna arność. Na przykład dla genu utworzonego za pomocą zbioru funkcji F = {Q, +, −, ∗, /} i zbioru terminali T = {a, b}, n _max = 2. A jeśli wybierzemy długość głowy 15, a następnie t = 15 (2–1) + 1 = 16, co daje długość genu g wynoszącą 15 + 16 = 31. Poniższy losowo wygenerowany ciąg jest przykładem jednego takiego genu:

0123456789012345678901234567890

*b+a-aQab+//+b+babbabbbababbaaa

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 może kodować drzewa ekspresyjne o różnych rozmiarach i kształtach, przy czym najprostszy składa się tylko z jednego węzła (gdy pierwszy element genu jest terminalem) 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 arystotywności).

Nietrudno też zauważyć, że wprowadzenie wszelkiego rodzaju modyfikacji genetycznych ( mutacji , inwersji, insercji, rekombinacji itd.) z gwarancją, że wszystkie powstałe potomstwo zakodują poprawne, bezbłędne programy.

Chromosomy wielogenowe

Chromosomy programowania ekspresji genów zwykle składają się z więcej niż jednego genu o jednakowej długości. Każdy gen koduje drzewo podwyrażeń (sub-ET) lub podprogram. Wtedy pod-ET mogą oddziaływać ze sobą na różne sposoby, tworząc bardziej złożony program. Rysunek przedstawia przykład programu składającego się z trzech pod-ET.

Ekspresja genów GEP jako sub-ET. a) Trójgenowy chromosom z ogonami pogrubionymi. b) Sub-ET kodowane przez każdy gen.

W końcowym programie pod-ET mogą być połączone przez dodanie lub inną funkcję, ponieważ nie ma ograniczeń co do rodzaju funkcji łączenia, jaką można wybrać. Niektóre przykłady bardziej złożonych łączników obejmują wzię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.

Komórki i ponowne użycie kodu

W programowaniu ekspresji genów geny homeotyczne kontrolują interakcje różnych pod-ET lub modułów programu głównego. 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 pod-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 jakim głównym programie lub komórce oraz jakiego rodzaju połączenia ze sobą nawiązują.

Geny homeotyczne a układ komórkowy

Geny homeotyczne mają dokładnie taki sam rodzaj organizacji strukturalnej jak normalne geny i są budowane w identycznym procesie. 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 – terminale genowe – które reprezentują normalne geny. Ekspresja normalnych genów jak zwykle skutkuje w różnych pod-ET, które w systemie komórkowym nazywane są ADF (funkcje definiowane automatycznie). Jeśli chodzi o ogony, zawierają one tylko końcówki genowe, czyli cechy pochodne generowane w locie przez algorytm.

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

Ekspresja systemu jednokomórkowego z trzema ADF. a) Chromosom złożony z trzech genów konwencjonalnych i jednego genu homeotycznego (pogrubiony). 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 łączenia, ale także ponowne wykorzystanie kodu. A implementacja rekurencji w tym systemie nie powinna być trudna .

Wiele programów głównych 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 podekspresji lub ADF, tworząc wiele komórek lub programów głównych.

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

Ekspresja systemu wielokomórkowego z trzema ADF i dwoma głównymi programami. a) Chromosom złożony z trzech genów konwencjonalnych i dwóch genów homeotycznych (pogrubiony). 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ą liczne i zróżnicowane i podobnie jak systemy wielogenowe mogą być wykorzystywane zarówno w problemach z jednym wyjściem, jak i w 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łowa/ogon. Zasadniczo te złożone struktury składają się z jednostek funkcjonalnych lub genów z podstawową domeną głowy/ogonu plus jedną lub więcej dodatkowych domen. Te dodatkowe domeny zwykle kodują losowe stałe liczbowe, które algorytm nieustannie dostraja w celu znalezienia dobrego rozwiązania. Na przykład te stałe numeryczne mogą być wagami lub współ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 terminali;
3. Załaduj zestaw danych do oceny sprawności;
4. Utwórz losowo chromosomy populacji początkowej;
5. Dla każdego programu w populacji:
   1. Ekspresja chromosomu;
   2. Wykonaj program;
   3. Oceń sprawność fizyczną;
6. Sprawdź warunek 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 iteracyjnej pętli algorytmu (kroki od 5 do 10). Spośród tych kroków przygotowawczych, kluczowym jest stworzenie 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 z populacjami osobników, którymi w tym przypadku są programy komputerowe. Dlatego trzeba stworzyć pewien rodzaj populacji początkowej, aby zacząć. Kolejne populacje są potomkami, poprzez selekcję i modyfikację genetyczną , populacji początkowej.

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

Funkcje fitness i środowisko selekcji

Funkcje fitness i środowiska selekcji (nazywane treningowymi zestawami danych w uczeniu maszynowym ) to dwa aspekty sprawności i dlatego są ze sobą misternie powiązane. Rzeczywiście, sprawność 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 zapisów treningowych, zwanych również przypadkami sprawności. Te przypadki sprawnościowe mogą być zbiorem obserwacji lub pomiarów dotyczących jakiegoś problemu i tworzą tak zwany zestaw danych treningowych.

Jakość danych treningowych ma kluczowe znaczenie dla rozwoju dobrych rozwiązań. Dobry zestaw treningowy 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 zestawów danych do trenowania, ponieważ spowoduje to niepotrzebne spowolnienie działania. Dobrą zasadą jest wybranie wystarczającej liczby rekordów do szkolenia, aby umożliwić dobre uogólnienie danych walidacyjnych i pozostawienie pozostałych rekordów do walidacji i testowania.

Funkcje fitness

Ogólnie rzecz biorąc, istnieją zasadniczo trzy różne rodzaje problemów w zależności od rodzaju dokonywanej prognozy:

1. Problemy dotyczące prognoz numerycznych (ciągłych);
2. Problemy związane z przewidywaniami kategorialnymi lub nominalnymi, zarówno dwumianowymi, jak i wielomianowymi;
3. Problemy związane z przewidywaniami binarnymi lub boolowskimi.

Pierwszy rodzaj problemu nosi nazwę regresji ; drugi jest znany jako klasyfikacja , przy czym regresja logistyczna jest szczególnym przypadkiem, w którym oprócz ostrych klasyfikacji, takich jak „Tak” lub „Nie”, do każdego wyniku jest również przypisane prawdopodobieństwo; a ostatni jest związany z algebrą Boole'a i syntezą logiczną .

Funkcje fitness do regresji

W regresji odpowiedź lub zmienna zależna jest liczbowa (zwykle ciągła), a zatem wynik modelu regresji jest również ciągły. Tak więc ocena przydatności ewoluujących modeli jest dość prosta, porównując dane wyjściowe modelu z wartością odpowiedzi w danych treningowych.

Istnieje kilka podstawowych funkcji sprawności służących do oceny wydajności modelu, z których najczęstsze opierają się na błędzie lub różnicy między danymi wyjściowymi modelu a wartością rzeczywistą. Takie funkcje obejmują błąd średni kwadratowy , pierwiastek błędu średniokwadratowego , średni błąd bezwzględny , błąd względny kwadratowy, pierwiastek względny błąd kwadratowy, względny błąd bezwzględny i inne.

Wszystkie te standardowe miary zapewniają drobną ziarnistość lub gładkość przestrzeni rozwiązania i dlatego działają bardzo dobrze w większości zastosowań. Ale niektóre problemy mogą wymagać bardziej zgrubnej ewolucji, na przykład ustalenie, czy prognoza mieści się w określonym przedziale, na przykład mniej niż 10% rzeczywistej wartości. Jednak nawet jeśli interesuje nas tylko liczenie trafień (czyli przewidywanie mieszczące się w wybranym przedziale), tworzenie populacji modeli ewoluujących na podstawie tylko liczby trafień, które każdy program ocenia, zwykle nie jest zbyt wydajne ze względu na zgrubne ziarnistość krajobrazu sprawności . Zatem rozwiązanie zwykle obejmuje połączenie tych zgrubnych miar z pewnym rodzajem gładkiej funkcji, takiej jak standardowe miary błędu wymienione powyżej.

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

Funkcje fitness do klasyfikacji i regresji logistycznej

Projekt funkcji przystosowania do klasyfikacji i regresji logistycznej wykorzystuje trzy różne cechy modeli klasyfikacji. Najbardziej oczywistym jest po prostu liczenie trafień, co oznacza, że ​​jeśli rekord jest prawidłowo sklasyfikowany, jest liczony jako trafienie. Ta funkcja fitness jest bardzo prosta i działa dobrze w przypadku prostych problemów, ale w przypadku bardziej złożonych problemów lub zestawów danych o wysokim stopniu niezrównoważenia daje słabe wyniki.

Jednym ze sposobów poprawy tego typu funkcji fitness opartej na trafieniach jest rozszerzenie pojęcia prawidłowej i nieprawidłowej klasyfikacji. W zadaniu klasyfikacji binarnej poprawne klasyfikacje mogą 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ł prawidłowo sklasyfikowany. Klasyfikacje typu „00” nazywane są prawdziwie negatywnymi (TN) i „11” prawdziwie pozytywnymi (TP).

Istnieją również dwa rodzaje błędnych klasyfikacji i są one reprezentowane przez 01 i 10. Nazywa się je fałszywymi trafieniami (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 zwanej macierzą pomyłek .

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

Funkcje te oparte na macierzy pomyłek są dość wyrafinowane i są wystarczające do skutecznego rozwiązywania większości problemów. Istnieje jednak inny wymiar modeli klasyfikacyjnych, który jest kluczem do efektywniejszego eksploracji przestrzeni rozwiązań, a zatem skutkuje odkryciem lepszych klasyfikatorów. Ten nowy wymiar obejmuje badanie struktury samego modelu, która obejmuje nie tylko dziedzinę i zakres, ale także rozkład wyników modelu i margines klasyfikatora.

Eksplorując ten inny wymiar modeli klasyfikacyjnych, a następnie łącząc informacje o modelu z macierzą pomyłek, można zaprojektować bardzo wyrafinowane funkcje sprawnościowe, które pozwalają na płynną eksplorację przestrzeni rozwiązań. Na przykład można połączyć pewną miarę opartą na macierzy pomyłek z błędem średniokwadratowym ocenianym między surowymi danymi wyjściowymi modelu a rzeczywistymi wartościami. Lub połącz miarę F z R-kwadratem oszacowanym dla surowego modelu wyjściowego i celu; lub macierz kosztów/zysków ze współczynnikiem korelacji itd. Bardziej egzotyczne funkcje dopasowania, które badają szczegółowość modelu, obejmują obszar pod krzywą ROC i miarę rang.

Z tym nowym wymiarem modeli klasyfikacyjnych wiąże się również idea przypisywania prawdopodobieństw do wyników modelu, co robi się w 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 wartościami rzeczywistymi, a następnie połączenie tego z macierzą pomyłek w celu stworzenia bardzo wydajnych funkcji dopasowania dla regresji logistycznej. Popularne przykłady funkcji przystosowania opartych na prawdopodobieństwach obejmują estymację największej wiarygodności i utratę zawiasów .

Funkcje fitness dla problemów logicznych

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

Selekcja i elitarność

Selekcja za pomocą koła ruletki jest prawdopodobnie najpopularniejszym schematem selekcji używanym w obliczeniach ewolucyjnych. Polega na odwzorowaniu sprawności każdego programu na wycinek koła ruletki proporcjonalnie do jego sprawności. Następnie ruletka jest kręcona tyle razy, ile jest programów w populacji, aby utrzymać stałą wielkość populacji. Tak więc w przypadku ruletki programy selekcji wybierane są zarówno pod kątem kondycji, jak i szczęścia losowania, co oznacza, że ​​czasami najlepsze cechy mogą zostać utracone. Jednak łącząc selekcję na kole ruletki z klonowaniem najlepszego programu każdego pokolenia, gwarantuje się, że przynajmniej najlepsze cechy nie zostaną utracone. Ta technika klonowania programu najlepszych generacji jest znana jako prosta elitarność 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. Do reprodukcji nie jest wymagana modyfikacja genomu, 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 jednego programu może się różnić, przy czym niektóre programy są kopiowane więcej niż jeden raz, podczas gdy inne są kopiowane tylko raz lub wcale. Ponadto selekcja jest zwykle ustalana tak, 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 tylko instrukcja kopiowania strun jest wymagana do przekazywania wszystkich informacji w genomie z pokolenia na pokolenie.

Replikacja wybranych programów jest fundamentalnym elementem wszystkich sztucznych systemów ewolucyjnych, ale aby ewolucja mogła zaistnieć, musi być zaimplementowana nie ze zwykłą precyzją instrukcji kopiowania, ale raczej z kilkoma wrzuconymi błędami. Rzeczywiście, różnorodność genetyczna jest tworzone 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. Kumulacja 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 genu dowolny symbol domeny może być zastąpiony 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 tak długo, jak chromosomy rodzicielskie są wyrównane, a wymieniane fragmenty są homologiczne (to znaczy zajmują tę samą pozycję w chromosomie), nowe chromosomy utworzone przez rekombinację 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 wybiera się 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 poprzez 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ą pojawiać się w dowolnym miejscu chromosomu, ale są one wstawiane tylko w główkach genów. Ta metoda gwarantuje, że nawet sekwencje wstawiania z ogonów dają w wyniku programy bezbłędne.

Aby transpozycja działała prawidłowo, musi zachować długość chromosomu i strukturę genów. Tak więc w programowaniu ekspresji genów transpozycja może być realizowana przy użyciu dwóch różnych metod: pierwsza tworzy przesunięcie w miejscu insercji, a następnie delecję na końcu głowy; drugi nadpisuje lokalną sekwencję w miejscu docelowym i dlatego jest łatwiejszy do wdrożenia. Obie metody można wdrożyć do działania między chromosomami lub w obrębie chromosomu, a nawet w obrębie pojedynczego genu.

Inwersja

Inwersja to interesujący operator, szczególnie przydatny do optymalizacji kombinatorycznej . Polega na odwróceniu małej sekwencji w chromosomie.

W programowaniu ekspresji genów może być łatwo zaimplementowany we wszystkich domenach genów i we wszystkich przypadkach wytworzone potomstwo jest zawsze poprawne składniowo. W przypadku dowolnej domeny genu 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 jednorodna, transpozycja genów, transpozycja korzeni, mutacja specyficzna dla domeny, inwersja specyficzna dla domeny, transpozycja specyficzna dla domeny itd. wdrożone i szeroko stosowane.

Algorytm GEP-RNC

Stałe numeryczne są podstawowymi elementami modeli matematycznych i statystycznych, dlatego ważne jest, aby umożliwić ich integrację z modelami zaprojektowanymi przez algorytmy ewolucyjne.

Programowanie ekspresji genów bardzo elegancko rozwiązuje ten problem poprzez użycie dodatkowej domeny genu – Dc – do obsługi losowych stałych liczbowych (RNC). Łącząc tę ​​domenę ze specjalnym placeholderem 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 złożony tylko z jednego genu o wielkości głowy 7 (Dc rozciąga się na pozycje 15–22):

01234567890123456789012

+?*+?**aaa??aaa68083295

gdzie terminal "?" reprezentuje symbol zastępczy dla RNC. Ten rodzaj chromosomu jest wyrażany 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 przez symbole (dla uproszczenia reprezentowane przez cyfry) w Dc, dając:

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 jak zwykle poprzez ekspresję jednego genu po drugim, a następnie łączenie ich wszystkich razem za pomocą tego samego rodzaju procesu łączenia.

Operatory genetyczne używane w systemie GEP-RNC są rozszerzeniem operatorów genetycznych podstawowego algorytmu GEP (patrz wyżej ) i wszystkie mogą być bezpośrednio zaimplementowane w tych nowych chromosomach. Z drugiej strony, podstawowe operatory mutacji, inwersji, transpozycji i rekombinacji są również wykorzystywane w algorytmie GEP-RNC. Co więcej, specjalne operatory specyficzne dla Dc, takie jak mutacja, inwersja i transpozycja, są również wykorzystywane do wspomagania bardziej wydajnego obiegu RNC między poszczególnymi programami. Ponadto istnieje również specjalny operator mutacji, który umożliwia trwałe wprowadzenie zmienności w zestawie RNC. Początkowy zestaw RNC jest tworzony losowo na początku przebiegu, co oznacza, że ​​dla każdego genu w populacji początkowej losowo generowana jest określona liczba stałych liczbowych, wybranych z pewnego zakresu. Następnie ich krążenie i mutację umożliwiają operatorzy genetyczni.

Sieci neuronowe

Sztuczna sieć neuronowa (ANN lub NN) jest urządzeniem obliczeniowym, które składa się z wielu prostych dołączonych urządzeń lub neuronów. Powiązania 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 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. Wzór aktywacji jest prezentowany na jednostkach wejściowych, a następnie rozprzestrzenia się w przód od jednostek wejściowych przez jedną lub więcej warstw jednostek ukrytych do jednostek wyjściowych. Aktywacja przychodząca do jednej jednostki z innej jednostki jest mnożona przez wagi na ogniwach, przez które się rozprzestrzenia. Cała przychodząca aktywacja jest następnie sumowana, a jednostka zostaje aktywowana tylko wtedy, gdy przychodzący wynik przekracza próg jednostki.

Podsumowując, podstawowymi elementami sieci neuronowej są jednostki, połączenia między jednostkami, wagi i progi. Aby więc w pełni zasymulować sztuczną sieć neuronową, trzeba w jakiś sposób zakodować te składniki w liniowym chromosomie, a następnie umieć je wyrazić w sensowny sposób.

W sieciach neuronowych GEP (sieci GEP-NN lub GEP) architektura sieci jest zakodowana w zwykłej strukturze domeny head/tail. Głowica 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 zaciski/jednostki wejściowe.

Oprócz głowy i ogona, te geny sieci neuronowej zawierają dwie dodatkowe domeny, Dw i Dt, służące do kodowania wag i progów sieci neuronowej. Strukturalnie Dw znajduje się za ogonem, a jego długość d _w zależy od wielkości głowy h i maksymalnej arności n _max i jest obliczana według wzoru:

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

DT jest po Dw i ma długość d _t RÓWNOWARTOŚCI 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 stosuje się również specjalne operatory, aby umożliwić stały przepływ zmienności genetycznej w zestawie wag i progów.

Na przykład poniżej pokazana jest sieć neuronowa z dwiema jednostkami wejściowymi ( i ₁ oraz i ₂ ), dwiema jednostkami ukrytymi ( h ₁ i h ₂ ) i 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ą pominięte):

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

gdzie „a” i „b” reprezentują dwa wejścia i ₁ i i _2, a „D” reprezentuje funkcję z łącznością 2. Ta funkcja dodaje wszystkie swoje ważone argumenty, a następnie progi tej 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 niż próg, 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 problemu wyłączności lub . Ma rozmiar głowy 3 i rozmiar Dw 6:

0123456789012

DDDabab393257

Jej wyrażenie daje w wyniku następującą sieć neuronową:

które 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:

co jest idealnym rozwiązaniem na wyłączność-lub funkcję.

Oprócz prostych funkcji logicznych z wejściami binarnymi i wyjściami binarnymi, algorytm sieci GEP może obsługiwać wszelkiego rodzaju funkcje lub neurony (neuron liniowy, neuron tanh, neuron atan, neuron logistyczny, neuron graniczny, neurony o podstawie radialnej i trójkątnej, wszelkiego rodzaju neurony krokowe i tak dalej). Interesujące jest również to, że algorytm sieci GEP może używać wszystkich tych neuronów razem i pozwolić ewolucji zdecydować, które z nich najlepiej rozwiążą dany problem. Tak więc sieci GEP mogą być używane nie tylko w problemach logicznych, ale także w regresji logistycznej , klasyfikacji i regresji . We wszystkich przypadkach sieci GEP mogą być wdrażane nie tylko z systemami wielogenowymi, ale także z systemami komórkowymi , zarówno jednokomórkowymi, jak i wielokomórkowymi. Co więcej, problemy klasyfikacji wielomianowej można również rozwiązać za jednym zamachem za pomocą sieci GEP, zarówno w przypadku systemów wielogenowych, jak i systemów wielokomórkowych.

Drzewa decyzyjne

Drzewa decyzyjne (DT) to modele klasyfikacyjne, w których serie pytań i odpowiedzi są mapowane 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ścia określają etykietę klasy dla wszystkich różnych ścieżek w drzewie.

Większość algorytmów indukowania drzewa decyzyjnego polega na wybraniu atrybutu dla węzła głównego, a następnie podejmowaniu tego samego rodzaju świadomej decyzji o wszystkich węzłach 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 udziału człowieka.

Zasadniczo istnieją dwa różne typy algorytmów DT: jeden do wywoływania drzew decyzyjnych tylko z atrybutami nominalnymi, a drugi do wywoływania drzew decyzyjnych zarówno z atrybutami liczbowymi, jak i nominalnymi. Ten aspekt indukcji drzewa decyzyjnego prowadzi również do programowania ekspresji genów i istnieją dwa algorytmy GEP do indukcji drzewa decyzyjnego: algorytm ewoluujących drzew decyzyjnych (EDT) do zajmowania się wyłącznie atrybutami nominalnymi oraz EDT-RNC (EDT z losowymi stałymi liczbowymi) dla obsługa zarówno atrybutów nominalnych, jak i liczbowych.

W drzewach decyzyjnych indukowanych przez programowanie ekspresji genów atrybuty zachowują się jak węzły funkcji w podstawowym algorytmie ekspresji genów , podczas gdy etykiety klas zachowują się jak terminale. Oznacza to, że węzły atrybutów również powiązały z nimi określoną arność lub liczbę gałęzi, które determinują ich wzrost, a ostatecznie wzrost drzewa. Etykiety klasy zachowują się jak terminale, co oznacza, że dla k -class zadania klasyfikacji, terminal zestaw z k terminali jest używana, reprezentujących k różnych klas.

Zasady kodowania drzewa decyzyjnego w genomie liniowym 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 terminale, a ogon zawiera tylko terminale. To znowu zapewnia, że ​​wszystkie drzewa decyzyjne zaprojektowane przez GEP są zawsze poprawnymi programami. Co więcej, 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 przez równanie:

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

Na przykład rozważ poniższe drzewo decyzyjne, aby zdecydować, czy grać na zewnątrz:

Może być zakodowany liniowo jako:

01234567

HOWbaaba

gdzie „H” reprezentuje atrybut Wilgotność, „O” atrybut Outlook, „W” oznacza wietrznie, a „a” i „b” oznaczają odpowiednio etykiety klasy „Tak” i „Nie”. Zauważ, że krawędzie łączące węzły są właściwościami danych, określającymi typ i liczbę gałęzi każdego atrybutu, a zatem nie muszą być kodowane.

Proces indukcji drzewa decyzyjnego z programowaniem ekspresji genów rozpoczyna się, jak zwykle, od początkowej populacji losowo utworzonych chromosomów. Następnie chromosomy są wyrażane jako drzewa decyzyjne, a ich dopasowanie oceniane na podstawie zestawu danych treningowych. W zależności od sprawności są następnie wybierane do reprodukcji z modyfikacją. Operatory genetyczne są dokładnie takie same, jakie są używane w konwencjonalnym systemie jednogenowym, na przykład mutacja , inwersja , transpozycja i rekombinacja .

Drzewa decyzyjne z atrybutami zarówno nominalnymi, jak i liczbowymi są również łatwo indukowane za pomocą programowania ekspresji genów przy użyciu opisanej powyżej struktury do obsługi losowych stałych liczbowych. Architektura chromosomowa obejmuje dodatkową domenę do kodowania losowych stałych liczbowych, które są wykorzystywane jako wartości progowe do podziału danych w każdym węźle rozgałęzienia. Na przykład poniższy gen o wielkości głowy 5 (Dc zaczyna się w 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 czy terminal), ma skojarzoną z nim 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 dziedzinie Dc, a ich wyrażenie jest zgodne z bardzo prostym schematem: 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ż bardziej kolorowo przedstawić jako konwencjonalne drzewo decyzyjne:

Krytyka

GEP został skrytykowany 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

GeneXproNarzędzia

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

Biblioteki open-source

GEP4J – GEP dla projektu Java

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

PyGEP — programowanie wyrażeń genów w Pythonie

Stworzony przez Ryana O'Neila w celu stworzenia prostej biblioteki odpowiedniej do akademickiej nauki programowania ekspresji genów w Pythonie , mającej na celu łatwość użycia i szybką implementację. Wdraża standardowe chromosomy wielogenowe oraz mutacje, krzyżowanie i transpozycje 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, aby uzyskać rzeczywistą prędkość. jGEP jest hostowany na SourceForge .

Dalsza lektura

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

Zobacz też

• Regresja symboliczna
• Sztuczna inteligencja
• Drzewa decyzyjne
• Algorytmy ewolucyjne
• Algorytmy genetyczne
• Programowanie genetyczne
• GeneXproNarzędzia
• Nauczanie maszynowe
• Sieci neuronowe

Bibliografia

Zewnętrzne linki

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