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

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

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

Что было бы лучшим способом для алгоритмов приближения unit test? Генерировать случайные экземпляры и обеспечивать, чтобы возвращаемые результаты были меньше, чем оценка, гарантированная алгоритмом? У этого, казалось бы, были бы ложные срабатывания (тест просто повезло, что время, не гарантированное, чтобы все экземпляры были ниже границы).

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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