Algoritmi di approssimazione del test delle unità

Question

Sto lavorando ad una libreria di algoritmi di approssimazione open-source per grafici e reti usando come base alcuni pacchetti python popolari. L'obiettivo principale è comprendere algoritmi di approssimazione aggiornati per problemi NP-Complete su grafici e reti. La ragione di ciò è 1) Non ho visto un bel pacchetto (moderno) consolidato che copra questo e 2) sarebbe un bel strumento pedagogico per imparare ad algoritmi di approssimazione su problemi di ottimizzazione NP-Hard.

Nella creazione di questa libreria sto usando unit-test per verificare l'integrità (come farebbe uno sviluppatore corretto). Sono un po 'cauto riguardo ai miei test unitari in quanto, per loro stessa natura, gli algoritmi di approssimazione potrebbero non restituire la soluzione corretta. Attualmente sto risolvendo alcune piccole istanze a mano e poi assicurando che il risultato restituito corrisponda a quello, ma questo non è desiderabile, né scalabile in senso implementativo.

Quale sarebbe il modo migliore per testare gli algoritmi di approssimazione? Generare istanze casuali e assicurarsi che i risultati restituiti siano inferiori al limite garantito dall'algoritmo? Sembrerebbe avere falsi positivi (il test è stato solo fortunato in quel momento, non è garantito che tutte le istanze siano inferiori al limite).

Answer 1

È necessario separare due problemi qui. La qualità dei tuoi algoritmi di approssimazione e la correttezza di implementazione di quegli algoritmi.

Il test della qualità di un algoritmo di approssimazione di solito non si presta ai metodi di verifica dell'unità utilizzati nello sviluppo del software. Ad esempio, è necessario generare problemi casuali rappresentativi delle dimensioni reali dei problemi. Potresti aver bisogno di fare un lavoro matematico per ottenere un limite superiore/inferiore per giudicare la qualità dei tuoi algoritmi per le grandi istanze irrisolvibili. Oppure usa set di test problematici che hanno soluzioni note o più conosciute e confronta i tuoi risultati. Ma in ogni caso i test unitari non ti aiuteranno molto a migliorare la qualità degli algoritmi di approssimazione. Questo è dove la conoscenza del dominio in ottimizzazione e matematica aiuterà.

La correttezza della vostra implementazione è dove i test unitari saranno davvero utili. È possibile utilizzare qui problemi di dimensioni giocattolo e confrontare risultati noti (risolvendo manualmente o verificati tramite debug in codice passo a passo) con ciò che genera il codice. Avere piccoli problemi non solo è sufficiente ma anche desiderabile, in modo che i test siano eseguiti velocemente e possano essere eseguiti molte volte durante il ciclo di sviluppo. Questi tipi di test assicurano che l'algoritmo complessivo stia arrivando al risultato corretto.È da qualche parte tra un test unitario e un test di integrazione poiché si sta testando una grande porzione del codice come una scatola nera. Ma ho trovato che questi tipi di test sono estremamente utili nel dominio di ottimizzazione. Una cosa che raccomando di fare per questo tipo di test è la rimozione di ogni casualità negli algoritmi attraverso i semi fissi per i generatori di numeri casuali. Questi test dovrebbero sempre funzionare in modo deterministico e dare esattamente lo stesso risultato il 100% delle volte. Raccomando anche il test delle unità nei moduli di livello inferiore dei tuoi algoritmi. Isolare il metodo che assegna i pesi agli archi sul grafico e verificare se sono stati assegnati i pesi corretti. Isolare la funzione di calcolo del valore della funzione obiettivo e l'unità di test. Ottieni il mio punto.

Un'altra preoccupazione che taglia entrambe queste sezioni è la prestazione. Non è possibile testare in modo affidabile le prestazioni con piccoli problemi di giocattoli. Anche la realizzazione di un cambiamento che degrada significativamente le prestazioni per un algoritmo di lavoro è molto desiderabile. Una volta che hai una versione in esecuzione dei tuoi algoritmi, puoi creare problemi di test più grandi dove misuri le prestazioni e automatizzale come test di performance/integrazione. È possibile eseguirli con minore frequenza poiché impiegheranno più tempo ma almeno notificheranno in anticipo i colli di bottiglia introdotti di recente durante il refactoring o nuove aggiunte agli algoritmi

Answer 2

Controllare la validità delle soluzioni prodotte è il primo passo ovvio.

Inoltre, un angolo di attacco può essere regression testing utilizzando istanze per le quali è nota la soluzione approssimativa prevista (ad esempio ottenuta eseguendo l'algoritmo manualmente o utilizzando l'implementazione dell'altrui stesso algoritmo).

Esistono anche archivi di istanze di problemi con soluzioni (ottimali) note, come ad esempio TSPLIB per problemi simili a TSP. Forse questi potrebbero essere messi in qualche modo.

Se sono presenti limiti superiori noti per l'algoritmo in questione, la generazione di molte istanze casuali e la verifica delle soluzioni euristiche contro i limiti superiori potrebbero rivelarsi fruttuose. Se lo fai, ti esorto a rendere riproducibili le corse (ad esempio utilizzando sempre lo stesso generatore di numeri casuali e seme).

Un'ultima nota: per alcuni problemi, le istanze completamente casuali sono in media piuttosto facili da trovare per soluzioni approssimate. TSP asimmetrico con pesi d'arco scelti in modo uniforme e indipendente è uno di questi esempi. Sto menzionando questo poiché potrebbe influire sulla tua strategia di test.

Answer 3

Di solito, è possibile controllare, ad esempio, che il proprio algoritmo restituisce sempre soluzioni che soddisfano i loro vincoli, anche se non sono ottimali. Dovresti anche fare dei controlli di asserzione in ogni occasione possibile - questi saranno specifici per il tuo programma, ma potresti controllare che una certa quantità sia conservata, o che qualcosa che dovrebbe aumentare o, nel peggiore dei casi, rimanere uguale non diminuisca, o che alcuni locali supposti ottimo è davvero un ottimo locale.

Dato questo tipo di controlli e i controlli sui limiti che hai già menzionato, io preferisco eseguire test su un numero molto grande di piccoli problemi generati casualmente, con semi casuali scelti in modo tale che se fallisce in caso di problemi 102324 è possibile ripetere questo errore per il debug senza aver prima eseguito i problemi 102323. Con un gran numero di problemi, aumenti la possibilità che un bug sottostante causi un errore abbastanza ovvio da non riuscire a controllare. Con piccoli problemi, aumenti le possibilità che tu possa trovare e correggere il bug.