Содержание к диссертации
Введение
1 Обзор методов проектирования электротехнических устройств методами эволюционного поиска 13
1.1. Методы проектирования на основе эволюционных вычислений 13
1.2. Обзор методов анализа электрических цепей 29
Выводы 42
2. Алгоритм проектирования пассивных электрических цепей с использованием численно-аналитических моделей 44
2.1. Интегральное эволюционное проектирование 44
2.2. Особенности реализации модифицированного метода решающих деревьев 51
2.3. Оценка эффективности применения численно-аналитических моделей на различных этапах проектирования электрических цепей 60
2.4. Выводы 77
3- Эволюционное проектирование электрических цепей на основе численно-аналитических моделей 78
3.1. Параметрический синтез на основе эволюционных вычислений 78
3.2. Структурный синтез на основе эволюционных вычислений 96
3.3. Иерархический алгоритм проектирования электротехнических устройств на основе эволюционных вычислений 103
3.4. Выводы 107
4. Экспериментальные исследования 108
4.1. Исследование эффективности численно-аналитических моделей 108
4.2. Исследование параметрического синтеза на основе эволюционных вычислений 115
4.3. Исследование алгоритма иерархического эволюционного алгоритма проектирования линейных электрических цепей с использованием численно-аналитических моделей 122
4 4 Выводы 126
Заключение 130
Литература 132
Приложения 144
- Обзор методов анализа электрических цепей
- Особенности реализации модифицированного метода решающих деревьев
- Структурный синтез на основе эволюционных вычислений
- Исследование параметрического синтеза на основе эволюционных вычислений
Введение к работе
При проектировании электротехнических устройств огромное значение приобретают эффективные методы автоматизированного проектирования, которые позволяют создавать высоконадёжные электрические цепи в короткие сроки и при сравнительно низких затратах. Стоимость любого электротехнического устройства складывается из стоимости проектирования и стоимости производства- Каждодневное увеличение числа требований, предъявляемых к электротехнической аппаратуре, приводит к постоянному росту сложности проектирования, что вызывает рост размерности решаемых при проектировании задач [1-4], В таких условиях повышение эффективности проектирования является единственным ВЫХОДОМ-
В настоящий момент большое число исследований посвящено задаче автоматизированного проектирования аналоговых устройств.. В этой области проектирования, ранее считавшейся пригодной только для экспертных САПР, появляются автоматизированные системы проектирования, базирующиеся на принципах вычислительного интеллекта.
Разработка методов и алгоритмов для решения задачи автоматизированного проектирования электротехнических устройств является актуальной уже несколько десятков лет- Это связано, в первую очередь, с тем, что эта задача является NP-полной, и, как следствие, затруднительна разработка универсального алгоритма, позволяющего находить оптимальное решение за приемлемое время. Появление новых, более совершенных средств производства электротехнической аппаратуры, становится причиной для разработки новых алгоритмов решения задачи автоматического проектирования аналоговых электротехнических устройств. Конечной целью процесса автоматизации проектирования электротехнических устройств является выделение человеческого участия в проектировании на уровень задания характеристик желаемого решения и промежуточного контроля.
Интеллектуальные системы проектирования уже сегодня способны брать на себя часть работы по проектированию, В этих интеллектуальных системах используются экспертные системы, элементы самообучения, нейронные сети и численные методы оптимизации. Среди различных методов проектирования особое место занимает метод оптимизации с помощью моделирования эволюции.
Использование силы эволюции для нахождения решений является одним из альтернативных путей повышения интеллектуальности систем проектирования. Способность эволюционных алгоритмов к нахождению нестандартных и неожиданных решений подтверждается результатами большого числа исследований [5-19].
Алгоритмы эволюционных вычислений, являющиеся одним из разделов случайно-направленного поиска, способны отыскать эффективное (близкое к оптимальному) решение за достаточно короткий промежуток времени. В настоящее время эти алгоритмы находят всё более широкое применение в силу своей способности решать слабо формализованные задачи. Это область задач на сегодняшний день требует интуитивных знаний о предмете проектирования и решается с привлечением экспертов для каждой конкретной задачи отдельно, где нет сформулированных, чётких правил, что изменение какого-либо параметра приведёт к определенным последствиям.
Правила построения алгоритмов, использующих эволюционные вычисления, заключаются в адаптации набора генетических операторов, функции пригодностн и способа кодирования альтернативных решений (хромосом) к выбранной области проектирования.
Эволюционные вычисления позволяют автоматизировать проектирование схем и их последовательное итеративное улучшение па основе принципов селекции. Естественная селекция, использующая операции репродукции (кроссинговера, мутации) и редукции, сводиться к поиску эффективных решений из ограниченного генетического материала. Искусственная селекция
6 (генная инженерия) состоит в расширении исходного генетического состава популяции путём добавления новых элементов (строительных блоков).
Таким образом, аналогии с естественной селекцией могут быть использованы при решении задач инновационного проектирования. Для решения более сложной задачи творческого проектирования эффективнее использование аналогий с искусственной селекцией.
Автоматизация проектирования сталкивается с проблемами формализации поиска решения в нестандартных ситуациях..В обшем случае процесс проектирования электротехнических устройств могут быть разделён на две группы: структурный и параметрический синтез [1,20-22]- Чем меньше известно о правилах и процедурах синтеза, тем сложнее оказывается формализация процедуры поиска возможных решений. При параметрическом синтезе задача сводится к определению численных параметров элементов при заданной топологии схемы. Более сложной является задача структурного синтеза, которая в свою очередь может быть инновационным проектированием (перебор законченных структур, выделение варианта из обобщённой структуры, трансформация описаний) или творческим проектированием (наращивание структуры, последовательный синтез, генерация топологий).
В связи с тем, что при проектировании электротехнических устройств разработчик сталкивается одновременно с проблемами синтеза топологии и поиска параметров схемы, эволюционное проектирование электротехнических устройств эффективно выполнять на основе интегрального подхода-Интегральное эволюционное проектирование сочетает в себе преимущества эволюционной оптимизации и креативного эволюционного проектирования, используя достоинства каждого из этих подходов и компенсируя недостатки.
Интегральное эволюционное проектирование является очень быстро развивающимся направлением в эволюционном проектировании и является важным шагом к дальнейшей интеллектуализации САПР электротехнических устройств. Конечной целью является полностью автоматическое, сквозное
проектирование электротехнических устройств по заданным критериям без участия человека.
Задача проектирования электротехнических устройств в диссертационной работе рассматривается как итеративный процесс, состоящий из двух зависимых частей - структурного или схемотехнического и параметрического синтезов, В задаче проектирования электротехнических устройств креативный потенциал эволюционного моделирования проявляется в большей степени на этапе схемотехнического синтеза, так как именно схемотехнический синтез является наиболее сложным для формализации. Методы осуществления параметрического синтеза в значительной степени формализованы и сравнительно легко реализуемы. Параметрический синтез предлагается выполнять на основе эволюционной оптимизации.
Одним из существенных недостатков эволюционного проектирования электротехнических устройств являются большие вычислительные затраты на определение критерия пригодности- При этом важными критериями искомого конечного решения остаются качество получаемых решений и скорость их получения.
Минимизация вычислительных затрат расчёта критерия пригодности является важной задачей для минимизации вычислительной сложности эволюционного проектирования, С этой целью для сокращения вычислительных затрат, связанных с многократным решением систем уравнений для выбора элементов для последующей репродукции эффективным является численно - аналитическое моделирование. Подобный подход позволяет устранить этап решения систем уравнений для каждого элемента текущей популяции и значительно сократить вычислительные затраты*
Хорошо себя зарекомендовавшие численно-аналитические модели используготся в диссертации для уменьшения вычислительных затрат получения функции пригодности на этапе оценки альтернативных схемных решений. Применение методик предварительного формирования и
s эффективного хранения позволяет, незначительно снизив эффективность на этапе схемотехнического синтеза, значительно повысить общую эффективность за счёт сокращения вычислительных затрат на этапе параметрического синтеза.
Целью диссертационной работы является разработка и исследование эффективности двухуровневого иерархического алгоритма проектирования линейных RLC цепей на основе численно-аналитических моделей в соответствии с изложенными концепциями повышения интеллектуализации проектирования электротехнических устройств.
Для достижения поставленной цели решены следующие задачи:
метод декомпозиции задачи интеллектуального проектирования электротехнических устройств на логически связанные подзадачи;
разработка и исследование иерархического алгоритма эволюционного проектирования электротехнических устройств;
разработка и исследование методов использования численно-аналитических моделей линейных электрических цепей для повышения эффективности алгоритмов эволюционного проектирования схемотехнических устройств;
разработка принципов кодирования, хранения и модификации альтернативных решений на различных этапах проектирования на основе проблемно-ориентированных компонент;
разработка комплекса программ эволюционного проектирования на основе предложенных алгоритмов.
Методы исследования. Методы исследования основаны на теории алгоритмов, алгоритмах, эволюционных вычислений, моделировании линейных цепей Приведенные в работе положения подтверждаются экспериментальными результатами.
Методы решения. Методология процесса проектирования схемотехнических решений элементов и узлов вычислительной техники в общем случае опирается на теорию многоуровневых иерархических систем, дискретную математику, теорию принятия решений- В силу значительного числа параметров систем и их сложности формализации синтеза подобных систем в общем виде в настоящий момент невозможна. Одним из перспективных направлений, позволяющих решить эту проблему, являются интеллектуальные системы автоматизированного проектирования.
Научная новизна заключается в следующем:
Предложены методы построения систем эволюционного проектирования линейных электрических цепей с использованием численно-аналитических моделей;
Разработаны алгоритмы эволюционного проектирования линейных электрических цепей, базирующиеся на иерархически связанных этапах структурного и параметрического синтеза электротехнических устройств;
3- Сформулированы принципы формирования схемной карты проектируемого схемотехнического устройства на этапе структурного синтеза;
Предложена архитектура инструментальной среды эволюционного моделирования, включая методы кодирования альтернативных решений.
Установлены эмпирические зависимости эффективности эволюционного проектирования электрических цепей от параметров алгоритма;
Практическая ценность. Разработанные методы многокомпонентного эволюционного проектирования линейных электрических целей с
использованием численно-аналитических моделей позволяют значительно повысить эффективность проектирования электротехнических устройств Реализация методов декомпозиции позволяет значительно сократить временные затраты на проектирование электротехнических устройств. Предложенный алгоритм позволяет повысить уровень автоматизации при создании новых электротехнических устройств.
Разработанная программная реализация предложенных подходов доказывает их эффективность. Программа реализована на языке C++ для ОС Windows NT- Получено свидетельство об официальной регистрации программы для ЭВМ №2003612184 от 25 июля 2003г.
Реализация результатов работы* Основные теоретические и практические результаты диссертационной работы использованы в научно-исследовательских работах, выполненных по фанту РФФИ № 01-01-0044 и гранту Минобразования в Таганрогском государственном радиотехническом университете г/б 14890 (ЭО-044).
Материалы диссертации использованы в учебном процессе в Таганрогском государственном радиотехническом университете при проведении практических занятий в цикле лабораторных работ по курсам «Алгоритмическое и программное обеспечение задач электроснабжения» и «Моделирование электрооборудования и систем электроснабжения».
Апробация результатов работы. Результаты работы докладывались и обсуждались на научной международной научно-технической конференции «Интеллектуальные САПР» (г.Дивноморск, 2001, 2002 гг.), на Всероссийской научно-технической конференции студентов и аспирантов «Новые информационные технологии. Информационное, программное и аппаратное обеспечение» (г, Таганрог, 2001 г.), на Всероссийской научно-технической
II конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 2002 г.),
Публикации, По теме диссертации опубликовано 8 печатных работ. Получено авторское свидетельство на регистрацию программы для ЭВМ.
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 142 стр., а также 63 рис., 3 таблицы, список литературы из 127 наименований, 6 стр. приложений и актов об использовании.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы,
В ПЕРВОЙ ГЛАВЕ приведены основные этапы проектирования электротехнических устройств. Проведена классификация методов моделирования электрических цепей. Проведён обзор имеющихся методов эволюционного проектирования электротехнических устройств. Сделан вывод о необходимости повышения эффективности проектирования электротехнических устройств за счёт увеличения степени автоматизации творческого проектирования и применения новых методов моделирования-Указаны взятые за основу методы и модели, используемые в данной работе.
Во ВТОРОЙ ГЛАВЕ проведён анализ проблем, возникающих при
эволюционном проектировании электротехнических устройств. Приведены
постановки задач проектирования на различных этапах. Сделан вывод о
необходимости применения численно — аналитических моделей для
сокращения временных затрат и повышения точности моделирования.
Разработаны модификации алгоритмов числеино-аиалитического
моделирования линейных электрических цепей, адаптированные для поставленной задачи проектирования. Рассмотрены вопросы представления
информации и принципы оценки решения на различных этапах проектирования. Приведена обобщённая схема алгоритма проектирования,
В ТРЕТЬЕЙ ГЛАВЕ выбраны комплексные критерии оценки качества
решения на различных этапах проектирования- Разработаны алгоритмы
оптимизации параметров электротехнических устройств на этапе
параметрического синтеза и создания структуры проектируемого электротехнического устройства на этапе схемотехнического синтеза. Приведён детальный алгоритм создания начальной популяции учитывающий принципы иерархического проектирования. Разработаны методы кодирования решений на двух этапах проектирования. Разработаны генетические операторы для модификации генетического материала на различных этапах проектирования с учётом особенностей выбранного метода моделирования.
В ЧЕТВЕРТОЙ ГЛАВЕ приведены экспериментальные исследования эффективности предложенного во второй главе модифицированных методов моделирования линейных электрических цепей* Приведены исследования разработанного алгоритма интегрированного эволюционного проектирования линейных электрических цепей изложенного в третьей главе. Доказана высокая эффективность используемого алгоритма численно-аналитического моделирования. Выявлены эффективные параметры, управляющие генетическим поиском. По результатам экспериментов определены оценки временной сложности алгоритмов, также приведены результаты проектирования на основе предложенных подходов.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы*
ПРИЛОЖЕНИЯ включают в себя акты об использовании результатов работы.
Обзор методов анализа электрических цепей
Все алгоритмы проектирования электрических цепей в данной диссертации основаны на модифицированном методе узловых потенциалов [54], Выбор этого метода основан на простоте и универсальности данного метода при описании электрических цепей любой размерности. Кроме того, для данного матричного представления модели цепи существует большое число оптимизирующих эвристик, так, например приведённый ниже метод MTDDD 55J использует данный вид представления цепи, В диссертации в процессе проектирования используются только пассивные элементы RLC, поэтому матрица проводимостей принимает свою простейшую, симметричную форму.
Из литературы известно два перспективных метода декомпозиции сложных символьных выражений:- метод модифицированных, проблемно ориентированных решающих деревьев [55-57 и метод иерархической декомпозиции [58,59]. По методу иерархической декомпозиции исходная схема разбивается на иерархически связанные подсхемы. При этом жёстко контролируется уровень ошибки. Этот метод повышения эффективности пригоден для большого числа схем,
В то же время функционирование метода решающих деревьев заключается в полном замещении матрицы узловых потенциалов решающим деревом, значительно сокращающим потребление ресурсов [56]. Нет необходимости в явном представлении передаточной функции в качестве рациональной дроби H(s)=N(s)/D(s). Предлагаемая структура уже содержит всю необходимую для моделирования информацию в неявном виде.
Решающие деревья позволяют максимально эффективно избегать проблем, связанных с использованием разреженных матриц при эксплуатации методов узловых потенциалов. Иерархическая декомпозиция вносит возможность гибкой перестройки схемы на основе блочной перестановки без больших вычислительных затрат.
В настоящий момент существует несколько методов, применяемых для моделирования электрических цепей: Численные методы; Аналитические методы; Численно-аналитические методы. Из них наиболее широко применяются и лучше всего исследованы численные методы моделирования. Стремление к более эффективному использованию ресурсов вычислительной техники породило новые направления в моделировании. Первым из них стало символьное направление в моделировании- Относительно новым направлением в моделировании электрических цепей является численно-аналитическое моделирование электрических цепей. Оно совмещает достоинства численных и аналитических моделей. Классификация алгоритмов моделирования линейных электрических цепей в частотной области представлена на рисЛ.6. Рассмотрим основные особенности каждого типа алгоритмов. Проведённый анализ источников показал, что в настоящий момент существует большое число публикаций посвященных задаче уменьшения вычислительной сложности процессов моделирования электрических цепей. Для данной диссертационной работы актуальными являются методы оптимизации, касающиеся модифицированного символьного анализа электрических цепей. Алгоритм Гаусса основан на простой идее исключения переменных по одной до тех пор, пока не останется только одно уравнение с одной переменной в левой части. Затем это уравнение решается относительно этой единственной переменной, например, хп. После этого значение хп подставляется в предыдущие уравнения для получения остальных решений 154,60]. Алгоритм исключений Гаусса для решения системы уравнений Ах=1 состоит из двух основных шагов:
Особенности реализации модифицированного метода решающих деревьев
Существующие методы численно-аналитического моделирования являются эффективными при моделировании электрических цепей малой размерности.
К их достоинствам относится малые временные затраты на расчёт характеристик схемы, низкая чувствительность структуры модели к изменению параметров элементов [55-58,63], При наличии численно-аналитической модели схемы для получения частотной характеристики схемы нет необходимости выполнять полный расчет схемы при изменении параметров элементов. Достаточно произвести подстановку изменившихся значений в известную формулу. Все существующие методы численно-аналитического моделирования можно разделить на два больших класса с потерями точности [58 и без потери точности 55-57. При моделировании с потерями точности решения исходная схема разбивается на ряд слабо связанных подсхем. Для каждой подсхемы расчёт выполняется только для внутренних переменных- При этом влияние подсхем друг на друга учитывается только функцией расчёта ошибки. В этом заключается принцип иерархической декомпозиции [581, Моделирование без потери точности заключается в явном выражении искомой функции через параметры цепи, с учётом всех связей. К недостаткам методов численно-аналитического моделирования относят большую пространственную сложность таких алгоритмов и быстро снижающуюся эффективность с ростом размера схемы. Для решения этой проблемы ведутся многочисленные исследования- Один из найденных путей — это метод решающих деревьев. Преимущества использования метода решающих деревьев проявляются для сильно разреженных матриц.
Разреженные матрицы являются основным типом матриц при анализе линейных RLC схем замещения. Для расчёта частотных характеристик формируется символьная матрица С по модифицированному методу узловых потенциалов. Каждый элемент1 Су-матрицы проводимостей является символьным выражением, содержащим в простейшем случае алгебраическую сумму величин, зависящих от частоты и, и не зависящих от неё (рис.2.2). Для расчёта характеристик пассивных линейных цепей в частотной области в общем случае используется выражения в виде отношения полиномов [2634, часто эти полиномы являются определителями систем уравнений моделирующих цепь (1 Л). При использовании правила (1-4) определитель det(A) исходной матрицы А преобразуется в бинарное решающее дерево. Его можно сформировать так, что число совпадающих вершин будет максимальным. Вершины дерева с одинаковыми ассоциированными подматрицами образуются из принципа построения. Поочерёдно вычеркивая строки и столбцы из исходной матрицы и перебирая возможные варианты неизбежно появление таких матриц отличающихся только порядком, в котором были вычеркнуты те или иные строки и столбцы (рис.2.5). Чем больше вершин будет разделено, тем быстрее будет рассчитываться модель, и тем меньший объём памяти ЭВМ будет задействован для храпения этого дерева. В диссертации рассматриваются методы повышения эффективности предложенных в [55-57,63] подходов.
В предлагаемом подходе вершина бинарного решающего дерева инкапсулирует: хэш-идентификатор, на основании, которого устанавливается идентичность текущей вершины вершине дерева. Расчёт этого индекса основан на подматрице ассоциированной с данной вершиной; знак ассоциированного алгебраического дополнения (+ либо —); адрес ассоциированного элемента в матице про води мостей, что позволяет менять параметры элементов в неограниченном диапазоне без обновления структуры решающего дерева; размер подматрицы ассоциированной с вершиной {разделяться могут вершины только с равным размером ассоциированной матрицы); адрес следующей вершины дерева с тем же значением размера ассоциированной подматрицы (рис.2.6) для повышения эффективности поиска следующей разделяемой вершины. Повышение эффективности алгоритма построения решающего дерева является одной из задач данной работы. Предложены следующие шаги для достижения поставленной цели: 1) В начале работы алгоритма создавался битовый массив, указывающий на отличие от нуля соответствующего элемента матрицы проводимостей. Если элемент матрицы проводимостей отсутствует, либо его численное значение меньше определённой пороговой величины, то в соответствующий бит заносится единица. Этот битовый массив модифицировался во время работы алгоритма, когда из рассмотрения исключались некоторые элементы; 2) Для дальнейших расчётов создавались два массива, в которые заносилась информация о количестве оставшихся в ряде/колонке значащих элементов (ql[]5qc[]). Значение -1 являлся признаком того, что данная строка/столбец вычеркнут из текущей подматрицы.
Структурный синтез на основе эволюционных вычислений
На предыдущем этапе были определены границы поставленной исследовательской задачи. Входными данными к последнему этапу проектирования являются требуемые частотные характеристики получаемого решения. Ограничениями на проектирование являются требования, накладываемые на топологию получаемой схемы, дискретный набор номиналов элементов и класс проектируемых схем — линейные RLC схемы. Проектирование таких схем предлагается осуществлять с использованием интегрированного подхода заключающегося в применении структурного синтеза и параметрического синтеза в рамках одного иерархически связанного алгоритма- В качестве модельной базы для расчёта качества получаемых решений предлагается использовать численно - аналитические модели, чьи особенности рассмотрены в предыдущей главе. Для направления поиска предлагается использовать эволюционное моделирование, хорошо зарекомендовавшее себя при решении различных задач проектирования [76-831 В данной главе предлагаются методы предстааіения альтернативных решений на различных этапах проектирования. Предлагаются методики сокращения временных затрат на проектирование с использованием особенностей объекта и метода проектирования. Предлагается структура интегрированного алгоритма поиска инновационных решений.
Общая структура генетического алгоритма, использующего эти подходы, описана в [41), На этом этапе осуществляется генерация номиналов элементов по выбранной топологии схемы. Топология схемы определяется списком объектов типа Element (рис J Л) Этот список содержит топологию в виде списка инциденций, текущие номиналы элементов, тип каждого элемента (один из трёх). Номиналы элементов обозначаются по их номерам из списка возможных номиналов, задаваемых перед началом работы алгоритма.
Перед началом параметрического синтеза имеется решающее дерево, составленное по принципам, изложенным в главе 2. Опорная матрица, изображенная на рис 3.1, определяет структурные зависимости в схеме. Опорная матрица состоит из символических выражений (см.рис.2.12) которые в свою очередь содержат ссылки на номиналы элементы, составляющие схему, а не сами номиналы. Такой подход позволяет без копирования быстро получать частотные характеристики (рис.2Л1) при изменении номиналов элементов. Этот метод получения частотных характеристик описывается выражением (2.2). Входной вектор _Element содержит в себе вектора Т, Е- Вектор Т={і 2,-.., іч} определяет тип элементов с соответствующим номером в векторе Element, при этом Vi, tj{R,L,C}_ N определяет количество элементов входящих в топологию. Вектор-Е-{еі,Є2,...»Єм} определяет индекс номинала элемента, при этом Vi, Єіє{О..К }, где 1С - количество возможных номиналов элементов в заданном базисе. Элементный базис B={ RbR2 Кк иЛп LK , C,,C2,„.,CK } состоит из проиндексированных номиналов элементов, возможных к выбору для всех типов элементов.
Опорная матрица схемы составляется по принципам модифицированного узлового метода [54, Она существует только через её представление в виде решающего дерева. Опорная матрица состоит из символьных выражений и значений номиналов элементов (рис.2.11). Каждое символьное выражение содержит алгебраическую сумму элементов состоящих из элементов базиса В, выбранных на основе модифицированного метода узловых потенциалов. На рис.3 Л, приведена схема гибкой модификации опорной матрицы для быстрого расчёта характеристик схемы показанной на рис 2.14. Преимущество данного подходя заключаются в отсутствии необходимости создавать матрицу и решающее дерево заново для каждого изменённого номинала любого элемента, таким образом модель схемы не испытывает никаких изменений на всём протяжении параметрического синтеза. Это значит, что нет никаких дополнительных вычислительных расходов. Всё что изменяется,— это объект, на который указывают элементы символьных выражений. Этот объект всегда является одним из номиналов В, в зависимости от исходного типа элемента с соответствующим индексом. На этапе параметрического синтеза представление решения заключается в указании номера соответствующего номинала из элементного базиса для каждого элемента из входящей топологии. Получаемый вектор целых чисел X= XIIX2,-..»XN называется альтернативным решением, В данной формулировке поиск эффективного решения сводится к поиску вектора X (рис.3.2). Найти в заданных фиксированных значениях номиналов такой вектор X, который, будучи декодирован в номиналы схемы по энергетическим законам, даст наиболее подходящее решение. Каждое альтернативное решение является вектором целых чисел X, Индекс гена определяет для какого элемента из текущей топологии определяет номинал текущий ген {рис.3.2). Индекс гена определяет тип элемента, то есть столбец таблицы номиналов, а значение гена определяет строку этой таблицы (рис.3.2). Для декодирования используется численно — аналитическая модель схемы» номиналы для которой берутся из базисного массива по типу элемента из входного вектора элементов -_Element (рис.3.2). Для каждого альтернативного решения необходимо получение частотной характеристики для последующей оценки критерия пригодности. Эта задача выполняется следующим образом. Для очередного целого числа из вектора х;єХ определяется тип соответствующего элемента по номеру і из списка _Element b при этом длина вектора N=X является одновременно и количеством
Исследование параметрического синтеза на основе эволюционных вычислений
В данном параграфе приводятся результаты экспериментальных исследований по определению эффективных характеристик параметров генетических операторов и размера популяции на уровне параметрического синтеза. Исследования проводились в двух направлениях — временная сложность алгоритма, и эффективность найденного решения. Конечной целью исследований было применение найденных эффективных параметров параметрического синтеза для оценки альтернативной топологии на этапе структурного синтеза согласно принципам, изложенным в главе 2 Исследования проводились на базе фильтра низких частот (рис.4.9) и на базе схемы цепи определения питания (рис 4.1). Производилось 100 итераций и по результатам строилась таблица. Для схемы на рис 4.9. требуемая частотная характеристика имеет аналитическое описание в виде от 1 до ІОООГц 0,5 вольт, выше — ноль вольт; F(w) = JO.55,0 f 1А7 1/;0В,/ 2кГц) . Полученная зависимость качества решения от размера популяции показана на рис 4Л0. Влияние размера популяции на время поиска иллюстрирует рис, 4.12. На рис 4ЛЗ показана зависимость времени проектирования от количества узлов в цепи.
Для параметрического синтеза на основе эволюционных вычислений является важным размер RLC базиса элементов. Зависимость качества решения от размера пула элементов показана на рис.4.11. Для параметрического синтеза лестничных и мостовых схем наиболее эффективным является размер пула элементов равный 100, то есть по 100 элементов разного номинала каждого из типов R, L и С- Это параметр специфичен только для предложенного алгоритма параметрического синтеза.
Для исследования влияния жадности генетических операторов на скорость нахождения решения значения жадности менялись в диапазоне от 0.0 до КО для операторов кроссинговера и мутации. Результаты этого исследования показаны в таблице 4. К
Наиболее эффективными являются параметры 0.4 для оператора мутации и 0.6 для оператора кроссинговера. При этих параметрах эффективное решение найдено на 68 итерации. Большие значения жадности приводят к истощению популяции, а меньшие к неэффективному использованию вычислительных ресурсов- Повышение вероятности селекции лучших решений для оператора кроссинговера является иногда подходом, позволяющим ускорить поиск эффективного решения. Результаты исследований показаны на рис 4.14, Анализ результатов показывает, что повышение вероятности скрещивания лучших решений позволяет повысить качество решения.
Для определения эффективных параметров вероятности мутации и кроссинговера проведено исследование, результаты которого приведены в таблице 4,2. Анализ таблицы 4-2 позволяет сделать вывод, что наиболее эффективными будут 0.2 для оператора мутации и 0.5 для оператора кроссинговера.
Для определения эффективных параметров генетических операторов была проведена серия экспериментов выявивших зависимости, приведенные в приложении 3. При анализе экспериментальных данных были получены следующие эффективные параметры параметрического синтеза на основе эволюционных вычислений:
