🚀 go-pugleaf

On 7 Paź, 15:03, Mateusz Piąty <x...@y.z> wrote:
>         Szukam jakiegoś opracowania po polsku na tem temat w Internecie lub w
> wersji elektronicznej i nie mogę trafić na takie które mnie zadowoli.
>
>         Problem mam taki (niezależny od wariantu):
> Mrówka stoi przed wyborem drogi. Czy parametry alfa i beta sa stałe dla
> wszystkich mrówek, czy dla każdej mrówki należy wyliczyć w momencie wyboru
> wartość losową alfa i beta?
>
>         Może ktoś mi podpowie albo poda linka do jakiegoś opracowania w którym to
> będzie jednoznacznie okreslone. Jeśli ustawię je na sztywno to praktycznie
> po pierwszym cyklu już nic lepszego nie potrafią znaleźć

http://stud.ics.p.lodz.pl/~giaur/mgr/praca%20magisterska.pdf strona 10

Pozdrawiam,
   Wit Jakuczun

Mam to opracowanie ale tam nie ma odpowiedzi na moje pytanie

On 7 Paź, 15:20, Mateusz Piąty <x...@y.z> wrote:
> Mam to opracowanie ale tam nie ma odpowiedzi na moje pytanie

Ja to rozumiem tak, że alfa i beta są wspólne dla wszystkich mrówek.
Kluczowym tutaj jest
wzór 2.1.

Pozdrawiam,
   Wit Jakuczun

Tylko że we zworze są liczone dwie wartości. Jedna jako wartość feromonu do
potęgi alfa - dla każdej mrówki w tym samym węźle będzie to liczone tak
samo i da tę samą wartość. Druga wartość zależna od odwrotności odległości
między miastami do potęgi beta - też dla każej mrówki tak samo liczone. Nie
widzę więc tu "przypadkowości" wyboru drogi bo dla każdej mrówki wychodzi
taka sama wartość po przeliczeniu wzoru.

On 7 Paź, 16:32, Mateusz Piąty <x...@y.z> wrote:
> Tylko że we zworze są liczone dwie wartości. Jedna jako wartość feromonu do
> potęgi alfa - dla każdej mrówki w tym samym węźle będzie to liczone tak
> samo i da tę samą wartość. Druga wartość zależna od odwrotności odległości
> między miastami do potęgi beta - też dla każej mrówki tak samo liczone. Nie
> widzę więc tu "przypadkowości" wyboru drogi bo dla każdej mrówki wychodzi
> taka sama wartość po przeliczeniu wzoru.

Wzór 2.1 służy wyznaczeniu prawdopodobieństwa tego, że dana mrówka
pójdzie do węzła j (będąc w i).
Żeby mrówka gdzieś poszła trzeba dokonać losowania. W tym losowaniu
ukryta jest "przypadkowość",
której poszukujesz.

Pozdrawiam,
   Wit Jakuczun

Dzięki.
Po wyliczeniu wartości wg wzoru mnożę je przez liczbę pseudolosową i to
załatiwa problem. Nie mogę się jednak tego doszukać nawet w pracy Dorigo.
Może to tak oczywiste, że przy mojej niedoskonałej znajomości angielskiego
nie doczytałem czegoś.

On 7 Paź, 16:58, Mateusz Piąty <x...@y.z> wrote:
> Dzięki.
> Po wyliczeniu wartości wg wzoru mnożę je przez liczbę pseudolosową i to
> załatiwa problem.
Po co mnożysz? I jaki problem to załatwia?

Pozdrawiam,
   Wit Jakuczun

Prawdopodobieństwo, że mrówka przejdzie z wierzhołka "i" do wierzhołka "j"
wylicza się wzorem:

    power(Tij,alfa)*power(Nij,beta)
P = -------------------------------------
    Suma(power(Tij,alfa)*power(Nij,beta))

Dla mozliwych do wybrania "j"

W tym wzorze nie ma nic co by różnicowało prawdopodobieństwo wyboru
konkretnego wierzchoła dla różnych mrówek. Dla każdej mrówki P będzie takie
samo. Powoduje to, że wszystkie mrówki wybierają tę samą drogę.

