Моделирование систем обработки информации

.

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

4.3 Классификация нейронных сетей

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

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

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

Лекция № 5.

5.1 Однослойные сети прямого распространения

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

Рис. 4.3. Однослойная нейронная сеть

На n входов поступают некоторые сигналы, проходящие по синапсам на три нейрона, образующих единственный слой этой нейронной сети и выдающие три выходных сигнала:

,

где j = 1,2,3 - порядковый номер нейрона.

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

Весовые коэффициенты синапсов одного слоя нейронов можно свести в матрицу W, в которой каждый элемент wij задает величину i-той синоптической связи j-гo нейрона. Таким образом, процесс, происходящий в нейронной сети, можно записать:

где X и Y - соответственно векторы входных и выходных сигналов, а F(XW) - активационная функция.

5.1 Многослойные сети прямого распространения

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

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

Рис. 4.4. Нейронная сеть с одним скрытым и одним выходным слоями

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

.

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

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

Как уже говорилось выше, мощность выходного слоя сети, выполняющего окончательную классификацию пространства состояний исследуемого объекта, выбирается исходя из сложности решаемой задачи. Дело в том, что для разделения множества входных образов, например, по двум классам достаточно всего одного выхода. При этом каждый логический уровень «1» или «0» - будет обозначать отдельный класс. На двух выходах можно закодировать уже 4 класса и тд. Однако, результаты работы сети, организованной таким образом недостаточно надежны. Для повышения достоверности классификации следует ввести избыточность путем выделения каждому классу одного нейрона в выходном слое или что еще лучше, нескольких, каждый из которых обучается определять принадлежность конкретных состояний входов к определенному классу со своей степенью достоверности, например, высокой, средней и низкой. Такие нейронные сети позволяют проводить классификацию входных неявно выраженных состояний, объединенных в нечеткие (размытые или пересекающиеся) множества. Это свойство ИНС позволяет использовать нейронные сети в технической диагностике.

5.3 Сети с обратными связями (рекуррентные)

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

Рис. 4.5. Рекуррентная сеть без скрытых нейронов с обратной связью нейронов с самими собой

Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах. Рекуррентная сеть может решать задачи распознавания, если есть наборы образцовых данных. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить («вспомнить») соответствующее состояние, т. е. соответствующий образец (если такой есть) или дать заключение о том, что входные данные не соответствуют ни одному из образцов. В общем случае любой сигнал может быть задан вектором. Обозначим вектор, описывающий k-ое состояние объекта через Xk, а его компоненты, соответственно, - xik. Где k = 0, 1, …, (m - 1), m - число состояний или число запомненных образцов. Когда сеть распознает (или «вспомнит») какое-либо состояние, на основе предъявленных ей данных, ее выходы будут содержать именно это состояние, т. е. Y = Xk-ое состояние. В противном случае, выходной вектор не совпадет ни с одним образцовым набором данных или состояний. На стадии распознавания весовые коэффициенты синапсов устанавливаются следующим образом:

где i и j - индексы соответственно предсинаптического и постсинаптического нейронов; Xik, Xjk - i-тый и j-тый элементы вектора k-гo состояния.

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

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

5.4 Обучение нейронных сетей

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

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

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

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

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

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

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

,

где  - выходное значение i-ого нейрона (n-1) слоя; -выходное значение j-ого нейрона (n) слоя; и  - весовые коэффициенты синапса соединяющего эти нейроны на интерациях t и (t-1) соответственно; а - коэффициент скорости обучения.

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

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

,

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

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

Лекция № 6. МЕТОДЫ ПОЛУЧЕНИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И ОСОБЕННОСТИ ИХ МОДЕЛИРОВАНИЯ НА РАЗНЫХ УРОВНЯХ

6.1 Классификация математических моделей

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

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

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

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

Полная математическая модель технической системы получается путем объединения модели элементов в общую систему уравнений. Эта система уравнений и есть полная математическая модель.

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

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

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

