Разработка и исследование алгоритмов эволюционного синтеза комбинационных схем

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

ОГЛАВЛЕНИЕ
Введение.

1. АЛГОРИТМЫ ЭВОЛЮЦИОННОГО СИНТЕЗА КАК СРЕДСТВО АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

2.1 Классификация алгоритмов синтеза

2.2 Постановка задачи диссертационной работы

2.3 Специфика проектирования эволюционных аппаратных средств

2.4 Классификация эволюционных аппаратных средств.

2. РАЗРАБОТКА АЛГОРИТМОВ ЭВОЛЮЦИОННОГО СИНТЕЗА

КОМБИНАЦИОННЫХ СХЕМ

2.1 Разработка бинарного генетического алгоритма для ПЛМ

2.1.1 Разработка бинарных генетических операторов

2.1.2 Разработка структуры генетического алгоритма для ПЛМ
2.2 Разработка десятичного генетического алгоритма для ПЛМ
2.3 Разработка десятичного генетического алгоритма синтеза
комбинационных схем для логических элементов.
2.3.1 Разработка методов передачи наследственной информации
2.3.2 Разработка алгоритма генерации популяции.
2.3.3 Разработка структуры генетического алгоритма для логических элементов
3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ЭВОЛЮЦИОННОГО СИНТЕЗА
КОМБИНАЦИОННЫХ СХЕМ.
3.1 Разработка устройства автоматизированного синтеза комбинационных схем для ПЛМ
3.1.1 Разработка параллельных генетических операторов
3.1.2 Разработка структурной схемы алгоритма автоматизированного синтеза комбинационных схем для ПЛМ.
3.1.3 Анализ разработанного устройства автоматизированного синтеза комбинационных схем для ПЛМ.
3.2 Особенности разработанного генетического алгоритма автоматизированного синтеза комбинационных схем
3.2.1 Структура взаимодействия генетического материала.
3.2.2 Анализ генетических операторов.
3.2.3 Временная сложность функционирования алгоритма синтеза.
3.2.4 Схемотехническое представление синтезированных
комбинационных схем
Заключение
СПИСОК ЛИТЕРАТУРЫ


Различают параметрический и структурный синтез. Задачи параметрического синтеза -это совокупность задач, связанных с определением требований к параметрам объекта, номинальных значений параметров и их допусков, в условиях, когда известны структура объекта или его топология. Сложность задач структурного синтеза заключается в том, что формирование и отбор решений осуществляется только на основе соответствия заданных соотношений вход/выход, т. В зависимости от степени формализации задачи синтеза условно можно разделить на несколько уровней сложности. К первому уровню сложности необходимо отнести задачи, в которых требуется выполнение только параметрического синтеза, в то время как структура объекта задана спецификой технического задания или результатами процедур, выполненных на более ранних этапах проектирования. Второй уровень сложности представляют задачи, в которых возможен полный перебор известных решений, т. При увеличении мощности множества элементов, когда алгоритмы перебора не могут найти решение за приемлемое время или задача с трудом поддается четкой формализации, или становится многопараметрической, задачу синтеза следует отнести к третьему уровню сложности. Примерами таких задач могут быть задачи компоновки и размещения элементов на платах, трассировки соединений и др. Если мощность множества поиска становится неизвестной или отсутствует какая-либо информация, способная ввести ограничение на параметры проектирования, то такую задачу синтеза следует отнести к четвертому уровню сложности. Формализация таких задач наиболее трудоемка, и одним из методов решения может быть методика, суть которой сводится к нахождению среди многих генерируемых структур такой, которая будет удовлетворять определенным (пусть и не всем) количественным требованиям. В качестве вспомогательного механизма рациональным является применение методов эволюционного поиска, способных находить решения в областях, сведения о которых недостаточно определены или в условиях, когда задача не имеет четкой формализации. Нетрудно видеть, что возможен перевод задачи из четвертого уровня сложности в третий, при условии, что вводятся ограничения на область поиска и задаются граничные параметры исследуемого объекта. Выделив несколько уровней сложности задач синтеза, можно формализовать методики их решения. Рассматривая уровни сложности как иерархию, к самому низшему уровню необходимо отнести методы, в основе которых заложены алгоритмы перебора, способные выполнять оценку различных вариантов на основе перебора готовых законченных структур. На самом высоком уровне в иерархии методик решения могут быть использованы алгоритмы трансформации описаний различных аспектов, суть которых может быть представлена в выделении некоего базиса (скалярного критерия), объединяющего частные показатели в многокритериальных ситуациях. На рисунке 1. Тогда рассматриваемые в диссертационной работы алгоритмы синтеза в рамках приведенной классификации представим как переборные, в основе которых положен частичный перебор с генерацией схем из заданных элементов. Но так как данная классификация полностью не охватывает специфику, заложенную в эволюционные алгоритмы, где синтез выполняется не на основе частичного перебора, а посредством эволюции схемы объекта проектирования, то целесообразно определить алгоритмы эволюционного синтеза (АЭС), являющиеся подклассом переборных алгоритмов структурного синтеза и использующие в своей основе многообразие методов искусственной эволюции синтезируемого объекта. Специфика функционирования данных алгоритмов эволюционного синтеза будет положена в основу разрабатываемых в данной диссертационной работе алгоритмов автоматизированного синтеза. Разработку алгоритмов синтеза проведем на примере решения задачи построения математической модели (ММ) синтезируемой схемы, в которой будет введен ряд упрощений принципа функционирования комбинационных схем. В частности, будут рассматриваться входные сигналы, принимающие только два значения: логическая единица и логический нуль.