Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news: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'.

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