Метод случайного поиска

Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

В программе рассматривается реализация данного метода для функции одной переменной.

Произвольная функция F(x) задана на промежутке [ A,B ]. С помощью датчика случайных чисел, равномерно распределенных на промежутке [0,1], строится последовательность случайных чисел x{ k }, k=1...,N, равномерно распределенных на промежутке [A,B]. Вычисляются и сравниваются между собой значения функции F(x) в точках x{ k }. Минимальное из них принимается за оценку минимума функции F(x) на промежутке [A,B].

Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что рассматривается.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).

Метод Фибоначчи.

Метод Фибоначчи (МФ) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [ A,B ].

Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s}= B{s} – G{s} (B{s} – А{s})

R{s}= А{s}+ G{s} (B{s} – А{s})

где G{s}=Fi (N – s – 1) /Fi(N – s), s=0...,N – 3, G{N – 2 } = (1+e) /2 или (1 – e) /2, N — заданное число итераций e > 0, F_i(j) — числа Фибоначчи, что задаются рекуррентным соотношением

Fi(j)= Fi(j – 1) + Fi(j – 2), j ³ 2, Fi(0)= Fi(1)= 1.

Возлагают

А { s+1 } = А{s}, B{s+1}= R{s}, если F (L{s}) £ F (R{s})

А { s+1 } = L{s}, B{s+1}= B{s}, если F (L{s} ) > F ( R{s}).

За приближенное решение задачи принимают

x* = (А{N}+ B{N}) /2, y* = F (x*).

Для МФ в случае предварительно фиксированного числа итераций длина конечного интервала поиска минимальная.

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).