Автоматизация разработки алгоритмических моделей на основе алгоритмических сетей: на примере логистической транспортной системы тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Васильченко, Дмитрий Сергеевич

• Васильченко, Дмитрий Сергеевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Васильченко, Дмитрий Сергеевич

Введение.

Глава 1. Анализ основных подходов к автоматизации моделирования.

1.1. Методы представления моделей.

1.2.Системы автоматизации моделирования.

1.3. Обобщённый технологический процесс моделирования.

1.4.Выводы и результаты.

Глава 2. Теоретические основы алгоритмического моделирования на основе обобщённых алгоритмических сетей.

2.1. Алгоритмическое моделирование и методы представления алгоритмов.

2.2. Основные понятия алгоритмических сетей.

2.3.Алгоритмические сети со ссылками в вершинах. Алгоритмы, реализованные при помощи обобщённых алгоритмических сетей.

2.4. Синтаксис языка обобщённых алгоритмических сетей.

2.5. Выводы и результаты.

Глава 3. Основные алгоритмы системы автоматизации моделирования на основе обобщённых алгоритмических сетей.

3.1. Графический редактор.

3.2. Подсистема подготовки проведения вычислительного эксперимента.

3.3. Подсистема проведения вычислительного эксперимента.

3.4. Анализ моделей и процедур принятия решений.

3.5. Выводы и результаты.

Глава 4. Реализация системы поддержки алгоритмического моделирования на основе обобщённых алгоритмических сетей.

4.1. Постановка задачи проектирования системы поддержки моделирования.

4.2. Особенности системы и режимы работы.

4.3. Генерация системы.

4.4.Технология работы автоматизации системы поддержки алгоритмического моделирования.

4.5. Пример модели логистической транспортной системы в алгоритмических сетях.

4.6. Решённые задачи.

4.7. Выводы и результаты.

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

Актуальность работы.

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

Цели и задачи диссертации.

Целью диссертации является повышение эффективности на этапе разработки структуры модели и её программной реализации.

В соответствии с поставленной целью сформулированы основные задачи, решаемые в диссертации:

1. Анализ существующих систем автоматизации моделирования.

2. Расширение и формализация класса алгоритмов, представимых в формализме алгоритмических сетей.

3. Модификация синтаксиса алгоритмических сетей для представления расширенного класса алгоритмов.

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

Объектом исследования является технологический процесс разработки математических моделей на основе алгоритмических сетей. з

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

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

На защиту выносятся:

1. Аппарат алгоритмических сетей со ссылками в вершинах.

2. Технологический процесс моделирования на основе обобщённых алгоритмических сетей.

3. Алгоритм распознавания изоморфизма АС

4. Функционально-организационная структура системы автоматизации моделирования на основе обобщённых алгоритмических сетей.

Научная новизна заключается в следующем:

1. Произведено теоретическое обоснование класса алгоритмов, представимых в алгоритмических сетях со ссылками в вершинах.

2. Сформулирован синтаксис языка алгоритмических сетей со ссылками в вершинах.

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

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

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

Практическая значимость.

Программные средства поддержки алгоритмического моделирования на основе алгоритмических сетей со ссылками в вершинах, встроенные в одну из версий системы КОГНИТРОН.

Система была внедрена в следующих организациях:

Санкт-Петербургский государственный университет водных коммуникаций;

Санкт-Петербургский институт информатики и автоматизации Российской академии наук.

Апробация работы.

Основные положения и результаты диссертационной работы докладывались, обсуждались и получили одобрение на научно-практических конференциях: Региональная информатика-2008, ИММОД-2009 (Санкт-Петербург), Всероссийская школа-семинар «Прикладные проблемы управления макросистемами», Апатиты, 2010, семинары на кафедре «Вычислительные системы и информатика» СПГУВК.

Публикации.

По теме диссертации опубликованы 5 научных статей, в том числе одна в издании, рекомендованном ВАК РФ.

Объём и структура работы.

Диссертация состоит из введения, четырёх глав, заключения и списка использованных источников из 100 наименований. Общий объём работы составляет 144 страницы, в том числе 70 рисунков и 3 таблицы.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Васильченко, Дмитрий Сергеевич

4.7. Выводы и результаты

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

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

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

Были использованы ряд дополнительных возможностей для удобства построения моделей: изменение масштаба модели, вывод на печать, экспорт модели в Microsoft Word и возможность отключения отображения сетки поля. Генерация этой системы выполняется автоматически без вмешательства со стороны пользователя.

Заключение

В работе получены следующие основные результаты и сделаны выводы:

1. Произведён анализ существующих систем автоматизации моделирования и предыдущих версий системы КОГНИТРОН.

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

