Разработка программного модуля прямого и градиентного поиска

Размещено на http://www.allbest.ru/

Разработка программного модуля прямого и градиентного поиска



Оглавление

Аннотация

Введение

1. Постановка задачи

1.2 Структура разрабатываемой программы

1.3 Техническое задание на дипломное проектирование

1.4 Этапы разработки

1.5 Порядок сдачи программы

2. Теоретические основы проектирования и оптимизации

2.1 Процесс и этапы проектирования

2.2 Автоматизация процесса проектирования на основе методов оптимизации

2.3 Одномерная оптимизация

2.4 Общая характеристика методов многомерной оптимизации

2.5 Анализ методов прямого поиска

2.6 Анализ методов градиентного поиска

2.7 Программные и технические средства

3. Конструктивно-технологическая часть проекта. Разработка ПО

3.1 Функции разрабатываемого ПО и предъявляемые к нему требования

3.2 Структура программных средств разрабатываемой подсистемы

3.3 Разработка алгоритмов

4. Охрана труда. Обеспечение безопасности труда при эксплуатации электрооборудования

4.1 Основные понятия

4.2 Опасные и вредные факторы, возникающие при эксплуатации ЭВМ

4.3 Электробезопасность

4.4 Необходимость проведения защитного зануления

4.5 Принцип работы зануления

4.6 Устройство зануления

4.7 Расчет защитного зануления

4.8 Методы и средства защиты от статического электричества

5. Экологическая часть проекта. Влияние шума на производительность труда

5.1 Основные понятия шума

5.2 Влияние шума на организм человека

5.3 Нормирование шума

5.4 Средства и методы защиты от шума

6. Микроклимат в рабочей зоне

7. Решение задачи на ЭВМ. Пример использования программного обеспечения

Заключение

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



Аннотация

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

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

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

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



Введение

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

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

проектирование многомерный оптимизация программный



1. Постановка задачи

1.1 Назначение и структура

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

Назначение программмного комплекса

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

Цели создания программы

Уменьшение затрат времени и ресурсов для разработки объекта.

Модули прямого и градиентного поиска

Для определения оптимальных параметров объекта используются различные методы поиска. В рамках данного дипломного проекта рассматриваются методы нулевого и первого порядка.

1.2 Структура разрабатываемой программы

Структуру разрабатываемого программного комплекса можно представить на следующей блок-схеме:

Рис 1. Структура программного комплекса CADoptimizer

1.3 Техническое задание на дипломное проектирование

Разработать программный модуль прямого и градиентного поиска, реализующий следующие функции:

· Прием входных параметров и их ограничений.

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

· Вывод найденного вектора параметров.



1.4 Этапы разработки

1. Исследование объекта проектирования - 28 февраля 2013г

2. Анализ методов прямого и градиентного поиска -- 20 марта 2013г

3. Создание модуля, реализующего методы прямого поиска -- 15 апреля 2013г

4. Создание модуля, реализующего методы градиентного поиска -- 25 апреля 2013г

5. Отладка программных модулей -- 10 мая 2013г

6. Оформление дипломного проекта -- 20 мая 2013г

1.5 Порядок сдачи программы

Согласно ГОСТ 19301-79 ЕСПД "Порядок и методика испытаний, тестирования. Требования к содержанию и оформлению".



2. Теоретические основы проектирования и оптимизации

2.1 Процесс и этапы проектирования

Современные предприятия, выпускающие сложные промышленные изделия, широко используют системы автоматизированного проектирования (САПР).

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

Проектирование является одним из основных этапов современного производства. Большое внимание уделяется совершенствованию методологии проектирования. Системы автоматизированного проектирования помогают развитию математической теории проектирования сложных систем.[1]

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

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

Процесс и этапы проектирования.

Проектирование -- это сложный многоэтапный процесс, справится с которым в одиночку невозможно. Поэтому в процессе проектирования задействуют большие коллективы специалистов, которые могут быть представлены в том числе целыми институтами и научно-проектными объединениями. [6]

Проектирование сложных технических систем можно разделить на следующие этапы, показанные на схеме:

Рис 2 Этапы проектирования сложных систем

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

Являясь этапом предварительного проектирования, он оказывается одним из самых трудоемких и ответственных этапов в процессе проектирования.

2.2 Автоматизация процесса проектирования на основе методов оптимизации

