Минимум

From

Ilya Rogov (2:5030/1334.1024)

To

Alexander Shevchenko ()

Date

2003-02-28T02:10:30Z

Area

RU.ALGORITHMS

    Привет тебе, Alexander, с того света от Ильи.

 Давным-давно, 10 Feb 03 16:32, когда земля была ещё тёпленькая
 и по ней бегали мамонты, Alexander Shevchenko и Ilya Rogov говорили про Минимум:

 AS>>> Подобная дрянь (мною описанная) имеет вид перевернутого
 AS>>> колокола, на дне которого типа картофельного поля, то есть полно
 AS>>> локальных минимумов. Даже маткад не всегда находит минимум
 AS>>> (приходится руками изменять начальную точку).
 IR>>   В случае многих локальных экстремумумов попробуй имитацию
 IR>> отжига (моя лубимая :-)) ) - быстро и красиво.
 AS> А это как?

   О! :-))) Если вкратце и в общих чертах ... Значится так:

     1. Берёшь произвольную точку (начальную). Обзываешь пока-решением.

     2. Считаешь в ней свою много-раз-чёрти-где-экстремальную функцию.       Обзываешь пока-оптимальным-значением.

     3. Берёшь новую точку. Совсем произвольно, но лучше небольшим
        произвольным сдвигом из первоначальной.

     4. Считаешь функцию в этой новой точке. Обзываешь полученное       значением-функции-на-данном-шаге.

     4. Имеешь функцию оценки exp(-deltaE/T) < X. (X - генерится каждый раз,   как (float)random(1); deltaE - разница между значением-на-данном-шаге
        и пока-оптимальным-значением; T - температура, о ней позжее, пока это  просто параметр;). Т.е. если X оказывается больше - то это плохая
        точка, а если меньше - то хорошая и ты обзываешь её пока-решением.

     5. goto 3, пока не надоест.

     6. Как только надоело - понижаем температуру. Например - умножая на       её каждый раз какую-нить константу, типа 0.99. И - снова goto 3.

     7. Когда T (из начальных, скажем 20 абстрактных градусов) достигнет,      скажем, 0.0001 абстрактных градусов, тормозишь, делаешь радостное лицо        и считаешь пока-решение совсем решением, а пока-оптимальное-значение       совсем оптимальным значением.

   Метод вероятностный и требует подгонки параметров (начальная/конечная температура и способ её уменьшения, какие-нить ограничения, типа максимального числа вычислений функции вообще и вычислений без изменения температуры в 5 ).

   Ежели бредово - попытаюсь прояснить ...

ЗЫЖ А кто-нить ещё пробовал им решать хоть какие-нибудь задачи ??

                                                        Ilya Rogov
... Бредить помогали вопли моих соседей
---
 * Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)