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

• Автор: Буздалов, Максим Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 204 с. : ил.

СОДЕРЖАНИЕ
Введение
1. Олимпиады по программированию, эволюционные алгоритмы и поисковая инженерия программного обеспечения

1.1. Олимпиады по программированию

1.1.1. Термины и обозначения

1.1.2. Руководство по подготовке задач для Google Code Jam

1.1.3. Особенности архивов задач с проверяющей системой

1.1.4. Практика генерации тестов для олимпиадных задач по программированию

1.1.5. Вычислительная сложность задачи генерации тестов

1.2. Эволюционные алгоритмы

1.2.1. Термины и обозначения
1.2.2. (1 + 1)-эволюционный алгоритм
1.2.3. Генетические алгоритмы
1.2.4. «Классический» генетический алгоритм
1.2.5. Генетическое программирование
1.2.6. Эволюционные стратегии
1.3. Поисковая инженерия программного обеспечения
1.3.1. Обзор избранных работ по поисковому тестированию программного обеспечения
1.3.2. Альтернативные подходы
1.4. Задачи, решаемые в диссертационной работе
Выводы по главе
2. Метод генерации тестов для алгоритмов решения NP-трудных задач
на основе генетического алгоритма (на примере задачи о рюкзаке)
2.1. Задача о рюкзаке
2.2. Алгоритмы решения задачи о рюкзаке
2.2.1. Алгоритм SimpleBranch

2.2.2. Алгоритм ЕхрКыар
2.2.3. Алгоритм НаибКиар
2.3. Генерация случайных тестов для задачи о рюкзаке
2.4. Описание генетического алгоритма
2.5. Экспериментальное исследование
2.5.1. Постановка экспериментального исследования
2.5.2. Результаты экспериментального исследования
2.5.3. Анализ случайных тестов
2.5.4. Сравнение генерации случайных тестов и генетического алгоритма
2.5.5. Сравнение частичных и полных решений
2.5.6. Анализ сложных тестов
Выводы по главе
3. Метод генерации тестов для алгоритмов решения графовых задач на основе генетического алгоритма (на примере задачи о поиске максимального потока)
3.1. Задача о поиске максимального потока
3.2. Алгоритмы решения задачи о поиске максимального потока
3.2.1. Алгоритм Форда-Фалкерсона с масштабированием пропускной способности
3.2.2. Алгоритм Эдмондса-Карпа
3.2.3. Алгоритм Эдмондса-Карпа с масштабированием пропускной способности
3.2.4. Алгоритм Диница
3.2.5. Неоптимальная реализация алгоритма Диница
3.2.6. Улучшенный алгоритм поиска кратчайших дополняющих путей

3.3. Генераторы тестов для задачи о поиске максимального потока
3.3.1. Генерация случайных графов
3.3.2. Генерация ациклических графов
3.3.3. Генератор транзитных решеток
3.3.4. Генератор случайных слоев
3.3.5. Генератор Черкасского и Гольдберга
3.3.6. Генератор «Washington»
3.3.7. Тесты Заде
3.4. Описание разработанного генетического алгоритма
3.5. Экспериментальное исследование
3.5.1. Выбор критерия для анализа результатов, наиболее точно отражающего время работы
3.5.2. Лучшие тесты и генераторы для каждого алгоритма поиска максимального потока
3.5.3. Средняя эффективность генераторов тестов
3.5.4. Другие наблюдения
Выводы по главе
4. Алгоритм выбора из нескольких функций приспособленности функции, оптимальной по времени решения задачи оптимизации
4.1. Постановка задачи
4.2. Общий вид и верхняя оценка времени работы алгоритма выбора критериев оптимизации
4.3. Алгоритм с экспоненциальной стратегией перезапуска и его верхняя оценка времени работы
4.4. Пример входных данных, на которых верхняя оценка времени работы асимптотически достигается
4.5. Оптимальная экспоненциальная стратегия перезапуска
4.6. О необходимости перезапуска алгоритмов

тя в различных применениях эволюционных алгоритмов может требоваться как максимизация, так и минимизация функции приспособленности (которую в последнем случае логичнее было бы назвать «функцией штрафа»). В дальнейшем для простоты описаний предполагается, что функция приспособленности должна быть максимизирована.
Отметим, что во многих реальных задачах, для решения которых применяются эволюционные алгоритмы, может быть не одна функция приспособленности, а несколько, возможно, конфликтующих, и все они должны быть по возможности максимизированы. Для решения таких задач существуют многокритериальные эволюционные алгоритмы, самым цитируемым на настоящий момент многокритериальным эволюционным алгоритмом является генетический алгоритм КБСА-П [98]. Так как в настоящей работе многокритериальные эволюционные алгоритмы не используются, они не будут рассмотрены ниже.
1.2.2. (1 + 1)-эволюционный алгоритм
Наиболее простым эволюционным алгоритмом является (1 + 1)-эволюционный алгоритм [99]. В каждый момент в данном алгоритме поддерживается наилучшая (обладающая максимальным значением приспособленности) из известных особей, причем в начальный момент эта особь генерируется случайным образом. Оптимизация проводится итеративно. На каждой итерации генерируется измененная копия лучшей особи (в терминах эволюционных алгоритмов, эта операция называется мутацией, по аналогии с мутациями генома живых существ, а функция, сопоставляющая особи ее мутировавшую копию, называется оператором мутации) и вычисляется ее значение приспособленности. Если оно не меньше, чем значение приспособленности лучшей особи, то лучшая особь заменяется на текущую. Если текущая особь удовлетворяет постановке задачи оптимизации (будем говорить, что такая особь является хорошим решением задачи оптимизации), то алго-