close

Вход

Забыли?

вход по аккаунту

?

Язык lmpl как средство синтеза прикладных программных моделей и метамоделей на основе принципов математического программирования.

код для вставкиСкачать
Кибернетика. Информационные системы и технологии
УДК 519.693+519.688+519.71+519.1
ЯЗЫК LMPL КАК СРЕДСТВО СИНТЕЗА ПРИКЛАДНЫХ ПРОГРАММНЫХ МОДЕЛЕЙ
И МЕТАМОДЕЛЕЙ НА ОСНОВЕ ПРИНЦИПОВ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
© Н.В. Абасов1, А.В. Каверзина2, Е.Н. Осипчук3, М.Ю. Чернышов4
1,3
Институт систем энергетики им. Л.А. Мелентьева СО РАН
664033, г. Иркутск, ул. Лермонтова, 130.
2
Иркутский государственный лингвистический университет,
664025, Россия, г. Иркутск, ул. Ленина, 8.
4
Иркутский научный центр Сибирского отделения РАН,
664033, Россия, г. Иркутск, ул. Лермонтова, 134.
Описывается разработанный авторами язык LMPL как эффективное средство синтеза прикладных программных
моделей и метамоделей, строящихся на основе принципов математического программирования (МП). Он отличается наглядной формой декларативного представления МП-моделей, упрощенным синтаксисом, предусматривает автоматическое построение и преобразование моделей, а также формирование результирующих диаграмм
с возможностью подключения внешних программных пакетов. Реализация LMPL является портабельной и кроссплатформенной.
Ил. 3. Табл. 2. Библиогр. 7 назв.
Ключевые слова: язык LMPL; моделирование; метамоделирование; математическое программирование; автоматическое построение и преобразование моделей.
LMPL LANGUAGE AS A SYNTHESIS MEANS FOR APPLIED SOFTWARE MODELS AND METAMODELS BASED
ON MATHEMATICAL PROGRAMMING PRINCIPLES
N.V. Abasov, A.V. Kaverzina, E.N. Osipchuk, M.Yu. Chernyshov
L.A. Melentiev Energy Systems Institute SB RAS,
130 Lermontov St., Irkutsk, Russia, 664033.
Irkutsk State Linguistic University,
8 Lenin St., Irkutsk, Russia, 664025.
Irkutsk Scientific Center SB RAS,
134 Lermontov St., Irkutsk, Russia, 664033.
The paper describes the LMPL language developed by the authors as an efficient synthesis means of applied software
models and metamodels constructed on the basis of mathematical programming (MP) principles. It differs in an explicit
form of declarative representation of MP-models, simplified syntax, presumes automatic constructing and transformation
of models, and automatic constructing of resulting diagrams with the possibility to add external software packages. The
implementation of LMPL is portable and cross-platform.
3 figures. 2 tables. 7 sources.
Key words: LMPL language; modeling; metamodeling; mathematical programming; automatic construction and transformation of models.
LMPL как язык синтеза моделей и метамоделей. Авторами разработан Light Mathematical
Programming Language (ниже – язык LMPL), предназначенный для компактного и наглядного представления задач математического программирования (МП).
Этот язык построен на основе прототипов в виде базового языка MPL [6] и его расширенного (augmented)
варианта AMPL [5].
LMPL обеспечивает упрощенный синтез, модификацию и анализ МП-моделей и имеет следующие характеристики:
– компактная и наглядная форма декларативного
представления МП-моделей (в т.ч. уравнений, ограничений, критериев оптимизации) в виде набора блоков
(табл. 1, 2) с определением индексных переменных;
– упрощенный синтаксис (отсутствуют операторы,
___________________________
1
Абасов Николай Викторович, кандидат технических наук, ведущий научный сотрудник, тел.: 89646535739, e-mail:
nva@isem.sei.irk.ru
Abasov Nikolai, Candidate of technical sciences, Leading Researcher, tel.: 89646535739, e-mail: nva@isem.sei.irk.ru
2
Каверзина Анастасия Владимировна, аспирант, тел.: 89246067987, e-mail: anastasiakaver@mail.ru
Kaverzina Anastasiya, Postgraduate, tel.: 89246067987, e-mail: anastasiakaver@mail.ru
3
Осипчук Евгений Николаевич, младший научный сотрудник, тел.: 89500694090, e-mail: evgeny-osipchuk@yandex.ru
Osipchuk Evgeny, Junior Researcher, tel.: 89500694090, e-mail: evgeny-osipchuk@yandex.ru
4
Чернышов Михаил Юрьевич, кандидат филологических наук, зав. научно-методической частью Президиума, тел.:
89149327490, e-mail: Michael_Yu_Chernyshov@mail.ru
Chernyshov Mikhail, Candidate of Philology, Head of the Research-Methodological Division of the Presidium of Irkutsk Scientific
Center, Siberian Branch of RAS, tel.: 89149327490, e-mail: Michael_Yu_Chernyshov@mail.ru
12
ВЕСТНИК ИрГТУ №3 (74) 2013
Кибернетика. Информационные системы и технологии
характерные для императивных языков программирования);
– поддержка проведения многоитерационных расчётов, включая стохастическую оптимизацию и автоматическое построение результирующих диаграмм;
– поддержка автоматических преобразований моделей (поиск структурных отличий моделей, выделение
общих частей, построение новых моделей), эта функция может быть использована, например, для исследования алгоритмов;
– возможность подключения внешних (в т. ч. экспериментальных) программных пакетов для решения МПзадач;
– компактная (портабельная) и кроссплатформенная
реализация (в виде библиотек на языке Lua с использованием пакета lp_solve в качестве базового решателя).
Заметим, что декларативная форма записи значительно упрощает процесс создания средств синтеза,
анализа и преобразования МП-моделей, в т.ч. средств
автоматического построения графов связей между
объектами, средств сравнения и т.д. Табл. 1 представляет перечень базовых блоков языка LMPL с
кратким описанием их функций.
Синтаксис языка LMPL в расширенной форме Бэкуса-Наура представлен в табл. 2.
Таблица 1
Базовый набор основных функциональных блоков языка LMPL и их описание
Блок
Описание блока
идентификатор модели, класс оптимизационной задачи; опционально указывается предTITLE
полагаемый решатель
входные переменные и их типы: дискретные (целочисленные INT, логические и бинарные
IN
BIN); свободные (FREE); с ненулевыми показателями (SOS)
OUT
выходные переменные
CONST
константы
OPT
целевая функция
EQ
система уравнений, часть уравнений определяется в блоке VAR
VAR
промежуточные переменные из уравнений блока EQ
LIMIT[N]
различные классы ограничений
INDEX
пределы для индексных переменных
Таблица 2
Синтаксис языка LMPL в расширенной форме Бэкуса-Наура
Базовые блоки
block = bnam ":" {bbody [";"]}
bnam = "TITLE" | "IN" | "OUT" | "CONST" | "OPT" | "EQ" | "VAR" |
"LIMIT"[nat] | "INDEX"
bbody = btitle | binp | bout | bconst | bopt | beq | bvar | blimit | bind
Блок TITLE: идентификатор модели, классы задач, решатели
btitle = idmod "," optc ["," slv]
idmod = name
optc = "lp"|"nlp"|"mip"|"lfp"|"rmip"|"minlp"|"rminlp"|"mcp"|"cns"
slv = "lp_solve" | "GAMS" | "AMPL" | "CPLEX" | "MINOS"
блок IN: входные переменные
блок OUT: выходные переменные
binp= vtype var | var"="exp | name"="seq
bout = varv
var = name | name "[" exp "]"
varv = {var ","} var
vtype = "SOS" | "BIN" | "INT" | "FREE"
блок CONST: константы
блок VAR: промежуточные переменные
bconst = var "=" exp | name "=" seq
bvar = var "=" exp
блок OPT: критерий оптимизации
блок EQ: система уравнений
bopt = exp "->" optm
beq = exp "=" exp
optm = "min" | "max"
блок LIMIT: ограничения
блок INDEX: индексы
blimit = exp comop exp | exp "*=" ["[" | "("] exp "," exp ["]" | ")"] bindex = name "*=" exp "," exp
выражения
последовательности
exp = term | [unop]{exp binop} exp |
seq = "{" expv "}"
"(" exp ")" | fnam "(" exp ")"
expv = {exp ","} exp
term = digit | var
операции
функции
binop = "+" | "-" | "*" | "/" | "^"
fnam = "sum" | "prod" | "abs"
unop = "-"
comop = "<" | ">" | "<=" | ">="
где digit - десятичное число, name – идентификатор
Любая прикладная модель, записанная в терминах LMPL, после преобразований автоматически при-
ВЕСТНИК ИрГТУ №3 (74) 2013
13
Кибернетика. Информационные системы и технологии
водится к классической форме соответствующей исходной МП-задачи, т.е. к форме, во-первых, удобной
для исследователя, а, во-вторых, – для автоматической передачи различным решателям задач (lp_solve,
COPL_QP, GAMS [7], AMPL и др.).
LMPL как средство метамоделирования. Язык
LMPL изначально предполагает возможность построения (синтеза) и анализа метамоделей. Под метамоделью понимается обобщенная модель, пригодная
для описания множества простых моделей [2; 4]. ММ
включает в себя обобщенную базу знаний и конструктора для синтеза прикладных моделей. Идея языка
LMPL основана на принципах декларативного описания логики программ языка ОЛФИС [1].
Функция метамоделирования как синтеза
предполагает следующие этапы: 1) задание шаблона
метамодели; 2) объявление блоков, входящих в метамодель (примером может быть включение блока базовых уравнений моделей, констант); 3) объявление
заменяемых в процессе генерации моделей промежуточных переменных (метапеременных); 4) задание
параметров метамодели (например, названия объекта, режима работы, начального состояния) и выбор
предполагаемого решателя задач (его характеристик);
5) генерация модели на языке LMPL с помощью разработанного модуля-конвертера; 6) приведение LMPLмодели к формату решателя (в случае необходимости
может быть выполнен анализ результатов, полученных решателем и генерация отчётов (в текстовом и
графическом виде).
Процесс моделирования предполагает: 1) объявление набора случайных параметров и их характеристик; 2) задание параметров управления блоком стохастической оптимизации (количество итераций, шаг
дискретизации); 3) генерацию множества детерминированных моделей (генерации случайных чисел); 4)
решение оптимизационной задачи с сохранением текущих оптимальных показателей по каждой итерации;
5) обработку накопленной статистики; 6) формирование итоговых таблиц с вероятностными распределениями.
Структура исходного текста модели строится из
функциональных блоков, которым сопоставляются:
класс задачи, идентификатор типа модели, тип решателя задачи, целевая функция, функция сравнения,
ограничения, индексные переменные, переменные и
константы соответствующие задачам и условиям моделирования. На рис. 1 приведена структура модели
на языке LMPL (базовый набор основных функциональных блоков языка LMPL, функции, переменные и
константы). Очевидно, что LMPL позволяет описать
модель в форме, являющейся в некотором смысле
отображением матлогической формы, поскольку
предполагает использование множества индексных
переменных, констант, операторов и кванторов. Представления о переменных, множествах, граничных
условиях позволяют обращаться к ним, используя соответствующие индексы. Опционально может быть
указан предполагаемый решатель МП-задач.
При синтезе моделей важной является возможность их представления в декларативной форме. Дело
в том, что в случае императивной формы, в терминах
которой строится большинство программ и моделей,
логика синтеза существенно осложнена необходимостью последовательного процесса синтеза модели.
Декларативная форма дает возможность эффективно
описывать модели, а также создавать гибкие средства
для последующего исследования алгоритмов, их развития и сопровождения.
Разработанный программный комплекс, использующий LMPL (ПК-LMPL), позволяет выполнять следующие операции синтеза:
 построение модели из частей (более простых
моделей);
 сравнение модели с прототипом и выявление
