Метод оптимизации для поиска плавающего состояния объекта

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

Функция, которую я использую, вычисляет смещенный объем и центр плавучести тела с учетом опускания, крена и дифферента. Где уклон — это единица длины, а крен/дифферент — это угол, ограниченный значением от -90 до 90.

Иллюстрация трех переменных

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

Я реализовал это как нелинейную задачу поиска корня Ньютона-Рафсона с 3 переменными (провал, обрезка, крен) и 3 уравнениями. Этот метод работает, но требует хороших начальных предположений. Поэтому я надеюсь найти лучший подход для этого или хороший метод для поиска начальных значений.

Ниже приведен код алгоритма Ньютона и Якобиана, используемого для итерации Ньютона-Рафсона. Функция Volume принимает параметры снижения, крена и дифферента. И возвращает объем, и координаты центра плавучести.

Я также включил алгоритмы maxabs и GSolve2, я полагаю, что они взяты из числовых рецептов.

void jacobian(float x[], float weight, float vcg, float tcg, float lcg, float jac[][3], float f0[]) {
    float h = 0.0001f;
    float temp;
    float j_volume, j_vcb, j_lcb, j_tcb;
    float f1[3];

    volume(x[0], x[1], x[2], j_volume, j_lcb, j_vcb, j_tcb);
    f0[0] = j_volume-weight;
    f0[1] = j_tcb-tcg;
    f0[2] = j_lcb-lcg;

    for (int i=0;i<3;i++) {
        temp = x[i];
        x[i] = temp + h;
        volume(x[0], x[1], x[2], j_volume, j_lcb, j_vcb, j_tcb);

        f1[0] = j_volume-weight;
        f1[1] = j_tcb-tcg;
        f1[2] = j_lcb-lcg;
        x[i] = temp;

        jac[0][i] = (f1[0]-f0[0])/h;
        jac[1][i] = (f1[1]-f0[1])/h;
        jac[2][i] = (f1[2]-f0[2])/h;
    }
}


void newton(float weight, float vcg, float tcg, float lcg, float &sinkage, float &heel, float &trim) {
    float x[3] = {10,1,1};

    float accuracy = 0.000001f;
    int ntryes = 30;
    int i = 0;
    float jac[3][3];
    float max;
    float f0[3];
    float gauss_f0[3];

    while (i < ntryes) {
        jacobian(x, weight, vcg, tcg, lcg, jac, f0);

        if (sqrt((f0[0]*f0[0]+f0[1]*f0[1]+f0[2]*f0[2])/2) < accuracy) {
            break;
        }

        gauss_f0[0] = -f0[0];
        gauss_f0[1] = -f0[1];
        gauss_f0[2] = -f0[2];

        GSolve2(jac, 3, gauss_f0);

        x[0] = x[0]+gauss_f0[0];
        x[1] = x[1]+gauss_f0[1];
        x[2] = x[2]+gauss_f0[2];

        // absmax(x) - Return absolute max value from an array
        max = absmax(x);
        if (max < 1) max = 1;

        if (sqrt((gauss_f0[0]*gauss_f0[0]+gauss_f0[1]*gauss_f0[1]+gauss_f0[2]*gauss_f0[2])) < accuracy*max) {
            x[0]=x2[0];
            x[1]=x2[1];
            x[2]=x2[2];
            break;
        }

        i++;
    }

    sinkage = x[0];
    heel = x[1];
    trim = x[2];
}

