Обоснование и описание методов оптимизации

Поиск оптимальных условий

Курсовая работа по дисциплине

«Планирование и организация эксперимента»

ЯГТУ 200503.65-11 КР

Нормконтролер Работу выполнил

профессор, д. т. н. студентка гр. ЭСК-32

____Ю.В. Васильков ____ Д.И.Логинова

«__»_________2011 «__»_________ 2011

ЗАДАНИЕ

На курсовое проектирование

по дисциплине "Планирование и организация экспериментов"

Задача проекта: организовать "экспериментальные" исследования некоторого объекта с целью поиска минимального значения выходной величины Y. Объект имеет входные управляющие воздействия X₁, X₂, X₃, …, X_n.

X₁

X₂ Объект исследования Y

X_n

Имеются заданные начальные условия. Необходимо проводя экстремальные "эксперименты" на программном эмуляторе объекта получить такие режимы его работы, при которых достигается минимальное значение величины Y. При этом следует построить и обосновать стратегию "экспериментальных" работ, выбрать и обосновать применяемые методы (2 различных).

В записке к проекту привести обоснование и описание стратегии организации экспериментальных работ, используемых методов, "экспериментальные" результаты (т.е. полученные путем расчетов по программному имитатору объекта) включая промежуточные, результаты их статистической обработки, принимаемые в процессе экспериментирования решения, их обоснования, полученные оптимальные результаты X₁^*, X₂^*, X₃^*, …, X_n^*, Y^*.

Обосновать полученное решение с точки зрения: локальный найден минимум или глобальный?

Необходимо подобрать реальный процесс, для которого могла бы быть поставлена аналогичная содержательная задача, и описать его с обоснованием постановки задачи.

Содержание

Введение……………………………………………………………………….4

1. Обоснование и описание методов оптимизации………………………6

1.1 Метод Гаусса-Зайделя…………………………………………………6

1.2 Метод Наказания случайностью………………………………………7

2. Проведение экспериментов………………………………………………..9

2.1 Метод Гаусса-Зайделя …………………………………………………..9

2.2 Метод наказания случайностью………………………………………...15

3. Подбор реального процесса……………………………………………….26

4. Список используемой литературы………………………………………29

Введение

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

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

R( … )→ (1)

R – критерий оптимальности

Решением этой задачи называется такой ( , … ), при котором R( )= ( ), R( )≥R(x) для любого x.

Методы оптимизации– поиска экстремума функции (в практических задачах –критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике. Количественная оценка оптимизируемого качества объекта обычно называется критерием оптимальности. Критерий оптимизации y обычно задается. Этот критерий должен удовлетворять следующим основным требованиям: 1) экстремум величины R должен характеризовать наилучшее состояние объекта в выбранном смысле; 2) Критерий должен выражаться количественно. Если критерий не выражается количественно, то можно ввести рейтинговые, бальные, экспертные оценки, которые количественно выражают лучшее или худшее; 3) По возможности критерий оптимальности должен выражаться одним числом, хотя на практике часто его выражают совокупностью чисел, т.е. разными частными критериями.

Решение задачи оптимизации осуществляют с помощью экспериментального поиска. Для этого сначала осуществляют изучение характера поверхности отклика в районе первоначально выбранной точки факторного пространства (с помощью специально спланированных «пробных» опытов). Затем совершают «рабочее» движение в сторону экстремума, причем направление движения определяют по результатам пробных опытов. Такое движение может осуществляться путем ряда этапов, которые могут объединяться в «циклы».

После выхода в район экстремума оптимальную точку можно уточнить одним из двух способов: 1) постановкой дополнительных, особым образом спланированных опытов; 2) получением математической модели второго или более высокого порядка и последующим решением системы уравнений.

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

Обоснование и описание методов оптимизации

Существует достаточно большое количество численных методов оптимизации. Рассмотрим два метода поисковой оптимизации: «Метод Гауса-Зайделя» и «Метод наказанием случайностью». Первый метод относится к многомерной безградиентной оптимизации, а второй метод аналог метода наискорейшего спуска. Эти методы различаются способами постановки пробных опытов и определения направления движения к экстремуму, а также способами организации самого рабочего движения к экстремуму.

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

Метод Гаусса-Зайделя

Методсводится к поиску экстремума поочередно по каждой переменной отдельно. Алгоритм выражается формулой: x^j+1= x^j+f(R (x^j)).

Пусть имеется некоторая начальная точка x⁰ и R(x₁,x₂). Сначала будем искать по первой переменной x₁, при этом фиксируя значение остальных переменных и начинаем менять x₁. Смотрим результат. Найденную точку с наилучшим значением по первой переменной фиксируем и начинаем менять вторую переменную x₂. Найденная наилучшая точка x₁ завершает первый цикл. Последовательный поиск экстремума по каждой переменной не приводит нас в общем случае, к экстремуму функции, поэтому после завершения первого цикла наступает второй, третий и т. д. Точность нахождения экстремума зависит от величины шага по переменной. Его выбирают так, чтобы:

- уверенно почувствовать изменение функции при наличии помех;

- общее число экстремумов не слишком большое;

- далеко не проскакивать оптимум по направлению.

Основная особенность рассматриваемого метода - отсутствие вычисления градиента критерия оптимальности. Ряд методов прямого поиска базируется на последовательном применении одномерного поиска по переменным или по другим задаваемым направлениям, что облегчает их алгоритмизацию и применение.

Метод обладает низкой эффективностью в овражных функциях, может застревать в «ловушках», особенно при сравнительно больших шагах h при поиске оптимума по каждой переменной, очень чувствителен и к выбору системы координат. Метод прост в реализации. На эффективность метода влияет порядок чередования переменных.

Достоинства метода:

• очевидная простота стратегии и наглядность;

• высокая помехозащищенность в смысле выбора направления движения.

Недостатки метода:

• при большом числе влияющих n факторов путь к главному экстремуму оказывается обычно долгим;

• в условиях крупного промышленного производства оказывается трудным застабилизировать n-1 факторов на длительное время;

• если поверхность отклика имеет сложную форму (узкие гребни, овраги и т.п.), то использование метода может привести к ложному ответу на вопрос о месте расположения экстремума;

• метод не дает информации о взаимодействиях факторов.

Условием окончания поиска является малость изменения критерия оптимальности за один цикл или невозможность улучшения критерия оптимальности ни по одной из переменных.

1.2 Метод с наказанием случайностью

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

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

Достоинства метода:

· очевидная простота;

· выбор случайного вектора для выполнения пробного опыта не зависит от случайных помех и формы поверхности отклика;

· позволяет находить глобальный экстремум;

· эффективен в задачах высокой размерности и вдали от оптимума, позволяет в среднем быстрее выходить в район оптимума.

Недостатки метода:

· в общем случае направление рабочих шагов не является оптимальным;

· малая эффективность в условиях пологих поверхностей отклика.

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