Nie zajmowałem się nigdy algorytmami genetycznymi. Czy można za ich pomocą
wyszukać minimum (globalne) funkcji trzech i więcej zmiennych? Jeśli chodzi
o szukanie minimum to z metod iteracyjnych jest metoda najszybszego spadku,
ale nie bardzo wiem jaką wartość podstawić za parametr (alfa lub lambda)
długości kroku.
Z tego co kojarzę to wygląda to tak, że w przestrzeni R^N wybieramy losowo
np. 20 osobników (od czego zależy ich liczba?) każdy ma kilak chromosomów
czyli rejestrów binarnych. Krzyżowanie jest binarne i wygląda tak że losowo
wybieramy pozycję podziału bitów i wymieniamy fragmenty np.
mając
01001 | 100
11100| 101
na
01001 | 101
11100 | 100
Czy też krzyżowanie jest arytmetyczne xk = alfa *xt + (1-alfa)xm gdzie alfa
z przedziału 0..1
Mutacja to losowa zmiana bitu - z jaką powinna być częstotliwością? Czy
zmiana bitu wyższego powinna przytrafiać się rzadziej niż niższego? Czy też
mutacja to przesunięcie o wektor w inne miejsce przestrzeni z
prawdopodobieństwem odwrotnie proporcjonalnym do długości przesunięcia ?
Czy łączymy w pary poczynając od najlepiej przystosowanego pierwszy z
drugim, trzeci z czwartym czy tez możemy za każdym razem wybierać losowo
rodziców do utworzenia potomka, czy pary potomków?
Jak nie utknąć w minimum lokalnym? Gdy będziemy mutować to bardzo niewielkie
prawdopodobieństwo jest że wartość funkcji mutanta będzie lepsza niż przed
mutacją?

Pozdrawiam
Andrzej

do góry

On 20 Lip, 13:02, "Borneq" <b...@a...hidden.pl> wrote:
> Nie zajmowałem się nigdy algorytmami genetycznymi. Czy można za ich pomocą
> wyszukać minimum (globalne) funkcji trzech i więcej zmiennych?

Można próbować, ale naiwny algorytm genetyczny z reguły nie daje
lepszych wyników niż np. błądzenie losowe. Aby algorytm genetyczny
zadziałał, trzeba użyć takiego kodowania które zwiększy
prawdopodobieństwo
że dobrze przystosowani rodzice będą mili dobrze przystosowane
potomstwo. Naiwne kodowanie da taki efekt, że skrzyżowanie
dwóch dobrych rozwiązań daje fatalne potomstwo :)

Jak zrobić dobre kodowanie? W ogólnym przypadku nie wiadomo, bywa
to tak trudne, że rezygnuje się z algorytmów genetycznych. Algorytmy
genetyczne z powodzeniem można zastosować jedynie tam gdzie
nie ma nadziei na jakikolwiek inni algorytm.

> Jeśli chodzi
> o szukanie minimum to z metod  iteracyjnych jest metoda najszybszego spadku,
> ale nie bardzo wiem jaką wartość podstawić za parametr (alfa lub lambda)
> długości kroku.
Algorytm genetyczny można z powodzeniem zastosować do dobrania punktu
początkowego i długości kroku.

> Z tego co kojarzę to wygląda to tak, że w przestrzeni R^N wybieramy losowo
Tak, ale bez specjalnych zabiegów daje to nędzne efekty.

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:3dc4027b-5344-4d66-8935-6c1248fc4049@l14g2000yq
l.googlegroups.com...
> Można próbować, ale naiwny algorytm genetyczny z reguły nie daje
> lepszych wyników niż np. błądzenie losowe. Aby algorytm genetyczny


Próbowałem zrobić pierwszą krzyżówkę, ale wszytstkie wyniki dążą do wyniku
który osiągnął któryś i skrzyżował z inymi starsze bity. Daleko od minium
(moja testowa funkcja ma tylko jedno globalna).
Algorytm daje fatalne rezultaty

> Algorytm genetyczny można z powodzeniem zastosować do dobrania punktu
> początkowego i długości kroku.
A w jaki sposób można to zrobić? Jeżeli funkcja celu za każdym razem
uruchamiała by procedurę iteracji najszybszego spadku dla punktu
początkowego i alfa, to by było długotrwałe. Czy można jakoś wyznaczyć
współczynnik alfa w tej metodzie nie korzystając z programowania
genetycznego?

Pozdrawiam

do góry

On 20 Lip, 19:04, "Borneq" <b...@a...hidden.pl> wrote:
> Algorytm daje fatalne rezultaty
Pokombinuj jeszcze, może masz błędy jakieś? Naiwny algorytm genetyczny
ogólnie słabo, ale jak prosta funkcja to z tego powodu że dzisiejsze
komputery
są mocne powinien sobie poradzić.

> A w jaki sposób można to zrobić? Jeżeli funkcja celu za każdym razem
> uruchamiała by procedurę iteracji najszybszego spadku dla punktu
> początkowego i alfa, to by było długotrwałe.
Długotrwałe, ale szybsze niż sam algorytm genetyczny i pewniejsze niż
uruchomienie metody największego spadku z jednego punktu startowego.

