Скобцов Ю. А.
Рассматриваются теоретические и прикладные вопросы применения в программной инженерии эволюционных вычислений – нового направления в теории искусственного интеллекта, которое в последнее время активно используется в инженерной практике. Приводится описание генетического алгоритма и его основных модификаций для численной и комбинаторной оптимизации. Изложены основы многокритериальной эволюционной оптимизации. Рассмотрено применение этих методов в программной инженерии: эволюционные алгоритмы оценки стоимости проектов, планирования программных проектов, кластеризации и тестирования программных систем. Для студентов вузов, обучающихся по специальностям «Программная инженерия», «Прикладная математика и информатика» и другим смежным специальностям. Может быть полезно преподавателям и аспирантам.
ПРЕДИСЛОВИЕ 5
ВВЕДЕНИЕ 6
1. ОСНОВЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 8
1.1. Источники 8
1.2. Простой генетический алгоритм 9
1.2.1. Генетические операторы 9
1.2.2. Кодирование вещественных решений 12
1.3. Параметры генетических алгоритмов 16
1.4. Модификации и обобщения ГА 17
1.4.1. Кодирование особей – потенциальных решений 17
1.4.2. Отбор родителей (селекция) 19
1.4.3. Операторы рекомбинации (скрещивания, кроссинговера) 23
1.4.4. Оператор мутации 29
1.5. Генетические алгоритмы многокритериальной оптимизации 35
1.5.1. Концепция доминирования Парето 36
1.5.2. Метод взвешенной функции 38
1.5.3. Недоминируемая сортировка 2 41
1.5.4. Эволюционный алгоритм на основе «силы» Парето 42
Выводы 44
Вопросы для самопроверки 44
2. ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ОЦЕНКИ СТОИМОСТИ ПРОЕКТОВ В ПРОГРАММНОЙ ИНЖЕНЕРИИ 45
2.1. Модель COCOMO 45
2.2. Эволюционные алгоритмы 46
2.3. Генетический алгоритм для оценки стоимости программных проектов 47
2.4. Фитнесс-функция 48
2.5. Результаты при использовании другой фитнесс-функции 50
2.6. Уточнение модели 52
2.7. Расширенное множество программных проектов НАСА 56
2.8. Различные типы ошибок 58
2.9. Применение генетического программирования для оценки стоимости проекта 60
2.10. Роевые алгоритмы 64
Выводы 69
Вопросы для самопроверки 69
3. ЭВОЛЮЦИОННЫЕ МЕТОДЫ ПЛАНИРОВАНИЯ ПРОГРАММНЫХ ПРОЕКТОВ 71
3.1. Планирование программных проектов 72
3.2. Генетический алгоритм планирования проекта 79
3.3. Эксперименты и результаты планирования 82
3.4. Многокритериальные эволюционные алгоритмы планирования 86
3.4.1. Современные многокритериальные эволюционные алгоритмы 87
3.4.2. Экспериментальные исследования 88
3.4.3. Сравнение многокритериальных эволюционных алгоритмов 90
3.5. Анализ решений 94
Выводы 97
Вопросы для самопроверки 97
4. АВТОМАТИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ПРОГРАММНЫХ СИСТЕМ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 98
4.1. Разбиение графов зависимостей модулей 98
4.2. Генетический алгоритм разбиения графов зависимостей модулей 100
4.3. ГА кластеризации программного обеспечения 101
4.4. Компьютерные эксперименты по кластеризации 104
4.5. Работы по кластеризации программ 106
Выводы 107
Вопросы для самопроверки 107
5. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ТЕСТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 108
5.1. Основные виды тестирования программ 108
5.2. Эволюционные методы тестирования по методу «белого ящика» 109
5.2.1. Генетический алгоритм тестирования на основе потока данных 109
5.2.2. Тестирование путей 117
5.2.3. Муравьиный алгоритм в тестировании путей 123
5.2.4. Тестирование на основе дуального графа 123
5.2.5. Автоматический метод на основе эволюционных вычислений 125
5.3. Эволюционные методы тестирования по методу «черного ящика» 125
5.3.1. Нейронные сети в качестве искусственных спецификаций 126
5.3.2. Тестирование на основе мутации и нечетких контроллеров 132
Выводы 138
Вопросы для самопроверки 138
ЗАКЛЮЧЕНИЕ 139
СПИСОК ЛИТЕРАТУРЫ 140
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ 143