Курсовая работа на тему: Освоение решения типовой задачи оптимизации поисковым методом Хука-Дживса

Введение

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной Xj , j = 1, 2, . . . , n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f(x) в базисной точке b1, с целью получения сведений о локальном поведении функции f(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1 находится следующим образом:

1. Вычисляется значение функции f(b1) в базисной точке b1.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f(b1 + h1e1), где е1 - единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1. В противном случае вычисляется значение функции f(b1 - h1e1), и если ее значение уменьшилось, то b1 заменяем на b1 - h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f(b1 + h2e2), и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

3. Если b2 = b1, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b2 ≠ b1, то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b2 в направлении b2 - b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

Р1= b1 + 2 (b2 - b1)

В общем случае

Рi = bi + 2 (bi+1 - bi).

2. Затем исследование следует продолжать вокруг точки Р1 (Рi).

3. Если наименьшее значение на шаге В.2 меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг В.1. В противном случае не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Ниже приведена блок-схема данного метода (рисунок 1).

Рисунок 1 - Блок-схема поискового метода Хука-Дживса.

Оглавление

- Освоение решения типовой задачи оптимизации поисковым методом Хука-Дживса

- Теоретическая часть

- Практическая часть

- Анализ и модификация метода решения реальной задачи оптимизации на основе конкретной научной публикации Список литературы

Список литературы

- Банди. "Методы оптимизации". Поисковый метод Хука-Дживса.

- Журнал "Современные технологии автоматизации", 4, 2000 г., с.