La generación de secuencias de pruebas dinámicas desde una especificación formal complementa los métodos tradicionales de pruebas para encontrar errores en el código fuente. En este artículo extendemos un enfoque combinatorio en particular, el llamado Método del Árbol de Clasificación - Classification Tree Method (CTM), con información sobre transiciones para la generación de secuencias de pruebas. Aunque en este artículo usamos CTM, esta extensión es también posible para otros métodos de pruebas combinatorios. La generación de secuencias mínimas de pruebas que cumplan con el criterio de cobertura requerido es un problema NP-duro. Así que, vamos a necesitar un enfoque basado en búsqueda para encontrar las secuencias de pruebas óptimas en un tiempo razonable. En la sección de experimentos se comparan dos técnicas bio-inspiradas con un algoritmo voraz determinista. Hemos utilizado un conjunto de 12 modelos de programas jerárquicos concurrentes, extraídos de la literatura. Nuestras propuestas basadas en algoritmos genéticos y colonias de hormigas son capaces de generar secuencias de pruebas que alcanzan cobertura total tanto de clases como de transiciones, es decir, son capaces de encontrar el camino válido más corto para visitar todas las clases y usar todas las transiciones de un programa. El análisis de los experimentos revela que las propuestas bio-inspiradas son mejores que el algoritmo voraz determinista, especialmente en las instancias más complejas.