Методы Хука-Дживса - (реферат)

p>(*** (следует за последним комментарием) ***) (*** и провести исследование вокруг новой базисной точки ***) j: =1;

    goto 0;
    5: k: =k/10;
    writeln('Уменьшить длину шага');
    if k    (*** Если поиск незакончен, то произвести новое ***)
    (*** исследование вокруг новой базисной точки ***)
    j: =1;
    goto 0;
    (*** Поиск по образцу ***)
    6: for i: =1 to n do
    begin
    p[i]: =2*y[i]-b[i];
    b[i]: =y[i];
    x[i]: =p[i];
    y[i]: =x[i];
    end;
    calculate;
    fb: =fi;
    ps: =1;
    bs: =0;
    fi: =z;
    writeln('Поиск по образцу', ' ', z: 2: 3);
    for i: =1 to n do
    writeln(x[i]: 2: 3);
    (*** После этого произвести исследование вокруг ***)
    (*** последней точки образца ***)
    j: =1;
    goto 0;
    7: writeln('Минимум найден');
    for i: =1 to n do
    writeln('x(', i, ')=', p[i]: 2: 3);
    writeln;
    writeln('Минимум функции равен', ' ', fb: 2: 3);
    writeln('Количество вычислений функции равно', ' ', fe);
    repeat until keypressed;
    end.

Приведенная выше программа реализует описанную процедуру. Одной или двух точек бывает недостаточно для определения начальной точки. Первая точка всегда должна выбираться осмотрительно. ЭВМ работает только с ограниченной точностью, и ошибки могут накапливаться в процессе сложных вычислений, особенно если шаг имеет “неудобную” длину. (Обычно мы будем избегать “неудобной” длины, но программа должна быть работоспособна и в таких ситуациях. ) Поэтому в строке , где выясняется вопрос об изменении базисной точки, мы избегаем уменьшения длины шага из-за накапливания ошибки введением длины шага, равной. Мы отслеживаем, где производится исследование –в базисной точке (В5 = 1, Р5 = 0) или в точке образца (В5 = 0, Р5 = 1). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна. В приведенной программе минимальная длина шага равна , но она может быть изменена . Для контроля за выполнением процедуры в программу введена печать промежуточных результатов. Для увеличения скорости счета могут быть удалены строки вывода подсказок и пояснений. Процедура calculate вычисляет значение минимизируемой функции , в нашем случае : f (x1, x2) = 3x12+4x1x2+5x22 , при ограничениях x1 x2 x1+x2.

Минимум, равный 44, достигается в точке (3; 1) при ограничении x1+x2=4. Для начальной точки (4; 3) и при длине шага , равной единице , программой успешно решена задача минимизации .

    Ниже приведена распечатка результата работы программы :
    Модифицированный метод Хука-Дживса
    (при наличииограничений)
    Введите число переменных
    2
    Введите начальную точку х1, х2, …, хN
    4
    3
    Введите длину шага
    1
    Начальное значение функции 141. 000
    4. 000
    3. 000
    Пробный шаг 108. 000
    3. 000
    3. 000
    Пробный шаг 71. 000
    3. 000
    2. 000
    Поиск по образцу 1. 70000000000001566Е+0038
    2. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Поиск по образцу 1. 70000000000001566Е+0038
    3. 000
    0. 000
    Пробный шаг 48. 000
    4. 000
    0. 000
    Пробный шаг 48. 000
    4. 000
    0. 000
    Замена базисной точки 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Пробный шаг 44. 000
    3. 000
    1. 000
    Пробный шаг 44. 000
    3. 000
    1. 000
    Уменьшить длину шага
    Минимум найден
    х(1) = 3. 000
    х(2) = 1. 000
    Минимум функции равен 44. 000
    Количество вычислений равно 74

Для начальной точки (3; 4) и длины шага , равной единице , программой также успешно решена задача минимизации .

Для начальной точки (5; 6) и длины шага , равной единице , задача не решена , т. к. программа остановилась в точке (1; 3) , т. е. на активном ограничении , и выдала неверный результат .

    Распечатка результата работы программы приведена ниже :
    Модифицированный метод Хука-Дживса
    (при наличииограничений)
    Введите число переменных
    2
    Введите начальную точку х1, х2, …, хN
    5
    6
    Введите длину шага
    1
    Начальное значение функции 375. 000
    5. 000
    6. 000
    Пробный шаг 324. 000
    4. 000
    6. 000
    Пробный шаг 253. 000
    4. 000
    5. 000
    Поиск по образцу 155. 000
    3. 000
    4. 000
    Пробный шаг 124. 000
    2. 000
    4. 000
    Пробный шаг 81. 000
    2. 000
    3. 000
    Поиск по образцу 1. 70000000000001566Е+0038
    0. 000
    1. 000
    Пробный шаг 1. 70000000000001566Е+0038
    0. 000
    1. 000
    Пробный шаг 1. 70000000000001566Е+0038
    0. 000
    1. 000
    Замена базисной точки 81. 000
    2. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Поиск по образцу 1. 70000000000001566Е+0038
    0. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Замена базисной точки 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Пробный шаг 60. 000
    1. 000
    3. 000
    Пробный шаг 60. 000
    1. 000
    3. 000
    Уменьшить длину шага
    Минимум найден
    х(1) = 1. 000
    х(2) = 3. 000
    Минимум функции равен 60. 000
    Количество вычислений равно 89

Аналогичные неутешительные результаты были получены для начальной точки (5; 6) и длины шага , равной 0. 5 . Неверное решение было найдено в точке (1. 5; 2. 5) . Для начальной точки (4; 3) и длины шага , равной 0. 5 , программа работала нормально , но было получено неверное решение в точке (2. 5; 1. 5) .

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

    Литература:
    Б. Банди “Методы оптимизации”

Р. Хук , Т. А. Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с. , 1961 .

Страницы: 1, 2