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

• Автор: Душутин, Игорь Васильевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 156 с. : ил.

Содержание.
Введение.

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

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

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

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

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

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

структу ры автоматизированной информационной системы.

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

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

3. Устранение избыточности в модели связей АИС.
4. Принципы построения хромосом для модели связей АИС.
5. Схемы размножения особей.
6. Анализ генотипов хромосом.
7. Краткое описание алгоритма.
Выводы по главе 2.
Глава 3. Программная реализация мультихромосомного генетического алгоритма оп тимизации структуры автоматизированной информационной системы.
I. Назначение программного комплекса I 2.0 и технические требования для
работы с ним.
2. Предварительные действия пользователя I 2.0.
3. Работа в I2.0.
4. Ограничения на применение программного комплекса I2.0.
5. Особенности программной реализации алгоритма.
6. Организация расчета значений целевых функций.
7. Форматы файлов.
Выводы по главе 3.
СОДЕРЖАНИЕ
Глава 4. Экспериментальная проверка мультихромосомных генетических алгоритмов 0 на задаче оптимизации структу ры обобщенной модели САПР.
1. Обобщенная форма представления САПР.
2. Описание целевых функций оптимизации структуры САПР.
3. Оценка глубины декомпозиции САПР, описание подсистем.
4. Результаты оптимизации структу ры САПР.
Выводы по главе 4.
Заключение.
Список литературы


Рассматриваются системы, обладающие большим числом компонентов. Компоненты подсистем - сложные объекты; в каждом конкретном случае уровень “сложности” отдельного компонента определяется уровнем детализации исходных данных (например, компьютер как компонент структуры - сложный объект, его составляющие - СРи, КАМ. ШЮ также являются сложными и т. Задача ставится следующим образом: "Разработать метод и средства автоматизированной оптимизации структуры произвольной (в пределах указанных ограничений) автоматизированной информационной системы". При постановке задачи оптимизации [2] физические представления о назначении и степени полезности объекта преобразуются в математическую формулировку экстремальной задачи, то есть формулируются цели оптимизации и формализуется понятие оптимальности. Цели оптимизации выражаются в критерии оптимальности - правиле предпочтения сравниваемых вариантов. Основу критерия оптимальности составляет' целевая функция (? К АИС относятся большое количество различных типов. Поэтому метод оптимизации должен быть инвариантен к особенностям обработки информации каждой конкретной системы. Не уточняется ни характер целевых функций, ни их количество. При построении нового метода оптимизации следует рассмотреть возможность использования существующих методов в качестве его основы. Обзор методов численной оптимизации. Существует множество методов отыскания экстремума функции многих переменных. Рассмотрим некоторые из них. Метод Гаусса-Зейлеля [4,5]. А',о(хг - Д,/,-| < ()[хг| < 0;[хг + А,/,| - длина шага вдоль оси I, 0,шт[е(л:г - Дб(дсг + Д,/,)] > ? Метод градиента [6]. АГ5Г. О(х) вычисляется по формуле 5' = -уф' )/||У? Метод наискорсйшего спуска [5,7]. Движение к экстремуму начинается с нахождения градиента Уб(х°). Q(xr + VSr) = min Q(xr + XrSr). Метод "тяжелого шарика" [8,9]. Отличительной чертой метода является введение "инерции”, то есть учет предыстории движения. Это придаст качественно новые особенности алгоритму. Движение происходит по направлению, являющемуся линейной комбинацией градиента в очередной точке и предыдущего направления движения. Метод обладает повышенной скорос тью по отношению к методу градиента и позволяет "проскакивать" локальные экстремумы. Метод Ныотона [4. Аппроксимация функции строится на основе разложения в ряд Тейлора. Отличительной чертой метода является отсутствие проблемы выбора шага, что способствует увеличению скорости сходимости. Методы многошаговой редукции размерности [2]. Методы конечно-разностной аппроксимации [,]. VV0{х)® >где o+(X,a) = [Q(x + aei),. Q_(x,а) = [Q(x - аех),. Q(x - аеп )] , а -длина пробного шага, ej -базисные векторы. Поясним последний пункт. Когда речь идет о аргументах целевой функции, подразумевается, что они нам известны. Это необходимо и при вычислении производных и при выборе направления следующего шага. Чаще всего в роли аргументов выступают внутренние параметры (они же - структурные компоненты) системы. Практика, однако, показывает, что определить, какие именно внутренние параметры системы являются аргументами гой или иной целевой функции, не всегда удастся []. Анализ литературы позволяет сделать вывод о том, что для решения задач аналогичной нашей (независимость от вида целевой функции, сложность рассматриваемых объектов и др. ГА). Генетические алгоритмы. Эволюционно-генетический подход позволяет' строить алгоритмы поиска оптимальных решений, называемые генетическими алгоритмами, на основе моделирования биологических механизмов популяционной генетики []. Перечисленные свойства определили выбор ГА в качестве основы нового метода оптимизации структуры АИС. В связи с этим рассмотрим подробно основные этапы построения генетических алгоритмов и терминологию, используемую в []. Представление допустимых решений экстремальной задачи в виде бинарных строк. Допустимое решение х еО экстремальной задачи однокритериального выбора является п-мерным вектором х = (х, ,. Х/ ? Р,- е[0,? К1, + 1) - число возможных дискретных значений Гой управляемой переменной в области поиска и.