Politechnika Lubelska

Laboratorium Sztucznej Inteligencji
Tomasz Skrzypiec
Grupa 8.1
Rok akademicki :2008/2009

\

1. Programowanie w Prolog-u.

Prolog (od francuskiego Programmation en Logique) to język programowania logicznego - program w Prologu to opis reguły wnioskowania oraz celu do którego zmierzamy, a rola komputera polega na odpowiednim zastosowaniu reguł aby znaleźć rozwiązanie.
Prolog został stworzony w 1971 roku przez Alaina Colmeraurera i Phillipe'a Roussela. Używany w wielu programach z zakresu sztucznej inteligencji.
Prolog opiera się o rachunek predykatowy pierwszego rzędu, jednak ogranicza się tylko do klauzul Horna. Programowanie w Prologu bardzo różni się od programowania w językach algorytmicznych. W Prologu podaje się bazę faktów i reguł. Potem można wykonywać zapytania na tej bazie.

Programowanie w Prologu bardzo różni się od programowania w językach algorytmicznych. W Prologu podaje się bazę faktów i reguł. Potem można wykonywać zapytania na tej bazie. Podstawową jednostką w Prologu jest predykat. Predykat składa się z nagłówka i argumentów, na przykład: ojciec(tomasz, agata), gdzie ojciec to nagłówek a tomasz i agata to argumenty. Predykat może zostać użyty do wyrażenia pewnych faktów o świecie, które są znane dla programu. W tym przypadku programista musi nadać im znaczenie. Jedną z interpretacji zdania ojciec(tomasz, agata) jest "tomasz to ojciec agaty". Jednak równie dobrze mogło by to znaczyć "ojcem tomasza jest agata". Prolog nie ma pojęcia, co oznaczają te stwierdzenia. Wszystko co robi to manipulacja symbolami w oparciu o reguły. Dlatego można wybrać dowolny sposób zapisu tego, że "tomasz to ojciec agaty", pod warunkiem konsekwentnego przestrzegania kolejności argumentów w całym programie.
Pewne predykaty mogą oprócz wyrażania faktów mieć skutki uboczne, jak na przykład wbudowany predykat write('Cześć'), który wypisuje na ekranie 'Cześć'.

1. Naszym pierwszym zadaniem było zdefiniować za pomocą faktów i reguł wybrane drzewo genealogiczne pewnej rodziny.

Wiedza :

rodzice(stanislawa,zbigniew,malgorzata).

rodzice(stanislawa,zbigniew,tomasz).

rodzice(stanislawa,zbigniew,mateusz).

rodzice(jolanta,karol,hubert).

rodzice(jolanta,karol,ola).

rodzice(jolanta,karol,natalka).

rodzice(lucyna,stefan,elzbieta).

rodzice(lucyna,stefan,marcin).

rodzice(lucyna,stefan,ewa).

rodzice(wladyslawa, tadeusz, zbigniew).

rodzice(wladyslawa, tadeusz, stefan).

rodzice(wladyslawa, tadeusz, jolanta).

rodzice(elzbieta, rafal, oliwia).

rodzice(elzbieta, rafal, krzysztof).

rodzice(zofia, tadeusz, waldemar).

rodzice(zofia, tadeusz, leokadia).

rodzice(zofia, tadeusz, marian).

rodzice(zofia, tadeusz, jan).

rodzice(zofia, tadeusz, stanislawa).

rodzice(krystyna, waldemar, tomasz).

rodzice(krystyna, waldemar, katarzyna).

rodzice(krystyna, waldemar, lukasz).

rodzice(krystyna, waldemar, marcin).

rodzice(leokadia, wladyslaw, grzegorz).

rodzice(leokadia, wladyslaw, pawel).

rodzice(leokadia, wladyslaw, dorota).

rodzice(leokadia, wladyslaw, pior).

rodzice(ewa, grzegorz,lukasz).

rodzice(ewa, grzegorz,patrycja).

rodzice(dorota, krzysztof, weronika).

rodzice(genowefa, marian, mariusz).

rodzice(genowefa, marian, marcin).