В правила метода «мозгового штурма» входят следующие положения: критика не допускается; оценка предложений осуществляется после завершения сессии; чем больше выдвигается идей, тем лучше; чем оригинальнее идея, тем лучше; приветствуются комбинации идей; идеи не персонифицируются; численность группы экспертов 10-15 человек. Совершенно другим методом генерирования групповой идеи является метод Дельфы. К его характерным чертам относят анонимность, регулируемую обратную связь, групповой ответ. Обработка мнений включает в себя следующие стадии: 1) вопросы в анкетах ставятся таким образом, чтобы можно было дать количественную характеристику; 2) опрос проводится в несколько этапов, в ходе которых уточняются ответы и даже вопросы; 3) все опрашиваемые знакомятся с ответами после каждого тура; 4) если эксперт имеет мнение отличное от большинства, то он его мотивирует; 5) с полученной мотивацией знакомят всех остальных экспертов; 6) процесс повторяется, но при этом участники имеют результаты статической обработки, а также мнения коллег несогласованные с мнением большинства. Характер изменения оценок таков, что средняя оценка после интераций смещается в область, содержащую истинный ответ.

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

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

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

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

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

6.2 Особенности математического моделирования на микроуровне

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

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

6.3 Особенности математического моделирования на макроуровне

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

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

Рассмотрим примеры компонентных и топологических уравнений на примере механических поступательных систем.

Роль основных фазовых переменных в механических системах выполняют либо силы и скорости, либо силы и перемещения. Основными элементами этих систем являются:

- элементы массы, отображающие свойства инерции;

- элементы гибкости, отображающие свойства упругости;

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

Компонентное уравнение массы есть уравнение второго закона Ньютона:

,

где m - масса элементарного участка; F - сила; U - скорость.

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

,

где у - механическое напряжение; l - размер элемента в продольном направлении; Дl - изменение этого размера; Е - модуль упругости Юнга.

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

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

Механические упругие системы. Это системы - частные случаи механических поступательных систем.

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

где н - коэффициент Пуассона, уy и уz - напряжения, действующие в направлениях координатных осей y и z.

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

Гидравлические и пневматические системы. Основными фазовыми переменными гидравлических систем являются поток жидкости (расход) g и давления Р - аналоги электрических тока и напряжения соответственно.

Компонентное уравнение гидравлической системы, соответствующее резервуару:

,

где Сr - гидравлическая емкость:

,

где V - объем резервуара; - скорость распространения звука в жидкости.

Топологическое уравнение гидравлической системы имеет вид:

,

т. е. сумма потоков в любом узле системы и сумма давлений вдоль любого контура системы равны нулю.

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

Лекция № 7. ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ И ВЫБОР ЦЕЛЕВОЙ ФУНКЦИИ

7.1 Постановка и решение задач оптимизации

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

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

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

Требуемые соотношения между выходными параметрами и техническими требованиями (ТТ) называют условиями работоспособности и могут быть записаны в виде: Yi < TTi , где i лежит в пределах от 1 до k, Yj < TTj ± ДYj , где j лежит в пределах от k+1 до l; ДYj - допустимое отклонение j-го выходного параметра от указанного в ТЗ значения ТТj .

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

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

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

Решение задачи оптимизации можно разбить на два основных этапа:

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

Решение задачи, уже имеющей математическую формулировку.

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

- выбор целей функции и управляемых параметров;

- назначение ограничений;

- нормирование управляемых и выходных параметров и т. п.

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

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

Назначение ограничений. Ограничения неизбежно появляются при проектировании технических объектов и вытекают из конкретной физической и технологической реализуемости внутренних параметров элементов, ограниченности ресурсов и т.п. При постановке задачи оптимизации учет ограничений иногда бывает принципиально необходим. Так, если целевая функция имеет вид и не наложены ограничения на параметр х, то задача поиска экстремального значения W(X) становится некорректной. Ограничение суживает область проектных параметров, и искомый экстремум становится условным. Различают прямые и функциональные ограничения. Прямые ограничения имеют вид:

,

где хнi и хвi - нижнее и верхнее допустимые значения i-го управляемого параметра.

Для многих объектов параметры элементов не могут быть отрицательными, тогда ограничения записываются хнi>0 (геометрические размеры, электрическое сопротивление, масса и т.д.).

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

Типа равенства ш(х) = 0,

Типа неравенства ц(х) > 0,

где ш(х) и ц(х) - векторы.

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

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

,

где оi - коэффициент, численно равный единице параметра ui.

Нормирование выходных параметров можно выполнить с помощью весовых коэффициентов, как в аддитивном критерии.

7.2 Частные критерии оптимальности, примеры их использования, достоинства и недостатки этого подхода

Частные критерии могут применяться в случаях, когда среди выходных параметров можно выделить один основной параметр y(X), наиболее полно отражающий эффективность проектируемого объекта. Этот параметр и принимают за целевую функцию. Примерами таких параметров являются: для энергетического объекта - мощность, для технологического автомата - производительность, для транспортного средства - грузоподъемность. Для многих технических объектов таким параметром может служить стоимость. Условие работоспособности всех остальных выходных параметров объекта относят при этом к функциональным ограничениям. Оптимизация на основе такой постановки называется оптимизацией по частному критерию.

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

7.3 Взвешенный аддитивный и мультипликативный критерии, их использование и недостатки

Взвешенный аддитивный критерий применяют тогда, когда можно выделить две группы выходных параметров. В первую группу входят выходные параметры, значения которых в процессе нужно увеличить - yj+(X) (например, производительность), во вторую - выходные параметры, значения которых следует уменьшать - yj-(X) (например, вес или стоимость). Объединение нескольких выходных параметров, имеющих в общем случае различную физическую размерность, в одной скалярной целевой функции требует предварительного нормирования этих параметров. Если принятые параметры можно свести к безразмерным, тогда для случая минимизации целевой функции свертка векторного критерия будет иметь вид:

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

определяющем среднеквадратичное приближение yj(X) к значениям заданным техническим требованиям ТТj .

Требуемые соотношения между входными параметрами и техническими требованиями (ТТ) называют условиями работоспособности.

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

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

7.4 Минимаксные (максиминные) критерии, их применение при проектировании

Минимаксные (максиминные) критерии позволяют достичь одной из целей оптимального проектирования - наилучшего удовлетворения условий работоспособности.

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

где aj - весовой коэффициент; yj ном - номинальное значение j-го выходного параметра; дj - величина разброса j-го технического требования; ТТj - величина выходного параметра, заданного техническим требованием.

Здесь предполагается, что все соотношения сведены к виду yj < ТТj . Если yj > ТТj, то необходимо принимать аj >1 (рекомендуемые значения 5 ? аj ? 20). Если желательно достичь выполнения j-го технического требования с заданным допуском, т. е. , если необходимо получить максимально возможную оценку zj.

Качество функционирования технической системы характеризуется вектором выходных параметров Z = (z1, z2, …zn). Поэтому целевую функцию следует формировать, как некоторую функцию ц(Z) вектора оценок. Если в качестве целевой функции рассматривается запас только того выходного параметра, который в данной точке Х является наихудшим с позиций выполнения требований ТЗ, то W(X) = min zj(X), где j изменяется в пределах 1 ? j ? m, где m - количество запасов работоспособности.

Теперь поставим задачу поиска значения Х, которая максимизировала бы минимальный из запасов, т.е. maxW(X) = max min zj(X), причем это максимальное значение целевой функции должно лежать в допустимой области поиска. Такой критерий оптимизации целевой функции называют максиминным критерием.

Лекция № 8. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

8.1 Классификация методов поиска экстремума

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

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

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

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

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

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

8.2 Методы одномерного поиска

