Реферат: В. В. Гудилов эволюционное проектирование аппаратных средств

Информатика, вычислительная техника и инженерное образование. – 2011. − № 5 (7)

РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ


УДК  681.3


В.В. Гудилов


ЭВОЛЮЦИОННОЕ ПРОЕКТИРОВАНИЕ АППАРАТНЫХ СРЕДСТВ


Рассматриваются методы эволюционного проектирования аппаратных средств, применение которых возможно для решения задач схемотехнического проектирования при неполной информации о синтезируемом объекте. В статье приводится подробное описание разработки алгоритма эволюционного синтеза комбинационных схем для базиса логических элементов и показаны методы перехода к синтезу более сложных схем. Много внимания уделяется разработке генетических операторов, методам кодирования и оценки схем, а также методам вероятностной передачи наследственной информации.

Эволюционный синтез; эволюционное проектирование; синтез с неполной информацией.


V.V. Gudilov


^ EVOLUTIONARY DESIGN OF HARDWARE


The Methods of evolutionary hardware's design, which application is possible for the decision of problems circuit designing by incomplete information about synthesized object, are considered. The article gives a detailed description of the algorithm's of the evolutionary synthesis combinational circuits for basis of the logic elements development, and the methods of transition to synthesis of more complex circuits are shown. Much attention is given to development of genetic operators, methods of coding and a rating of circuits, and also probabilistic methods of transfer of the hereditary information.

Evolutionary synthesis; evolutionary designing; synthesis with the incomplete information.


Введение


В современных исследованиях в области автоматизированного проектирования аппаратных средств [1] большое внимание уделяется самореконфигурируемым вычислительным системам [2,3] и эволюционным аппаратным средствам [4-6]. Приоритетными направлениями в исследованиях выступают нахождение новых методов проектирования аппаратных средств [7] и вывод задачи проектирования на качественно новый уровень. Необходимость данных исследований связана еще и с тем, что существующие методы проектирования не могут находить решения для задач, когда исходные данные задачи не полностью определены или постановка задачи является нечеткой. Для подобных задач, количество возможных вариантов решений значительно возрастает, и необходимо найти лишь те, которые будут соответствовать заданным критериям проектирования. Затруднения в этом случае испытывает и эксперт, выполняющий проектирование, т.к. человек не может одновременно оперировать множеством параметров, часть из которых так же является множеством в силу нечеткой постановки задачи. Таким образом, актуальным направлением в исследованиях выступает стремление разработчиков “научить” алгоритмы синтеза самостоятельно адаптироваться под поставленную задачу на основе методов эволюционного моделирования на примере решения задач схемотехнического проектирования, чему и будет посвящена данная статья.


^ Методология эволюционного проектирования


Алгоритмы эволюционного синтеза используют в своей основе многообразие методов искусственной эволюции синтезируемого объекта, в их основе лежит применение генетических алгоритмов и их модификаций. Для эволюционных алгоритмов синтеза постановка задачи проектирования, как и топологические ограничения, могут изменяться в режиме реального времени, при этом, синтезируемые решения генерируются согласно заданного многообразия (базиса) функциональных элементов, т.е. получаемые решения не являются шаблонными.

Классическая задача структурного синтеза рассматривает синтез структуры объекта по его функциональному описанию. Исходным описанием для задач проектирования цифровых схем зачастую выступает математическое представление задачи на основе графа, булевой алгебры или заданной таблицы истинности, полностью или частично отражающей требуемые состояния искомой схемы. Дополнительными ограничениями выступает функциональный базис элементов, на основе которого производится синтез, параметры топологии синтезируемого объекта, возможное количество элементов, минимальная и максимальная задержка распространения сигнала и пр.

Многообразие проектируемых решений задачи рассматривается генетическими алгоритмами (ГА) [8−10] как набор особей (хромосом) популяции, степень приспособления особи к критерию выживания которых, оценивается функцией критерия. Отличительной чертой применения эволюционных методов для решения задачи схемотехнического проектирования выступает необходимость построения модели синтезируемой схемы, на основе которой выполняется оценка величины критерия приспособленности каждой особи. В качестве такой модели может быть рассмотрена математическая модель или выполнено построение и оценка схемы на заданном диапазоне параметров функционального описания. Тогда критерий выживания определяет совокупную приспособленность синтезируемой схемы к заданному закону функционирования искомой схемы. Но с другой стороны, для цифровой схемы, сложно выполнять оценку качества только лишь по совокупной приспособленности к заданному функциональному описанию, т.к. незначительные изменения в топологии схемы или функциональном наборе могут привести к неработоспособности всей схемы, в то время, как отдельные ее участки могут соответствовать искомому решению.