Общие понятия

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

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

Введем некоторые понятия и обозначения.

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

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

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

Характеристиками называют свойства, характеризующие количественные значения показателей объекта проектирования.

Математическая модель оптимизируемого объекта -- это отображение между двумя множествами параметров

,

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта. На основании выбранного критерия оптимальности составляется целевая функция. [5]

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

Возможно использование одинаковых алгоритмов для поиска минимума и максимума -- задачу минимизации превращается в задачу поиска максимума при помощи изменения знака целевой функции на обратный.

В ряде задач оптимизации требуется введение более одной целевой функции. Иногда одна из них может оказаться несовместимой с другой. В таких случаях разработчик должен ввести весовые коэффициенты -- безразмерные множители, которые показывают приоритетность одной задачи относительно других. [4]

Локальным минимумом называется такая точка, в которой целевая функция имеет наименьшее значение по сравнению с ее значениями в окрестности этой точки.

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

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

Классификация оптимизационных задач

Задачи оптимизации можно классифицировать по виду математических моделей, которые основываются на различных математических средствах. В математическую модель входят следующие элементы: исходные данные, искомые переменные. Так же в качестве элемента математической модели стоит рассматривать зависимости между переменными. [5]

Подобную классификацию оптимизационных задач удобно представить в виде схемы

Рис 3. Классификация задач оптимизации.

Исходные данные могут быть детерминированными (заранее и полностью обусловленные и не подверженные случайностям) и случайными(заранее не известны, учитывают возможность альтернативных вариантов системы).

Искомые переменные делятся на непрерывные и дискретные. Непрерывные переменные способны принимать любые значения, входящие в область определения, дискретные - только заданные значения. Если дискретная переменная принимает только целые значения, ее называют целочисленной.

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

Сочетание различных элементов модели образует различные классы задач оптимизации, которые требуют разных методов решения.

Многокритериальная оптимизация.

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

Задачу многокритериальной оптимизации можно сформулировать следующим образом:

,

где - целевые функции, - вектор параметров.

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

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



2.3 Одномерная оптимизация

Наиболее простым типом оптимизационных задач является оптимизация функции одной переменной. Но, тем не менее, задачи одномерной оптимизации встречаются достаточно часто. Кроме того, такие задачи входят в некоторые алгоритмы более сложной, многопараметрической оптимизации.[3]

Разработанные методы одномерной оптимизации можно разделить на две группы -- методы сужения интервала неопределенности и методы с использованием производных.

Методы сужения интервала неопределенности

Идея методов сужения интервала неопределенности заключается в нахождении некоторого множества абсцисс x1,x2,...,xn, в которых вычисляется значение целевой функции, такое, что искомое оптимальное значение целевой функции лежит в интервале (xi-1,xi). Такой интервал называют интервалом неопределенности.

Существуют различные способы сужения интервала неопределенности. Рассмотрим некоторые из них.

Общий поиск

Если по условиям задачи известно, что точка минимума находится на некотором интервале [a,b], и дополнительная информация отсутствует, то для поиска можно использовать метод общего поиска.

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

В результате интервал неопределенности сужается до двух шагов сетки.

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

Рис 4 Метод общего поиска.

Метод деления интервала пополам.

Данный метод похож на метод общего поиска. Однако метод деления интервала на два равные части эффективнее.

Рассмотрим подробнее алгоритм метода.

Для данного метода можно условно выделить два типа итераций -- начальная и основная.

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

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

Ее результатом является интервал, содержащий точку минимума, уже разделенный на две равные части.

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

Рис 5 Метод деления интервала пополам.

Данный метод можно применять только при условии, функция является унимодальной на заданном интервале.

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

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

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

Полученные точки получаются симметричны относительно центра отрезка.

Точки, делящие отрезок [a,b] на четыре части выбираются согласно формуле:

где - пропорция золотого сечения.

Построенные точки обладают следующим свойством. Точка x1 делит отрезок [a,x2], в отношении золотого сечения, также как и точка x2 делит отрезок [ x2 ,b].

На основе этого свойства можно построить итерационный процесс.

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

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

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

Поиск продолжается до достижения точки минимума необходимой точностью.

2.4 Общая характеристика методов многомерной оптимизации

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

