ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

Методика и программа для статистического исследования алгоритмов разрезания графов

Статья опубликована в выпуске журнала № 1 за 2007 год.[ 23.03.2007 ]
Аннотация:
Abstract:
Авторы: Павленко А.В. () - , , , Пикулин В.В. (pvv@pgta.ru) - Пензенская государственная технологическая академия, , , кандидат технических наук
Ключевое слово:
Ключевое слово:
Количество просмотров: 6268
Версия для печати
Выпуск в формате PDF (1.53Мб)

Размер шрифта:       Шрифт:

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

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

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

Правила выбора формулируются таким образом, чтобы обеспечить формирование сильно связанных подграфов (табл. 1), однако эвристические правила не гарантируют формирования оптимального (по заданным показателям) результата. Разработка математических моделей для оценки качества эвристических алгоритмов (по показателям назначения) представляет значительную сложность, поэтому целесообразно использовать методы статистических исследований. Авторами разработана соответствующая методика и инструментальное программное средство «Graph­Tool».

Методика исследования включает в себя определение процедуры и показателей оценки качества решений. Процедура исследования включает следующие операции:

1)  задание характеристик генерируемых ориентированных взвешенных мультиграфов (условий задач);

2)  выбор алгоритмов для решения задачи разрезания;

3)  генерация графа с заданными характеристиками;

4)  решение задачи разрезания сгенерированного графа по всем выбранным алгоритмам;

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

6)  переход к п. 3 (генерация нового графа) заданное количество раз;

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

Для оценивания качества результатов решения задач использованы следующие показатели:

-    отношение суммарного веса внутренних дуг к суммарному весу внешних дуг для каждого подграфа,

-    отношение количества внутренних дуг к количеству внешних дуг для каждого подграфа,

-    количество подграфов,

-    среднее число вершин в подграфе,

-    среднее число дуг в подграфе,

-    интегральный показатель эффективности.

В качестве интегрального показателя используется аддитивный показатель, включающий частные показатели с весами, устанавливаемыми экспертным путем: , где ki – весовые коэффициенты, k>0, ; Ri – нормированный частный показатель.

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

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

В разработанном программном средстве исследования алгоритмов введен набор характеристик, определяющих алгоритм (табл. 1).

Таблица 1

Характеристики алгоритмов

Характеристика

Варианты характеристики

Обозначение

1.  Показатель результата разрезания графа

максимальная сумма весов дуг (максимальное количество дуг) в подграфе

Р11

максимальная связность вершин (поиск сильных компонент)

Р12

2.  Правило выбора начальной вершины

вершина с максимальной суммой весов дуг

Р21

вершина с максимальным количеством дуг

Р22

3.  Критерий включения вершин в подграф

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

Р31

максимальное количество дуг внутри подграфа

Р32

4.  Критерий выбора вершины для включения в подграф ее окрестности или критерий выбора вершины для нового подграфа

максимальный вес дуг к нераспределенным вершинам графа

Р41

максимальное количество дуг к нераспределенным вершинам графа

Р42

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

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

-    соотношение количества дуг и количества вершин должно соответствовать связному графу;

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

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

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

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

-    частота формирования алгоритмом самого эффективного решения;

-    среднее значение одного из показателей по каждому алгоритму;

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

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

Таблица 2

Алгоритмы решения задач разрезания графов

Характеристика алгоритма и ее значения

Вариант алгоритма

1

2

3

4

5

6

Показатель результата разрезания графа:

Р11

Р12

           

Способ выбора начальной вершины:

Р21

 

Р22

       

 

Критерий присоединения вершин в подграф:

Р31

 

 

Р32

 

 

   

Критерий выбора вершины для включения в подграф ее окрестности:

Р41

   

 

Р42

 

 

 

Критерий выбора вершины для нового подграфа:

Р41

   

 

Р42

 

   

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

Таблица 3

Значения условий задач

Характеристика графа

Значение характеристики

1

2

Количество вершин

100

100

Количество дуг

115

135

Максимальное количество вершин в одном подграфе

9

9

Минимальное и максимальное значение весов дуг в графе

10 .. 200

10 .. 200

Минимальное и максимальное значение меток вершин в графе

0 .. 50

0 .. 50

Таблица 4

Результаты испытаний эффективности алгоритмов

Номер тестового набора данных

Номер алгоритма

1

2

3

4

5

6

Количество наилучших решений алгоритма, %

1

67

2

2

4

1,5

23,5

2

56

1,5

5,5

7,5

5

24,5

Среднее значение показателя "Вес внутренних дуг / Вес внешних дуг"

1

1,902

1,367

1,434

1,712

1,488

1,787

2

1,102

0,815

0,886

0,961

0,929

1,026

Среднее значение показателя "Количество внутренних дуг / Количество внешних дуг"

1

1,352

1,334

1,336

1,334

1,323

1,343

2

0,822

0,806

0,813

0,81

0,814

0,816

Среднее значение интегрального показателя

1

161,03

128,31

132,34

148,97

135,15

153,78

2

96,62

78,77

83,29

87,66

85,95

91,88

Программа «GraphTool» реализована в среде программирования Delphi; структура программы приведена на рисунке (см. выше), где овалы обозначают объекты для диалога, а прямоугольники – основные процедуры.

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

Проведенные на вышеопределенном наборе алгоритмов исследования позволили установить, что наиболее эффективными по указанным показателям являются алгоритмы №1 (набор характеристик: Р11 Р21 Р31 Р41) и №6 (набор характеристик: Р11 Р21 Р31 Р42).


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=413
Версия для печати
Выпуск в формате PDF (1.53Мб)
Статья опубликована в выпуске журнала № 1 за 2007 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: