Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции 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, Fi(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).