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

Введение.

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

§ 1. Формулировка задачи и описание объекта исследований.

§ 2. Обзор методов численной оптимизации.

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

Выводы по главе 1.

Глава 2. Построение мультихромосомного генетического алгоритма оптимизации 28 структуры автоматизированной информационной системы.

§ L Многоуровневая декомпозиция автоматизированной информационной системы.

§ 2. Формальное построение модели связей АИС.

§ 3. Устранение избыточности в модели связей АИС.

§ 4. Принципы построения хромосом для модели связей АИС.

§ 5. Схемы размножения особей.

§ 6. Анализ генотипов хромосом.

§ 7. Краткое описание алгоритма.

Выводы по главе 2.

Глава 3. Программная реализация мультихромосомного генетического алгоритма оп- 65 тимизации структуры автоматизированной информационной системы.

§ 1. Назначение программного комплекса MULTI 2.0 и технические требования для 65 работы с ним.

§ 2. Предварительные действия пользователя MULTI 2.0.

§ 3. Работа в MULTI2.0.

§ 4. Ограничения на применение программного комплекса MULTI2.0.

§ 5. Особенности программной реализации алгоритма.

§ 6. Организация расчета значений целевых функций.

§ 7. Форматы файлов.

Выводы по главе 3.

СОДЕРЖАНИЕ

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

§ 1. Обобщенная форма представления САПР.

§ 2. Описание целевых функций оптимизации структуры САПР.

§ 3. Оценка глубины декомпозиции САПР, описание подсистем.

§ 4. Результаты оптимизации структуры САПР.

Выводы по главе 4.

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

Помимо увеличения состава АИС изменились основные подходы к их проектированию. Раньше вопрос о выделении средств на проектирование практически не ставился; исследования в данной области имели приоритетный характер (выделялось столько средств, сколько требовалось). Для каждой новой системы создавалось уникальное программное обеспечение. В таких условиях вопрос об оптимизации систем вызывал интерес лишь с научной точки зрения. На сегодняшний день ситуация изменилась. Возник обширный рынок программного обеспечения, различные программные комплексы способны решать сходные задачи (то есть появилась возможность выбора)\ имеется широкий выбор технических средств реализации поставленных задач, широкий выбор информационной поддержки. Одновременно с возможностью выбора средств реализации, ставятся существенные ограничения на финансирование. Поэтому на сегодняшний день задача оптимизации АИС является актуальной задачей, имеющей практическое значение, что подтверждается постоянно высоким числом научных работ, посвященных проблеме оптимизации систем обработки информации. Большой вклад в исследовании данной проблемной области среди российских ученых внесли Д.И. Батищев, И.П. Норенков, В.М. Курейчик и другие.

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

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

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

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

Достижение указанной цели предполагает решение следующих задач:

• анализ литературы по существующим методам оптимизации;

• разработку метода построения мультихромосомной модели АИС;

• разработку методов минимизации полученной модели;

• разработку алгоритмов оптимизации структуры АИС;

• программную реализацию разработанного метода оптимизации;

• экспериментальную проверку разработанного метода на реальном объекте -системе автоматизированного проектирования.

Выводы по главе 4.

Имея результаты оптимизации по всем трем направлениям, можно дать следующие рекомендации для получения "хороших" результатов оптимизации структуры данной САПР:

1. Численность популяции следует устанавливать не ниже 100.

2. Увеличение числа мутантов в общем случае не приводит к улучшению результатов; имеет смысл остановиться на 5 % (поскольку качественные мутации все-таки имеют место, определенный процент мутантов в популяции желателен).

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

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

До разработки мультихромосомных генетических алгоритмов поставленная задача решалась с применением алгоритма пошагового устранения "узких мест системы" на основе аналитической модели САПР. Расчеты проводились с помощью программы "Эволюция" [5]. При выполнении процедуры оптимизации использовались следующие вариации исходных параметров системы:

• изменение распределения потока заявок между различными способами выполнения процедур;

• изменение интенсивности входного потока заявок;

• изменение компонентов системы, на которых выполняется проектная процедура;

• изменение времен выполнения проектных операций. Этот метод обладал двумя основными недостатками:

• выбор метода поиска "узкого места" системы на каждом шаге определялся экспертом, то есть носил интуитивный характер;

• в программе "Эволюция" не учитываются стоимостные показатели качества.

В ПК MULTI 2.0 эти недостатки отсутствуют; поиск и устранение "узких мест" автоматизированы; эксперт влияет на процесс оптимизации только на этапе описания исходных характеристик процесса и популяции; имеется возможность ввести любую необходимую целевую функцию, ограничения на ЦФ только количественные (общее число не должно превышать 128).

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

