Powitać

Jest dana macierz M, co ma R wierszy i C kolumn.
Kolumny mają średnio V różnych wartości.
Jest dana funkcja F odwzorowująca iloczyn kartezjański
wierszy i klas RxK w zbiór liczb całkowitych.

Szukane: drzewo klasyfikujące, binarne, składające się z N węzłów
decyzyjnych (i N+1 liści), które przypisze wierszom takie klasy,
alby
suma F po wszystkich wierszach była bliska maksymalnej.

Upraszczając, warunki w węzłach drzewa ograniczmy do M_ij <= C_j,
gdzie C_j jest jedną z wartości kolumny j.
Kolejne uproszczenie, niech drzewo składa się tylko z jednego
węzła N=1 decyzyjnego i dwóch liści.

Podejście bardzo naiwne:
1) Weź wszystkie warunki, których jest VxC
2) Każdy warunek sprawdź na wszystkich rekordach R, czyli
VxCxR operacji
3) Uwzględnij wszystkie kombinacje liści: K^(N+1)=KxK, razem
VxCxRxKxK operacji

Podejście mniej naiwne:
1) Zbuduj sumy częściowe F dla każdej wartości w kolumnie i dla
każdego sposobu przypisania jej do klasy: CxRxK operacji
2) Posortuj sumy częsciowe po wartościach kolumny, mamy
Cx(RxK+V*LG(V)) operacji
3) Wybierz maksymalną sumę sum częściowych dla kombinacji
klas (liści), mamy Cx(RxK+VxLg(V)+VxK) operacji

Porównujemy jeden wzór z drugim:
Cx(RxK+VxLg(V)+VxK)
----------------------------------
VxCxRxKxK

Co w przybliżeniu równa się:
R + V*Lg(V) + V
------------------------
VxRxK

1 Lg(V) 1
----- + ---------- + ---------
VxK RxK RxK

Dla dużej ilości rekordów można zaokrąglić do
1
-----
VxK

Co przykładowo przy 5 klasach i 50 wartościach
w kolumnie daje około: 1/50/5, czyli jedną dwieście
pięćdziesiątą czasu wykonania "algorytmu bardzo
naiwnego". Jeśli drzewo ma więcej węzłów niż
jeden, stosunek obu czasów wykonania maleje
wykładniczo.

Jak działa algorytm genetyczny na dwóch
powyżej opisanych algorytmów? Otóż działa
tak jak pierwszy, czyli "bardzo naiwny". Algorytm
genetyczny losuje (poniekąd to nie jest losowanie,
ale inteligentny dobór) kombinacje reguł dla
drzewa decyzyjnego a następnie testuje drzewo
na wszystkich rekordach.

Uważam że porównanie czasów obu algorytmów
stawia algorytm genetyczny w bardzo niekorzystnej
sytuacji. Testy które wykonałem zdają się to
potwierdzać. W zależności od danych, dobrym
algorytmem wyczerpującego przeszukania da
się zbudować optymalne drzewo decyzyjne
składające się 2-4 węzłowe. Algorytmem
genetycznym też można, ale znalezienie równie
dobrego rozwiązania przez algorytm genetyczny w
tym samym czasie, jest znacznie mniej prawdopodobne,
właśnie rzędu (1/250)^2 - (1/250)^4.

Pozdrawiam serdecznie

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:65951300-fad8-4492-9ecb-724eb64dd4a7@g23g2000vb
r.googlegroups.com...

>Jak działa algorytm genetyczny na dwóch
>powyżej opisanych algorytmów? Otóż działa
>tak jak pierwszy, czyli "bardzo naiwny". Algorytm
>genetyczny losuje (poniekąd to nie jest losowanie,
>ale inteligentny dobór) kombinacje reguł dla
>drzewa decyzyjnego a następnie testuje drzewo
>na wszystkich rekordach.

Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
funkcja oceny) - to masz wynik, jaki masz ;)))

do góry

On 22 Paź, 11:39, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:

> Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
> funkcja oceny) - to masz wynik, jaki masz ;)))

Zaproponuj lepszy AG.
Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:d824d3b8-0e3e-40ab-a2f9-aaba31b6be79@l31g2000vb
p.googlegroups.com...
On 22 Paź, 11:39, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:

> Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
> funkcja oceny) - to masz wynik, jaki masz ;)))

Wiesz - może ja czegoś nie rozumiem - ale moim zdaniem
nie opisałeś w jaki sposób zbudowałeś chromosom,
jak wyglądało krzyżowanie i jak funkcja oceny.
Masz liniowy chromosom, w który wrzucasz na sztywno
wszystkie współczynniki z węzłów drzewa decyzyjnego ?

Istotą AG jest składanie rozwiązania z kombinacji rozwiązań
cząstkowych. Czy u Ciebie wymiana fragmentów chromosomów
zawierajacych rozwiązania 'dobre' daje prawdopodobieństwo
uzyskania rozwiązania 'lepszego' wyraźnie większe niż krzyżowanie
dowolnych innych chromosomów, czy takie samo ?

Przy opisie dwóch rozwiązań dokonałeś jakiejś obserwacji
dot. problemu związanej z liczeniem sum częściowych - i tę
wiedzę zaszyłeś w drugim algorytmie. Czy tę obserwację
zastosowałes w AG ? Może jakaś wielokryterialna funkcja
oceny by się przydała, albo wybierająca max z jakichś
funkcji cząstkowych ?

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:65951300-fad8-4492-9ecb-724eb64dd4a7@g23g2000vb
r.googlegroups.com...
Powitać

>Jest dana macierz M, co ma R wierszy i C kolumn.
>Kolumny mają średnio V różnych wartości.
>Jest dana funkcja F odwzorowująca iloczyn kartezjański
>wierszy i klas RxK w zbiór liczb całkowitych.

Prawdę mówiąc - nie rozumiem. jaki jest związek między
'wartością kolumny' a funkcją F ? Jaki wpływ 'wartosc kolumny'
ma na funkcję F ? Z powyższego wynika, jak dla mnie, że żaden.

do góry

On 22 Paź, 12:39, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:
>
> > Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
> > funkcja oceny) - to masz wynik, jaki masz ;)))
>
> Wiesz - może ja czegoś nie rozumiem - ale moim zdaniem
> nie opisałeś w jaki sposób zbudowałeś chromosom,
> jak wyglądało krzyżowanie i jak funkcja oceny.
> Masz liniowy chromosom, w który wrzucasz na sztywno
> wszystkie współczynniki z węzłów drzewa decyzyjnego ?

Dobrze się domyślasz, skoro nie opisałem, to użyłem
naiwnego kodowana i naiwnego AG. Nie mam pojęcia
co można zrobić aby ulepszyć AG i czy cokolwiek
można ulepszyć.

> Istotą AG jest składanie rozwiązania z kombinacji rozwiązań
> cząstkowych. Czy u Ciebie wymiana fragmentów chromosomów
> zawierajacych rozwiązania 'dobre' daje prawdopodobieństwo
> uzyskania rozwiązania 'lepszego' wyraźnie większe niż krzyżowanie
> dowolnych innych chromosomów, czy takie samo ?
Nie rozumiem dlaczego w takim problemie jakiekolwiek krzyżowanie
dobrych osobników ma dawać większe prawdopodobieństwo powstania
lepszego osobnika. Jakie to by musiało być krzyżowanie?

> Przy opisie dwóch rozwiązań dokonałeś jakiejś obserwacji
> dot. problemu związanej z liczeniem sum częściowych - i tę
> wiedzę zaszyłeś w drugim algorytmie. Czy tę obserwację
> zastosowałes w AG ?
No właśnie nie, polegałem na "sile algorytmu genetycznego", w
ewolucji poniekąd sobie poradziły ;-)

> Może jakaś wielokryterialna funkcja
> oceny by się przydała, albo wybierająca max z jakichś
> funkcji cząstkowych ?
Może, ale co to by mogła być za funkcja?