int GSolve2(float a[][3],int n,float b[]) {
    float x,sum,max,temp;
    int i,j,k,p,m,pos;

    int nn = n-1; 

    for (k=0;k<=n-1;k++)
    {
        /* pivot*/
        max=fabs(a[k][k]);
        pos=k;


        for (p=k;p<n;p++){
            if (max < fabs(a[p][k])){
                max=fabs(a[p][k]);
                pos=p;
            }
        }

        if (ABS(a[k][pos]) < EPS) {
            writeLog("Matrix is singular");
            break;
        }

        if (pos != k) {
            for(m=k;m<n;m++){
                temp=a[pos][m];
                a[pos][m]=a[k][m];
                a[k][m]=temp;
            }
        }

        /*   convert to upper triangular form */
        if ( fabs(a[k][k])>=1.e-6)
        {
            for (i=k+1;i<n;i++)
            {
            x = a[i][k]/a[k][k];
            for (j=k+1;j<n;j++) a[i][j] = a[i][j] -a[k][j]*x;
            b[i] = b[i] - b[k]*x;
            }
        }
        else
        {
            writeLog("zero pivot found in line:%d",k);
            return 0;
       }
     }

/*   back substitution */
     b[nn] = b[nn] / a[nn][nn];
     for (i=n-2;i>=0;i--)
     {
        sum = b[i];
         for (j=i+1;j<n;j++) 
           sum = sum - a[i][j]*b[j];
        b[i] = sum/a[i][i];
     }
     return 0;
}

float absmax(float x[]) {
    int i = 1;
    int n = sizeof(x);
    float max = x[0];
    while (i < n) {
        if (max < x[i]) {
            max = x[i];
        }
        i++;
    }
    return max;
}

person user978281    schedule 27.01.2013    source источник
comment
Есть ли у вас доступ к решателю нелинейной оптимизации KNITRO (вы академик)? Есть опция мультизапуска. Вы можете попробовать это и посмотреть, как работает multistart, прежде чем запускать свой собственный метод.   -  person user327301    schedule 27.01.2013
comment
Я не академик, поэтому, к сожалению, у меня нет доступа к KNITRO.   -  person user978281    schedule 29.01.2013
comment
user978281 - Вы предоставили недостаточно подробностей, чтобы на ваш вопрос можно было ответить сколь-нибудь подробно. Можете ли вы привести пример кода? Если бы мы могли увидеть ваш нелинейный метод NR, было бы намного яснее, как можно реализовать оптимизацию.   -  person Mike Vella    schedule 30.01.2013
comment
@ user978281, поддерживаю комментарий Майка Веллы. Особенно, если вы назначаете вознаграждение за свой вопрос, вы должны указать в своем вопросе как можно больше соответствующих деталей.   -  person user327301    schedule 30.01.2013
comment
Обновлено примером кода, надеюсь, что это даст некоторые дополнительные сведения   -  person user978281    schedule 30.01.2013


Ответы (2)


Рассматривали ли вы некоторые методы стохастического поиска для нахождения начального значения и последующей точной настройки с помощью Ньютона Рафсона? Одна из возможностей — эволюционные вычисления, вы можете использовать пакет Inspyred. Для физической проблемы, во многом похожей на описанную вами, посмотрите на этот пример: http://inspyred.github.com/tutorial.html#lunar-explorer

person Mike Vella    schedule 27.01.2013

Как насчет использования демпфированной версии метода Ньютона? Вы можете довольно легко изменить свою реализацию, чтобы сделать это. Думайте о методе Ньютона как о поиске направления

d_k = f(x_k) / f'(x_k)

и обновление переменной

x_k+1 = x_k - L_k d_k

В обычном методе Ньютона L_k всегда равно 1, но это может привести к перерегулированию или недорегулированию. Итак, пусть ваш метод выбрал L_k. Предположим, что ваш метод обычно дает перерегулирование. Возможная стратегия состоит в том, чтобы взять наибольшее L_k в наборе {1,1/2,1/4,1/8,... L_min} такое, что условие

|f(x_k+1)| <= (1-L_k/2) |f(x_k)|

удовлетворяется (или L_min, если ни одно из значений не удовлетворяет этому критерию).

С теми же критериями другая возможная стратегия состоит в том, чтобы начать с L_0=1, и если критерии не выполняются, пробовать с L_0/2, пока это не сработает (или пока L_0 = L_min). Затем для L_1 начните с min(1, 2L_0) и сделайте то же самое. Затем начните с L_2=min(1, 2L_1) и так далее.

Кстати: вы уверены, что ваша проблема имеет единственное решение? Я предполагаю, что ответ на этот вопрос зависит от формы вашего объекта. Если у вас есть мяч для регби, есть один угол, который вы не можете исправить. Так что, если ваша форма близка к такому объекту, я не удивлюсь, что проблему трудно решить для этого угла.

person Dr_Sam    schedule 31.01.2013