rodzice(barbara,jan,anna).

rodzice(barbara,jan,bozena).

rodzice(barbara,jan,jozef).

rodzice(zuzanna, janusz, krzysztof).

rodzice(marta, krzysztof, gabryjela).

rodzice(zuzanna, janusz, karol).

rodzice(zuzanna, janusz, anna).

rodzice(zuzanna, janusz, katarzyna).

rodzice(anna, marek, weronika).

rodzice(aleksandra, wladyslaw,waclaw).

rodzice(aleksandra, wladyslaw,leokadia).

rodzice(aleksandra, wladyslaw,marianna).

rodzice(aleksandra, wladyslaw,tadeusz).

rodzice(marianna, jan, zbigniew).

rodzice(marianna, jan, bogdan).

rodzice(marianna, jan, juzef).

rodzice(marianna, jan, wladyslawa).

rodzice(zofia, bogdan, edward).

rodzice(zofia, bogdan, ryszard).

rodzice(zofia, bogdan, krzysztof).

rodzice(anna, edward, karolina).

rodzice(anna, edward, marlena).

rodzice(marta, krzysztof, gabryjela).

rodzice(marta, krzysztof, maciej).

rodzice(danuta, ryszard, damian).

mezczyzna(jan).

mezczyzna(bogdan).

mezczyzna(edward).

mezczyzna(ryszard).

mezczyzna(krzysztof).

mezczyzna(maciej).

mezczyzna(damian).

mezczyzna(wladyslaw).

mezczyzna(janusz).

mezczyzna(karol).

mezczyzna(mark).

mezczyzna(zbigniew).

mezczyzna(stefan).

mezczyzna(tadeusz).

mezczyzna(rafal).

mezczyzna(lukasz).

mezczyzna(tomasz).

mezczyzna(mateusz).

mezczyzna(grzegorz).

mezczyzna(piotr).

mezczyzna(pawel).

mezczyzna(marcin).

mezczyzna(hubert).

kobieta(marianna).

kobieta(wladyslawa).

kobieta(aleksandra).

kobieta(zofia).

kobieta(anna).

kobieta(barbara).

kobieta(marianna).

kobieta(gabryjela).

kobieta(marlena).

kobieta(karolina).

kobieta(marta).

kobieta(zuzanna).

kobieta(ewa).

kobieta(leokadia).

kobieta(lucyna).

kobieta(dorota).

kobieta(stanislawa).

kobieta(malgorzata).

kobieta(genowefa).

kobieta(jolanta).

kobieta(ola).

ojciec(zbigniew, tadeusz).

ojciec(stefan,tadeusz).

ojciec(tomasz, zbigniew).

ojciec(mateusz, zbigniew).

ojciec(tadeusz, jozef).

matka(malgorzata, stanislawa).

matka(natalia, mariola).

matka(ola, mariola).

matka(mariola, wladyslawa).

matka(stanislawa, zofia).

Reguły wnioskowania:

babcia(Y,Z):-rodzice(X,Y,B),rodzice(A,B,Z).

babcia(Y,Z):-rodzice(X,Y,A),rodzice(A,B,Z).

dziadek(X,Z):-rodzice(X,Y,B),rodzice(A,B,Z).

dziadek(X,Z):-rodzice(X,Y,A),rodzice(A,B,Z).

dziadkowie(X,Y,Z):-rodzice(X,Y,A),rodzice(A,B,Z).

dziadkowie(X,Y,Z):-rodzice(X,Y,B),rodzice(A,B,Z).

dziecko(Z,X,Y):-rodzice(X,Y,Z).

malzenstwo(X,Y):-rodzice(X,Y,Z).

rodzenstwo(X,Y):-rodzice(A,B,X),rodzice(A,B,Y),not(X=Y).

wnuk(X,Y,Z):-mezczyzna(X),rodzice(A,B,X),rodzice(Y,Z,A).

wnuk(X,Y,Z):-mezczyzna(X),rodzice(A,B,X),rodzice(Y,Z,B).

wnuczka(X,Y,Z):-kobieta(X),rodzice(A,B,X),rodzice(Y,Z,A).

