3.3. Метод пробных движений

По каждой из переменных:

• из исходной точки делается маленький пробный шаг;

• находится значение функции;

• шаг делается обратно, чтобы вернуться в исходную точку.

Из всех опробованных направлений выбирается то, в котором уменьшение (увеличение) целевой функции наибольшее. Делается шаг (возможно, больше пробного) в выбранном таким образом направлении. Процедура повторяется до достижения заданной точности поиска.

Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.

function[]=ProbShag2D_170809();

function [f]=Function(xVector);

nVar=length(xVector); % nVar означает число варьируемых переменных

f=1;

for i=1:nVar

f=f+(xVector(i)-2)^2;

end

end

%метод пробных движений

disp('ДВУМЕРНЫЙ ПОИСК МИНИМУМА ФУНКЦИИ ');

disp('С ИСПОЛЬЗОВАНИЕМ МЕТОДА ПРОБНОГО ШАГА');

disp('применен для указанной функции: z(i,j)=-sqrt(256-(x(i))^2-(y(j))^2)');

disp('ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска');

function[xOptVector,fMinValue,leftBorderVector,rightBorderVector,stepNumberVector]=FunctionPS();

numberOfVariables=input('введите число переменных:');

%ввод вектора аргументов, их левых и правых границ, их шагов

for i=1:numberOfVariables

lBVstring=strcat('введите левую границу диапазона поиска по х(',num2str(i),'):');

leftBorderVector(i)=input(lBVstring);

rBVstring=strcat('введите правую границу диапазона поиска по х(',num2str(i),'):');

rightBorderVector(i)=input(rBVstring);

sNVstring=strcat(‘введите величину шага по х(‘,num2str(i),’):’);

stepNumberVector(i)=input(sNVstring);

OK=input(‘перейти к следующей переменной=1 переделать ввод текущей переменной=0’);

if OK==0

i=i-1;

continue;

end

end

k=1;

for i=1:numberOfVariables

xVector(i)=(leftBorderVector(i)+rightBorderVector(i))/2; %все переменные по середине диапазонов поиска

end

funVector(k)=Function(xVector); % вычислили функцию

df=-1;

%основной цикл поиска минимума функции

control=1;

while (df<0)&(control>0)

if k>1000

disp('k>1000');

break;

end

%делаем пробные шаги в сторону возрастания переменных по всем

%переменным и создаем первую половину вектора изменений функции

l=0;

for i=1:(numberOfVariables*2)

funChangeVector(i)=0; % массив, хранящих изменения значений функций при следанных шагах

end

disp('делаем пробные шаги в сторону возрастания переменных');

for i=1:numberOfVariables

if (leftBorderVector<=xVector(i))&(xVector(i)<=rightBorderVector(i))

xVector(i)=xVector(i)+stepNumberVector(i);

l=l+1;

funChangeVector(l)=Function(xVector)-funVector(k);

disp(strcat(‘funChangeVector(‘,num2str(l),’)=’,num2str(funChangeVector(l))));

xVector(l)=xVector(l)-stepNumberVector(l);

else

control=-1;

disp(‘control=-1;’);

end

end

%делаем пробные шаги в сторону убывания переменных по всем переменным и создаем вектор %изменений функции

l=0;

disp('делаем пробные шаги в сторону убывания переменных');

for i=1:numberOfVariables

if (leftBorderVector<=xVector(i))&(xVector(i)<=rightBorderVector(i))

xVector(i)=xVector(i)-stepNumberVector(i);

l=l+1;

funChangeVector(l+numberOfVariables)=Function(xVector)-funVector(k);

disp(strcat(‘funChangeVector(‘,num2str(l),’)=’,num2str(funChangeVector(l+numberOfVariables))));

xVector(l)=xVector(l)+stepNumberVector(l);

else

control=-1;

end

end

disp(strcat(‘xVector после шага ‘,num2str(k),’ равен ‘,num2str(xVector),’ funChangeVector после шага ‘,num2str(k),’ равен ‘,num2str(funChangeVector)));

minCF=0;

for i=1:(numberOfVariables*2)

if minCF>funChangeVector(i)

minCF=funChangeVector(i);

if i<=numberOfVariables

indexOfArg=i;

znak=1;

else

indexOfArg=i-numberOfVariables;

znak=-1;

end

end

end

disp(strcat(‘Наибольшее убывание функциии по переменной номер ‘,num2str(indexOfArg),’ эта переменная =’,num2str(xVector(indexOfArg))));

%нашли переменную, по которой наибольшее убывание функции

%увеличиваем (или уменьшаем) ее на полную величину шага

if znak==1

xVector(indexOfArg)=xVector(indexOfArg)+stepNumberVector(indexOfArg);

else

xVector(indexOfArg)=xVector(indexOfArg)-stepNumberVector(indexOfArg);

end

k=k+1;

funVector(k)=Function(xVector); % вычислили функцию

df=funVector(k)-funVector(k-1); % вычислили ее приращение

if df>0 %если пройден минимум и функция начала возрастать

%отступаем на один шаг назад

if znak==1

xVector(indexOfArg)=xVector(indexOfArg)-stepNumberVector(indexOfArg);

else

xVector(indexOfArg)=xVector(indexOfArg)+stepNumberVector(indexOfArg);

