Algorytmy.Genetyczne.A.Logika.Rozmyta

[ Pobierz całość w formacie PDF ]
Algorytmy genetyczne a logika rozmyta
Politechnika Wrocławska 1998
Bogusław Molecki Algorytmy genetyczne a logika rozmyta
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_____________________________________________________
1.
Wprowadzenie
Popularne w ostatnich latach algorytmy genetyczne, pozwalają na symulację w komputerowym
środowisku procesów ewolucyjnych na organizmach reprezentujących różne próby rozwiązania różnych, często
silnie skomplikowanych problemów optymalizacji.
Logika rozmyta natomiast bardzo dobrze nadaje się do wykorzystania przy problemach, gdzie posiadana
informacja, charakteryzująca środowisko, jest niepewna i nieprecyzyjna. Jak wyjaśnił twórca logiki rozmytej, L.
Zadeh, systemy wykorzystujące ją mają dwa zastosowania:
•
wąskie, w którym logika rozmyta jest używana do przybliżonego rozumowania,
•
szerokie, w którym jest ona wykorzystywana wraz z teorią zbiorów rozmytych, czyli klasą obiektów,
w których przejście między należeniem a nienależeniem jest stopniowe, a nie gwałtowne.
Połączenie tych dwóch technik może być więc bardzo obiecujące. W związku z tym, przeprowadzona została
krótka analiza problemu, na podstawie ogólnie dostępnej literatury, zarówno z wykorzystaniem danych ze
zbiorów dr Haliny Kwaśnickiej, jak i zbiorów bibliotecznych Politechniki Wrocławskiej oraz artykułów
dostępnych w Internecie. Pełen spis podany jest na końcu opracowania.
Podstawowe dziedziny, w których połączenie algorytmów genetycznych i logiki rozmytej może być
wykorzystane, zostały wymienione w opracowaniu [Cor ??]. Przytoczone opracowanie stanowi krótki wstęp -
opis do bibliografii dotyczącej połączenia logiki rozmytej i algorytmów genetycznych. Bibliografia ta [Cor 96],
uwzględniająca podział wymieniony w [Cor ??] jest bardzo cennym opracowaniem, umożliwiającym dalsze
poszukiwania w dokładniej już określonej dziedzinie zastosowań. Dodatkową zaletą jest w tym przypadku
możliwość łatwego uzyskania jej z Internetu, w postaci plików .html, lub .ps.
W niniejszym opracowaniu natomiast, za cel przyjęto przedstawienie podstawowych zasad połączenia obu
dziedzin, wraz z przeglądem występujących możliwości ich zastosowań. Algorytmy genetyczne wraz z logiką
rozmytą (której skrócone zasady przedstawione są w rozdziale 2.) znajdują zastosowanie w:
•
rozmytych algorytmach genetycznych (opis w rozdziale 3.),
•
optymalizacji sterowników rozmytych (opis w rozdziale 4.),
•
zadawaniu pytań do baz danych (opis w rozdziale 5.),
•
modelowaniu reakcji chemicznych (opis w rozdziale 6.),
•
problemach podziału i klasyfikacji (opis w rozdziale 7.),
•
podejmowanie decyzji ekonomiczno-finansowych (opis w rozdziale 8.),
oraz innych, nie opisanych tu bezpośrednio dziedzinach zastosowań, takich jak:
•
sieci neuronowe,
•
systemy ekspertowe.
3
 Bogusław Molecki Algorytmy genetyczne a logika rozmyta
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_____________________________________________________
2.
Od logiki tradycyjnej do logiki rozmytej
Na co dzień jesteśmy przyzwyczajeni do tradycyjnej logiki dwuwartościowej, z wartościami równymi
prawdzie i fałszowi. Jednym z możliwych zapisów wartości, który będzie używany w tym opracowaniu, polega
na oznaczeniu prawdy przez wartość 1, a fałszu przez 0. Dla przypomnienia (i możliwości porównania z
następnymi przypadkami) podam tablice wartościujące działania trzech operatorów logicznych (negacji, sumy i
koniunkcji):
¬
∨
0 1
∧
0 1
0 1
0
0 1
0
0
0
1 1
1 1 1
1 0 1
W pewnych przypadkach jednak sytuacja nie daje opisać się tak restrykcyjnymi pojęciami jak prawda i fałsz,
„białe” i „czarne”. Postaci jednoznacznie dobre i jednoznacznie złe występują jedynie w bajkach dla dzieci i
czechosłowackich westernach („Lemoniadowy Joe”). W większości rzeczywistych przypadków wartość leży
gdzieś pośrodku, mówiąc popularnie jest „szara”.
Dlatego właśnie powstały logiki wielowartościowe, których teorię opracował polski matematyk, Jan Łukasiewicz
(1878÷1956). Mianem tym są określane logiki, które dopuszczają trzy i więcej wartości. W najprostszym
przypadku dopuszczona jest dodatkowa w stosunku do logiki tradycyjnej, trzecia wartość, którą liczbowo określa
się jako 0,5 (tzw. półprawda). Tablice wartościujące działania logiczne wykorzystują znane reguły
„odziedziczone” niejako z logiki tradycyjnej:
¬
A = 1 - A
(2.1.);
A
∧
0 = 0
(2.2.);
A
∧
1 = A
(2.3.);
A
∨
0 = A
(2.4.);
A
∨
1 = 1
(2.5.).
. Jak widać,
pozostało wolne miejsce wewnątrz tablic, wypełnione są jedynie krawędzie (efekt ten jest jeszcze bardziej
widoczny przy logikach więcej-wartościowych).
∧
i
∨
¬
∨
0
0,5 1
∧
0
0,5 1
0 1
0
0
0,5 1
0
0
0
0
0,5
0,5
0,5
0,5
?
1
0,5
0
?
0,5
1 1
1 1 1 1
1 0
0,5 1
Wartości w centrum tablic nie można wyznaczyć jednoznacznie, wykorzystując zależności z logiki tradycyjnej.
Oto przykład:
B = A;
A
∧
B = A
∧
A = A
(2.6.);
B =
¬
A;
A
∧
B = A
∧
¬
A = 0
(2.7.);
Powyższe związki (2.6. oraz 2.7.) są prawdziwe dla logiki tradycyjnej. Niestety, uogólnienie ich na logikę
wielowartościową musi zakończyć się porażką. Dla przykładu niech A=0,5. Tzw. „zdrowy rozsądek”
podpowiada nam, że powyższe zależności powinny być spełnione w każdej logice. W tym przypadku jednak,
wartościując równania (2.6. i 2.7.) otrzymamy następujące wyrażenia:
(z 2.6.): A
∧
B = 0,5
∧
0,5 = 0,5
(2.8.);
(z 2.7.): A
∧
B = 0,5
∧
0,5 = 0
(2.9.);
) dla takich samych wartości dawać powinien dwa różne wyniki (2.8. i 2.9.).
Analogiczny przykład można podać dla operatora
∧
∨
. Rozwiązanie powstało przez stworzenie dodatkowych
4
Niestety, reguły te nie wystarczają do wypełnienia całej tablicy wartościowania dla spójników
Jak widać, ten sam operator (
 Bogusław Molecki Algorytmy genetyczne a logika rozmyta
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_____________________________________________________
operatorów - tzw. „strong-operators” [Kin 98]. Przyjęto następujące ich definicje, rozwiewające wyżej opisane
wątpliwości:
A
∧
B = min(A,B)
(2.10.);
A
⊗
B = max(0,A+B-1)
(2.11.);
A
∨
B = max(A,B)
(2.12.);
A
⊕
B = min(1,A+B)
(2.13.);
Na tej podstawie określa się tabele wartościowania operatorów logicznych w logikach wielowartościowych -
poniżej podane są, pełne już, tablice wartościowań dla logiki trójwartościowej:
¬
∨
0
0,5 1
∧
0
0,5 1
0 1
0
0
0,5 1
0
0
0
0
0,5
0,5
0,5
0,5
0,5 1
0,5
0
0,5
0,5
1 1
1 1 1 1
1 0
0,5 1
Kolejnym krokiem w rozwoju logik niebinarnych było stworzenie przez Lotfiego Zadeha (1921÷) [Woe 95]
logiki rozmytej. Można wyróżnić dwa „poziomy” wykorzystywania logiki rozmytej - pierwszy polega na użyciu
logiki rozmytej jako naturalnego rozszerzenia logiki wielowartościowej (przejście z wyznaczonych n wartości
dyskretnych w logikach n-wartościowych na nieskończoną liczbę wartości z przedziału [0;1] w logice rozmytej).
Często ta część teorii logiki rozmytej wykorzystywana jest nieświadomie, bez wgłębienia się w dalsze jej
zależności. Tymczasem, logika rozmyta nawet w tym, wąskim rozumieniu niesie dodatkowe definicje, które
porządkują m.in. operatory logiczne.
W logikach wielowartościowych, jak wspomniałem wyżej, definiowane były prócz zwykłych operatorów (
∧
oraz
(patrz wzory 2.10. ÷ 2.13), które definiowały skrajne wartości możliwe przy próbie
rozszerzenia zwykłych operatorów
) operatory
⊗
oraz
⊕
na logiki wielowartościowe. Poniżej podane są tablice wartościowań dla
logiki trójwartościowej właśnie tych operatorów:
∧
i
∨
⊕
0
0,5 1
⊗
0
0,5 1
0
0
0,5 1
0
0
0
0
0,5
0,5 1 1
0,5
0
0
0,5
1 1 1 1
1 0
0,5 1
W logice rozmytej wszelkie operatory, których wyniki działania mieszczą się pomiędzy operatorami zwykłymi a
dodatkowymi („strong-”) ujęte są w postaci norm. Operatory iloczynu w logice rozmytej określane są przez tzw.
T-normy. Operatory sumy określane są jako T-conormy, dualne do T-norm. W polskiej literaturze znaleźć
można określenie „S-norma” w stosunku do T-conorm, które jednak nie wydaje się najwłaściwsze.
W zależności od podejścia, przeprowadzane w logice rozmytej obliczenia, mogą wykorzystywać różne operatory
sumy i iloczynu. Najbardziej popularne 11 definicji operatorów przytoczonych zostało w [Rut 97]. Poniżej
przytoczone zostały pierwsze cztery pozycje zestawienia (operatory nieparametryzowane).
L.p.
T-norma (operatory
∧
)
T-conorma (operatory
∨
)
1
min(A,B)
max(A,B)
2
A*B
A+B-A*B
3
max(A+B-1,0)
max(A+B-1)
4
A jeżeli B=1
B jeżeli A=1
0 jeżeli A,B
A jeżeli B=0
B jeżeli A=0
1 jeżeli A,B
≠
1
≠
0
5
∨
Bogusław Molecki Algorytmy genetyczne a logika rozmyta
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_____________________________________________________
Szersze zastosowanie logiki rozmytej polega na wykorzystaniu funkcji rozmytych przynależności do zbiorów.
Określenie rozmytej przynależności do zbiorów pozwala na opisanie wartości zmiennej, bez podawania liczby
opisującej tę wartość, a jedynie zbiorów, do których należy, wraz ze stopniem przynależności.
Przykładem może być tu opis temperatury.
Rys. 2.1.
Opis temperatury za pomocą zbiorów rozmytych
Jak widać na powyższym rysunku, temperatura opisana może być za pomocą terminów słownych, określających
zbiory rozmyte (podział na rysunku wykonany został według osobistych odczuć autora, stąd być może nie
odpowiada on powszechnemu). I tak, temperatura 20°C należy w 100 % do temperatur odpowiednich, zaś np.
6°C w połowie do chłodnych, w połowie do ciepłych. Podobnie, -29,4°C w 70% należy do silnie mroźnych, a w
30% do mroźnych. Rysunek w pełni wyjaśnia proces zamiany wartości liczbowej na wartość opisywaną
funkcjami przynależności w logice rozmytej. Proces ten nazywany jest fuzzyfikacją (dokładniejszy opis w [Hei
??] i [Hry 96]).
Figury określające stopień przynależności danego obszaru wartości do określonych zbiorów rozmytych mogą być
trapezami, trójkątami, lub innymi figurami geometrycznymi. Ich kształt i usytuowanie powinno jednak zapewniać
fakt należenia każdej z wartości zmiennej w sumie w 100% (w innych przypadkach konieczna jest późniejsza
normalizacja) do zbiorów rozmytych.
Procesem odwrotnym (przejście z wartości logiki rozmytej na wartości liczbowe) jest defuzzyfikacja. W tym
przypadku obszary często definiowane są także jako trapezy odwrócone, lub singletony (pionowe prążki
wskazujące środek ciężkości zbioru). Proces zamiany na wartości liczbowe polega na określeniu wartości jako
średniej ważonej (aktywnymi polami figur) środków ciężkości tych figur. Aktywne pola figur to pola, obliczane
od ich podstawy do wysokości odpowiadającej wartości stopnia przynależności do zbioru (stąd przydatne są w
niektórych zastosowaniach trapezy odwrócone). Wyjaśnia to rysunek poniżej :
P
ZI
=1,81 P
CH
=4,00 T=(1,81*10+4,00*15)/(1,81+4,00)
Rys. 2.2.
Obliczenie wartości na podstawie stopni przynależności do zbiorów rozmytych
Dokładniejszy opis zawierają [Hei ??], [Hry 96]. Ze względu na charakter wykorzystywanych w rzeczywistych
zastosowaniach reguł rozmytych, suma stopni przynależności do poszczególnych zbiorów nie musi być równa
jeden ! Stąd konieczne jest zapewnienie normalizacji przy średniej ważonej nawet w przypadku użycia
singletonów.
Więcej informacji na temat teorii logiki rozmytej zawierają pozycje [Dri 96] i [Rut 97].
6
[ Pobierz całość w formacie PDF ]