Обозначим через Х* искомое значение управляемого параметра, составляющего минимум целевой функции W(X) . К функции не предъявляются требования дифференцируемости или непрерывности. Предполагается, что для любого х, лежащего в интервале поиска [a,b] значение W(X*) может быть вычислено, т. е. найдено путем вычислительного экстремума.

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

Рассмотрим методы последовательного поиска. Стратегию последовательного поиска Х*, при которой любая пара вычислений целевой функции W(X) позволяет сузить область поиска (или интервал поиска). Это осуществляется следующим образом: в интервале поиска вычисляется W(X) в точках Х1 и Х2, таких что а< Х1< Х2 < b, можно локализовать интервал поиска путем анализа полученных значений:

если W(X1) < W(Х2), то Х* лежит в интервале [a, Х2 ];

если W(X1) = W(Х2), то Х* лежит в интервале [Х1, Х2];

если W(X1) > W (Х2), то Х* лежит в интервале [Х1, b].

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

8.3 Метод дихотомии

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

В условиях, когда на k-м шаге проводятся два опыта аргументы Х1k и Х2k должны выбираться на расстоянии д/2 справа и слева от середины интервала.

; ,

где д>0 - константа, определяющая расстояние между двумя значениями аргумента; аk , bk - границы интервала на k-м шаге.

Вычислив W(X1k) и W(X2k) и сравнив полученные значения, найдем интервал неопределенности:

если W(X1k) < W(Х2k), то аk+1 = аk , bk+1 = X2k ;

если W(X1k) = W(Х2k), то аk+1 = X1k , bk+1 = X2k ;

если W(X1k)> W(Х2k), то аk+1 = X1k , , bk+1 = bk .

Затем снова вычислим координаты Х1 и Х2 и продолжим поиск.

Коэффициент дробления интервала при этом способе задается зависимостью:

.

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

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

Рис. 7.1

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

Кроме того Z1 + Z2 = Z. Из первого уравнения определяем:

.

Подставив в это выражение значение Z из второго уравнения, получим:

.

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

.

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

.

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

8.5 Особенности поиска при максиминных постановках задач оптимизации

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

Максиминная постановка задач параметрической оптимизации одна из наиболее перспективных при проектировании технических объектов. Это объясняется тем, что в результате оптимизации улучшаются запасы работоспособности практически для всех выходных параметров проектируемого изделия. Однако решение этих задач при такой постановке имеет специфику. Прежде всего, это касается условий формирования целевой функции, которая называется функцией с максиминным критерием и выглядит W(X) = minZj(X) , где Zj(X) - оценка степени выполнения j-го условия работоспособности, а j - изменяется в пределах 1<j<m (m - количество запасов работоспособности). Эта оценка в процессе поиска формируется следующим образом.

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

Среди всех оценок в точке Xk находят минимальную, пусть например это будет оценка Zp. В этом случае целевая функция W(X) = Zp(X). До момента смены оценки Zp на другую, гиперповерхность целевой функции является гладкой, что позволяет провести максимизацию этой целевой функции одним из методов нелинейного программирования. Происходит улучшение оценки Zp. Однако, в силу конфликтности выходных параметров улучшения оценки Zp, приводит к ухудшению других оценок. Например, увеличение прочности элемента конструкции приводит к увеличению ее массы и стоимости. Поэтому на определенном этапе поиска оказывается, что минимальной становится другая оценка, например Zq. Такая смена минимальных оценок может наблюдаться для разных условий.

На представленном рис. 7.2 показан случай, когда на k+1-м шаге поиска в качестве целевой функции будет фигурировать функция W(X) = Zq(X).

Рис. 7.2

Рис. 7.3