wnuczka(X,Y,Z):-kobieta(X),rodzice(A,B,X),rodzice(Y,Z,B).

wnuczeta(X,Y,Z):-rodzice(A,B,X),rodzice(Y,Z,A).

wnuczeta(X,Y,Z):-rodzice(A,B,X),rodzice(Y,Z,B).

pradziadkowie(Z,X,Y):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,C).

pradziadkowie(Z,X,Y):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,D).

pradziadkowie(Z,X,Y):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,C).

pradziadkowie(Z,X,Y):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,D).

pradziadek(Z,X):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,C).

pradziadek(Z,X):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,D).

pradziadek(Z,X):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,C).

pradziadek(Z,X):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,D).

prababcia(Z,Y):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,C).

prababcia(Z,Y):-rodzice(A,B,Z),rodzice(C,D,A),rodzice(X,Y,D).

prababcia(Z,Y):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,C).

prababcia(Z,Y):-rodzice(A,B,Z),rodzice(C,D,B),rodzice(X,Y,D).

szwagier(X,Y):-mezczyzna(X),malzenstwo(X,A),rodzenstwo(Y,A).

bratowa(X,Y):-kobieta(X),malzenstwo(A,X),rodzenstwo(Y,A).

ziec(X,Y,Z):-mezczyzna(X),malzenstwo(X,A),rodzice(Y,Z,A).

synowa(X,Y,Z):-kobieta(X),malzenstwo(A,X),rodzice(Y,Z,A).

tesciowie(Z,X,Y):-malzenstwo(Z,A),rodzice(X,Y,A).

tesciowie(Z,X,Y):-malzenstwo(A,Z),rodzice(X,Y,A).

tesc(Z,X):-malzenstwo(Z,A),rodzice(X,Y,A).

tesc(Z,X):-malzenstwo(A,Z),rodzice(X,Y,A).

tesciowa(Z,Y):-malzenstwo(Z,A),rodzice(X,Y,A).

tesciowa(Z,Y):-malzenstwo(A,Z),rodzice(X,Y,A).

1. Wykorzystanie rekurencji i list w Prologu.

zwraca długość listy:

dlugosc_listy([],0).

dlugosc_listy([_|Ogon],I):-dlugosc_listy(Ogon,J),I is J+1.

suma elementow listy:

dlugosc_listy([],0).

dlugosc_listy([Glowa|Ogon],I):-dlugosc_listy(Ogon,J),I is Glowa+J.

silnia:

silnia(0,1).

silnia(N,Nsilnia):-N>0,M is N-1,silnia(M,Msilnia),Nsilnia is N*Msilnia.

rekurencja w prologu prawostronna:

dlugosc_listy(L,N):-dlugosc_akum(L,0,N).

dlugosc_akum([],A,A).

dlugosc_akum([_|Ogon],A,N):- A1 is A + 1,dlugosc_akum(Ogon,A1,N).

rekrencja prawostronna silnia:

wsilnia(L,N):-wartosc_akum(L,1,N).

wartosc_akum(0,A,A).

wartosc_akum(L,A,N):-L>0,

L1 is L-1,

A1 is A*L,

wartosc_akum(L1,A1,N).

suma kwadratow elementow listy:

sumaKwListy([],0).

sumaKwListy([H|T],N):-sumaKwListy(T,N1),square(H,HM),N is N1+HM.

square(H,HM):-HM is H*H.

suma ujemnych elementów listy:

sumaUjemnych([],0).

sumaUjemnych([H|T],N):-sumaUjemnych(T,N1),modul(H,HM),N is N1+HM.

modul(H,HM):-H<0,HM is H.

modul(H,HM):-H>0,HM is 0.

srednia elementów listy:

sumaElementow([],0).

sumaElementow([H|T],N):-sumaElementow(T,N1),N is N1+H.

dlugoscListy([],0).

dlugoscListy([G|O],N):-dlugoscListy(O,N1),N is N1+1.

srednia(L,Average):-sumaElementow(L,Sum),dlugoscListy(L,Dl),

Average is Sum/Dl.

