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

Введение.

Глава 1. Обзор применений генетических алгоритмов в задачах САПР.

1.1 Обзор генетических алгоритмов.

1.1.1 Генетические алгоритмы, как инструмент стохастической оптимизации.

1.1.2 Эволюционные стратегии.

1.1.3 Генетическое программирование.

1.1.4 Эволюционный алгоритм.

1.1.5 Генетические алгоритмы.

1.1.5.1 История появления генетических алгоритмов.

1.1.5.2 Общие сведения.

1.1.5.3 Выбор способа кодирования.

1.1.5.4 Определение размера популяции.

1.1.5.5 Содержание стандартного генетического алгоритма.

1.1.5.6 Сходимость стандартного генетического алгоритма.

1.1.5.7 Эффективность генетических алгоритмов.

1.1.6 Применение генетических алгоритмов.

1.1.7 Символьная модель простого ГА.

1.2 Особенности задачи оптимизации вычислительных сетей при автоматизированном проектировании.

1.2.1 Особенности современных ВС. Корпоративные сети. Intranet-технологии.

1.2.2 Возможности сетевого администратора по оптимизации трафика в ВС.

1.3 Особенности задачи размещения элементов, как задачи автоматизированного проектирования.

1.3.1 Задача размещения.

1.3.2 Структура задачи размещения разногабаритных элементов.

1.3.3 Содержание задачи автоматизированного размещения элементов.

1.3.4 Традиционные алгоритмы размещения элементов.

1.4 Основные цели и задачи исследования ГА в САПР.

1.5 Критерии оценки результативности ГА в задачах САПР.

Глава 2. Модель вычислительной сети организации и адаптация генетических алгоритмов к оптимизации ВС.

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

2.2 Определение трафика вычислительных сетей.

2.3 Адаптация генетических алгоритмов к задаче оптимизации ВС.

2.4 Анализ применимости генетических алгоритмов разных видов к задаче оптимизации.

2.5 Вычислительная эффективность применения ГА для оптимизации ВС.

Глава 3. Адаптация мобильного ГА к задачам размещения.

3.1 Адаптация стандартного генетического алгоритма.

3.1.1 Кодирование решение - формирование хромосомы.

3.1.2 Инициализация исходной популяции решений.

3.1.3 Функция оптимальности.

3.1.4 Оператор селекции.

3.1.5 Оператор рекомбинации.

3.1.6 Оператор мутации.

3.1.7 Оператор формирования нового поколения.

3.1.8 Условия окончания поиска решения.

3.2 Мобильный генетический алгоритм.91.

3.2.1 Кодирование решение - формирование хромосомы.

3.2.2 Общая схема мобильного генетического алгоритма.

3.2.3 Инициализация исходной популяции решений.

3.2.4 Функция оптимальности.

3.2.5 Оператор селекции.

3.2.6 Операторы CUT и SPLICE.

3.2.7 Оператор мутации.

3.2.8 Оператор формирования нового поколения.

3.2.9 Условия окончания поиска решения.

Глава 4. САПР ВС и программа размещения элементов на основе ГА.

4.1 Программная система оптимизации трафика на основе измерений.

4.1.1 Программы мониторинга ВС. Измерение трафика. Особенности клиент-серверной реализации.

4.1.2 Представление ВС в форме, требуемой ГА.

4.1.3 Структура и функции программ оптимизации ВС.

4.1.4 Особенности объектно-ориентированной реализации САПР ВС.

4.2 Программная система оптимизации трафика на базе прогнозных значений.

4.2.1 Ограничения для проектируемой сети.

4.2.1.1 Виды коммуникационного оборудования.

4.2.1.2 Ограничение по структуре сети.

4.2.1.3 Оптимизация трафика с помощью переподключения узлов сети.

4.2.2 Общее описание программы.,.

4.2.3 Библиотека алгоритмов оптимизации.

4.2.4 Структура данных программы и реализация процедур оптимизации.

4.2.4.1 Параметры сети, закладываемые в программу.

4.2.4.2 Алгоритм оптимизации трафика.

4.3 Проектирование инструментальной среды исследования мобильных генетических алгоритмов.

4.3.1 Выбор среды реализации.

4.3.2 Структуры данных. Класс Популяция. Тип Flagterminate.

4.3.3 Реализация стандартного генетического алгоритма.