ЗАКЛЮЧЕНИЕ.

В диссертационной работе исследована возможность представления структуры АИС в виде модели связей компонентов подсистем, полученных в результате декомпозиции системы.

Теоретическое обоснование возможности упрощения модели связей (т.е. сокращения числа рассматриваемых связей) для АИС, удовлетворяющих ограничениям, описанным в §1 первой главы, позволило разработать методику построения минимальной модели, достаточной для корректного представления структуры системы.

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

Создан инструмент (программный комплекс MULTI 2.0), реализующий предлагаемый метод оптимизации структуры АИС, разработанная технология моделирования позволяет строить модели АИС различных видов.

МГА могут применяться при оптимизации с различными критериями, поскольку способ получения решения не зависит ни от характера целевых функций, ни от их количества.

Универсальность программного комплекса MULTI 2.0 (в том смысле, что он выполняет весь комплекс типовых генетических операций, оставляя пользователю право выбирать цели оптимизации и организовывать расчет значений критериев) позволяет использовать его для решения различных сложных задач переборного типа.

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

1. И.П. Норенков. Подходы к проектированию автоматизированных систем. "Информационные технологии", № , 1998.

2. Д.И. Батищев. Поисковые методы оптимального проектирования. М., "Советское радио", 1975.

3. Б.Т. Поляк, Я.З. Цыпкин. Псевдоградиентные алгоритмы адаптации и обучения. "Автоматика и телемеханика", 1973, №3.

4. Д.И. Батищев. Методы оптимального проектирования. М., "Радио и связь", 1984.

5. В.Г. Карманов. Математическое моделирование. М., "Наука", 1980.

6. Б.Т. Поляк. Градиентные методы минимизации функционалов. "Журнал вычислительной математики и математической физики", 1963, том 3, №4.

7. Н.Н. Моисеев, Ю.П. Иванилов. Методы оптимизации. М., "Наука", 1978.

8. Б.Т. Поляк. О некоторых способах ускорения сходимости итерационных методов. "Журнал вычислительной математики и математической физики", 1964, том 4, №5.

9. JI.C. Турин, А.Д. Меркулев. Задачи и методы оптимального распределения ресурсов". М., "Советское радио", 1968.

10. С.Е. Даниленко, Б.М. Каган, Т.Г. Шахунянц. О дискретных алгоритмах в задачах оптимизации. "Автоматика и вычислительная техника". Рига, 1977, №2.

11. Я.З. Цыпкин. Адаптация, обучение и самообучение в автоматических системах. "Автоматика и телемеханика", 1966, №1.

12. Я.З. Цыпкин. Адаптация и обучение в автоматических системах. М., "Наука", 1970.

13. М. Вазан. Стохастическая аппроксимация. М., "Мир", 1972.

14. Е.Г. Гладышев. О стохастической аппроксимации. "Теория вероятности и ее применение", 1965, том 10, №2.

15. Д.И. Батищев. Генетические алгоритмы решения экстремальных задач. Нижегородский университет, 1995.

16. Ф.И. Перегудов. Введение в системный анализ. М., "Высшая школа", 1989.

17. Ф. Айала. Введение в популяционную и эволюционную генетику. М., "Мир", 1984.

18. Y. Tsujimura, М. Gen, Y. Li, Е. Kubota. An Efficient Method for Solving Fuzzy Assembly-Line Balancing Problems in Genetic Algorithm. Thrid European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1995.

19. D. Gong, M. Gen, W. Xu, G.Yamazaki. Evolutionary Strategy for Obstacle location-Allocation. Thrid European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1995.

20. В.Д. Дмитриенко. Формальные математические теории и модели в эволюционных методах. XXIII международная конференция и дискуссионный научный клуб "Новые информационные технологии в науке, образовании и бизнесе". Украина, Крым, Ялта-Гурзуф, 1996.

21. Д.И. Батищев, С.Е. Власов. Применение генетических алгоритмов для трассировки нерегулярных структур с однослойной коммутацией. Сб. Научных трудов "Оптимизация и моделирование в автоматизированных системах". Воронеж, Воронежский гос. техн. ун-т, 1995.

22. Е.Л. Глориознов, В.П. Панферов. Формализация основ генетических алгоритмов. XXIII международная конференция и дискуссионный научный клуб "Новые информационные технологии в науке, образовании и бизнесе". Украина, Крым, Ялта-Гурзуф, 1996.

23. И.П. Норенков, В.Б. Маничев. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М., "Высшая школа", 1983.

