유닛 테스팅 근사 알고리즘

Question

저는 유명한 파이썬 패키지를 기본으로 그래프와 네트워크를위한 오픈 소스 근사 알고리즘 라이브러리를 만들고 있습니다. 주요 목표는 그래프 및 네트워크에 대한 NP-Complete 문제에 대한 최신 근사 알고리즘을 포괄하는 것입니다. 그 이유는 1) 이것을 다루는 멋진 (현대적인) 통합 패키지를 보지 못했고 2) NP-Hard 최적화 문제에 대한 근사 알고리즘에 대해 배울 수있는 좋은 교수법 도구가 될 것입니다.

이 라이브러리를 구축 할 때 적절한 테스트를 수행하기 위해 단위 테스트를 사용하고 있습니다. 근사 알고리즘이 올바른 해결책을 반환하지 않을 수도 있다는 점에서 본인의 단위 테스트에 대해서는 다소 신중합니다. 현재 손으로 작은 인스턴스를 해결하고 리턴 된 결과가 그와 일치하는지 확인하고 있지만, 이는 구현의 관점에서 바람직하지 않으며 확장 할 수도 없습니다.

단위 테스트 근사 알고리즘의 가장 좋은 방법은 무엇입니까? 무작위 인스턴스를 생성하고 반환 된 결과가 알고리즘에 의해 보증 된 범위보다 작은 지 확인하십시오. 그건 거짓 긍정을 가진 것처럼 보일 것입니다. (이 테스트는 그 시간에 운이 좋았지 만, 모든 인스턴스가 묶여 있다는 보장은 없습니다).

Answer 1

여기서 두 가지 문제를 구분해야합니다. 근사 알고리즘의 품질과 알고리즘 구현의 정확성.

근사 알고리즘의 품질을 테스트하는 것은 일반적으로 소프트웨어 개발에 사용되는 단위 테스트 방법에 적합하지 않습니다. 예를 들어, 실제 크기의 문제를 나타내는 무작위 문제를 생성해야합니다. 해결할 수없는 큰 인스턴스에 대한 알고리즘의 품질을 판단하기 위해 상한/하한 경계를 얻기 위해 수학적 작업을해야 할 수도 있습니다. 또는 알려진 솔루션이나 가장 잘 알려진 솔루션이있는 문제 테스트 세트를 사용하여 결과를 비교하십시오. 그러나 단위 테스트는 근사 알고리즘의 품질을 개선하는 데 많은 도움이되지 않습니다. 최적화 및 수학 분야의 지식을 활용할 수있는 곳입니다.

구현의 정확성은 단위 테스트가 정말 유용 할 것입니다. 여기에서 장난감 크기의 문제를 사용하고 코드가 생성하는 것과 알려진 결과 (손으로 해결하거나 코드에서 단계별 디버깅을 통해 확인)를 비교할 수 있습니다. 작은 문제가있는 것만으로는 충분하지 않을뿐만 아니라 테스트가 빠르게 실행되고 개발주기 동안 여러 번 실행될 수 있도록 여기에 바람직합니다. 이러한 유형의 테스트는 전체 알고리즘이 정확한 결과에 도달하는지 확인합니다.코드의 상당 부분을 블랙 박스로 테스트하기 때문에 단위 테스트와 통합 테스트 사이에 있습니다. 그러나 이러한 유형의 테스트가 최적화 도메인에서 매우 유용하다는 것을 알게되었습니다. 이 유형의 테스트를 수행하기를 권장하는 한 가지는 난수 생성기의 고정 된 시드를 통해 알고리즘의 모든 임의성을 제거하는 것입니다. 이러한 테스트는 항상 결정 론적 방식으로 실행되어야하며 정확히 동일한 결과를 100 % 제공해야합니다. 알고리즘의 하위 모듈에서 단위 테스트를하는 것도 좋습니다. 그래프의 호에 가중치를 할당하고 올바른 가중치가 할당되어 있는지 확인하는 방법을 분리합니다. 목적 함수 값 계산 함수와 단위 테스트를 분리하십시오. 너는 내 요점을 얻는다.

두 슬라이스 모두를 줄이는 또 다른 문제는 성능입니다. 작은 장난감 문제로도 성능을 안정적으로 테스트 할 수는 없습니다. 또한 작동중인 알고리즘의 성능을 크게 저하시키는 변경을 실현하는 것이 매우 바람직합니다. 실행중인 알고리즘 버전을 사용하면 성능을 측정하고 성능/통합 테스트가되도록 자동으로 테스트하는 곳에서 더 큰 테스트 문제를 만들 수 있습니다. 더 적은 시간이 걸릴 수는 있지만 적어도 리팩터링 중에 새로 도입 된 성능 병목 현상이나 알고리즘에 대한 새로운 기능 추가에 대해 알려줄 것입니다.

Answer 2

생성 된 솔루션의 유효성을 확인하는 것이 첫 번째 단계입니다. 또한, 예상 된 근사해가 알려진 경우 (예를 들어, 손으로 또는 다른 알고리즘의 동일한 알고리즘의 구현을 사용하여 획득 됨) 인스턴스를 사용하여 하나의 공격 각도가 regression testing 일 수있다.

또한 TSP와 유사한 문제에 대해 TSPLIB과 같이 알려진 (최적의) 해를 가진 문제 인스턴스의 리포지토리가 있습니다. 아마도 이것들은 어떤 용도로 쓰일 수 있습니다.

문제의 알고리즘에 대해 알려진 상한이있는 경우 많은 무작위 인스턴스를 생성하고 상한에 대해 경험적 솔루션을 검증하는 것이 효과적 일 수 있습니다. 이 작업을 수행하면 실행 가능성을 재현성있게 만드는 것이 좋습니다 (예 : 항상 동일한 난수 생성기 및 시드 사용).

하나의 마지막 참고 사항 : 일부 문제의 경우 완전히 무작위로 추출한 인스턴스는 평균적으로 좋은 해결책을 찾기 쉽습니다. 균일하고 독립적으로 선택된 원호 무게를 갖는 비대칭 TSP가 그러한 예 중 하나이다. 나는 당신의 테스트 전략에 영향을 줄 수 있기 때문에 이것을 언급하고있다.

Answer 3

일반적으로 확인할 수있는 것이 있습니다 최적이 아닌 경우에도 제약 조건을 만족하는 솔루션을 항상 반환합니다. 또한 가능한 모든 기회에 단언 문을 써야합니다. 이것은 프로그램에 따라 다르지만 일부 수량이 보존되어 있는지 또는 동일한 상태로 유지되어야하는지 또는 최악의 상태로 유지되어야하는지가 감소하지 않는지 또는 일부 지역 최적은 실제로 국부 최적이다.

이러한 종류의 검사와 이미 언급 한 범위에 대한 검사가 주어지면 문제가 발생하지 않는 임의의 시드를 선택하여 매우 많은 수의 임의로 생성 된 작은 문제에 대한 테스트를 실행하는 것을 선호합니다 102324 이전의 102323 문제점을 실행하지 않고 디버깅을 위해 그 실패를 반복 할 수 있습니다. 많은 수의 문제가 있으면 기본 버그로 인해 수표에 실패 할 정도로 오류가 발생할 확률이 높아집니다. 작은 문제가 있으면 버그를 찾아 수정할 수있는 기회가 증가합니다.