no i co z tymi algorytmami genetycznymi?
Mariusz Marszałkowski
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
Filip Sielimowicz
U�ytkownik "Mariusz Marsza�kowski" <mmar...@gmail.com> napisa� w wiadomo�ci
news:65951300-fad8-4492...@g23g2000vbr.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 ;)))
Mariusz Marszałkowski
wrote:
> Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
> funkcja oceny) - to masz wynik, jaki masz ;)))
Zaproponuj lepszy AG.
Pozdrawiam
Filip Sielimowicz
On 22 Paďż˝, 11:39, "Filip Sielimowicz" <sielim_tnij...@to.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 ?
Filip Sielimowicz
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.
Mariusz Marszałkowski
wrote:
>
> > Zastosowałeś naiwny AG (naiwne kodowanie i naiwna
> > funkcja oceny) - to masz wynik, jaki masz ;)))
>
> 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
Filip Sielimowicz
>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.
Mariusz Marszałkowski
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
Filip Sielimowicz
>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 ;)
Mariusz Marszałkowski
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
Filip Sielimowicz
On 23 Paďż˝, 13:05, "Filip Sielimowicz" <sielim_tnij...@to.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'.
>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 ?
>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.
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.
>> 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.
>> 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'.
>> 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.
Ok.
>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 ? ;)
>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�.
>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�.
Filip Sielimowicz
Co� ciekawego uda�o si� wyprodukowa� ?
Mariusz Marszałkowski
wrote:
> I jak tam eksperymenta ?
Trochę chorowałem i nie zdołałem nic konkretnego zrobić przez
ostatnie dni. Ale w przeciągu 10 dni opiszę kolejne eksperymenty,
pomysły i rezultaty... bądź ich brak ;-)
Pozdrawiam serdecznie :)
Mariusz Marszałkowski
wrote:
> Użytkownik "Mariusz Marszałkowski" <mmars...@gmail.com> napisał w wiadomościnews:8056130c-9c4f-4b4e...@p9g2000vbl.googlegroups.com...
> On 23 Paź, 13:05, "Filip Sielimowicz" <sielim_tnij...@to.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 :)