> Prawdę mówiąc - nie rozumiem. jaki jest związek między
> 'wartością kolumny' a funkcją F ? Jaki wpływ 'wartosc kolumny'
> ma na funkcję F ? Z powyższego wynika, jak dla mnie, że żaden.
Coś w rodzaju:
max (\sum_{i=1}^{i=N} F( i , T( i ) )

N - ilość rekordów
i = 1..N - to numer rekordu
T( i ) szukany klasyfikator, przypisująca numer klasy 1..G rekordowi i
F( i , T(i) ) to dowolna funkcja przypisująca dowolne wartości
rekordowi i klasie - inaczej: funkcja F ocenia jakość klasyfikatora T
( i ).

Trzeba znaleźć takie T żeby suma F była maksymalna.
Ograniczenia nałożone na T są mniej/więcej takie:
- ma być drzewem klasyfikującym
- ma zawierać mało węzłów względem ilości rekordów, np. N*10^-5 -
N*10^-6

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:7aef3e64-3e94-42af-82e4-784a813e6f34@p20g2000vb
l.googlegroups.com...

>Nie rozumiem dlaczego w takim problemie jakiekolwiek krzyżowanie
>dobrych osobników ma dawać większe prawdopodobieństwo powstania
>lepszego osobnika. Jakie to by musiało być krzyżowanie?

No i właśnie dlatego bezpośrednie zastosowanie AG w tym przypadku jest do d
... ;)

> No właśnie nie, polegałem na "sile algorytmu genetycznego", w
> ewolucji poniekąd sobie poradziły ;-)
Ewolucja rozwiązuje wiele, wiele mniej lub bardziej powiązanych
problemów jednocześnie i kombinuje z łączeniem tych rozwiązań
w całość.
U Ciebie, póki co - problem jest jeden - funkcja F - o której
nie wiemy nic ... Czy jest monotoniczna, czy ma jakieś minima-maksima itp
(w zależności od rekordu i w zależności od T(i) ). Np. proste pytanie:
Czy jeśli F ([x,y,z], k) ) daje wysoki wynik, to jest szansa, że
F ([x,y,A], k) ) również da wysoki wynik ?

>Coś w rodzaju:
>max (\sum_{i=1}^{i=N} F( i , T( i ) )
>
>N - ilość rekordów
>i = 1..N - to numer rekordu
>T( i ) szukany klasyfikator, przypisująca numer klasy 1..G rekordowi i
>F( i , T(i) ) to dowolna funkcja przypisująca dowolne wartości
>rekordowi i klasie - inaczej: funkcja F ocenia jakość klasyfikatora T
>( i ).
>
>Trzeba znaleźć takie T żeby suma F była maksymalna.
>Ograniczenia nałożone na T są mniej/więcej takie:
> - ma być drzewem klasyfikującym
> - ma zawierać mało węzłów względem ilości rekordów, np. N*10^-5 -
>N*10^-6

Oki, to sprawa jest dużo jaśniejsza.
Natomiast wydaje mi się, że kluczem do dobrego algorytmu AG jest tu
jednak przyjrzenie się funkcji F i próba określenia jakichś jej własności.
Jak znajdę w domu czas, to jeszcze nad tym poślęczę ... Brakuje mi tu
jakiejś podpowiedzi dot. tego, czy klasy są podobne - tzn, czy
są klasy, które dają podobne wyniki funkcji F dla podobnych rekordów.
Wtedy krzyżowanie parametrów klasyfikatora będzie miało sens.
Jeśli nie ma takich podobieństw między klasami (z punktu widzenia
funkcji F) to mamy problem kombinatoryczny i trzeba by spróbować
inaczej go podejść.

Pierwsza rzecz, która mi się narzuca, to:
- zostawić krzyżowanie, tak jak miałeś, ale funkcję oceny zdefiniować
nie jako pełne sumowanie po wszystkich rekordach (tak zdaje się
zrobiłeś - testujesz klasyfikator po wszystkim), ale wybierasz za
każdym razem jakiś losowy zestaw rekordów ze zbioru, np. 10-100
(losową próbkę, im więcej kolumn, tym większą), dla każdego
z nich liczysz F i funkcją oceny jest albo max z tych wyników
cząstkowych, albo suma. Pokombinowałbym z maxem.

Nie upierałbym się też przy znlezieniu absolutnie idealnego T, ale
zadowoliłbym się 'prawie idalnym' - badaj wykres funkcji
przystosowania najlepszego osobnika w zależności od iteracji.

do góry

On 22 Paź, 16:53, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:
> > No właśnie nie, polegałem na "sile algorytmu genetycznego", w
> > ewolucji poniekąd sobie poradziły ;-)
>
> Ewolucja rozwiązuje wiele, wiele mniej lub bardziej powiązanych
> problemów jednocześnie i kombinuje z łączeniem tych rozwiązań
> w całość.
> U Ciebie, póki co - problem jest jeden - funkcja F - o której
> nie wiemy nic ...
Coś niezwykłego jest w Ewolucji, jeśli naprawdę to ona poradziła
sobie
ze skonstruowaniem oka, mózgu, itd. Wydaje się nieprawdopodobne
aby ewolucja opierała się na czymś tak prostym jak krzyżowanie i
mutacja.

