Мультихромосомные генетические алгоритмы оптимизации структуры автоматизированных информационных систем

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

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

Верхний уровень проектирования АИС, называемый концептуальным [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 предоставляет пользователю возможность проводить исследования, варьируя различные характеристики процесса оптимизации, с целью получения результатов, удовлетворяющих поставленным требованиям в наибольшей степени.