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

Презентация:



Advertisements
Похожие презентации
Разработка программного средства 3Genetic для генерации автоматов управления системами со сложным поведением Государственный контракт «Технология.
Advertisements

Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Царев Ф. Н. Научный руководитель.
Применение генетического программирования для реализации систем со сложным поведением Санкт-Петербургский Государственный Университет Информационных Технологий,
Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Федор Николаевич Царев, СПбГУ.
Применение генетического программирования в задаче поиска усердных бобров Д. О. Соколов, П.В. Федотов, Ф. Н. Царев Научный руководитель – А. А. Шалыто.
Основные этапы моделирования. Моделирование – исследование объектов путем построения и изучения их моделей. Моделирование – творческий процесс, и поэтому.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Моделирование – исследование объектов путем построения и изучения их моделей. Моделирование – творческий процесс, и поэтому заключить его в формальные.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ НАСТРОЙКИ ИСКУССТВЕННОЙ НЕЙРОННОЙ СЕТИ Конференция «Технологии Microsoft в информатике и программировании», февраля 2004г.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Основные направления подготовки учащихся к олимпиаде по информатике. Решение олимпиадных задач Калашникова Е.В., МБОУ «Чернянская средняя общеобразовательная.
ПА 2012 РАЗРАБОТКА ТЕСТА СРЕДСТВАМИ MOODLE Салихов Сергей Валерьевич, ПЗ, 4 часа.
Математическое обеспечение. Содержание Назначение, состав и структура МО. Формализация и моделирование. Модели и алгоритмы обработки информации. Характеристика.
Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач Дворкин М. Э. Научный руководитель: Корнеев Г. А., к. т. н., доцент КТ.
1 Применение методов искусственного интеллекта в разработке управляющих программных систем. Первый этап Разработка, программная реализация и экспериментальное.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Алгоритм - точная конечная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью.
Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель.
Транксрипт:

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

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

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

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

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

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

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

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

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

Задача: N = 10, 0

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