najwiekszy wspolny dzielnik:

dzielnik(I,0,I). dzielnik(I,J,Zmienna) :- J > 0, R is I mod J, dzielnik(J,R,Zmienna).

czy element jest na liscie:

czyENaLiscie(Element, [X|_]) :- Element=X. czyENaLiscie(Element, [_|O]) :- czyENaLiscie(Element,O).

1. Algorytmy genetyczne.

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.

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

• wartości zmiennych

• wywołania funkcji

• wywołania procedur

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:

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.

1. Oprogramowanie gabi.

Gabi jest programem służącym do ilustracji podstawowych elementów algorytmów ewolucyjnych.

Na informację o osobniku składa się genotyp (w postaci tablicy wartości zmiennych niezależnych i tablicy parametrów, wykorzystywanych do samoczynnej adaptacji), wartość funkcji przystosowania i wiek osobnika (mierzony liczbą sukcesji, które przetrwał nienaruszony). Osobniki są elementami populacji bazowej i potomnej. Każdy osobnik podlega ocenie podczas prezentacji środowisku – określa się wówczas wartość jego funkcji przystosowania. Wartość tę oblicza się tylko raz – w momencie utworzenia nowego osobnika i nie podlega ona ponownemu przeliczeniu nawet wówczas, gdy jest on przetrzymywany w populacji bazowej dłużej niż jedną generację.

Środowisko, w jakim odbywa się ewolucja jest określone przez funkcję przystosowania. W wykorzystywanej przez nas wersji programu funkcja przystosowania jest tworzona na podstawie zadania optymalizacji z funkcją celu i graniczeniami; w przypadku obecności tych ostatnich, zdefiniowania wymagają jeszcze metody uwzględniania ograniczeń. Użytkownik oprogramowania powinien zdefiniować metodę próbkowania obszaru zainteresowania wykorzystaną do inicjacji genotypów osobników populacji bazowej.

W oprogramowaniu gabi można stosować wiele typów operatorów genetycznych w zależności od specyfiki rozwiązywanego zagadnienia. Operatory te są wybierane losowo z puli dostępnych operatorów – o wyborze decyduje zmienna losowa o znanym, podanym przez użytkownika rozkładzie. Stwarza to możliwość adaptowania rozkładu wraz z przebiegiem ewolucji.

Nad przebiegiem ewolucji ‘czuwają’ dwa monitory: populacji i zadania. Pierwszy z nich ma za zadanie prowadzić bieżące statystyki populacji bazowej, takie jak informacje o najgorszym, najlepszym, przeciętnym osobniku, o wieku populacji. Są one wykorzystywane przede wszystkim przez niektóre metody reprodukcji, mogą także posłużyć do określenia kryterium zatrzymania (np. opartego na zaniku różnorodności populacji) czy do adaptacji parametrów (np. zasięgu mutacji). Z kolei monitor zadania jest jakby zewnętrznym ‘obserwatorem’ algorytmu ewolucyjnego – nie wnika w głąb populacji , lecz obserwuje najlepszego znalezionego dotychczas osobnika, czyli bieżące oszacowanie rozwiązania. Monitor ten służy do określenia spełnienia prostych, zewnętrznych kryteriów zatrzymania, bazujących na szybkości zmian rozwiązanie czy też na przekroczeniu limitu obliczeń wartości funkcji przystosowania.

Program rozpoczyna swoje działanie od wczytania ustawień z plików konfiguracyjnych. Określa się w nich metody reprodukcji i sukcesji, sposób reprezentacji osobnika, rodzaje wykorzystywanych operatorów genetycznych, kryterium zatrzymania oraz wartości parametrów niezbędnych do pełnego zdefiniowania algorytmu ewolucyjnego. Środowisko, szczególne operatory genetyczne, oraz inne elementy nie mieszczące się w ‘standardzie’ algorytmów ewolucyjnych ogólnego przeznaczenia wymagają zdefiniowania w postaci fragmentów oprogramowania, podlegających kompilacji i konsolidacji z dostępnym kodem.