1. Из точки Qi в n-мерном пространстве (n - количество оптимизируемых параметров) выбираеся направление изменение вектора Qi :

такое, что при достаточно малых < 0 выполняется условие убывания функции:

2. Определяется шаг изменения параметроввдоль направления :

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

Математическая реализация данного алгоритма основана на изучении поведения функции качества (целевой функции) F(Q) в окрестности Qi.

Различают 3 основных группы методов оптимизации.

1. Методы нулевого порядка без использования частных производных целевой функции по параметрам.

2. Методы первого порядка, использующие первые производные.

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

Наличие ограничений на оптимизируемые параметры и значение целевой функции приводят к некоторым особенностям оптимизации, поэтому решение некоторых задач рассматривается в двух аспектах:

1. Задачи безусловной оптимизации, в которых не учитываются ограничения.

2. Задачи нелинейного программирования, в которых учитываются ограничения типа неравенств:

2.5 Анализ методов прямого поиска

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

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

Метод покоординатного спуска

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

Алгоритм метода может быть представлен следующим образом:

1. Задают исходную точку поиска

2. Определяют направление поиска, которое совпадает с одним из координатных векторов. Если варьируется первый параметр , вектор направления принимает вид.

3. Делают шаг в выбранном направлении : , где h - шаг поиска, который выбирается таким образом, чтобы значение целевой функции в исследуемой точке было меньше чем в базовой.

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

5. Поиск завершается при выполнении условия:

то есть, когда достигнута заданная точность в нахождении точки минимума.

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

Метод поиска Хука-Дживса

Алгоритм поиска по методу Хука-Дживса состоит из двух этапов -- исследующий поиск и поиск по образцу.

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

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

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

После определения базовой точки алгоритм переходит к этапу - поиску по образцу.

На этом этапе используется информация о предыдущих успешных итерациях. Шаг производится вдоль прямой, которая соединяет 2 предыдущие базовые точки. Новая базовая точка определяется в соответствии с формулой:

xk+1 = xk + (xk -- xk-1)

Если значение целевой функции в новой точке, полученной в результате такого шага, не превышает значения в базовой точке, то шаг считается успешным, и найденная точка принимается в качестве базовой.

Движение по образцу продолжается до тех пор, пока значение значение целевой функции не начнет увеличиваться.

В случае увеличения значения целевой функции в качестве базовой точки фиксируется xk+1, и проводится исследовательский поиск. Если он оказывается успешным, то найденная точка принимается новой базовой точкой, и продолжается поиск по образцу. Если же поиск не выявил точки с меньшим значением целевой функции по сравнению со значением в базовой точке, то необходимо вернуться в точку xk и провести исследовательский поиск для поиска нового направления минимизации.

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

Таким образом, поиск по методу Хука-Дивса завершится тогда, когда величина шага станет достаточно малой. Иными словами -- когда точка минимума будет определена с заданной точностью.

Рис. 6 Поиск по методу Хука-Дживса

Метод Хука-Джився нашел широкое применение в инженерных приложениях. К его преимуществам можно отнести простоту стратегии поиска, а также невысокий уровень требований к ЭВМ.

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

Метод поиска по симплексу

В основе симплексного поиска лежит регулярный симплекс, который в n-мерном пространстве представляет собой многогранник с n+1 вершинами, являющимися равноотстоящими друг от друга. В трехмерном пространстве регулярный симплекс представляет собой тетраэдр.

При помощи определенного алгоритма построения такой фигуры можно найти минимум целевой функции.

Во-первых, необходимо построить регулярный симплекс. Для этого необходимо выбрать начальное приближение и построить оставшиеся n точек, согласно формуле

где i и j = 1,2 ... n; xi - координата i - той вершины, и - приращения, зависящие от размерности задачи и определяющиеся следующим образом:

где - масштабный коэффициент, который выбирается исходя из характера решаемой задачи.

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

Для определения координат отраженной точки строят прямую, проходящую через центр тяжести и точку, подлежащую отражению. Точки, лежащие на такой прямой определяются по формуле:

x = xj + (xc - xj).

Из формулы видно, что при =0 точка является исходной (xj), а при =1 -- центром тяжести(xc ).

Для успешной работы метода необходимо сохранить свойства регулярности строящегося симплекса. Для этого полагают =2. В таком случае новую вершину симплекса можно рассчитать по формуле

