Автор: Г.В. ЗЕМСКОВ, научный руководитель: Ю.С. БАЖАНОВ, НГТУ, 2004

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

Введение

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

В арсенале современного инженера множество методов решения данной задачи. Это методы сокращенного перебора,  морфологический подход, структурирование объекта, алгоритм Форда-Фалкерсона-Келли и случайный поиск. Каждый метод имеет свои преимущества и недостатки, а их применимость определяется условиями, которые определены при постановке задачи [1].

С начала 90-х годов в математике получило развитие новое направление, называемое прикладным эволюционным моделированием, которое объединяет несколько алгоритмов решения оптимизационных задач. Наиболее интересный среди них – генетический алгоритм, предназначенный для оптимизации функций дискретных переменных.
При решении задачи структурно-временного согласования [2], необходимо найти реализацию схемы с наименьшей сложностью при заданном ограничении на быстродействие (в математической интерпретации необходимо решить оптимизационную задачу нахождения экстремума функции (минимума) при заданных ограничениях).

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

Использование методов эволюционного моделирования для решения задач оптимизации

В качестве объекта исследования данной статьи выступает применение методов эволюционного программирования [3,4] для решения задачи структурно-временного согласования логических схем.

Исследование задачи согласования и методов эволюционного моделирования как единого целого, позволяет разработать полномасштабно функционирующий алгоритм структурно-временного согласования.

 Рассмотрим  задачу структурно-временного согласования. В качестве объекта TS-  согласования будем рассматривать любую комбинационную схему (КС), представленную как композиция блоков (блок – схема из нескольких логических элементов, реализующая конкретную законченную микрооперацию (МОП)). Причем сама комбинационная схема также может рассматриваться как блок.

Введем следующие обозначения: Tзад – заданное время срабатывания КС, T –  расчетное время срабатывания КС, S – стоимость реализации КС.
Время работы схемы будем определять ее  рангом, а стоимость – суммарным количеством входов/выходов всех логических элементов КС.
Тогда задача TS-согласования ставится, как нахождение таких комбинаций блоков, чтобы КС в целом отвечала следующим критериям:

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

Использование генетического алгоритма для структурно-временного согласования комбинационных схем в классической интерпретации усложнено необходимостью кодирования всех возможных реализаций группового переноса сумматоров и блоков, реализованных на базе сумматора [5]. Однако, как известно, не все сумматоры имеют групповой  перенос, за счет чего встает вопрос о длине хромосомы каждой особи. Поскольку, согласно алгоритму, в результате мутации особь без каких-либо ограничений может изменить любой ген, то, соответственно, и длина битовой последовательности, кодирующей хромосому, может изменяться в некотором диапазоне.

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

В свою очередь, кодирование параметров также представляет собой сложную задачу. Экспериментально установлено, что количество реализаций группового переноса сумматора (с учетом блоков, состоящих из одного разряда и содержащих все разряды) составляет 2n возможных вариантов, где n – разрядность сумматора. Применяя двоичное кодирование ГП, итерационная функция декодирования по номеру количества групп и разрядности групп работает достаточно длительное время, поскольку уже для разрядности в 128 бит количество возможных реализаций ГП сумматора составит 2128 ~ 3,4•1038,  а это еще не предел.
Соответственно, для ускорения работы предлагается произвести кодирование параметра в виде, представленном на Рис.1. После сборки из таких генов и параметров хромосомы фактически наблюдается эффект, который можно назвать переменной длиной хромосомы.

Кодирование параметра гена

 Рис. 1 Кодирование хромосомы

На рис.1 используются следующие обозначения m – количество блоков группового переноса, ki – разрядность i-го блока ГП, 0 < i ≤ m. За счет двухярусности кодирования гена достигается существенное увеличение скорости декодирования конкретной реализации, но увеличивается время, необходимое на кодирование случайным образом первоначального группового переноса и мутации ГП.

Физическая интерпретация

Физическая интерпретация генов, хромосом и популяций в данной реализации генетического алгоритма следующая:

Ген – одна из возможных реализаций блока микроопераций, заданных пользователем
Хромосома (особь) – одна из реализаций схемы, заданной пользователем, представляющая собой совокупность микроопераций, закодированных в генах.
Популяция – множество реализаций схем, закодированных в хромосомах.

Критерий качества

Поскольку задача структурно-временного согласования КС ставится как минимизации стоимости (сложности) схемы при суммарном быстродействии не хуже заданного, а генетические алгоритмы требуют увеличение критерия качества, то критерий в данном случае можно рассчитать из следующих соображений:
- первоначально необходимо накопить особи в популяции, которые отвечают заданному условию быстродействия при минимальной стоимости;
- затем вести постепенный отбор особей, которые обеспечивают минимальную сложность.
Исходя из вышесказанного, критерий приспособленности особи можно представить в следующем виде:

В формуле (2) используются следующие обозначения: k – критерий приспособленности, tзад – заданное время работы КС (быстродействие), t – время работы (быстродействие) текущей реализации КС, S – стоимость (сложность) текущей реализации КС. Отметим, что сложность КС, как правило, определяется суммарным количеством входов и выходов логических элементов, а быстродействие – максимальным рангом КС.

Генетические операторы

Поскольку кодирование генов особей не является стандартным, то, несмотря на то, что набор операций генетического алгоритма остается без изменений, внутреннее представление операций претерпевает некоторое изменение. Это связано в большей мере с переменной длиной хромосом и наличием параметров гена.

Генерация начальной популяции

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

Кроссовер

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

