Generative Genetics 

1. Wstęp

Pierwotnym celem projektu, była próba zmierzenia się z problemem stworzenia przy pomocy algorytmu ewolucyjnego konstrukcji o typowo utylitarnym charakterze, mającym odpowiedniki w świecie rzeczywistym. Pod uwagę brane były dwie konstrukcje: stół oraz most. Miała umożliwiać to odpowiednio dobrana funkcja celu, prowadząca ewolucję w odpowiednim kierunku. W trakcie przygotowywania sie do tego tematu i w trakcie szukania materiałów, autor natknął się na prace G. Hornby'ego, których tematem jest ten sam problem. W swojej pracy autor dowodzi, że na jakość wyników znaczny wpływ ma zastosowana reprezentacja genetyczna osobników. Od typowej reprezentacji genetycznej stosowanej w algorytmach genetycznych znacznie lepiej spisuje się reprezentacja umożliwiająca wielokrotne użycie pewnych fragmentów genotypu, a więc pewnych części składowych organizmu. Taką reprezentacją może być reprezentacja oparta na systemie Lindenmayera, opisana w kolejnym punkcie.

2. Systemy Lindenmayera

Systemy Lindenmayera (L-systemy) zostały opracowane przez duńskiego botanika Aristida Lindenmayera. Umożliwiają one modelowanie wzrostu roślin za pomocą przepisywania ciągu znaków. Późniejsze prace nad systemami, w których brał również udział polski naukowiec Przemysław Prusinkiewicz, umożliwiły wykorzystanie ich do modelowania bardziej złożonych organizmów.

Najprostszym rodzajem L-systemów jest system bezkontekstowy, deterministyczny, w których podane mamy słowo początkowe, oraz zbiór reguł (produkcji) postaci a -> b co oznacza, że litera b zamieniona zostaje na literę a.

Innym z rodzajów systemów Lindenmayera jest system parametryczny, w którym z każdym znakiem w może być związany jeden lub więcej parametrów. Ponadto, każda produkcja może posiadać warunek na dane parametry, kiedy może zostać użyta.

3. Implementacja systemu Lindenmayera dla środowiska Framsticks

Jako reprezentacje genetyczną dla środowiska Framsticks wybrano L-system parametryczny. Stworzenie Framsticka używając powyższej reprezentacji odbywa się dwufazowo. Pierwszym etapem jest stworzenie zbioru produkcji oraz słowa początkowego, z którego rozwinięty zostanie cały genotyp sztucznego organizmu. Należy także podac liczbę iteracji, w ciągu których będzie się odbywało parsowanie genotypu, oraz początkowe wartości parametrów użytych w słowie początkowym. Następnie parser przekształca słowo kluczowe używając podanego zbioru produkcji w docelowy genotyp Framsticka wyrażonego za pomocą reprezentacji f1.

3.1 Format danych wejściowych

Format danych wejściowych objaśniony zostanie na przykładzie:

10
n0=56.000000
n1=55.000000
---
P3
P3(n0,n1): n0>10.0 | [X(2.000000)C(1.000000)R(2.000000)X(1.000000)]:n0>1 | P3(12.000000-n1,2.000000)P2(3.000000,2.000000)
P2(n0,n1): n0>2.0 | X(3.000000)q(2.000000)[X(1.000000)^P0(n0-5.000000,n1)X(2.000000)X(1.000000)]

Pierwsza linijka, to maksymalna liczba iteracji, jaką ma sie odbywac parsowanie genotypu. Kolejne 2 linijki to wartości początkowe parametrów, jakie zostaną przekazane do produkcji początkowej. Linia '---' oddziela wartości parametrów od produkcji początkowej, po której już następują właściwe produkcje systemu (dokładny opis formatu produkcji w kolejnym punkcie).

3.2 Składnia systemu

Każda nazwa reguły musi zaczynac sie literą P, po czym w nawiasach podawana jest dowolna liczba parametrów. Każdy parametr musi zaczynac się od litery n. Po parametrach, oddzielone dwukropkiem podawane są poszczególne produkcje danej reguły. Każda produkcja składa się z dwóch części: warunku i właściwej produkcji, czyli ciągu znaków którymi zastępowany jest znak reguły. Warunkiem może byc obłożony każdy parametr przekazywany do reguły, poszczególne warunki oddzielane są od siebie przecinkiem. Przy tworzeniu warunków przyjęto następujące reguły: zawsze jako pierwsza musi byc podana nazwa parametru, nastepnie jedna z relacji: >, >=, ==, !=, <=, <, a następnie wartośc.

Warunek od produkcji oddzielony jest znakiem |. Produkcje to ciąg komend dostępnych w systemie, z których każda posiada parametr oznaczający liczbę powtórzeń danej komendy w przetworzonym genotypie f1. Poszczególne komendy to odpowiedniki analogicznych komend reprezentacji f1. Dostępne komendy
  • X
  • R oraz r
  • C oraz c
  • Q oraz q
  • [ będący odpowiednikiem ( w f1
  • ] będący odpowiednikiem ) w f1
  • ^ będący odpowiednikiem , w f1

Dodatkowym elementem składni L-systemu jest odpowiednik pętli for - ciąg komend umieszczony pomiędzy nawiasami {}(x) zostanie powtórzony x razy.