i n d i v i d u a l s Then t h e p o p u l a t i o n s i z e i s
Then d i m e n s i o n f o r e a c h i n d i v i d u a l \ i s Then f i t n e s s i s i n i t i a l i z e d
Fig. 7. Fichero init.feature
El algoritmo elegido es un algoritmo gen´etico estacionario, SSGA, que hace uso del operador de cruce BLX − α [12]. Como mecanismo de selecci´on de padres, se aplica el criterio Negative Assortative Mating, NAM. El primer padre es elegido de forma aleatoria de la poblaci´ on, y para calcular el segundo padre se seleccionan aleatoriamente Nnum soluciones y se elige la soluci´ on m´ as alejada del primer padre. Como mecanismo de reemplazo se elige el Replacement Worst, en el que el nuevo individuo reemplaza al peor individuo de la poblaci´ on, si lo mejora. Se ha demostrado que esta combinaci´ on de selecci´on y reemplazo permite un adecuado equilibrio entre exploraci´ on y explotaci´ on [13]. Se puede observar que es un algoritmo que aunque simple posee caracter´ısticas t´ıpicas de un algoritmo evolutivo t´ıpico: Es un algoritmo poblacional, elitista, y con distintas operaciones con componente aleatorio: cruce, y selecci´ on.
el c´odigo del test ser´ıa una repetici´on del original, por lo que si hubiese un error en su implementaci´ on, dicho error se trasladar´ıa al test, no detect´andose. Por tanto, no es un modelo recomendable. El enfoque que proponemos es el siguiente: aprovechar que el resultado del operador define una serie de caracter´ısticas que se deben cumplir si est´ a implementado de forma correcta. Por tanto, nos centramos en comprobar el comportamiento esperado en vez del c´odigo. Evidentemente, no es una prueba completa, pero s´ı nos puede ser de utilidad para detectar errores. F e a t u r e : SSGA NNAM I n o r d e r t o t e s t t h e NAM s e l e c t i o n we c h e c k t h a t t h e two p a r e n t s a r r e n o t t h e same one , and than c r i t e r i o n between t h e t h e f i r s t p a r e n t and t h e s e c o n d p a r e n t i s r g i h t . Scenario : NAM s e l e c t s d i f f e r e n t p a r e n t s Given I have an SSGA a l g o r i t h m f o r \ d i m e n s i o n 10 Given I i n i t t h e p o p u l a t i o n w i t h \
i n d i v i d u a l s When I s e l e c t p a r e n t s w i t h tournament \ s i z e Then t h e p a r e n t s a r e d i f f e r e n t \ a f t e r t e s t s Examples : | p o p s i z e | t o u r n a m e n t s i z e | numruns | | 50 | 3 | 300 | ... Scenario : NAM S e l e c t t h e f a r away p a r e n t Given I have an SSGA a l g o r i t h m f o r \ d i m e n s i o n 10 Given I i n i t t h e p o p u l a t i o n w i t h \ 50 i n d i v i d u a l s When I s e l e c t p a r e n t s w i t h tournament \ s i z e 49 Then t h e d i s t a n c e between p a r e n t s i s \ the l o n g e s t
IV. Pruebas de comportamiento El uso de pruebas BDD permite establecer pruebas de los distintos elementos del algoritmo como la inicializaci´ on, selecci´ on, y cruce, en un formato legibles por alguien experto en el algoritmo. En este apartado se mostrar´ an las definiciones de los tests, el fichero steps.py asociado se incluye en el ap´endice, en las Figuras 13, 14, y 15. A. Inicializaci´ on Para comprobar la inicializaci´ on hemos definido unos tests que comprueben el estado de la poblaci´on inicial. La Figura 7 muestra la especificaci´on de los tests. Este test es relativamente sencillo, pero permite comprobar la coherencia de la poblaci´ on inicial. B. Selecci´ on Para probar la selecci´ on NAM, un primer intento ser´ıa crear un test a bajo nivel que probase que cada elecci´ on de padre siguiese el criterio indicado. Este enfoque tiene dos graves inconvenientes. Por un lado, el comportamiento aleatorio del operador impide que los resultados sean repetibles. Adem´ as, en este caso https://github.com/dmolina/ssgatests
Fig. 8. Fichero selection.feature
En este caso, nos podemos basar en el requisito que ambos padres sean siempre diferentes y; por otro lado, si el grupo de torneo incluyese al resto de la poblaci´on, el segundo padre debe ser el individuo m´ as distante al primero. La Figura 8 muestra la especificaci´on de dichos tests. C. Cruce Para probar el algoritmo BLX − α, aplicamos el mismo enfoque que en el anterior. En este caso, nos centramos en el comportamiento con α = 0. Los comportamientos que queremos probar son que el cruce de un individuo consigo mismo devuelve ese mismo individuo, y que el cruce de dos padres genera un hijo que est´a entre dichos padres. La Figura 9 muestra la especificaci´on. D. Ejecutando el Algoritmo Para que el algoritmo sea correcto, existen dos comportamientos que debe de cumplir: que el algoritmo sea elitista; y que el n´ umero de evaluaciones que realmente realice sea el que se le indica. La Fi-
482
T´ecnicas de pruebas autom´ aticas para algoritmos evolutivos
F e a t u r e : SSGA C r o s s o v e r Check f o r BLX−0 t h a t c r o s s i n g a s o l u t i o n w i t h i t s e l f g i v e s t h e same s o l u t i o n , and t h a t o f f s p r i n g a r e a l w a y s between their parents Scenario : C r o s s o v e r w i t h i t s e l f Given I have an SSGA a l g o r i t h m When I i n i t t h e p o p u l a t i o n w i t h \ 50 i n d i v i d u a l s When I s e t t h e same p a r e n t a s mother When I c r o s s w i t h a l p h a 0 Then t h e c h i l d r e n i s t h e same Scenario : O f f s p r i n g i s between t h e i r p a r e n t s Given I have an SSGA a l g o r i t h m When I i n i t t h e p o p u l a t i o n w i t h \ 50 i n d i v i d u a l s When I s e t randomly two p a r e n t s When I c r o s s w i t h a l p h a 0 Then t h e c h i l d r e n i s between them
Fig. 9. Fichero crossover.feature F e a t u r e : SSGA run Check two f e a t u r e s o f t h e a l g o r i t h m . F i r s t , t h e r e a l e v a l u a t i o n s number i s r i g h t , and the e l i t i s m of the algorithm . Scenario : SSGA a c t u a l l y u s e t h e \ maximum e v a l u a t i o n number Given I have a SSGA a l g o r i t h m When I i n i t t h e p o p u l a t i o n \ w i t h
When I run t h e a l g o r i t h m d u r i n g \ i t e r a t i o n s Then t h e y were e v a l u a t e d \ s o l u t i o n s Examples : | population size | 50 ...
| n u m i t e r a | num eval | | 1000 | 1000 |
Scenario : SSGA i s e l i t i s t Given I have a SSGA a l g o r i t h m When I i n i t t h e p o p u l a t i o n w i t h \ 50 i n d i v i d u a l s When I s t u d y t h e e v o l u t i o n o f t h e \ i n d i v i d u a l When I run t h e a l g o r i t h m d u r i n g \ i t e r a t i o n s Then i t s f i t n e s s i s a l w a y s b e t t e r Examples : | individual | best | worst | mean
| num itera | 1000 | 1000 | 1000
| | | |
Fig. 10. Fichero run.feature
gura 10 muestra la especificaci´ on de dichas comprobaciones.
dificando el c´odigo para que en vez generar n´ umeros aleatorios utilizase un conjunto de n´ umeros generados inicialmente. Sin embargo, este enfoque requerir´ıa una modificaci´on del c´odigo para las pruebas, lo que no es deseable. Una alternativa es utilizar herramientas que permitan sustituir de forma din´amica las clases que realizan una determinada tarea por objetos mocks que simulan dicho comportamiento. Un ejemplo, es la librer´ıa mocks5 de Python. Con una herramienta como ´esta, se puede modificar el comportamiento de un m´etodo o funci´on para que, durante el test, cuando se vaya a llamar a una determinada funci´on, su ejecuci´on se sustituya por otra (usando mocks) con el mismo interfaz y que simula su comportamiento. En nuestro caso, podemos reemplazar durante el test el c´odigo que realiza la generaci´on de n´ umeros aleatorios por c´odigo que devuelve n´ umeros previamente fijados en el test. De esta manera, se puede simular el comportamiento del c´odigo ante distintas secuencias de n´ umero seudoaleatorios sin tener que cambiar el c´odigo original. Scenario : Checking c r o s s o v e r w i t h \ seudorandoms and a l p h a=0 Given I have a SSGA a l g o r i t h m When I i n i t t h e p o p u l a t i o n \ w i t h 50 i n d i v i d u a l s When I s e t randomly two p a r e n t s When I u s e pseudorandoms= When I c r o s s w i t h a l p h a 0 Then t h e c h i l d r e n i s e q u a l s t o \ the o f i t s parents Examples : | seudo random | | 0 | | 1 | | 0.5 |
criterion minimum maximum mean
| | | |
Fig. 11. Escenario de cruce usando seudoaleatorios
from mock i m p o r t patch , Mock @step ( ‘ When I u s e pseudorandoms = ( [\ d . ] + ) ’ ) d e f set pseudorandoms ( step , expected random ) : # Change t h e random g e n e r a t i o n i n t o t h e t e s t w o r l d . newRandom = p a t c h ( ‘ earandom . r a n d r e a l ’ , s p e c=True ) # S e t t h e r e t u r n s when i t i s c a l l e d w o r l d . random = w o r l d . newRandom . s t a r t ( ) expected random = f l o a t ( expected random ) r e t u r n s = e x p e c t e d r a n d o m ∗np . o n e s ( dim ) w o r l d . random . r e t u r n v a l u e = r e t u r n s
´ meros seudoaleatorios V. Pruebas con nu Hasta ahora hemos abordado el problema del nodeterminismo por medio de pruebas sobre caracter´ısticas que debe cumplir un algoritmo, en vez de sobre los resultados concretos, es decir, tests de caja negra. Sin embargo, ser´ıa deseable poder complementarlo con tests de caja blanca. Para conseguir hacer tests de caja blanca m´as cercanos al c´ odigo ser´ıa necesario que el resultado fuese reproducible, pero el uso de n´ umero seudoaleatorios lo impide. En la pr´ actica, ser´ıa posible hacerlo mo-
Fig. 12. C´ odigo que modifica los n´ umeros seudoaleatorios
Como ejemplo, podemos complementar los tests anteriores sobre el operador de cruce con el test indicado en la Figura 11, en donde la asignaci´ on de generaci´on de n´ umeros aleatorios se realiza de forma sencilla al interpretar la sentencia ‘I use pseudorandoms. . . ’ con el c´odigo asociado indicado en la Figura 12 del fichero steps.py. En dicho c´odigo se indica, 5 http://www.voidspace.org.uk/python/mock/
483
Daniel Molina Cabrera y Juan Manuel Dodero
por medio de la funci´ on patch que cuando durante el test se desee llamar a la funci´ on erandom.randreal, se llame, en cambio, al objeto mock newRandom. Y luego se configura la salida que devuelve cuando se realicen dichas llamadas. Puede consultarse una explicaci´ on mucho m´ as detallada en la documentaci´on oficial de la librer´ıa mocks. El uso de pruebas autom´ aticas es una herramienta muy u ´til para detectar errores en el c´ odigo, pero el comportamiento no-determinista de los AEs se suele ver como un impedimento para poder realizarlas. En este trabajo se plantean dos estrategias para aplicar pruebas autom´ aticas sobre AEs, a pesar del uso de n´ umeros seudoaleatorios, que hace que los resultados no sean repetibles. En la primera, en vez de aplicar tests sobre resultados concretos de un operador, se propone realizar comprobaciones sobre el comportamiento que dichos operadores deben ofrecer. Se muestra el uso de esta estrategia aplic´ andola a los operadores de inicializaci´ on, cruce y ejecuci´ on de un SSGA. La otra estrategia propuesta es utilizar librer´ıas que permiten reemplazar durante los tests el c´odigo de generaci´ on de n´ umeros seudoaleatorios por c´odigo que devuelve secuencias de n´ umeros definidos de antemano, para hacer comprobaciones de m´as bajo nivel, o de caja blanca. Se ha mostrado el uso de esta estrategia para tests adicionales sobre el operador de cruce BLX − α. En conclusi´ on, en este trabajo se proponen estrategias que permiten aplicar pruebas autom´aticas a las implementaciones de AEs, con lo que se puede detectar m´ as f´ acilmente errores de implementaci´on, al mismo tiempo que son entendibles por cualquier investigador en AEs sin necesidad de conocer los detalles concretos de su implementaci´ on. Por tanto, se prueba que los AEs pueden (y deber´ıan) incorporar pruebas autom´ aticas para mejorar la confianza en la implementaci´ on de los algoritmos. VI. Agradecimientos Este trabajo fue financiado por los proyectos de investigaci´ on TIN2008-05854 y P08-TIC-4173. ´ndice Ape Las Figuras 13, 14 y 15 muestran el c´ odigo de test asociado a las definici´ on de las pruebas del art´ıculo. El c´ odigo est´ a libremente disponible en la url https://github.com/dmolina/ssgatests. Referencias [1] [2] [3] [4]
T B¨ ack, D B Fogel, and Z Michalewicz, Eds., Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997. Patrick Siarry and Zbigniew Michalewicz, Advances in metaheuristics for hard optimization, Springer-Verlag New York Inc, springer edition, 2007. G J Myers, C Sandler, T Badgett, and T M Thomas, “The art of software testing,” 2004. K Beck, Test-driven development: by example, AddisonWesley Professional, 2003.
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12] [13]
Forrest Shull, Grigori Melnik, Burak Turhan, Lucas Layman, Madeline Diep, and Hakan Erdogmus, “What Do We Know about Test-Driven Development?,” IEEE Software, vol. 27, no. 6, pp. 16–19, 2010. Nachiappan Nagappan, E. Michael Maximilien, Thirumalesh Bhat, and Laurie Williams, “Realizing quality improvement through test driven development: results and experiences of four industrial teams,” Empirical Software Engineering, vol. 13, no. 3, pp. 289–302, Feb. 2008. R.M. Hierons, “Testing from a nondeterministic finite state machine using adaptive state counting,” IEEE Transactions on Computers, vol. 53, no. 10, pp. 1330– 1342, Oct. 2004. Gordon Fraser and Franz Wotawa, “Test-Case Generation and Coverage Analysis for Nondeterministic Systems Using Model-Checkers,” International Conference on Software Engineering Advances (ICSEA 2007), pp. 45–45, 2007. D Chelimsky, D Astels, Z Dennis, A Hellesoy, B Helmkamp, and D North, “The RSpec Book: Behaviour Driven Development with RSpec, Cucumber, and Friends,” Pragmatic Bookshelf, 2010. Madhuri R. Marri, Nikolai Tillmann, Jonathan de Halleux, and Wolfram Schulte, “An empirical study of testing file-system-dependent software with mock objects,” 2009 ICSE Workshop on Automation of Software Test, pp. 149–153, May 2009. F Herrera, M Lozano, and A.M. Sanchez, “A Taxonomy for the Crossover Operator for Real-coded Genetic Algorithms,” International Journal of Intelligent Systems, vol. 18, no. 3, pp. 204–217, 2003. L.J. Eshelman and J.D. Schaffer, “Real-coded Genetic Algorithms in Genetic Algorithms by Preventing Incest,” Foundation of Genetic Algorithms 2, pp. 187–202, 1993. D Whitley, “The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best,” Proc. of the Third Int. Conf. on Genetic Algorithms, pp. 116–121, 1989.
484
T´ecnicas de pruebas autom´ aticas para algoritmos evolutivos
Inicializaci´ on @step ( ’ I have a SSGA a l g o r i t h m f o r d i m e n s i o n ( \ d + ) ’ ) d e f h a v e c o n f i g u r a t i o n ( s t e p , dim ) : dim = i n t ( dim ) w o r l d . s s g a = SSGA( f i t n e s s , domain , dim , s i z e=p o p s i z e ) @step ( ’ I i n i t t h e p o p u l a t i o n w i t h ( \ d+) i n d i v i d u a l s ’ ) def i n i t p o p u l a t i o n ( step , popsize ) : world . p o p s i z e = i n t ( p o p s i z e ) world . s s g a . i n i t P o p u l a t i o n ( i n t ( p o p s i z e ) ) @step ( ’ p o p u l a t i o n s i z e i s ( \ d + ) ’ ) def p o p s i z e r i g h t ( step , p op si z e e xp ec ted ) : popsize expected = int ( popsize expected ) ( v a l u e s s i z e , v a l u e s d i m )= w o r l d . s s g a . p o p u l a t i o n ( ) . s h a p e a s s e r t v a l u e s s i z e == p o p s i z e e x p e c t e d @step ( ’ f i t n e s s i s i n i t i a l i z e d ’ ) def f i t n e s s r i g h t ( step ) : f i t s = world . s s g a . p o p u l a t i o n f i t n e s s ( ) a s s e r t f i t s . s i z e == w o r l d . p o p s i z e @step ( ’ a l l f i t n e s s v a l u e s a r e d i f f e r e n t ’ ) def fitness not same ( step ) : f i t s = world . s s g a . p o p u l a t i o n f i t n e s s ( ) # Check t h e s i z e o f removing e q u a l s f i t n e s s a s s e r t np . u n i q u e ( f i t s ) . s i z e == w o r l d . p o p s i z e
Selecci´ on @step ( ’ I s e l e c t p a r e n t s w i t h tournament s i z e ( \ d + ) ’ ) def s e t p a r e n t s ( step , t s i z e ) : w o r l d . n a m t s i z e=i n t ( t s i z e ) @step ( ’ t h e p a r e n t s a r e d i f f e r e n t a f t e r ( \ d+) t e s t s ’ ) def m o t h e r p a r e n t d i f f e r e n t ( step , t e s t s ) : tests = int ( tests ) for
i in range ( t e s t s ) : [ mother , p a r e n t ]= w o r l d . s s g a . g e t P a r e n t s ( w o r l d . n a m t s i z e ) a s s e r t mother != p a r e n t
@step ( ’ t h e d i s t a n c e between p a r e n t s i s t h e l o n g e s t ’ ) def best parent ( step ) : s s g a = world . s s g a [ motherId , p a r e n t I d ]= s s g a . g e t P a r e n t s ( w o r l d . n a m t s i z e ) population = ssga . population () mother = p o p u l a t i o n [ motherId ] parent = population [ parentId ] d i s t a n c e s = [ u t i l s . d i s t a n c e ( p o p u l a t i o n [ i ] , mother ) f o r m a x d i s t a n c e s = np . a r r a y ( d i s t a n c e s ) . max ( ) d i s t a n c e = u t i l s . d i s t a n c e ( p a r e n t , mother ) a s s e r t d i s t a n c e == m a x d i s t a n c e s
i
i n range ( world . p o p s i z e ) ]
Fig. 13. Fichero steps.py (Parte 1)
485
Daniel Molina Cabrera y Juan Manuel Dodero
Cruce @step ( ’ I s e t t h e same p a r e n t a s mother ’ ) def set parents same ( s e l f ) : p o p u l a t i o n = world . s s g a . p o p u l a t i o n ( ) motherId = random . r a n d i n t ( 0 , w o r l d . s s g a . p o p s i z e ) w o r l d . mother = p o p u l a t i o n [ motherId ] w o r l d . p a r e n t = w o r l d . mother @step ( ’ I s e t randomly two p a r e n t s ’ ) def cross set random ( step ) : p o p u l a t i o n = world . s s g a . p o p u l a t i o n ( ) [ motherId , p a r e n t I d ] = random . r a n d i n t ( 0 , w o r l d . s s g a . p o p s i z e , 2 ) w o r l d . mother = p o p u l a t i o n [ motherId ] w o r l d . p a r e n t= p o p u l a t i o n [ p a r e n t I d ] @step ( ’ I c r o s s w i t h a l p h a ( [ \ d . ] + ) ’ ) def a p p l y c r o s s ( s e l f , alpha ) : alpha = f l o a t ( alpha ) w o r l d . c h i l d r e n = w o r l d . s s g a . c r o s s ( w o r l d . mother , w o r l d . p a r e n t , a l p h a ) @step ( ’ The c h i l d r e n i s t h e same ’ ) def has same children ( s e l f ) : a s s e r t u t i l s . d i s t a n c e ( w o r l d . c h i l d r e n , w o r l d . p a r e n t )==0 @step ( ’ The c h i l d r e n i s between them ’ ) def is between then ( s e l f ) : p a r e n t s = np . a r r a y ( [ w o r l d . mother , w o r l d . p a r e n t ] ) m i n p a r e n t = np . amin ( p a r e n t s , a x i s =0) max pare nt = np . amax ( p a r e n t s , a x i s =0) a s s e r t ( w o r l d . c h i l d r e n >= m i n p a r e n t ) . a l l ( ) , ” B r o k e s i n f e r i o r a s s e r t ( w o r l d . c h i l d r e n
