Thuật toán xấp xỉ thử nghiệm đơn vị

Question

Tôi đang làm việc trên thư viện thuật toán xấp xỉ nguồn mở cho biểu đồ và mạng bằng cách sử dụng một số gói python phổ biến làm cơ sở. Mục tiêu chính là bao gồm các thuật toán xấp xỉ cập nhật cho các vấn đề NP-Complete trên biểu đồ và mạng. Lý do cho điều này là 1) Tôi chưa thấy một gói hợp nhất (hiện đại) bao gồm điều này và 2) nó sẽ là một công cụ sư phạm tốt đẹp để tìm hiểu về các thuật toán xấp xỉ trên các vấn đề tối ưu hóa NP-Hard.

Khi xây dựng thư viện này, tôi đang sử dụng các bài kiểm tra đơn vị để kiểm tra sanity (như bất kỳ nhà phát triển thích hợp nào). Tôi hơi thận trọng về bài kiểm tra đơn vị của tôi trong đó bởi bản chất của họ, các thuật toán gần đúng có thể không trả về giải pháp đúng. Hiện tại tôi đang giải quyết một số trường hợp nhỏ bằng tay và sau đó đảm bảo rằng kết quả trả về khớp với kết quả đó, nhưng điều này không phải là mong muốn và cũng không thể mở rộng theo nghĩa thực hiện.

Điều gì sẽ là cách tốt nhất để các thuật toán xấp xỉ kiểm tra đơn vị? Tạo các trường hợp ngẫu nhiên và đảm bảo rằng các kết quả trả về nhỏ hơn giới hạn được đảm bảo bởi thuật toán? Điều đó dường như có dương tính giả (thử nghiệm chỉ có may mắn thời gian đó, không được bảo đảm cho tất cả các trường hợp được dưới ràng buộc).

Answer 1

Bạn cần tách hai mối quan tâm ở đây. Chất lượng của các thuật toán gần đúng của bạn và tính chính xác của việc thực hiện các thuật toán đó.

Kiểm tra chất lượng của thuật toán xấp xỉ thường sẽ không cho vay chính nó vào các phương pháp thử nghiệm đơn vị được sử dụng trong phát triển phần mềm. Ví dụ bạn sẽ cần phải tạo ra các vấn đề ngẫu nhiên đại diện cho các kích thước thực sự của các vấn đề. Bạn có thể cần phải làm công việc toán học để có được một số ràng buộc trên/dưới để đánh giá chất lượng của các thuật toán của bạn cho các trường hợp lớn không thể giải quyết được. Hoặc sử dụng các bộ kiểm tra sự cố có các giải pháp đã biết hoặc được biết đến nhiều nhất và so sánh kết quả của bạn. Nhưng trong mọi trường hợp thử nghiệm đơn vị sẽ không giúp bạn nhiều trong việc cải thiện chất lượng của các thuật toán xấp xỉ. Đây là nơi mà kiến ​​thức về lĩnh vực tối ưu hóa và toán học của bạn sẽ giúp ích.

Tính chính xác của việc triển khai của bạn là nơi thử nghiệm đơn vị sẽ thực sự hữu ích. Bạn có thể sử dụng các vấn đề có kích thước đồ chơi ở đây và so sánh các kết quả đã biết (giải quyết bằng tay hoặc xác minh qua từng bước cẩn thận bằng cách gỡ lỗi mã) với mã của bạn tạo ra. Có vấn đề nhỏ không chỉ đủ nhưng cũng mong muốn ở đây để các bài kiểm tra chạy nhanh và có thể chạy nhiều lần trong chu kỳ phát triển. Các loại kiểm tra này đảm bảo rằng thuật toán tổng thể đến đúng kết quả.Nó là một nơi nào đó giữa một bài kiểm tra đơn vị và một bài kiểm tra tích hợp kể từ khi bạn đang thử nghiệm một phần lớn của mã như một hộp đen. Nhưng tôi đã tìm thấy các loại thử nghiệm này cực kỳ hữu ích trong miền tối ưu hóa. Một điều tôi khuyên bạn nên làm cho loại thử nghiệm này là loại bỏ tất cả sự ngẫu nhiên trong thuật toán của bạn thông qua các hạt cố định cho các trình tạo số ngẫu nhiên. Các xét nghiệm này phải luôn chạy theo cách xác định và cho kết quả chính xác 100% thời gian. Tôi cũng khuyên bạn nên kiểm tra đơn vị ở các mô-đun cấp thấp hơn trong thuật toán của bạn. Cô lập phương thức gán trọng số cho vòng cung trên biểu đồ và kiểm tra xem trọng số chính xác có được gán hay không. Cô lập chức năng tính toán giá trị hàm mục tiêu của bạn và kiểm tra đơn vị đó. Bạn nhận được quan điểm của tôi.