В работе [7] автором предложено применение вероятностных методов передачи наследственной информации для сохранения и передачи функционально-верных участков схемы, положенных в основу разработанного вероятностного генетического алгоритма. Предложенные методы позволяют выполнять оценку вероятности наследования структурных и функциональных составляющих синтезируемых схем, определенных как многообразие генетического материала, и выполнять передачу в последующее поколение вероятности использования параметров генетического материала, а не сам материал в исходном виде, что отличает подобные алгоритмы от классических ГА. Таким образом, сходимость генетического материала к требуемым параметрам выполняется быстрее, т.к. каждое поколение синтезируемых схем наследует множество лучших параметров схемных решений из предыдущих итераций, а вероятностные оценки вносят элемент случайности, препятствующий преждевременной сходимости алгоритма к локальным оптимумам.


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


Рассмотрим применение эволюционных алгоритмов для решения задачи проектирования схем на примере синтеза комбинационных схем. Представим задачу синтеза комбинационных схем как множество R = {H, cF, P}, где элемент множества H определяет генотип синтезируемого решения, cF – оценку его математической модели и P определяет вероятность наследования генетического материала из текущей популяции в последующую. Генотип синтезируемого решения H определяется выбранным методом кодирования синтезируемых схем и кодирует метод представления архитектуры целевого устройства. Тогда построение математической модели есть не что иное, как переход от метода построения архитектуры к представлению (математическому или физическому) синтезируемой схемы. Тогда оценка математической модели cF есть, нечто иное, как критерий отбора, на основе которого выполняется отбор оптимальных решений и формируется признак нахождения решения.

В рамках данной работы, мы не затрагиваем физические аспекты распространения сигналов в цепи схемы, исключаем эффекты гонок и, в общем, идеализируем синтезируемую схему, рассматривая лишь ее функциональную составляющую. То есть на этапе разработки алгоритма синтеза нас интересует вопрос применения ГА для нешаблонного синтеза схем по функциональному описанию задачи. Учет временных параметров схемы, как и переход к реализации схем с обратными связями и элементами памяти возможен, но это отразится на сложности алгоритма оценки схем, поэтому в рамках данной работы рассмотрен не будет.

Для алгоритма эволюционного синтеза комбинационных схем для базиса логических элементов (ЛЭ) кодирование хромосомы определяется на основе матричного представления схемы Mm,n (рис. 1,а), содержащей абстрактные логические элементы, посредством перехода от двумерной индексации ЛЭ (столбец m, строка n) в синтезируемой схеме к одномерной. Число с входов xс, поступающих на схему, образуют нулевой столбец входов элементов L0,n, где n = с задает количество строк матрицы Mm,n. Количество выходов схемы yq, определяется согласно количеству q выражений, описывающих закон функционирования искомой схемы. Номера элементов Lr,t в схеме имеют сквозную нумерацию, совпадающую с нумерацией логических элементов внутри матрицы Mm,n и используемую при синтезе схемы для обозначения выхода элемента. Индексы элементов Lr,tr и t задаются согласно порядковому расположению элемента в матрице Mm,n, по возрастанию слева направо и сверху вниз, где 0 ≤ t < n и 0 ≤ r ≤ m (нулевой столбец m = 0 содержит сигналы входов схемы, т.е. количество столбцов m дополнено столбцом входов). Выходы схемы y подключаются только к выходам элементов Lr,t столбца m (r = m), при этом элемент нулевой строки Lm,0 соответствует нулевому выходу y0 схемы и т.д.