4.3.4 Реализация мобильного генетического алгоритма.

4.3.5 Структура программных модулей.

Глава 5. Анализ эффективности ГА в задачах САПР.

5.1 ГА в задачах оптимизации трафика ВС.

5.1.1 Анализ результатов оптимизации ВС вуз.

5.1.2 Проектирование ВС предприятий дорожного строительства на основе анализа бизнес-процессов.

5.1.2.1 Бизнес-процесс - реинжиниринг и проектирование ВС.

5.1.2.2 Анализ бизнес-процессов и проектирование ВС в ПТ'Ульяновскавтодор".

5.1.2.3 Описание Информационной системы предприятия дорожного строительства.

5.1.3 Проектирование ВС предприятия АОЗТ "Ульяновсккровля".

5.2 Моделирование трафика в ходе проектирования ВС. Вычислительные эксперименты по моделированию вычислительных сетей.

5.3 Мобильный ГА в задачах размещения. Результаты вычислительных экспериментов.

5.3.1 Набор задач размещения как тестовый набор.

5.3.2 Решение задач тестового набора с помощью стандартного генетического алгоритма.

5.3.3 Решение задач тестового набора с помощью мобильного генетического алгоритма.

5.3.4 Сравнение результатов экспериментов. Основные выводы из исследования.

5.3.5 Стоимость решения задачи размещения на предприятии.

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

Классической задачей синтеза структуры можно считать распространенную задачу размещения элементов на плоскости. В качестве задачи анализа выбрана задача оптимизации трафика вычислительной сети.

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

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

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

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

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

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

Целью диссертации является исследование эффективности применения ГА в задачах оптимизации трафика ВС и задачах размещения элементов.

Для достижения поставленной цели необходимо решить следующие задачи исследования.

1. Необходимо провести сравнительный анализ существующих методов.

2. Необходимо построить обобщенную математическую модель автоматизированного проектирования ВС.

3. Необходимо разработать методы, алгоритмы и программы оптимизации трафика в вычислительных системах.

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

5. Необходимо разработать методы, алгоритмы и программы размещения элементов методом мобильного ГА.

6. Необходимо провести вычислительные эксперименты по оптимизации трафика в вычислительных системах и сделать на их основе выводы об эффективности ГА в задачах анализа.

7. Необходимо провести вычислительные эксперименты по размещению разногабаритных элементов и сделать на их основе выводы об эффективности ГА в задачах синтеза структуры.

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

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

Основные выводы и итоги:

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

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

3. Адаптирован к задаче оптимизации топологии вычислительной сети генетический алгоритм. Адаптация включает формализацию функции оптимальности за счет моделирования трафика.

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

5. Разработана и реализована программная система оптимизации ВС методом генетических алгоритмов. Программа использована при проектировании ВС ряда организаций.

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

Мобильный генетический алгоритм, кроме того, обеспечивает более высокую

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

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

Заключение

1. Клир Дж. Системология. Автоматизация решения системных задач: Пер. сангл.- М.: Радио и связь, 1990.- 544 е.: ил. ISBN 5-256-00649-5.

2. Данелян Т.Я. Организация и функционирование больших информационныхсистем: Учебное пособие/ Моск. Экон.- стат. ин-т, М. 1997.

3. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР:

4. Учебник для вузов М.: Энергоатомиздат, 1987. - 400 е.: ил.

5. Дружинин В.В., Конторов Д.С. Системотехника.- М.: Радио и связь. 1985- 200 с.

6. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с франц.- М.: Мир,1991.-568 с.

7. Gero J.S. Creativity, emergence and evolution in design. Knowledge-Based Systems,

8. Vol. 9, N. 7, 1996, pg. 435-448

9. Jamshidi M. Fuz2y control of complex systems. Soft Computing Vol. 1 ,N. 1, 97 pg.42.56

10. Дюбуа Д., Прад А. Теория возможностей. Приложение к представлению знанийв информатике: Пер. с франц. М.? Радио и связь, 1990.- 288 с.

11. В.Б. Тарасов. От искусственного интеллекта к искусственной жизни: новыенаправления в науках об искусственном. Новости искусственного интеллекта. N4. с. 93-117

12. Борисов А.Н., Федоров И.П. Формирование технических решений на основе экспертных знаний. Изв. АН СССР, Техническая кибернетика 5 1990, с. 154164

