Содержание к диссертации
Введение
ГЛАВА I. ЗАДАЧИ КОНСТРУКТИВНОГО ЭТАПА ПРОЕКТИРОВАНИЯ РАДИОЭЛЕКТРОННОЙ И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ АППАРАТУРЫ И ИХ ОБЩАЯ МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА
1.1. Неформальная постановка комплексной задачи проектирования 16
1.2. Математическая модель элементов схем РЭА и отношения между ними 23
1.3. Математические модели конструкций узлов РЭА и условия размещения в них элементов 27
1.4. Математическая постановка комплексной задачи проектирования РЭА 30
1.5. Основные особенности комплексной задачи 37
1.6. Математическая постановка задач проектирования цифровых узлов 41
ВЫВОДЫ ПО ГЛАВЕ 48
ГЛАВА II ОБЩАЯ СХЕМА РЕШЕНИЯ КОМПЛЕКСНОЙ ЗАДАЧИ ПРОЕКТИРОВАНИЯ РАДИОЭЛЕКТРОННОЙ И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ АППАРАТУРЫ
2.1. Выбор критерия оптимальности задачи и задание отношения предпочтения на множестве ее решений 49
2.2. Построение приближенных моделей задач формирования наборов узлов и назначения в них элементов 53
2.3. Общая схема получения приближенных решений комплексной задачи проектирования РЭА 73
ГЛАВА III СПОСОБЫ ЗАДАНИЯ ВАРИАНТОВ РЕІІЕНИЯ ЗАДАЧ КОНСТРУКТОРСКОГО ЭТАПА ПРОЕКТИРОВАНИЯ РАДИОЭЛЕКТРОННОЙ И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ АППАРАТУРЫ НА ПЕРЕСТАНОВКАХ
3.1. Использование принципа прямого отображения для задания вариантов решения 76
3.2. Общая схема метода последовательно-группового размещения 82
3.3. Алгоритмы решения задач, реализующие метод последовательно-группового размещения 89
3.3. .Построение вариантов решения задач назначения элементов 91
3.3.2 .Построение вариантов решения задач проектирования
цифровых узлов 96
ВЫВОДИ ПО ГЛАВЕ 100
ГЛАВА ІV СТАТИСТИЧЕСКАЯ ОПТИМИЗАЦИЯ ФУНКЦИОНАЛОВ НА ПЕРЕСТАНОВКАХ
4.1. Рандомизация задачи и анализ некоторых схем последовательной статистической оптимизации 101
4.2. Непараметрический подход 10?
4.3. Основные параметры метода 114
ВЫВОДЫ ПО ГЛАВЕ 124
ГЛАВА V. РЕШЕНИЕ НЕКОТОРЫХ ПРАКТИЧЕСКИХ, МОДЕЛШЫХ И
ТЕСТШЫХ ЗАДАЧ ПРОЕКТИРОВАНИЯ РАДИОЭЛЕКТРОННОЙ И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ АППАРАТУРЫ 125
5.1. Решение задач конструкторского этапа проектирования ЭВА 126
5.І.І. Решение известных и практических задач назначения элементов в узлы ЭВА 126
5.2.2 Решение тестовых и практических задач размещения элементов ЭВА 132
5.2. Решение некоторых задач конструкторского этапа проектирования РЭА 142
ВЫВОДЫ ПО ГЛАВЕ 145
ЗАКЛЮЧЕНИЕ 146
ЛИТЕРАТУРА 148
ПРИЛОЖЕНИЕ I 163
ПРИЛОЖЕНИЕ II 171
- Неформальная постановка комплексной задачи проектирования
- Выбор критерия оптимальности задачи и задание отношения предпочтения на множестве ее решений
- Использование принципа прямого отображения для задания вариантов решения
- Рандомизация задачи и анализ некоторых схем последовательной статистической оптимизации
- Решение задач конструкторского этапа проектирования ЭВА
Введение к работе
Автоматизированное проектирование радиоэлектронной (РЭА) и электронно-вычислительной аппаратуры (ЗВА) в настоящее время представляет не только теоретический, но и практический и производственный интересы. Как отмечается в предисловии к работе / I /, численность инженерно-технических работников, занятых конструированием и технологической подготовкой производства достигает 50-6С$ и более от общей численности рабочих, занятых на производстве. Именно поэтому в решениях XX7I съезда КПСС предусматривается "расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники" /2/.
Из всех этапов создания РЭА и ЭВА (системотехническое, схемотехническое и техническое проектирование) наиболее сложным, ответственным и трудоемким является этап технического проектирования, включающий в себя конструкторское и технологическое проектирование. Основной целью конструкторского этапа проектирования является переход от функциональной схемы РЭА или ЭВА к конкретному набору взаимосвязанных конструктивных элементов, модулей и устройств, реализующих разрабатываемую схему, в определении их формы, размеров и взаимного расположения, т.е. синтез конкретной конструкции устройства /3/, наилучшим образом удовлетворяющей требованиям технического задания и максимальным образом учитывающей возможности используемой для ее изготовления технологической базы производства.
Для синтеза конструкции РЭА и ЭВА в связи с трудностью построения общей формальной модели задачи конструкторского проектирования в настоящее время, как правило, используются методы и алгоритмы решения отдельных задач: выбора набора узлов для реализации устройства, компоновки узлов, размещения элементов в узлах и трассировки соединений /4, 5, 6, 7/. Такая декомпозиция позволяет уменьшить размерность решаемой задачи, но, естественно, вызьюает ухудшение качественных показателей конструкции проектируемого устройства в целом. В первую очередь это ухудшение вызывается взаимосвязью решаемых задач и, как следствие, существенной зависимостью результатов решения каждой последующей задачи от результатов, полученных при решении предшествующих задач. Так, выбор набора узлов в значительной степени влияет на результат решения задачи компоновки, а решение задачи компоновки, в свою очередь - на качество последующего размещения элементов и т.д.
С математической точки зрения задачи конструкторского этапа проектирования РЭА и ЭВА относятся к классу, так называемых, NP - полных задач. В настоящее время не известны алгоритмы их решения, обладающие полиномиальной сложностью. Более того, существует гипотеза, что такие алгоритмы для NP - полных задач разработать невозможно /8, 9/. Вследствие указанной причины для решения задач конструкторского этапа проектирования наиболее широкое применение получили эвристические методы и алгоритмы.
Первые работы, затрагивающие в той или иной степени вопросы решения задач конструкторского этапа проектирования РЭА и ЭВА, появились в начале 50-х годов. В частности, пионерский характер носит статья С.Крея и С.Киша /10/, в которой рассматривается задача компоновки структуры проектируемой ими ЭВМ по конструктивным узлам. В дальнейшем количество публикаций, связанных с решением задач конструкторского этапа проектирования РЭА и ЭВА, возрастало чрезвычайно быстро и продолжает нарастать в настоящее время. Вследствие этого рассмотрение всех работ, связанных с вопросом автоматизированного проектирования РЭА и ЭВА, в кратком обзоре является весьма проблеме-тичным. Достаточно полное описание существующих методов и алгоритмов решения задач конструкторского этапа проектирования приведено в работах /4-7, 11-28/. Рассмотрим некоторые подходы, получившие широкое применение в практике проектирования РЭА и ЭВА или отличающиеся оригинальностью и новизной, непосредственно связанные с решением рассматриваемых в настоящей диссертационной работе задач.
Прежде всего остановимся на задаче выбора рационального набора узлов. Математическая постановка этой задачи может быть осуществлена с использованием результатов, приведенных в /29/, однако, практическое использование такой постановки затрудняется необходимостью учета ряда факторов, зависящих от специфики конкретного производства /З, 31/. Непосредственно связанные с задачей выбора наборов узлов вопросы построения размерно - параметрических рядов конструкций РЭА рассматриваются в работах /З, 31, с/.
Рассмотрим некоторые подходы к решению задачи назначения элементов схемы проектируемого устройства в узлы (задача компоновки). В зависимости от критериев качества, которым должна удовлетворять проектируемая РЭА, можно выделить три подзадачи /4, 6/: типизация - разбиение схемы на подсхемы, содержащие минимум номенклатуры формируемых функциональных узлов; покрытие - преобразование функциональной схемы устройства в схему соединений между функциональными узлами определенного типа; разбиение - назначение элементов схемы в узлы, реализуемые в виде отдельных конструктивов.
Среди методов решения задач типизации, покрытия и разбиения выделим,так называемый, метод параллельного свертывания /13, 33/, заключающийся в многоуровневом моделировании, разбивающем решаемую задачу на множество иерархически вложенных друг в друга идентичных задач, решаемых единой оптимизационной процедурой.
Для решения задач разбиения в настоящее время широко используются последовательные методы и алгоритмы (метод максимальной конъюнкции-минимальной дизъюнкции /34/ и его многочисленные модификации /4, 36, 37/). Основу этих методов составляет последовательная процедура выделения из исходной схемы связанных групп элементов. Последовательные методы являются особенно эффективными при разбиении схем с повышенной связностью между элементами.
Широкое применение для решения задачи назначения элементов схемы в узлы получили алгоритмы итерационного типа /4/. Характерным для алгоритмов этого типа является требование начального варианта и наличие некоторого рационального варианта назначения элементов на каждом шаге (итерации) их работы. Начальные.варианты, как правило, получают алгоритмами последовательного типа или вручную. Основой алгоритмов итерационного типа является процесс обмена местами элементов, или групп элементов, с целью минимизации критерия качества. Наиболее распространенным алгоритмом этого типа является алгоритм парных перестановок /20/, заключающийся в последовательной минимизации связей между узлами путем парных замен элементов в разных узлах. -
Среди других алгоритмов итерационного типа выделим алго- - 8 -ритмы последовательного разделения /37/ и последовательного выделения /4, 38/. Эти алгоритмы особенно эффективны для разбиения схем, содержащих сильно связанные группы элементов, в случае, когда размеры этих групп приблизительно равны.
Достаточно эффективными методами решения задач компоновки большой размерности являются методы случайного поиска. Некоторые подходы, использующие случайный поиск для разбиения схем РЭА и ЭВА,изложены в работах /4, 39, 40/.
Для решения задач размещения элементов РЭА и ЭВА в дискретном монтажно-коммутационном пространстве (МКП) (наборе фиксированных позиций) используются методы и алгоритмы, схожие с используемыми для задач назначения элементов в узлы. Поэтому рассматривать их не будем, а остановимся только на вопросах, связанных с размещением элементов в нерегулярных МКП. Решение этих задач производится, как правило, с использованием двух подходов. Первый подход заключается в наложении на непрерывные МКП дискретной сетки, в узлы которой и размещаются элементы. Некоторые алгоритмы, реализующие указанный подход, рассматриваются в работах /4, 6:f 28/.
Существенно более трудным, но более эффективным, является второй подход, при котором размещение элементов производится непосредственно в непрерывном МКП. Задача размещения в этом случае сводится к задаче размещения геометрических объектов /24, 42, 43, 41/ в заданной области.
Известны некоторые работы, посвященные совместному решению задач конструкторского этапа проектирования РЭА и ЭВА /44, 45, 46, 47, 48, 49, 50/. Эффективность решения при этом существенно определяется построением математической модели задачи и используемыми для ее решения методами. Основные затруднения, возникающие при совместном решении задач проектиро- _ о- _ вания, в основном,вызваны необходимостью учета отношений, порождаемых реальной геометрической формой элементов схемы. Эти отношения, в первую очередь, определяются условиями взаимного непересечения элементов схемы при их размещении в узлах и условиями взаимного непересечения элементов и границ МНП узла. Совместное решение задач конструкторского этапа проектирования в общем случае сводится к решению задач векторной оптимизации /51/. Методы и различные подходы к решению задач векторной оптимизации рассмотрены в работах /5, 53, 54, 55, 56, 57, 58, 59, 60/.
Для решения ряда задач конструкторского этапа проектирования могут быть использованы и некоторые более общие математические методы, разработанные для решения задач целочисленного программирования. Здесь отметим метод последовательного анализа и отсева вариантов /61,62/, метод ветвей и границ /63,64/, метод отсечения /65/, метод вектора спада /66/ и метод сужающихся окрестностей /67/. Б этих методах полный перебор всех возможных вариантов решения задачи заменяется сокращенным (направленным) перебором, обеспечивающим отбрасывание неперспективных вариантов и тем самым увеличивающим эффективность поиска.
Диссертация является продолжением исследований, проводимых в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники им., акад. М.К.Янгеля и Институте проб-лем машиностроения АН УССР под руководством профессора Ю.Г.Стояна, направленных на разработку способов формализа- * ции задач геометрического проектирования, задач САПР ,; методов и алгоритмов решения оптимизационных задач. В частности, метод последовательно-одиночного размещения, используемый при разработке метода последовательно-группового размещения, - 10 -предлагаемого в настоящей работе, рассмотрен в работе /42/. Идея, лежащая в основе упоминавшегося ранее метода сужающихся окрестностей, использована при разработке предлагаемого в работе непараметрического статистического метода последовательной оптимизации. Дальнейшее развитие она получила в работах /43,68/. В них основной акцент делается на использование параметрических законов, а вопросы построения непараїлетрических методов адаптивного случайного перебора не рассматриваются. В настоящей диссертационной работе основное внимание уделено именно непараметрическому подходу, т.к. он становится более логичным, обоснованным и,что наиболее важно, эффективным при решении задач конструкторского этапа проектирования РЭА большой размерности.
Диссертация состоит из пяти глав.
В первой главе анализируется :общая задача конструирования РЭА при использовании функционально-узлового метода проектирования. Выделяется этап синтеза конструкции РЭА, общий для ряда задач проектирования узлов различных иерархических уровней. На базе аппарата Ф -функций формализуются отношения с пространственными расположениями элементов РЭА, а также элементами и областями для их размещения в проектируемых узлах. Осуществляется точная математическая постановка комплексной задачи проектирования РЭА и выделяются ее особенности. Показывается, что эта задача относится к классу задач векторной оптимизации. В качестве примера рассматривается упрощение модели комплексной задачи проектирования РЭА для случая мон-натао-коммутационных пространств дискретного типа и использования в качестве математической модели схемы раскрашенного графа.
Во второй главе разрабатываются алгоритмы решения рас- - II - сматриваемой задачи, реализующие метод последовательного анализа и отсева вариантов. Осуществляется выбор критерия оптимальности задачи и задание отношения предпочтения на множестве ее решений. Показывается, что при выбранном способе задания предпочтений решение комплексной задачи проектирования РЭА может быть декомпозировано на решение трех задач математического программирования. Осуществляется анализ особенностей и построение приближенных моделей этих задач, позволяющих производить их решение более простыми способами. Приводятся алгоритмы решения комплексной задачи проектирования, реализующие метод последовательного анализа и отсева вариантов и использующие предложенные приближенные модели задач математического программирования.
В третьей главе рассматриваются способы задания вариантов решения задач конструкторского этапа проектирования РЭА на перестановках. Приводятся алгоритмы, позволяющие непосредственно сводить эти задачи к задаче минимизации функционала на перестановках. Предлагается метод последовательно-группового размещения, позволяющий осуществлять отображение множества локальных экстремумов задач конструкторского этапа проектирования на множество перестановок. Рассматрі-шаются итерационные формулы, реализующие предлагаемый метод для решения конкретных задач проектирования РЭА. Для определения локальных экстремумов задачи размещения элементов РЭА используется годограф вектор-функции плотного размещения.
В четвертой главе осуществляется рандомизация задач минимизации функционала на перестановках, в результате чего минимизируемая функция рассматривается как случайная величина. Производится анализ известных методов адаптивной статистической оптимизации и делается вывод о их низкой эффективности - x& -применительно к решению рассматриваемых задач. Предлагается непараметрический метод последовательной статистической оптимизации, основанный на изменении вероятностной меры, производимом на основании исследования свойств минимизируемого функционала и использовании для выяснения этих свойств схемы испытаний Бернулли. Производится анализ и рассматриваются способы задания параметров предлагаемого метода. Приводятся конкретные вычислительные алгоритмы, реализующие метод.
В пятой главе описываются результаты применения предлагаемых методов и алгоритмов для решения практических задач конструкторского этапа проектирования РЭА. Рассмотрены задачи покрытия, назначения элементов в узлы и размещения элементов в узлах для случаев непрерывного и дискретного монтажно-коммутационных пространств. Приводятся результаты решения практической комплексной задачи проектирования и тест-задачи Штейнберра. Иллюстрируется процесс решения указанных задач при помощи предлагаемых методов. Осуществляется сравнение полученных результатов с решениями, полученншш конструктором, а также с известными из литературы решениями.
Новизна научных результатов, полученных по теме диссертационной работы, состоит в следующем: построена общая математическая модель комплексной задачи проектирования РЭА, включающей в себя вопросы выбора набора узлов для конструкторской реализации аппаратуры, назначение элементов схемы в узлы этого набора и пространственного размещения элементов в каждом из узлов. Проанализированы основные особенности рассматриваемой задачи; осуществлен выбор задания отношения предпочтения на множестве вариантов решения задачи. Обоснована возможность решения рассматриваемой задачи при выбранном отношении предпочте- - ІЗ -ния путем последовательного решения трех задач математического программирования; предложены алгоритмы, построенные по общей схеме метода последовательного анализа и отсева вариантов, позволяющие находить оптимальные решения рассматриваемой комплексной задачи проектирования РЭА с учетом введенных предпочтений; выделены способы задания функционалов на перестановках, в том числе основанные на предлагаемом методе последовательно-группового размещения. Построены итерационные формулы, реализующие общую схему этого метода применительно к решению рассматриваемых задач; предложен непараметрический статистический метод последовательной оптимизации, предназначенный для решения широкого класса задач оптимизации функционалов на комбинаторных множествах большой размерности; исследована сравнительная эффективность предлагаемых методов при решении тестовых и практических задач конструкторского этапа проектирования РЭА.
Полученные в работе теоретические результаты послужили основой для разработки комплекса программ, предназначенного для решения задач конструкторского этапа проектирования РЭА и ЭВА, предшествующих этапу трассировки соединений.
Диссертационная работа выполнена в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники им. акад. М.К.Янгеля в период с 1978г. по 1984г. в соответствии с планом аспирантской подготовки и планами научно-исследовательских и госбюджетных работ: - "Разработка комплекса программ оптимального раскроя промышленных материалов для подключения их в состав матема тического обеспечения автоматизированной системы технологиче- - 14 -ской подготовки производства (№ гос. per. 78023102); "Разработка математического обеспечения ШП АСУ цехом" (Р гос. per. 79079095); "Разработка комплекса программ математического обеспечения автоматизированной системы проектирования радиоэлектронной аппаратуры" (Р гос. per. 80000478); "Исследование возможностей создания микроэлектронной аппаратуры методом установки ИС в кремниевую подложку эвтектической пайкой (№ гос. per. 01820086378); -"Система автоматизированного проектирования плат с неоднотипными элементами под комбинированный монтаж" (№ гос. per. 0I8290I0798); -"Разработка математического обеспечения для проектирования двухслойных печатных плат" (№ гос. per. 01840062175); - теме У.9.3.7 "Разработка методического обеспечения для решения задач проектирования радиоэлектронной аппаратуры и использование результатов в учебном процессе" проблемы
У.9."Повышение эффективности и качества учебного процесса на основе широкого использования ЭВМ и видеотерминальных устройств"; - договором о научно-техническом сотрудничестве с Институ том проблем машиностроения АН УССР.
Основные результаты диссертационной работы докладывались и обсуждались на I Всесоюзном симпозиуме "Статистический и дискретный анализ нечисловой информации, экспертные оценки и дискретная оптшшзация" (Алма-Ата, 1981г.), УII Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования"(Нарва-Йыэссу, 1982г.)f II Всесоюзном симпозиуме "Планирование эксперимента, оптшшзация и практические приложения" (Харьков, 1984г.), II Всесоюзном сове- - 15 -щании "Методы и программы решения оптимизационных задач на графах и сетях" (Улан-Удэ, 1982г.), Всесоюзном совещании "Случайный поиск в угольной промышленности" (Кемерово, 1984г.), Всесоюзной конференции "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации систем автоматизированного проектирования радиоэлектронной аппаратуры" (Цахкадзор, 1983г.), Всесоюзной конференции "Вероятностные методы и средства" (Новгород, 1983г.), научно-технической конференции "Контроль и автоматизированное проектирование монтажа узлов и устройств цифровой аппаратуры" (Каунас, 1981г.), научно-технической конференции "Автоматизированное техническое проектирование электронной аппаратуры" (Каунас, 1982г.), 10-й Юбилейной научно-технической конференции "Автоматизация конструкторского проектирования РЭА и ЭВА" (Пенза, 1983г.), научно-технической конференции 'Применение систем автоматизации проектирования в машиностроении" (Свердловск, 1983г.), II Республиканской научно-технической конференции "Моделирование и автоматизация процессов проектирования, изготовления и эксплуатации сложных систем" (Одесса, 1983г.), деловой встрече ученых "Случайный поиск в задачах дискретной оптимизации" (Харьков, 1983г.), школе-семинаре "Дискретная оптимизация: методы и приложения" (Севастополь, 1984г.), Республиканской конференции молодых ученых (Харьков, 1983г.), ХУТ-ХУТІІ научно-технических конференциях профессорско-преподавательского состава Харьковского института радиоэлектроники (Харьков, 1978-1983г.), а также на семинарах Научного совета АН УССР по проблеме "Кибернетика" в Киеве, Харькове в 1979-1983 годах и научно-технических конференциях молодых ученых Института проблем машиностроения Ш. УССР (Харьков, 1979-1983г.).
Основные результаты диссертации опубликованы в /69-78/.
Неформальная постановка комплексной задачи проектирования
В настоящее время при проектировании РЭА и ЭВА наиболее широкое применение получил функционально-узловой метод проектирования /3, 30/, основанный на представлении конструкции РЭА в виде совокупности определенным образом взаимосвязанных конструктивных и схемотехнических элементов и узлов, находящихся в отношении соподчиненности. Использование этого метода позволяет представить каждое устройство РЭА в виде иерархической структуры конструкций, в которой элементы низших уровней иерархии входят в состав элементов высших уровней. Ориентация на современные методы конструирования, требования стандартизации и ограничения рядов типоразмеров конструкций РЭА привели к созданию единой конструктивной базы РЭА -комплексу универсальных типовых конструкций (УТК) /3, 80, 81/, позволяющих автоматизировать процессы проектирования и производства РЭА.
Иерархическая структура РЭА, проектируемой при помощи функционально-узлового метода с использованием комплекса УТК, включает в себя пять уровней (Рис.1.I).
Первый иерархический уровень включает в себя бескорпусную элементную базу РЭА. Этот уровень имеет место при проектировании РЭА с использованием микроэлектронных компонентов /82, 83/.
Второй иерархический уровень включает в себя всевозможные дискретные элементы РЭА различной степени интеграции, выполненные в виде функционально-законченных элементов. Это транзисторы, резисторы, конденсаторы, интегральные и гибридные микросхемы.
Третий иерархический уровень составляют типовые элементы конструкций (ТЭК). Это, как правило, плоские конструкции и их пространственные объединения. Примером ТЭК являются типовые элементы замены (ТЭЗы) ЭВА, печатные платы РЭА, кассеты и другие конструкции, разрабатываемые с использованием дискретных элементов.
Четвертый иерархический уровень включает в себя различные блочные конструкции РЭА: частичные вставные блоки, комплектные и универсальные блоки, блочные каркасы и другие конструкции, проектируемые из элементов более низких уровней.
Пятый иерархический уровень определяет РЭА "в целом". Это стойки, шкафы, законченные приборы и другие конструкции.
Выбор критерия оптимальности задачи и задание отношения предпочтения на множестве ее решений
Отметим, что для практических задач проектирования наличие вариантов Ч Т) , минимизирующих все функции цели - ( I - I, 2, 3) одновременно, фактически исключается. В то же время, решения задачи (2.1), оптимальные по Парето /52/, не могут быть сравнены между собой без задания на множестве "У отношения предпочтения. Таким образом, прежде чем приступить к выбору метода решения задачи (2.1), необходимо свести ее к однокритериальной задаче оптимизации, т.е. заменить совокупность критериев -С единым обобщенным критерием.
Учитывая важность частных критериев оптимальности установим на множестве 1 следующие отношения предпочтения. Будем считать, что критерий $L более важен, чем %ь и 5з » а , в свою очередь, предпочтительнее, чем . Такое предпочтение является естественным для рассматриваемой комплексной задачи проектирования РЭА по следующим соображениям. Критерий $1 » определяющий выбор набора узлов для реализации устройства, характеризует габариты конструкции в цедом, а, следовательно, является наиболее предпочтительным /3/. Критерий 5г определяет количество связующих соединений между узлами, в конечном счете влияя на такие важные параметры конструкции, как вес проводников, их объем, надежность и т.д. В то же время критерий $3 ЛИ1пь косвенно способствует улучшению решения этапа трассировки соединений в узлах. Как отмечается в работе /105/ изменение в небольших пределах значения этого критерия, как правило, не оказывает существенного влияния на результаты трассировки. Таким образом, критерий 5г несомненно является более предпочтительным, чем 3 .
Использование принципа прямого отображения для задания вариантов
Возможны два итога работы алгоритма 3.1. Первый, наступающий при окончании работы на шаге 5, соответствует успешному формированию набора Р . В этом случае ограничения(2.7)-(2.9) выполняются, а значение функции цели (2.6) равно S . Отметим, что набор Р однозначно задает матрицу Ь . Второй исход работы алгоритма, возникающий при окончании его работы на шаге 8, означает, что набора, соответствующего перестановке 11 , не существует.
Перейдем к рассмотрению использования принципа прямого отображения для задания вариантов решения задачи назначения элементов схемы в узлы (задача (1.24), (1.29)-(1.30), (2.10)). Каждому элементу схемы t. Т поставим в соответствие число из натурального ряда от I до П , где И - число элементов схемы. Пусть элементу Xj_ соответствует число I, \ь -число 2 и т.д. Тогда любая последовательность (перестановка) из этих натуральных чисел однозначно определяет последовательность элементов схемы.
class4 СТАТИСТИЧЕСКАЯ ОПТИМИЗАЦИЯ ФУНКЦИОНАЛОВ НА ПЕРЕСТАНОВКАХ link4
Рандомизация задачи и анализ некоторых схем последовательной статистической оптимизации
Описанная в главе 2 общая схема решения комплексной задачи проектирования РЭА строилась в предположении, что известны алгоритмы решения задач выбора набора узлов, назначения элементов в узлы и размещения элементов в узлах. Однако, несмотря на детерминированный характер этих задач, использование существующих на сегодняшний день детерминированных методов глобальной оптимизации для их решения практически невозможно. Это связано, в первую очередь, с большой размерностью практических задач проектирования РЭА. Вместе с тем при применении алгоритмов решения задач выбора наборов узлов, назначения элементов в узлы и размещения элементов в узлах, разработанных в главе 3, решение этих задач естественным образом сводится к минимизации соответствующих функционалов на перестановках, которая может быть произведена с использованием статистических методов оптимизации.
Невозможность использования, с практической точки зрения, для решения задачи (4.1) методов полного перебора или других детерминированных методов приводит к необходимости использования для ее решения статистических методов оптимизации, основанных на построении вероятностной модели, т.е. рандомизации исходной задачи. Использование статистических методов для решения задачи (4.1) является, в общем случае, обоснованным, т.к. при решении многоэкстремальных задач большой размерности поведение регулярных алгоритмов носит близкий к статистическому характер /118-118/.
Одним из тривиальных подходов к решению задачи (4.1) является "слепой" перебор, при котором случайным образом из множества П выбирается отдельные перестановки и вычисляются соответствующие им значения функционала -J (%). Такой подход не учитывает свойств минимизируемого функционала. Несмотря на простоту и универсальность, "слепой" перебор обладает и существенным недостатком, а именно - медленной сходимостью. В частности, для рассматриваемых в работе задач его низкая эффективность демонстрируется в главе 5.
class5 РЕШЕНИЕ НЕКОТОРЫХ ПРАКТИЧЕСКИХ, МОДЕЛШЫХ И
ТЕСТШЫХ ЗАДАЧ ПРОЕКТИРОВАНИЯ РАДИОЭЛЕКТРОННОЙ И ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНОЙ АППАРАТУРЫ class5
Решение задач конструкторского этапа проектирования ЭВА
Рассмотрим тестовую задачу компоновки, приведенную в монографии /39/,
Требуется назначить элементы схемы, содержащей 37 равновеликих элементов, в 4 узла таким образом, чтобы число выводов каждого узла не превышало 15, Количество элементов, компонуемых в каждый узел, соответственно равно 9, 9, 9, 10, Схема устройства задается матрицей цепей, приведенной в /39/.
Решение задачи производилось предложенным в главе 4 методом и рассмотренным в работе /43/ методом сужающихся окрестностей. Количество испытаний в серии (для метода сужающихся окрестностей) и предельное число испытаний Бернулли (для предлагаемого метода) выбиралось равным 100. Алгоритм, реализующий метод последовательно-группового размещения,строился следующим образом. /I - R[ элементов схемы, определяемых перестановкой jft , назначаются в те же узлы, что и для перестановки S , соответ-ствующей рекордному значению j . Остальные элементы схемы назначаются в соответствии с описанной в пункте 3.3 процедурой.
Усредненные (по результатам 20 экспериментов) значения функции цели j (Я"), полученные при использовании метода, предложенного в разделе 4,и метода сужающихся окрестностей ., сведены в таблицы 5.1 и 5.2, соответственно.
Лучшее решение получено предлагаемым методом при использовании метода последовательно-группового размещения и уменьшении радиуса окрестностей поиска в соответствии с (4.15): I: ( I, 3, 15, 16, 17, 18, 27, -28, 29 ) ; II:( 23, 24, 25, 26, 30, 31, 32, 33, 35 ) ; III: ( 2, 4, 19, 20, 21, 22, 31, 36, 37 ) ; Ж: ( 5, 6, 7, 8, 10, II, К, 13, 14 ) .
Общее количество соединений между узлами, соответствующее приведенному варианту назначения элементов в узлы,равно 29. Результат получен за 620 испытаний.
