1. Zbiór rozmyty, zbiór normalny, wysokość zbioru
Zbiorem rozmytym A w pewnej (niepustej) przestrzeni X, co zapisujemy jako A Í X, nazywamy zbiór uporządkowanych par
gdzie:
jest to funkcja przynależności zbioru rozmytego A. Funkcja ta każdemu elementowi x Î X przypisuje jego stopień przynależności do zbioru rozmytego A, przy czym można wyróżnić 3 przypadki:
1. μA(x) = 1 oznacza pełną przynależność do zbioru rozmytego A, tzn. x Î A,
2. μA(x) = 0 oznacza brak przynależności elementu x do zbioru rozmytego A, tzn. x ∉ A,
3. 0 < μA(x) < 1 oznacza częściową przynależność elementu x do zbioru rozmytego A.
Symboliczny zapis zbiorów rozmytych.
Ponieważ niewygodnie jest posługiwać się uporządkowanymi dwójkami zapisywanymi np. w nawiasach, stosuje się zapis symboliczny. I tak, jeżeli X jest przestrzenią o skończonej liczbie elementów, X = {x1, ..., xn}, do zbioru rozmytego A określonego na przestrzeni X stosujemy zapis:
Warto tu zauważyć, że elementami zbioru X mogą być nie tylko liczby, ale również inne przedmioty, osoby lub pojęcia. Zapis ten ma charakter symboliczny. Kreska ułamkowa nie oznacza dzielenia a przyporządkowanie poszczególnym elementom zbioru stopni przynależności. Podobnie znak „+” nie oznacza dodawania, a sumę mnogościową elementów.
Jeżeli X jest przestrzenią o nieskończonej liczbie elementów, to zbiór A Í X symbolicznie zapiszemy jako:
Zbiór rozmyty normalny
Normalnym nazywamy zbiór rozmyty wtedy i tylko wtedy, gdy h(A) = 1. Jeśli zbiór rozmyty A nie jest normalny, to możemy go znormalizować poprzez przekształcenie:
gdzie h(A) jest wysokością tego zbioru.
Wysokość zbioru rozmytego
Wysokość zbioru rozmytego A oznaczamy przez h(A) i określamy jako:
W przypadku zbiorów przeliczalnych jest to maximum funkcji przynależności.
2. Tworzenie populacji początkowej (algorytmy genetyczne) - Przykład
Inicjacja jest to utworzenie początkowej populacji chromosomów, polega na losowym wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.
Przykład.
Zgodnie z algorytmem zaczynamy od wylosowania populacji początkowej. Zakładamy, że liczebność naszej populacji będzie wynosić 8 osobników. W wyniku losowania otrzymujemy:
ch1 = [00110] ch2 = [00101]
ch3 = [01101] ch4 = [10101]
ch5 = [11010] ch6 = [10010]
ch7 = [01000] ch8 = [00101]
Teraz rozpoczyna się główna pętla algorytmu genetycznego. Najpierw obliczamy przystosowanie poszczególnych osobników. Trzeba zdekodować informacje zawarte w chromosomach, otrzymujemy następujące fenotypy:
ch1* = 6 ch2* = 5
ch3* = 13 ch4* = 21
ch5* = 26 ch6* = 18
ch7* = 8 ch8* = 5
Następnie obliczamy wartość funkcji przystosowania, która jest taka sama jak funkcja optymalizowana. Za x podstawiamy wyliczone właśnie fenotypy:
F(ch1) = 2 × ch1 + 1 = 13
F(ch2) = 2 × ch2 + 1 = 11
F(ch3) = 2 × ch3 + 1 = 27
F(ch4) = 2 × ch4 + 1 = 43
F(ch5) = 2 × ch5 + 1 = 53
F(ch6) = 2 × ch6 + 1 = 37
F(ch7) = 2 × ch7 + 1 = 17
F(ch8) = 2 × ch8 + 1 = 11
3. Suma zbiorów rozmytych
Sumą zbiorów rozmytych A i B jest zbiór rozmyty A È B określony funkcją przynależności:
mAÈB(x) = max(mA(x), mB(x)) dla każdego x Î X.
Suma większej ilości zbiorów A1, A2, A3, …, An określona jest podobną funkcją przynależności:
mA1ÈA2ÈA3… ÈAn (x) = max(mA1(x), mA2(x) , mA3(x), …, mAn(x)) dla każdego x Î X.
Ilustracja operacji sumy.
Działanie operacji sumy zbiorów rozmytych możemy przedstawić na rysunku:
Rysunek 1. Operacja sumy zbiorów rozmytych.
4. Zbiory rozmyte równe
Zbiór rozmyty A jest równy zbiorowi rozmytemu B, co zapisujemy A = B, wtedy i tylko wtedy, gdy: mA(x) = mB(x) dla każdego x Î X.
5. Poziom równości zbiorów rozmytych
Stopień równości.
Poprzednia definicja jest definicją sztywną. Mamy do czynienia ze zbiorami rozmytymi, dlatego jeśli funkcje przynależności dwu zbiorów rozmytych są podobne, możemy powiedzieć, że zbiory są prawie równe i wprowadzić pojęcie stopnia równości zbiorów rozmytych A i B jako:
gdzie T = {x Î X: mA(x) ¹ mB(x)}.
Nie jest to jedyna możliwość, można spotkać różne definicje stopnia równości lub też stopnia inkluzji zbiorów rozmytych.
6. Wartość bezwzględna liczby rozmytej
Wartość bezwzględną liczby rozmytej A Í R oznaczamy |A| Í R i określamy jako:
Liczba rozmyta |A| jest liczbą rozmytą dodatnią.
7. Mutacja w algorytmach genetycznych
Mutacja polega na zmianie wartości genu na przeciwną w przypadku binarnego kodu w chromosomach. Zmiany tej dokonuje się dla każdego genu z prawdopodobieństwem mutacji, które jest bardzo małe, dlatego też zachodzi bardzo rzadko.
Możemy np. losować liczbę z przedziału [0, 1] i jeśli jest mniejsza od wartości prawdopodobieństwa mutacji, mutacja zachodzi i zmieniamy wartość genu. Jeśli wylosowana liczba jest większa, mutacja nie zachodzi. Podobnie jak dla krzyżowania.
Wpływ mutacji.
Rozważmy teraz wpływ mutacji. Mutacja zachodzi albo w puli populacji potomków, albo w populacji rodzicielskiej. Możemy zatem rozważać wpływ tej mutacji tylko na pulę rodzicielską, gdyż populacja potomków będzie pulą rodzicielską w następnej generacji, a właśnie o wpływ na pulę rodzicielską nam chodzi.
Operator mutacji zmienia z prawdopodobieństwem pm zmienia wartość jakiegoś bitu na przeciwną. Jeżeli schemat ma przetrwać mutację, to ustalone pozycje w schemacie, czyli zera i jedynki powinny pozostać niezmienione. Mutacja może zachodzić dla każdego bitu. Prawdopodobieństwo mutacji wynosi pm, czyli prawdopodobieństwo, że mutacja nie zajdzie to 1 – pm. Prawdopodobieństwo tego, że mutacja zajdzie na kilku bitach jest iloczynem poszczególnych prawdopodobieństw, a tego, że nie zajdzie też jest odpowiednim iloczynem.
pm∙ pm∙ pm∙ pm pm∙…= pmL – jest prawdopodobieństwem zajścia mutacji na wszystkich bitach chromosomu.
(1 – pm) ∙(1 – pm)…= (1 – pm)L – jest prawdopodobieństwem nie zajścia mutacji na wszystkich bitach chromosomu.
Ostatecznie prawdopodobieństwo tego, że mutacja nie zajdzie dla żadnej ustalonej pozycji w schemacie wynosi:
Wniosek 4 – wpływ mutacji.
Dla danego chromosomu ze zbioru M(t) Ç S, czyli z populacji rodzicielskiej pasującego do schematu S, prawdopodobieństwo, że chromosom ten będzie należał do schematu S po operacji mutacji, jest dane przez
Jest to prawdopodobieństwo przetrwania mutacji przez schemat S.
Wniosek 5 – wpływ mutacji.
Jeżeli prawdopodobieństwo mutacji pm jest małe, (pm << 1), to można przyjąć, że prawdopodobieństwo przetrwania mutacji przez schemat S, jest w przybliżeniu równe:
Mutacja.
Operacja mutacji jest dokonywana jest na pojedynczym osobniku. Jako pierwszy mutacji poddawany jest chromosom odchyleń standardowych zgodnie z formułą:
gdzie:
n – długość chromosomu
N(0, 1) – liczba losowa z rozkładu normalnego losowana dla całego chromosomu
Ni(0, 1) - liczba losowa z rozkładu normalnego losowana dla każdego genu osobno
t’, t - parametry strategii ewolucyjnej
Najczęściej spotykaną postacią tych parametrów jest:
C najczęściej przyjmuje wartość 1.
W ten sposób obliczone nowe zakresy mutacji wpływają na zmianę wartości genów niezależnych x tak jak w poprzedniej strategii:
gdzie znowu Ni(0, 1) jest liczbą losową z rozkładu normalnego.
Mutacja binarna.
Operator mutacji ma za zadanie wprowadzenia pewnego urozmaicenia w populacji. W klasycznym algorytmie genetycznym jego rola jest raczej mała, natomiast w strategiach ewolucyjnych jest on podstawowym operatorem.
W przypadku mutacji binarnej, operacji mutacji podlegały wszystkie geny z założonym bardzo małym prawdopodobieństwem. Mutacja w takim wypadku może polegać na negacji wartości bitu, lub na zamianie wartości bitu na wartość losową.
Mutacja zmiennoprzecinkowa.
Jeżeli chromosom jest kodowany za pomocą liczb rzeczywistych nie można przeprowadzić zwykłej mutacji.
Jeżeli wartość i – tego genu jest ograniczona przedziałem [ai, bi], to jeżeli gen podlega mutacji, to przeprowadzamy ją według wzoru:
yi = ai + (bi - ai)Ui(0,1)
gdzie Ui(0,1) – zmienna losowa wygenerowana z rozkładu równomiernego w przedziale (0, 1).
W tym wypadku nowa wartość genu nie zależy od wartości poprzedniej. Możliwa jest też mutacja, gdzie do starej wartości genu dodajemy losową wartość, najczęściej z rozkładu normalnego.
yi = xi + zi
Inwersja działa na pojedynczym chromosomie zmieniając kolejność alleli pomiędzy dwoma losowymi pozycjami w chromosomie.
Operator ten został zdefiniowany poprzez analogię do biologicznego procesu inwersji chromosomowej, jednak jest on raczej stosowany bardzo rzadko. Jego działanie dla chromosomu przedstawionego niżej z punktami inwersji 4 i 11, wygląda tak:
[0010 1000111 10001] ® [0010 1110001 10001]
8. Standardowe funkcje przynależności w Zbiorach rozmytych
Singelton.
W różnych zastosowaniach zbiorów rozmytych używa się standardowych funkcji przynależności. I tak mamy funkcję singelton, zdefiniowaną wzorem:
Jest to specyficzna funkcja przynależności, gdyż przyjmuje wartość 1 tylko w jednym punkcie przestrzeni, w pozostałych punktach przyjmuje wartość 0. Ta funkcja charakteryzuje jednoelementowy zbiór rozmyty, jedynym elementem tego zbioru jest punkt x-kreska. Funkcja ta jest stosowana głównie do operacji rozmywania w rozmytych systemach wnioskujących. W sumie jest bardzo podobna do delty Diracka stosowanej w przetwarzaniu sygnałów, która to delta Diracka też przyjmuje wszędzie 0, poza jednym punktem, gdzie ma wartość nieskończoną.
Funkcja Gausowska.
...