Алгоритм с парными пробами

2. Алгоритм с парными пробами

f(x1, ...,xi+ gi, ..., xn) - f(x1, ..., xi- gi..., xn)             2gi

 

где g_i – пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.  

Отметим, что при таких расчетах g_i ,нельзя брать слишком малым, а значения функции нужно вычислять с достаточно высокой степенью точности, иначе при вычислении разности

Df(x₁, ...,x_i+ g_i, ..., x_n) - f(x₁, ..., x_i, ..., x_n)

Df(x₁, ...,x_i+ g_i, ..., x_n) - f(x₁, ..., x_i- g_i,..., x_n)

будет допущена большая ошибка.

Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, эта погрешность зависит от величины пробного шага

 На рис. изображены линии уровня функции двух переменных u= f (х, у), , и приведена траектория поиска ее минимума с помощью метода градиентного спуска.

 

 

 

Метод наискорейшего спуска

 

Суть метода наискорейшего спуска состоит в следующем. Как и прежде, в начальной точке определяется антиградиент минимизируемой функции. Однако теперь в направлении антиградиента делается ни один шаг, а движутся в данном направлении до тех пор, пока целевая функция убывает, достигает в некоторой точке минимума. В этой точке опять определяют антиградиент и ищут новую точку минимума целевой функции и так далее. В данном методе спуск имеет более целеустремлённый характер, производится более крупными шагами и градиент функции вычисляется в меньшем числе точек.

Описание программы

 

Программа предназначена для нахождения точек минимума функций нескольких переменных – другими словами для минимизации этих функций.

В программе реализован один из методов спуска – Градиентный метод спуска с выбором шага. Начальный шаг задается.

Изменение шага осуществляется по схеме

 если ;  если

Вычисление градиента происходит по методу с парными пробами, это улучшает поиск за счёт более точного вычисления градиента.

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

Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях.

В связи с этим в программе был реализован более точный метод градиентного спуска.

В качестве условия окончания поиска задаётся требуемая малость модуля градиента функции, т.е. должно выполнятся условие

(В области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).

Так же в программе можно задавать номер итерации выхода из цикла,

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

Реализация программы:

Общая блок схема

Руководство для пользования

Программа написана на языке программирования С++, в

среде Borland C++5.

Программа имеет понятный интуитивный графический интерфейс.

После запуска необходимо следовать инструкциям и вводить все необходимые данные.

На начальном этапе выбирается одна из предложенных функций,

Затем вводится начальное приближение и диапазоны по каждой переменной. На следующем этапе вводятся параметры вычислений: начальный коэффициент шага, пробный шаг, погрешность.

Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума.

Затем графически отображает траекторию поиска точки минимума.

 

 

 

Приложение А

Листинг программы

 

#include <vcl.h>

#pragma hdrstop

#include "Math.hpp"

#include "math.h"

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

int ii=0,n=0,s=0;

AnsiString Formula[3]={"U=A*x1^3+B*x2^2-C*x1-D*x2","U=x1^2+x1*x2+x2^2","U=X1^2+X2^2"};

int KolPer[3]={2,2,2};// массив в котором хранится кол-во перемен. для каждой ф-ии

bool DD=true,Diapozon=true; // если true то точка входит в диапозон иначе нет

double PeremenN[5]={0};//double *PeremenN =new double[n]; //нул.приб

double InterN[5]={0};//double *InterN =new double[n]; //нач

double InterK[5]={0};//double *InterK =new double[n]; //кон

double Param[4]={0}; //параметры

double T1[5]={0};//double *T1 =new double[n]; //tochka i -я

double T2[5]={0};//double *T2 =new double[n]; //tochka i+1 -я

double TempT[5]={0};//double *TempT =new double[n]; // временная tochka i+1 -я

double BB[5]={0};//double *BB= new double [n]; // BB - массив с измененой i-ой точкой X[i]+g

double B[5]={0};//double *B= new double [n]; //B - массив с измененой i-ой точкой X[i]-g

int g=0;

double ModG =0; //модуль градиента

int ss=0,ind=0;

double **Tochki; // указатель на массив с точками приближения

//---------------------------------------------------------------------------

 double TForm1::F1( double T[]) //Formula1 U=A*x1^3+B*x2^2-C*x1-D*x2

 { double U = 0;

U=IntPower(T[0],3)+2*IntPower(T[1],2)-3*T[0]-4*T[1];

return U; }

//---------------------------------------------------------------------------

 double TForm1::F2( double T[]) //Formula2 U=x1^2+x1*x2+x2^2

 { double U = 0;

U = IntPower(T[0],2)+T[0]*T[1]+IntPower(T[1],2);

return U; }

//---------------------------------------------------------------------------

 double TForm1::F3( double T[]) //Formula3 U=X1^2+X2^2

 { double U = 0;

U =T[0]*T[0]+T[1]*T[1]+1;

return U; }