В качестве минимального базиса ЛЭ определим множество L = {Li | i = 1, 2,..., nl}, элементами которого являются стандартные двухвходовые элементы “И”, “ИЛИ”, “XOR” и одновходовые элементы “НЕ” и “WIRE”, имеющие один выход, где nl – количество элементов множества. Функциональные составляющие элементов “И”, “ИЛИ”, “XOR” и “НЕ” аналогичны соответствующим им логическим элементам. Функциональный элемент “WIRE” (перемычка) выполняет передачу сигнала, поступающего на единственный вход элемента к выходу, без каких-либо изменений функциональной составляющей входного сигнала. Кодирование элементов функционального базиса выполняется посредством назначения кода в порядке возрастания их порядкового номера (рис. 2).




Рис. 1. Матричное представление схемы: а) представление схемы, содержащей матрицу n на m ЛЭ Lr,t, имеющую с входов и q выходов; б) представление структуры хромосомы, кодирующей схему




^ Рис. 2. Кодировка логических элементов на основе заданного базиса


Расположение АЛЭ в узлах решетки схемы остается неизменным в процессе синтеза схемы, а изменяется лишь их функциональная составляющая (код) и соединения между входами и выходами элементов. Логический элемент Lr,t, кодируемый геном gr,t, заносится в хромосому H последовательно, по столбцам, от младшего элемента t столбца r к старшему, где 0 < r ≤ m, 0 ≤ t < n (см. рис. 1,б). Каждый ген хромосомы H определяется вектором gn = {gni | i = 1,2,3}, который кодирует отдельно взятый ЛЭ Lr,t, где элементы вектора gn1 и gn2 задают информацию о входах r и t ЛЭ Lr,t, и gn3 задает код кодируемого ЛЭ Lr,t. Локус гена в хромосоме соответствует заданной позиции кодируемого им элемента в схеме, т.о. значение, получаемое на выходе ЛЭ, ассоциируется с отождествляемым ему геном. Переход к многовходовым схемам возможен посредством дополнения функционального базиса новыми элементами и модификации структуры гена хромосомы. Приведенные методы кодирования схем могут быть легко доработаны для различных представлений структуры целевых устройств и включать необходимые технологические ограничения, требуемые для реализации задачи синтеза с учетом специфики функционирования целевого устройства. Подобные ограничения достаточно отразить в структуре гена или хромосомы и в дальнейшем учитывать при анализе схемы.

Для анализа синтезируемой схемы разработан метод построения математической модели (ММ) схемы с ее последующим анализом на s = 2c входных наборах ТИ, где с − количество входных переменных функций. Построение ММ схемы для схем на основе ЛЭ определен как переход от одномерного массива ЛЭ, кодирующего фенотип в виде хромосомы, к некоторому множеству двумерных массивов Zm,n(матриц размерности m на n), элементы которых отражают функциональную составляющую синтезируемого объекта. Элементы Zm,nпредставлены в виде матриц Zem,n, Zin1m,n, Zin2m,nи Zoutm,n, где Zem,n задает матрицу кодов ЛЭ, Zin1m,nи Zin2m,nопределяют адреса ЛЭ, подключаемых к входам текущего ЛЭ, Zoutm,nсодержит значения выходов ЛЭ. Построение ММ схемы выполняется посредством анализа ген хромосомы и построения на их основе матрицы кодов ЛЭ Zem,nи матриц адресов входов Zin1m,nи Zin2m,n. Матрицы выходов ЛЭ Zoutm,nформируются для каждого набора s входных сигналов схемы на основе набора состояний входных сигналов в ТИ.

Степень соответствия эволюционирующей и искомой схемы определена как критерий cF, значение которого изменяется в интервале от нуля до единицы, т.е. при полном соответствии эволюционирующей и искомой схемы cF принимает единичное значение. Искомая ТИ определяется на основе входных функций, эволюционирующая ТИ вычисляется посредством установки s входных значений из искомой ТИ на входы ММ схемы с занесением в таблицу значений с выходов схемы. Результатом построения ММ является построение эволюционирующей ТИ TTz, элементы которой сравниваются с элементами искомой ТИ TTf, где ТИ представлены в виде матриц:


(1)


размерности s на q элементов. Тогда значение соответствия hiti вычисляется как:


(2)


