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

Введение

Основные обозначения, принятые в работе

1 Многорежимные системы и задача синтеза

1.1 Многорежимные системы . ,.

1.2 Общая постановка задачи синтеза.

1.3 Общие подходы к решению задачи синтеза МРС

1.4 Однокаскадные схемы.

1.5 Двухкаскадные схемы.

1.6 Многокаскадные схемы.

1.7 Описание программных реализаций задач синтеза.

2 Статистическое исследование и программная реализация случайного поиска

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

2.2 Статистическое исследование метода случайного поиска.

2.3 Различные модификации случайного поиска.

2.4 Описание диалогового программного комплекса глобальной оптимизации "OPTIMUM"

3 Многокритериальная оптимизация

3.1 Общая постановка задачи и метод решения

3.2 Статистические исследование метода решения.

3.3 Описание диалогового программного комплекса многокритериальной оптимизации "PARET0".

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

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

Практическое применение MPC находят для синтеза механических коробок перемены передач [22,34, 43, 55, 67], многофункциональных логических модулей [38], структурно перестраиваемых приборов СВЧ [15, 36], радиоэлектронных [15, 36] устройств и др.

В первой главе приводится краткое описание систем со структурным управлением, у которых процесс функционирования зависит от дискретной настройки системы путем изменения ее структуры на определенный режим работы. Такие системы еще называются многорежимными (MPC), или структурно управляемыми, системами (СУС) [54]. Для их описания используются сетевые модели [39, 54].

Приводится общая постановка задачи синтеза MPC и описываются подходы ее решения.

Рассматриваются задачи синтеза многорежимных систем, состоящих из двухполюсных элементов. При этом используются подходы, позволяющие сократить перебор на множестве дискретных структур. Предлагается модификация одного алгоритма минимизации элементов управления в схемах с максимальным числом режимов при фиксированном количестве функциональных элементов. Описывается разработанное программное обеспечение, реализующее разработанные алгоритмы синтеза на ЭВМ с использованием объектно-ориентированного подхода.

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

В заключении второй главы описываются основные принципы построенного диалогового программного комплекса глобальной оптимизации "OPTIMUM", из которых можно выделить, прежде всего, применение такого средства программирования как DLL (Dinamic Link Library). Основные цели использования DLL: представление задач оптимизации на языке ЭВМ, программное разбиение задачи оптимизации на модули целевой функции и ограничений с дальнейшим их независимым друг от друга использованием, решение важной проблемы совместимости программного комплекса с модулями программ пользователя.

Третья глава посвящена многокритериальной оптимизации. В ней предлагается и исследуется метод построения множества Парето.

В ее заключении проводится описание специально разработанного диалогового программного комплекса многокритериальной оптимизации "PARETO". Особое внимание при этом уделено использованию в многокритериальной оптимизации принципов динамически подключаемых библиотек DLL.

Проведенные исследования показали высокую практической эффективность всех рассмотренных здесь методов оптимизации. Именно поэтому было принято решение о создании технологии ROOT - Red Organization of Optimization Technology, объединяющей все исследованные методы с целью решения различных задач оптимизации, возникающих на практике.

Для общедоступности к технологии ROOT построен специальный Интернет-сайт, описание которого находится в приложении.

К - множество действительных чисел; 2 - множество целых чисел; N - множество натуральных чисел; х\Р(х)} - множество всех ж, удовлетворяющих условию Р(х) ; |Л| - мощность множества А ; т : п~ множество натуральных чисел от то до га, т < п ; {а, с,.} = (а, 6, с,.) - множества; где А = {¿ь г2,., ¿|А|} Ст:п ; А С В - нестрогое вхождение А в В ; А С В - А собственное подмножество В ; 2г - множество всех подмножеств из 2, ;

- множество всех /¿-элементных подмножеств из Ъ ; / : X А - отображение / множества X в А ; дХ jjjj . х —у А} - множество всех возможных отображений из X в А]

Основные обозначения, принятые в работе у а\ а2 а3 def гл; 1 2 3

