Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

РЕШЕНИЕ ЗАДАЧИ ЗАМЕНЫ ОБОРУДОВАНИЯ СЕТИ СВЯЗИ НА ОСНОВЕ ИНТЕГРАЦИИ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПОДХОДА, ЭКСПЕРТНЫХ СИСТЕМ И ДЕРЕВЬЕВ РЕШЕНИЙ

Аксенова О.П. 1 Аксенов К.А. 1 Попов М.В. 1 Неволина А.Л. 1 Смолий Е.Ф. 1
1 ФГАОУ ВПО “Уральский Федеральный Университет им. первого Президента России Б.Н. Ельцина”
В статье рассмотрен эвристический метод решения задачи замены оборудования сети связи на основе интеграции фреймовых систем, объектно-ориентированного подхода, имитационного моделирования и деревьев решений. Для данной задачи в качестве модели представления знаний выбрано фреймовое представление знаний. Разработано объектное дерево решений, используемое для визуализации поиска в пространстве решений фреймовой системы. Решена задача преобразования объектно-ориентированного дерева решений в классическое дерево решений. Применение метода Беллмана при реализации интеллектуальных систем на основе фреймовых систем и объектно-ориентированного подхода позволяет решить задачу оценки альтернатив. Новый метод и информационная технология принятия решений BPsim3 были использованы для решения задачи оценки альтернатив и планирования работы по замене оборудования мультисервисной сети связи в Уральском регионе.
дерево решений
имитационное моделирование
объектно-ориентированный подход
экспертные системы
фреймы
1. Аксенов К. А. Интеллектуальная система моделирования «BPsim.MSS» и объектно-структурный метод технико-экономического проектирования мультисервисных сетей связи // Вестник компьютерных и информационных технологий. – № 8. – М., 2010. – С.19-27.
2. Аксенов К. А. Модель мультиагентного процесса преобразования ресурсов и системный анализ организационно-технических систем // Вестник компьютерных и информационных технологий. – № 6. – М., 2009. – С. 38-45.
3. Доросинский Л. Г., Аксенов К. А., Попов М. В. Имитационное динамическое моделирование и технико-экономическое проектирование мультисервисных сетей связи // Научно-технические ведомости СПбГПУ. – № 1(72) 2009. Информатика. Телекоммуникации. Управление. СПб. – С.153-159.
4. Скобелев П. О., Виттих В. А. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах // Автоматика и телемеханика. – № 1. – М., 2003. – С.177-185.
5. Черноруцкий И. Г. Методы принятия решений: учебное пособие. – СПб.: БХВ, 2005. – 416 с.
6. Aksyonov K., Bykov E., Dorosinskiy L., Smoliy E. and Aksyonova O. Decision Support based on Multi-Agent Simulation Algorithms with Resource Conversion Processes Apparatus Application, Multi-Agent Systems - Modeling, Interactions, Simulations and Case Studies, Faisal Alkhateeb, Eslam Al Maghayreh and Iyad Abu Doush (Ed.), InTech (2011), [Электронный ресурс]. – Режим доступа: http://www.intechopen.com/articles/show/title/decision-support-based-on-multi-agent-simulation-algorithms-with-resource-conversion-processes-appar (дата обращения: 02.12.12).
7. Aksyonov K. A., Bykov E. A., Smoliy E. F., Khrenov A. A. Industrial Enterprises Business Processes Simulation with BPsim.MAS // Proceedings of the 2008 Winter Simulation Conference (WSC 2008), December, 2008, Miami, USA, Pages 1669- 1677.
8. Aksyonov K.A., Smoliy E.F., Bykov E.A., Popov M.V., Dorosinskiy L.G. Development of decision support system «BPsim3»: Multi-service telecommunication networks design and modeling application // Proceedings of 10th International PhD Workshop on Systems and Control, Hluboka nad Vltavou, Czech Republic, 2009, Pages 112-117.
9. Aksyonov K.A., Smoliy E.F., Goncharova N.V., Khrenov A.A. Development of Multi Agent Simulation Modeling System “BPsim2” // Proceedings of the EUROCON 2007. The International Conference on "Computer as a Tool" – Poland, Warsaw. 2007. Page(s):2172 – 2176.

Введение

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

При проектировании мультиагентных интеллектуальных систем в основном используется холистический подход [4] и методы искусственного интеллекта, что позволяет учитывать эвристики [1–3, 6–7], используемые в предметной области, что в свою очередь позволяет находить эффективное решение многопараметрической задачи в условиях ограничений вычислительных ресурсов и времени принятия решения, однако задача поиска оптимального решения и выбора наиболее эффективного решения остается открытой .ристики, используемые в предметной области (что м Аппарат мультиагентных систем позволяет учесть . Мультиагентная модель процесса преобразования ресурсов [2, 6-7, 9] разработана на основе интеграции имитационного, экспертного, ситуационного и мультиагентного моделирования. В данной работе решается задача применения метода Беллмана (деревьев решений) при анализе альтернативных решений, получаемых для интеллектуального агента с помощью фреймовой экспертной системы. 

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

Постановка задачи: требуется спланировать массовую замену оборудования при выполнении гарантийных обязательств генерального подрядчика ООО «ИнсталСайтУрал» на сети сотовой связи оператора «Мегафон». Исходные данные следующие:

1. Имеются координаты 197 распределенных по региону объектов сети связи, на которых необходимо произвести замену оборудования Хуавей.

2. Имеется дорожная сетка (ГИС) с привязкой объектов к дорогам и матрицей расстояний между объектами.

3. Характер работы: получение на региональном складе в областном центре функциональных блоков (ФБ), выезд на объект, замена, возврат ФБ  на региональный склад – мастерскую по ремонту.

4. Состав бригады (инженер и водитель), передвигаются на легковом автомобиле вместительностью 16 блоков. Норматив  выполнения работ 1 бригадой на 1 объекте – 70 минут. Рабочий день от 8 до 12 часов. Заканчивается остановкой бригады в населенном пункте  для ночлега (остановка в гостинице).

5. Средняя скорость движения автомобиля – 40 км/ч.

6. Склад и бригады работают без выходных.

Условия решения задачи:

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

2. Выполнить расчёт необходимых ресурсов для выполнения работ в срок < 20 дней.

3. Оценить технико-экономические показатели планов.

Исходные данные для расчета (в приведении на 1 бригаду):

1) фонд оплаты труда (1 смена) – 2700 руб.;

