Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

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

---

А.Е. Кононюк Дискретно-непрерывная математика 
331 
ченного объема настоящей работы мы не будем рассматривать до-
полнительные примеры, демонстрирующие различные возможности 
его реализации с использованием программы 
GTO
.
Наиболее важные замечания относительно гибридного подхода, 
состоящего в объединении генетического алгоритма с градиентным 
методом обучения нейронных сетей (программа 
BrainMaker
) 
представлены в п. 3.21.1. Программа 
GTO 
представляет собой пример 
равноправного объединения обоих методов, при котором в соот-
ветствии с типовым циклом эволюции приспособленность особей 
популяции рассчитывается генетическим алгоритмом по результатам 
обучения нейронных сетей. Существование такой программы, как 
GTO
, подтверждает практическое применение гибридного подхода, 
объединяющего достоинства двух оптимизационных методов: 
генетического алгоритма, который легко находит точку, близкую к 
оптимальному решению, и градиентного алгоритма, который стартует 
из найденной точки и быстро приводит к настоящему оптимуму. 
6. 
Применение генетических алгоритмов
 
6.1
. Применение ГА для автоматической 
генерации тестов 
При разработке и сопровождении программного обеспечения, 
значительная часть усилий тратится на поиск и устранение ошибок. 
Самым распространённым методом поиска ошибок является 
тестирование, то есть процесс выполнения программ с целью 
обнаружения ошибок. Здесь слово «программа» понимается в 
широком смысле, как любая запись алгоритма. В частности, 
программами являются отдельные процедуры, функции, классы и т.д. 
Процесс тестирования включает выполнение некоторого набора тестов 
и анализ полученных результатов. Тест - это последовательность 
обращений к тестируемой программе. Результатом выполнения теста 
является решение (вердикт) о том, отработала ли программа корректно 
или некорректно. Основной характеристикой тестового набора, 
определяющей качество тестирования, является класс возможных 
ошибок в программе, которые данный тестовый набор способен 

---

А.Е. Кононюк Дискретно-непрерывная математика 
332 
обнаружить. Для количественной оценки качества тестирования 
используются различные метрики тестового покрытия. Для 
качественного тестирования необходимо построить полный тестовый 
набор, т. е. набор, удовлетворяющий некоторому критерию полноты. 
Зачастую критерий полноты для тестового набора определяют через 
пороговое значение метрики тестового покрытия. Построение полного 
тестового набора для больших систем вручную может быть крайне 
трудоёмкой задачей. Автоматизация этого процесса позволяет 
существенно снизить затраты на тестирование. Существуют различные 
подходы к решению задачи автоматической генерации тестов. Один из 
них основан на применении генетических алгоритмов. Этот подход во 
многих случаях даёт хорошие результаты. К сожалению, его 
эффективность существенно зависит от используемого критерия 
полноты. Цель данного роздела - проанализировать некоторые широко 
распространённые критерии полноты тестового набора на их 
применимость при использовании генетических алгоритмов для 
генерации тестов.
Основные понятия 
Генетические алгоритмы 
Как мы знаем, генетические алгоритмы - это метод решения задач 
оптимизации. В методе используются идеи, почерпнутые из 
эволюционной 
биологии: 
наследование 
признаков, 
мутация, 
естественный отбор и кроссовер. Определяется множество кандидатов, 
среди которых ищется решение задачи. Кандидаты представляются в 
виде списков, деревьев или иных структур данных. Общая схема 
работы генетического алгоритма подробно была описана в начальных