3. Рассмотрен процесс моделирования на основе обобщённых алгоритмических сетей.

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

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

6. Разработаны модули для системы автоматизации КОГНИТРОН, обеспечивающих возможность работать с обобщёнными и распределёнными сетями.

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

8. Использован ряд дополнительных возможностей для удобства построения моделей: изменение масштаба модели, вывод на печать, экспорт модели в Microsoft Word и возможность отключения отображения сетки поля.

9. Генерация этой системы выполняется автоматически без вмешательства со стороны пользователя.

Список литературы диссертационного исследования кандидат технических наук Васильченко, Дмитрий Сергеевич, 2011 год

1. Бирюков Б.В. Кибернетика и методология науки. М.: Наука, 1974, 412 с

2. Курилов А.Е., Поспелов Г.С. Процедуры и алгоритмы формирования комплексных программ. М.: Наука, 1985,423 с.

3. Берг А.И. Управление, информация, интеллект. М.: Мысль, 1976, 383 с.

4. Пономарёв В.М. Алгоритмические модели в задачах исследования систем. М.: Наука, 1980, с. 4-8

5. Вендров А.М., "CASE-технологии. Современные методы и средства проектирования информационных систем", 1997

6. Кобозева А.А. Применение сингулярного и спектрального разложения матриц в стеганографических алгоритмах, 2006, с.74-83.

7. Колесов Ю.Б. Объектно-ориентированное моделирование сложных динамических систем. СПб.: Изд-во СПбГПУ, 2004. - 239 с.

8. Наместников A.M. Разработка имитационных моделей в среде MATLAB: Методические указания для студентов специальностей 01719, 351400. -Ульяновск: УлГТУ, 2004. 72 с

9. Бигдан В.Б., Гусев В.В., СТАНОВЛЕНИЕ И РАЗВИТИЕИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ В УКРАИНЕ

10. Жуков К.Г. Моделирование последовательно-параллельных интегрирующих структур. Компьютерное моделирование 2002:Труды Междунар. Науч.-техн. конф. СПб.: Изд-во СПбГПУ, 2002.230 стр.

11. Прицкер А., Введение в имитационное моделирование и язык СЛАМ II, М: Мир, 1987, 646 с.

12. Иничёва М.А., Колесов Ю.В., Model Vision для Windows. Спб, 1995

13. Using Altia Design with Statemate MAGNUM, 2000

14. Henzinger Т., Ho P-T.: HyTech: The Cornell Hybrid Technology Tool.Hybrid Systems II, Lecture Notes in Comp.Sci 999, p.265-293. Springer-Verlag, 1995.

15. Лазарев Ю., Моделирование процессов и систем в MatLab, Спб, 2005, 512 с.

16. Михайлов В.В., Марлей В.Е. Алгоритмические сети и их применение: Учебное пособие. СПб.: ГУАП, 2004. - 80 с.

17. Пономарёв В.М., Александров В.В., Алгоритмические модели как средство автоматизации исследований// Автоматизация исследований и проектирования, М.: 1978, с. 5-8

18. Иванищев В.В., Алгоритмический базис для описания механизмов экономики.// Алгоритмические модели в автоматизации исследований. М.: Наука, 1980, с. 13-16.

19. Иванищев В.В., Марлей В.Е., Морозов В.П. Язык алгоритмических сетей. Препринт №63. Л.: ЛНИВЦ АН СССР, 1984-37с.

20. Колдаев В.Д., «Основы алгоритмизации и программирования», ИД «ФОРУМ»: ИНФРА-М, М. ,2006 г.;

21. Могилев A.B. «Информатика: Учеб. пособие для студ. пед. вузов», 3-е изд., М. :

22. Издательский центр «Академия», 2004 г.;138

23. Стариченко Б.Е., Теоретические основы информатики: Учеб. пособие для вузов. 2-е изд., М.: Телеком, 2004 г.

24. Иванищев В.В., Марлей В.Е., Введение в теорию алгоритмических сетей. СПб.: изд-во СПбГТУ, 2000 г., 180 с.

25. Марлей В.Е., Морозов В.П. Интерпретация алгоритмических сетей как языковых конструкций.//Проблемы автоматизации в научных и производственных процессах. М.: Наука, 1985 г., с. 40-46.

26. Иванищев В.В., Егоров М.Б., Логико-графический предпроцессор в системах автоматизации моделирования. // Проблемы автоматизации в научных и производственных процессах. М.: Наука, 1985 г., с. 9-14.

27. Марлей В.Е., Морозов В.П. Методы и системы автоматизации в задачах науки и производства. М.: Наука, 1986, с. 23-34

