On 23 Paź, 13:05, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:

> Trochę EOT, ale ... w jednym aspekcie natura ma przewagę nad komputerami:
> może dość swobodnie wykorzystywać siłę 'komputera molekularnego'.
> Kod genetyczny składa się z dwóch zestawów genów, do tego istnieje
> zjawisko duplikacji genów itp. Mutacja jednego z genów nie powoduje
> ucieczki poprzedniej wartości. Można by w przybliżeniu powiedzieć, że
> w każdej pozycji, każde lokum w genotypie może przyjmować
> RÓWNOCZEŚNIE kilka wartości. Trochę to też przypomina
> mechanikę kwantową ;). W dużym przybliżeniu mówiąc, natura liczy
> funkcję oceny na fenotypie jednocześnie dla bardzo wielu różnych
> kombinacji. U nas gen ma albo wartość A albo B i jeśli
> chcielibyśmy zasymulować naturę wprowadzajac dwa zestawy genów,
> musielibyśmy liczyć funkcję oceny wielokrotnie, dla różnych kombinacji
> genów dobieranych raz z jednego a raz z drugiego chromosomu. Przy
> długich genotypach złożoność obliczeniowa rośnie koszmarnie ...
> Natura zaś się tym nie martwi: wrzuca produkcję białka A, wrzuca
> równolegle produkcję białka B, a funkcją oceny zajmuje się 'komputer
> molekularny' - sprawdzi, jak oba te białka mają się do wszystkich innych
> białek, które są produkowane równolegle w otoczeniu, czy mają na siebie
> jakiś wpływ, czy nie. Mutując A w C nie traci A ;) Tak w dużym
> przybliżeniu ;)
Dobrze że to opisałeś, nie miałem pojęcia że istnieją takie mechanizmy
w
naturalnej ewolucji. Naiwne krzyżowanie cech, nawet na taką skalę jaką
jest cała planeta i miliardy lat czasu, wydaje się słabym pomysłem.

> >Hmmm... może zbudować wiele drzew decyzyjne metodą losowo/zachłanną,
> >następnie osobniki zainicjować węzłami z tych drzew i odpalić algorytm
> >genetyczny... nie wiem czy to ma jakikolwiek sens.
>
> Teraz się zastanawiam, jak Ty to zrobiłeś ;)
>
> Osobnikiem-fenotypem u Ciebie jest klasyfikator. Chromosomem
> jest liniowy zestaw cech, opisujący jednoznacznie klasyfikator. Np.
> lista reguł. Jak ty to właściwie robiłeś ? W jaki sposób upakowałeś
> drzewo decyzyjne w chromosom i w jaki sposób robisz krzyżowanie ?
> To jest sprawa kluczowa.
Kombinowałem bardzo różnie. Np. budowałem tablicę wszystkich
sensownych reguł. Taką tablicę traktowałem jak zbiór atomowych
reguł. Eksperymentowałem z prostymi regułami i z bardziej
skomplikowanymi:

Prosta reguła to np.: if( dane[nr_wiersza][nr_kolumny] operacja
wartość )
Operacja to porównanie typu: równy, różny, mniejszy, itd.
Np. mając 30 kolumn, w każdej kolumnie 50 różnych wartosci, możemy
zbudować
30x50=1500 sensownych reguł typu: if( dane[nr_wier][nr_kol] <=
wartość )

Bardziej rozbudowana reguła to np.: if( vmin <= dane[nr_wier][nr_kol]
<= vmax )
Dla 30 kolumn i 50 różnych wartości wychodzi 30x51x50/2=~40tys
sensownych
reguł.

Najbardziej rozbudowane reguły jakich próbowałem były takie:
if( vmin <= dane[nr_wier][nr_kol_1] operacja dane[nr_wier][nr_kol_2]
<= vmax )
gdzie operacja byla: dodawaniem, odejmowanie, albo mnożeniem.
Ten najbardziej skomplikowany wzór na budowę reguły dawał około 80mln
sensownych reguł, dla zbioru danych jak powyżej.

Takich atomowych reguł można użyć do wypełnienia węzłów w drzewie
decyzyjnym. Drzewo decyzyjne najczęściej budowałem w zwykłej
tablicy liniowej. Każdy element tablicy składał się z:
- reguły atomowej
- indeks tablicy gdy reguła pasuje do rekordu (gdy reguła odpala)
- indeks tablicy gdy reguła nie odpala
- numer klasy do jakiej należy rekord, jeśli element tablicy jest
liściem