//---------------------------------------------------------------------------

void TForm1::Tochka(double shag) // функция считает координаты следующей точки

{ // n - количество переменных

for (int i = 0; i < n; i++)

{

TempT[i]=T2[i]-shag*Gr(i);

//точка X[j+1]=точка X[j]- h козф шага *градиет grad R(X[j])

}

}

//---------------------------------------------------------------------------

double TForm1::Gr( int i) //gradient i-номер переменной

 {

double dR=0; // dR - градиент по i

for (int j=0;j<n;j++) //BB,B==T1;

{

BB[j]=T2[j];

B[j]=T2[j];

}

BB[i]=T2[i]+ Param[1] ; // добавляем и отнимаем пробный шаг

B[i]=T2[i]- Param[1] ; // к i-ой переменной

switch (UD->Position) {

case 0: dR = (F1(BB)- F1(B))/(2*Param[1]) ; break;

case 1: dR = (F2(BB)-F2(B))/(2*Param[1]); break;

case 2: dR = (F3(BB)-F3(B))/(2*Param[1]); break;

}

return dR;

 }

//--------------------------------------------------------------------------

void TForm1::Min()

 { // массив в котором

//double Tochki[1][5]; //хранится первое приближение

//double **Tochki; //создаем массив Temp[ss][n]

Tochki = new double*[100];

for (int j = 0; j < 100; j++)

Tochki[j] = new double[3];

bool Minimum=false,Pogresh=false,shag=false;

double sh=Param[0];

for (int j=0;j<n;j++) //T1,T2,TempT=PeremenN;

{

T1[j]=PeremenN[j];

T2[j]=PeremenN[j];

TempT[j]=PeremenN[j];

Tochki[0][j]=PeremenN[j];

}

while ( Minimum == false ) // после выхода из цикла

{ // минимум в точке T2

shag=false;

// начало блока 2

while (shag == false)

{

double R=0;

Tochka(sh);

switch (UD->Position) {

case 0: R=F1(TempT)-F1(T1) ; break;

case 1: R=F2(TempT)-F2(T1); break;

case 2: R=F3(TempT)-F3(T1); break; }

if (R > 0) // шаг большой то

{ // уменьшаем его в 2 раза

sh= sh/2;

}

else

{ shag =true; }

}

// конец блока 2

// Проверяем входит ли точка в указанный диапозон

// если нет то считаем предыдущую точку минимальной

if (DD==true )

{

for ( int i=0; i<n; i++)

{

if ( InterN[i] > TempT[i])

{

Diapozon=false;

Minimum = true;

}

if (InterK[i] < TempT[i])

{

Diapozon=false;

Minimum = true;

}

}

}

for (int j=0;j<n;j++)

{

T1[j]=T2[j]; //T1=T2

T2[j]=TempT[j]; //T2=TempT

}

// начало блока 3

ModG=0; //- модуль градиента

for (int i = 0; i < n; i++)

{

ModG+= Gr(i)*Gr(i);

}

ModG=sqrt(ModG);

if ( ModG < Param[2]) // /gradient/ < e где e-погрешность

 { Minimum=true; } // /gradient/ - модуль градиента

// конец блока 3

ss++;

if (Param[3] != -1 )

if (ss == Param[3])

Minimum=true;

// начало блока 4

if ( ss > 99 )

{ MessageDlg("Предел превышен ...точек более 100 ..измените шаг",mtWarning,

TMsgDlgButtons() << mbOK , 0);break;}

if(Diapozon==true)

{

for (int j = 0; j < n; j++)

Tochki[ss][j] = T2[j];

}

}

for (int j = 0; j <= ss; j++)

{

for (int i = 0; i < n; i++)

TempT[i]= Tochki[j][i];

switch (UD->Position) {

case 0: Tochki[j][2] = F1(TempT) ; break;

case 1: Tochki[j][2] = F2(TempT); break;

case 2: Tochki[j][2] = F3(TempT); break; }

}

//

/* double **Temp; //создаем массив Temp[ss][n]

Temp = new double*[ss];

for (int j = 0; j < ss; j++)

Temp[j] = new double[n];

//

for (int i = 0; i < ss; i++)

for (int j = 0; j < n; j++)

Temp[i][j]=Tochki[i][j];

//

//for (int i = 0; i < ss; i++) //удаляем массив Tochki[ss][n]

//delete[] Tochki[i];

//delete Tochki;

//

int mm=ss+1;

double **Tochki; //создаем массив Tochki[ss+1][n]

Tochki = new double*[mm];

for (int j = 0; j < mm; j++)

Tochki[j] = new double[n];

//

for (int i = 0; i < mm-1; i++)

for (int j = 0; j < n; j++)

Tochki[i][j] = Temp[i][j];

//

for (int j = 0; j < n; j++)

Tochki[ss][j] = T2[j];

//

//for (int i = 0; i < ss; i++) //удаляем массив Temp[ss][n]

//delete[] Temp[i];

//delete [] Temp;

}

// конец блока 4 */

}

