'

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

Понравилась презентация – покажи это...





Слайд 0

Применение генетических алгоритмов для генерации тестов к олимпиадным задачам по программированию Буздалов М.В., СПбГУ ИТМО


Слайд 1

Тестирование Занимает до 50% времени и стоимости разработки ПО Подлежащие тестированию процессы разнообразны Автоматизация тестирования позволяет снизить затраты на разработку ПО и увеличить его качество


Слайд 2

Олимпиадные задачи Решения тестируются на определенном наборе тестов Жесткие ограничения на время работы решения Простой текстовый формат входных и выходных данных Автоматическая проверка корректности ответа Процесс тестирования полностью автоматизирован Качество проверки зависит от качества набора тестов


Слайд 3

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


Слайд 4

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


Слайд 5

Даны N предметов, каждый с весом WI и стоимостью PI. Требуется указать, какие из этих предметов нужно выбрать, чтобы их суммарный вес не превзошел W, а суммарная стоимость была бы максимальной Задача является NP-полной Разработано множество алгоритмов, решающих эту задачу для больших N (порядка 100 тысяч) за малое время (порядка 1 секунды) для большей части (но не для всех) входных данных Пример применения: задача о рюкзаке Задача: найти трудный тест для конкретного решения.


Слайд 6

Особь генетического алгоритма: древовидный генератор Описание генетического алгоритма W = 10, P = 4 W = 7, P = 6 W = 5, P = 2 W += 3, P += 2 W *= 2, P += 1


Слайд 7

Кроссовер – обмен случайными поддеревьями Мутация – изменение параметров в случайно выбранной вершине Схема алгоритма – скрещивание с наилучшей особью, затем выбор фиксированного числа наиболее приспособленных особей Размер поколения – 100 особей Описание генетического алгоритма


Слайд 8

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


Слайд 9

Задача: N = 10, 0 <= W,P <= 2128 Ограничение по времени: 4 секунды За 30 минут генетическим алгоритмом найден тест, на котором решение работает больше 4 секунд Генерация тестов случайным образом в соответствии с шаблоном, известным как самый сложный случай для данного алгоритма, в течение 2 часов не привела к подобному результату (максимальное достигнутое время работы – 2 секунды)? Результаты работы


Слайд 10

Выбор наиболее эффективных схем генетических алгоритмов Создание тестов, трудных одновременно для нескольких решений Применение к другим классам задач Дальнейшие направления исследований


×

HTML:





Ссылка: