On 26 Paź, 12:23, "Filip Sielimowicz" <s...@t...tez.wp.pl>
wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
wiadomościnews:8056130c-9c4f-4b4e-bca3-b40d93a72ae6@
p9g2000vbl.googlegroups.com...
> On 23 Paź, 13:05, "Filip Sielimowicz" <s...@t...tez.wp.pl>
> wrote:
>
> >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.
>
> mechanizmy to trochę za dużo powiedziane. po prostu duplikacja genów
> i produkcja białek, które się rozchodzą w komórce i albo coś zmieniają
> (na gorsze lub lepsze) albo są neutralne. Dopiero uszkodzenie/usunięcie
> wszystkich genów (np. spotkanie się genów recesywnych) powoduje, że
> coś co było u rodzica, 'znika'.
Nie mniej jednak bardzo interesujące, interesujące ponieważ wydaje się
że
błądzenie losowe nawet na taką skalę jaką jest cała planeta i 4
miliardy
lat to zdecydowanie za mało do stworzenia choćby takiego narządu jakim
jest oko.


> >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:
>
> Ok, widzę, że sporo już się namęczyłeś z tematem.
> I nie było żadnych ciekawych efektów ? badałeś zmiany w funkcji
> przystosowania
> (wykresy), tempo jej wzrostu ?
Właściwie to namęczyłem się duuużo więcej niż zdołałem opisać
w poprzednim poście. Właściwie od jakiś 10 lat od czasu do czasu
próbuję różne zadania rozwiązać przy pomocy algorytmu genetycznego.
Najwięcej eksperymentów (około 35 różnych programów) przeprowadziłem
na kostce rubika, algorytm (bardziej lub mniej podobny do algorytmu
genetycznego) miał za zadanie stworzyć program do układania
kostki rubika w małej ilości ruchów.

Czy były efekty? Cóż, takich o których warto wspominać nie było :)
Warto natomiast wspomnieć, że na wielu różnych zadaniach obserwowałem
podobną skuteczność trzech algorytmów, albo trzech grup algorytmów.
1) Najgorzej wypadała grupa algorytmów błądzenia losowego.
2) Niewiele lepiej wypadały różne odmiany algorytmu genetycznego
bazującego na krzyżowaniu. Z reguły im więcej "sprytnej" mutacji i
im mniej krzyżowania tym algorytm genetyczny miał większą
przewagę nad błądzeniem losowym.
3) Trzecia grupa algorytmów to algorytmy które moim zdaniem niczym
istotnym nie różnią się od algorytmu symulowanego wyżarzania.
Ilość
osobników w tych algorytmach jest ograniczona do jednego.
Krzyżowania
nie ma w ogóle, występuje tylko "sprytna" mutacja. Mutacja, a
więc
ten istotny krok z symulowanego wyżarzania "wylosuj nowe
rozwiązanie w
pobliżu starego". Jeśli nowe rozwiązanie jest gorzej przystosowane
do
starego, to z pewnym prawdopodobieństwem wróć do starego. Właśnie
te odmiany symulowanego wyżarzania za każdym razem biły na głowę
błądzenie losowe i algorytmy z krzyżowaniem.
4) Można wymienić jeszcze czwartą grupę algorytmów: jeśli dało się
zbudować
jakiś dobry algorytm zachłanny, albo dało się zastosować jakaś
sztuczkę
jak np. w ostatnim problemie z agregacją sum częściowych, to
oczywiście
algorytm zachłanny dawał jeszcze lepsze wyniki niż symulowane
wyżarzanie.
Ale algorytmy zachłanne też nie były pozbawione wad, np. mój
ostatni algorytm
zachłanny buduje ogromne drzewo decyzyjne (zamiast małego), co
często
kończy się dużo gorszym uogólnianiem na zbiorze testowym.

Powstaje pytanie dlaczego krzyżowanie dawało takie mizerne rezultaty?
Odpowiedzą
na to pytanie chyba jest inne pytanie: dlaczego z dwóch dobrych
osobników miałby
powstać z dużym prawdopodobieństwem trzeci lepszy? Nie dostrzegam w
ogólnym
przypadku żadnego powodu z którego poprzez skrzyżowanie zakodowanych
cech
mogłyby powstać lepsze cechy, dające większą wartość funkcji
przystosowania.


> Oki ... Pojęcia bitu bym tu raczej jednak nie mieszał, jeśli nie ma
> wyraźnego związku między problemem a bitową reprezentacją danych
> to bym unikał np. operatorów genetycznych, które coś tam mieszają w
> bitach liczb.
Na razie nie próbowałem ( w ostatnim problemie nie próbowałem )
operacji
na bitach. Niemniej jednak wydaje się, że operacje na bezpośredniej
reprezentacji
bitowej posiadają pewną zaletę. Załóżmy że osobnik składa się z
ciągu N bitów. Możemy stworzyć tablicę T o rozmiarze NxN par liczb
całkowitych. Następnie mutując bit i-ty, w wierszu i-tym tablicy T
agregujemy wpływ mutacji i-tego bitu na funkcje przystosowania, w
zależności od nie/ustawionych pozostałych bitów. W ten sposób,
po wielu mutacjach, zbudujemy statystykę (to chyba coś podobnego
do klasyfikatora bayesowskiego), jakie bity najbardziej lubią być
ustawione
w zależności od ustawienia pozostałych bitów. Jeśli osobnik składa
się z małej ilości bitów, a wywołanie funkcji przystosowania jest
bardzo
kosztowne, można pokusić się o tablicę trójwymiarową NxNxN, wtedy
zbudujemy statystykę jednego bitu, od pozostałych par bitów.
Jeśli nie napisałem zrozumiale, a zainteresowało Cię to, to pisz,
podam
przykład :)