13. Мелихов А.Н., Бернштейн Л.С., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука. Гл. ред. физ.-мат. лит., 1990.- 272 с,-ISBN 5-02-014144-5

14. Малышев Н.Г., Бернштейн Л.С., Боженюк А.В. Нечеткие модели для экспертных систем в САПР.-М.: Энергоатомиздат, 1991. -136 е.: ил. ISBN 5283-01592-0

15. Тартаковский A.M., Курносов В.Е. Информационные технологии проектирования оптимальных конструктивных форм на основе методов эволюционного моделирования. HTllllN 3-4, 1996 г., с. 3- 11

16. Zadeh L. What is soft computing? Soft Computing Vol. 1 ,N. 1, 97, pg. 1

17. Bonissone P.Soft computing: the convegence of emerging reasoning technologies, Soft Computing Vol. l,N.l, 97, pg.6-18

18. Борисов A.H., Алексеев A.B., Крумберг О.А. и др. Модели принятия решений на основе лингвистической переменной. Рига: Зинатне, 1982.

19. Броневич А.Г., Каркищенко А.Н. Вероятностные и возможностностные модели классификации случайных последовательностей / Под ред. Л.С. Бернштейна. Таганрог: ТРТУ, 1996. 193 с.

20. Аверкин А.Н. Нечеткое отношение моделирования и его использование для классификации и аппроксимации в нечетких лингвистических пространствах. // Изв. АН СССР. Техническая кибернетика.- 1982.- N 2.- с. 215-217

21. Zadeh L. A theory of approximate reasoning(AR)// Machine Intelligence,!979.-V. 9.-P. 149-194

22. И.З. Батыршин Методы представления и обработки нечеткой информации в интеллектуальных системах. Новости ИИ. N 5 1995, с. 9-65

23. Беллман Р., Заде Л. Принятие решений в расплывчатых условиях.- В кн.: Вопросы анализа и процедуры принятия решений.- М. Мир, 1976, с. 172-215

24. R.R. Yager Ordered weighted averaging aggregation operators in multi-criteria decision making, IEEE Trans, on Systems, Man and Cybernetics, 18(1988) 183190.

25. Саати P., Керне Д. Аналитическое планирование: организация систем. М. 1992

26. Zadeh L.A. Fuzzy sets as a basis for a theory of Possibility. Fuzzy sets and systems. 1978. V. 1.

27. Язенин A.B. Нечеткое математическое программирование. Калинин: КГУ, 1986

28. Язенин А.В. Нечеткие переменные и нечеткое математическое программирование // Модели выбора альтернатив в нечеткой среде. Рига, 1984.

29. Язенин А.В. О непрямых методах нечеткого математического программирования // Нечеткие системы: моделирование структуры и оптимизация. Калинин, 1987.i

30. Yazenin A.V. Fuzzy and stohastic programming. Fuzzy sets and systems. 1987. V. 22.

31. Nahmais S. Fuzzy variables in a random environment. Advances in fuzzy set theory. Amsterdam, 1979.

32. Язенин А.В. Модели возможностного программирования в оптимизации систем //Изв. АН СССР. Техническая кибернетика. 1991. №5.

33. Kraft D.H., Petry F.E. Fuzzy information systems: managing uncertainty in databases and information retrieval systems. Fuzzy sets and systems. Vol. 90, N 2, September 1,1997, 183-191i

34. Salton G., Allan J., Buckley C. ,Sighal A. Automatic analysis, theme generation and summerization of machine-readable texts, Science, 264(1994), 1421-1426.

35. Алиев P.А. Теоретические аспекты построения размытых систем управления // Изв. вузов СССР. Нефть и газ, 1981. №9. С.83-87.

36. Мельцер М.И. Диалоговое управление производством. М.: Финансы и статистика, 1983.

37. Baptitella L.F.B., Ollerra A. Fuzzy methodologies for interactive multicriteria optimization //IEEE Trans, on Syst., Man and Cybern. 1980. Vol. SMC-10. N7. P.355-365.

38. Zadeh L.A. Fuzzy sets // Inf. Contr. 1965. N8. P. 338-353.

39. Заде JI.А. Основы нового подхода к анализу сложных систем и процессов принятия решений // Математика сегодня. М.: Знание. 1974. С.5-49.

40. Заде JI.A. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976.