Krzyżowania i mutacji dokonywałem na różnych reprezentacjach. Czasami
postępowałem po chamsku: genem było miejsce w tablicy reprezentującej
drzewo, a dopuszczalnymi allelami zbiór reguł atomowych, bądź iloczyn
kartezjański:
- reguł atomowych
- indeksów do węzłów potomnych gdy reguła odpala
- indeksów do węzłów potomnych gdy reguła nie odpala
- klas do jakich zostanie przypisany rekord gdy węzeł jest liściem

Na różne sposoby dodawałem finezji chamskiemu algorytmowi
genetycznemu:
1) Każdy osobnik miał swoją kopię (to chyba diploidalność/
poliploidalność), jeśli w
wyniku mutacji i krzyżowania nie dochodziło do zwiększenia funkcji
przystosowania,
to osobnik z pewnym prawdopodobieństwem zostawał całkowicie
odtwarzany
z kopii.
2) Reguły atomowe miały swój ranking. Jeśli w wyniku mutacji regula r1
została
zastąpiona regułą r2 i doszło do zwiększenia funkcji
przystosowania, to zwiększał
się ranking reguły r2. Reguły z większym rankingiem miały (dużo)
większe
prawdopodobieństwo wylosowania w następnych mutacjach
3) Budowałem drzewo decyzyjne tylko z jednej reguły, obliczałem
wartość funkcji
przystosowania dla takiego drzewa, a następnie nadawałem regułom
atomowym
początkowy ranking "proporcjonalnie" do wartości funkcji
przystosowania.
4) Wprowadzałem mutację "inteligentną", jeśli reguła przed mutacją
była na
zakresie vmin <= kolumna_x <= vmax, to po mutacji z dużym
prawdopodobieństwem
też dotyczyła kolumny_x, a zakres <vmin,vmax> nieznacznie się
rozszerzał lub
zawężał.

To tyle odnośnie kodowania chamskiego. Poza chamskim stosowałem też
coś co
nie wiem jak się nazywa, a sam nazwałem "systemem głosowania". Każdy
gen był ciągiem
bajtów, czyli wartości z przedziału <0,255>. W każdym genie, czyli w
ciągu
bajtów, były pod-ciągi bajtów. Wartości z każdego podciągu były
sumowane i w
ten sposób była ustalana "siła głosu". Przykładowo rekord składa się z
4-rech
kolumn. Pod-ciąg składa się z 10 bajtów. Więc część genu biorąca
udział w
głosowaniu za wyborem konkretnej kolumny to 4x10=40 bajtów.
Przykładowo
w wyniku zsumowania kolejnych 10-cio bajtowych podciągów wychodzą
wartości: 10,11,20,30.
Największa jest suma czwarta, więc zostanie wybrana kolumna czwarta.
Analogicznym
pod-ciągiem bajtów były zakodowane wszystkie cechy reguły: kolumny,
operacje
arytmetyczne, wartości przedziału <vmin,vmax>, itd. Dalej już nie
muszę
opisywać... z genów powstawały reguły, z reguł drzewa, dla drzew
funkcja
przystosowania, selekcja najlepiej przystosowanych, krzyrzowanie,
mutacja...

Czasami w "systemie głosowania" bajty głosujące na konkretną (jedną)
cechę reguły
rozrzucałem po całym osobniku. Np. bajty głosujące na kolumnę leżały
na losowych pozycjach:
13,34,67,86 w osobniku o długości 100 bajtów. Geny nie były ciągami od
N do N+10 przylegających
do siebie bajtów, ale były maskami bajtów z losowo wybranych pozycji.

> >Problem jest kombinatoryczny z cechami statystycznymi. Czasami
> >różnica jednego bitu powoduje że rekordy powinny przynależeć do
> >innych klas. A czasami kombinacja kilku bitów często się powtarza
> >w jednej klasie. Właśnie chciałbym badać funkcję F przy pomocy
> >klasyfikatora.
>
> Mówisz 'bitu'. Czy elementami rekordów/macierzy są pojedyncze bity ?
Reprezentacje danych w komputerze zawsze można przestawić jako
ciągi bitów. Ale wartości w kolumnach są niezbyt licznym podzbiorem
liczb całkowitych, np. o mocy równej 50.

Użyłem określenia bit, aby podkreślić, że czasami niewielka zmiana w
danych wejściowych może decydować o zmianie ich klasy, a czasami
nawet po istotnej zmianie rekord cały czas należy do tej samej klasy.
Więc dane reprezentują problem z pogranicza problemu kombinatorycznego
i
statystycznego. Liczę na wyłonienie tych statystycznych cech.

> Daj info, jak Ty skonstruowałeś chromosom i krzyżowanie, tymczasem
> ja tu coś wyeksponuję na 'dalszy ciąg':
> Napisałeś wcześniej:
>
> 3) Uwzględnij wszystkie kombinacje liści: K^(N+1)=KxK, razem
> VxCxRxKxK operacji
>
> 3) Wybierz maksymalną sumę sum częściowych dla kombinacji
> klas (liści), mamy Cx(RxK+VxLg(V)+VxK) operacji
>
> Co to znaczy 'kombinacji liści' ?
Liściem nazwałem węzeł który nie zawiera już żadnej reguły, zawiera
tylko numer klasy do której zostanie przypisany rekord.
Drzewo binarne z jedną regułą może zaklasyfikować rekord do jednej z
dwóch klas. Drzewo takie zawiera jeden węzeł z regułą decyzyjną i
dwa liście. Jeśli dopuszczalna ilość klas wynosi K, to pierwszy liść
może zawierać numer klasy od 1 do K. Niezależnie od wartości w
pierwszym liściu, drugi liść także może zawierać numer klasy od 1 do
K.
Daje to K^L wariacji dla L liści, powinienem do razu użyć określenia
wariacji
zamiast kombinacji :) Oczywiście niewielki jest praktyczny sens liści
wyprowadzonych z tego samego węzła i klasyfikujących do tej samej
klasy, można więc zamiast KxK dać Kx(K-1) w drzewie jedno-regułowym.

> W operacji krzyżowania dwóch drzew decyzyjnych widzę tu
> największe pole do popisu - np. przez takie zdefiniowanie krzyżowania,
> by modyfikowało decyzje nadając im różne priorytety (poprzez przestawianie
> węzłów decyzyjnych w górę/w dół drzewa i mieszania ich z decyzjami
> z drugiego drzewa).
Nie sprawdzałem jeszcze tego sposobu, ale czeka na swoją kolej.

> Reguły masz postaci
> "Upraszczając, warunki w węzłach drzewa ograniczmy do M_ij <= C_j,
> gdzie C_j jest jedną z wartości kolumny j."
> Nie bardzo kumam, co oznacza tu owe C_j. To wartość wylosowana ze
> wszystkich rekordów ? Rozumiem, że jest to po prostu jakiś mniej lub
> bardziej przypadkowo wygenerowany współczynnik ?
C_j to konkretna wartość z kolumny. Dajmy przykładową tabelę:
1 4 1 0 5
1 1 0 4 4
2 1 1 3 5
1 1 0 0 1
1 2 0 3 0
2 1 2 2 2
2 2 1 0 4
Kolumna pierwsza to numer klasy.
Kolumna druga to wartość funkcji celu F, jeśli klasyfikator T
na podstawie kolumn 3,4,5 przypisze rekord do dobrej
klasy (tej określonej w pierwszej kolumnie) to funkcja F
zwraca wartość z drugiej kolumny, jeśli klasyfikator T źle
przypisze klasę, to funkcja F zwraca np. wartość z drugiej
kolumny pomnożoną przez -1. Oczywiście klasyfikator "nie zna"
wartości z kolumny pierwszej i drugiej.

Na tym przykładzie widać, że reguła:
if( kolumna_3 < 1 ) then klasa 1
wybierze dokładnie te same rekordy co reguła:
if( kolumna_3 < 1.1 ) then klasa 1
Więc nie ma sensu testować obu reguł. Tylko dlatego
użyłem określenia C_j, aby podkreślić, że zbiór sensowych reguł
jest ograniczony przez ilość wartości w kolumnie j-tej.

Z ograniczonej ilości wartości w kolumnach także wynika wzór
na przyspieszenie dzięki sumom częściowym. W czasie liniowym
względem ilości rekordów można zbudować sumy częściowe funkcji F dla
wszystkich wartości pojawiających się w kolumnie. Następnie w czasie
liniowym
względem ilości wartości można przetestować wszystkie reguły typu:
mniejszy równy.
Więc ilość operacji wynosi ilość_rekordów + ilość_wartości. Bez sum
częściowych
ilość operacji wynosiłaby ilosc_rekordow*ilosc_wartosci.