где 0 ≤ i < U, 0 ≤ j < s, 0 ≤ v < q и hiti определяет результат выполнения операции сравнения i-го элемента матриц TTz и TTf. Таким образом, критерий оценки cF для хромосомы j вычисляется на основе соотношения:

. (3)

Данное значение критерия оценивает функциональную составляющую схемы и при значении , схема j, кодируемая хромосомой H(j), стремится к искомому решению. Таким образом, параметром эволюции выступает степень соответствия схемы искомому решению. Предложенная ММ рассматривает схему с позиции идеализированной, с упрощением физических процессов прохождения сигнала через ЛЭ. Учет в ММ специфики функционирования целевых устройств, а также методов оценки схем с памятью, синхронизацией по фронтам и пр., позволяет модифицировать алгоритмы синтеза для различных схем и целевых устройств, что позволяет расширить область применения рассматриваемого алгоритма синтеза.

Передача генетического материала выполняется на основе лучших решений, для выбора которых предназначен оператор отбора, выполняющий перемещение из популяции Пcs, размера Ps, заданного количества Es хромосом el(i) с максимальным значением критерия cF(j) в порядке убывания cF(j), где 0 < i ≤ Es, 0 < j ≤ Ps и i ≤ j. Разработанный метод передачи наследственной информации определен вектором вероятности P = {pi | i = 1, 2,..., hL} наследования генетического материала из множества элитных хромосом Hel текущей популяции Псs в последующую популяцию Псs+1, где hL – длина хромосомы. Величина pi определяет степень отношения многообразия генетического материала для гена gi, представленного в локусе i хромосом элитной области, к величине Es элитной области. В случае бинарного кодирования хромосомы, величина pi определяет вероятность наследования единичных ген:

. (4)

При десятичном кодировании схемы, когда ген хромосомы задает ЛЭ, элементы pi вектора P определяют вероятность наследования всех возможных состояний гена gi и имеют длину, определяемую количеством состояний, которое может принимать ген gi. Значение векторов вероятности piможет изменяться в интервале от нуля до единицы и при единичном значении означает, что гены в локусе i хромосом H последующей популяции Псs+1унаследуют доминирующее значение генетического материала данного гена. Пример вычисления вектора вероятности передачи наследственной информации приведен на рис. 3.




Рис. 3. Пример вычисления вектора вероятности для десятичного представления хромосомы

Исходная популяция из заданного количества Ps хромосом ^ H генерируется случайным образом. В процессе эволюции генерация i-го гена хромосомы выполняется на основе выбора значений вероятности, определяющих вероятность наследования комбинаций для i-го гена хромосомы, как результат сравнения числа, сгенерированного случайным образом, и значений вектора вероятности, представленных соответствующим вектором pi.

В качестве дополнительного механизма передачи генетического материала в диссертационной работе разработан метод сегрегации, в основу которого положен метод элитизма (давления элитных хромосом), позволяющий накапливать генетический материал, что оказывает существенное влияние на сходимость алгоритма. Механизмом предотвращения предварительной сходимости разработанных алгоритмов выступает разработанный метод направленной мутации, не разрушающий схему и применяемой только при попадании алгоритма в локальный оптимум. Для расширения многообразия топологий синтезируемых решений предложен метод вывода популяции из области глобального экстремума на основе метода редукции, исключающего из популяции хромосомы представляющие искомое решение.

Алгоритм эволюционного синтеза комбинационных схем приведен на рис. 4. В рамке указана итерационная часть алгоритма, включающая генерацию популяции, анализ синтезированных схем посредством построения ММ, оценку схем на основе вычисления значения критерия, проверку нахождения решений, если критерий останова не достигнут (не найдено заданное количество решений или не выполнено заданное кол-во итерационных циклов), то выполняется формирование элитной области и вычисление вероятности. После вычисления вероятности для всех ген хромосомы выполняется переход к следующему итерационному циклу.





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


На рис. 5 показан пример решения задачи синтеза одноразрядного сумматора с функцией переноса для заданного базиса логических элементов на основе представленного алгоритма эволюционного синтеза комбинационных схем.




^ Рис. 5. Пример синтезированной схемы для одноразрядного сумматора с функцией переноса для заданного базиса логических элементов