Nie bardzo rozumiem co masz na myśli pisząc "losowanie". Tego elementu
właśnie nie mogę się dopatrzeć. Jedynie w przypadku wariantu ACS i Ant-Q
jest losowanie wartości "Q" które rozwiązuje ten problem.

Witam,

"Mateusz Piąty" <x@y.z> wrote in message 
news:17uzkoerj49cg$.cdb84ramqvld$.dlg@40tude.net...
> Prawdopodobieństwo, że mrówka przejdzie z wierzhołka "i" do wierzhołka "j"
> wylicza się wzorem:
>
>    power(Tij,alfa)*power(Nij,beta)
> P = -------------------------------------
>    Suma(power(Tij,alfa)*power(Nij,beta))
>
> Dla mozliwych do wybrania "j"
>
> W tym wzorze nie ma nic co by różnicowało prawdopodobieństwo wyboru
> konkretnego wierzchoła dla różnych mrówek. Dla każdej mrówki P będzie 
> takie
> samo. Powoduje to, że wszystkie mrówki wybierają tę samą drogę.

A jak (algorytmicznie) interpretujesz to prawdopodobieństwo?
Coś czuję, że wcale nie jako prawdopodobieństwo...

Pozdrawiam,
Jakub Wróblewski 

On 8 Paź, 10:33, Mateusz Piąty <x...@y.z> wrote:
> Prawdopodobieństwo, że mrówka przejdzie z wierzhołka "i" do wierzhołka "j"
> wylicza się wzorem:
>
>     power(Tij,alfa)*power(Nij,beta)
> P = -------------------------------------
>     Suma(power(Tij,alfa)*power(Nij,beta))
>
> Dla mozliwych do wybrania "j"
>
Oznaczmy wyliczone P jako Pij bo dla każdego j wartość może być inna.
P nie zależy od konkretnej mrówki ale od Tij czyli tego jak inne
mrówki chodziły
po grafie. Konkretna mrówka pójdzie z większym prawdopodobieństwem
tam,
gdzie częściej chodziły inne mrówki.

> W tym wzorze nie ma nic co by różnicowało prawdopodobieństwo wyboru
> konkretnego wierzchoła dla różnych mrówek. Dla każdej mrówki P będzie takie
> samo. Powoduje to, że wszystkie mrówki wybierają tę samą drogę.
>
 Prawdopodobieństwo wylosowania każdej liczby oczek jest identyczne.
Czy jak rzucasz kostką
to zawsze otrzymujesz tę samą liczbę oczek?

> Nie bardzo rozumiem co masz na myśli pisząc "losowanie". Tego elementu
Moim zdaniem mrówka podróżuje z punktu startu, przechodząc przez różne
wierzchołki.
Będąc w wierzchołku i, mrówka może pójść do wierzchołka j ze zbioru
Nij. Ten właśnie wierzchołek musisz
wylosować. Prawdopodobieństwo wylosowania wierzchołka j wynosi Pij
dane wzorem, który
przytoczyłeś. Musisz teraz wylosować j z rozkładu dyskretnego danego
liczbami Pij. Jak już wylosujesz to mrówka idzie
z i do j.
Zobacz jeszcze tę prezentację http://stefanbrock.neostrada.pl/materialy/NMS/CI_wyklad_ewoluc_4.pdf

Pozdrawiam,
   Wit Jakuczun

> A jak (algorytmicznie) interpretujesz to prawdopodobieństwo?
> Coś czuję, że wcale nie jako prawdopodobieństwo...

Wyliczam prawdopodobieństwo "P" dla każdej możliwej trasy do sąsiefniego
miasta i wybieram dla konkretnej mrówki tę trasę dla której to
prawodpodobieństwo jest największe.

Witam,

"Mateusz Piąty" <x@y.z> wrote in message 
news:ziaqtxyww5kc$.av9ngi2u4ylc$.dlg@40tude.net...
>
>> A jak (algorytmicznie) interpretujesz to prawdopodobieństwo?
>> Coś czuję, że wcale nie jako prawdopodobieństwo...
>
> Wyliczam prawdopodobieństwo "P" dla każdej możliwej trasy do sąsiefniego
> miasta i wybieram dla konkretnej mrówki tę trasę dla której to
> prawodpodobieństwo jest największe.