Po zdefiniowaniu algorytmu i zadania, program przechodzi do zainicjowania populacji bazowej i obliczenia wartości funkcji przystosowania dla jej elementów. Następnie wykonuje się pętle główną algorytmu z cyklem reprodukcji, operacji genetycznych i sukcesji. Powtarza się ją dopóty, dopóki nie zostanie spełnione kryterium zatrzymania. Podczas działania pętli głównej wyprowadza się na standardowe wyjście wartości dostępne poprzez monitory populacji i zadania. Format i ilość wyprowadzonej informacji określa użytkownik w odpowiednim pliku konfiguracyjnym. Błędy techniczne oraz niespełnienie wewnętrznych wymagań algorytmu ewolucyjnego (takich jak próba ustawienia wartości prawdopodobieństwa powyżej jedności) są sygnalizowane na standardowym wyjściu błędów. Oprogramowanie gabi nie wykorzystuje standardowego strumienia wejściowego.

• Sposób implementacji:

  • Większość informacji jest umieszczona w strukturach (struct),

  • Informacje są przekazywane przez odpowiednie wskaźniki,

  • Konwencja nazewnictwa – wskaźnik do struktury nosi nazwę odpowiadającą jak największym stopniu reprezentowanemu przez nią obiektowi,

  • Wartości pól konfiguracyjnych są nadawane na podstawie zawartości plików konfiguracyjnych w części inicjującej ustawienia,

  • W czasie działania algorytmu ewolucyjnego struktury te są wykorzystywane wyłącznie do odczytu, występuje dokładnie jedna kopia każdej z nich, wskazywana przez zmienną globalną.

• Pliki konfiguracyjne:

  • Każdej ze struktur konfiguracyjnych odpowiada plik, w którym znajdują się wartości nadawane odpowiednim polom struktury podczas inicjacji programu. Zawartość pliku konfiguracyjnego ma następującą składnię:

<zawartość pliku>::= <zawartość pusta>|<nazwa><wartość>|<określenie tablicy>

<określenie tablicy>::= <nazwa><liczba całkowita bez znaku><nazwa tablicy>{<wartość>}

<nazwa tablicy>::=[‘a’-‘z’][‘a’-‘z’]*

<nazwa>::=[‘a’-‘z’][‘a’-‘z’]*

<wartość>::= <liczba całkowita bez znaku>|<liczba rzeczywista>|<łańcuch znakowy>

• Każda z wymienionych wyżej jednostek leksykalnych musi być otoczona białymi znakami,

• Pola struktur konfiguracyjnych mogą zawierać pojedyncze wartości (liczby lub łańcuch znakowy) lub ich tablice,

• Para <nazwa><wartość> służy do inicjacji takiego pola, którego wartość jest liczbą, <nazwa> musi być nazwą tego pola – pisaną wyłącznie małymi literami, którego <wartość> będzie nadana. Należy zwrócić szczególną uwagę na zgodność typów. Podczas wczytywania plików konfiguracyjnych nie prowadzi się zgodności typów. Nazwy nie mające odpowiednika w odpowiedniej strukturze konfiguracyjnej są pomijane bez zgłoszenia błędu ani ostrzeżenia.

• Inicjowanie pola tablicowego: wykonuję się to podając parę <nazwa><wartość>, następnie nazwę tablicy, a po niej wartości tablicy w liczbie dokładnie odpowiadającej jej rozmiarom (należy pamiętać o zgodności typów danych z oczekiwanymi w tablicy gdyż oprogramowanie nie jest odporne na błędnie wprowadzone dane).

• Działanie oprogramowania:

• Funkcja main:

• Pierwszą z wykonywanych procedur jest procedura okreslParametry, której zadaniem jest wykonanie kolejnych sekwencji polegających na otwarciu pliku konfiguracyjnego, zainicjowaniu odpowiedniej struktury konfiguracyjnej i zamknięci pliku.

• Następnie zostaje uruchomiona funkcja initLosowe, która dokonuje inicjacji generatora liczb pseudolosowych.

