Politechnika Lubelska	Laboratorium sztucznej inteligencji
Michał Bogusz		Semestr VIII	Grupa: ID8.1	Rok akademicki: 2008/2009

Podczas zajęć poznaliśmy dwa programy:

1. „SWI Prolog”:

Prolog to język programowania logicznego. Należy do rodziny deklaratywnych języków programowania. Nie ma więc w nim typowych instrukcji wykonywanych jedna po drugiej - od początku do końca. Program w Prologu to baza wiedzy programu (dane), oraz opis reguł wnioskowana. Przykładowy program Prologowy może wyglądać następująco:

% *** baza wiedzy:

mezczyzna(piotr). % Piotr jest mężczyzną

mezczyzna(bartek). % Bartek jest mężczyzną

kobieta(basia). % Basia jest kobietą

dziecko(piotr,bartek). % Bartek jest dzieckiem Piotra

dziecko(bartek,basia).% Basia jest dzieckiem Bartka

% *** reguły wnioskowania:

syn(X,Y) :- dziecko(X,Y),mezczyzna(Y).

% ktoś jest czyimś synem, jeśli jest jego/jej dzieckiem, oraz jest mężczyzną

corka(X,Y) :- dziecko(X,Y),kobieta(Y).

% ktoś jest czyjąś córką jeśli jest jego/jej dzieckiem, oraz jest kobietą

dziadek(X,Y) :- dziecko(X,Z),dziecko(Z,Y),mezczyzna(X).

% ......?

babcia(X,Y) :- dziecko(X,Z),dziecko(Z,X),kobieta(Y).

% ......?

Zmienne pisane są z wielkich liter, stałe - z małych. Podstawowa jednostka Prologa to predykat, który składa się z nagłówka i argumentów np: dziecko(piotr,bartek). Programowi możemy wydawać zapytania, a Prolog manipulując symbolami, stosując reguły stara się znaleźć odpowiedz na zadane pytanie np:

dziadek(X,basia), czyli: "kto jest dziadkiem Basi?" - uzyskana odpowiedz to oczywiście X = piotr. Widać, zatem, że Prolog może być bardzo pomocny przy rozwiązywaniu szczególnego typu problemów.

Nasz pierwszy program, jaki napisaliśmy wyglądał jak wyżej i opisywał nasze drzewo genealogiczne. Opisywaliśmy wiele reguł takich jak: syn, córka, szwagier, dziadek, babcia, wnuk wnuczka, przodek, teść, teściowa, itp.

Następnie poznaliśmy listy i działania na listach(sumowanie elementów, dodawanie elementu do listy, usuwanie, itp.). Można powiedzieć, że lista jest podstawową strukturą danych Prologu. Listę można definiować wyliczając jej kolejne elementy, np.:

["a","b","c","b"]

lub też podając jej dwa fragmenty, pierwszy element (zwany głową) i listę pozostałych elementów (zwaną ogonem):

["a"|["b","c","b"]]

W tym przykładzie, ogonem jest lista ["b","c","b"], a głowę od ogona oddziela operator |. Możliwa jest też konwencja mieszana, w której pierwsze elementy listy są wyliczane i doklejana jest do nich lista-ogon:

