Содержание к диссертации
Введение
1. Анализ методов и алгоритмов синтеза РЭУ 12
1.1. Постановка задачи синтезаРЭУ 12
1.2. Анализ существующих подходов синтеза РЭУ 21
1.3. Применение эволюционных методов при решении задачи синтеза РЭУ 29
1.4. Выбор метода синтеза РЭУ 34
1.5. Выводы 35
2. Разработка эволюционных алгоритмов структурного синтеза РЭУ 36
2.1. Представление модели РЭУ в виде хромосомы для структурного синтеза 36
2.2. Определение целевой функции 48
2.3. Генетические операторы и структура генетических алгоритмов структурного синтеза РЭУ 49
2.4. Теоретическая оценка алгоритмов синтеза 70
2.5. Выводы 72
3. Разработка эволюционных алгоритмов параметрического синтеза РЭУ , 73
3.1. Представление модели РЭУ в виде хромосомы для параметрического синтеза 73
3.2. Определение целевой функции 78
3.3. Структура генетических алгоритмов параметрического синтезаРЭУ 80
3.4. Теоретическая оценка алгоритмов синтеза 98
3.5. Выводы 100
4. Экспериментальные исследования разработанных алгоритмов 101
4.1. Цель экспериментальных исследований 101
4.2. Определение основных параметров генетических алгоритмов для структурного и параметрического синтеза РЭУ 102
4.3. Результаты экспериментальных исследований, сравнение с существующими алгоритмами 107
4.4. Выводы 110
Заключение 111
Литература
- Анализ существующих подходов синтеза РЭУ
- Генетические операторы и структура генетических алгоритмов структурного синтеза РЭУ
- Структура генетических алгоритмов параметрического синтезаРЭУ
- Определение основных параметров генетических алгоритмов для структурного и параметрического синтеза РЭУ
Введение к работе
Роль начальных стадий проектирования при разработке радиоэлектронных устройств (РЭУ) велика. Здесь закладываются основы новой разработки. Поэтому экономия средств и времени на начальной стадии оборачивается огромными затратами на последующих стадиях, связанных с устранением недоработок и ошибок.
Эффективность работ по проектированию технических устройств определяется их организацией на каждой стадии, и применяемой методикой. Это особенно важно на начальной стадии проектирования [1].
При проектировании электронных устройств разработчик сталкивается одновременно с проблемами поиска топологии и определения параметров схемы, а также с жесткими ограничениями к срокам проектирования. Поэтому традиционные методы проектирования являются малоэффективными, а отсутствие в используемых моделях и алгоритмах возможности изменения системы ограничивает область поиска решения только типовыми схемами. Современным и эффективным методом решения данной проблемы является использование эволюционного проектирования электронных устройств.
Методы эволюционного моделирования появились в начале 70-х годов двадцатого века. Однако только последние 10 лет эволюционное моделирование стало активно применяться в различных областях человеческой деятельности. Существует множество задач, решаемых с его использованием: автоматизация проектирования, создание искусственной жизни, эстетическое проектирование и др. [2]. В основе эволюционного проектирования лежит вычислительная техника, проектирование и эволюционная биология.
Эволюционное моделирование представляет собой одно из быстро развивающихся направлений математического моделирования, которое объединяет в себе компьютерные методы моделирования эволюционных
5 процессов в естественных и искусственных системах, такие как генетические алгоритмы, эволюционные стратегии, эволюционное программирование и другие эвристические методы. Основной сложностью при построении вычислительных систем, основанных на принципах эволюции живой природы и применения этих систем в прикладных задачах, является то, что природные системы достаточно хаотичны, а действия исследователей носят направленный характер [3]. Исследователи используют компьютер как инструмент для решения поставленных задач, которые сами и формулируют, при этом внимание акцентируется на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае, они не очевидны. Однако биологические системы обладают свойствами воспроизводства, адаптации, самоисправления, устойчивости, гибкости и многими другими, которые лишь фрагментарно присутствуют в искусственных системах [3].
Основная идея эволюционного проектирования заключается в поиске решения на основе эволюционной адаптации [4]. Набор схемных решений (текущая популяция) генерируется и итерационно развивается в соответствии с определенными правилами. Для каждой последующей популяции выживает только несколько особей, в то время как остальные, оказавшиеся недостаточно приспособленными, погибают. Новые решения создаются заново путем смешивания накопленного генетического материала родителей [5, 6].
Эволюционная оптимизация является наиболее простым этапом эволюционного проектирования. Процесс проектирования начинается с существующего проектного решения, отдельные параметры которого могут быть изменены в определенных пределах [7]. Для всех возможных электронных схем учитываются все доступные элементы и технологические ограничения, такие как, сколько элементов может быть использовано, и то, как они могут взаимодействовать. Далее эти параметры кодируются как генотип, который затем развивается на основе эволюционного поиска. После
этого, полученные проектные решения оцениваются по степени полезности. Подобная оценка называется целевой функцией (ЦФ) [6].
Эволюционное проектирование имеет дело с обширной областью поиска и большим количеством требований, поэтому используются мощные методы поиска, для разрешения поставленной задачи. Естественно, когда область поиска очень большая, может иметь место случайное решение. Поэтому выбор размера области поиска это сложный вопрос, поскольку он должен быть достаточно большим, чтобы включить обильное разнообразие топологий новой схемы. Однако если область проектных параметров будет увеличиваться без ограничения, шансы найти хорошее решение будут очень малы [7]. Это важная проблема для методики поиска, решением которой являются эволюционные алгоритмы.
Эволюционные алгоритмы хорошо приспособлены, чтобы производить выборку большой области проектных параметров, выполняя ее лучше, чем стандартные методы оптимизации. Тем не менее, для больших областей поиска, даже эволюционные алгоритмы имеют свои ограничения -необходимо ограничить размер области поиска, но одновременно с этим сохранить разнообразие ее проектов. Область поиска обычно ограничивается выбором максимального размера для схем, среди которых будет производиться выборка [7]. Еще одной проблемой является добавление специальных методов в алгоритм поиска для того, чтобы успешно находить схему, соответствующую всем спецификациям. Новые методы вводятся, чтобы улучшить средства поиска, и применяются для обработки специфических свойств процесса электронного проектирования, таких как его многокритериальность и непредсказуемость размера решения.
Эволюционные алгоритмы предоставляют возможность объединить в одно целое все эти методологии, что позволяет улучшить производительность проектирования электронных устройств, дает возможность находить новые методы проектирования схем и способность рассматривать большое количество параметров.
Из всего вышеизложенного следует, что задача разработки новых алгоритмов для проектирования электронных схем на основе методов эволюционного моделирования и генетического поиска, позволяющего сократить время поиска решений в задачах с большой областью поиска, и в то же время повысить качество получаемых решений является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является исследование и разработка новых моделей и алгоритмов структурного и параметрического синтеза радиоэлектронных устройств на основе методов эволюционной адаптации, позволяющих повысить качество решений для задач большой размерности.
Для достижения поставленной цели необходимо решить следующие основные задачи:
Разработать метод представления схемотехнических решений в виде альтернативных решений (кодирование и декодирование хромосом);
Разработать новые эволюционные алгоритмы синтеза топологии и параметров схемотехнических решений;
Разработать новые модифицированные генетические и эволюционные операторы, адаптированные к требованиям решаемой задачи (операторы кроссинговера, селекции, мутации, отбора и генерации начальной популяции);
Разработать целевые функции для оценки качества получаемых схемотехнических решений;
Провести экспериментальные исследования разработанных методов и алгоритмов, а также их сравнение с известными алгоритмами синтеза РЭУ.
Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, теории алгоритмов и теории генетического поиска, теории графов и гиперграфов, теории выбора и принятия решений.
8 НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:
Разработке новых методов представления схемотехнических решений в виде альтернативных решений (хромосом), позволяющих для случая структурного синтеза схем значительно сократить получение неработоспособных схем;
Разработке новых генетических алгоритмов для структурного и параметрического синтеза РЭУ, учитывающих особенности решаемой задачи;
Разработке модифицированных генетических и эволюционных операторов, позволяющих сократить время работы алгоритма;
Разработке целевых функций для различных классов электронных схем.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
Новые методы представления схемотехнических решений в виде хромосом;
Пакет программ для синтеза топологии и параметров РЭУ, разработанный на основе генетических алгоритмов, позволяющих найти работоспособное решение за приемлемое время.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12354 «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», а также в научно-исследовательской, выполненной по гранту РФФИ №12381 (№05-08-18115) «Разработка теории и принципов построения систем автоматизированного проектирования на основе эволюционной адаптации». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при проведении лабораторных и курсовых работ по дисциплинам: «Эволюционное моделирование и генетические алгоритмы», «Методы
9 оптимизации», «Автоматизация проектирования печатных плат» и «Математические основы дискретной техники».
АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах кафедры САПР «Генетические алгоритмы» (с 2004 по 2007 гг., ТРТУ), всероссийской научно-практической конференции молодых ученых и аспирантов «Новые информационные технологии» (г. Таганрог, 2004 г.), международной конференции «Интеллектуальные системы (ШЕЕ AIS'04)» (с. Дивноморское, 2004 г.), всероссийской научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Таганрог, 2005 г.), всероссийской научной конференции студентов и аспирантов с международным участием «Робототехника, мехатроника и интеллектуальные системы» (г. Таганрог, 2005 г.), международной конференции «Интеллектуальные системы (IEEE AIS'06)» (с. Дивноморское, 2006 г.).
ПУБЛИКАЦИИ. Результаты диссертации отражены в 9 печатных работах.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.
Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, приложения и примеров. Работа содержит 155 страниц, включая 31 рисунок, 10 таблиц, список использованной литературы из 105 наименований, 32 страницы приложений и актов об использовании.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, представлены сведения о практической ценности, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приведена постановка задачи синтеза радиоэлектронных устройств. Проведен аналитический обзор существующих подходов и методов решения задачи синтеза радиоэлектронных устройств, выявлены их достоинства и недостатки. Кратко проанализированы основные
10 положения теории генетического поиска. Обоснован выбор метода синтеза радиоэлектронных устройств. В качестве перспективного метода для решения задачи синтеза радиоэлектронных устройств определен эволюционный подход. Сделаны выводы и выработаны рекомендации о целесообразности применения схемотехнического синтеза на основе эволюционного подхода.
ВО ВТОРОЙ ГЛАВЕ описана процедура представления радиоэлектронных устройств в виде хромосом для структурного синтеза схемотехнического решения (кодирование), учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений. Предложена процедура генерации начальной популяции схемотехнических решений. Разработана процедура определения «заведомо неверных», с точки зрения схемотехника, схемотехнических решений. Разработаны и приведены основные генетические операторы, адаптированные к особенностям решаемой задачи. Разработан генетический алгоритм структурного синтеза радиоэлектронных устройств. Определена теоретическая оценка временной сложности разработанного алгоритма. Сделаны выводы о научной новизне и практической ценности предлагаемого алгоритма.
В ТРЕТЬЕЙ ГЛАВЕ приведен метод представления РЭУ в виде альтернативного решения (хромосомы) для параметрического синтеза РЭУ на основе генетического алгоритма. Предложена структура нового (модифицированного) генетического алгоритма параметрического синтеза РЭУ. Приведены традиционные и разработаны модифицированные генетические операторы, адаптированные к решаемой задаче. На примере схемы усилителя показан принцип действия модифицированных операторов. Построена целевая функция, оценивающая синтезируемые схемотехнические решения. Определена теоретическая оценка временной сложности алгоритма параметрического синтеза. Сделаны выводы о пользе предложенного алгоритма и модифицированных генетических операторов.
В ЧЕТВЕРТОЙ ГЛАВЕ приведены результаты экспериментальных исследований, предложенных автором генетических алгоритмов. Проведены серии экспериментов для определения оптимальных параметров алгоритма. По результатам исследований определены оптимальные управляющие параметры для алгоритмов. Выполнено сравнение исследуемых алгоритмов с уже существующими. Экспериментально подтверждена временная сложность представленных алгоритмов.
В ЗАКЛЮЧЕНИИ приведены основные результаты и выводы, полученные в диссертационной работе.
В ПРИЛОЖЕНИЯХ приведены копии актов о внедрении, примеры синтезированных схем, исходные тексты основных процедур программы структурного и параметрического синтеза РЭУ на языке C++.
Анализ существующих подходов синтеза РЭУ
Проектирование аналоговых схем характеризуется большим уровнем сложности, по сравнению с цифровым проектированием, поэтому его реализация полагается на опыт и интуицию конструктора. Несмотря на то, что большинство современных интегральных схем основано на цифровых технологиях, аналоговые схемы все еще необходимы для осуществления их взаимодействия с внешним миром, который является аналоговым [19].
О методах автоматизации аналогового проектирования стало известно, начиная с 70-х годов прошлого века. Проблемам автоматизированного структурного и параметрического синтеза аналоговых радиоэлектронных устройств было посвящено много трудов отечественных и зарубежных ученых. Ими был предложен ряд подходов к решению этой проблемы, в том числе методы классического синтеза электрических цепей [20], теоретико-множественные методы [21], методы целенаправленного и случайного поиска структур [22, 23], методы «выращивания» элементов [24, 25], методы перебора [25,26], сведение задач синтеза к оптимизационным проблемам [27, 28] и др.
Классический синтез электрических цепей является одним из распространенных методов и предусматривает решение задач аппроксимации и реализации. При решении задачи аппроксимации необходимо определить физически реализуемую функцию цепи, удовлетворяющую техническим требованиям. На этапе реализации синтезируется электрическая схема по найденной функции цепи [29, 30]. Указанные задачи имеют большое количество решений, поэтому на каждом этапе целесообразно определять оптимальное решение по определенным критериям. В качестве таких критериев используются, например, показатели чувствительности и стабильности [30-32]. Методы оптимальной аппроксимации применительно к задачам синтеза электрических цепей изучены достаточно глубоко, разработаны алгоритмы и программы расчета на ЭВМ [30, 33-35].
Оптимальная реализация электрических схем или оптимальный синтез является сложной и мало изученной задачей. Структурный синтез электрических схем разделен на два основных направления. Первое основано на теории эквивалентных преобразований Кауэра [26]. Множество электрических схем, из которых выбирается оптимальная структура, формируется путем эквивалентных преобразований определенной исходной схемы [36, 37]. Данный подход обладает существенными недостатками, такими как ограниченность получаемого множества эквивалентных схем и сложность учета условий физической реализуемости.
Второе направление основано на методе компонентных уравнений [38]. Множество структур получается из схемы исходной топологической структуры, а параметры элементов определяются при решении системы компонентных уравнений, учитывая заданный критерий оптимальности. В ходе решения этих уравнений некоторые параметры элементов могут принимать нулевые значения, что приведет к изменению структуры схемы.
Структурный синтез, основанный на методе компонентных уравнений является одним из перспективных методов оптимальной реализации [38]. В настоящее время распространение получил параметрический синтез электрических схем или оптимизация характеристик схемы в рамках заданной структуры [33, 36, 39-41]. Для решения задач параметрического синтеза применяются методы нелинейного математического программирования, а в качестве начальных значений элементов используются значения, полученные классическими методами.
В последние десять лет задачи структурного и параметрического синтеза аналоговых РЭУ вызвали интерес специалистов в связи с возросшей необходимостью их решения, а также появлением новых методов, идей и технических средств (современные ЭВМ). Решение этих задач в настоящее время стало актуальным в первую очередь по экономическим причинам из-за необходимости сокращения времени разработки радиоэлектронных изделий и уменьшения числа квалифицированных кадров. Именно поэтому указанная проблема является одним из основных вопросов рассматриваемых на большинстве международных конференций по автоматизированному проектированию. По всему миру в данном направлении работает много научных групп.
Благодаря усилиям ученых в этой области, были разработаны эффективные алгоритмы и программы структурного синтеза для некоторых классов аналоговых РЭУ, например, операционных усилителей [42-44]. Разработаны новые подходы решения задачи синтеза аналоговых РЭУ, основанные на современных достижениях в области искусственного интеллекта: применение баз знаний [45], эволюционный поиск на основе генетических алгоритмов [43] и генетическое программирование [42, 44], глобальные методы оптимизации [46-48] и др. С появлением этих методов разработано много экспериментальных программных комплексов синтеза РЭУ, в том числе ISAAC/OPTIMAN [46], ASTRX/OBLX [47], ANAKONDA [48], OPASYN [49], BLADES [45], OASIS [50], DARWIN [51], WYWIWYG [43] и др. С использованием этих программ реализован синтез различных аналоговых устройств, основанных на интегральной технологии, среди которых активные фильтры, операционные усилители, широкополосные усилители, автогенераторы и др. [42-44]. Только в некоторых случаях схемы устройств синтезированные в этих программах по своим характеристикам близки к устройствам, спроектированным человеком. Поэтому автоматически синтезированные РЭУ пока не могут превзойти результаты «ручного» проектирования. Это объясняется .сложностью задачи структурного синтеза аналоговых РЭУ, которую трудно формализовать [43]. Тем не менее, дальнейшее повышение степени автоматизации проектирования зависит именно от успехов в разработке эффективных алгоритмов и методов структурного синтеза.
Задачи структурного синтеза можно классифицировать по некоторым признакам. В зависимости от стадии проектирования, на которой производится синтез, выделим следующие процедуры: 1) выбор основных принципов функционирования устройства; 2) выбор технического решения в рамках заданного принципа действия; 3) оформление технической документации.
Для решения задач структурного синтеза необходимо решить проблему формализации этих процедур. Существуют следующие подходы к решению задач структурного синтеза: - методы (алгоритмы) перебора; - последовательные алгоритмы; - алгоритмы трансформации описаний.
Генетические операторы и структура генетических алгоритмов структурного синтеза РЭУ
Генетический алгоритм - это один из поисковых методов, основанный на эволюционной теории. Генетический алгоритм подобен процессам биологической эволюции, где наиболее приспособленные индивидуумы выживают и размножаются, а слабые умирают [69]. Со временем, через несколько поколений популяция становится оптимизированной и состоит из индивидуумов приспособленных к окружающей среде.
В первой главе был рассмотрен простой ГА, состоящий из трех основных операторов, и приведена его схема (Рис. 1.4). Ниже приведен псевдокод простого алгоритма: chromosome TopologyGeneticAlgorithm() { initializeGeneration(); bestValue = calculateFitnessOflndividuals(); while (bestValue desiredValue) { Selection(); Crossover ); MutationO; bestValue = calculateFitnessOflndividuals(); } return(chromosoneOf(best Value)); }
Данный генетический алгоритм может использоваться для решения разнообразных задач, однако для получения желаемых результатов необходима его адаптация под конкретную задачу. Поэтому ГА используемый для задачи структурного синтеза будет обладать некоторыми отличиями. Также в зависимости от типа синтезируемой схемы необходимо вносить определенные изменения в генетический алгоритм. В данной главе автором была разработана методика представления РЭУ в виде хромосомы для задачи структурного синтеза. Для кодирования индивидуумов было предложено использовать хромосому с целочисленным представлением фиксированной длины. Помимо этого на хромосому могут быть наложены определенные ограничения, например, значение некоторых генов фиксируется (в рассмотренном в подразделе 2.1 примере были зафиксированы значения 1-го и последнего генов хромосомы) - это первая особенность, которую необходимо учесть в ГА структурного синтеза схемотехнических решений. Вторым отличием является необходимость разработки собственной целевой функции для каждого типа задач. Также необходимо использовать модифицированные генетические операторы, которые будут учитывать специфику решаемой задачи.
Основываясь на вышеизложенном материале, составим схему генетического алгоритма структурного синтеза схемотехнических решений: 1. Ввод исходных данных (требования технического задания, максимальное количество и тип элементов схемы, параметры генетического алгоритма, шаг дискретизации). 2. Определение структуры хромосомы (определение длины и ограничений хромосомы). 3. Генерация начальной популяции. Установление номера текущей популяции NTeKym = 1. 4. Оценка популяции (использование составной целевой функции, в зависимости от типа синтезируемого устройства вторая часть целевой функции будет отличаться). 5. Проверка условия NTeKyiy Nn0JIH или выполнения условий технического задания. Если хотя бы одно из условий выполняется, переходим к пункту 12. 6. Оператор селекции (выбираем пару хромосом, для применения к ним генетических операторов). 7. Оператор кроссинговера (скрещивание пары хромосом, получение двух потомков). 8. Мутация потомков. 9. Оценка полученных потомков. 10. Замещение хромосом (добавление двух потомков в популяцию и удаление двух хромосом). 11- Нгекущ = Nrocyn, + 1, переход к пункту 5. 12. Вывод лучшего решения. 13. Конец работы алгоритма.
Структура генетических алгоритмов параметрического синтезаРЭУ
Например, при проектировании усилителя из базы знаний поступает информация, что для получения наилучшего результата необходимо использовать «Алгоритм №1». После применения данного алгоритма, экспертная система выводит оптимальное (по определенным критериям) решение, полученное в ходе проектирования. Поэтому возникает необходимость использования разных алгоритмов для каждого типа задач. Отличия этих алгоритмов проявляются в генетических операторах и в том, что для каждой задачи разрабатывается своя собственная целевая функция. Именно от качества выбранных операторов и целевой функции зависит эффективность работы генетического алгоритма.
Вообще, широко распространенный генетический алгоритм, использующий три оператора можно представить через следующие этапы [88]:
- Случайным образом создается популяция п двоичных строк. Эти двоичные строки называются хромосомами;
- Каждая хромосома оценивается относительно определенной спецификации, которая обычно является функцией, которую необходимо оптимизировать. Затем каждой хромосоме присваивается скалярное значение, называемое целевой функцией;
- Основываясь на значении целевой функции, популяция подвергается процессу селекции. Совокупность п хромосом выбирается вероятностным образом, таким способом, что более высокое значение целевой функции дает больше шансов в выборе хромосомы. Поэтому, несмотря на вероятностный характер, процесс селекции склонен к более приспособленным хромосомам.
- После процесса селекции, пара хромосом, выбранных из популяции случайным образом, и с определенной вероятностью, подвергается процессу кроссинговера. Оператор кроссинговера соединяет содержимое каждой пары хромосом, создавая два потомка, смешивая генетический материал представленный в строках их родителей. В случае если родители не подвергаются операции кроссинговера, они копируются неизменными в новую популяцию;
- Оператор мутации применяется к новой популяции хромосом, полученных после применения кроссинговера. Мутация обычно применяется с низким процентом ко всем двоичным разрядам, которые составляют хромосому. В случае успешного исхода, оператор мутации изменяет значение определенного разряда, иначе разряд остается неизменным; - После применения оператора мутации образуется новая популяция хромосом. Это новое поколение полностью проходит процесс описанный выше, от шага оценки до шага мутации; - Этот цикл повторяется, пока не будет встречен критерий останова, т.е. до тех пор, пока не будет достигнуто максимальное число поколений или не будет найдено желаемое решение.
В первой главе на Рис. 1.4 приведена схема классического генетического алгоритма, который может использоваться для решения большого числа различных задач. При проектировании электронных устройств важным моментом является адаптация структуры алгоритма под конкретную задачу. Хотя большая часть схемы при этом остается неизменной, существует, как минимум, несколько отличий, которые необходимо учитывать каждый раз при решении новой задачи [73, 89, 90].
Первой особенностью является методика представления РЭУ в виде альтернативного решения (хромосомы). Для кодирования индивидуумов можно использовать хромосому с двоичным, целочисленным или вещественным представлением фиксированной или переменной длины. Для некоторых задач необходимо занесение в строку информации обо всех параметрах, что значительно усложняет процесс кодирования и декодирования. Вторым отличием является то, что для каждого типа задач необходимо разрабатывать свою собственную целевую функцию. Помимо этого могут отличаться генетические операторы, как по типу, так и порядком их выполнения. Эффективность работы генетического алгоритма напрямую зависит от качества выбранных функций и генетических операторов.
Тогда на основании вышеизложенного материала составим схему генетического алгоритма параметрического синтеза усилителей: 1. Ввод исходных данных (требования технического задания, параметры генетического алгоритма, шаг дискретизации, библиотека моделей активных элементов). 2. Определение структуры хромосомы (для пассивных элементов задаются значения, а для активных их модели). 3. Генерация начальной популяции. 4. Оценка текущей популяции (использование целевой функции для усилителей). 5. Селекция усечения (отбор индивидуумов выше определенного значения ЦФ). 6. Объявление новой популяции - текущей. Установление номера Текущей ПОПуЛЯЦИИ N-гекущ = 1. 7. Проверка условия NTeKyw Nn0J]H или выполнения условий технического задания. Если хотя бы одно из условий выполняется, переходим к пункту 14. 8. Выбор пары хромосом, для применения к ним генетических операторов.
Определение основных параметров генетических алгоритмов для структурного и параметрического синтеза РЭУ
Целью экспериментальных исследований является доказательство эффективности разработанных алгоритмов, по сравнению с аналогичными алгоритмами, определение оптимальных параметров генетических алгоритмов. Объектами исследований в работе являются алгоритмы структурного и параметрического синтеза радиоэлектронных устройств.
Экспериментальные исследования разработанных генетических алгоритмов преследовали следующие цели [92]: 1. решение проблемы выбора параметров генетических алгоритмов; 2. исследование и доказательство эффективности разработанных алгоритмов.
Проблема выбора параметров генетических алгоритмов заключается в определении влияния параметров генетических алгоритмов на получаемые результаты. В ходе экспериментов необходимо определить параметры генетических алгоритмов, такие как тип селекции, кроссинговера, мутации, вероятность выполнения данных операторов, размер популяции и т.п., а также доказать эффективность разработанных алгоритмов, провести их сравнение с аналогами. Для решения поставленной задачи необходимо провести серию экспериментов с различными параметрами моделей и алгоритмов [92-94].
Для задачи структурного синтеза необходимо определить: - зависимость временных затрат на решение задачи от числа элементов синтезируемого схемотехнического решения; - для какого максимального числа элементов будет эффективен разработанный алгоритм.
В качестве критерия оптимальности алгоритма для задачи структурного синтеза используется минимальное количество элементов и узлов, представляющих найденное решение.
Для задачи параметрического синтеза необходимо определить: - зависимость времени решения задачи от числа параметров синтезируемого схемотехнического решения; - для какого максимального числа параметров схемотехнического решения будет эффективен разработанный алгоритм.
Для разработанных алгоритмов создан пакет программ на языке программирования C++, позволяющий значительно упростить процесс проектирования радиоэлектронных устройств [95]. Эксперименты были проведены на IBM PC совместимом компьютере с процессором Intel Pentium 4 3,0ГГц, памятью объемом 1Гб, операционной системой Microsoft Windows ХР.
Выбор оптимальных параметров генетических алгоритмов (тип селекции, кроссинговера, мутации, вероятность их выполнения, размер популяции и т.п.) является важной задачей, поскольку эти параметры влияют на качество получаемых решений и на время работы алгоритма [96, 97].
Определение оптимальных параметров генетических алгоритмов для конкретных задач в основном осуществляется методами вычислительного эксперимента. Это связано с отсутствием теорий, позволяющих анализировать динамику поведения генетических алгоритмов (сходимость, точность, время работы и т.п.) [79, 98-100]. Процесс определения параметров генетических алгоритмов предложено разбить на два этапа. В ходе первого этапа определялось влияние типа селекции и типа кроссинговера на качество получаемых решений. Рассматривались операторы элитной, случайной и турнирной селекции, модифицированные одноточечный и двухточечный операторы кроссинговера. В ходе экспериментов вероятность выполнения оператора кроссинговера Р0к принимала значения - 0.6, 0.7, 0.8, вероятность оператора мутации Р0м была равна 0,1. Размер популяции был выбран равным 100, для каждого из вариантов установки генетических параметров было проведено по 50 испытаний.
Второй этап заключался в определении оптимального размера популяции и вероятности мутации. Тип и вероятность выполнения операторов селекции и кроссинговера были взяты из первого этапа (при которых были получены лучшие результаты). Размер, популяции принимал значения - 50, 100 и 150; вероятность мутации - 0.05, 0.1 и 0.15.
Для задачи структурного синтеза радиоэлектронных устройств полученные схемотехнические решения оценивались по структурной сложности (количество элементов и количество узлов).
