Прикладные разработки в области синтеза архитектур и планирования вычислений

Конструктор специализированных алгоритмов оптимизации

Типы решаемых задач

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

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

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

Инструментальные средства

В основу построения инструментальных средств конструирования алгоритмов оптимизации положен принцип декомпозиции алгоритмов на следующие составляющие:
1. Операции алгоритмов, которые не зависят от особенностей решаемой задачи и являются универсальными для всех задач оптимизации. Они включены в единую программную библиотеку инструментальных средств.
2. Операции алгоритмов, которые зависят от особенностей решаемой задачи. Они должны быть заданы пользователем для конкретной задачи.
3. Внутренние параметры алгоритмов. Они могут задаваться пользователем или специальными функциями их вычисления.
Конструирование алгоритма для решения конкретной задачи оптимизации осуществляется в единой программной среде из этих составляющих. Разработанные инструментальные средства также включают готовые алгоритмы для решения конкретных задач (см. раздел "Приложения").
Программное обеспечение функционирует на платформе Windows. Основные средства разработки - С++, MATLAB.

Алгоритмы

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

Приложения

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

Возможные направления сотрудничества

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

Система автоматизированного планирования информационного обмена по шине с централизованным управлением

Научной группой разработаны алгоритмы и инструментальные средства для планирования информационного обмена по шине с централизованным управлением для вычислительных систем реального времени. Шина работает в соответствии со стандартом MIL-STD 1533В. Инструментальные средства позволяют автоматически решать следующие задачи:

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

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

Направления дальнейшего развития системы: расширение системы для решения задач построения топологии среды обмена и планирования обменов для вычислительных систем реального времени на основе стандарта Fibre Channel.

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

  • поддержка процесса проектирования бортовых информационно-управляющих систем;
  • поддержка процесса модернизации бортовых информационно-управляющих систем;
  • поддержка процесса проектирования систем управления сложными техническими объектами.

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

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

Возможные направления сотрудничества:

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

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

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

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

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

Password: