Исследование алгоритмов одномерной оптимизации. Исследование комбинаторного метода, ветвей и границ: Методические указания к лабораторным работам, страница 2

Для тоге чтобы начать поиск по методу Фибоначчи, необходимо определить полокение первых двух точек проведения испытаний. Э?" точяи располагаются симметрично внутри начального интервала неопре­деленности на расстоянии /<д    от соответствующих концов этого ин­тервала. Полагая в выражении (5) К =- П-2. , получаем

, ^ =1 F^L^ - e-Fn-з 3=      ^ .    ^

^ ^f1"1 + с Fri-i F"-i - FnFij:3 ^ Fri-1 ^ (~_U-^ Fn              Fn            Fn      Fn

2.4. Метод "золотого сечения"

Для начала поиска по методу Фибоначчи необходимо предваритель­но задаться числом экспериментов П • исходя из допустимого значе­ния интервала неопределенности в конце поиска. От этого недостатка свободен метод "золотого сечения", который почти столь же э^ективен, как и метод Фибоначчи. Здесь так же, как и f последнем методе, точ­ка, выбираемая внутри интервала неопреде^чнности для проведения эк­сперимента на очередном шаге, располагается синыатрично цтнооитель-но уже находящейся там точки, оставшейся от предыдущих экоперимен-.. тов. Поэтов здесь для трех соседних интервалов неопределннности так-'" же справедливо соотношение (3). Однако в методе "золотого сечения" не используется соотношение (2), которое зависит от /7  . вместо этого- выдерживается постоянным, равным Т , отношение длин пос­ледовательных интервалов, т.е.

^-' = ^ -^.                            (8)

"/       ^

Разделав (3) на   ^л-f    и приняв во внимание, что согласно (8) L.-i/L.^, sT4 , имеем

r^^^i,                   ^

откуда

Г= (I + /?)/2 ^ 1,618033989.         (10) Тогда

^/z/^ =^^ ч-1-/^^ =^J я T-»-

Следовательно, ^/Л„ = t"''1 , т.е.

1-п = ^^Т ^ '-T^-l ' .                   ^^

':зким образом, в методе "золотого сечения" начальный отрезок делится по "правилу золотого сечения" (8), (10) а первые два экспе­римента располагаются симметрично на расстояния  св 0,618 . от соот­ветствующих концов интервала. По результатам этих двух экоперимеа- . тов сохраняется один из интервалов, в котором расположен оставшийся эксперимент. Симметрично ему располагается следующий эксперимент я так далее.

Можно показать, что окончательный интервал неопределенности в дараом методе при достаточно больших П   всего лишь на, 17 % боль-га, чем в методе Фибоначчи. Можно показать также, что при .больших /7    оба метода начинаются практически из одной и той же точки.

3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ      '       '

3.1. Расчетная часть

3.1.1. Построить.блок-схемы алгоритмов дихотомического деления, Фибоначчи, "золотого сечения".

3.1.2. Выбрать из таблицы функций, приведенной в прилскенид^одяу ^нкцщо (по указанию преподавателя) и определить для нее начальный интервал поиска локального минимума.

ЗЛ.З. Для алгоритма Фибоначчи определять количество эксперимен­тов, позволяющее уменьшить интервал неопределенности в 1000 раз.

3.1.4. Осуществить по 2-3 итерации поиска экстремума заданной функции каждым из рассматриваемых методов.

3.2. Экспериментальная часть

3.2Л. Подготовить ЭВМ к работе.       ' '

3.2.2. С помощью процедуры  P01SK    вызвать программу ла­бораторной работы а в диалоговом режиме ввести необходимую информа­цию.

3.2.3. Получить решение задачи тремя методами. Получить лио-

Т1ШГИ рРШвВИЙ.

4. ССДЕРаАНИЕ ОТЧЕТА ПО РАБОТЕ

4.1. Исходное задание на исследование.

4.2. Результаты, полученные в ini.S.I^-^.i.T расчетной час­тя.

4.3. Результаты машинного решения и их анализ.

5. КОНТРОЛЬНЫЕ «ОПРОСЫ

^.1. и1есто'задачи одномерного поиска в общей задаче оптимиза-•      аии.

5.2. Сущность методов дихотомического деления, Фибоначчи, "золотого сечения".

5.3. Сравнительные характеристики исследуемых алгоритмов. .

5.4. Использовать метод Фибоначчи для поиски мшшуиа функции 2д^ - е х  в интервала (0,1) при пятикратном вычислении функции.

5.5. Для задача из п. 5.4 использовать метод ''золотого сечения".

Библиографический список

1. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1976.

2. Бонда Б. Методы оптимизации. Вводный курс.   м.: Радао и связь, 1988.

          ПРИЛСВШНИЕ

          ТАБЛИЦ ФУНКЦИЙ п/п Название

1        F(x)= x^^^^x-i_________________

2        Р(х} = J-a^-^a: +2.

3        F(x.] ^^(x-^-i __________________

4        ^J = .r^J-a:^____________________

5        F(x) ^ tj^____________________________

б        /^T-xJ = r-r^^r-^J3- . __

7        P(x} = X+^e _________________________

8        /'(^ = гх1-- е^

9        у-^ ^(X^^X^f)3- _______

~io     FW = е-^^___________________

и        р(х)= ^е3^ ________\

V        FCx) ^з^-^х^бО^-РОУ

 Лабораторная работа № 2

ИССЛЕДОВАНИЕ ПОНСКОВЖ МЕТОДОВ ОПТИМГ13АШН КОНСТ1У1{!№1 ЭВА

1. UEttb РАБОТЫ               . .

Целью настоящей работы являются изучение и анализ поисковых методов: покоординатного спуска (МЛС) я сопряьюнных направленна (МОН),. используемые для решения задач пара^етрическо!' оптимиза­ции конструкций и технологических процессов произЕоп^таа ЭЗА.

2. ТЕОРЕТИЧЕСЖАЯ ЧАСТЬ

2.1. Введение

Задачи параметрического синтеза, связанные и выборов таких параметров, которые обеспечивают оптимизаций некоторого критерия качества конструкции или технологического процесса, относятся в общем случае к задачам нелинейного nporpawit; ..iBaii'M няца:

найти min F(U)                           (I)

при ограничениях

_^(U)^ 0, /,2,.-.,/7.      i   (2)

Здесь £/ - /7-мерный вектор управляемых парауетров конст­рукции, F(U) - целевая функция (критерий оптимальности).

В настоящей лабораторной работе изучаются методы поиска без­условного экстремума, т.е. методы поиска экстремума в задачах, в - которых отсутствуют ограничения (2). Подобные задачи представля­ют самостоятельный интерес, т.к. в ряде случаев пеленая функция мокет быть построена так, что она пана учитывает все ограничения fl] .Кроме того, большинство алгоритмов решения задач с ограни­чениями (задач на условный экстремум) включают минимизацию без ограничений в качестве основной поэтапной процедуры.

Суть любого алгоритма поиска состоит в определении такой последовательности {^к\ вектороа управляемых параметров И. U^, ^ц которые удовлетворяэт уолошии

F(U^>F(U,)>...> F(Un).        (3)

Различные алгоритмы поиска от.лича.ггся чгуг от Дгугз лишь ви-бором направления поиска и длтаы шага ^дола sroi'o напр.^влечия. :) этих методах последовательность {^/<?    л"1П|;'!.чется ;io if-w^w

^/= ^•+rJ^   К=0,/.;;,..,,    (•I)

где  S^ - вектор, определяющий        направление потека, У   - длина 'лага вдоль этого направления.

Г) зависимости от максимального порядка производных миними­зируемое мучкют, используемых. для определения яапрввления по­яска sk > "етоды брзусловчой минимизации разделяются на мето-цъ1 нулевого, первого и второго порядка.