28. Иванищев В.В. Автоматизация моделирования потоковых систем. JL: Наука, 1986, 142 с.

29. Иванищев В.В., Игнашкина Е.М., Марлей В.Е., Пономарёв В.В. Укрупнённая алгоритмическая потоковая модель. Л.: ЛНИВЦ АН СССР, 1981, 48 с.

30. Иванищев В.В., Мовчан B.C., Пономарёв В.В. Структура алгоритмического описания отраслей непроизводственной сферы региона // Алгоритмические модели в автоматизации исследований. М.: Наука, 1980, с. 46-50

31. Иванищев В.В., Корсакова Л.И. Задачи оптимизации на алгоритмических сетях. // Проблемы автоматизации научных и производственных процессов. М.: Наука, 1985, с. 23-30

32. Морозов В.П., Фёдоров В.П. Укрупнённая алгоритмическая модель «автомобильный транспорт» региона. // Вычислительные системы и методы автоматизации исследований и управления. М.: Наука, 1982, с 14-16

33. Михайлов В.В. Алгоритмическая потоковая модель биотического блока экосистемы крупного озера. // Проблемы автоматизации в научных и производственных процессах. М.: Наука, 1985, 40-45

34. Иванищев В.В., Марлей В.Е. Типовые конструкции алгоритмических сетей. // Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с 7-25

35. Морозов В.П., Ионова Л.С. Алгоритмические модели годового планирования республики. // Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с 131-139

36. Марлей В.Е. Алгоритмические сети и параллельные граф-схемы алгоритмов. // Проблемы информационной технологии и интегральной автоматизации производства. Л.: Наука, 1989, с 130-136

37. Морозов В.П. Задачи на вычисление при наличии ограничений. Метод обращения. // Алгоритмическое моделирование: инструментальные средства и модели. СПб.: СПИИРАН, 1992, с 112-137.

38. Бомбина-Михайлова Е.В., Игнашкина Е.М. Диалоговая процедура принятия решений на основе алгоритмической потоковой модели. // Вычислительные системы и методы в автоматизации исследований и управления. М.: Наука, 1982, с. 11-13

39. Коплан-Дикс И.С., Игнашкина Е.М. Алгоритмическая модель управления потоками фосфора на водосборе Ладожского озера. JL: ЛНИВЦ АН СССР, 1984,42 с.

40. Тубольцева В.В. Система автоматизации моделирования экологических объектов ЭКО-САПФИР. // Проблемы обработки информации и интегральной автоматизации производства. Л.: НАУКА ЛО, 1986, с. 102-110

41. Ревайкин A.C., Быстрицкий С.П. Модель экономического и социального развития «Край-85». Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с. 140-147

42. Ширков Э.И., Коломийцев Ф.И. Алгоритмическая потоковая модель рыбохозяйственного комплекса.// Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с. 162-172

43. Тарасов Е.А., Корсакова Л.И. Алгоритмическая модель природно-экономической системы бассейна реки Камчатка.// Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с. 185-189

44. Михайлов В.В., Тубольцева В.В. Особенности системы автоматизации экологического моделирования.// Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с. 26-31

45. Машистов С.А., Дедков A.B. Моделирование дискетного производства на основе потоковых алгоритмических сетей.// Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с 114-130

46. Михайлов В.В., Казанский А.Б. Алгоритмическая модель озерного рыбопитомника. Л.: ЛИИАН, 1989, 27 с.

47. Иванищев В.В. Когнитивный анализ процесса построения алгоритмических сетей.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 5-27

48. Михайлов В.В. Матричное расширение языка алгоритмических сетей.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 28-46

49. Егоров М.Б. Особенности программной реализации системы САПФИР 2.0.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 47-77

50. Каширская Е.В. Алгоритм планирования блочной сети.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 97111.

51. Иванищев В.В. Алгоритм обеспечения функциональной полноты экспертных знаний.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 138-151

52. Попов В.Ю., Тубольцева В.В. Алгоритмическая модель двухуровневой сети снабжения и задачи управления.// Алгоритмическое моделирование: инструментальные средства и модели. СПб: СПИИРАН, 1992, с. 165-170

53. Марлей В.Е. Эквивалентность в алгоритмических моделях и алгоритмических сетях.// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 75-76

54. Иванищев В.В., Марлей В.Е, Михайлов В.В. Рекуррентная модель технологического процесса в терминах матричного представления.// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 61-63

55. Морозов В.П. Процедура поддержки принятия решений в инструментальной системе моделирования Когнитрон.// V Санкт-Петербургская международная конференция «Региональная Информатика-96». Тезисы докладов. Часть 2. СПб: 1996, с. 231