Một mối quan ngại khác là cắt giảm cả hai lát này là hiệu suất. Bạn không thể kiểm tra hiệu suất một cách đáng tin cậy với các vấn đề đồ chơi nhỏ. Cũng thực hiện một thay đổi làm giảm hiệu suất đáng kể cho một thuật toán làm việc một cách nhanh chóng là rất mong muốn. Một khi bạn có một phiên bản chạy của các thuật toán của bạn, bạn có thể tạo ra các vấn đề kiểm tra lớn hơn, nơi bạn đo lường hiệu suất và tự động hóa nó để được kiểm tra hiệu năng/tích hợp của bạn. Bạn có thể chạy ít thường xuyên hơn vì họ sẽ mất nhiều thời gian hơn nhưng ít nhất sẽ thông báo cho bạn sớm về các tắc nghẽn hiệu suất mới được giới thiệu trong khi tái cấu trúc hoặc bổ sung tính năng mới cho các thuật toán

Answer 2

Kiểm tra tính hợp lệ của các giải pháp được tạo ra là bước đầu tiên rõ ràng.

Ngoài ra, một góc tấn công có thể là regression testing sử dụng các trường hợp mà giải pháp gần đúng được mong đợi (ví dụ: thu được bằng cách thực hiện thuật toán bằng tay hoặc bằng cách sử dụng thuật toán tương tự của người khác).

Cũng tồn tại các kho lưu trữ của các phiên bản sự cố với các giải pháp (tối ưu) đã biết, chẳng hạn như TSPLIB đối với các sự cố giống như TSP. Có lẽ chúng có thể được sử dụng.

Nếu có giới hạn trên cho thuật toán được đề cập, sau đó tạo nhiều trường hợp ngẫu nhiên và xác minh các giải pháp phỏng đoán chống lại giới hạn trên có thể chứng minh hiệu quả. Nếu bạn làm điều này, tôi khuyên bạn nên thực hiện các lần chạy lặp lại (ví dụ: bằng cách sử dụng cùng một trình tạo số ngẫu nhiên và hạt giống).

Một lưu ý cuối cùng: đối với một số vấn đề, các trường hợp hoàn toàn ngẫu nhiên ở mức trung bình khá dễ tìm các giải pháp gần đúng tốt. TSP bất đối xứng với trọng lượng vòng cung thống nhất và độc lập được chọn là một ví dụ như vậy. Tôi đang đề cập đến điều này vì nó có thể ảnh hưởng đến chiến lược thử nghiệm của bạn.

Answer 3

Thường có điều bạn có thể kiểm tra - ví dụ, thuật toán của bạn luôn trả về các giải pháp thỏa mãn các ràng buộc của chúng, ngay cả khi chúng không tối ưu. Bạn cũng nên đặt trong kiểm tra xác nhận ở mọi cơ hội có thể - những điều này sẽ cụ thể cho chương trình của bạn, nhưng có thể kiểm tra xem một số lượng có được bảo tồn không, hoặc điều gì đó sẽ tăng hoặc ở mức tồi tệ nhất vẫn không giảm hoặc tối ưu thực sự là một địa phương tối ưu.

Với các loại kiểm tra và kiểm tra giới hạn mà bạn đã đề cập, tôi ưu tiên chạy thử nghiệm trên một số lượng lớn các vấn đề nhỏ được tạo ngẫu nhiên, với các hạt ngẫu nhiên được chọn theo cách sao cho nó không thành vấn đề 102324 bạn có thể lặp lại lỗi đó để gỡ lỗi mà không cần phải chạy qua 102323 vấn đề trước đó. Với một số lượng lớn các vấn đề, bạn tăng khả năng một lỗi tiềm ẩn sẽ gây ra lỗi đủ rõ ràng để không kiểm tra được. Với các vấn đề nhỏ, bạn tăng cơ hội mà bạn sẽ có thể tìm và sửa lỗi.