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

GENETYK

Podczas zajęć wykorzystywaliśmy program „Genetyk”, 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.

Przykład:

Jeśli chcemy stworzyć program, który zawsze będzie znajdywał drogę wyjścia z labiryntu funkcja oceny będzie sprawdzała jak daleko „zaszedł” dany program.

Te programy, który znajdują poprawne wyjście otrzymują najwięcej punktów, natomiast te, które od wyjścia się oddalają otrzymują tych punktów najmniej.

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.

PROLOG

Kolejnym poznanym przez nas programem był SWI Prolog, w którym tworzyliśmy drzewo genealogiczne i wyznaczaliśmy przodków. Podczas procedury tworzenia kodu nie posługiwaliśmy się typowymi - jak w przypadku innych języków programowania - instrukcjami wykonywanymi od początku do końca. Program ten jest bazą wiedzy (danych), oraz opisem reguł wnioskowania.

Przykład:

Napisać relacje rodzinne w drzewie genealogicznym.

##kod programu:

baba(Janina).

baba(jenna).

baba(wanda).

baba(stefania).

baba(mieczyslawa).

baba(wladyslawa).

baba(iza).

baba(pamela).

facet(marian).

facet(stefan).

facet(ambrozy).

facet(Marek).

facet(pawel).

facet(kamil).

facet(madafaka).

facet(baltazar).

facet(darek).

facet(jozio).

facet(brutus).

rodzice(stefan,jenna,Marek).

rodzice(ambrozy,wanda,kamil).

rodzice(ambrozy,wanda,pawel).

rodzice(Marek,stefania,iza).

rodzice(Marek,stefania,wladyslawa).

rodzice(Marek,stefania,baltazar).

rodzice(ambrozy,wanda,mieczyslawa).

rodzice(marian,Janina,ambrozy).

rodzice(marian,Janina,stefania).

rodzice(madafaka,iza,pamela).

rodzice(darek,wladyslawa,jozio).

rodzice(darek,wladyslawa,brutus).

## 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):-facet(X),rodzice(A,B,X),rodzice(Y,Z,A).

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

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

wnuczka(X,Y,Z):-baba(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):-facet(X),malzenstwo(X,A),rodzenstwo(Y,A).

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

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

synowa(X,Y,Z):-baba(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).

facet(marek).

facet(kuba).

baba(janina).

dziecko(marek,kuba).

dziecko(kuba,Janina.

% *** reguły wnioskowania:

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

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

Prolog jest bardzo pomocny przy rozwiązywaniu różnego typu problemów.

W tym programie można operować także na listach (sumowanie elementów, dodawanie elementu do listy, usuwanie, itp.).

Przykład:

Wykorzystanie rekurencji i list w Prologu.

zwraca dlugosc 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).

GABI

Gabi to program służący 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.

ZBIORY ROZMYTE

Klasyczna logika bazuje na dwóch wartościach reprezentowanych najczęściej przez: 0 i 1 lub prawda i fałsz. Granica między nimi jest jednoznacznie określona i niezmienna. Logika rozmyta stanowi rozszerzenie klasycznego rozumowania na rozumowanie bliższe ludzkiemu. Wprowadza ona wartości pomiędzy standardowe 0 i 1; `rozmywa' granice pomiędzy nimi dając możliwość zaistnienia wartościom z pomiędzy tego przedziału (np.: prawie fałsz, w połowie prawda).

Polem naszego przykładu niech będzie wiek ludzi. Załóżmy, że chcemy określić granice między ludźmi młodymi, w średnim wieku i starymi. W klasycznej logice będziemy zmuszeni przyjąć stałe niezmienne granice, jak na przykład dla ludzi młodych moglibyśmy przyjąć 0 a 30 lat, dla ludzi w średnim wieku 30 a 40 lat i dla ludzi starych 40 i więcej lat. Jednakże dobrze wiemy, że jeżeli przeprowadzilibyśmy ankietę, w której pytalibyśmy do jakiej z trzech grup zaliczyć 28 latka znalazłoby się kilka osób, którzy przypisaliby go do ludzi w średnim wieku. Jak widać z powyższego przykładu granice przynależności ulegają rozmyciu.

 

     

• Zastosowanie logiki rozmytej :

Logika rozmyta jest stosowana wszędzie tam, gdzie użycie klasycznej logiki stwarza problem ze względu na trudność w zapisie matematycznym procesu lub gdy wyliczenie lub pobranie zmiennych potrzebnych do rozwiązania problemu jest niemożliwe. Ma szerokie zastosowanie w różnego rodzaju sterownikach. Sterowniki te mogą pracować w urządzeniach tak pospolitych jak lodówki czy pralki, jak również mogą być wykorzystywane do bardziej złożonych zagadnień jak przetwarzanie obrazu, rozwiązywanie problemu korków ulicznych czy unikanie kolizji. Sterowniki wykorzystujące logikę rozmytą są również używane na przykład w połączeniu z sieciami neuronowymi.

• Operacje na zbiorach rozmytych:

Podstawowymi operacjami na zbiorach rozmytych są:

• negacja (NOT)

• suma (OR)

• iloczyn (AND)

Poniżej predstawione 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żeli A={	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 }

Przykład:

Lp.	Zbiór	Wartości
1.	Temperatura	Niska	OK.	Wysoka
2.	Obsługa	Wolna	Średnia	Szybka
3.	Napiwek	Mały	Średni	Duż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

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ów. Mró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.

Przykład:

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.)

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

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)

3. 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.

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

5. 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.
   

14

---