Оптимизация в САПР

double x2 = a + b - x1;    //выбираем вторую точку

 

// сокращаем ТИЛ до  соответствующего условия

while((fabs(dfp(x+((a+b)/2)*p,p)))>e && fabs(a-b)>e && k<max_step)

{

if(f(x+x1*p) > f(x+x2*p))

{

if(x1 > x2)

b = x1;

else

a = x1;

x1 = a + 0.618*fabs(b-a);

}

else

{

if(x1 > x2)

a = x2;

else

b = x2;

x2 = a + b - x1;

}

k++;    // увеличиваем счётчик итераций

}

alpha=(a+b)/2;  // изменяем значение коэффициента удлинения вектора

return k;   // возвращаем количество итераций

}

 

 

// Метод Пауэлла

 

int CMETODI::Pauell_Odn(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

int k=0;    // задаём счётчик числа итераций

   double c=b,d;  // задаём необходимые переменные

 

   b=(a+c)/2;   // определяем начальное значение b

 

// определяем начальное  значение d

   d=0.5*(f(x+a*p)*(b*b-c*c)+f(x+b*p)*(c*c-a*a)+f(x+c*p)*(a*a-b*b))/

     (f(x+a*p)*(b-c)+f(x+b*p)*(c-a)+f(x+c*p)*(a-b));

 

// сокращаем ТИЛ до соответствующего условия

   while((fabs((d-b)/fabs(b))>e) && (fabs((f(x+d*p)-f(x+b*p))/f(x+b*p))>e) && k<max_step)

   {

      if(f(x+b*p)>f(x+d*p))

      {

if(b>d)  // выбираем "лучшую" точку -

c=b;  // которой соответствует наименьшее

else   // значение функции, и, обозначив её как b

a=b;  // рассматриваем 4 ситуации

     b=d;

      }

      else

      {

if(b>d)

c=d;

else

a=d;

      }

 

// определяем значение d

      d = 0.5*((f(x+a*p)-f(x+b*p))*(b-c)*(c-a))/

(f(x+a*p)*(b-c)+f(x+b*p)*(c-a)+f(x+c*p)*(a-b))+0.5*(a+b);

      k++;    // увеличиваем счётчик итераций

   }

   alpha=(b+d)/2;  // изменяем значение коэффициента удлинения вектора

   return k;   // возвращаем количество итераций

}

 

 

// Метод Давидона

 

int CMETODI::Davidon(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

    int k=0;   // задаём счётчик числа итераций

    double z,w,r;  // задаём необходимые переменные

 

 if (a>b)

    {

r=b;

b=a;

a=r;

    }

 

// находим переменные  в соответстви с методом

    z=dfp(x+a*p,p)+dfp(x+b*p,p)+3*(f(x+a*p)-f(x+b*p))/(b-a);

    w=sqrt(z*z-dfp(x+a*p,p)*dfp(x+b*p,p));

    r=a+(b-a)*(z-dfp(x+a*p,p)+w)/(dfp(x+b*p,p)-dfp(x+a*p,p)+2*w);

 

// сокращаем ТИЛ до соответствующего условия

while((fabs(dfp(x+((a+b)/2)*p,p)))>e && fabs(a-b)>e && k<max_step && dfp(x+r*p,p)>e)

    {

k++;    // увеличиваем счётчик итераций

 

if(dfp(x+r*p,p)<0) // рассматриваем 2 ситуации

a=r;

else

b=r;

 

// находим переменные  в соответстви с методом

z=dfp(x+a*p,p)+dfp(x+b*p,p)+3*(f(x+a*p)-f(x+b*p))/(b-a);

w=sqrt(z*z-dfp(x+a*p,p)*dfp(x+b*p,p));

r=a+(b-a)*(z-dfp(x+a*p,p)+w)/(dfp(x+b*p,p)-dfp(x+a*p,p)+2*w);

    }

alpha=r/*(a+b)/2*/; // изменяем значение коэффициента удлинения вектора

    return k;   // возвращаем количество итераций

}

 

 

