Материал: 1785
оптимальности называют овражным в своей области определения, если в этой области имеют место слабые изменения критерия по одним направлениям и значительные изменения по другим.
Одной из особенностей задач оптимизации, возникающих при автоматизированном проектировании, является высокая вычислительная
сложность и сложность программной реализации. Это обусловлено тем, |
|
что при решении задач оптимизации в современных САЕ-системах |
|
С |
|
широко используют метод суррогатных моделей (мета-функций), которые |
|
представляют собой аппроксимации целевых функций полиномами, |
|
радиально-баз сными |
другими функциями [1]. |
Задачи |
|
Методы одномерной оптимизации |
|
опт м зац |
, в которых критерий оптимальности задан |
функцией одной переменной и методы их решения часто встречаются в |
|
|
большого |
инженерной практ ке, а также используются при исследовании подзадач |
|
многомерной опт м зац и. Поэтому анализ задач такого типа занимает |
|
центральное место в математическом обеспечении САПР. Это обусловило |
|
разработку |
ч сла методов и их модификаций. Математическая |
|
А |
формулировка задач одномерной оптимизации часто эквивалентна задаче |
|
отыскания экстремума функции одной переменной. Вследствие этого для |
|
решения таких задач могут ыть использованы методы математического |
|
анализа. Но часто на практике при математическом моделировании могут |
|||
получаться функции трудоемкие для аналитического решения, поэтому |
|||
|
|
Д |
|
актуальным является использование численных методов одномерной |
|||
оптимизации и их реализация в системах автоматизированного |
|||
проектирования [4]. |
|
|
|
К наиболее изученным методам одномерной оптимизации можно |
|||
отнести следующие: |
|
И |
|
• |
метод сканирования; |
|
|
|
|
||
• |
метод локализации экстремума; |
|
|
• |
метод золотого сечения; |
|
|
• |
метод с использованием чисел Фибоначчи. |
||
Метод сканирования
Идея этого метода заключается в том, что весь рассматриваемый интервал xmin xmax разбивается на n одинаковых подынтервалов. На концах интервала и в точках его разбиения вычисляются значения целевой функции [4]. Затем производится сравнение полученных величин друг с другом и из них выбирается наибольшее значение, если определяется max, и наименьшее, если min.
16
F(x)
С |
|
|
|
F(xmin) |
|
|
|
Геометрическая |
x |
||
|
|
xmin |
|
|
бА |
|
|
Р сунок 5. |
интерпретация метода сканирования |
|
|
Точность по ска решения методом сканирования равна подынтервалу разбиения [4].
Метод локализации экстремума
На первом этапе решения весь диапазон изменения неизвестной |
|
Деление |
|
разбивается на крупные подынтервалы. Затем вычисляют значение |
|
целевой функции на концах рассматриваемого отрезка и в точках его |
|
разбиения и выбирают из них оптимальное, т.е. наибольшее при поиске |
|
max и наименьшее при определении min. |
алее оптимальную точку |
окружают прилегающими подынтервалами |
полученный новый интервал |
разбивают вновь на крупные отрезки. |
И |
отрезков повторяется до |
|
тех пор, пока на очередном шаге длина подынтервала не станет меньше или равной заданной точности [4].
17
F(x)
С |
|
|
|
F(xmin) |
|
|
|
Рисунок |
xmin x2 |
x |
|
|
x1 |
||
бА |
|
||
6. Геометр ческая интерпретация метода локализации экстремума
Метод локал зац экстремума при равных условиях обеспечивает более высокую относ тельную точность поиска по сравнению с методом сканирования. Практически наилучшие результаты при использовании метода локализации экстремума получаются, если исходный отрезок делится на четыре равных части, а затем прилегающие к экстремальной точке подынтервалы делятся пополам [4].
Метод золотого сечения
В основе этого метода лежит геометрическое соотношение или закон золотого сечения [4]. Если весь отрезок обозначить через а,большую его часть - b, меньшую - c, то закон золотого сечения устанавливает
следующую связь: |
Д |
|||||
|
a |
|
b |
|
И |
|
|
|
c |
||||
|
b |
|
||||
или |
||||||
b2 |
a c |
|||||
Определим, при каких условиях возможно выполнение соотношения золотого сечения. Для этого рассмотрим отрезок единичной длины
(рис. 7).
18
С |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
Р сунок 7. Деление отрезка по закону золотого сечения |
|||||||||||
Большую его часть обозначим через Z, а меньшую (1-Z); исходя из |
||||||||||||||
имеем |
|
|
|
|
|
|
|
|
||||||
этого |
|
согласно соотношению: |
|
|
|
|
|
|
||||||
|
|
|
Z2 |
|
1 Z |
|
|
|
|
|
|
|||
|
|
|
бАh b a |
|||||||||||
|
|
|
Z2 |
Z 1 0 |
|
|
|
|
||||||
|
|
|
Z |
|
|
|
1 |
|
|
1 |
|
4 |
|
|
|
|
1,2 |
|
|
|
|
2 |
|
|
|
|
|
||
|
|
|
Z 0,618 |
|
|
|
|
|
|
|||||
Сущность метода золотого сечения состоит в том, что |
||||||||||||||
рассматриваемый отрезок |
делится |
|
по закону геометрического |
|||||||||||
|
|
|
|
|
|
|
|
Д |
||||||
соотношения, который называется золотым сечением [4]. |
||||||||||||||
|
|
|
x1 |
a 0,618 h |
И |
|||||||||
|
|
|
x2 |
|
a 0,6182 h |
|||||||||
|
|
F(x) |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1 |
|
|
|
F2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
|
|
x2 |
|
|
|
|
|
x |
|
|
|
Рисунок 8. Геометрическая интерпретация метода золотого сечения |
||||||||||||
19
Метод золотого сечения обеспечивает более высокую точность поиска по сравнению с методом локализации экстремума.
|
|
Метод Фибоначчи |
|
|
Последовательность |
|
чисел, |
подчиняющаяся |
рекуррентному |
соотношению |
|
|
|
|
С |
Fn |
Fn 1 Fn 2 |
|
|
|
|
|||
называется последовательностью чисел Фибоначчи. В этой последовательности каждое последующее число Фибоначчи равно сумме двухПрипредыдущ х ч сел. этом нулевое и первое число Фибоначчи равно ед н це [4].
В табл.1 пр вод тся последовательность чисел Фибоначчи для
некоторого д |
апазона. |
|
|
|
|
|
|
|
|
|
|
|
|||||
x1 a (b бАa) |
|
|
Таблица 1 |
||||||||||||||
|
|
|
|
|
Последовательность чисел Фибоначчи |
|
|
|
|||||||||
|
n |
|
0 |
1 |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
… |
|
|
Fn |
|
1 |
1 |
|
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
… |
|
Алгоритм
1. Даны начальные границы отрезка а, b, и число итераций n.
Находим точки разбиения отрезка [a,b] |
||||
|
|
Fn 2 |
Д |
|
|
|
|
||
|
|
|
Fn |
И |
x2 |
a (b a) |
|
Fn 1 |
|
|
|
|||
Fn
f (x1), f (x2) значения функции в точках х1,х2 Fn ,Fn 1,Fn 2 числа Фибоначчи
2. Если f(x1)>f(x2), то
а=x1, x1=x2, x2=b-(x1-a), f(x1)=f(x2), вычислить f(x2)
иначе
b=x2, x2=x1, x1=a+(b-x2), f(x2)=f(x1), вычислить f(x1)
20