> Czy jest monotoniczna, czy ma jakieś minima-maksima itp
> (w zależności od rekordu i w zależności od T(i) ). Np. proste pytanie:
> Czy jeśli F ([x,y,z], k) ) daje wysoki wynik, to jest szansa, że
> F ([x,y,A], k) ) również da wysoki wynik ?
Właśnie tego wszystkiego o funkcji chcę się dowiedzieć od algorytmu
który zbuduje klasyfikator. Chcę żeby klasyfikator sam wyznaczył
miarę podobieństwa i podobnym rekordom przypisał te same klasy.

> >Coś w rodzaju:
> >max (\sum_{i=1}^{i=N} F( i , T( i ) ))
>
> Oki, to sprawa jest dużo jaśniejsza.
> Natomiast wydaje mi się, że kluczem do dobrego algorytmu AG jest tu
> jednak przyjrzenie się funkcji F i próba określenia jakichś jej własności
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.

> Jak znajdę w domu czas, to jeszcze nad tym poślęczę ... Brakuje mi tu
> jakiejś podpowiedzi dot. tego, czy klasy są podobne - tzn, czy
> są klasy, które dają podobne wyniki funkcji F dla podobnych rekordów.
> Wtedy krzyżowanie parametrów klasyfikatora będzie miało sens.
> Jeśli nie ma takich podobieństw między klasami (z punktu widzenia
> funkcji F) to mamy problem kombinatoryczny i trzeba by spróbować
> inaczej go podejść.
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.

> Pierwsza rzecz, która mi się narzuca, to:
> - zostawić krzyżowanie, tak jak miałeś, ale funkcję oceny zdefiniować
> nie jako pełne sumowanie po wszystkich rekordach (tak zdaje się
> zrobiłeś - testujesz klasyfikator po wszystkim), ale wybierasz za
> każdym razem jakiś losowy zestaw rekordów ze zbioru, np. 10-100
> (losową próbkę, im więcej kolumn, tym większą), dla każdego
> z nich liczysz F i funkcją oceny jest albo max z tych wyników
> cząstkowych, albo suma. Pokombinowałbym z maxem.
Wydaje się ciekawe, na pewno znacznie by przyspieszyło
obliczanie funkcji przystosowania.

> Nie upierałbym się też przy znlezieniu absolutnie idealnego T, ale
> zadowoliłbym się 'prawie idalnym' - badaj wykres funkcji
> przystosowania najlepszego osobnika w zależności od iteracji.

Dla dużej ilości danych nie ma szans na znalezienie optimum, no
chyba że mocno ograniczy się ilość węzłów.

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:1817f1e4-113c-43f2-b936-8fecc6c6991e@p23g2000vb
l.googlegroups.com...

>Coś niezwykłego jest w Ewolucji, jeśli naprawdę to ona poradziła
>sobie
>ze skonstruowaniem oka, mózgu, itd. Wydaje się nieprawdopodobne
>aby ewolucja opierała się na czymś tak prostym jak krzyżowanie i
>mutacja.
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 ;)


>Właśnie tego wszystkiego o funkcji chcę się dowiedzieć od algorytmu
>który zbuduje klasyfikator. Chcę żeby klasyfikator sam wyznaczył
>miarę podobieństwa i podobnym rekordom przypisał te same klasy.
Ok, jasna sprawa.

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

>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 ?


>> każdym razem jakiś losowy zestaw rekordów ze zbioru, np. 10-100
>> (losową próbkę, im więcej kolumn, tym większą), dla każdego
>> z nich liczysz F i funkcją oceny jest albo max z tych wyników
>> cząstkowych, albo suma. Pokombinowałbym z maxem.
>Wydaje się ciekawe, na pewno znacznie by przyspieszyło
>obliczanie funkcji przystosowania.

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

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.

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.
Tego nie wiem. Na razie zakładam, że kolumny są raczej różnych
typów, wartości nie można między nimi wymieniać.

Jak coś niejasne - pytaj ;)

do góry

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

do góry