// Метод Фибоначчи-1

 

int CMETODI::Fibonachchi_1(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

   int k=0;    // задаём счётчик числа итераций

 

double Ln=0.01*e;   // задаём длину конечного интервала

   double n=0;     // порядковый номер числа Фибоначчи

 

   while(Fib(n)<(b-a)/Ln) // определяем этот номер в

      n++;      // соответствии с алгоритмом

 

   double l, m;    // задаём необходимые переменные

 

   l=a+(Fib(n-2)*(b-a))/(Fib(n)); // первая начальная точка

   m=a+(Fib(n-1)*(b-a))/(Fib(n)); // вторая начальная точка

 

   while(k<n-1)    // сокращаем ТИЛ в соответствии с методом

   {

      if(f(x+l*p)<f(x+m*p))

      {

b=m;

m=l;

l=a+(Fib(n-k-2)*(b-a))/Fib(n-k);

      }

      else

      {

a=l;

l=m;

m=a+(Fib(n-k-1)*(b-a))/Fib(n-k);

      }

      k++;      // увеличиваем счётчик итераций

   }

 

   if(f(x+l*p)<=f(x+m*p)) // рассматриваем 2 возможные ситуации,

      alpha=(a+m)/2;   // вычисляем результирующее значение и

   else       // изменяем значение коэффициента

      alpha=(l+b)/2;   // удлинения вектора

 

   return k;     // возвращаем количество итераций

}

 

 

// Метод Фибоначчи-2

 

int CMETODI::Fibonachchi_2(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

   int k=0;     // задаём счётчик числа итераций

 

double Ln = 0.01*e; // задаём длину конечного интервала

double x1 ,x2;   // задаём необходимые переменные

   double n=0;    // порядковый номер числа Фибоначчи

 

while(Fib(n)<(b-a)/Ln) // определяем этот номер в

      n++;      // соответствии с алгоритмом

 

   x1=a+Fib(n-1)*(b-a)/Fib(n)+pow((-1),n)*e/Fib(n); // первая начальная точка

 

   while(k<n)       // сокращаем ТИЛ в соответствии с методом

   {

      x2 = a+b-x1;     // вторая точка

 

      if(f(x+x1*p)<f(x+x2*p))  // Сокращаем текущий интервал

      {         // локализации рассмотрением

if(x1<x2)     // 4-х ситуаций, аналогично

b=x2;      // методу золотого сечения-2

else

a=x2;

      }

      else

      {

if(x1<x2)

a=x1;

else

b=x1;

x1=x2;

      }

      k++;     // увеличиваем счётчик итераций

   }

   alpha=x2;    // изменяем значение коэффициента удлинения вектора

   return k;    // возвращаем количество итераций

}

 

 

// Метод экстраполяции-интерполяции

 

int CMETODI::ExIn(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

   int k=0;      // задаём счётчик числа итераций

double c=0,d=norma(x); // задаём необходимые переменные

  

   double h=0.001; // шаг

 

// сокращаем ТИЛ в  соответствии с методом

   while((fabs((d-b)/b)>e) && (fabs((f(x+d*p)-f(x+b*p))/f(x+b*p))>e) && k<max_step)

   {

      b=d;

      a=b-h;

      c=b+h;

      d=0.5*(f(x+a*p)*(b*b-c*c)+f(x+b*p)*(c*c-a*a)+

f(x+c*p)*(a*a-b*b))/(f(x+a*p)*(b-c)+f(x+b*p)*(c-a)+f(x+c*p)*(a-b));

      k++;    // увеличиваем счётчик итераций

   }

   alpha=(b+d)/2;  // изменяем значение коэффициента удлинения вектора

   return k;   // возвращаем количество итераций

}

 

// Методы многомерной  оптимизации

 

// Метод параллельных  касательных

 

CMatrix CMETODI::ParallelKasat(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step,  // максимальное количество итераций

int i1Min)   // метод одномерного поиска