xjновая = 2xc - xjпредыдущая.

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

В ходе поиска может произойти так называемое "накрытие" точки минимума. Это означает, что вершина которой соответствует наибольшее значение целевой функции была построена на предыдущей итерации. В таком случае следует отразить вершину, значение целевой функции в которой является вторым по величине.

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

M = 1,65N + 0,05N2.

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

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

Рис 7. Поиск по симплексу.

Рассмотренный метод можно характеризовать простотой логической структуры, а значит он прост для реализации на ЭВМ. Кроме того, метод использует небольшое число заранее установленных параметров.

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

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

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

Для расширения симплекса требуется перерасчет значений целевой функции во всех его точках.

Метод сопряженных направлений Пауэла

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

Идея рассматриваемого метода заключается в том, что точку минимума квадратичной целевой функции возможно найти за n2 ( n - размерность задачи) одномерных поисков, если построена система сопряженных направлений. Понятно, что скорость поиска оптимального решения будет быстро уменьшаться при увеличении числа искомых параметров.

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

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

Пусть e1 и e2 - единичные координатные вектора, а x0 -- начальное приближение. При помощи одного из методов одномерного поиска находится коэффициент , при котором достигается минимальное значение целевой функции в точке x0 + e1. Найденная точка принимается в качестве x1 и вычисляется значение , соответствующее значению минимума целевой функции в точке x1 + e2 и обозначим ее как x2. Далее вычисляется и минимум целевой функции в соответствующей точке x3 = x2 + e1.

Направления x1 -- x3 и e1 являются сопряженными. А поиск, проводимый по направлению прямой, объединяющей точки x1 и x3 приведет в точки минимума целевой функции.

Таким образом вектор оптимальных параметров (содержащий два параметра) квадратичной функции можно найти за четыре итерации одномерных поиска.

Рис. 8. Метод сопряженных направлений Пауэла для двух параметров.

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

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

Рис. 9. Метод сопряженных направлений Пауэла для трех параметров.

Рассматриваемый метод поиска интересен тем, что имеет высокую скорость сходимости в задачах с квадратичной целевой функцией и малым количеством параметров -- всего n (размерность задачи) итераций.

Однако, если функция не является квадратичной, то количество итераций увеличивается.

2.6 Анализ методов градиентного поиска

Методы первого порядка, в отличие от нулевого, основываются на исследовании функции в окрестности точки Qi за счет ее линейной аппроксимации.

Изменение вектора параметров осуществляется одновременно для всех составляющих по формуле

,

где Pi - направление наискорейшего спуска. Для убывания функции на (i+1)-й итерации необходимо, чтобы производная функции вдоль направления Pi по была отрицательной, т.е увеличение должно вести к уменьшению F(Qi).

Новое значение параметров отыскивается вдоль направления Pi по формуле

В зависимости от сочетания процедур вычисления градиента и определения шага изменения параметров различают семейство градиентных методов.

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

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

Метод градиентного спуска

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

где - норма градиента, и sk - единичный вектор.

Траектория спуска сильно зависит от параметра . Если значение параметра велико, траектория напоминает колебательный процесс. А при слишком больших метод может расходиться. При малых значениях траектория будет плавной. Но при этом метод сходится медленно.

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

Рис 10. Метод наискорейшего спуска

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

2.7 Программные и технические средства

Язык высокого уровня PHP

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

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

Хотя, сновной областью применения PHP является написание скриптов, работающих на стороне сервера, возможности языка на этом не ограничиваются.

PHP можно использовать для написания скриптов, выполняемых в командной строке. Для таких программ уже не нужно наличие рабочего сервера. Все, что необходимо -- парсер PHP. Использование языка таким образом идеально подходит для регулярно выполняемых скриптов.

При помощи расширения PHP-GTK язык можно использовать для создания оконных приложений. Язык разрабатывался для других целей и является не самым удобным для подобных проектов. Однако, при хорошем владении PHP это становится возможным.

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

Одним из значительных преимуществ PHP является поддержка широкого круга баз данных, в том числе MySQL, InterBase, Solid и другие.

Denwer

