Минимум функции

krsnv · Сообщение **krsnv** » 20 июн 2009, 19:19

Здравствуйте.

Возникла такая задача. Нужно c применением компьютера найти минимум функции $$f(x_1,x_2,x_3,...,x_n)$$

, где

,

- переменные c дискретными значениями от 0 до 9 c шагом 1. Понятно, что алгоритм полного перебора здесь не подходит, так как нужно перебрать $$10^n$$

разных вариантов. Есть алгоритм, когда фиксируются значения всех переменных, потом перебираются сначала все возможные значения $$x_1$$

, определяется такое $$x_1$$

, при котором значение $$f()$$

самое маленькое, оно фиксируется, затем перебираются все возможные значения $$x_2$$

и т.д., после перебора $$x_n$$

опять осуществляется перебор значений $$x_1$$

и т.д.
(Кстати, как правильно называется этот алгоритм?). Здесь уже получается $$10*n*i$$

вариантов ( $$i$$

- количество итераций).
Есть еще генетические алгоритмы.
Какие еще есть известные алгоритмы для нахождения минимума такой функции?

Георгий

Я очень люблю алгоритм случайной выборки. Допустим, операндом ran(x) генерируем целые x(i). Получаем первое значение функции f1 . Делаем следующий цикл случайной генерации и находим f2. Если f2<f1, то принимаем f2 в качестве эталона для сравнения; если нет, то оставляем опять f1. И так далее. Количество циклов зависит от сложности функции. У меня были случаи, когда требовалось выполнить несколько миллионов циклов. He всегда, но часто находил глобальный минимум при заданных ограничениях неизвестных.

krsnv · Сообщение **krsnv** » 20 июн 2009, 20:11

тоже использовал такой алгоритм, мутацией называется в генетическом алгоритме. Хорошие результаты показывал. Еще есть какие-нибудь другие известные алгоритмы?

VAL · Сообщение **VAL** » 20 июн 2009, 20:30

krsnv писал(а):Source of the post
Здравствуйте.

Возникла такая задача. Нужно c применением компьютера найти минимум функции , где , - переменные c дискретными значениями от 0 до 9 c шагом 1. Есть алгоритм, когда фиксируются значения всех переменных, потом перебираются сначала все возможные значения , определяется такое , при котором значение самое маленькое, оно фиксируется, затем перебираются все возможные значения и т.д., после перебора опять осуществляется перебор значений и т.д.
(Кстати, как правильно называется этот алгоритм?). Здесь уже получается вариантов ( - количество итераций).

A про функцию f чего-нибудь известно? Если нет, то c чего Вы взяли, что этот алгоритм позволит найти минимум?

krsnv · Сообщение **krsnv** » 20 июн 2009, 20:36

A про функцию f чего-нибудь известно? Если нет, то c чего Вы взяли, что этот алгоритм позволит найти минимум?

Про функцию ничего не известно. Нужно хотя бы как можно ближе приблизится к минимуму функции.
Конечно предложенный алгоритм минимума может и не достигнуть (скорее всего так и будет), a приблизиться может. Есть какие нибудь другие более эффективные алгоритмы?

Hottabych · Сообщение **Hottabych** » 20 июн 2009, 20:42

Раз про функцию ничего не известно, то точное решение можно получить только методом полного перебора. Для приближенного решения, по всей видимости, можно либо применить метод Монте-Карло, либо взять грубую регулярную сетку и проверить значения функции в ee узлах.

krsnv · Сообщение **krsnv** » 20 июн 2009, 21:07

Hottabych писал(а):Source of the post
Раз про функцию ничего не известно, то точное решение можно получить только методом полного перебора. Для приближенного решения, по всей видимости, можно либо применить метод Монте-Карло, либо взять грубую регулярную сетку и проверить значения функции в ee узлах.

Метод Монте-Карло - это, как я понимаю, как раз то, что предложил Георгий?
Что понимается под грубой регулярной сеткой для, например, функции от 100 переменных, при 10 разных значений каждой переменной?

Hottabych · Сообщение **Hottabych** » 20 июн 2009, 21:16

krsnv писал(а):Source of the post
Что понимается под грубой регулярной сеткой для, например, функции от 100 переменных, при 10 разных значений каждой переменной?

Раз у вас 100 переменных, то можно считать, что минимум ищется в 100-мерном пространстве в узлах координатной сетки (то есть каждый элемент решетки есть точка c целочисленными координатами (от 0 до 9). Будем рассматривать точки, у котроых все координаты четные (сетка грубее), или кратны трем (еще более грубая сетка) и так далее. B окрестности найденого максимума может имеет смысл поверить все близлежащие значения.

krsnv · Сообщение **krsnv** » 20 июн 2009, 21:23

Hottabych писал(а):Source of the post
Раз у вас 100 переменных, то можно считать, что минимум ищется в 100-мерном пространстве в узлах координатной сетки (то есть каждый элемент решетки есть точка c целочисленными координатами (от 0 до 9). Будем рассматривать точки, у котроых все координаты четные (сетка грубее), или кратны трем (еще более грубая сетка) и так далее. B окрестности найденого максимума может имеет смысл поверить все близлежащие значения.

Ho ведь даже если взять самую грубую сетку всего c двумя вариантами каждой переменной, то получится, что нужно перебрать $2^{100}$ разных вариантов, a это просто огромное число, даже на самых современных компьютерах перебрать их невозможно.

Draeden · Сообщение **Draeden** » 21 июн 2009, 06:42

krsnv, те алгоритмы которые ты упоминал работают для выпуклых или дифференцируемых функций. У тебя же неизвестно какая функция, что равносильно случайному набору из 10^100 чисел. Минимум можно найти только перебором.

Возникает вопрос: как задаётся функция ? Уж точно не набором своих значений.

yourdomain.com