9. Język LISP

rodzina języków programowania z długą historią i charakterystyczną składnią. Lisp jest drugim z kolei pod względem wieku językiem programowania wysokiego poziomu pozostającym w użyciu (starszy jest tylko Fortran). Lisp powstał jako wygodna matematyczna notacja dla programów komputerowych, oparta na rachunku lambda. Szybko został najchętniej wybieranym językiem do badania i rozwoju sztucznej inteligencji.

Podstawową strukturą danych w Lispie jest lista. Kod źródłowy programów w Lispie składa się z list. W wyniku tego programy mogą manipulować kodem źródłowym jak zwykłą strukturą danych. Umożliwia to pisanie makr, pozwalających programiście tworzyć nową składnię lub nawet małe zagnieżdżone w Lispie języki.

Kod tworzony jako struktura danych sprawia, że Lisp ma charakterystyczną składnię. Cały kod źródłowy ma postać tzw. S-wyrażeń (S-expressions), czyli list otoczonych nawiasami. Wywołanie funkcji, makra lub formy specjalnej ma postać listy, której pierwszym elementem jest nazwa funkcji, a następnymi elementami - jej argumenty. Na przykład funkcję o nazwie f z argumentami a, b i c wywołuje się za pomocą kodu (f a b c).

Główne cechy:

-dynamiczne typowanie danych, ale z silną kontrolą typów

-wieloparadygmatowość- łączy wiele styli programowania: programowanie funkcyjne oraz programowanie obiektowe i refleksyjne

-Garbage collection, self - hosting compiler, język homologiczny

- wszystkie wyrażenia są zapisywane w notacji polskiej

-przejrzysta składnia oraz dynamiczne typowanie

-wyróżnia się 2 dialekty: Scheme oraz Common Lisp

Podstawy:

Podstawowymi elementami Lispa są listy i atomy. Każdym elementem listy jest albo lista, albo atom. Atomami są np. liczby, podstawowe operatory arytmetyczne (+ - * /), stałe znakowe czy dłuższe łańcuchy. W przypadku zagnieżdżania w sobie list mamy do czynienia z tzw. Ewaluacją.

12. Rola liczebności populacji

Jeśli populacja będzie zawierała zbyt mało osobników, to algorytm może zatrzymać się bardzo szybko np. w jakimś minimum lokalnym. Rezultat będzie wówczas mało wiarygodny.

Z drugiej strony zbyt duża liczebność populacji zmniejsza szybkość działania algorytmu zużywając czas i zasoby komputerowe.

13. Metody krzyżowania

Zadaniem kroku krzyżowania jest wymiana „materiału genetycznego” pomiędzy dwoma rozwiązaniami w populacji. W wyniku krzyżowania, na podstawie dwóch rozwiązań (rodzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania musza sie ze sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości od 0 do 1), który pokazuje jaka część osobników powinna być w jednej iteracji skrzyżowana, bądź określa prawdopodobieństwo, z jakim każde rozwiązanie może wziąć udział w krzyżowaniu.

W przypadku binarnej reprezentacji chromosomu najprostsze krzyżowanie polega na podziale dwóch chromosomów (rodzice) na dwie części (niekoniecznie równe) i utworzeniu dzieci przez polaczenie fragmentu od jednego rodzica z fragmentem od drugiego. Rozszerzeniem takiego krzyżowania jest krzyżowanie wielopunktowe, gdzie chromosomy rodziców dzieli sie na kilka części a później dzieci tworzy sie na podstawie przeplatanych wycinków rodziców

14. Metody mutacji

Mutacja, podobnie jak krzyżowanie, zapewnia wprowadzanie do populacji nowych osobników. Jednak, w odróżnieniu od krzyżowania, w przypadku mutacji modyfikowany jest jeden, a nie dwa osobniki. Podobnie jak w przypadku

krzyżowania istnieje tzw. współczynnik mutacji, który określa jaka część osobników będzie w jednej iteracji ulegała mutacji.

Mutacja polega na losowej zmianie wartości niektórych (lub wszystkich) genów reprezentujących osobnika. Ma ona za zadanie zwiększyć różnorodność osobników w populacji, czyli zapobiegać przedwczesnej zbieżności algorytmu oraz eksplorować przestrzeń rozwiązań. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów. Może być zarówno operatorem lokalnym (jak w algorytmach genetycznych), jak i operatorem globalnym (jak w strategiach ewolucyjnych).

W algorytmie genetycznym, zależnie od metody kodowania genotypu, może wyglądać następująco:

-W przypadku chromosomów kodowanych binarnie losuje się zazwyczaj dwa geny i zamienia się je miejscami bądź np. neguje pewien wylosowany gen.

-W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.

-W przypadku genotypów zakodowanych liczbami rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.

15. Ograniczenia w algorytmach ewolucyj.

model ewolucji przyjęty w algorytmie ewolucyjnym nie odzwierciedla wielu aspektów naturalnych procesów ewolucyjnych, takich jak:

-dynamicznie zmieniające się warunki środowiska

-jednoczesny wpływ wielu kryteriów

- brak wiedzy globalnej i synchronizacji pokoleniowej

-ewolucja gatunków

-ewoluujące odwzorowanie cech geno- i fenotypowych

Jako najistotniejsze ograniczenia klasycznych obliczeń ewolucyjnych wskazać zatem należy:

1. cały proces ewolucji jest realizowany przy pomocy jednego

algorytmu, przez co jest on scentralizowany

2. obiekty podlegające ewolucji są zredukowane do struktur danych (genów)

---