Исследование и разработка бионических методов размещения коммутационных схем ЭВА

• Автор: Мищенко, Максим Николаевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Таганрог
• Количество страниц: 135 с. : ил.

Содержание
ВВЕДЕНИЕ.
1. Анализ задач размещения при автоматизированном проектировании типовых элементов конструкций ЭВА.

1.1. Постановка оптимизационной задачи размещения

1.2. Построение математических моделей монтажного пространства

для задачи размещения

1.3. Анализ методов размещения типовых элементов

конструкций ЭВА.

1.4. Выводы
2. Теоретические исследования эволюционных и генетических алгоритмов ориентированных на размещение элементов ЭВА

2.1. Построение архитектуры комбинированного поиска для размещения элементов ЭВА.

2.2. Разработка стратегии и принципов размещения
элементов в бионических алгоритмах.
2.3. Построение генетических операторов, ориентированных
на решение задачи размещения ТЭК ЭВА
2.4. Выводы
3. Построение бионических алгоритмов размещения
типовых элементов конструкций ЭВА.
3.1. Разработка бионических алгоритмов параллельного размещения
3.2. Размещение элементов КС на основе анализа
коротких цепей.
3.3. Комплексные методы размещения ТЭК ЭВА
3.4. Выводы.
4. Результаты вычислительного эксперимента при исследовании разработанных алгоритмов.
4.1. Цель и основные задачи построения программного
обеспечения для решения задач размещения.
4.2. Описание программной оболочки
4.3. Результаты экспериментальных исследований на
стандартных и тестовых задачах.
4.4. Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Отмечено, что перспективными исследованиями являются разработка интегрированных алгоритмов размещения ТЭК, основанных на бионических методах, позволяющих получать эффективные решения для последующих этапов автоматизированного проектирования. Во втором разделе разработаны модифицированные методы поиска ориентированные на размещение ТЭК ЭВА. Приведены способы создания стартовой популяции, построения целевой функции и оценки генетического разнообразия популяции альтернативных решений. Описаны стратегии селекции (отбора) хромосом (альтернативных решений). Сделан вывод о перспективности интегрированного «жёсткого и мягкого» отбора решений. Построены поисковые алгоритмы размещения ТЭК. Временная сложность этих алгоритмов не выходит за пределы полиномиальной области. Сформулированы стратегии интегрированного поиска при размещении ТЭК ЭВА. Разработаны новые архитектуры генетического поиска на основе моделей эволюций. Это дает возможность распараллеливать процесс оптимизации, эффективно управлять поиском, получать оптимальные и квазиоптимальные решения в задачах размещения ТЭК ЭВА за время, сопоставимое с временем реализации итерационных алгоритмов. В третьем разделе приведена новая архитектура бионического поиска, ориентированная на задачу размещения. Разработаны модифицированные генетические операторы, учитывающие параметры поиска для задачи размещения ТЭК, имеющие полиномиальную временную сложность. Разработаны интегрированные алгоритмы размещения ТЭК на основе выделения клик и ядер в графовых моделях. Построены новые архитектуры параллельно-последовательного и последовательно- параллельного поиска для частичного устранения преждевременной сходимости при решении задач размещения. Временная сложность алгоритмов находится в полиномиальной зависимости от числа элементов ТЭК и ориентировочно равна (0(п1о§п)-0(п3). В четвертом разделе описаны результаты вычислительного эксперимента. Приведены количественные и качественные оценки разработанных алгоритмов размещения ТЭК ЭВА. По результатам вычислительного эксперимента уточнены оценки временной сложности алгоритмов. Определены оптимальные сочетания управляющих параметров разработанного алгоритма размещения ТЭК ЭВА. Произведено сравнение результатов, полученных разработанными алгоритмами, с существующими тестовыми примерами. Приведен интерфейс, построены таблицы, графики и гистограммы, показывающие преимущества разработанных алгоритмов. В заключении изложены основные выводы и результаты диссертационной работы. В приложении даны копии актов внедрения. Известно, что понятие оптимальности в общем случае - это оценочное отражение субъективного свойства через некоторое количественное соотношение, то есть количественное значение качества, которое желательно придать моделируемой задаче [-]. Моделирование - это исследование явлений, процессов путем построения их моделей. Модель - это копия или аналог, изучаемого явления или процесса, отражающая существенные свойства моделируемого объекта с точки зрения исследователя [8-]. В проектно-конструкторских задачах размещения применяют двухуровневое, трехуровневое или четырехуровневое представление устройства. При двухуровневом описании элемент (НТ)-го уровня рассматривают как некоторое устройство с соответствующим делением на составные элементы (компоненты) 1-го уровня. При трёхуровневом представлении элемент (1+2)-го уровня рассматривают как некоторое устройство (например, ТЭК, кристалл, линейка), состоящее из макроэлементов (1+1)-го уровня (панели, блоки), которые в свою очередь состоят из базовых элементов 1-го уровня [8-,,]. Представление устройства в виде совокупности блоков разного уровня определяет формальную структурную модель, в которой каждый блок содержит блоки нижних уровней. Такой иерархический подход позволяет снизить временную сложность задач автоматизированного проектирования, разбивая её на подзадачи меньшей размерности. Таким образом, иерархическое деление позволяет организовать описание и хранение данных, при котором конструкторско-технологические ограничение не нарушаются [3,5,,,].