Trafiłem z podejrzeniami :)
Prawopodobieństwo to parametr losowania. To, co proponujesz, to 
deterministyczne kryterium wyboru, a nie prawdopodobieństwo.

Pozdrawiam,
Jakub Wróblewski 

Dnia Thu, 8 Oct 2009 11:30:20 +0200, Mateusz Piąty napisał(a):

>> A jak (algorytmicznie) interpretujesz to prawdopodobieństwo?
>> Coś czuję, że wcale nie jako prawdopodobieństwo...
> 
> Wyliczam prawdopodobieństwo "P" dla każdej możliwej trasy do sąsiefniego
> miasta i wybieram dla konkretnej mrówki tę trasę dla której to
> prawodpodobieństwo jest największe.

Zapomniałem dodać, że zanim dokonam wyboru mnożę to wyliczone p przez
wwartość pseudolosową random() (pascal)

Dzięki za sugestie. Problem już jest zlokalizowany. Tak jak przypuszczał
Jakub Wróblewski nie dokonywałem chyba prawidłowo losowania. SPrawdzom to
teraz.

Użytkownik "Mateusz Piąty" <x@y.z> napisał
w wiadomości news:17uzkoerj49cg$.cdb84ramqvld$.dlg@40tude.net...
> Prawdopodobieństwo, że mrówka przejdzie z wierzhołka "i"
> do wierzhołka "j" wylicza się wzorem:
>
>    power(Tij,alfa)*power(Nij,beta)
> P = -------------------------------------
>    Suma(power(Tij,alfa)*power(Nij,beta))
>
> Dla mozliwych do wybrania "j"

Zły symbol: nie P, tylko Pij powinno być - prawdopodobieństwo
w węźle "i" wyboru przejścia do węzła "j".

>
> W tym wzorze nie ma nic co by różnicowało prawdopodobieństwo
> wyboru konkretnego wierzchoła dla różnych mrówek. Dla każdej
> mrówki P będzie takie samo.

OCZYWIŚCIE! Automat mrówkowy na tym właśnie polega,
że wszystkie mrówki są takie same - działają według
dokładnie tych samych reguł. W szczególności mają
te same prawdopodobieństwa konkretnych przejść.

> Powoduje to, że wszystkie mrówki wybierają tę samą drogę.

A to bzdura jest.

Jeśli masz z węzła np. i=5 dwa możliwe przejścia: do j=2
i do j=10, z prawopodobieństwami odpowiednio P(5, 2)=1/100
i P(5, 10)=99/100, to KAŻDA mrówka która weszła na piątkę
ma takie same prawdopodobieństwa - w stosunku 1:99 - wyboru
dalszej drogi.
Ale PRAWDOPODOBIEŃSTWO oznacza że coś MOŻE się zdarzyć,
a nie że MUSI się zdarzyć. Każda mrówka stojąca na piątce
musi WYLOSOWAĆ, czy pójdzie do 2 czy do 10. Oczywiście
losowanie nie ma być "orzeł czy reszka", tj. 50:50, tylko
1:99 (np. generatorem o rozkładzie równomierzym losujesz
liczbę ze zbioru {1, 2, 3, ... 100} i sprawdzasz czy wyszło
1 - jeśli tak, to idziesz do 2, w przeciwnym razie do 10).

W ten sposób jedna na sto mrówek wchodzących na węzeł nr 5
przejdzie dalej do  węzła 2, a 99% pójdzie do 10.


>
> Nie bardzo rozumiem co masz na myśli pisząc "losowanie".

Funkcję rnd() ...?


Maciek 

> 
> Trafiłem z podejrzeniami :)
> Prawopodobieństwo to parametr losowania. To, co proponujesz, to 
> deterministyczne kryterium wyboru, a nie prawdopodobieństwo.

Czy to co napisałem równocześnie z Tobą (że mnożę potem prawdopodobieństwa
przez random() - pascal) jest prawidłowe? 

Jakoś tak intuicyjnie to zrobiłem i działa ale z drugiej strony jakoś nie
mogłem znaleźć konieczności zastosowania tego i dlatego podejrzewałem, że
moja koncepcja jest zła.

D
> 
> Zły symbol: nie P, tylko Pij powinno być - prawdopodobieństwo
> w węźle "i" wyboru przejścia do węzła "j".
>