Результаты проведенных исследований алгоритма эволюционного синтеза комбинационных схем показали значительное превосходство в быстродействии данного алгоритма при сравнении с аналогами. Также в работе [7] приведено подробное описание аппаратной реализации разработанного алгоритма эволюционного синтеза. Необходимо заметить, что преимуществом предложенного метода перехода к оценке хромосом на основе векторного представления является возможность развернуть матричное представление информации в векторное и провести синтез, используя сравнения вероятности различных решений. Данный подход позволяет уйти от классической оптимизационной задачи, решение которой выполняется по некоторому, как правило, сложно-вычисляемому алгоритмическому критерию, к задаче удовлетворения ограничений. Это другого класса задача, она решается достаточно просто с использованием матричных операций: сравнения на основе матриц, легко поддающихся программной и аппаратной реализации.


Заключение


Представленный в статье алгоритм эволюционного синтеза комбинационных схем может быть обобщен на решение более сложных задач, применяемых, в том числе, в задачах поиска последовательных схем в рамках заданного функционального базиса элементов, соответствующих требуемым временным и топологическим ограничениям для случая, когда постановка задачи определена нечетко или задача поставлена с потерей некоторой информации непервостепенной важности. Решение задачи структурного синтеза с применением эволюционных алгоритмов необходимо для дальнейших исследований в области построения алгоритмов эволюционного проектирования сложных систем, для которых, зачастую, в системе присутствуют неточности и неполнота описаний как отдельных частей, так и общих требований к системе в целом. В этом случае структурный синтез рассматривается в совокупности с параметрическим и функциональным синтезом для нахождения оптимальных конструкторских и технологических решений.


^ БИБЛИОГРАФИЧЕСКИЙ СПИСОК


R.S. Zebulum, M.A. Pacheco, M.M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms // USA, CRC Press LLC, 2002.

Brandon Blondet, Philip James-Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform //Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings, pp. 565-574.

Reetinder Sidhu, Sameer Wadhwa, Alessandro Mei and Viktor K. Prasanna. A Self-Reconfigurable Gate Array Archtecture// Field-Programmable Logic and Applications. The Roadmap to Reconfigurable Computing. 10th International Conference, FPL 2000, Villach, Austria, August 27-30, 2000 Proceedings.

Hemmi H., Mizoguchi J. and Shimonara K. Development and evolution of hardware behaviours, in Towards Evolvable Hardware: An International Workshop, Lausanne, Swiss, 1995.

Higuchi T. et al., Evolvable hardware and its applications to pattern recognition and fault-tolerant systems, in Towards Evolvable Hardware: An International Workshop, Lausanne, Swiss, 1995.

Keymeulen D., Durantez M., Konaka K., Kuniyoshi Y. and Higuchi T. Evolution of a digital circuit for a robot navigation system, in Proc. of the First International Conference on Evolvable Systems: From Biology to Hardware (ICES96), Tsukuba, Japan, Goos, G., Hartmanis, J., and Leeuwen, J. van, Eds., vol. 1259, LNCS, Springer-Verlag, 1996.

Гудилов В.В. Разработка и исследование алгоритмов эволюционного синтеза комбинационных схем / Диссертация. − Таганрог, 2007.

Курейчик В.М. Генетические алгоритмы и их применение / Монография. − Таганрог: Изд-во ТРТУ, 2002.

В.В. Курейчик. Биоинспирированный поиск с использованием сценарного подхода // Известия ЮФУ. Технические науки. – 2010. − № 7. – С. 7-13.

В.В. Курейчик, С.И. Родзин. О правилах представления решений в эволюционных алгоритмах // Известия ЮФУ. Технические науки. – 2010. − № 7. – С. 13-21.


Гудилов Виталий Витальевич.

ООО "Инвестиционный консультант", г. Ростов-на-Дону.

Е-mail vgudilov@mail.ru.

344000, г. Ростов-на-Дону, ул. Евдокимова 190

Тел.: 89198781600

Технический директор.


Gudilov Vitaly Vitaljevich.

LTD “Investment consultant”, Rostov-on-Don.

E-mail vgudilov@mail.ru.

190 Evdokimova, Rostov-on-Don, 344000, Russia.

Phone.: +79198781600.

Technical director (CTO).