Алгоритмы аппроксимации модульного тестирования

Question

Я работаю над библиотекой алгоритмов аппроксимации с открытым исходным кодом для графов и сетей, используя в качестве основы некоторые популярные пакеты python.Основная цель состоит в том, чтобы охватить современные алгоритмы аппроксимации для задач NP-Complete по графам и сетям.Причина этого в том, что: 1) я не видел хорошего (современного) консолидированного пакета, который покрывает это, и 2) он был бы хорошим педагогическим инструментом для изучения алгоритмов аппроксимации в задачах оптимизации NP-Hard.

При создании этой библиотеки я использую юнит-тесты для проверки работоспособности (как это сделал бы любой правильный разработчик).Я несколько осторожен с моими модульными тестами, поскольку по самой своей природе алгоритмы аппроксимации могут не дать правильного решения.В настоящее время я решаю некоторые небольшие случаи вручную, а затем проверяю, соответствует ли возвращаемый результат этому, но это нежелательно и не масштабируется в смысле реализации.

Каков наилучший способ аппроксимации модульных тестов алгоритмами?Сгенерировать случайные экземпляры и убедиться, что возвращаемые результаты меньше границы, гарантированной алгоритмом?Это может показаться ложным срабатыванием (в тот раз тесту просто повезло, не гарантируется, что все экземпляры будут ниже допустимых).

Answer 1

Вы должны разделить две проблемы здесь.Качество ваших приближенных алгоритмов и правильность реализации этих алгоритмов.

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

Правильность вашей реализации - это то, где модульные тесты будут действительно полезны.Здесь вы можете использовать задачи размером с игрушку и сравнить известные результаты (решение вручную или тщательная пошаговая отладка кода) с тем, что генерирует ваш код.Наличие небольших проблем не только достаточно, но и желательно, чтобы тесты выполнялись быстро и могли запускаться много раз в течение цикла разработки.Эти типы тестов удостоверяются, что общий алгоритм достигает правильного результата.Это что-то среднее между модульным тестом и интеграционными тестами, поскольку вы тестируете большую часть кода в виде черного ящика.Но я обнаружил, что эти типы тестов чрезвычайно полезны в области оптимизации.Одна вещь, которую я рекомендую сделать для этого типа тестирования, - удалить все случайности в ваших алгоритмах через фиксированные начальные числа для генераторов случайных чисел.Эти тесты должны всегда выполняться детерминистическим образом и давать точно такой же результат 100% времени.Я также рекомендую юнит-тестирование на модулях более низкого уровня ваших алгоритмов.Изолируйте этот метод, который присваивает веса дугам на графике, и проверьте, назначены ли правильные веса.Изолируйте вашу функцию вычисления значения целевой функции и проверьте ее.Вы поняли мою точку зрения.

Еще одна проблема, которая обрезает оба этих среза, - это производительность.Вы не можете надежно протестировать производительность с небольшими игрушечными проблемами.Также очень желательно реализовать изменение, которое значительно снижает производительность рабочего алгоритма.Когда у вас есть работающая версия ваших алгоритмов, вы можете создавать более сложные тестовые задачи, где вы измеряете производительность и автоматизируете ее для тестирования производительности / интеграции.Вы можете запускать их реже, так как они будут занимать больше времени, но, по крайней мере, заблаговременно уведомят вас о недавно появившихся узких местах производительности во время рефакторинга или о новых возможностях, добавленных в алгоритмы

Answer 2

Проверка достоверности полученных решений является очевидным первым шагом.

Кроме того, одним из углов атаки может быть регрессионное тестирование с использованием случаев, для которых известно ожидаемое приблизительное решение (например, полученное путем выполнения алгоритма вручную или с использованием чьей-либо реализации того же алгоритма).

Существуют также хранилища экземпляров проблем с известными (оптимальными) решениями, такими как TSPLIB для задач, подобных TSP. Возможно, их можно было бы использовать.

Если существуют известные верхние границы для рассматриваемого алгоритма, то генерация множества случайных случаев и проверка эвристических решений по верхним границам может оказаться плодотворной. Если вы сделаете это, я призываю вас сделать воспроизводимые прогоны (например, всегда используя один и тот же генератор случайных чисел и начальное число).

И последнее замечание: для некоторых задач в среднем довольно легко найти хорошие приближенные решения. Асимметричный TSP с равномерно и независимо выбранными весами дуги является одним из таких примеров. Я упоминаю об этом, поскольку это может повлиять на вашу стратегию тестирования.

Answer 3

Обычно есть что-то, что вы можете проверить - например, что ваш алгоритм всегда возвращает решения, которые удовлетворяют их ограничениям, даже если они не оптимальны. Вы должны также проверять утверждения при каждой возможной возможности - они будут характерны для вашей программы, но могут проверять, сохраняется ли некоторое количество, или что то, что должно увеличиваться или в худшем случае оставаться прежним, не уменьшается, или что некоторые предполагаемые локальные оптимум действительно является локальным оптимумом.

Учитывая такие виды проверок и проверки границ, о которых вы уже упоминали, я предпочитаю запускать тесты для очень большого числа случайно сгенерированных небольших задач, причем случайные начальные числа выбираются таким образом, что в случае сбоя в задаче 102324 Вы можете повторить этот сбой для отладки, не выполняя проблемы 102323 перед этим. При большом количестве проблем вы повышаете вероятность того, что основная ошибка вызовет ошибку, достаточно очевидную для того, чтобы провалить проверку. С небольшими проблемами вы увеличиваете вероятность того, что сможете найти и исправить ошибку.