MAsz rację - to po prostu pośpiech
 
> 
> Funkcję rnd() ...?

Czyli jak już zdażyłem odpisać Jakubowi Wróblewskiemu mnożę te wyliczone
prawopodobieństwa przez random() (pascal) i dopiero z tych wartości
wybieram maksimum.

Czy to jest prawidłe podejście? W praktyce działa ale nie chodzi mi o
odkrywanie Ameryki ale o prawidłową implementację algorytmu.
> 
> 
> Maciek

On 8 Paź, 11:49, Mateusz Piąty <x...@y.z> wrote:

> Czyli jak już zdażyłem odpisać Jakubowi Wróblewskiemu mnożę te wyliczone
> prawopodobieństwa przez random() (pascal) i dopiero z tych wartości
> wybieram maksimum.
>
> Czy to jest prawidłe podejście?
Nie.

Pozdrawiam,
   Wit Jakuczun

No to problem jest ustalony tylko teraz byłbym wdzięczny jak "zorganizować"
to losowanie w pascalu. Muszę odejść od komputera na kilka godzin ale potem
na pewno przeczytam jeśli cośpodpowiesz.

Witam,

"Mateusz Piąty" <x@y.z> wrote in message 
news:1r4h7ym0geox4.yvcspv0qomr4$.dlg@40tude.net...
>> Wyliczam prawdopodobieństwo "P" dla każdej możliwej trasy do sąsiefniego
>> miasta i wybieram dla konkretnej mrówki tę trasę dla której to
>> prawodpodobieństwo jest największe.
>
> Zapomniałem dodać, że zanim dokonam wyboru mnożę to wyliczone p przez
> wwartość pseudolosową random() (pascal)

To nie jest realizacja losowania z takim prawdopodobieństwem.

Zadanie jest takie: mamy k możliwych dróg, każda ma prawdopodobieństwo p_i, 
przy czym suma p_i po wszystkich k jest 1. Mamy dokonać wyboru losowego 
jednej z k mozliwości tak, aby wybór i-tej możliwości miało 
prawdopodobieństwo p_i.

Rozwiązanie dla leniwych:
- losujemy i ze zbioru {1, ... k}, każde z jednakowym prawdopodobieństwem,
- losujemy liczbę rzeczywistą r z przedziału [0,1],
- jeśli r < p_i, to zatwierdzamy rozwiązanie i,
- w przeciwnym przypadku wracamy na początek i losujemy kolejne i.

Rozwiązanie, które nie wymaga wielu losowań:
- liczymy dystrybuantę d_i = sum_{1..i} p_i, ustalamy d_0 = 0,
- losujemy liczbę rzeczywistą r z przedziału [0,1],
- znajdujemy takie j, żeby d_(j-1) < r <= d_j,
- j jest szukanym rozwiązaniem.

Pozdrawiam,
Jakub Wróblewski 

Użytkownik "Mateusz Piąty" <x@y.z> napisał
w wiadomości news:19pva9lnlf400$.1qqgz3d3va30l.dlg@40tude.net...
> D
>>
>> Zły symbol: nie P, tylko Pij powinno być - prawdopodobieństwo
>> w węźle "i" wyboru przejścia do węzła "j".
>>
>
> MAsz rację - to po prostu pośpiech
>
>>
>> Funkcję rnd() ...?
>
> Czyli jak już zdażyłem odpisać Jakubowi Wróblewskiemu mnożę te wyliczone
> prawopodobieństwa przez random() (pascal) i dopiero z tych wartości
> wybieram maksimum.
> Czy to jest prawidłe podejście? (...)

Nigdy w życiu...!

Co to znaczy "mnożę przez random"??? Jaki jest ten random?

Powiedzmy, że masz w danym podejściu prawdop. 1/100 : 99/100
i funkcja random() daje Ci liczbę rzeczywistą z przedziału
(0, 1). Po pomnożeniu przez 1/100 i 99/100 wyjdą dwie liczby
(dodatkowy problem: mogą być istotnie skorelowane!)
jedna o zakresie 0 - 1/00, druga 0 - 99/100. Druga będzie
większa od pierwszej z prawopodobieństwem 197/198, czyli
około 99,5% -- a miało być 99%. Twój program wybierze
pierwszą drogę tylko raz na 200 prób, zamiast raz na 100...