Физическая интерпретация оператора “кроссовер” для данной реализации генетического алгоритма – это обмен блоками микроопераций в двух схемах.

Мутация

Вероятность мутации определяется двумя параметрами: вероятность мутации гена и его параметра. Также как и оператор кроссовера, оператор мутации не может быть реализован стандартным образом. С заданными вероятностями выполняется мутация гена и мутация параметра. При этом исходный ген может мутировать только в ген микрооперации того же типа. А количество групп и их разрядность может варьироваться.

Физическая интерпретация оператора “мутация” для данной реализации генетического алгоритма – это замена блока МОП на эквивалентный. 

Отбор

При формировании новой популяции, отбор особей может быть осуществлен в алгоритме четырьмя способами – с помощью включения/отключения двух опций алгоритма: “хорошие без изменений” и “только лучшие после кроссовера и мутации”. Эти две опции определяют стратегию “элитизма”.  Первая из них гарантирует, что все особи с приспособленностью выше средней перейдут в следующее поколение без изменений. Вторая контролирует процесс  мутации и кроссовера таким образом, что из двух вариантов (до мутации и после мутации, и для каждой получившейся хромосомы в результате кроссовера), в новое поколение переходит только лучшая хромосома.

Исследование методов эволюционного моделирования для TS-согласования логических схем
На основе разработанного алгоритма было написано приложение для Windows, позволяющее выполнить TS-согласование комбинационной схемы, заданной формально.
Тестовая комбинационная схема обладает следующими  признаками:
 - содержит от 2 до 10 блоков идентичных микроопераций;
- отсутствуют обратные связи в КС.

На рис. 2 представлена КС, которая реализует, следующие микрооперации:

                                             (3) 

Приведенная схема на рис. 2 состоит из трех блоков, выполняющих микрооперацию сложения двух шестнадцатиразрядных чисел (код микрооперации в «ЭЛС 2.1» – 30).

Рис.  2 Схема тестового примера

Влияние параметров ГА на ход вычислительного процесса

В процессе подготовки тестовых примеров задавались различные параметры ГА. Изменялись следующие параметры:
- Размерность популяции
- Количество поколений
- Вероятности кроссовера и мутации
- Включение/отключение стратегий “элитизма”
- Параметр Tmin

Размерность популяции

Размерность популяции является одним из определяющих параметров при поиске глобального экстремума. Низкая размерность популяции приводит к быстрой сходимости ГА и малой области поиска возможных решений. Низкая скорость вычисления приспособленности каждой хромосомы, связанная с накладными расходами по запуску модулей экспертной системы “ЭЛС 2.1”, препятствует прогону тестового примера на популяции большой численности, поэтому максимальный размер популяции для ГА в прогонах  составлял 30 особей.

Результаты прогонов ГА с 20 и 30 особями практически не отличались, это объясняется малым количеством блоков МОП, из которых состоит тестовый пример.

Количество поколений

Для решения задачи TS-согласования в тестовых примерах количество поколений устанавливалось равным 100. Несмотря на это сходимость ГА наблюдалась уже на 20-м поколении. Быстрая сходимость обусловлена рядом причин: малое количество блоков микроопераций, из которых состоит тестовая схема, малое количество особей в популяции и стратегии “элитизма”.

Изменение вероятности мутации

В каноническом генетическом алгоритме, где ген кодируется двоичной битовой последовательностью, вероятность мутации гена рекомендуется устанавливать равной 0,1. Поскольку при решение задачи TS-согласования используется специфический формат генов, столь малое значение вероятности мутации не дает практически никакого результата: область поиска решений ограничивается приблизительно количеством случайно сформированных хромосом на начальном этапе и, как следствие, ГА сходится к локальному экстремуму.
Рекомендуемое значение вероятностей мутации гена и параметра – 0,7 и 0,5 соответственно. Данные значения зарекомендовали себя в качестве.

Увеличение вероятностей мутации приводит к медленной сходимости алгоритма при постоянном среднем значении сложности схемы.

Стратегия “элитизма”

Стратегия “элитизма” применяется в каноническом генетическом алгоритме для фильтрации наиболее приспособленных особей. Элитные особи чаще других участвуют в процессе скрещивания, могут переходить в следующие поколения без изменений и пр. В реализации ГА для решения задачи TS-согласования стратегия “элитизма” определяется двумя настройками ГА:
- “Хорошие – без изменений”.
Особи, приспособленность которых выше среднего переходят в следующее поколение без изменений (не подвергаются мутации)
- “Только лучшие после КО и М”
После операторов “кроссовер” и “мутация” из двух получившихся особей выбирается лучшая, и только она переходит в следующее поколение. Это способствует постоянному увеличению средней приспособленности поколения.
Каждая из двух стратегий является независимой.

Библиографический список

1. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. – М. МИР, 1966. –271 с.
2. Бажанов Ю.С. Интеллектуальные системы логического проектирования TS-согласованных цифровых устройств: Дис.  докт. техн. наук: 05.13.01 / Нижегородский государственный технический университет. – Н.Новгород, 1998. – 399 с.
3. Яблоков А.В., Юсуфов А.Г. Эволюционное учение (Дарвинизм): Учеб. для биол. спец. вузов. – 4-е изд., – М.: Высшая школа, 1998. – 336 с.
4. Курейчик В.М. Генетические алгоритмы и их  применение в САПР, Интеллектуальные САПР. Межведомственный тематический научный сборник,  Таганрог,  1995, с.7-11.
5. Потемкин И.С. Автоматизация синтеза функциональных схем: (на примере сумматоров с групповым переносом). – М.: Энергоиздат, 1981. – 88 с.