• Ostatnią czynnością funkcji main jest wywołanie funkcji petlaGlowna, która implementuje pętlę główną algorytmu ewolucyjnego. Zaimplementowana zgodnie ze standardowym algorytmem ewolucyjnym. Faza początkowa algorytmu ewolucyjnego składa się z inicjacji populacji bazowej, po której rozpoczyna się pętla główna algorytmu wykonywana dopóty, dopóki funkcja krytStopu nie zwróci wartości różnej od zera. W pętli tej wykonywana jest reprodukcja wraz z operatorami genetycznymi (genetyka), po której następuje sukcesja. Po zainicjowaniu populacji bazowej, jak również każdorazowo po zakończeniu reprodukcji i operacji genetycznych, dokonuje się ewaluacji wszystkich nowo wygenerowanych osobników (popEwaluacja). Dodatkowymi funkcjami są popMonitor i zadMonitor – uaktualniają one stan monitorów populacji i zadania, wyniki tych funkcji wyprowadzone są na standardowe wyjście za pomocą funkcji rapPop i rapZadanie. Populacje bazowa i potomna są zdefiniowane jako zmienne lokalne Pt i Ot, których zarządzaniem zajmują się funkcje z przedrostkiem pop, odpowiadające za stworzenie populacji, wypełnienie jej osobnikami oraz opróżnianie jej i usunięcie.

1. Operacje na zbiorach rozmytych.

LOGIKA ROZMYTA (ang. fuzzy logic) - wielowartościowa logika

wraz z opartym na niej systemem wnioskowania

Rozmyta reprezentacja zmiennych i parametrów złagodzenie żądania precyzji modelu. W realnym świecie wiele zjawisk opisywanych jest w sposób bardzo nieprecyzyjny:

• „prawie” identyczny

• „trochę” większy

• „znacznie” odmienny

• „niska” temperatura

• „zadawalający” poziom wiedzy

Konieczne jest odejście od binarnego widzenia świata.

Przykładowe zastosowania:

• wszędzie tam, gdzie trudno jest utworzyć matematyczny model

ale daje się opisać sytuację w sposób jakościowy,

• systemem ogniskowania niektórych kamer wizyjnych (Cannon)

podejmujący decyzję co jest fotografowanym obiektem,

• helikopter sterowany głosem, rozumiejący polecenia postaci: leć trochę

wyżej, skręć mocno w prawo,

• sprzęt elektroniczny powszechnego użytku: np. AGD lodówki, pralki,mikrofalówki.

Najważniejsze paradygmaty:

• pojęcie zbioru rozmytego, algebra zbiorów rozmytych

• powiązanie zbiorów rozmytych i miar prawdopodobieństwa,

• zmienne lingwistyczne oraz wnioskowanie przybliżone,

• inne: rozmyte programowanie dynamiczne, rozmyte podejmowanie

decyzji, rozmyta interpretacja języka, rozmyta algebra,

rozmyte procesy stochastyczne

POJĘCIE ZBIORU ROZMYTEGO

Klasyczna teoria zbiorów:

• Każdy element należy albo do zbioru, albo do jego dopełnienia.

Nie może należeć do obu naraz (prawo niesprzeczności, prawo

wyłączonego środka)

W teorii zbiorów rozmytych przyjmuje, że element może należeć

częściowo do zbioru jak i do jego dopełnienia.

gdzie f(x) – dowolna funkcja o wartościach z przedziału [0,1].

X - uniwersum, zbiór uniwersalny, przestrzeń elementów; x c X

A - zbiór rozmyty, koncepcja, zmienna lingwistyczna,

μA(x) - funkcja charakterystyczna (funkcja przynależności) określa

stopień, w jakim element x należy do zbioru A.

Sposoby definowania zbiorów rozmytych:

• analityczna postać funkcji przynależności

(np. krzywa Gaussa, trójkątna, trapezoidalna)

• wyliczenie par (wartość, stopień przynależności)

Funkcja przynależności to nie jest prawdopodobieństwo:

• np. łysy w 80% to nie to samo, co łysy 1 na 5 razy.

• prawdopodobieństwo jest unormowane do jedynki,

a funkcja przynależności nie.

