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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………………………...…..10

1 АНАЛИЗ ТЕХНИЧЕСКОГО ЗАДАНИЯ.………………………..14

1.1 Постановка задачи………………………………………………………..14

1.2 Обзор стохастических алгоритмов оптимизации………………….....17

1.2.1 Случайные методы решения оптимизационных задач………………..19

1.2.1.1 Метод Монте-Карло…………………………………………………..19

1.2.1.2 Метод моделирования отжига……………………………………….21

1.2.1.3 Эволюционный поиск и генетические алгоритмы…………………...23

2 РАЗРАБОТКА АЛГОРИТМА ДИНАМИЧЕСКОГО УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫМ ПРОЦЕССОМ В СТОХАСТИЧЕСКИХ МЕТОДАХ ОПТИМИЗАЦИИ……….….25

2.1 Статистические исследования данных…………………………….…...25

2.1.1 Основные понятия и определения……………………………….…….…26

2.1.2 Анализ полученных данных……………………………………………….28

2.2 Описание разработанного алгоритма…………………………………..31

3 РАЗРАБОТКА ПОДПРОГРАММЫ РЕШЕНИЯ ЗАДАЧ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ЭВА СТОХАСТИЧЕСКИМ МЕТОДОМ С ДИНАМИЧЕСКИМ УПРАВЛЕНИЕМ ВЫЧИСЛИТЕЛЬНЫМ ПРОЦЕССОМ……34

3.1 Структурная схема программы…………………………………………35

3.2 Графический интерфейс пользователя………………………………...37

3.3 Тестовые испытания программы……………………………………….39

3.4 Инструкция по подключению подпрограммы к программам решения задач конструкторского проектирования ЭВА………………..44

4 ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ ПРОЕКТА…………………………………………………………………….45

4.1 Маркетинговые исследования рынка……………………………….….45

4.2 Расчет затрат на этапе проектирования…………………………….….45

4.3 Выбор базы сравнения (аналога)………………………………………..52

4.4 Сравнительный анализ затрат в ходе эксплуатации программного продукта и аналога…………………………………………………………….54

4.5 Расчет экономии от увеличения производительности труда пользователя…………………………………………………………………...58

4.6 Ожидаемый экономический эффект и срок окупаемости капитальных затрат…………………………………………………………..59

5 БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ ПРОЕКТА……….62

5.1 Системный анализ отказа работы программы………………………..62

5.2 Напряженность трудового процесса…………………………………….65

5.3 Мероприятия по повышению безотказности системы и по улучшению условий труда................................................................................69

5.4 Пожарная безопасность…………………………………………………...74

5.5 Экологичность проекта…………………………………………………...75

ЗАКЛЮЧЕНИЕ……………………………………………………………..77

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………78

ПРИЛОЖЕНИЕ А………………………………………………………….80

ПРИЛОЖЕНИЕ Б………………………………………………………...101

ВВЕДЕНИЕ

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

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

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

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

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

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

Существенным отличием автоматизированного проектирования от неавтоматизированного является возможность замены дорогостоящего и занимающего много времени физического моделирования — математическим моделированием, основанном на математическом обеспечении САПР. Математическое обеспечение –  это совокупность математических методов, математических моделей и алгоритмов проектирования, представленных в заданной форме. Математической моделью называют совокупность уравнений или иных средств, описывающих функционирование объекта и реализующих математические методы расчёта его характеристик, а алгоритмом проектирования – совокупность предписаний, необходимых для выполнения проектирования. При этом следует иметь в виду одно важнейшее обстоятельство: при проектировании число вариантов необозримо [5].

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

В конечном итоге математическое обеспечение реализуется в САПР в виде программ и сопровождающей документации.

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

В программном обеспечении выделяют две части: системную и проблемную (часто называемую прикладной). Системная часть обеспечивает функционирование САПР в процессе проектирования, а также на этапах создания и модифицирования САПР. Задачу реализации конкретных проектных процедур решает прикладное программное обеспечение, ориентированное на решение задач из определённой области знаний, называемой предметной областью. Особенности конкретной  предметной области в первую очередь проявляются в математических моделях проектируемых объектов, но эти особенности отражаются и на способах решения задач структурного синтеза [5]. Хотя существует множество различных форм представления математического обеспечения, его практическое использование происходит только лишь после реализации в программном обеспечении.

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

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

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