2) налоги от фонда оплаты труда (1 смена) – 918 руб.;

3) гостиница – 1100 руб./сутки;

4) амортизация автомобиля – 980 руб./ в смену;

5) горюче-смазочные материалы 2,6 руб./км.

Применение фреймовых систем и объектно-ориентированного подхода

Для решения задачи использовалась система технико-экономического проектирования BPsim3 [1, 3, 6, 8], построенная в результате интеграции мультиагентных, фреймовых и продукционных систем, объектно-ориентированного подхода.

При проведении этапа системного анализа (построении концептуальной модели предметной области (КМПО)) в качестве основы описания структуры фрейм-концептов может быть использована диаграмма классов языка UML. Дальнейшее описание концептуальных графов (семантики) и наполнение данными полученной концептуальной модели образуют базу знаний [1, 3, 6]. Диаграмма классов задачи замены оборудования представлена на рис. 1.

Рис. 1. Диаграмма классов задачи замены оборудования в BPsim3

Для реализации визуального построителя МЛВ оболочки ЭС предложено использование диаграмм последовательности языка UML [1, 6]. Диаграмма последовательности графически описывает последовательность вызова методов между классами при решении определенной задачи (сценария). Данный подход позволяет визуально (в виде блок-схемы) описать ход решения задачи – последовательность вызовов процедур (методов демонов) от одного фрейма к другому.

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

Система ТЭП BPsim.MSN обеспечивает разработку интеллектуальных агентов поиска решения с помощью технологии проектирования визардов с использованием диаграмм последовательности на основе языка UML и языка управления базами данных Transact-SQL. Для реализации визуального построителя механизма вывода оболочки ЭС используются диаграммы поиска решений (расширение диаграмм последовательности языка UML).

Формы диалога системы технико-экономического проектирования «BPsim3», реализующие информационную поддержку принятия решения задачи замены оборудования реализуются в диалоговой ЭС. Для визуализации альтернативных путей поиска предлагается использовать объектное дерево поиска решений (рис. 2) [6].

Рис. 2. Объектное дерево поиска решения

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

Применение численного метода (деревьев решений Беллмана) для поиска альтернатив в экспертной системе

Для применения метода Беллмана [5] необходимо решить задачу конвертации диаграммы поиска решений в классическое дерево решений. Для преобразования фреймовой сети поиска решения (диаграммы поиска решения) в классическое дерево решений необходимо выполнить следующие действия:

1. Произвести классификацию фреймов на фреймовой сети. Для этой цели вводятся три группы фреймов:

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

б) ФК-альтернатив, к ним относится фрейм  «Бригады», если условие задачи подразумевает наличие нескольких субподрядчиков, то альтернативные условия применения бригад субподрядчиков представляются еще одним фрейм-концептом;

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

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

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

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

Рис. 3. Диаграмма поиска решений задачи замены оборудования

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

1. Выбор стратегии поиска.

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

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

4. Применение метода Беллмана [5]. После расчета всех альтернативных вариантов дерева поиска (означивания всех фреймов, относящихся к данному дереву решений). 

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

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

Рис. 4. Дерево решений задачи замены оборудования сети связи

Заключение

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

Для реализации поставленной задачи с точки зрения экономической целесообразности и запаса по времени на непредвиденные обстоятельства наиболее подходит вариант с 3 бригадами. Результаты экспериментов были использованы при планировании и выполнении работ по массовой замене оборудования связи. Исполнитель работ –  ООО «ИнсталСайтУрал» с учетом ограничений (по срокам выполнения работ в 15, запаса по времени 20 % на непредвиденные обстоятельства, ограничений по затратам в 300 000 руб.) выбрал вариант с 4-мя бригадами. С учетом ограничений, оптимальным решением по критерию срока проекта является вариант использования 4 бригад, а по критерию стоимости – привлечение 3 бригад.

Работа поддержана грантом РФФИ № 12-07-31045.

Рецензенты:

Поршнев Сергей Владимирович, д.т.н., профессор, заведующий кафедрой радиоэлектроники и информационных систем, ФГАОУ ВПО “Уральский федеральный университет им. первого Президента России Б.Н. Ельцина”, г. Екатеринбург.

Доросинский Леонид Григорьевич, д.т.н., профессор, заведующий кафедрой Информационных технологий, ФГАОУ ВПО “Уральский федеральный университет им. первого Президента России Б.Н. Ельцина”, г. Екатеринбург.


Библиографическая ссылка

Аксенова О.П., Аксенов К.А., Попов М.В., Неволина А.Л., Смолий Е.Ф. РЕШЕНИЕ ЗАДАЧИ ЗАМЕНЫ ОБОРУДОВАНИЯ СЕТИ СВЯЗИ НА ОСНОВЕ ИНТЕГРАЦИИ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПОДХОДА, ЭКСПЕРТНЫХ СИСТЕМ И ДЕРЕВЬЕВ РЕШЕНИЙ // Современные проблемы науки и образования. – 2012. – № 6.;
URL: http://www.science-education.ru/ru/article/view?id=7931 (дата обращения: 20.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074