41. Шапиро Д.И. Принятие решений в системах организационного управления: использование расплывчатых категорий. М.: Энергоатомиздат, 1983.

42. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Наука, 1981.t

43. Негойце К. Применение теории систем к проблемам управления. М.: Мир, 1981.

44. Янбых Г.Ф., Столяров Б.А. Оптимизация информационно-вычислительных систем. М.: Радио и связь, 1987.

45. А.Н. Скурихин Генетические алгоритмы. Новости искусственного интеллекта, N4, 1995, с. 6- 17

46. Системы автоматизированного проектирования в радиоэлектронике: Справочник/Е.В. Авдеев, А.Т. Еремин, И.П. Норенков, М.И. Песков; Под ред. И.П. Норенкова.- Радио и связь, 1986.- 368 е.: ил:

47. А. В. Алексеев, А.Н. Борисов, Э.Р. Вилюмс, Н.Н. Слядзь, С.А. Фомин Интеллектуальные системы принятия проектных решений.- Рига: Зинатне, 1997.- 320 е., ил.

48. L.A. Zadeh Fuzzy sets as basis for a theory of possibility. Fuzzy Sets and Systems, 1,3-28.

49. Э. В. Попов, Евсеев O.B. Технологии реинжиниринга бизнес-процессов. Сб. науч. трудов Всероссийской научно-прак. конф. "Реинжиниринг бизнес-процессов предприятий на основе современных информационных технологий" , МЭСИ, Москва, 1997, с. 6-18.

50. Hammer М., Champy J. Reengineering the Corporation. A Manifesto for Busness Revolution. Harper Business, 1993

51. Ярушкина Н.Г. Мягкий метод анализа иерархий в системах принятия решений //Междунар. семинар "Мягкие вычисления-96", Казань, 1996 , с. 219-221

52. Yarushkina N. Soft method of hierarchy analysing for decision making support system//Междунар. семинар "Мягкие вычисления-96", Казань, 1996 , с. 222

53. Ярушкина Н.Г., Шишкин В.В. Экспертная система анализа финансово-хозяйственной деятельности предприятия // Всеросс. конф. "Культура, нраственность и экономика", Ульяновск: УлГТУ, 1996, с. 71-73

54. Yarushkina N. An analysis of Economic Data Diagramms Based on Fuzzy Intervalsiin an Expert System of Economical Analysis // Pattern Recognition and Image Analysis. Vol. 6, N. 2, 1996, p. 329-330

55. Yarushkina N., Shishkin V., Merkulova T. Vizualization of the Enterprise Economy State in an Expert System of Economic Analysis // Pattern Recognition and Image Analysis. Vol. 6, N. 2, April-June 1996, p. 331

56. Ярушкина Н.Г., Пирогов B.B. Методы и средства проектирования информационно- вычислительных сетей // 31-ая науч.-тех. конф. УлГТУ, Ульяновск: УлГТУ, 1997 , с. 52

57. Ярушкина Н.Г., Краснов С.В. Об одном подходе к оптимизации локальнойtвычислительной сети на этапе проектирования // Науч.-прак. конф. "Наука -производству. Конверсия сегодня", Ч. 2,Ульяновск, 1997 ,с. 84-85

58. Ярушкина Н.Г., Пирогов В.В. Оптимизация ресурсов информационно-вычислительной сети в условиях неопределенности // 2-я Междунар. науч.-тех. конф. "Интерактивные системы: Проблемы человеко- компьютерного взаимодействия". Ч. 1. Ульяновск, 1997 , с. 52-53

59. Yarushkina N. Soft hierarchy analysing method for economic expert system // Proceedings of Seventh International Fuzzy Systems Association World Congress, Vol. 3, June 1997, pg. 80-82

60. Ярушкина Н.Г., Суркова Е.В. Анализ финансово-хозяйственной деятельности предприятия в среде Microsoft office // Науч.-пр. конф. с междунар. участием "Новые методы, средства и технологии в науке, промышленности и экономике". Ульяновск, 1997

61. Yarushkina N. Soft Hierarchy Analysing Method for Economic Experts System // Proceeding of 5th European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1997, pg. 980-981

62. Yarushkina N. Soft Computing in an Experts Systems // Proceeding of 1th International Conference on Soft Computing and Measurements St. Petersburg, 1998, Vol. l,pg. 300-304