> Czy można jakoś wyznaczyć
> współczynnik alfa w tej metodzie nie korzystając z programowania
> genetycznego?
Można ręcznie dobrać. Uruchamiasz procedurę, podglądasz czy krok
jest za długi czy za krótki, zmieniasz i znów uruchamiasz. Tak samo
ręcznie można z kilku punktów startowych uruchomić.

Można też zastosować minimalizację kierunkową, wtedy długość
kroku w każdej iteracji jest dobierana niezależnie.

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:7997649b-bd8b-4f4c-b379-9684c2a4a441@d8g2000yqf
.googlegroups.com...
> Pokombinuj jeszcze, może masz błędy jakieś? Naiwny algorytm genetyczny
> ogólnie słabo, ale jak prosta funkcja to z tego powodu że dzisiejsze
> komputery
> są mocne powinien sobie poradzić.

Może dlatego że nie mam mutacji. Próbowałem sposobu binarnego i tworzenie
nowego na podstawie alfa(jeden rodzic)+(1-alfa) drugi rodzic (alfa należy od
0 do 1). Gdy wszystkie zgormadzą się w pobliżu jednego punktu to już
wszystkie nowe tam będą i nie szukają nowego punktu.

do góry

On 20 Lip, 22:22, "Borneq" <b...@a...hidden.pl> wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
wiadomościnews:7997649b-bd8b-4f4c-b379-9684c2a4a441@
d8g2000yqf.googlegroups.com...
>
> > Pokombinuj jeszcze, może masz błędy jakieś? Naiwny algorytm genetyczny
> > ogólnie słabo, ale jak prosta funkcja to z tego powodu że dzisiejsze
> > komputery
> > są mocne powinien sobie poradzić.
>
> Może dlatego że nie mam mutacji. Próbowałem sposobu binarnego i tworzenie
> nowego na podstawie alfa(jeden rodzic)+(1-alfa) drugi rodzic (alfa należy od
> 0 do 1). Gdy wszystkie zgormadzą się w pobliżu jednego punktu to już
> wszystkie nowe tam będą i nie szukają nowego punktu.

Może zastosuj symulowane wychładzanie? To taki algorytm
genetyczny w którym jest tylko jeden osobnik i tylko mutacja :)
Dla niektórych funkcji sprawuje się bardzo dobrze.

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:933d3ab8-6a72-4a90-800a-26e59db7f62f@s9g2000yqd
.googlegroups.com...
> Może zastosuj symulowane wychładzanie? To taki algorytm
> genetyczny w którym jest tylko jeden osobnik i tylko mutacja :)
> Dla niektórych funkcji sprawuje się bardzo dobrze.


Chyba całkowicie zrezygnuję z algorytmów genetycznych i problem może da się
rozwiązać przy pomocy iterowanych metod znajdowania ekstremów jak metody
zmiennej metryki. Przyglądam się metodzie BFGS i zastanawiam nad znajdowanie
długości kroku alfa, musi spełnić warunek Wolfa.
http://en.wikipedia.org/wiki/Wolfe_conditions
Nie bardzo wiem jak z tych warunków obliczyć Alfa, przy czym warunek IIa nie
wygląda jak uściślenie II a jak zupełnie przeciwny.
Ale to już temat na grupę pl.sci.matematyka a na tej moderowanej grupie nie
przybył jak dotąd żaden post.

Pozdrawiam

do góry

On 20 Lip, 23:33, "Borneq" <b...@a...hidden.pl> wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
wiadomościnews:933d3ab8-6a72-4a90-800a-26e59db7f62f@
s9g2000yqd.googlegroups.com...
>
> > Może  zastosuj symulowane wychładzanie? To taki algorytm
> > genetyczny w którym jest tylko jeden osobnik i tylko mutacja :)
> > Dla niektórych funkcji sprawuje się bardzo dobrze.
>
> Chyba całkowicie zrezygnuję z algorytmów genetycznych i problem może da się
> rozwiązać przy pomocy iterowanych metod znajdowania ekstremów jak metody
> zmiennej metryki.
Jakie funkcje chcesz optymalizować?

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:219b57eb-b7a8-4c00-a1a2-de05af9ea357@g35g2000yq
a.googlegroups.com...
> Jakie funkcje chcesz optymalizować?
> Pozdrawiam

Mam osobny algorytm zarządzania blokami dużymi i małymi, małe poniżej pewnej
wielkości - której szukam, poza tym jeszcze z dwa parametry, które chciałbym
ustawić optymalnie.

do góry

On 21 Lip, 01:00, "Borneq" <b...@a...hidden.pl> wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
wiadomościnews:219b57eb-b7a8-4c00-a1a2-de05af9ea357@
g35g2000yqa.googlegroups.com...
>
> > Jakie funkcje chcesz optymalizować?
> > Pozdrawiam
>
> Mam osobny algorytm zarządzania blokami dużymi i małymi, małe poniżej pewnej
> wielkości - której szukam, poza tym jeszcze z dwa parametry, które chciałbym
> ustawić optymalnie.

Dwa to bardzo mało, może po prostu w excelu policz?
Pozdrawiam

do góry