|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 05 Dec 2002 08:46:34
To : Alex Cvetkov
Subject : Re: Методы поиска глобального минимума.
--------------------------------------------------------------------------------
Alex Cvetkov wrote:
>
> О сходимости в любых условиях? или всетаки в какихто конкретных.
> Hе говоря уж о том что эта сходимость по вероятности.
>
> У меня есть обратных примеров. Все вероятностные методы плохо работают в
> условиях высокой овражности. (Есть даже определение овражных функционалов как
> неоптимизируемых вероятностными методами)
>
> Hахождение глобального экстремума возможно лиш при выполнении условия Лившица.
> Причем необходимо знание коэфициэнта лившица (или ее оценки сверху)
> Hо все известные методы работают крайне медленно. Hе говоря уж о том что
> вычеисление этого коэфициэнта задача не из простых.
Лифшиц фамилия знакомая, но на память приходит матанализ. А в anealing
все сводится к Марковской цепи без финальных состояний (и финальных
циклов), проще говоря вероятность перехода из любого состояния в любое
больше нуля, и имея конечную разрядность представления чисел в
компьютере, получаем Марковскую цепь, которая побывает в КАЖДОМ
состоянии и найдет минимум. Управляя разрядностью, управляем точностью
решения, а зная рапределение вероятностей положения минимума (априорное
или оцененное по ходу дела) повышаем скорость сходимости. И если
температуру понижать со скоростью не быстрее установленной законом (см.
соотв. литературу, наибольшая скорость - у Инбера), то процесс сходится
(по вероятности) к глобальному минимуму.
Анатолий Савельев
Казанский университет
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Методы поиска глобального минимума. 