Как видно из рисунка оценки Zp и Zq имеют тенденцию к увеличению и смену целевой функции можно трактовать как переход с одной гиперповерхности поиска на другую. Анализ поведения оценок, отраженный на рис. 7.3 показывает, что ограничиться простой сменой оценок в целевой функции нельзя. Искомый максимум должен находиться на гиперповерхности пересечений двух гиперповерхностей Zp(Х) и Zq(Х). Эта гиперповерхность пересечений является гребнем гиперповерхности целевой функции, а точка пересечения оценок Zp(Х) и Zq(Х), является точкой гребня. В этом случае, безусловный поиск целесообразно заменить на условный: вводится ограничение типа равенства Zp(Х) = Zq(Х), а в качестве целевой функции можно рассматривать прежнюю оценку.

Анализ особенностей формирования целевой функции показывает, что функция минимума W(X) не может быть гладкой. В точках гребней целевая функция не дифференцируемая, поэтому одним из наиболее эффективных алгоритмов решения задач в максиминной постановке является метод проекции градиента. Использование этого метода возможно потому что, уравнения гребней удается сформулировать в виде равенств конфликтных оценок Zp(Х) = Zq(Х) и рассматривать их, как ограничения задачи.

Лекция № 9

9.1 Методы случайного поиска

Методы случайного поиска классифицируются как методы многомерного поиска. Идея методов заключается в том, чтобы перебором случайных значений управляемых параметров найти оптимальное значение целевой функции. В этих методах направление поиска выбирается случайным образом, на основании генерации ЭВМ случайных чисел посредством ГСЧ. Среди многих разновидностей методов случайного поиска простейшим является метод Монте-Карло. На (k+1) шаге поиска определяется случайная точка Xk+1, вычисляется значение W(Xk+1) и сравнивается со значением, полученном на предыдущем шаге. Если W(Xk+1) < W(Xk), то запоминаются координаты точки и новые значения целевой функции.

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

Если производится k выборок случайных точек, то вероятность попадания, хотя бы одной из них в е - окрестность составляет P(k) = 1 - (1 - еn)k. Следовательно, величина выборки k случайных точек, необходимое для того, чтобы с вероятностью Р можно было бы утверждать, что найденное с точностью е оптимальное значение соответствует истинному, равно

,

где е - окрестность точки экстремума; n - величина мерности пространства (Евклидова); Р - вероятность попадания случайной точки в окрестности.

Например, для двумерной задачи (n = 2) при Р=1/2 и е= 10-3 нужно вычислить не менее, чем

выборок случайных чисел.

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

Для дальнейшего с использованием метода “Монте-Карло” приведем следующий пример.

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

Рис. 7.4.

Предположим, у нас имеется монета и при выпадении «орла» будем считать, что элемент выбран из Тайваня, а «решки» - из Китая. Если одновременно бросить три монеты и при этом выпадут три «решки», то компьютер считается неисправным. Таким образом, мы сымитировали ситуацию и разыграли случайное число, которое имеет равномерное распределение. Вероятность первого события (элемент из Тайваня) равно 0,5, и вероятность второго события (элемент из Китая) тоже равна 0,5.

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

Таблица 7.1

Номер реализации	1-я монета	2-я монета	3-я монета	Результат
1	0,86	0,51	0,56	Брак
2	0,91	0,86	0,41	Годен
3	0,68	0,68	0,65	Брак
4	0,22	0,72	0,58	Годен
5	0,75	0,24	0,52	-“-
6	0,76	0,77	0,30	-“-
7	0,48	0,25	0,87	-“-
8	0,87	0,11	0,38	-“-
9	0,38	0,47	0,54	-“-
10	0,90	0,79	0,51	Брак

Теперь разделим количество случаев с браком на общее количество реализации. Получим . Данную задачу можно решить и аналитически. В этом случае ответ будет 0,125. Если продолжим дальнейшие реализации (бросание монет), то можем получить ответ, близкий к расчетному. Какой вывод можно сделать из этого примера? Очевидно, что результат в данном методе напрямую связан с количеством реализаций. И ошибка метода обратно пропорциональна величине . Следовательно, сходимость к истинному результату требует значительного числа реализации, а значит, метод крайне эффективен, прост, но необходим «хороший» генератор.

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