Для тестирования и отладки PHP-скриптов необходим сервер. Для использования веб-сервера необходимо подключение к интернету. От скорости подключения будет зависеть и скорость работы над проектом, так как для выполнения скрипта, его необходимо загрузить на сервер. Использование веб-сервера не является удобным для разработки. Поэтому будет использоваться локальный сервер. Так как он запускается на машине разработчика, подключение к интернету становится необязательным.

В качестве локального сервера используется Денвер. Это комплекс программ, позволяющий запустить полноценный веб-сервер Apache с поддержкой PHP, Perl и сервер MySQL на машине, работающей под управлением MS Windows 95/98/Me/NT/2000/XP. Как правило, при установке не требуется никакой настройки.

Данный комплекс программ выбран не случайно. Он выгодно отличается от своих аналогов.

Во-первых, базовая версия предлагаемого комплекса Apache+PHP+Perl+MySQL имеет размер всего около 3.1Мб и при этом полностью функциональна. Дополнительные программы могут быть при необходимости установлены дополнительно.

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

Apache -- это веб-сервер с открытым исходным кодом, разработанный в начале 1995 года. На данный момент это самый популярный HTTP-сервер[2].

Основными достоинствами Apache считаются надёжность и гибкость конфигурации. Существует возможность подключения к серверу внешних модулей, разрабатываемых как создателями ядра веб-сервера ( Apache Software Foundation), так и отдельными open source-разработчиками.



3. Конструктивно-технологическая часть проекта. Разработка ПО

3.1 Функции разрабатываемого ПО и предъявляемые к нему требования

Функции разрабатываемого ПО и предъявляемые к нему требования.

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

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

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

В результате работы разрабатываемой подсистемы пользователь получает вектор оптимальных параметров для разрабатываемого объекта.

3.2 Структура программных средств разрабатываемой подсистемы

Рассмотрим общую структуру программного обеспечения и опишем функции которые выполняют его отдельные модули.

Из рисунка видно, что программный модуль состоит из пяти основных компонентов:

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

2. Метод покоординатного спуска.

3. Метод Хука-Дживса.

4. Метод поиска по симплексу.

5. Метод градиентного спуска.

Рис 11. Блок-схема модуля прямого и градиентного поиска.

3.3 Разработка алгоритмов

Подробные описания алгоритмов приведены в специальной части проекта. В данном разделе рассматриваются блок-схемы их реализации.

Метод покоординатного спуска.



Метод Хука-Дживса



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

Метод поиска по симплексу



4. Охрана труда. Обеспечение безопасности труда при эксплуатации электрооборудования

4.1 Основные понятия

Согласно Трудовому кодексу Российской Федерации (статья 209):

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

Условия труда - совокупность факторов производственной среды и трудового процесса, оказывающих влияние на работоспособность и здоровье работника.

Вредный производственный фактор - производственный фактор, воздействие которого на работника может привести к его заболеванию.

Опасный производственный фактор - производственный фактор, воздействие которого на работника может привести к его травме.

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

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

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

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

4.2 Опасные и вредные факторы, возникающие при эксплуатации ЭВМ

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

Также существует связь между работой на компьютере и такими заболеваниями, как астенопия ( утомляемость глаз), поражение срединного нерва запястья, тендиты ( воспаления тканей сухожилий), стенокардия. Кроме того длительная работа с ПЭВМ может вызывать стрессовые состояния, повышенную возбудимость, депрессии. Возможны нарушения сна и снижение концентрации внимания.

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

Конфигурация моего компьютеризированного рабочего места:

- ПК на основе процессора Intel Core Duo c необходимым набором устройств ввода-вывода и хранения информации;

лазерный принтер HP LaserJet 1018;

Монитор Philips 220XW c разрешением 1680х1050,

Частота развертки (верт.) 56-76 Гц

Частота развертки (гор.) 30-83 кГц

Далее будут рассмотрены вредные и опансые факторы, которые

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

При работе с ПЭВМ существует опасность поражения элекрическим током. Пределом безопасного напряжения для человека является 40В, в то время как ЭВМ питает напряжение сети 220В.

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

Таким образом, основные опасные и вредные факторы, возникающие при эксплуатации ЭВМ -- поражение электрическим током и статическое электричество.

4.3 Электробезопасность

Электробезопасность - система организационных и технических мероприятий и средств, обеспечивающих защиту людей от вредного и опасного воздействия электрического тока, электрической дуги, электромагнитного поля и статического электричества (ГОСТ 12.1.009-76 (1999)). Настоящее время уже невозможно представить без электроустановок различного класса напряжения. Однако их эксплуатация связана с повышенной опасностью.