//--------------------------------------------------------------------------

void __fastcall TForm1::UDClick(TObject *Sender, TUDBtnType Button)

{

Edit2->Text=Formula[UD->Position];

}

//---------------------------------------------------------------------------

void __fastcall TForm1::StartClick(TObject *Sender)

{

Panel1->Visible=false;

Edit2->Text=Formula[UD->Position];

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Sh1NextClick(TObject *Sender)

{

ii++;

PageControl1->ActivePageIndex=ii;

g=1;

switch (UD->Position) {

case 0: Kol->Caption=KolPer[0];break;

case 1: Kol->Caption=KolPer[1];break;

case 2: Kol->Caption=KolPer[2];break;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Sh2NextClick(TObject *Sender)

{

ii++;

PageControl1->ActivePageIndex=ii;

g=3;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Sh3BackClick(TObject *Sender)

{

ii--;

PageControl1->ActivePageIndex=ii;

Panel5->Visible=false;

Sh2Next->Visible=false;

g=2;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Sh2BackClick(TObject *Sender)

{

if (g ==1 )

{

ii--;

PageControl1->ActivePageIndex=ii;

Panel2->Visible=true;

Panel3->Visible=false;

Panel4->Visible=false;

Panel5->Visible=false;

}

if (g == 2)

{

Panel3->Visible=true;

Panel4->Visible=false;

Panel5->Visible=false;

n=KolPer[UD->Position];

Per->Caption="X1 =";

s=0;

g=1;

}

if (g == 3)

{

Panel5->Visible=false;

Sh2Next->Visible=false;

g=2;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

Panel3->Visible=true;

n=KolPer[UD->Position];

Per->Caption="X1 =";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

PeremenN[s]=StrToFloat(Edit4->Text); //нул.приб

InterN[s]=StrToFloat(Edit3->Text); //нач

InterK[s]=StrToFloat(Edit5->Text); //кон

s++;

Per->Caption="X"+ IntToStr(s+1)+"=";

g=2;

if (s == n)

{Panel4->Visible=true;g=2;}

 }

//---------------------------------------------------------------------------

void __fastcall TForm1::Button3Click(TObject *Sender)

{

Param[0]=StrToFloat(Edit6->Text); //коэ.шага

Param[1]=StrToFloat(Edit7->Text); // проб.шаг

Param[2]=StrToFloat(Edit8->Text); // погр.

if(CB1->Checked == true )

{Param[3]=StrToFloat(NT->Text); }

else

{Param[3]=-1;}

Sh2Next->Visible=true;

Panel5->Visible=true;

g=3;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::PuskClick(TObject *Sender)

{

ss=0; //количество точек которых получилось

Diapozon=true;

Min();

if (Diapozon==false)

 ss=ss-1;

Sh3Back->Visible=true;

Panel6->Visible=true;

Series1->Clear();

for(int i = 0; i <ss; i++)

 {

Series1->AddXY(i,Tochki[i][2],"",clBlue);

Nomer->Items->Add(i);

}

Nomer->Items->Add(ss);

//Nomer->Items->St

//ListT->Items->Add(123);

//if ( Diapozon=true )

 //{ Itog->Caption="Точка минимума в указанном диапозоне "; }

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

void __fastcall TForm1::CB1Click(TObject *Sender)

{

if(CB1->Checked == true )

NT->Visible=true;

if(CB1->Checked == false )

NT->Visible=false;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button8Click(TObject *Sender)

{

Panel6->Visible=false;

ListT->Items->Clear();

Nomer->Items->Clear();

Nomer->ItemIndex=-1;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::NomerChange(TObject *Sender)

{

 int ind=Nomer->ItemIndex;

 ListT->Items->Clear();

 for (int i=0;i<n;i++)

 ListT->Items->Add(Tochki[ind][i]);

 ListT->Items->Add(Tochki[ind][2]);

 if (ind == ss)

 if( Diapozon==true)

{ ListT->Items->Add(" Минимум");}

else

{

ListT->Items->Add(" Минимум");

ListT->Items->Add("Следующая точка в");

ListT->Items->Add("диапозон не входит");

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Pr1Click(TObject *Sender)

{

if(Pr1->Checked == true )

DD=true;

if(Pr1->Checked == false )

{

DD=false;

MessageDlg("Вы отключили проверку диапозона точки,"

"убедитесь в этом",mtWarning,

TMsgDlgButtons() << mbOK , 0);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CB2Click(TObject *Sender)

{

 if(CB2->Checked == true )

{

Panel7->Visible=true;

Series1->Active=false;

Series2->Clear();

Perem->Text="Xi";

Perem->Items->Clear();

CB3->ItemIndex=-1;

CB3->Items->Clear();

CB4->ItemIndex=-1;

CB4->Items->Clear();

for(int i = 0; i < n; i++)

Perem->Items->Add(i+1);

for(int i = 0; i <= ss; i++)

{

CB3->Items->Add(i);

}

}

 if(CB2->Checked == false )

{

Series2->Clear();

Series2->Active=false;

Series1->Active=true;

Panel7->Visible=false;

CB4->Enabled=false;

CB3->Enabled=false;

}

 }

//---------------------------------------------------------------------------

void __fastcall TForm1::PeremChange(TObject *Sender)

{

int ind=Nomer->ItemIndex;

CB3->Enabled=true;

CB3->ItemIndex=0;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CB3Change(TObject *Sender)

{

CB4->Items->Clear();

CB4->ItemIndex=-1;

int in=CB3->ItemIndex;

CB4->Enabled=true;

for(int i = in; i <=ss ; i++)

CB4->Items->Add(i);

CB4->ItemIndex=0;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CB4Change(TObject *Sender)

{

 Bild->Visible=true;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BildClick(TObject *Sender)

{

Series2->Clear();

ListP->Items->Clear();

int nh=CB3->ItemIndex;

int nk=CB4->ItemIndex;

Series2->Active=true;

for(int i = nh; i <=nk+nh; i++)

{

Series2->AddXY(i,Tochki[i][ind],"",clBlue);

ListP->Items->Add(Tochki[i][ind]);

}

Bild->Visible=false;

CB4->Enabled=false;

CB4->Items->Clear();

CB4->ItemIndex=-1;

 }

//---------------------------------------------------------------------------

Приложение B

Исследование функции U=1*x1^3+2*x2^2-3*x1-4*x2 (изменением шага).

h=0,1; x₁ =-0,5; x₂=-1 ; x_1нач=-2, x_1кон=2, x_2нач=-2, x_2кон=2

№	x1	x2	R
0	-0,5	-1	7,375
1	-0,2750	-0,1999	1,6842
2	0,0023	0,2800	-0,9701
3	0,3023	0,5680	-2,5059
4	0,5749	0,7408	-3,4002
5	0,7757	0,8445	-3,8120
6	0,8952	0,9067	-3,9508
7	0,9548	0,9440	-3,9877
8	0,9813	0,9664	-3,9967
9	0,9924	0,9798	-3,9990
10	0,9969	0,9879	-3,9997
11	0,9988	0,9927	-3,9999
12	0,9995	0,9956	-4,0000
13	0,9998	0,9974	-4,0000
14	1,0000	0,9984	-4,0000

h=0,2; x₁ =-0,5; x₂=-1 ; x_1нач=-2, x_1кон=2, x_2нач=-2, x_2кон=2

№	x1	x2	R
0	-0,5	-1	7,375
1	0,0500	0,6000	-1,5301
2	0,5485	0,9200	-3,4676
3	0,9680	0,9840	-3,9964
4	1,0058	0,9968	-3,9999
5	0,9988	0,9994	-4,0000

h=0,3; x₁ =-0,5; x₂=-1 ; x_1нач=-2, x_1кон=2, x_2нач=-2, x_2кон=2

№	x1	x2	R
0	-0,5	-1	7,375
1	0,1750	1,4	-2,1996
2	1,0473	0,9200	-3,9804
3	0,9600	1,016	-3,9948
4	1,0305	0,9968	-3,9972
5	0,9747	0,0006	-3,9981
6	1,0196	0,9999	-3,9988
7	0,9839	1,0000	-3,9992
8	1,0126	1,0000	-3,9995
9	0,9898	1,0000	-3,9997
10	1,0081	1,0000	-39998
11	0,9935	1,0000	-3,9999
12	1,0052	1,0000	-3,9999
13	0,9958	1.0000	-3,9999
14	1,0033	1,0000	-4,0000
15	0,9973	1,0000	-4,0000
16	1,0021	1,0000	-4,0000
17	0,9983	1,0000	-4,0000
18	1,0013	1,0000	-4,0000

h=1; x₁ =-0,5; x₂=-1 ; x_1нач=-2, x_1кон=2, x_2нач=-2, x_2кон=2

№	x1	x2	R
0	-0,5	-1	7,375
1	0,6250	3	4,3692
2	1,5391	-1,0000	5,0283
3	0,5125	1	-3,4029
4	1,0655	1	-3,9869
5	0,9640	1	-3,9961
6	1,0170	1	-3,9991
7	0,9913	1,0000	-3,9998
8	1,0043	1	-3,9999
9	0,9978	1	-4,0000
10	1,0011	1	-4,0000