Исходный URL: http://www.uran.donetsk.ua/~masters/publ2004/kita/kita_yaroslavtsev
ИССЛЕДОВАНИЕ И РАЗРАБОТКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ПОСТРОЕНИЯ ТЕСТОВ ДЛЯ ЦИФРОВЫХ СХЕМ
Ярославцев В.А.
ДонНТУ
Факультет компьютерных информационных технологий и автоматизации
E-mail: HranitelEFA_dntu@mail.ru
Abstract:
Yaroslavtsev V.A. Research and development genetical algorithms of construction of the tests for digital circuits. Clause describes use of genetic algorithms for construction of checking tests of digital schemes. The program which is created builds sets of checking sequences, using three basic operators of a reproduction, crossing and mutations.
Введение
На сегодняшний день исследования в области эволюционных вычислений является одной из самых перспективных и динамично развивающихся отраслей знаний в мире. То, что впервые описал Гольдберг на основе работ Холланда, теперь нашло своё признание во многих областях науки, организовав самостоятельное направление - эволюционные вычисления. Применение генетических алгоритмов как одного из самых интересных понятий уже привело науку к невероятным результатам. Так в Стэнфордском университете создана компьютерная система способная самостоятельно делать изобретения.
Система основана на использовании генетических алгоритмов. Сначала создаётся "среда", образованная множеством правил. Все вместе они определяют задачу, которую придётся решить. В этот исскуственный мир подселяются много сот тысяч "обитателей" - сгенерированных случайным образом программ, каждая из которых соответствует одному из подходов к решению задачи. Затем они начинают "жить": программы скрещиваются, мутируют и отбраковываются поколение за поколением.
Как и при настоящей эволюции, в итоге выживают сильнейшие - программы, определяющие наилучшие решения задачи. Поскольку система использует для работы мощный тысячеузловый кластер, принадлежащего компании Genetic Programming, сроки вычислений вполне разумны.
Хотя сами эти программы и их "мир" сделаны по образу и подобию примитивных одноклеточных существ, результаты, которые даёт система, на удивление разумны. К настоящему моменту система совершенно независимо повторила несколько настоящих изобретений, запатентованных в Америке в период с 1917 по 1974 год.
Цель нашей работы заключается в создании компьютерной системы которая на базе выбора и использования наиболее эффективных и оптимальных методов обработки данных при помощи генетических алгоритмов, сможет продуцировать построение проверяющих тестов для цифровых схем.
Актуальность данной темы диктуется быстрым темпом роста производства цифровых схем с всё более миниатюрными размерами и с всё большим количеством деталей, таких как транзисторы. Но как известно: Количество не всегда значит качество. Создавая всё новые и новые схемы, производители уделяют недостаточно сил, времени и средств, на проверку и до усовершенствование своих изделий, теряя при этом боснословные материальные ресурсы. Создание системы, компьютерной системы, которая бы в течении не длительного промежутка времени могла бы с достаточно высокой точностью проверять цифровые схемы при помощи построенных ею проверяющих тестов, могла бы намного сократить затраты производителей на изготовление комплектующих, а следовательно и дала бы возможность снизить стоимость данной продукции, что без сомнения отразилось бы и на конечных пользователях.
Рассмотрим, что же такое генетический алгоритм и каковы его реальные и перспективные возможности построения тестов для цифровых схем.
Генетические алгоритмы (ГА) – алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора.
Классический “простой” ГА использует двоичные стринги для кодирования решения проблемы – особи. Это делает его привлекательным для использования в задачах генерации проверяющих тестов логических схем, где решение задачи представляется в виде двоичных наборов или их последовательностей. На множестве решений определяется целевая (fitness) функция (ЦФ), которая позволяет оценить близость каждой особи к оптимальному решению. Простой ГА использует три основных оператора: репродукция, кроссинговер-скрещивание, мутация. Используя данные операторы, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению. Таким образом, чтобы задать ГА для решения конкретной проблемы, необходимо определить понятия особи, популяции, операций скрещивания и мутации, задать оценочную функцию.
Предварительно простой ГА случайным образом генерирует начальную популяцию стрингов (хромосом). Затем алгоритм генерирует следующее поколение (популяцию), с помощью трех основных генетических операторов:
1) Оператор репродукции (ОР);
2) Оператор скрещивания ( кроссинговера, ОК);
3) Оператор мутации (ОМ).
Рассмотрим кратко каждый из этих операторов рассмотрев процессы которым данные операторы соответствуют.
Репродукция
Репродукция – это процесс, в котором хромосомы копируются в промежуточную популяцию согласно их значениям целевой (фитнес-) функции . При этом хромосомы с лучшими значениями целевой функции имеют большую вероятность попадания одного или более потомков в следующее поколение.
Очевидно, оператор репродукции является искусственной версией натуральной селекции – выживания сильнейших по Дарвину. Этот оператор представляется в алгоритмической форме различными способами. Самый простой (и популярный) метод реализации ОР – построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный ее значению ЦФ.
Для селекции хромосом используем случайный поиск на основе колеса рулетки. При этом колесо рулетки вращается и после останова ее указатель определяет хромосому для селекции в промежуточную популяцию. Очевидно, что хромосома, которой соответствует больший сектор рулетки, имеет большую вероятность попасть в следующее поколение. В результате выполнения оператора репродукции формируется промежуточная популяция, хромосомы которой будут использованы для построения поколения с помощью операторов скрещивания.