Выводы, касающиеся сходимости СП здесь аналогичны предыдущим. Кривые сходимостей расположились на рис. 2.2.8 в очередности, приведенной в табл. 2.2.3

Далее приводится график для функции 6, аналогичный графику на рис. 2.2.7. В отличии от графика на рис. 2.2.7 здесь кривые сходимости не пересекаются.

Рис. 2.2.9. Сходимость СП для функции 6 в зависимости от

Подтверждением эффективности используемого здесь случайного поиска может послужить ознакомление с работой [19], где оптимизация функции б выполнялась с помощью генетических алгоритмов.

Функция 7. Ф(Х1,Х2,Х3,Х4) = вт2^) + £ ((^ - 1)2(1 + 10эт2(71-^+1))) 1

4 - I)2, 2,- = 1 - (11 - 20х{)/4, ¿€1:4, Ф(0.55,0.55,0.55,0.55) = 0.

Функция 7 является также многоэкстремальной и имеет в области поиска 625 локальных минимумов.

На рис. 2.2.10 представлена сходимость СП в зависимости от числа обращений к вычислению целевой функции. Параметры случайного поиска, соответствующие кривым 1-5, приведены в табл. 2.2.4.

Рис. 2.2.10. Сходимость СП для функции 7 в зависимости от nstep.

Заключение

В диссертации:

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

- разработаны алгоритмы, позволяющие сэкономить машинное время при решении различных задач синтеза;

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

- разработан программный комплекс глобальной оптимизации с развитым пользовательским интерфейсом, использующий технологию DLL;

- предложен и статистически исследован метод получения парето-оптимальных точек;

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

- все исследованные методы, объединенные под технологией ROOT выведены для всеобщего обозрения и использования в Глобальную Сеть Интернет.

1. Абакаров А.Ш., Сушков ЮА. Интерактивная система стохастической многокритериальной оптимизации / / Тезисы докладов Первого Всероссийского Симпозиума по прикладной и промышленной математике, Сочи, октябрь, 2000. - Москва. 2000. - С.117.

2. Абакаров А.Ш., Сушков Ю.А. Синтез структурно управляемых систем // Тезисы докладов Второго Всероссийского Симпозиума по прикладной и промышленной математике, Самара, июль, 2001. Москва. 2001. - С.71.

3. Абакаров А.Ш., Сушков Ю.А. Программный комплекс глобальной оптимизации // Тезисы докладов Восьмой Всероссийской школы-коллоквиума по стохастическим методам, Йошкар-Ола, декабрь, 2001. Москва. 2001. - С.735.

4. Абакаров А.Ш., Сушков Ю.А. Программный комплекс многокритериальной оптимизации // Проблемы оптимизации дискретных систем. СПб., СПбГУ, 2001. - С.60-69.

5. Абакаров А.Ш. (научный руководитель проф. Сушков Ю.А.) Инженерный программный комплекс глобальной оптимизации // Тезисы конференции Технические науки промышленностисеверо-западного региона, Санкт-Петербург, февраль, 2001. -СПб. 2001. -С.8.

6. Абакаров А.Ш., Сушков Ю.А. О синтезе структурно управляемых систем // Тезисы докладов 18-ой Международной конференции Проблемы теоретической кибернетики, Казань, май, 2002. -Москва, МГУ, 2002. С.8.

7. Абакаров А.Ш., Сушков Ю.А. Оптимизационные Интернет-технологии // Тезисы докладов Третьего Всероссийского Симпозиума по прикладной и промышленной математике, Сочи, июль, 2002. Москва. 2002. - С.83.

8. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование случайного поиска // Проблемы оптимизации дискретных систем. -СПб., СПбГУ, 2002. (в печати)

9. Абакаров А.Ш., Сушков Ю.А. Программный комплекс глобальной оптимизации "OPTIMUM" // Проблемы оптимизации дискретных систем. СПб., СПбГУ, 2002. - (в печати)

10. Абакаров А.Ш., Сушков Ю.А. Об одном способе организации ветвления случайного поиска. Сборник трудов кафедры. 2002. (в печати)

11. Абрамов В.А. Розеточные графы и геометрическая совместность схем планетарных коробок передач с двумя степенями свободы // Вычислительная техника в машиностроении. Минск, ИТК АНБССР. - 1972, июнь. - С.23-27.

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

13. Алекперов В.П. и др. Фильтры переменной структуры на основе кворум-элемента (кворум-фильтры) // Автоматика и телемеханика. 1970, №5. - С.37-39.

14. Андреев Д.П. Механически перестраиваемые приборы СВЧ и разделительные фильтры. "Связь", 1973. - 232 с.

15. Анкудинов Г.И. Синтез структуры сложных объектов; логика-комбинаторный подход. Л. Из-во ЛГУ. 1986. - 260 с.

16. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь. 1988. - 127 с.

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

18. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов // Межвуз. сб."Высокие технологии в технике, медицине и образовании". Часть 3. Воронеж, ВГТУ. 1997.

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

20. Берж К. Теория графов и ее применение. М., ИЛ, 1962. 320 с.

21. Вашец А.Д., Иванченко П.Н., Сушков Ю.А. Автоматизация выбора схем планетарных коробок передач. Справочное пособие. -Л.: Машиностроение. 1974. 232 с.

22. Вентцель Е.С. Элементы динамического программирования. -М.: Наука, 1964. 174 с.

23. Джамаль A.A., Сушков Ю.А. Декомпозиция многорежимных систем // Вестник ЛГУ. Математика. Механика. Астрономия. Л., 1987. - 22 с. - Деп. в ВИНИТИ 06.01.87, №140-В87.

24. Евстигнеев В.А., Касьянов В.Н. Алгоритмы на деревьях. Новосибирск, ВЦ АН СССР. 1989. - 312 с.

25. Ермаков С.Е., Митиоглова JI.B. Об одном методе поиска экстремума функции, основанном на оценивании ковариационной матрицы // Автоматика и вычислительная техника. 1977. - С.38-41.

26. Захаров В.В. Десять распространенных тестовых функций для методов оптимизации // Автоматика и вычислительная техника.- 1974. С.41-44.

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

28. Жиглявский A.A. Математическая теория глобального случайного поиска. JL: Из-во ЛГУ, 1987. - 293 с.

29. Иванова A.B., Сушков Ю.А. Многорежимные системы из двухполюсных функциональных элементов // Проблемы оптимизациии дискретных систем. JL, ЛГУ, 1990. Вып.25. - С.21-33.

30. Корбут A.A., Финкелыдтейн Ю.Ю. Дискретное программирование. М.: Наука, 1975. - 428 с.

31. Кофман А. Введение в прикладную комбинторику. М., Наука, 1975. - 480 с.

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

33. КрейнесМ.А., Розовский М.С. Зубчатые механизмы. М., Наука, 1975. - 480 с.

34. Кувырков П.П., Темников Ф.Е. Комбинаторные системы. М., "Энергия". 1975. - 152 с.

35. Лавренов О.П., Сушков Ю.А. Применение метода случайного поиска для конструирования пленочных LC-фильтров // Тезисы докладов научнотехнической конференции по микроэлектронике, Казань, КАИ, октябрь, 1975. Казань, КАИ. 1975. - С.24-25.

36. Липский В. Комбинаторика для программистов. М.: Наука, 1990. - 384 с.

37. Мазкур А., Сушков Ю.А. Передаточные функции линейных систем с переменной структурой // Теория и приложения дискретных систем. СПб, СПбГУ. 1995. Вып.27. - С.87-96.

38. Мазкур А., Сушков Ю.А., Фатташ И. Математические модели многорежимных систем // Вычислительная техника и вопросы кибернетики. СПб, Из-во СПбГУ. 1995. Вып. 28. - С.84-104.

39. Николаев В.Г., Сушков Ю.А. Графы и оптимальное проектирование регуляторов давления газа // Труды ЦНИИТА. Л., 1978. Вып.71. - С.73-79.

40. Николаев В.Г., Сушков Ю.А. Оптимизация регулятора давления газа по критерию максимальной статистической ошибки методом случайного поиска // Тр. ЦНИИТА. Ленинград. 1974. Вып.63.- С.34-40.

41. Пантелеев Ю.Р. Методы комбинаторного синтеза // Препр., ВНИИ прикладных автоматизированных систем. М., 1986. -63 с.

42. Планетарные передачи. Справочник. Л., "Машиностроение". 1977. - 535 с.

43. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: "Наука", 1982. - 254 с.

44. Рейнгольд Э. и др. Комбинаторные алгоритмы. Теория и практика. М., "Мир". 1980. - 476 с.

45. Риордан Дж. Введение в комбинаторный анализ. М., ИЛ. 1963.- 288 с.

46. Романовский И.В. Субоптимальные решения. Из-во Петрозаводский Университет 1998. - 96 с.

47. Румянцев П.В. Азбука программирования Win 32 API. 2-е изд. -М.: Радио и связь, 1999. 272 с.

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

49. Соболь И.М., Статников P.C. Наилучшие решения где их искать. - М.: Знание, 1982. - 52 с.

50. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: "Наука", 1982. - 110 с.

51. Соломон, Д., Русинович, М. Внутреннее устройство Microsoft Windows 2000. Мастер-класс. СПб.: Питер, 2001. - 752 с.

52. Страуструп В., Язык программирования С++. Спб.: Невский Диалект, 1999. - 991 с.

53. Сушков Ю.А. Структурно управляемые системы. Автореферат диссертации на соискание ученой степени доктора физико-математических наук. - С-Пб.: 2001. - 20с.

54. Сушков Ю.А. Графы зубчатых механизмов. Д., Машиностроение 1983. - 215 с.

55. Сушков Ю.А., Фатташ И. Синтез многорежимных систем из двухполюсников // Дискретные системы и их програмное обеспечение. Л., ЛГУ. 1991. Вып.26. - С.30-43.

56. Сушков Ю.А., Фатташ И. Об одном классе многофункциональных схем // Теория и приложения дискретных систем. СПб., СПбГУ. 1995. Вып.27. - С.67-87.

57. Сушков Ю.А., Фатташ И. Об одной задаче математического программирования при синтезе систем с дискретным управлением / / Дискретные модели. Анализ, синтез и оптимизация. СПбГУ. 1998. Вып.29. - С.57-64.

58. Сушков Ю.А. Метод, алгоритм и программа случайного поиска.- Л. ВНИИТрансМаш. 1969. 43 с.

59. Сушков Ю.А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. Л. ЛГУ. 1972. Вып.1. - С.180-185.

60. Сушков Ю.А. Многокритериальность в многорежимных системах // Архитектура и программное обеспечение цифровых систем. М., МГУ, 1984. - С.71-77.

61. Сушков Ю.А. Неопределенность при моделировании бизнес-процессов // Математические модели и информационные технологии в менеджменте. СПб., СПбГУ, 2001.

62. Сушков Ю.А. Связность в гиперграфах и матроидах. Исследование операций и статистическое моделирование, С-Пб.: 1994. Вып.6. - С.111-138.

63. Татт У. Теория графов. М.: Мир, 1988. - 192 с.

64. Уилсон Р. Введение в теорию графов. М., "Мир". 1977. - 207 с.

65. Харари Ф. Теория графов. М.: Мир, 1973. - 302 с.

66. Харченко А.П. Конструирование и расчет планетарных передач. Часть 1. Л., Из-во ЛПИ. 1974. - 192 с.

67. Харари Ф., Палмер Э. Перечисление графов. М., "Мир". 1977.- 324 с.

68. Черноруцкий И.Г. Методы оптимизации и принятия решений. -СПб.: Из-во Лань, 2001. 384 с.

69. Яблонский C.B. Введение в дискретную математику. М., "Наука". 1986. - 384 с.