end

funVector(k)=Function(xVector); % вычислили функцию

disp(‘df>0’);

end

disp(strcat(‘xVector: ‘,num2str(xVector),’ function= ‘, num2str(funVector(k))));

end

%возвращаемые значения

xOptVector=xVector;

fMinValue=funVector(k);

end %конец функции поиска методом пробных движений

%обращение к функции

[xOptVector, fMinValue, leftBorderVector, rightBorderVector, stepNumberVector] =FunctionPS();

%вывод ответа в виде текста

disp('НАЙДЕН МИНИМУМ ФУНКЦИИ');

for i=1:length(xOptVector)

string=sprint(‘номер переменной= %4i\t переменная= %7.3f\t’,i,xOptVector(i));

disp(string);

end

string=sprint(‘минимум функции= %7.3f’,fMinValue);

disp(string);

% вывод на экран

%подготовка данных для графика

if length(xOptVector)==5

hx=(rightBorderVector(1)-leftBorderVector(1))/100;

hy=(rightBorderVector(2)-leftBorderVector(2))/100;

x=leftBorderVector(1):hx:rightBorderVector(1);

y=leftBorderVector(2):hy:rightBorderVector(2);

z(2,2)=0;

for i=2:100

for j=2:100

x(i)=x(i-1)+hx;

y(j)=y(j-1)+hy;

xV(1)=x(i);

xV(2)=y(j);

z(i,j)=Function(xV);

end

end

surf(x,y,z);

title(‘f=f+(xVector(i)-2)^2;’);

xlabel(‘X’);

ylabel(‘Y’);

zlabel(‘Z’);

text(xOptVector(1),xOptVector(2),fMinValue,’\leftarrow Minimum ‘);

legend(‘f=f+(xVector(i)-2)^2’,0);

end

end

В данном случае рисункок к данному примеру поиска экстремума функциине приведен из-за его сходства с приведенными выше (например, с рис. 3.4).

После выполнения этой программы пользователь видит на экране соответствующий текст, вводит нужные значения и получает результат:

ДВУМЕРНЫЙ ПОИСК МИНИМУМА ФУНКЦИИ

С ИСПОЛЬЗОВАНИЕМ МЕТОДА ПРОБНОГО ШАГА

Применен для указанной функции: z(i,j)=-sqrt(256-(x(i))^2-(y(j))^2)

ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска

введите число переменных:2

введите левую границу диапазона поиска по х(1):-10

введите правую границу диапазона поиска по х(1):10

введите величину шага по х(1):0.5

перейти к следующей переменной=1 переделать ввод текущей переменной=01

введите левую границу диапазона поиска по х(2):-10

введите правую границу диапазона поиска по х(2):10

введите величину шага по х(2):0.5

перейти к следующей переменной=1 переделать ввод текущей переменной=01

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =-1.75

изменение функции после шага по:2 переменной =-1.75

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =2.25

изменение функции после шага по:2 переменной =2.25

вектор переменных после шага:1 равен:0 0

Наибольшее убывание функциии по переменной номер:1 эта переменная =0

вектор переменных:0.5 0 function=7.25

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =-1.25

изменение функции после шага по:2 переменной =-1.75

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =1.75

изменение функции после шага по:2 переменной =2.25

вектор переменных после шага:2 равен:0.5 0

Наибольшее убывание функциии по переменной номер:2 эта переменная =0

вектор переменных:0.5 0.5 function=5.5

часть вывода вырезана

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =-0.75

изменение функции после шага по:2 переменной =-0.75

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =1.25

изменение функции после шага по:2 переменной =1.25

вектор переменных после шага:5 равен:1 1

Наибольшее убывание функциии по переменной номер:1 эта переменная =1

вектор переменных:1.5 1 function=2.25

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =-0.25

изменение функции после шага по:2 переменной =-0.75

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =0.75

изменение функции после шага по:2 переменной =1.25

вектор переменных после шага:6 равен:1.5 1

Наибольшее убывание функциии по переменной номер:2 эта переменная =1

вектор переменных:1.5 1.5 function=1.5

часть вывода вырезана

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =0.25

изменение функции после шага по:2 переменной =-0.25

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =0.25

изменение функции после шага по:2 переменной =0.75

вектор переменных после шага:8 равен:2 1.5

Наибольшее убывание функциии по переменной номер:2 эта переменная =1.5

вектор переменных:2 2 function=1

делаем пробные шаги в сторону возрастания переменных

изменение функции после шага по:1 переменной =0.25

изменение функции после шага по:2 переменной =0.25

делаем пробные шаги в сторону убывания переменных

изменение функции после шага по:1 переменной =0.25

изменение функции после шага по:2 переменной =0.25

вектор переменных после шага:9 равен:2 2

Наибольшее убывание функциии по переменной номер:1 эта переменная =2

df>0 пройден минимум

вектор переменных:2 2 function=1

НАЙДЕН МИНИМУМ ФУНКЦИИ

номер переменной= 1 переменная= 2.000

номер переменной= 2 переменная= 2.000

минимум функции= 1.000

Кафедра информатики и компьютерного проектирования Российского химико-технологического университета имени Д.И. Менделеева.

Москва

Учебное издание