> >> 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
>
> Oki, to było dla mnie jasne już wcześniej, pytałem o słowo 'kombinacji',
> sugerowało to, że Twój algorytm w ramach krzyżowania/mutacji skupia się
> głównie na przestawianiu liści miejscami, co w oderwaniu od reguł
> wydaje mi się raczej słabym pomysłem. Mało efektywnym.
>
> >> 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.
>
> No, ja bym od tego chyba zaczął ;) Jak mamy do czynienia z drzewami
> to naturalne jest skonstruowanie takich operatorów, które mają świadomość
> tych drzew i np. przenoszą węzły, przepinają gałęzie itp.
Przymierzam się do tego pomysłu i zastanawiam jak skutecznie go
zaimplementować. Ostatnio drzewo decyzyjne, zastąpiłem grafem
decyzyjnym, bo
w sumie dlaczego jeden węzeł ma mieć tylko jednego rodzica? Drzewo
jest
jednocześnie trudniejsze w implementacji (trzeba dbać właśnie to aby
jeden
węzeł miał dokładnie jednego rodzica) i mniej wydajne. Graf realizuję
w taki
sposób:

#define IT (4)

int classify( const int param[] ) {
int i,next=0,clas;
for(it=0;it<IT;it++)
switch( next ) {
case 0: if( param[i01] operacja param[i02] porównanie stała0 ) next =
x01; else next = x02; clas = c0; break;
case 1: if( param[i11] operacja param[i12] porównanie stała1 ) next =
x11; else next = x12; clas = c1; break;
case 2: if( param[i21] operacja param[i22] porównanie stała2 ) next =
x21; else next = x22; clas = c2; break;
......................
case N: if( param[iN1] operacja param[iN2] porównanie stałaN ) next =
xN1; else next = xN2; clas = cN; break;
}
return clas;
}

"operacja" to: dodawanie, mnożenie lub odejmowanie
"porównanie" to: równy, różny, mniejszy lub równy, większy lub równy

Algorytm budujący taki graf ma za zadanie znaleźć wszystkie parametry:
- operacja
- porównanie
- zmienne: i, x, stała, c

Używam algorytmu bazującego na symulowanym wyżarzaniu, jeśli ktoś
jest zainteresowany, mogę udostępnić źródła tego programu i
przykładowe
dane. Mogę także udostępnić źródła do budowania drzewa decyzyjnego
dla tych samych danych, jeśli ktoś jest zainteresowany, to proszę o
info.

> >> 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
> >...
> >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.
>
> Oki, nie do końca chwytam, ale po prostu nie bardzo mam
> czas. Pozostanę na 'wyższym poziomie abstrakcji'.
Oki, to w sumie były szczegóły, możemy je pominąć :)


> >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ń.
>
> Oki ;) Przestrzeń duża, ale ... To typowe ;) jaka jest przestrzeń rozwiązań
> dla problemu komiwojażera ze 100 miastami ? A 1000 ? ;)
Coś pomiędzy silnia 100 a silna 1000 ;-) Ciekawy problem, chętnie bym
zobaczył o
ile gorszy wynik podaje algorytm genetyczny od algorytmu dokładnego
dla problemu
komiwojażera.

> >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.
>
> Z braku czasu nie wnikam ... Może jeszcze podejdę do tematu.
> Wydaje mi się, że sam AG nie stawia problemu, to tylko kwestia
> skomplikowania chromosomu, operatorów i funkcji oceny,
> wbudowania w problem tej samej wiedzy, co w innych rozwiązaniach
> analitycznych, a AG pozostawienie tylko kwesti związanych
> z przeszukiwaniem tego, czego już nie umiemy uprościć.

Dokładnie o to chodzi. Zaimplementować wszystko co się da,
zaimplementować całą znaną wiedzę, a tam gdzie nic nie wiadomo,
to zastosować AG. Niestety to może być bardzo trudne, np.
cały czas nie wiem jak przyspieszyć algorytm genetyczny dzięki
owym sumom częściowym.

> >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 ;-)
>
> Wystarczy jeden. Rozbudowujemy chromosom o dodatkowe
> (zresztą robiłes sam jakieś kombinacje z głosowaniami itp)
> pola, w których np. zapisujemy informacje o 'kolumnach podobnych'
> (np dodajemy miejsce na 6 par liczb) i wrzucamy to info jako
> parametry wpływające na działanie operatorów genetycznych
> (decydujacych np. które węzły z którymi wymieniać, czy kopiować
> reguły). Nazwałbym je 'genami regulacyjnymi'. Geny regulacyjne
> już krzyzujesz i mutujesz standardowo, prosto (wymiana par liczb
> między osobnikami). Można popróbować.
Dobra idea, efekt taki sam jak dwóch algorytmów genetycznych, a
reprezentacja znacznie prostsza. Zapamiętam to sobie :)

Pozdrawiam serdecznie
Sorry że tak późno odpisuję, ale trochę chorowałem i nie miałem
czasu, a nie chciałem odpowiadać bez zastanowienia :)