{

int k=0;    // задаём счётчик числа итераций

 

CMatrix x2,   // промежуточная точка

x0=x,    // начальная точка

d,     // ускоряющее направление

p;     // направление поиска

 

// переопределяем массив  значений х

// при пошаговом поиске  и задаём

// значение начальной  точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);

 

do

{

p = -df(x);       // устанавливаем антградиентное направление

x = x+alpha*p;      // спускаемся в точку х2

x2 = x;        // сохраняем точку х2

p = -df(x);       // устанавливаем антградиентное направление

FindAlpha(x,p,e,i1Min);   // находим коэффициент удлинения вектора

x = x+alpha*p;      // спускаемся в точку х3

d = x-x0;       // определяем ускоряющее направление

FindAlpha(x,p,e,i1Min);   // находим коэффициент удлинения вектора

x = x+alpha*d;      // спускаемся в точку х4

x0 = x2;        // если КОП не выполняется, то х2 - новая начальная точка

k++;         // увеличиваем счётчик итераций

MASSIV.insertCol(x);    // добавляем новое значение х в массив

}

while(norma(d)>e && norma(df(x))>e && k<*max_step);

 

*max_step=k;  // возвращаем количество итераций

return x;   // возвращаем найденный минимум

}

 

 

// Метод Коши

 

CMatrix CMETODI::Koshi(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step,  // максимальное количество итераций

int i1Min)   // метод одномерного поиска

{

int k=0;    // задаём счётчик числа итераций

CMatrix p(x);  // направление поиска

 

// переопределяем массив  значений х

// при пошаговом поиске  и задаём

// значение начальной  точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);

 

do

{ 

p = -df(x);       // устанавливаем антградиентное направление

FindAlpha(x,p,e,i1Min);   // находим коэффициент удлинения вектора

x = x+p*alpha;      // спускаемся в следующую точку х

k++;         // увеличиваем счётчик итераций

MASSIV.insertCol(x);    // добавляем новое значение х в массив

}

while(norma(p)>e && fabs(f(x+alpha*p)-f(x))>e && k<*max_step); // комбинированный КОП

 

*max_step=k;  // возвращаем количество итераций

return x;   // возвращаем найденный минимум

}

 

 

// Метод циклического покоординатного спуска

 

CMatrix CMETODI::CPS(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step,  // максимальное количество итераций

int i1Min)   // метод одномерного поиска

{

int k=0;     // задаём счётчик числа итераций

CMatrix x_prev(x), // предыдущее значение

d(x),     // ускоряющее направление

p(x);     // направление поиска

// переопределяем массив  значений х

// при пошаговом поиске  и задаём

// значение начальной  точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);

do

{

x_prev = x;       // сохраняем точку

for(int i=1; i<=x.getSizeRow(); i++)

{          // выполняем серию одномерных

p[i] = 1;      // поисков вдоль координатных осей

FindAlpha(x,p,e,i1Min);  // находим коэффициент удлинения вектора

x = x + p*alpha;    // спускаемся в следующую точку х

p[i] = 0;

}

d = x - x_prev;  // определяем ускоряющее направление

k++;      // увеличиваем счётчик итераций

MASSIV.insertCol(x); // добавляем новое значение х в массив

}

while(norma(d)>e && norma(df(x))>e && k<*max_step); // комбинированный КОП

 

*max_step=k;  // возвращаем количество итераций

return x;   // возвращаем найденный минимум

}

 

// Метод Гаусса-Зейделя

 

CMatrix CMETODI::GaussZeydel(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step,  // максимальное количество итераций

int i1Min)   // метод одномерного поиска