> Czy w twoim wypadku z jednym węzłem, chromosom wygląda
> po prostu jak czwórka (P, I, K1, K2) - gdzie P to odpowiednik powyższego
> C_j (próg), I to numer branego pod uwagę elementu z rekordu a K1 i K2
> to klasy (liście) ?
> Mam tylko wątpliwości co do tego I 9czy je masz) - nie wiem dokładnie,
> jak to drzewo decyzyjne wybiera u Ciebie jedną z wartości (kolumnę)
> w wierszu.
Mam nadzieję że udało mi się to wyjaśnić powyżej.

> W każdym bądź razie ja bym szedł w kierunku takim, że drzewo zapisuję
> w postaci chromosomu jako zbiór par (P1,I1), (P2,I2), a na końcu liście
> K1, K2, ... Krzyżowanie i mutację bym zdefiniował jako wymianę i przesuwanie
> w ramach chromosomu cegiełek (par) (P,I) z tym, że bym uważał na to, by
> razem z wymianą między chromosomami reguł na ostatnim poziomie
> wymieniać też liście (dał bym zasadę 'liście należą do ostatniej reguły').
> Potem bym się zastanowił nad mutacjami związanymi z modyfikacją
> samych P i K. W przypadku P mamy w przybliżeniu liczby rzeczywiste, w
> przypadku
> K mamy jakiś zbiór klas, czyli liczby całkowite. Więc zadanie jest o tyle
> 'niebanalne', że mamy do czynienia po pierwsze z drzewem, po drugie
> mamy niejednorodne geny - inaczej trzeba postępować z progami, inaczej
> z liściami(klasami) - inne operatory mutacji itp.
No i rozmiar przestrzeni rozwiązań decyduje o niebanalności. Załóżmy
że
wybieramy jako regułę atomową tą najbardziej zaawansowaną z trzech
jakie przestawiłem na początku. Więc mamy około 80mln reguł
atomowych.
Załóżmy że drzewo ma mieć 10 węzłów wewnętrznych + 11 liści, problem
niech
ma 6 klas, a dane to 2mln rekordów w tabeli. Więc mamy około 100
cyfrową
liczbę rozwiązań.

Poza tym w algorytmie zachłannym (dzięki sztuczce z sumami
częściowymi)
można dość szybko generować jedno (albo nawet dwu) węzłowe optymalne
poddrzewa. Następnie w algorytmie zachłannym do rozwiązania włącza się
to optymalne poddrzewo, które najbardziej maksymalizuje rozwiązanie.
Takiej sztuczki w algorytmie genetycznym chyba nie da się zrobić,
przynajmniej
ja nie wiem jak.

> W każdym bądź razie, najpierw bym mutacje całkowicie porzucił i skupił
> się na krzyżowaniu, z generowaniem dużej populacji początkowej.
> Powinieneś dzięki temu uzyskać taki efekt, gdzie AG będzie budował
> ciągi decyzyjne i kombinował zarówno z wartościami progów, jak i z
> kolejnością decyzji (które podejmować wpierw), oraz ze znalezieniem
> najistotniejszych dla klasyfikacji kolumn - czyli będzie badał 'co jest
> sensowne i ważne z punktu widzenia F'.
>
> Jak będzie ta podstawa, to widzę mnóstwo możliwości dalszych
> modyfikacji operatorów - w zależności od oceny ich sensowności.
> Może warto wymieniać progi między regułami - będzie to miało
> sens, jeśli funkcja F ma skłonności ku takim równościom
> F((A, B ..), K) = F( (B, A...), K) - a być może jest to w ogóle
> bez sensu, bo A i B (różne kolumny) są zupełnie różnych typów.

Znaczenie niektórych kolumn jest bardzo podobne a innych zupełnie
różne. Fajnie by było, jakby algorytm genetyczny sam odkrył reguły
podobieństwa pomiędzy kolumnami i sam swoją pracę tak
sparametryzował,
aby szybciej podać lepsze rozwiązanie ;-) Może jeden algorytm
genetyczny
by dobierał parametry dla drugiego algorytmu genetycznego ;-)

> Tego nie wiem. Na razie zakładam, że kolumny są raczej różnych
> typów, wartości nie można między nimi wymieniać.
Wartości każdej kolumny należą do małego podzbioru liczb całkowitych.
Małego, czyli o liczności od 2 do około 100 elementów.

Pozdrawiam serdecznie