Come testare un algoritmo genetico

Question

Ho fatto un pò di algoritmi genetici; lavorano (trovano rapidamente una soluzione ragionevole). Ma ora ho scoperto TDD. C'è un modo per scrivere un genetic algorithm (che si basa molto su numeri casuali) in un modo TDD?

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

1. Utilizzare un seme specifico. Il che non mi aiuterà se commetto un errore nel codice, ma aiuterò a trovare bug durante il refactoring.

2. Utilizzare un elenco di numeri noto. Simile a quanto sopra ma potrei seguire il codice a mano (che sarebbe molto noioso).

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

4. Cercare di spostare il maggior numero possibile di codice non deterministico dall'accordo GA. il che sembra sciocco dato che è il nocciolo del suo scopo.

Anche i collegamenti a ottimi libri di prova potrebbero essere apprezzati.

Answer 1

Mi sembra che l'unico modo per testare la sua logica coerente si applica ingresso coerente, ... o trattare ogni iterazione come singolo automa cui stato è provato prima e dopo iterazione, ruotando il sistema generale non deterministico in componenti testabili basati su valori di iterazione deterministici.

Per variazioni/allevamento/attributo di ereditarietà in iterazioni, verificare i valori sui limiti di ogni iterazione e testare l'uscita globale di tutte le iterazioni basato su noti ingresso/uscita dal successo iterazione-subtests ...

Poiché l'algoritmo è iterativo è possibile utilizzare l'induzione nei test per assicurarsi che funzioni per 1 iterazione, n + 1 iterazioni per dimostrare che produrrà risultati corretti (indipendentemente dal determinismo dei dati) per un determinato intervallo di input/dominio e i vincoli su possibile valori nell'input.

Modifica Ho trovato questo strategies for testing nondeterministic systems che potrebbe fornire alcune informazioni. Potrebbe essere utile per l'analisi statistica dei risultati live una volta che il TDD/processo di sviluppo dimostra che la logica è valida.

Answer 2

È possibile scrivere una rete neurale ridondante per analizzare i risultati del proprio algoritmo e classificare l'output in base ai risultati previsti. :)

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

Answer 3

Un test che l'algoritmo fornisce lo stesso risultato per lo stesso input può essere d'aiuto, ma a volte si apportano modifiche che modificano il comportamento di selezione dei risultati dell'algoritmo.

Farei il massimo sforzo per avere un test che garantisca che l'algoritmo fornisca un risultato corretto.Se l'algoritmo fornisce un risultato corretto per un numero di semi statici e valori casuali, l'algoritmo funziona o non viene interrotto attraverso le modifiche apportate.

Un'altra possibilità in TDD è la possibilità di valutare l'algoritmo. Se è possibile verificare automaticamente l'efficacia di un risultato, è possibile aggiungere test che dimostrino che una modifica non ha abbassato le qualità dei risultati o aumentato il tempo di calcolo irragionevole.

Se si desidera testare l'algoritmo con molti semi di base, si consiglia di testare un seme che esegue un test rapido per l'avvio dopo ogni salvataggio per assicurarsi di non aver infranto nulla e di un seme che viene eseguito per un tempo più lungo per una valutazione successiva

Answer 4

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

Answer 5

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

W/R/T il 4 ° punto, spostando il codice non deterministico fuori dalla GA, penso che questo sia probabilmente un approccio da prendere in considerazione. Se è possibile scomporre l'algoritmo e separare le preoccupazioni non deterministiche, dovrebbe rendere semplice la verifica delle parti deterministiche. Finché sei attento a come fai il nome delle cose, non penso che tu stia sacrificando molto qui. A meno che non ti fraintenda, l'AG continuerà a delegare questo codice, ma vive altrove.

Per quanto riguarda i collegamenti a molto buoni libri sul (sviluppatore) testare i miei preferiti sono:

• Test Driven da Lasse Kosela
• Working Effectively with Legacy Code di Michael Feathers
• XUnit Test Patterns da Gerard Meszaros
• Next Generation Java™ Testing: TestNG and Advanced Concepts da Cédric Beust & Hani Suleiman

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. Dovrai passare questo come parametro. In questo modo quando il tuo programma prende decisioni in base ai tuoi numeri casuali, puoi passare in numeri rappresentativi per testare l'output previsto per quel numero. L'unica cosa che non dovrebbe essere deterministica è il tuo generatore di numeri casuali, di cui non hai davvero bisogno di preoccuparti troppo perché non dovresti scrivere da solo. Dovresti essere in grado di presumere che funzioni fintanto che è una libreria stabilita.

Questo è per i test dell'unità. Per i test di integrazione, se lo fai, potresti prendere in esame la 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 C# TDD Genetic Algorithm applicazione didattica: http://code.google.com/p/evo-lisa-clone/

Prendiamo il più semplice metodo di risultato casuale nell'applicazione: PointGenetics.Create, che crea un punto casuale, dato i confini.Per questo metodo ho usato 5 prove, e nessuno di essi si basa su una specifica seme:

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

Il test casualità è semplice: per un grande contorno (molte possibilità), due consecutivi generati punti non devono essere uguali . I restanti test controllano altri vincoli.

Answer 8

Suggerisco vivamente di utilizzare gli oggetti fittizi per i casi di test dell'unità (http://en.wikipedia.org/wiki/Mock_object). Puoi usarli per deridere gli oggetti che fanno ipotesi casuali al fine di farti ottenere risultati attesi.

Answer 9

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

Per quanto riguarda il test dei parametri GA (tasso di mutazione, strategia di crossover, qualsiasi cosa) se stai implementando quella roba te stesso puoi certamente testarlo (puoi ancora test unitari attorno alla logica di mutazione, ecc.) Ma tu non sarà in grado di testare la "messa a punto" dell'AG.

In altre parole, non sarà possibile verificare se GA in realtà esegue altro che dalla bontà delle soluzioni trovate.

Answer 10

Un modo per il test unitario delle funzioni non deterministiche degli algoritmi GA è l'elezione di numeri casuali in una funzione diversa da quella logica che utilizza tali numeri casuali.

Ad esempio, se si dispone di una funzione che accetta un gene (vettore di qualcosa) e prende due punti casuali del gene per fare qualcosa con loro (mutazione o altro), è possibile inserire la generazione dei numeri casuali in una funzione, e quindi passarli insieme al gene ad un'altra funzione che contiene la logica data dai numeri.

In questo modo è possibile eseguire TDD con la funzione logica e trasmetterli a determinati geni e determinati numeri, sapendo esattamente cosa dovrebbe fare la logica sul gene dato quel numero e potendo scrivere asserzioni sul gene modificato.

Un altro modo, per testare con la generazione di numeri casuali è esternalizzare quella generazione in un'altra classe, a cui si può accedere tramite un contesto o caricata da un valore di configurazione e utilizzando una diversa per le esecuzioni di test. Ci sarebbero due implementazioni di quella classe, una per la produzione che genera numeri casuali reali, e un'altra per i test, che avrebbe modi per accettare i numeri che in seguito genererà. Quindi nel test è possibile fornire determinati numeri che la classe fornirà al codice testato.