> W praktyce działa ale nie chodzi mi o
> odkrywanie Ameryki ale o prawidłową implementację algorytmu.

WYOBRAŹ sobie podział przedziału jednostkowego na części
o długościach P(i,1), P(i,2), P(i,3), ... P(i,N) - gdzie N
maksymalny numer węzła, do którego można przejść z bieżącego
i-tego węzła. Masz wylosować liczbę z przedziału (0,1)
i sprawdzić w którą część trafiłeś -- tą drogą pójdzie mrówka.

Sprawdź więc, czy wylosowana liczba L jest mniejsza od P(i,1)
- jeśli tak, idziesz do 1. W przeciwnym razie odejmij od niej
P(i,1) i sprawdź, czy wynik jest mniejszy od P(i,2) - jeśli tak,
to idziesz do węzła 2, w przeciwnym razie od bieżącej, już raz
zmniejszonej wartości L, odejmujesz P(i,2), i porównujesz
z P(i,3) -- i tak dalej.
Wskutek błędów zaokrągleń może się zdarzyć, gdy wylosowane L
będzie bardzo bliskie 1, że odejmiesz wszystkie wartości P,
i wciąż pozostanie znikoma dodatnia reszta. Zalicz ją wtedy
do ostatniego przedziału.


Maciek 

Użytkownik "Maciek" <maciek@elkomtech.com.pl.nospam>
napisał w wiadomości news:hakdt4$5bj$1@opal.futuro.pl...
>
> Użytkownik "Mateusz Piąty" <x@y.z> napisał
> w wiadomości news:19pva9lnlf400$.1qqgz3d3va30l.dlg@40tude.net...
>> D
>>>
>>> Zły symbol: nie P, tylko Pij powinno być - prawdopodobieństwo
>>> w węźle "i" wyboru przejścia do węzła "j".
>>>
>>
>> (...........................)
>>
>> W praktyce działa ale nie chodzi mi o odkrywanie
>> Ameryki ale o prawidłową implementację algorytmu.
>
> WYOBRAŹ sobie podział przedziału jednostkowego na części
> o długościach P(i,1), P(i,2), P(i,3), ... P(i,N) - gdzie N
> maksymalny numer węzła, do którego można przejść z bieżącego
> i-tego węzła. Masz wylosować liczbę z przedziału (0,1)
> i sprawdzić w którą część trafiłeś -- tą drogą pójdzie mrówka.
>
> Sprawdź więc, czy wylosowana liczba L jest mniejsza od P(i,1)
> - jeśli tak, idziesz do 1. W przeciwnym razie odejmij od niej
> P(i,1) i sprawdź, czy wynik jest mniejszy od P(i,2) - jeśli tak,
> to idziesz do węzła 2, w przeciwnym razie od bieżącej, już raz
> zmniejszonej wartości L, odejmujesz P(i,2), i porównujesz
> z P(i,3) -- i tak dalej.
> Wskutek błędów zaokrągleń może się zdarzyć, gdy wylosowane L
> będzie bardzo bliskie 1, że odejmiesz wszystkie wartości P,
> i wciąż pozostanie znikoma dodatnia reszta. Zalicz ją wtedy
> do ostatniego przedziału.


W Pascalu to będzie jakoś tak (nie pisałem w tym języku już
wiele lat, ale mam nadzieję, że to przypomina Pascala):


var
    P : array[ 1 .. MaxN ] of real;  { prawopodobieństwa }
    N : integer;                     { liczba elementów P[] }
    L : real;                        { liczba losowa od 0 do 1 }
    i : integer;                     { licznik }

    ....

    { zakładam, że N > 0, elementy P[i] od i=1 do i=N
      są nieujemne a ich suma wynosi (prawie równo) 1 }

    L := random;
    i := 0;
    repeat
        inc( i );
        L := L - P[ i ];
    until (L <= 0) or (i = N);

    wynik := i;                      { tą drogą pójdzie mrówka }



Maciek

Dziękuję wam obu i biorę się do roboty :)

DZiękuję - teraz do roboty :)

Dziękuję wam obu i biorę się do roboty :)