{

int k=0;     // задаём счётчик числа итераций

CMatrix x_prev(x), // предыдущее значение

d(x),     // ускоряющее направление

p(x);     // направление поиска

// переопределяем массив  значений х

// при пошаговом поиске  и задаём

// значение начальной  точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);

do

{

x_prev = x;   // сохраняем точку

for(int i=1; i<=x.getSizeRow(); i++)

{          // выполняем серию одномерных

p[i] = df(x)[i];    // поисков вдоль производной

FindAlpha(x,p,e,i1Min);  // находим коэффициент удлинения вектора

x = x + p*alpha;    // спускаемся в следующую точку х

p[i] = 0;

}

d = x - x_prev;     // определяем ускоряющее направление

k++;         // увеличиваем счётчик итераций

MASSIV.insertCol(x);    // добавляем новое значение х в массив

}

while(norma(d)>e && norma(df(x))>e && k<*max_step); // комбинированный КОП

 

*max_step=k;  // возвращаем количество итераций

return x;   // возвращаем найденный минимум

}

 

// Метод Хука-Дживса

 

CMatrix CMETODI::HookJeeves(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step)  // максимальное количество итераций

{

   CMatrix h(x),  // шаг поиска в виде матрицы

b(x),    // базовая точка

c, q;    // вспомогательные матрицы

// переопределяем массив  значений х

// при пошаговом поиске и задаём

// значение начальной  точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);

 

for(int i=1; i<=h.getSizeRow(); i++)

h[i]=1;     // задаём начальный шаг

 

int n=x.getSizeRow(), // количество строк

is_sample=0,   // флаг для следующенго поиска

k=0;      // задаём счётчик числа итераций

 

   while(norma(h)>e && k<*max_step)  // проверяем стандартный КОП

   {

      // выполняем  исследующий поиск

      int not_found=1;   // флаг на окончание поиска

     

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

      {

double f_x=f(x);  // находим значение производной

c=x;      // сохраняем точку

c[i]+=h[i];    // шаг в положительном направлении i-ой коорд.

if(f(c)<=f_x)   // если нашли подходящую точку

{

x=c;     // сохраняем точку

not_found=0;  // устанавливаем флаг в 0

}

else      // если не нашли подходящую точку

{

c[i]-=2*h[i];     // шаг  в отрицательном направлении  i-ой корд.

if(f(c)<f_x)

{

x=c;    // сохраняем точку

not_found=0; // устанавливаем флаг в 0

}

}

//k++;

      }

 

      if(is_sample)    // проверяем необходимость

      {        // следующего исследующего поиска

if(not_found || !(f(x)<f(q)))

{

// возвращаемся к базовой  точке

x=q;

b=q;

is_sample=0;

continue;

}

else

{

// запоминаем новую  базовую точку

b=q;

}

      }

      else

      {

if(not_found)

{

// если исследующий  поиск закончился неудачей - уменьшаем  шаг

h/=10; // (здесь beta = 10)

continue;

}

      }

 

      // выполняем  ускоряющий поиск

      q=x;

x=x*2-b;

      is_sample=1;

k++;      // увеличиваем счётчик итераций

 

MASSIV.insertCol(x); // добавляем новое значение х в массив

   }

 

MASSIV.insertCol(x); // добавляем новое значение х в массив

k++;      // увеличиваем счётчик итераций

 

*max_step=k;   // возвращаем количество итераций

   return x;    // возвращаем найденный минимум

}

 

// Обобщённый метод  Ньютона

 

CMatrix CMETODI::Newton_Ob(

CMatrix x,   // начальная точка

double e,   // погрешность поиска

int* max_step,  // максимальное количество итераций

int i1Min)   // метод одномерного поиска

{

int k=0;    // задаём счётчик числа итераций

 

// переопределяем массив  значений х

// при пошаговом поиске  и задаём

// значение начальной точки

MASSIV.setSize(x.getSizeRow(),x.getSizeCol());

MASSIV.setCol(1,x);  

 

if(norma(df(x))<e) // дополнительный КОП:

{       // если х0 - точка

*max_step=0;  // минимума, то завершить

return x;   // поиск

}

 

CMatrix x0(x),   // предыдущая точка

x1,     // текущая точка

p;      // направление поиска

  

for(k=0; k<*max_step; k++)   // выполняем поиск в

   {           // соответствии с методом

if(norma(df(x0))<e)    // проверка на окончание поиска