Funkcja schładzania T(k)
dK
Są to
dla k N
1. T(k)~ = 1/(1+log k)
2. T(k)~=1/(k+1)
3. T(k)~=a^k, gdzie 0<a<1
Włodek Ty proponowałeś w swoim poście wariant 2.
Natomiast pod dyskusję chciałem rzucić wariant 3.
Argument - praktyka i teoria wskazuje, ze taka funkcja jest
najwydajniejsza w tym algorytmie.
Oczywiście mozna dla celów testowych zaimplementować wszystkie trzy
warianty albo dodać swoje własne.
Pozdrawiam
dK
Wlodzimierz Holsztynski
Tak, można próbować różne warianty schładzania.
To kwestia na przykład odkomentowania jednej
linijki i zakomentowania pozostałych definicji
schładzania (lub wybrania parametru; jestem
przesadnie chciwy na cpu, więc i mniej elegancki).
(Już się muszę wziąć za programowanie, pora
mi zacząć, bo mi się zrobił jakiś blok :-)
Trochę dziwi mnie szybkie schładzanie, bo
szybko daje suboptymalny wynik, ale musi
mieć szczególne szczęście by wylądować
na absolutnie optymalnym. W przypadku
liczb barokowych może być wciąż dobre,
gdyż podejrzewam, że ogromnych liczb
barokowych jest chmara. Przy zwykłym
podejściu idzie się od liczb małych do większych.
My z miejsca rozpatrywać będziemy iloczyny
przynajmniej kilkuset potęg liczb pierwszych.
Na serio będziemy badać iloczyny dziesiątków
tysięcy. Takich liczb nikt dotąd chyba nie badał.
Przy wielkiej przestrzeni szybkie schładzanie
jest atrakcyjne z musu, bo nie bardzo
nas stać na powolne, jest obawa, że nie
dożyjemy (jestem archeologiczny, niewiele
czasu mi zostało :-). Jednak powolniejsze
schładzanie jest solidniejsze. Amerykanie,
w Toyotach produkowanych w Stanach,
schładzają plastikowe elementy wewnątrz
samochodu, szybko je chłodząc, po czym
szybko użytkownikowi pękają, podczas, gdy
te wolno schładzane w Japonii, trwają latami.
Hm, przepraszam :-) -- serio, oba podejścia
mają swoje plusy i minusy (zalety i zady),
praktyka nam pokaże co i jak.
Pozdrawiam,
Włodek
dK
schładzania (w kolejności siły):
1. T(k) = T0/(1+ln (1+k)) - Boltzmana - schłodzenie z 100K
do 7 K trwa 588724 kroki
2. T(k) = T0/(1+k) - Cauchy'ego - schłodzenie z
100K do 7 K trwa 14 kroków
3. T(k) = T0/(1+k^l) - wykładniczy - schłodznie z
100K do 7 K trwa 177 kroków dla l=0.5 14 dla l=1 i 4 dla l=2
4. T(k) = T0*a^k - geometryczny - schłodzenie
j.w. trwa 265 kroków dla a=0.99, 26 dla a=0.9 i 12 dla
a=0.8
T0,l, a to parametry
k licznik pętli SA, gdzie k={0,1,2,3.....}
Ograniczenia:
T0>0, real
l>0, real
0<a<1 real
Wszystkie te funkcje mają jednak jedną cechę wspólną na początku
szybkie malenie potem coraz wolniejsze i asymptotycznie do zera
Proponuję jeszcze poeksperymentować z funkcją która na początku będzie
wolno spadała, potem szybciej by na końcu zwolnić i maleć
asymptotycznie do zera. To odbiega od naturalnego procesu stygnięcia,
ale utrzymanie się przez dłuższy czas w zakresie wysokich tempeatur
pozwoli na swobodniejsze wędrowanie. Można nawet przyjąć, że warunkiem
wyjścia będzie np. zmiana znaku drugiej pochodnej funkcji stygnięcia.
No i musi ona być mało obciążająca przy rekurencyjnej realizacji, zeby
się jak najszybciej liczyła.
dK
Artur
Wygląda na to, że jako jedyny masz na razie program (chyba, ze Włodek
też). Wykonywałeś już może jakieś eksperymenty z bazami TWR, lub z
"gołymi", czy na razie testujesz z jakimś innym problemem ?
Ja na razie jeszcze nie wziąłem się za kodowanie, ale się przymierzam.
Pod koniec tygodnia coś powinienem wysłać, jeśli mnie sprawy zawodowe
nie wyeksploatują. Spróbuję dość ogólnie i w C++ (coś tam jeszcze
pamiętam). Zobaczymy jak mi pójdzie, bo dawno nie pisałem.
Pozdrawiam,
Artur
Wlodzimierz Holsztynski
> Wszystkie te funkcje mają jednak jedną cechę wspólną na początku
> szybkie malenie potem coraz wolniejsze i asymptotycznie do zera
>
> Proponuję jeszcze poeksperymentować z funkcją która na początku będzie
> wolno spadała, potem szybciej by na końcu zwolnić i maleć
> asymptotycznie do zera.
Darku, tak jak proponujesz, też mam ochotę
próbować przyłączyć się do próbowania
kilku schładzań, które proponujesz.
Dodam, że nie aż tak subtelnie, również
probabilistyczna procedura wyboru ruchu
jest w praktyce skorelowana z "postępem"
i "regresem". Gdy będziemy nieco zaawansowani,
to będziemy na to zwracać uwagę, przedyskutujemy
nasze procedury.
Oczywiście wiecie, ale wspomnę, że w C++
mamy pointery do funkcji, więc bardzo łatwo
będzie się przerzucać z jednego schładzania
na inne.
A propos, Darku i Arturze (Artueze brzmi
bardzo tajemniczo i egzotycznie!), dopiero
zacznę s.a. programować z zera. Programowałem
s.a. tylko jeden temat w przeszłości, dwa razy,
bo za 2im podano mi bardziej złożone założenia
i baza danych była bardziej skomplikowana.
To był "global router" dla telekomunikacji.
(Za drugim razem połączenia miały nie tylko
przepustowość, ale jeszcze była ona podzielona
na "trunks"). Program dał mi wielką-wielką
satysfakcję, ale wszystko się zmarnowało, bo
firma de facto splajtowała (ten oddział). Szkoda!
(nie firmy, lecz mojego programu; latał na NeXT
i przede wszystkim na alpha DECa, 64-bit
station).
Strasznie rdzewieję, ale jestem zdeterminowany
odrdzewieć i poprogramować. Nawet też mam
wszelakie plany (gigantyczny apetyt), ale o tym
wspomnę w wątku ogólnym.
Pozdrawiam serdecznie,
Włodek
PS. U dentysty słuchałem muzyki
i leniwie myślałem o naszym projekcie.
dK
która najpierw powoli maleje potem szybciej by znowu zwolnić.
T(k)~=1/((ak)^2+1) - gdzie 0<a<1
Ze swojej strony temat funkcji schładzania kończe.
Na stronie zamieszcze gotowe procedurki w postaci wprost i
rekurencyjnej.
Pozdrawiam
dK
Wlodzimierz Holsztynski
> Wybrałem piątą funkcję schładzania,
> która najpierw powoli maleje potem szybciej by znowu zwolnić.
>
> T(k)~=1/((ak)^2+1) - gdzie 0<a<1
Darku, może czegoś nie doceniam.
Mam wrażenie, że przy ustalonym grafie,
i przy ustalonej procedurze ruchów,
wybór sposobu schładzania ma znaczenie
zarowno teoretyczne jak i praktyczne.
Sam jednak planuję zmiany w dobieraniu
tych wszystkich elementów. Głównie
przejmuję się ruchami; także samą
przestrzenią konfiguracji. Z tego powodu
dobór schładzan ia na początek
planuję bardzo prymitywny:
niech R oznacza liczbę ruchów (n.p.
R = 10^9, jako minimum przy w miarę serio
podejściu). Powiedzmy, że rozpatrujemy
ruch numer r, oraz że kara za proponowaną
konfigurację zwiększyła się. Wtedy konfigurację
tę program zaakceptuje, gdy random() % R > r.
To byłaby najprostsza wersja.
Prawdopodobieństwo akceptacji
gorszej konfiguracji maleje równomiernie
od 1 do 0. Jej plusikiem jest szybkośc
rachowania.
Zarzekłeś się Darku, że temat ze swojej
strony zakończyłeś, ale jeżeli ktoś, Ty
lub Artur lub Mirek, ma dalsze uwagi, to
chętnie przeczytam.
Pozdrawiam,
Włodek
Wlodzimierz Holsztynski
maleje do zera, od wartości zmiennej "eternity"
(która w czasie wykonywania programu jest stała,
ale jej wartośc zależy od argv[2]).
Index pętli schładzania nazywam timeLeft
(pozostasły czas).
Gdy konfiguracja jest "lepsza" od poprzedniej,
to zostaje zaakceptowana, i timeLeft
obniża się o 1 (zachodzi: --timeleft;).
Gdy konfiguracja jest "gorsza" od poprzedniej,
to w programie, który zamroziłem jako "brqJul23",
taka konfiguracja akceptowana jest z prawdopodobieństwem,
które maleje wraz z temperaturą, czyli wraz z timeLeft,
zgodnie z kodem:
else if (random()%eternity < timeLeft)
{ accept=1;
acceptMove();
}
else
{ accept=0;
rejectMove();
}
Oznacza to, że na początku jest bardzo gorąco,
może przesadnie (co modyfikuję w brqJulWhole).
W programie "brqJulSol" kod ten jest nieco zmodyfikowany.
Wprowadziłem 2 nowe zmienne (znowu dla programu
stałe, ale podawane w "command line" jako arg[3] argv[4]),
mianowicie goodSupp i wideSupp. Odrzucam konfiguracje,
których mośnik pierwszy nie przekracza gooSupp.
A więc zmniejszyłem przestrzeń konfiguracji (niezbyt
elegancko). Następnie akceptuję konfigurację, gdy jest
lepsza od poprzedniej. W przeciwnym wypadku,
"gorsza konfiguracja" ma szansę akceptacji większą
(dwa razy), gdy ma nośnik pierwszy większy od wide
support.
Widać, że pojęcie temperatury i kary nie da się czysto
odgrodzić. Wielkość mośnika stała się trzecim
filtrem w 3-stopniowym procesie kary (pierwszy,
to badPr--liczba niedorekomendowanych liczb
pierwszych; drugi to badSum--sumaryczny niedomiar
wykładników niedorekomendowanych liczb pierwszych).
Kod wygląda tak:
if (vsupp <= goodSupp)
{ accept = 0;
rejectMove();
}
else if (konfiguracja jest lepsza od poprzedniej)
{ accept=1;
acceptMove();
...
}
else
{ x = random()%eternity;
if ( ((x < timeLeft)&&(vsupp > wideSupp)) || ((x<<1) < timeLeft) )
{ accept=1;
acceptMove();
}
else
{ accept=0;
rejectMove();
} }
Następnie wersja brqJulWhole różni się od
wersji brqJulSol tylko jedną instrukcją:
x = (random()%eternity)<<1;
Czyli szansa zaakceptowania "gorszej" konfiguracji
jest tym razem 2 razy mniejsza. To tak jakbyśmy
wystartowali program w niższej temperaturze.
Można szansę zmienić w dowolnej proporcji,
na przykład tak:
x = ((random()%eternity)*3)>>1;
...
if ( ((x < timeLeft)&&(vsupp > wideSupp)) || ((x<<1) <
timeLeft) )
Tym razem szansę akceptacji wynosi więcej niż połowę
oryginalnej (z brwJul23), bo wynosi 2/3 oryginalnej.
***
Pozdrawiam,
Włodek