Come devo testare un algoritmo genetico

Question

Ho creato alcuni algoritmi genetici; funzionano (trovano rapidamente una soluzione ragionevole). Ma ora ho scoperto TDD . Esiste un modo per scrivere un algoritmo genetico (che si basa fortemente su numeri casuali) in modo TDD ?

Per porre la domanda più in generale, come testare un metodo / funzione non deterministico. Ecco cosa ho pensato:

1. Usa un seme specifico. Che non aiuta se commetto un errore nel codice in primo luogo, ma aiuterà a trovare bug durante il refactoring.

2. Utilizza un elenco noto di numeri. Simile al precedente ma ho potuto seguire il codice a mano (che sarebbe molto noioso).

3. Usa un numero costante. Almeno so cosa aspettarmi. Sarebbe bene assicurarsi che un dado legga sempre 6 quando RandomFloat (0,1) restituisce sempre 1.

4. Prova a spostare il più possibile il codice non deterministico da GA. che sembra sciocco in quanto questo è il nocciolo del suo scopo.

Anche i link a ottimi libri sui test sarebbero apprezzati.

Answer 1

Mi sembra che l'unico modo per testare la sua logica coerente sia applicare input coerenti , ... o trattare ogni iterazione come un singolo automa il cui stato viene testato prima e dopo quell'iterazione, trasformando il sistema non deterministico complessivo in componenti testabili basati su valori di iterazione deterministica.

Per variazioni / ereditarietà / ereditarietà degli attributi nelle iterazioni, testare quei valori sui limiti di ogni iterazione e testare l'output globale di tutte le iterazioni sulla base di input / output noti da esiti positivi di sub-test ...

Poiché l'algoritmo è iterativo, puoi utilizzare induzione nei tuoi test per assicurarti che funzioni per 1 iterazione, n + 1 iterazioni per dimostrare che produrrà risultati corretti (indipendentemente dal determinismo dei dati) per un dato intervallo / dominio di input e vincoli sui possibili valori nell'input.

Modifica Ho trovato queste strategie per i test sistemi non deterministici che potrebbero fornire alcune informazioni. Potrebbe essere utile per l'analisi statistica dei risultati in tempo reale una volta che il processo di sviluppo / TDD dimostra che la logica è valida.

Answer 2

Vorrei testare le funzioni casuali testandole un numero di volte e analizzando se la distribuzione dei valori di ritorno soddisfa le aspettative statistiche (ciò comporta alcune conoscenze statistiche).

Answer 3

Se stai parlando di TDD, direi sicuramente iniziare scegliendo un numero costante e facendo crescere la tua suite di test da lì. Ho fatto TDD su alcuni problemi altamente matematici e aiuta ad avere alcuni casi costanti che conosci e che hai elaborato a mano per correre dall'inizio.

W / R / T il tuo quarto punto, spostando il codice non deterministico da GA, penso che questo sia probabilmente un approccio che vale la pena considerare. Se riesci a scomporre l'algoritmo e separare le preoccupazioni non deterministiche, dovrebbe rendere semplice la verifica delle parti deterministiche. Finché stai attento a come dai un nome alle cose, non penso che stai sacrificando molto qui. A meno che non ti fraintenda, il GA continuerà a delegare a questo codice, ma vive altrove.

Per quanto riguarda i link a ottimi libri sui test (per sviluppatori) i miei preferiti sono:

• Test Driven di Lasse Kosela
• Lavorare efficacemente con il codice legacy di Michael Feathers
• XUnit Test Patterns di Gerard Meszaros
• Java di nuova generazione & # 8482; Test: TestNG e Advanced Concepts di C & # 233; dric Beust & amp; Hani Suleiman

Answer 4

Un modo che faccio per test unitari di funzioni non deterministiche degli algoritmi GA è mettere l'elezione di numeri casuali in una diversa funzione di quella logica che usa quei numeri casuali.

Ad esempio, se hai una funzione che prende un gene (vettore di qualcosa) e prende due punti casuali del gene per fare qualcosa con loro (mutazione o altro), puoi mettere la generazione dei numeri casuali in un e quindi passarli insieme al gene ad un'altra funzione che contiene la logica data quei numeri.

In questo modo puoi fare TDD con la funzione logica e passargli determinati geni e determinati numeri, sapendo esattamente cosa dovrebbe fare la logica sul gene dato quei numeri e potendo scrivere affermazioni sul gene modificato.