Teoria zbiorów rozmytych jest uogólnieniem klasycznej teorii zbiorów.

WŁASNOŚCI ZBIORÓW ROZMYTYCH

Nośnikiem zbioru rozmytego A nazywamy zbiór wartości x , dla

których funkcja przynależności jest nieujemna:

Support (baza) zbioru rozmytego A: supp(A) = { x c X : μA(x)>0 }

Core (jądro) zbioru rozmytego A: core(A) = { x c X : μA(x)=1 }

a-cut (a-cięcie) zbioru rozmytego A: Aa = { x c X : μA (x)>a }

singleton -> zbiór rozmyty, który stanowi tylko jeden punkt x z

wartością μ A(x)>0

Dopełnienie zbioru A, to zbiór rozmyty A o funkcji przynależności:

μ (x) A = 1 - μA (x)

Podstawowymi operacjami na zbiorach rozmytych są:

• negacja (NOT)

• suma (OR)

• iloczyn (AND)

• Poniżej przedstawione są liczbowe przykłady powyższych operacji logicznych:

 

NEGACJA:

Jeżeli mamy dany podzbiór rozmyty A zbioru Y, to jego negacją jest podzbiór Ā=Y-A. Czyli dla każdego y należącego do A mamy Ā(y)=1-A(y)

Przykład:

JeżeliA={	a/1;	b/0,4;	c/0,8;	d/0,2;	e/0 }
to     Ā={	a/0;	b/0,6;	c/0,2;	d/0,8;	e/1 }

   

SUMA:

Jeżeli mamy dane podzbiory rozmyte A i B zbioru Y, to ich sumą jest podzbiór C=AorB. Czyli dla każdego y należącego do Y mamy C(y)=Max[A(y), B(y)]

Przykład:

A={	a/1;	b/0,3;	c/0,8;	d/0;	e/0,1}
B={	a/0,6;	b/0,4;	c/0,9;	d/0,5;	e/0,7}
C={	a/1;	b/0,4;	c/0,9;	d/0,5;	e/0,7}

 

ILOCZYN:

Jeżeli mamy dane podzbiory rozmyte A i B zbioru Y, to ich iloczynem jest podzbiór C=AandB.

Czyli dla każdego y należącego do Y mamy C(y)=Min[A(y), B(y)]:

Przykład:

A={	a/1;	b/0,3;	c/0,8;	d/0;	e/0,1}
B={	a/0,6;	b/0,4;	c/0,9;	d/0,5;	e/0,7}
C={	a/0,6;	b/0,3;	c/0,8;	d/0;	e/0,1}

• Zadanie – zbiory rozmyte:

Lp.	Zbiór	Wartości
1.	Temperatura	Niska
2.	Obsługa	Wolna
3.	Napiwek	Mały

W zależności od wartości dwóch powyższych czynników ustalamy wartość napiwku:

Temperatura Obsługa	Niska	OK.	Wysoka
Wolna	Mały	Średni	Mały
Średnia	Mały	Średni	Mały
Szybka	Średni	Duży	Średni

1. Algorytmy Mrówkowe

Algorytmy mrówkowe należą do metod heurystycznych, czyli takich w których nie ma gwarancji znalezienia rozwiązania optymalnego, a jedynie wskazanie najlepszego jakie w wyniku zastosowania metody udało się znaleźć. Mrówki wędrując pozostawiają na podłożu ślad feromonowy, który z czasem się ulatnia. Mrówki mając do wyboru wiele dróg wybierają te które są najlepiej oznakowane. Fakt, że droga ta jest najczęściej najkrótsza wynika z tego, że na drogach częściej uczęszczanych znajduje się większa ilość feromonu i jest on dłużej zachowywany. Po pewnym czasie droga między gniazdem a pokarmem jest bardzo bliska drodze optymalnej.

Bardzo interesującym zachowaniem kolonii jest jej umiejętność przystosowania się do zmian w środowisku, znalezienie alternatywnej drogi w przypadku, gdy poprzednia przestaje spełniać swoje zadanie

• ponieważ ścieżka A jest krótsza, w związku z tym do pokarmu docierają jako pierwsze.