24. Душутин И.В. Принципы построения мультихромосомных моделей в задачах оптимизации. Труды второй Всероссийской научно-технической конференции «Электроника и информатика», часть-2. М., МИЭТ, 1997.

25. И.В. Душутин. Построение мультихромосомных моделей больших информационных систем. Депонент в ВИНИТИ №1624-В97. М., 1997.

26. Д.И. Батищев, Л.Н. Скидкина, Н.В. Трапезникова. Глобальная оптимизация с помощью эволюционно-генетических алгоритмов. Сб. научных трудов "Оптимизация и моделирование в автоматизированных системах". Воронеж, Воронежский гос. техн. ун-т., 1994.

27. В.М. Курейчик, В.В. Мягких, А.П. Топчий. Генетический алгоритм решения задач о комивояжере с новыми мерами против преждевременной сходимости.

28. XXIII международная конференция и дискуссионный научный клуб "Новые информационные технологии в науке, образовании и бизнесе". Украина, Крым, Ялта-Гурзуф, 1996.

29. С.А. Гладков, Г.В. Фролов. Программирование в Microsoft Windows. Часть-1. М., "Диалог-МИФИ", 1992.

30. К. Ахметов. Windows 95 не для всех. М., "Компьютер пресс", 1997.

31. В.А. Биллинг, И.Х. Мусикаев. Visual С++4. Книга для программистов. М., "Channel Trading Ltd", "Русская редакция", 1996.

32. Г. Шилдт. MFC: Основы программирования. К., "BHV", 1997.

33. F. Fagarasan, M.Gh. Negotia. A Genetic Algorithm With Variable Length of Genotypes. Application In Fuzzy Modeling. Fourth European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1996.

34. A.H. Dediu, D.Mihalia. Soft Computing Genetic Tool. Fourth European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1996.

35. A. Grauel, L.A. Ludwig. Genetic Algorithms For Optimal Feature selection. Fourth European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1996.

36. V. Olej, M. Unger. Analysis Of Genetic Algorithms And Evolution Stratigies With Distributed Genotype. Fourth European Congress on Fussy and Intelligent Technologies and Soft Computing (EUFIT), Aachen, Germany, 1996.

37. О.И. Лисов. Оценка характеристик автоматизированных систем проектирования. Уч. пособие. М., МИЭТ, 1983.

38. О.И. Лисов. Системный анализ и математическое моделирование САПР. М., МИЭТ, 1994.

39. О.И. Лисов, А.Н. Туфанов. Выбор целевых функций и оптимизация вычислительных систем в машинном проектировании. В кн.: "Управляющие системы и машины", 1978, №3.

40. А. Кофман. Р. Крюон. Массовое обслуживание. Теория и приложения. М., "Мир", 1965.

41. Е.Б. Дынкин, А.А. Юшкевич. Управляемые марковские процессы и их приложения. М., "Наука", 1975.

42. Э. Борель. Вероятность и достоверность. М., "Наука", 1969.

43. Е.С. Вентцель, JI.A. Овчаров. Теория вероятностей и ее инженерные приложения. М., "Наука", 1988.

44. В.М. Захаров. Оптимизация структуры ВС. Труды 1-ой Всесоюзной конференции по ВС. Новосибирск, 1968, вып.1.

45. Г. Корн, Т. Корн. Справочник по математике. М., "Наука",1978.

46. А.В. Ефимов, Ю.Г. Золотарев, В.М. Терпигорева. Математический анализ (специальные разделы). М., "Высшая школа", 1980.

47. Проектирование автоматизированное. Термины и определния. ГОСТ 22487-77.

48. Разработка, эксплуатация и развитие систем автоматизированного проектирования РЭА. М., МДНТП, 1978.

49. Г.Г. Казеннов. Структура, основные требования и принципы построения систем автоматизированного проектирования микроэлектронных приборов. М., "Машиностроение", 1978.

50. Б.В. Баталов, А.Р. Назарьян, А.А. Руденко. Направления и перспективы автоматизации проектирования изделий электронной техники. "Электронная промышленность", 1979, №4, с. 3-11.

51. Обмен опытом в радиопромышленности / Под ред. Ю.Х. Вермишева. М., 1978, вып. 4-5.

52. В.В. Преснухин, Ю.М. Елшин. Автоматизированное рабочее место разработчика радиоэлектронной аппаратуры. Обмен опытом в радиопромышленности. М., 1976, вып. 12.

53. Д. Девис, Д. Барбер, У. Прайс, С. Соломонидес. Вычислительные системы, сети и сетевые протоколы. М., "Мир", 1982.