Содержание к диссертации
Введение
1. Анализ задач размещения при автоматизированном проектировании типовых элементов конструкций ЭВА 11
1.1. Постановка оптимизационной задачи размещения 11
1.2. Построение математических моделей монтажного пространства для задачи размещения 18
1.3. Анализ методов размещения типовых элементов конструкций ЭВА 31
1.4. Выводы 40
2. Теоретические исследования эволюционных и генетических алгоритмов ориентированных на размещение элементов ЭВА... 42
2.1. Построение архитектуры комбинированного поиска для размещения элементов ЭВА 42
2.2. Разработка стратегии и принципов размещения элементов в бионических алгоритмах 52
2.3. Построение генетических операторов, ориентированных на решение задачи размещения ТЭК ЭВА 63
2.4. Выводы 79
3. Построение бионических алгоритмов размещения типовых элементов конструкций ЭВА 81.
3.1. Разработка бионических алгоритмов параллельного размещения 81
3.2. Размещение элементов КС на основе анализа коротких цепей 92
3.3. Комплексные методы размещения ТЭК ЭВА 101
3.4. Выводы 104
4. Результаты вычислительного эксперимента при исследовании разработанных алгоритмов 106
4.1. Цель и основные задачи построения программного обеспечения для решения задач размещения 106
4.2. Описание программной оболочки 111
4.3. Результаты экспериментальных исследований на стандартных и тестовых задачах , ...116
4.4. Выводы 121
Заключение 122
Список использованных источников
- Постановка оптимизационной задачи размещения
- Построение математических моделей монтажного пространства для задачи размещения
- Построение архитектуры комбинированного поиска для размещения элементов ЭВА
- Цель и основные задачи построения программного обеспечения для решения задач размещения
Введение к работе
Методы автоматизированного проектирования, конструирования и технологической подготовки производства позволяют создавать высоконадёжные СБИС и ССБИС в короткие сроки и при сравнительно низких затратах. Тенденция к росту степени интеграции СБИС «проблема проклятия размерности», приводит к увеличению трудоёмкости автоматизированного проектирования и конструирования [1-30].
Построение современных ЭВА на основе СБИС и ССБИС выдвигает проблему эффективной реализации межсоединений (коммутационных соединений) на всех уровнях на первый план. Одним из основных этапов автоматического или автоматизированного проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии: типизация, компоновка, размещение, планирование кристалла, сжатие, трассировка и верификация [20-30].
В общей проблеме автоматизации конструкторского проектирования ЭВА одной из важнейших является задача размещения узлов низшего уровня в узлах высшего уровня. Задачи размещения элементов тесно связаны с последующими этапами сжатия, трассировки соединений и верификации схем. Поэтому основной целью задачи размещения считают создание наилучших условий для последующих этапов сжатия, трассировки соединений и верификации схем при выполнении заданных ограничений и граничных условий, обеспечивающих эффективную работоспособность схем [15-20].
Задача размещения не может рассматриваться, как частная, локальная она должна решаться с учетом компоновки блоков будущей трассировки, т.е.. в рамках системного и синергетического подходов [31-39].
Задачи конструкторского проектирования и в частности размещение элементов принадлежат к классу оптимизационных задач [10-30,40-49].
5 Это связано, в первую очередь, с тем, что задача размещения элементов
СБИС на плоскости в общей постановке является NP-полной, и, следовательно, затруднительна разработка универсального алгоритма, позволяющего находить оптимальное решение за приемлемое время. Увеличение степени интеграции
СБИС, ССБИС и ЭВА на их основе является причиной для разработки новых методов, принципов, концепций и алгоритмов решения задачи размещения.
Предлагаются новые подходы решения задачи размещения с использованием бионических методов. Основой этих методов является случайно-направленный поиск. В настоящее время эффективными при случайно- направленном поиске, являются методы эволюционного моделирования и генетические алгоритмы [50-64]. Генетические алгоритмы (ГА) новая эффективная технология оптимизации, применяемая для различных задач САПР и автоматизации проектирования. Они основаны на моделировании естественного процесса эволюции для получения локальных и квазиоптимальных результатов проектирования [45-55]. Алгоритмы генетического поиска в САПР обладают следующими качествами: быстрой сходимостью, простотой реализации и высоким качеством решений.
В этой связи, разработка новых бионических методов и алгоритмов размещения элементов СБИС и СБИС, позволяющих найти эффективное по качеству, трудоёмкости и времени работы ЭВМ решения, является АКТУАЛЬНОЙ ПРОБЛЕМОЙ.
ЦЕЛЬЮ диссертационной работы является разработка бионических методов и алгоритмов для решения задачи размещения блоков ЭВА.
Достижения указанной цели предполагает решение следующих основных задач: . . построение моделей коммутационной схемы и монтажного пространства для анализа и преобразования данных при размещении элементов схем ЭВА; разработка принципов и механизмов распределения элементов схем ЭВА по макрообластям на основе списковых и стековых представлений с целью оптимизации заданных критериев качества; построение новых архитектур бионического поиска ориентированных на решение задач размещения; построение новых и модифицированных генетических операторов для распараллеливания процесса решения задач размещения элементов; реализован генетический алгоритм получения решения в блочном виде на основе анализа коэффициента связности кластеров.
МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, графов, алгоритмов, комбинаторной оптимизации и эволюционного моделирования.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем: разработан механизм размещения графовой модели на плоскости-на основе бионических методов с возможностью задания различных вариантов представления схем; :...:-;. :. предложена новая архитектура бионического поиска : для распараллеливания процесса размещения элементов схем ЭВА; ..,_.„ разработаны новые бионические алгоритмы размещения, основанные на выделении клик и ядер графа.
На защиту выносятся следующие новые научные результаты: архитектура бионического поиска, ориентированная на решение : задач размещения, позволяющая получать ::набор квазиоптимальных решений; бионические алгоритмы размещения, основанные на выделении клик и ядер графа, позволяющие распараллеливать: процесс решений;
7 модифицированные генетические операторы, ориентированные на знания о решаемой задаче размещения, позволяющие сокращать время поиска
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы определяется созданием комплекса программ размещения элементов на различных иерархических уровнях, позволяющих использовать новые архитектуры, принципы и эвристики размещения, отвечающие конкретным конструктивным и технологическим ограничениям.
Программная среда отвечает конкретным задачам управления жизненным циклом продукции при размещении элементов схем ЭВА. При построении комплекса программ использовались пакеты C++, Builder, Visual C++. Отладка и тестирование проводилось на ЭВМ типа IBM PC с процессором PentiumrIV:c ОЗУ-512М6. Проведенный вычислительный эксперимент, показал преимущество бионических алгоритмов для решения задач размещения элементов и блоков ЭВА, по сравнению с известными методами. Разработанные алгоритмы размещения позволяют получать набор квазиоптимальных альтернативных решений за полиномиальное время.
Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования.на основе эволюционной адаптации, нейросетевых моделей и методов.принятия решений». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле лекций и практических занятий по. курсам «автоматизация конструкторского и технологического проектирования», ..-:.,,:,.,,,8 «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы». і
Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск 2002-2005гг.), на международной конференции «Интеллектуальные системы» (г.Дивноморск, 2004, 2005гг.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2003, 2004г.г.).
Публикации. Результаты диссертации отражены в 6 печатных работах.
Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх разделов, заключения, списка литературы и приложения. Работа содержит 135 стр., а также 36 рис., расположенных на 23 стр., список литературы из 109 наименований, 2 стр. приложений и актов об использовании. .,..;..;
Во введении приведена актуальность диссертационной работы, поставлена цель работы, даны основные научные положения, выносимые; на защиту, приведены сведения о практической ценности, реализации, использовании, апробации диссертационной работы, дано краткое содержание основных разделов диссертации.
В первом разделе проведен анализ существующих автоматизированных методов и алгоритмов размещения различных типовых элементов конструкций (ТЭК) ЭВА. Отмечено, что при решении задач размещения необходимо использовать модифицированные графовые, списковые и:істековые модели коммутационных схем и монтажного пространства, учитывающие заданные конструкторские ограничения и граничные условия, а также знания о предварительных и последующих этапах проектирования.. Приведена постановка задачи размещения ТЭК ЭВА, как оптимизационной задачи на графах, учитывающей различные критерии. Рассмотрена модифицированная классификация методов размещения ТЭК ЭВА. Проведен краткий обзор существующих конструктивно-начальных (последовательных), итерационных, точных и интегрированных методов размещения. Отмечено, : что перспективными исследованиями являются разработка интегрированных алгоритмов размещения ТЭК, основанных на бионических методах, позволяющих получать эффективные решения для последующих этапов автоматизированного проектирования.
Во втором разделе разработаны модифицированные методы поиска ориентированные на размещение ТЭК ЭВА. Приведены способы создания стартовой популяции, построения целевой функции и оценки генетического разнообразия популяции альтернативных решений. Описаны стратегии селекции (отбора) хромосом (альтернативных решений). Сделан вывод о перспективности интегрированного «жёсткого и мягкого» отбора решений.
Построены поисковые алгоритмы размещения ТЭК. Временная сложность этих алгоритмов не выходит за пределы полиномиальной области. Сформулированы стратегии интегрированного поиска при размещении ТЭК ЭВА. Разработаны новые архитектуры генетического поиска на основе моделей эволюции. Это дает возможность распараллеливать процесс оптимизации, эффективно управлять поиском, получать оптимальные и квазиоптимальные решения в задачах размещения ТЭК ЭВА за время, сопоставимое с временем реализации итерационных алгоритмов.
В третьем разделе приведена новая архитектура бионического, поиска, ориентированная на задачу размещения. Разработаны модифицированные генетические операторы, учитывающие параметры поиска для задачи размещения ТЭК, имеющие полиномиальную временную сложность. Разработаны интегрированные алгоритмы размещения ТЭК на основе выделения клик и ядер в графовых моделях. Построены новые архитектуры параллельно-последовательного и последовательно- параллельного поиска для частичного устранения преждевременной сходимости при . решении задач размещения. Временная сложность алгоритмов находится в полиномиальной зависимости от числа элементов ТЭК и ориентировочно равна (O(nlogn)-O(n )."
10 В четвертом разделе описаны результаты, вычислительного эксперимента. Приведены количественные и качественные оценки разработанных алгоритмов размещения ТЭК ЭВА. По результатам вычислительного эксперимента уточнены оценки временной сложности алгоритмов. Определены оптимальные сочетания управляющих параметров разработанного алгоритма размещения ТЭК ЭВА. Произведено сравнение результатов, полученных разработанными алгоритмами, с существующими тестовыми примерами. Приведен интерфейс, построены таблицы, графики и гистограммы, показывающие преимущества разработанных алгоритмов.
В заключении изложены основные выводы и результаты диссертационной работы.
В приложении даны копии актов внедрения.
Постановка оптимизационной задачи размещения
Известно, что понятие оптимальности в общем случае - это оценочное отражение субъективного свойства через некоторое количественное соотношение, то есть количественное значение качества, которое желательно придать моделируемой задаче [40-45]. Моделирование - это исследование явлений, процессов путем построения их моделей. Модель - это копия или аналог, изучаемого явления или процесса, отражающая существенные свойства моделируемого объекта с точки зрения исследователя [8-10].
В проектно-конструкторских задачах размещения применяют двухуровневое, трехуровневое или четырехуровневое представление устройства. При двухуровневом описании элемент (і-Н)-го уровня рассматривают как некоторое устройство с соответствующим делением на составные элементы (компоненты) і-го уровня. При трёхуровневом представлении элемент (і+2)-го уровня рассматривают как . некоторое устройство (например, ТЭК, кристалл, линейка), состоящее из макроэлементов (і+1)-го уровня (панели, блоки), которые в свою очередь состоят из базовых элементов і-го уровня [8-14,25,29].
Представление устройства в виде совокупности блоков.разного уровня определяет формальную структурную модель, в которой каждый блок содержит блоки нижних уровней. Такой иерархический, подход позволяет снизить временную сложность задач автоматизированного проектирования, разбивая её на подзадачи меньшей размерности. Таким образом, иерархическое деление позволяет организовать описание и хранение данных, при котором конструкторско-технологические ограничение не нарушаются [3,5,13,17,19].
Задача размещения относится к задачам многокритериальной оптимизации, и проблемой является построение интегрированного критерия качества (целевой функции), обеспечивающего локальную оптимальность конструкции с учетом многих параметров.
При построении целевой функции (ЦФ) размещения будем использовать единый функционал на основе аддитивных и мультипликативных критериев.
Под оптимизационной задачей размещения ТЭК ЭВА понимается задача, в которой необходимо найти такое распределение элементов на плоскости или в линейке которое, в заданном смысле является наилучшим или оптимальным. Отметим, что наилучшего решения во всех смыслах быть не может. Оно может быть принято оптимальным на основе заданного критерия размещения или ЦФ [40-49]. Выделим три условных типа постановки оптимизационных задач размещения.
В первом, строится исходное множество альтернативных вариантов решений. Это исходное множество решений называется пространством решений. В .дальнейшем его будем обозначать - М. Из этого множества решений на основе модели, ЦФ и разработанного алгоритма выбирается оптимальное размещение.
Во втором, в пространстве решений задаются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения позволяют выделить в пространстве М некоторое подмножество М тех решений, которые удовлетворяют заданным конструкторско-технологическим ограничениям D.
В третьем, указывается принцип сравнения любых, двух допустимых решений. Этот способ сравнения задается с помощью критерия оптимальности (или функционала, функции качества, функции полезности и т.п.). .. ;...;
В общем случае критерий оптимальности при размещении представляют как отображение, определенное на множестве допустимых решений и имеющее в качестве значений вещественные неотрицательные числа. Обозначим это отображение, то есть критерий, следующим образом: Q-.M - -R, где R — множество неотрицательных вещественных чисел [48,50,64].
Зная функцию Q, можно реализовать процедуру сравнения вариантов решений. При этом произвольное размещение гаєМ будем считать «лучше», чем размещение га є М , если Q(m) Q(m ) (при минимизации критерия качества размещения Q). В этом случае говорят, что оптимизационная задача размещения ТЭК ЭВА состоит в минимизации критерия Q, то есть требуется найти такое допустимое решение т"є М , что [48]: (m") = mmg(/H )/m elf. (1.1) Итак, оптимизационную задачу размещения запишем в виде кортежа длины три: М, D, Q , где М - пространство решений; D-ограничения, выделяющие в М область допустимых решений M czM; Q :M - R - критерий оптимизации. Требование оптимизации Q(m) min.
Модель описывает зависимость между исходными данными и искомыми величинами. Математическая модель оптимизационной задачи состоит из трех составляющих: целевой функции, ограничений, граничных условий. Часто классификацию оптимизационных задач проводят по трем основным принципам: область применения; содержание задачи; класс математических моделей.
Оптимальное решение xeD называется точкой локального минимума (локальным решением), если Vx є d (х ,є) истинно высказывание Q(x ) Q(x), здесь d(x ,є)-є - окрестность точки х. Оптимальное значение х eD называется точкой глобального минимума (глобальным решением), если ни в одной другой точке области допустимых решений функция Q(x) не принимает меньших значений Q(x ) Q(x), VxeD. Квазиоптимальным решением задачи размещения будем считать одно из множества решений, попадающих в локальный экстремум, отличающийся от глобального на заданную величину є [50]. -- Существует условная классификация критериев размещения: по типу оптимизируемых параметров - метрические, топологические, по степени надёжности, плотности упаковки элементов; по эффективности будущей трассировки и т. п. [27].
Построение математических моделей монтажного пространства для задачи размещения
На этапе конструкторского проектирования ЭВА, РЭА, и других объектов одним из важных вопросов является размещение коммутационной схемы рассматриваемого устройства в конструктивно законченные части. Задача размещения не может рассматриваться, как частная, локальная она должна решаться с учетом компоновки блоков будущей трассировки, сжатия и верификации, т.е. в рамках системного и синергетического подходов [17-21]. Системный подход - это решение задач автоматизации конструкторского проектирования, например, размещения, совместно с компоновкой с учетом типизации, трассировки и верификации. При размещении производится анализ коммутационного поля и подбор конструктивных характеристик, позволяющих разместить заданные типовые элементы конструкций с учетом будущей трассировки соединений [65,66].
Синергетический подход в первую очередь учитывает качество целой конструктивной единицы, а не отдельных ее частей. При построении порядка т.е. . заданного размещения элементов из хаоса (неупорядоченной коммутационной модели схемы), важнейшей является чувствительность конечного результата к исходным данным [31-39].
ЭВА в общем случае, всегда содержит иерархию конструктивных частей. Выделяют 6 таких условных частей: интегральную микросхему, линейку, типовой элемент замены (ТЭЗ), блок, стойку, шкаф. Будем называть их типовые элементы конструкций (ТЭК), согласно [3,13,27]. Отметим, что иерархию конструктивных частей, можно изменять и наращивать в зависимости от исходных требований до заданного уровня сложности.
Реализация задач автоматизированного размещения ТЭК ЭВА зависит от заданной математической модели (ММ) коммутационной схемы. Для одной той же коммутационной схемы ЭВА можно построить различные математические модели. Они с различной точностью описывают одни и те же параметры устройства при размещении элементов. Разработка новых алгоритмов и эвристик размещения элементов приводит к построению различных моделей схем и моделей коммутационного пространства (МКП).
Входные переменные ММ будем представлять вектором X = (х1,х2,...,ха). Они характеризуют свойства внешней по отношению к модели среды, оказывающей влияние на ее функционирование. Внешней средой, например, при проектировании линеек СБИС, являются ТЭК, связанные с проектируемой. Внутренние переменные (переменные состояния) - величины, которые характеризуют состояние отдельных элементов модели. Обозначим, их вектором Z = ( ,22,-,2,). Величины, характеризующие свойства модели в целом и определяющие степень выполнения моделью своего назначения, называют выходными переменными. Их обозначают вектором Y = {у1,у2,...,ут).
Выражения, отображающие зависимость между входными и выходными переменными, а также переменными состояния называют математической моделью решаемой задачи [13]. Их можно представить в форме: 7 = F(X,Z) (1.13)
Выражение (1.13) представляет собой отображение (или соответствие) между двумя множествами переменных X, Z, которое можно получить на основе одной из моделей. Таким образом, под математической моделью задачи размещения будем понимать зависимость F, которая в общем случае может быть некоторым алгоритмом, оператором, функцией, правилом, инструкцией и т.п. Эта модель позволяет, определять значения выходных переменных, не обращаясь к реальному объекту (коммутационной схеме), для которого решается задача. .
Математические модели ТЭК можно применять итерационно: как строительные блоки при создании систем из этих элементов. При построении математических моделей КС при размещении в основном используются неформальные и эвристические методы, на основе нечетких множеств, и эволюционного моделирования [50].
Отметим, что в математической модели задачи выражение (.1.13) устанавливает взаимно однозначное соответствие между входными и выходными переменными и является ее детерминированным описанием. При решении задач автоматизированного проектирования параметры задачи часто имеют стохастический и нечеткий характер. Тогда параметры модели задаются как случайные величины, выбираемые согласно заданному закону распределения вероятностей.
Обозначим вектором р = (фр- Фг) множество параметров состояния фсС, которые, являясь случайными величинами, влияют на значения выходных переменных. Кроме того, обозначим вектором = ( ,,г -..,4/ ) совокупность параметров состояния сС, которые, являясь нечеткими величинами, влияют также на значения выходных переменных. При этом , = ( ., /), где ]ь(-функция принадлежности элемента cf к множеству ц/, то есть ц: ц/ — [од].
Построение архитектуры комбинированного поиска для размещения элементов ЭВА
В задаче размещения ТЭК ЭВА можно рассматривать, как целенаправленность действий принятия проектных решений приводящих к реализации заданной схемы проектируемого объекта заданной степени детализации. Продуктом проектирования является реализованная модель объекта реально несуществующая до момента проектирования. Процедуры проектирования в задачах размещения представляются, как процедуры преобразования его исходной модели в некоторый исходный объект, расположенный на МКП. Нечеткость и неопределенность постановки задачи размещения позволяют использовать различные множества альтернативных решений для получения оптимальных и квазиоптимальных результатов. Итак, процесс размещения элементов ТЭК ЭВА сводится к выбору стратегии проектирования, т.е. к поиску и определению последовательности операций выбираемых ЛПР для решения поставленной задачи. Стратегия проектирования реализуется на основе технологии проектирования, т.е. заданных алгоритмов, реализующих размещение элементов на МКП. В свою очередь алгоритмы проектирования при размещении отражают совокупность четких и нечетких правил необходимых для решения задач. В связи с тем, что задача размещения является творческим процессом важной задачей, является построение и выбор эффективной архитектуры алгоритмов размещения. При этом автор предлагает использовать комбинированные эвристические, бионические (эволюционные, генетические) методы поиска оптимальных решений с точки зрения ЛПР [19,20,25,27,30,50,77].
В задачах размещения любое альтернативное решение представляется набором параметров х,, представляющих один элемент некоторого множества альтернативных решений Р. В бионических методах множество Р называется популяцией. Каждому элементу из этого множества соответствует кодовая запись, называемая хромосомой (особью или альтернативным решением). В свою очередь каждая хромосома состоит из дискретных элементов. Они соответствуют параметрам х . Их называют генами. Каждый ген размещается в хромосоме в некоторой позиции - локусе. Каждый ген может иметь различные функциональные значения, называемые аллелями. Частичный набор генов называется строительным блоком. Из таких блоков составляются альтернативные решения задачи размещения. Каждой хромосоме соответствует некоторая точка пространства решений [50]. Число возможных, альтернатив размещения в общем случае составляет п!, где п - число элементов математической модели КС. Поэтому в каждый момент поиска бионический алгоритм оперирует некоторым подмножеством Р (Р сР) альтернативных решений мощности N .
В бионических алгоритмах каждое альтернативное . решение рассматривается как особь, развивающаяся в популяции - сообществе себе подобных [78,79]. Для каждой хромосомы в популяции определяется значение целевой функции в соответствии с выбранным или построенным критерием оптимизации задачи размещения.
Предлагается следующая технология бионического поиска . при размещении элементов. Сначала на основе конструкторско-технологических ограничений сокращается область поиска допустимых решений... Далее анализируя эту область, случайным, направленным или комбинированным образом создаётся начальная популяция или стартовое . множество альтернативных решений, которое в дальнейшем развивается на основе выбранной эволюционной теории [50,64]. Поиск решений в случайно выбранном направлении часто не приводит к эффективному реальному решению. В этой связи здесь вводится специальные этапы направления поиска.
На основе постановки задачи размещения определяется ЦФ. Далее на основе ЦФ производится анализ популяции альтернативных решений и селекция (отбор) хромосом для дальнейшего поиска оптимальных решений задачи размещения. В рассматриваемой схеме бионического поиска в зависимости от экспертной системы (шкалы) выбирается генетический или эволюционный алгоритм. В генетическом алгоритме новые решения в популяции формируются путём реализации различных генетических операторов (кроссинговер, мутация, инверсия, сегрегация, транслокация, транспозиция, удаления и вставки ) [64]. В эволюционном алгоритме новые решения в популяции формируются путём реализации модификаций одного оператора мутации. После репродукции размер популяции остается постоянным. Для этого производится его уменьшения до прежних размеров с помощью механизма естественного отбора или принципа «выживания сильнейших». В данной работе используется ; и другой способ, когда популяция изменяется динамически после реализации каждого оператора. Далее вся процедура повторяется на новом шаге эволюции.
На рис.2.1. приведем упрощенную схему бионического: алгоритма размещения. Здесь БА, ГА и ЭА - соответственно бионический, генетический и эволюционный алгоритмы размещения, ОР - оператор репродукции, изменяющий размер популяции альтернативных решений, ЭС - экспертная система, определяющая дальнейший ход поиска. Следовательно, БА состоит из пяти основных блоков. БА = (ГА,ЭА,ОР,ЭС, правила останова). Тогда ЭА и ГА можно представить в следующем виде: ЭА = (Р, N, МК, С, ЦФ, ОГР, ГУ, ОМ,ОР, G, рь L), ГА - (Р, N, МК, С, ЦФ, ОГР, ГУ, ГО (ОК,ОМ,ОИ,ОТ,ОС,ОТР,ОУ,ОВ), OP, G, pi, L). Здесь МК- метод кодирования хромосомы (альтернативного решения), С - селекция, ОГР и ГУ - ограничения и граничные условия на задачу размещения, ГО - генетические операторы, G - число генераций или поколений алгоритма, pt є Р - хромосома, a L- длина хромосомы.
Цель и основные задачи построения программного обеспечения для решения задач размещения
Проведение вычислительного эксперимента при размещении ТЭК ЭВА на коммутационном поле при анализе бионических алгоритмов преследовало следующие цели: определение управляющих параметров бионического поиска для каждой части и исследование эффективности предложенных алгоритмов. Определение параметров бионического, генетического и эволюционного поиска заключалось в определении влияния таких параметров, как размеры коммутационного поля, количество элементов и связей схемы, начальный порядок размещения элементов и связей, размер популяции, число генераций, количество строительных блоков, топология архитектуры поиска, число, порядок и вероятность применения генетических операторов. Исследование эффективности предложенных алгоритмов заключается в определении значений целевой функции, временной и пространственной сложности [50,80,107,108].
Для разработанных алгоритмов создана программная среда, содержащая несколько пакетов программ. При построении пакетов программ размещения использовались приложения Borland C++, Builder, Visual C++. Вычислительный эксперимент для бионического, генетического и эволюционного поиска проводился на ЭВМ типа IBM PC, с процессором Intel Pentium IV, 2500 МГц, ОЗУ 512 Мб, жёсткий диск 80 Гб.
Для проведения испытаний разработанных алгоритмов использовались два подхода.. В первом задавались стандартные тесты (бенчмарки) ведущих фирм мира и проводилось сравнение по времени решения и значению целевой функции [19,20,27]. Во втором случае использовался разработанный генератор случайных коммутационных схем и их графовых и гиперграфовых моделей. На вход генератора поступают управляемые параметры. Эти параметры принимают дискретные значения. Программная подсистема по исследованию этих задач и их процедур выполнена в виде комплекса программных средств, состоящих из различных программных модулей (ПМ) [109]. При этом выходными параметрами являются: время работы алгоритмов, стабильность алгоритма, лучшее решение, достигнутое в процессе работы, оценка алгоритма по сходимости. Общая структурная схема ПМ исследования различных задач на графах, аналогично схеме [109], и приведена на рис.4.1. Она состоит из блоков:
1. Хранилище данных. Здесь расположены тестовые задачи размещения (бенчмарки), библиотека спроектированных коммутационных схем, графовые и гиперграфовые модели, различные модели монтажно-коммутационного пространства, эвристики построения моделей, результаты работы генератора случайных коммутационных схем.
2. Редактор тестовых задач размещения. Производит действия по анализу, упорядочиванию, выбору их редактированию для конкретного этапа бионического поиска.
3. Блок адаптации. Здесь производится адаптация параметров алгоритма к внешней среде, т.е. к требованиям на проектирование.
4. Библиотека генетических операторов. В данном блоке производится выбор стандартных и построение комбинированных генетических операторов.
5. Библиотека различных методов поиска. Здесь приводятся точные, последовательные, итерационные и комбинированные методы поиска.
6. Библиотека моделей эволюции. В данном блоке производится, выбор стандартных и построение комбинированных моделей эволюции.
7. Экспертная подсистема. Здесь на основании заданных правил, сформулированными опытными экспертами-конструкторами производится выбор пути проектирования.
8. Блок управления. Здесь реализуется иерархический многоуровневый способ реализации процесса проектирования.
9. Бионический алгоритм. В данном блоке выбирается одна из :трех цепочек (бионический, эволюционный, генетический алгоритмы) реализации алгоритма размещения.
10. В блоке сходимости алгоритма анализируется попадание решения в локальный оптимум и выбираются эвристики выхода из него.
11. В блоке выдачи результатов выдаются статистические результаты работы программного комплекса и топология размещения коммутационной схемы на МКП.
Программная подсистема содержит в себе: панель ввода/вывода, позволяющую загружать/сохранять тестовые примеры (КС с настройками); выводить на печать статистические данные; панели настройки алгоритма; и ввода параметров, позволяющие отключать (или подключать) различные методики улучшения процесса поиска; разнообразные модели эволюции; панель работы алгоритма, позволяющую отображать в процессе работы значение целевой функции (ЦФ), график изменения ЦФ по популяции, статистические данные работы алгоритма.
Схема исследования разработанных алгоритмов при размещении коммутационной схемы на МКП показана на рис.4.2. Частные параметры для ИМ (рис.4.2) следующие: исследование всех описанных моделей эволюции, блока анализа преждевременной сходимости алгоритма, анализ эвристик при микро, макро и метаэволюций, анализ различных генетических операторов. После реализации моделей эволюции выполняется БА, Далее выполняется все или один из описанных методов локального поиска. Блок , внешней среды отвечает за обратные связи. Далее выполняется непосредственно БА в соответствие с выбранной схемой поиска. Затем производится подбор \ и установка генетических операторов с заданными вероятностями их реализации, которые влияют в итоге на качественные характеристики поиска.
