Библиотека

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

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

Результатом данной работы должна стать программа которая будет создавать входные последовательности с помощью которых будет возможно проверять широкий спектр неисправностей, Т = 80 - 90%.

Для создания данной программы я решил использовать одно из новых и наиболее перспективных на данный момент направлений Генетические алгоритмы.

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

Генетические алгоритмы (ГА) - алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора. Эти принципы основаны на следующих механизмах эволюции.

1. Первый принцип ГА основан на концепции выживания сильнейших и естественного отбора по Дарвину, которая была сформулирована им в 1859 г. в книге "Происхождение видов путем естественного отбора". Согласно Дарвину особи, которые лучше способны решать задачи в своей среде выживают и больше размножаются (репродуцируют). В ГА каждая особь представляет собой некоторое решение данной проблемы (например, поиска экстремума функции). По аналогии с этим принципом потомки с лучшими значениями целевой (фитнесс) функции имеют большие шансы выжить и репродуцировать.
2. Второй принцип ГА обусловлен тем фактом, что хромосома потомка состоит из частей, получаемых из хромосом родителей. Этот важнейший принцип был открыт в 1865 г. Менделем.
3. Третий принцип, используемый ГА, основан на концепции мутации, открытой в 1900 г. де Вре (Vries). Первоначально этот термин использовался для описания существенных (резких) изменений свойств потомков и приобретение ими свойств, отсутствующих у их родителей. По аналогии с этим принципом ГА используют подобный механизм для изменения свойств потомков и тем самым повышая разнообразие (изменчивость) особей в популяции (множестве решений).
4. Эти три принципа составляют ядро ГА. Используя эти принципы, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению

Классический "простой" ГА использует двоичные стринги для кодирования решения проблемы - особи. Это делает его привлекательным для использования в задачах генерации проверяющих тестов логических схем, где решение задачи представляется в виде двоичных наборов или их последовательностей. На множестве решений определяется целевая (fitness) функция (ЦФ), которая позволяет оценить близость каждой особи к оптимальному решению. Простой ГА использует три основных оператора: репродукция, кроссинговер-скрещивание, мутация. Используя данные операторы, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению. Таким образом, чтобы задать ГА для решения конкретной проблемы, необходимо определить понятия особи, популяции, операций скрещивания и мутации, задать оценочную функцию.

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

1. Оператор репродукции (ОР);
2. Оператор скрещивания ( кроссинговера, ОК);
3. Оператор мутации (ОМ).

Рассмотрим кратко каждый из этих операторов рассмотрев процессы которым данные операторы соответствуют.

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

Очевидно, оператор репродукции является искусственной версией натуральной селекции - выживания сильнейших по Дарвину. Этот оператор представляется в алгоритмической форме различными способами. Самый простой (и популярный) метод реализации ОР - построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный ее значению ЦФ.

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

Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью Pok выполняется в 3 этапа:

1-й этап. Две хромосомы выбираются случайно (или одним из методов, рассмотренных в разделе _ "современные модификации и обобщения ГА") из промежуточной популяции, сформированной при помощи оператора репродукции (ОР). Иногда 1-й этап может выполняться и без ОР.

2-й этап. Случайно выбирается точка скрещивания - число k из диапазона [1,2…L-1], где L - длина хромосомы (число бит в двоичном коде )

3-й этап. Две новых хромосомы A', B' формируются из A и B путем обмена подстроками после точки скрещивания:

Следует отметить, что ОК выполняется с заданной вероятностью Pok (отобранные два родителя не обязательно производят потомков !!!). Обычно величина Pok = 0.5.

Т.о. операторы репродукции и скрещивания очень просты - они выполняют копирование особей и частичный обмен частей хромосом.

Далее согласно схеме классического ГА с заданной вероятностью выполняется оператор мутации. Иногда этот оператор играет вторичную роль. Обычно вероятность мутации =0,001.

Оператор мутации (ОМ) выполняется в 2 этапа:

1-й этап. В хромосоме A случайно выбирается k -позиция (бит) мутации ( 1 k L ).

2-й этап. Производится инверсия значения гена в k-й позиции.

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

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

1. Работают не с параметрами, а с закодированным множеством параметров.
2. Осуществляет поиск из популяции точек, а не из единственной точки.
3. Использует целевую функцию непосредственно, а не ее непосредственное приращение.
4. Использует не детерминированные, а вероятностные правила.

ГА в генерации тестов

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

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

Библиотека

1. В.А. Ярославцев, Ю.А. Скобцов Исследование и разработка генетических алгоритмов построения тестов для цифровых схем (статья)., Донецк, Сборник статей магистров, 2004    Электронный вариант статьи
2. Д.-Э. Бэстенс, В.М. Ван Ден Берг, Д. Вуд. Hейронные сети и финансовые рынки., Москва, научное издательство. ТВП., 1997.
3. Галушкин А.И. Hейрокомпьютеры и их применение. Книга 1. Теория нейронных сетей. Москва, Издательское предприятие редакции журнала. Радиотехника., 2000.
4. Тейво Кохонен, Гвидо Дебок. Анализ финансовых данных с помощью самоорганизующихся карт., Москва, издательский дом .Альпина., 2001.
5. Ф. Уоссерман. Hейрокомпьютерная техника., Москва, издательство Мир, 1992.
6. Шумский C.A. Hейрокомпьютинг и его применение в экономике и бизнесе., Москва, издательство МИФИ, 1998.
7. А.И. Змитрович Интеллектуальные информационные системы. - Минск.: HТООО "Тетра Системс", 1997. - 368с.
8. В.В. Корнеев, А.Ф. Гарев, С.В. Васютин, В.В. Райх Базы данных. Интеллектуальная обработка информации. - М.: «Hолидж», 2000. - 352с.
9. С.А. Закусило, Д.Е. Иванов, В.Ю. Скобцов.. Эволюционный подход к генерации проверяющих тестов цифровых схем (статья) Труды конференций "Интеллектуальные САПР". - Москва: Физматлит. - 2003 - С.76-78.
10. Исаев Сергей, Популярно о генетических алгоритмах, Электронный вариант