Bagaimana cara saya menguji algoritma heuristik?

10

Katakanlah kita memiliki algoritma pencarian rute kami:

def myHeuristicTSP(graph):
    /*implementation*/
    return route

Sekarang kami ingin menguji unit ini:

class TestMyHeuristicTSP:
    def testNullGraphRaiseValueError(self):
        self.assertRaises(ValueError, myHueristicTSP(None))

    def testSimpleTwoNodeGraphReturnsRoute:
        self.assertEquals(expectedResult, myHeuristicTSP(input))

Pertanyaannya adalah, untuk algoritma TSP non-heuristik, kita dapat memberikan berbagai grafik dan memeriksa apakah mereka selalu mengembalikan rute terpendek secara absolut.

Tetapi karena algoritma heurtistik, sementara masih deterministik, kurang dapat diprediksi, apakah hanya dimaksudkan untuk memahami bagaimana algoritma itu dimaksudkan untuk bekerja, dan menemukan kasus tepi itu?

unit-testing heuristics djohnston
sumber
1
Terkait: programmers.stackexchange.com/questions/236925/… , programmers.stackexchange.com/questions/230355/…
Doc Brown

Jawaban:

11

Untuk algoritma heuristik yang seharusnya tidak mengembalikan solusi ideal tetapi "cukup baik", Anda akan memiliki berbagai kasus uji dan memeriksa

  1. apakah solusinya benar-benar valid? Anda tentu ingin memastikan algoritma pencarian rute Anda tidak mengembalikan jalur yang tidak mungkin atau yang tidak benar-benar mengarah dari awal hingga selesai. Anda mungkin tidak dapat membuktikan bahwa solusi itu ideal, tetapi Anda setidaknya harus dapat memverifikasi bahwa nilai pengembalian sebenarnya adalah solusi.
  2. apakah solusinya "cukup baik"? Anda harus memiliki beberapa persyaratan yang menentukan seberapa buruk algoritmanya daripada solusi ideal. Anda harus memiliki kasus uji di mana solusi ideal diketahui (atau setidaknya solusi yang dianggap cukup baik untuk digunakan sebagai standar perbandingan) dan mengonfirmasi bahwa solusi yang disediakan oleh algoritma tidak lebih dari x% lebih buruk.
  3. Apakah algoritma ini cukup cepat? Anda sering menggunakan pendekatan heuristik ketika Anda menganggap bahwa mereka menebus kurangnya presisi dengan menjadi lebih cepat. Untuk memverifikasi ini, Anda harus mengukur runtime mereka dan memastikan mereka memang lebih cepat daripada algoritma yang mendapatkan solusi tepat. Pengukuran runtime selalu sedikit kabur, jadi melebihi runtime yang diharapkan harus menjadi peringatan, bukan kesalahan (ketika kerangka pengujian unit Anda memungkinkan untuk berbeda antara peringatan dan kesalahan).
Philipp
sumber
Bisakah Anda memberikan saran untuk menguji bagaimana Anda menentukan bahwa suatu rute valid?
dwjohnston
@dwjohnston Cukup ambil grafik Anda, ambil jalur Anda, dan coba lintasi jalur di atas grafik Anda. Verifikasi bahwa setiap tepi jalan mengarah dari simpul saat ini dan bahwa jalur dimulai dan berakhir di simpul yang benar. Anda juga dapat memverifikasi bahwa node-akhir tidak tercapai sebelum akhir.
Philipp
Anda juga dapat memverifikasi bahwa tidak ada simpul di jalur Anda yang digunakan dua kali, karena ini menunjukkan loop yang tidak perlu. Kecuali, tentu saja, Anda memiliki beberapa aturan khusus yang membuat loop berguna, seperti sistem pencarian rute UPS yang lebih suka tiga belokan kanan daripada satu belokan kiri .
Philipp
3

Sebagian besar algoritma pengoptimalan (termasuk heuristik) berfungsi pada beberapa konfigurasi (dalam contoh Anda rute) dengan menerapkan operasi pada mereka. Operasi untuk dirinya sendiri harus menjamin bahwa mereka hanya memberikan konfigurasi yang valid, jadi pertama-tama harus ada unit test untuk masing-masing. Ketika Anda tahu pasti algoritma pengoptimalan hanya menggunakan operasi-operasi itu, biasanya tidak perlu ada uji validitas untuk hasil algoritma.

Untuk membuat unit test yang baik untuk semua jenis algoritma yang lebih kompleks, kita harus mengetahui algoritma itu sendiri secara detail . Untuk heuristik sederhana seperti "mendaki bukit", Anda biasanya dapat memprediksi hasil untuk input kecil. Misalnya, untuk rute awal 3 hingga 5 poin, ketika diberikan dalam urutan tertentu, Anda dapat memprediksi apa yang akan terjadi. Ini akan tetap berlaku untuk sebagian besar algoritma heuristik deterministik yang saya ketahui, jadi itu mungkin tempat yang baik untuk memulai.

Untuk algoritma yang lebih kompleks, dan ukuran input yang lebih besar, ketika Anda hanya memasukkan input ke dalam algoritma dan mencoba memeriksa output, Anda sebenarnya tidak melakukan tes unit lagi, Anda sedang melakukan tes penerimaan atau integrasi. Alasan mengapa Anda memiliki masalah untuk "tes unit" algo seperti itu karena biasanya terdiri dari segelintir bagian yang lebih kecil (unit individu). Jadi untuk unit yang benar-benar menguji algoritma semacam itu, Anda harus mengidentifikasi bagian-bagian itu dan mengujinya secara individual. Selain itu, Anda dapat menggunakan cakupan kode atau teknik cakupan cabang untuk memastikan Anda memiliki cukup kasus uji.

Jika Anda tidak mencari tes unit, tetapi tes penerimaan atau integrasi otomatis, Anda dapat mencoba apa yang disarankan oleh @Phillip pada (2) atau (3) .

Doc Brown
sumber