Тема магистерской работы: "Изучения и разработка эволюционных алгоритмов и построение тестов для логических схем. "

Руководитель: профессор Скобцов Юрий Александрович

Автореферат магистерской диссертации

Введение

История эволюционных вычислений началась с разработки ряда разных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голанда (Holland), разработанные в начале 60-х лет. Главная трудность при построении вычислительных систем, основанных на принципах естественного отбора и применении этих систем в прикладных задачах, состоит в том, что естественные системы довольно хаотичные, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, что мы сами и формулируем, и акцентируем внимание на максимально быстром выполнении при минимальных затратах.

Эти системы, смоделированные на биологических принципах. Т.е. эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies).

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

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

Отметим следующие особенности алгоритма эволюции:

1) Каждая новая популяция состоит из жизнеспособных особей (хромосом).

2) Каждая новая популяция лучше (в смысле целевой функции) предыдущей.

3) В процессе эволюции последующая популяция зависит только от предыдущей.

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

2. Построение тестов для микропроцессорных систем

  Современная технология проектирования и производства компьютерных систем позволяет реализовать в одном кристалле миллионы транзисторов. В настоящее время на одном кристалле реализуются достаточно сложные микропроцессорные системы. Их тестирование представляет очень серьезную проблему.

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

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

Далее они используются на втором верхнем уровне ГА для генерации полной тестовой программы. На этом уровне используется эволюционный алгоритм. Здесь популяция из N последовательностей генерируется из предыдущего поколения путем мутации. При этом применяется (N + N) стратегия – N родителей генерируют N потомков.

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

3. Ориентированный ациклический граф и его примеры.

Ациклическим графом  называется (ориентированный)  граф,  не имеющий  циклов. На  рисунке  показан пример ациклического графа. 

Ориентированный Ациклический Граф

Пример блок-схемы программы

Здесь каждая особь – программа представляется в виде графа. Вершина графа представляет линейный участок программы. Она имеет 2 части – собственно линейную программу и узел ветвления.

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

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

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы.

Основные принципы ГА были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, ГА только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.

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

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

В процессе эволюции используются генетические операторы.

ОПЕРАТОР КРОССИНГОВЕРА

ОК комбинирует генетический материал из 2-х родительских программ путем обмена некоторых частей программ, реализуется двумя

способами.

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

Как правило, в процессе эволюции используются ОК обоих типов. В целом ОК выполняется следующим образом:

1. Выбор точки скрещивания в обоих родителях.

2. Выбор с заданной вероятностью типа ОК (для 1-го типа с вероятностью , для 2-го с вероятностью 1- ).

Если выбран 1-й тип то переход на п.3, иначе на п.4.

3. Если размер потомка не превышает порога, то выполнить ОК 1-го типа, переход на п.5..

4. Если размер потомка не превышает порога, то выполнить ОК 2-го типа.

5.Конец.

ОПЕРАТОР МУТАЦИИ

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

5. Фитнесс функция для МП-систем

F = Na + Nf* Nm + (Nf )2 *Nd , где

Nf – число всех неисправностей,

Na – число активированных неисправностей,

Nm – число неисправностей, изменяющих содержимое памяти,

Nd – число проверенных неисправностей.

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

Заключение

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

Литература

1. К.К. Конева, Л.М.Терехова " Появление эволюционных алгоритмов " 2003 г. М: Мир - с. 243.
2. А.Ю.Дорогов, А.А. Алексеев "СТРУКТУРНЫЕ МОДЕЛИ И ТОПОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ БЫСТРЫХ НЕЙРОННЫХ СЕТЕЙ. методическое пособие Киев 2002 г. 108 с.
3. W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone. Genetic Programming An Introduction On the Automatic Evolution of Computer Programs and its Applications. Morgan Kaufmann, San Francisco und dpunkt verlag, Heidelberg , 1998.
4. W. B. Langdon and R. Poli. Genetic programming bloat with dynamic tness. In Wolfgang Banzhaf, Riccardo Poli, Marc Schoenauer, and Terence C. Fogarty, editors, Proceedings of the First European Workshop on Genetic Programming, volume 1391 of LNCS, pages 96 112, Paris , 14-15 April 1998. Springer-Verlag.