Для защиты жизни работников и с целью сокращения травматизма была разработана система правил эксплуатации электроустановок (ПУЭ). В этом документе приведены общие и специальные требования. В этом документе отражены как общие, так и специальные требования. Среди них внимание уделено использованию защитных заземлений и занулений.



4.4 Необходимость проведения защитного зануления

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

Зануленим называют преднамеренное электрическое соединение с нулевым защитным проводником металлических нетоковедущих частей, которые могут оказаться под напряжением.[8]

Защитное зануление применяется для электроустановок до 1кВ. Оно является эффективной мерой защиты при косвенном прикосновении.

Нейтральный проводник -- часть электроустановки, способная проводить электрический ток, потенциал которой при нормальном эксплуатировании близок или равен нулю.

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

Поражение человека электрическим током обычно разделяют на два вида -- электрические удары и травмы.

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

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

Так же, как и при электрическом ударе, сила поражения зависит от времени воздействия и мощности разряда. Кроме того на тяжесть повреждений влияют характер тока (переменный или постоянный), место соприкосновения, путь прохождения и состояние человека( к примеру влажность рук и т. п.).

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

Таблица 1. Воздействие на организм человека переменного и постоянного тока.

I, (мА)	Переменный (частота 50Гц)	Постоянный
0.5-1.5	Легкое дрожание пальцев	Ощущений нет
2-3	Сильное дрожание пальцев	Ощущений нет
5-7	Судороги в руках, боль в руках	Легкое дрожание пальцев, небольшой нагрев рук
8-10	Не отпускающий ток	Усиленный нагрев рук
20-10	Паралич мышечной системы	Сокращение мышц рук
50-80	Паралич дыхания	Не отпускающий ток
90-100	Паралич сердца	Паралич дыхания
Более 100	Фибрилляция (разновременное сокращение мышц сердца), через несколько секунд - паралич дыхания	При 300мА фибрилляция, через 2-3 секунды - паралич дыхания

Исходя из реакций организма человека на воздействие электрического тока определяют критерии электробезопасности. Установлено три критерия и соответствующие им уровни допустимого тока.

В качестве первого критерия принимают неощутимый ток. Он не вызывает нарушений деятельности организма, поэтому допускают его длительное воздействие -- не более 10 минут в сутки. Сила тока, отвечающего критериям, различается от его типа. Для переменного тока частотой 50 Гц она составляет 0.3 мА, а для постоянного -- от 2 до 3 мА.

Второй критерий -- отпускающий ток. Длительность воздействия такого тока на человека не должна превышать 30 секунд. Сила отпускающего переменного тока -- 6 мА, постоянного -- 15мА.

Третьим критерием является фибрилляционный ток, не превосходящий пороговый фибрилляционный ток и действующий до 1 сек.

4.5 Принцип работы зануления

Попадание фазы на корпус прибора (в случае, если он соединен с нулем) приведет к короткому замыканию, а прикосновение к корпусу в таком случае к поражению электрическим током. Для избежания подобных ситуаций в цепь включается автоматический выключатель, который отключит линию от электричества. Для отключения цепи от электричества также можно использовать плавкий предохранитель. В ПУЭ сказано, что время отключения фазного напряжения сети 380/220В не долдно превышать 0,4с.

Кроме того, благодаря заземлению нейтрали, зануление обеспечивает низкое напряжение на корпусе электроприбора, исключая возможность поражения человека электрическим током.

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

"Не допускается совмещение функций нулевого защитного и нулевого рабочего проводников в цепях однофазного и постоянного тока. В качестве нулевого защитного проводника в таких цепях должен быть предусмотрен отдельный третий проводник."[13]



4.6 Устройство зануления

Защитное зануление чаще всего применяется там, где заземление невозможно в силу объективных причин. Так, например, зануление требуется в помещениях с большим количеством электроприемников.

В наружных установках нулевые защитные проводники прокладывают в земле или в полу. Зануляемые части приемников подключаются к магистрали.

В сухих помещениях нулевые защитные проводники можно прокладывть по стенам. Если же помещение сырое, то необходимо соблюдать дистанцию между стеной и проводником -- не менее 10мм.

...