yourdomain.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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