• Jako drogę powrotną wybierają drogę A ponieważ tylko na niej znajdują się feromony

• Mrówki które przybyły trasą B także jako drogę powrotną wybiorą drogę A gdyż na niej występuje wyższe stężenie feromonówMrówki podążają drogami A i B pozostawiając za sobą feromony

Metody te wyróżniają się dwiema pozytywnymi cechami:

• Prosta zrozumiała idea

• Duża efektywność działania

• Kompromis pomiędzy efektywnością a skutecznością metody, który jest obecny w przyrodzie a nie występuje w klasycznych

metodach optymalizacji

Zastosowanie:

• problemie transportowym,

• zagadnieniu przydziału,

• szeregowaniu zadań,

• kolorowaniu grafu,

• sortowaniu sekwencyjnym,

• problemie komiwojażera,

• wyznaczaniu tras w sieciach telekomunikacyjnych.

Zadanie:

Typowy problem komiwojażera

Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Przy czym każde miasto może być odwiedzone tylko raz. Rozwiązanie polega na znalezieniu minimalnej trasy podróży.

• Połączenia  między miastami inicjowane są z pewną (niewielką) ilością feromonu. Pewna liczba mrówek umieszczona jest na losowo wybranych miastach.

• Mrówki poruszają się z miasta do miasta. Nie mogą wracać do miasta, w którym  już były. Miasto do którego przemieści się mrówka wybierane jest losowo jednakże preferowane są miasta bliżej położone i te z większą ilością feromonu.

• Gdy wszystkie mrówki zakończą obchód wszystkich miast to  feromon na wszystkich ścieżkach zmniejsza się o pewną wartość (parowanie). Ponadto feromon na ścieżkach, którymi przeszły mrówki zwiększa się o ilość odwrotnie proporcjonalną do całkowitej długości trasy danej mrówki (im krótsza trasa tym większy przyrost).

Konstrukcja najkrótszej ścieżki dla problemu komiwojażera

W algorytmie mrówkowym dla problemu komiwojażera, skończona liczba mrówek wspólnie znajduje rozwiązanie wykorzystując zapamiętane informacje w postaci śladów z feromonów. Algorytm ten działa wg poniższego schematu:

1. Każdy osobnik budując rozwiązanie lub jego część decyduje się na wybór alternatywnych możliwości z prawdopodobieństwem zależnym od dwóch czynników:

   • ilości feromonu związanego z danym rozwiązaniem (połączeniem między danymi dwoma miastami)

   • wartości lokalnej funkcji kryterium (odległość między dwoma danymi miastami.)

2. W klasycznym algorytmie mrówkowym powyższe prawdopodobieństwo określa się według wzoru:
   F_ij=

gdzie: - feromon znajdujący się na łuku (i,j)

- wartość lokalnej funkcji kryterium

- parametr regulujący wpływ

- parametr regulujący wpływ

- dopuszczalne rozwiązania (np. pozostałe do odwiedzenia miasta)

1. Najistotniejszym elementem algorytmu jest takie umiejętne sterowanie parametrami alfa i beta, aby alfa nie było ani zbyt małe w stosunku do beta (wtedy algorytm działa jak startujący z różnych punktów algorytm konstrukcyjny, dając rozwiązanie oparte na optymalizacji lokalnych funkcji), ani też alfa nie było zbyt duże, bo wtedy algorytm bada jedynie wąski obszar przestrzeni rozwiązań, w którym na ogół znajduje się jedynie optimum lokalne.

2. Po skończeniu trasy czyli wygenerowaniu rozwiązania, mrówka zostawia na swej drodze feromon w ilości określonej wzorem [stała] * [wartość f_k kryterium dla rozwiązania będącego trasą mrówki k ]

3. Podobnie jak to ma miejsce w naturze, gdzie feromon po jakimś czasie wyparowuje, w algorytmie mrówkowym w każdej iteracji ilość feromonu pomniejszana jest o pewien współczynnik, dzięki czemu unika się zbyt wczesnej zbieżności rozwiązania przed dostatecznym zbliżeniem się do optymalnych jego wartości.