56. Королёв О.Ф., Марлей В.Е. Вычисления на распределённых алгоритмических сетях.// Материалы первой международной конференции по проблемам самоорганизации и управления в сложных коммуникационных пространствах. СПб: 1997, с. 58-60

57. Марлей В.Е. Алгебра алгоритмических сетей. Юбилейный сборник трудов СПИИРАН. СПб: Наука, 1998.

58. Иванищев И.В., Морозов В.П. Инструментальная система автоматизации моделирования Когнитрон.// Информационные технологии и вычислительные системы. СПб: 1998

59. Иванищев В.В., Михайлов В.В. Алгоритмическая модель абиотического блока экосистемы крупного озера.// Проблемы автоматизации научных и производственных процессов. М.: Наука, 1985, с. 30-42

60. Иванищев В.В., Евсеев A.B., Кудасов В.И. Процедура прогнозирования развития отрасли на базе алгоритмической модели.// Системы и методы автоматизации научных исследований. М.: Наука, 1981, с. 4-11

61. Иванищев В.В., Михайлов В.В. Распределённые модели: принципы построения.// Системы автоматизации в науке и производстве. М.: Наука, 1984, с. 5-10

62. Иванищев В.В. Математическое описание алгоритмических сетей.// Системы автоматизации в науке и производстве. М.: Наука, 1984, с. 30-40

63. Иванищев В.В., Михайлов В.В., Селезнёва В.В. Матричное расширение системы автоматизации для решения многомерных задач.// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 133-134

64. Быков Я.А., Иванищев В.В. Теоретико-множественные операции на алгоритмических сетях.// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 126

65. Быков Я.А. Графический интерфейс в системе представления системы автоматизации моделирования «КОГНИТРОН» .// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 124-125

66. Костельцев A.B. Метод повышения точности моделирования динамических процессов в языке алгоритмических сетей.// IV Санкт-Петербургская международная конференция «Региональная Информатика-95». Тезисы докладов. Часть 1. СПб: 1995, с. 69-70

67. Михайлов В.В., Мордовии В.Ю. Биоклиматическая модель популяции диких северных моделей.// Освоение севера и проблема рекультивации. Доклады 2-ой Международной Конференции. Сыктывкар: 1994, с. 218-228.

68. Михайлов В.В. Комплексирование взаимно противоречивых алгоритмических моделей.// Материалы первой международной конференции по проблемам самоорганизации и управления в сложных коммуникационных пространствах. СПб.: 1997, с. 60-61

69. Михайлов В.В., Иванищев В.В. База сельскохозяйственных моделей для решения задач управления фермерским хозяйством.// V Санкт-Петербургская международная конференция «Региональная Информатика-96». Тезисы докладов. Часть 2. СПб: 1996, с. 259-260

70. Меныпуткин В.В. Язык моделирования гидробиологических процессов.// Гидробиологический журнал. 1975, Т.11, №6, с.271-276

71. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Советское радио, 1972, 280 с

72. Берс A.A. Операторные структуры (расширяемая модель расширяемого языка).// Теория программирования. Часть 2. Труды симпозиума. Новосибирск: ВЦ СО АН СССР, 1972, с. 44-81

73. Вальковский В.А., Малышкин В.Э. Синтез параллельных программ и систем на вычислительных моделях. Новосибирск: Наука СО, 1988, 127 с.

74. Кругов А.П., Петров A.A., Поспелов И.Г. Математическая модель воспроизводства в централизованной плановой экономики с товарно-денежными отношениями. М.:ВЦ АН СССР, 1989,49 с.

75. Нариньяни A.C. Модель или алгоритм: новая парадигма информационной технологии.// Информационные технологии, №4,1997, с. 11-16

76. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971,416 с.

77. Оре О. Теория графов. М.: Наука, 1968, 440 с.

78. Лавров С.С., Залогова Л.А., Петрушина Т.И. Принципы планирования решения задач в системе автоматического синтеза программ.// Программирование, №3, 1982, с. 35-43

79. Бусленко Н.П., Калашников В.В., Коваленко И.И. Лекции по теории сложных систем. М.: Советское радио, 1973, 440 с.

80. Евреинов Э.В., Прангеншвили И.В. Цифровые автоматы с настраиваемой структурой. М.: Энергия, 1974,240 с.

81. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука, 1990.

82. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

83. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1975

84. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высш. шк., 1976.

85. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969.

86. Зыков A.A. Основы теории графов. М.: Наука, 1984.

87. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.

88. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

89. Лекции по теории графов. В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. М.: Наука, 1990.

90. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

91. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

92. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

93. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные понятия и приложения. М.: Наука, 1987.

94. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985