Кроме того, очень часто при увеличении сложности проектируемого объекта, инженер упирается в проблему машинного времени. Нередко именно этот фактор выступает главным ограничивающим фактором при попытке улучшить качество исследования или повысить сложность решаемой задачи. Так происходит из-за того, что при решении большинства задач на ЭВМ используются универсальные модели и методы, которые отличаются сравнительно большим объемом вычислений, растущим с увеличением размерности задач. Поэтому требование экономичности по затратам машинного времени — одно из основных требований к математическому обеспечению САПР. Следовательно, желательно было бы иметь инструмент, который помог бы избежать избыточных вычислений и сэкономить тем самым ресурсы.

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

1 АНАЛИЗ ТЕХНИЧЕСКОГО ЗАДАНИЯ

Быстрый прогресс в технологии электронно вычислительной аппаратуры (ЭВА) требует новых средств автоматизированного проектирования. Разработчикам необходимы САПР, позволяющие реализовывать схемы с десятками и даже сотнями миллионов транзисторов на одном кристалле. Для достижения столь высоких показателей необходимы программы, в которых используются самые современные и наиболее совершенные алгоритмы. Результатом количественного роста сложности объекта проектирования стали к качественные изменениям в методологии проектирования и, как следстие, повышение роли математически строгих постановок и результатов.

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

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

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

1.1 Постановка задачи размещения

Характерной особенностью графика зависимости целевой функции F от времени t (графика оптимизации функции) (рис. 1) является то, что с увеличением времени работы алгоритма оптимизации меняется отношение   от величины меньшей 1 на начальном участке графика до величины   на конечном участке графика. Иными словами на начальном участке графика за малое время   целевая функция F изменяется на относительно большую величину  , а по мере приближения к конечному участку графика за длительное время   целевая функция F изменяется на малую величину  .

Рисунок 1 –  График оптимизации функции

В качестве динамических характеристик для исследований берутся следующие величины:

1. математическое ожидание,

2. дисперсия,

3. среднеквадратическое отклонение.

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

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

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

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

- минимизация суммарной длинны связей;

- минимизация длинны самой длинной связи;

- минимизация числа возможных пересечений;

- минимизация числа изгибов соединений;

- минимизация площади кристалла.

Каждый из этих критериев в большей или меньшей мере способствует решению основной задачи: максимизировать число реализованных соединений при последующей трассировке [5].

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

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

1.2 Обзор стохастических алгоритмов оптимизации

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

Целью оптимизационной задачи является выбор допустимого или оптимального решения из множества альтернатив для достижения поставленной цели. Это может быть некий набор параметров х={x1, х2, … хn}, которые могут быть определены как оптимальные. В узком смысле это может быть поиск минимума или максимума некой функции, как параметра от х={x1, х2, … хn}. В более широком смысле эта формулировка представляет собой минимизацию или максимизацию целевой функции F(x), при наличии ограничений в форме равенств или неравенств, а также ограничений на пределы изменения параметров.

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

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

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

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

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

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

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

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

1.2.1 Случайные методы

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

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

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

Третья категория поисковых методов – случайные методы, делится, в свою очередь, на три класса: случайный поиск, моделирование отжига и генетические алгоритмы (ГА). Эти методы в силу непрерывности оптимизационного поиска имеют наилучшие перспективы развития [2].

1.2.1.1 Метод Монте-Карло

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

Необходимо найти экстремум V(F) в заданной области допустимых параметров  с точностью интервала неопределенности  . Пусть допустимая область по одному из параметров  . В методе Монте-Карло вырабатывается псевдослучайный вектор параметров с равномерным распределением. Тогда вероятность непопадания в область экстремума за один шаг равна

      (1).

Соответственно за n шагов алгоритма

      (2),

а вероятность попадания в область минимума

      (3).

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

      (4).

В случае k внутренних параметров ЦФ число генераций этого вектора увеличится в   раз и составит  . А общее число обращений к модели метода Монте-Карло за G генераций составит

       (5)

и определит условие применимости метода при одинаковом числе итераций. Метод Монте-Карло эффективен при большом числе испытаний  . При повышенной точности   число испытаний резко возрастает и метод Монте-Карло неэкономичен.

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

Как уже было отмечено, при использовании метода Монте-Карло возможны два подхода: непосредственное проведение экспериментов или имитация этих экспериментов другими, со схожими показателями вероятностной структуры. В условиях данной задачи «натуральный» эксперимент — наблюдение за работой системы в течение времени Т.

1.2.1.2 Метод моделирования отжига

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