["a","b"|["c","b"]

Są dwa szczególne przypadki list:

• lista jednoelementowa, np. ["a"]

• lista pusta: []

Elementami listy mogą być dowolne wartości, w szczególności mogą być to listy, np.:

[["a","b"],["c"],"d", []]

W powyższym przykładzie, mamy do czynienia z listą zawierającą cztery elementy - pierwszym jest dwuelementowa lista ["a","b"], drugim - jednoelementowa lista ["c"], trzecim - wartość "d", zaś czwartym - lista pusta [].

Ostatnia rzeczą, jaka poznaliśmy był predykat „findall”, który przechodząc przez bazę wiedzy tworzy listę elementów spełniających zapytanie np.:

baba(maria1).

baba(maria2).

baba(janina1).

baba(janina5).

baba(janina2).

baba(janina3).

kobiety(L):-findall(X,baba(X),L).

2. „Genetyk”:

Program, w którym za pomocą programowania genetycznego aproksymowana jest funkcja na podstawie zadanych punktów. Zarys algorytmu genetycznego jest podobny jak przy znajdowaniu optymalnej ścieżki komiwojażera. Zmieniają się tylko poszczególne elementy składowe: w tym wypadku populację stanowią przykładowe programy komputerowe, z których każdy wykonuje określone działanie. Krzyżowanie i mutacja tworzą nowe osobniki na podstawie już istniejących. Program posiada również funkcję oceny mającą zadecydować, czy dany program chociaż w przybliżeniu wykonuje te działania o które nam chodzi.

Poniżej znajdują się poszczególne elementy algorytmu:

• populacja - reprezentacja pojedynczego rozwiązania

W tym programie została zastosowana jako reprezentacja pojedynczego rozwiązania struktura drzewiasta. Jest ona bardzo wygodna z punktu widzenia krzyżowania i mutacji, a poza tym wymusza kolejność przechodzenia przez węzły i liście. Jest to reprezentacja o zmiennej długości, ponieważ przykładowymi programami mogą być zarówno program wykonujący sumę dwóch argumentów jak i program obliczający pierwiastki równania kwadratowego.

Przykładowy program:

Wynikiem działania każdego programu jest pewna wartość. Aby ją wyznaczyć należy drzewo przeglądać wstecznie (przed wykonaniem działania zapisanego w węźle należy najpierw obliczyć wyrażenia „zaczepione” w jego dzieciach). Wartość zwracana przez powyższe drzewo jest określona wzorem:

(X*((5.00+X)-((((X-X)-(X*X))+(1.00-2.00))+(7.00-(7.00-5.00)))))

Elementami takiego drzewa mogą być:

• jako węzły:

• operatory arytmetyczne (+,-,/,*)

• operatory logiczne (&&,||,!)

• operatory bitowe (&,|,~)

• porównania (>,<,==)

• funkcje (trygonometryczne, potęgowe,…)

• instrukcja warunkowa - IF (jeśli spełniony jest warunek (pierwszy argument), wykonywane jest poddrzewo drugiego argumentu, jeśli nie trzeciego)

• instrukcja iteracyjna - FOR (pierwszy argument podaje ile razy ma zostać wykonane poddrzewo drugiego argumentu)

• jako liście

• wartości stałe, zmienno- lub stałoprzecinkowe (np.: 5, 10.5, -11)

• wartości zmiennych (np.: X)

• wywołania funkcji (np.: WczytajZnakZKlawiatury(), lub random())

• wywołania procedur (np.: printf(), clrscr())

W przypadku procedur problemem jest zwracana przez nie wartość (każdy element drzewa musi coś zwracać swojemu rodzicowi) - w przypadku procedur najczęściej przyjmuje się, że zwracają one zero.

Populacja początkowa wypełniona jest programami wygenerowanym całkowicie losowo. Podczas losowania osobników dobrze jest zadbać o to, aby osobniki nie były zbyt „rozrośnięte”. Można to zrobić ustalając maksymalną głębokość lub liczbę wierzchołków tworzonego drzewa.

Krzyżowanie

Krzyżowanie polega na wymianie pomiędzy dwoma osobnikami wybranych losowo poddrzew.

Przykład krzyżowania (ramką zaznaczone zostały wymieniane poddrzewa):

Sytuacja przed krzyżowaniem:

Pierwszy rodzic:	Drugi rodzic:

Sytuacja po krzyżowaniu:

Pierwsze dziecko:	Drugie dziecko:

Mutacja

Najczęściej stosowaną mutacją w przypadku programowania genetycznego jest usunięcie z osobnika losowego poddrzewa i na jego miejsce wygenerowanie nowego.

Przykład mutacji (ramką zastało zaznaczone poddrzewo usuwane oraz dodawane):

Osobnik przed mutacją:

Osobnik po mutacji:

Innym sposobem mutacji jest zmiana operatora w dowolnym wierzchołku drzewa. Należy tutaj pamiętać, że jeśli nowy operator ma mniej argumentów niż oryginalny (max(a,b)->sin(a)) należy usunąć nadmiarowe poddrzewa. Jeśli natomiast nowy operator ma więcej argumentów (max(a,b)->if(a,b,c)) należy dogenerować brakujące poddrzewa.

Można również mutować liście w drzewie. Jest to najprostszy rodzaj mutacji (nie trzeba dodawać nowych, ani usuwać starych poddrzew), jednak powoduje niewielką zmianę działania programu jaki mutowany osobnik reprezentuje. Ten sposób mutacji przydaje się gdy rozwiązanie (osobnik, program) działa „z grubsza” poprawnie a trzeba zmienić tylko jakieś współczynniki (np. zmiana liczby iteracji, próg do porównania dla instrukcji IF, itp.)

Funkcja oceny

Głównym zadaniem funkcji oceny jest sprawdzenie czy dany osobnik wykonuje taki program o jaki nam chodziło. W zależności od tego jak bardzo wyniki programu przypominają to o co nam chodziło osobnik dostaje odpowiednią liczbę punktów.

Np dla rozwiązywania zadania aproksymacji funkcji funkcja oceny sprawdza jak daleko wygenerowana funkcja odbiega od punktów bazowych.

Do funkcji oceny warto jest dodać pewną karę za wielkość osobnika. Dzięki temu poszczególne osobniki nie będą się nadmiernie rozrastać. W przypadku drzewowej reprezentacji rozwiązania można wprowadzić karę za liczbę wierzchołków oraz karę za maksymalną głębokość drzewa.

Selekcja

Ta część algorytmu jest dokładnie taka sama jak w przypadku innych wykorzystań algorytmów genetycznych. Zarówno koło ruletki jak i metoda turniejowa bazują tylko na wartościach funkcji oceny (do działania nie potrzebują informacji o osobnikach).

Iteracyjne wykonywanie wszystkich kroków algorytmu genetycznego prowadzi do otrzymania programu (przynajmniej w przybliżeniu) rozwiązującego zadany problem. Program wygenerowany dzięki programowaniu genetycznemu jest daleki od optymalnego.

---