Un altro modo, per testare con la generazione di numeri casuali è esternare quella generazione in un'altra classe, a cui è possibile accedere tramite un contesto o caricato da un valore di configurazione, e usarne uno diverso per le esecuzioni di test. Ci sarebbero due implementazioni di quella classe, una per la produzione che genera numeri casuali effettivi e un'altra per i test, che avrebbe modi di accettare i numeri che in seguito genererà. Quindi nel test potresti fornire quei numeri che la classe fornirà al codice testato.

Answer 5

Potresti scrivere una rete neurale ridondante per analizzare i risultati dal tuo algoritmo e far classificare l'output in base ai risultati previsti. :)

Suddividi il metodo il più possibile. Quindi puoi anche fare un test unitario solo attorno alla parte casuale per controllare l'intervallo di valori. Anche far eseguire il test alcune volte per vedere se il risultato cambia.

Answer 6

Tutte le tue funzioni dovrebbero essere completamente deterministiche. Ciò significa che nessuna delle funzioni che stai testando dovrebbe generare il numero casuale all'interno della funzione stessa. Ti consigliamo di passarlo come parametro. In questo modo quando il tuo programma prende decisioni in base ai tuoi numeri casuali, puoi passare numeri rappresentativi per testare l'output previsto per quel numero. L'unica cosa che non dovrebbe essere deterministica è il tuo vero generatore di numeri casuali, di cui non devi preoccuparti troppo perché non dovresti scriverlo da solo. Dovresti essere in grado di supporre che funzioni fintanto che è una libreria consolidata.

Questo è per i test unitari. Per i tuoi test di integrazione, se lo stai facendo, potresti cercare di deridere la tua generazione di numeri casuali, sostituendola con un algoritmo che restituirà numeri noti da 0..n per ogni numero casuale che devi generare.

Answer 7

Ho scritto un'applicazione didattica sull'algoritmo genetico TDD C #: http://code.google.com/p/evo-lisa-clone/

Prendiamo il metodo di risultato casuale più semplice nell'applicazione: PointGenetics.Create, che crea un punto casuale, dati i limiti. Per questo metodo ho usato 5 test e nessuno di essi si basa su un seme specifico:

http: / /code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

Il test di casualità è semplice: per un grande confine (molte possibilità), due punti generati consecutivi non dovrebbero essere uguali. I test rimanenti controllano altri vincoli.

Answer 8

Beh, la parte più testabile è la funzione di fitness - dove sarà tutta la tua logica. questo può essere in alcuni casi piuttosto complesso (potresti eseguire tutti i tipi di simulazioni in base ai parametri di input), quindi vuoi essere sicuro che tutto ciò funzioni con un sacco di test unitari e questo lavoro può seguire qualunque metodologia.

Per quanto riguarda il test dei parametri GA (tasso di mutazione, strategia di crossover, qualunque cosa) se stai implementando quella roba tu stesso puoi certamente testarla (puoi ancora avere test unitari attorno alla logica della mutazione ecc.) ma hai vinto essere in grado di testare la "messa a punto" di GA.

In altre parole, non sarai in grado di testare se GA in realtà si comporta diversamente dalla bontà delle soluzioni trovate.

Answer 9

Un test che l'algoritmo ti dà lo stesso risultato per lo stesso input potrebbe aiutarti ma a volte apporterai modifiche che cambiano il comportamento di selezione dei risultati dell'algoritmo.

Farei il massimo sforzo per fare un test che assicuri che l'algoritmo ti dia un risultato corretto. Se l'algoritmo fornisce un risultato corretto per un numero di seed statici e valori casuali, l'algoritmo funziona o non viene superato attraverso le modifiche apportate.

Un'altra possibilità in TDD è la possibilità di valutare l'algoritmo. Se riesci a controllare automaticamente quanto è buono un risultato, potresti aggiungere test che dimostrano che una modifica non ha abbassato le qualità dei risultati o aumentato il tuo tempo di calcolo irragionevole.

Se vuoi testare il tuo algoritmo con molti semi base, potresti voler testare una tuta che esegue un test rapido per iniziare dopo ogni salvataggio per assicurarti di non aver rotto nulla e una tuta che funziona per un più tempo per una valutazione successiva

Answer 10

Consiglio vivamente di esaminare l'uso di oggetti finti per i casi di test unitari ( http: // it. wikipedia.org/wiki/Mock_object ). Puoi usarli per deridere oggetti che fanno ipotesi casuali al fine di ottenere invece i risultati previsti.