структурных отличий;
 построение графов связей между объектами
модели (рис. 2), где в качестве объектов присутствуют
различные переменные или множества переменных.
Функция анализа моделей. Разработанная программная система, использующая LMPL, позволяет
выполнять следующие операции анализа моделей, в
том числе:
 анализ графов связей между объектами модели
(рис. 2) (т.е. между различными переменными и множествами переменных);
 выявление структурных отличий модели от прототипа;
 выделение общих частей модели и прототипа.
Функция преобразования моделей. Программ-
Рис. 1. Структура модели на языке LMPL (функциональные блоки, функции, переменные и константы)
14
ВЕСТНИК ИрГТУ №3 (74) 2013
Кибернетика. Информационные системы и технологии
Рис. 2. Пример графа связей между объектами LMPL-модели
ная система, использующая LMPL, позволяет выполнять преобразования модели, связанные с построением новых моделей из выделенных блоков.
Проведенные исследования показали, что язык
LMPL может быть эффективным средством синтеза и
анализа прикладных программных моделей, выполняемых на основе принципов математического программирования и осмысленного метамоделирования.
Пример метамоделирования режимов ГЭС.
Рассмотрим пример применения метамоделирования
в анализе моделей режимов гидроэлектростанций
(ГЭС). При рассмотрении и сравнении различных моделей режимов ГЭС у специалистов обычно появляется необходимость объединить их в единую систему,
построив целостную модель. Это можно сделать на
основе метамодели, введя краткое описание связей
между моделями, что позволяет сформировать целостную модель.
Метамодель предполагает наличие базы знаний
(БЗ), содержащей фрагменты моделей, и специальные решатели, которые могут быть использованы для
синтеза прикладных моделей. БЗ содержит фрагменты различных типов моделей, для которых можно вы-
делить, например, общие уравнения данной предметной области, переменные, константы, критерии оптимизации и ограничения. Это позволяет использовать
указанные средства метамоделирования для автоматической генерации конкретных прикладных моделей.
Пример модельного представления процесса выбора
оптимальных режимов ГЭС, полученного на основе
принципа метамоделирования, представлен на рис. 3.
Данная метамодель рассматривается нами в детерминированном и стохастическом вариантах. Метамодель является стохастической в том смысле, что в
ней один параметр или несколько параметров описываются некоторой функцией распределения.
Процесс метамоделирования в детерминированном варианте, предполагающем получение модельного представления процесса выбора оптимальных режимов ГЭС, предполагает следующие этапы: 1) задание шаблона данной метамодели; 2) объявление блоков, входящих в метамодель (в т. ч., включение блока
основных
уравнений
моделей
и
констант);
3) объявление метапеременных, заменяемых в процессе генерации данной прикладной модели; 4) задание параметров метамодели (объект, режим работы
Рис. 3. Пример модельного представления процесса выбора оптимальных режимов ГЭС, полученного на основе
принципа метамоделирования
ВЕСТНИК ИрГТУ №3 (74) 2013
15
Кибернетика. Информационные системы и технологии
ГЭС, параметры, отражающие начальные состояния,
т.е. значения переменных и констант); 5) выбор предполагаемого решателя задач; 6) генерация модели
режима ГЭС на языке LMPL с помощью модуляконвертера; 7) приведение построенной LMPL-модели
к формату решателя задач; 8) анализ результатов,
полученных решателем; 9) формирование отчётов в
текстовом и графическом виде.
Процесс моделирования в стохастическом режиме
предполагает этапы: 1) объявление набора случайных
параметров и их характеристик; 2) задание параметров управления стохастическим блоком (количество
итераций, шаг дискретизации); 3) создание множества
детерминированных моделей с помощью генератора
случайных чисел (ГСЧ) произвольного распределения;
4) решение оптимизационной задачи с сохранением
текущих оптимальных показателей на каждой итера-
ции; 5) обработку накопленной статистики, формирование итоговой таблицы с вероятностными распределениями.
Практическое опробование технологии метамоделирования с использованием языка LMPL на ряде
разнотипных прикладных задач (в том числе, моделирование режимов ГЭС; моделирование семантически
связных дискурсивных формаций; моделирование
оптимальных отношений в дискурсе [3]) убедительно
показало ее высокую эффективность. Таким образом,
можно утверждать, что язык LMPL, разработанный
авторами, реализованный в форме технологии метамоделирования, позволяет эффективно и комплексно
решать ряд оптимизационных задач математического
программирования, относящихся к различным прикладным областям.
Библиографический список
1. Абасов Н.В. О развитии языка описания логико4. Лядова Л.Н. Метамоделирование и многоуровневые мефункциональных связей ОЛФИС до языка моделирования //
таданные как основа технологии создания адаптируемых
Информационные и математические технологии в науке,
информационных систем // Advanced Studies in Software and
технике и образовании: Труды X Байкальской Всерос. конф.
Knowledge Engineering International Book Series «Information
(Иркутск, 19–21 апреля 2005 г.). Иркутск: ИСЭМ СО РАН,
Science & Computing». Varna, Bulgaria, 2008. № 4.
2005. С. 103–109.
P. 125–132.
2. Абасов Н.В., Осипчук Е.Н. Язык описания метамоделей
5. Fourer R., Gay D.M., Kernighan B.W. AMPL: A Modeling
задач математического программирования и его применение
Language for Mathematical Programming. New York : Thomson,
в гидроэнергетике // Вестник ИрГТУ. 2012. №5(64).
Brooks and Cole, 2002. 517 p.
3. Исследование структуры дискурса средствами математи6. MPL Modeling System, Maximal Software. URL:
ческого программирования и формальный анализ его логиhttp://www.maximal-usa.com (дата обращения: 20.01.2013).
ческой семантики / А.В. Каверзина, М.Ю. Чернышов, Н.В.
7. Tikhonova O., McKinney Daene C., Savitsky A. GAMS ManuАбасов, Е.Н. Осипчук // Вестник ИГЛУ. 2013. №2(23).
al: http://www.gams.com/docs/contributed/gamsman_russian.pdf
С. 180–187.
(дата обращения: 18.01.2013).
УДК 004.822
МЕТОДОЛОГИЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СОВМЕСТНОГО ИСПОЛЬЗОВАНИЯ
ОНТОЛОГИИ И КВАЛИМЕТРИЧЕСКОЙ ЭКСПЕРТИЗЫ ПРИ ОЦЕНКЕ КАЧЕСТВА СТАНКОВ
© Р.С. Дорофеев1
Иркутский государственный технический университет,
664074, Россия, г. Иркутск, ул. Лермонтова, 83.
Предлагается методология совместного использования квалиметрической экспертизы и онтологии для оценки
качества металлорежущих станков. Описывается разработанное на её основе приложение для корректировки
имеющейся онтологии и преобразования её в базу данных для дальнейшего использования сгенерированной
базы данных при оценке качества. Показано использование разработки для количественной оценки качества
двух металлорежущих станков одинакового типа, приведены результаты сравнения.
Ил. 11. Библиогр. 10 назв.
Ключевые слова: онтологии; квалиметрическая экспертиза; оценка качества; металлорежущие станки;
язык OBL.
METHODOLOGY AND SOFTWARE IMPLEMENTATION OF SHARED USE OF ONTOLOGIES AND QUALIMETRIC
EXAMINATION WHEN EVALUATING MACHINE TOOL QUALITY
R.S. Dorofeev
Irkutsk State Technical University,
83 Lermontov St., Irkutsk, Russia, 664074.
The paper proposes a methodology for sharing qualimetric examination and ontology to evaluate machine tool quality. It
describes the application based on it for adjusting the ontology available and its transformation into a database for future
use of the generated database under quality assessment. An example illustrates the use of the design for quantitative
___________________________
1
Дорофеев Роман Сергеевич, аспирант, тел.: 89500858769, e-mail: rdobermann@list.ru
Dorofeev Roman, Postgraduate, tel.: 89500858769, e-mail: rdobermann@list.ru
16
ВЕСТНИК ИрГТУ №3 (74) 2013
1/--страниц
Пожаловаться на содержимое документа