Haskell: Resumiendo un algoritmo genético

Question

Soy nuevo en el mundo de la programación de Haskell y estoy aprendiendo un algoritmo genético simple para encontrar buenas soluciones al problema del Viajero Vendedor. Estoy representando a las soluciones como permutaciones de números enteros y por lo que tengo este tipo de sinónimos

type Genome = [Int] 

El propio algoritmo es un conjunto de funciones que operan sobre las soluciones:

mutation :: Genome -> Genome 
selectParents :: [Genome] -> [Genome] -> [Genome] 
crossover :: Genome -> Genome -> (Genome, Genome) 
selectSurvivors :: [Genome] -> [Genome] -> [Genome] 

No estoy seguro de cómo gran parte de mi código es relevante para mi pregunta, así que pregunte si se necesitan más detalles. Una cosa que vale la pena mencionar es que las firmas de tipo anteriores están realmente simplificadas, de hecho estoy usando la mónada de estado para llevar a cabo un StdGen, por lo que todas estas funciones realmente devuelven cálculos con estado.

Hay varias cosas que me gustaría hacer con esto pero no puedo entender bien. Quiero hacer posible elegir diferentes representaciones para las soluciones, me parece que este sería un lugar natural para usar una clase de tipo, de modo que Genome sería la clase de tipo y [Int] una instancia específica de este Genome.

Ahora, quiero experimentar con las implementaciones, y quiero poder usar el código en otros proyectos. Usar una clase de tipo como esta requeriría que cada nuevo algoritmo que crease me requiriera crear otra instancia de Genome, ¿es esta una buena manera de crear una biblioteca?

Una pregunta extra, solo una cosa que me ha estado molestando, ¿hay alguna manera de crear algo así como un sinónimo para una función? Así que si estoy escribiendo una función que toma funciones como argumentos, puedo escribir el sinónimo que la firma de tipo entero de la función, es decir, para que funcione algo como lo siguiente.

type someFunc = [Int] -> [Int] -> Int 
someOtherFunc :: someFunc -> [Int] -> Int 

derecho, es de esperar que es una explicación lo suficientemente lúcida del problema, se siente como que he perdido la respuesta muy obvio pero no ha saltado a mí. Cheers

Answer 1

Desafortunadamente, la solución ideal generalmente depende del dominio de su problema. This blog post habla sobre el enfoque de tipo de letra y el enfoque de bit a bit. Personalmente creo que un enfoque híbrido es mejor si quieres flexibilidad. Si hay un buen mapeo a nivel de bits, puede definirlo y la implementación se deriva de eso; de lo contrario, puede implementar el crossover y mutar manualmente.

El método de ja en realidad no va a funcionar. Algunas de sus funciones genoma van a necesitar de entrada al azar, que se puede obtener mediante la ejecución de la mónada estado con un generador de números aleatorios like this thread

class Genome a where 
    fitness :: a -> Int 
    breed :: (RandomGen g, MonadState g m) => a -> a -> m a 
    mutate :: (RandomGen g, MonadState g m) => a -> m a 

Entonces usted tiene funciones comunes que operan sobre conjuntos de genomas, independientemente de la aplicación .

selectParents :: (Genome a, RandomGen g, MonadState g m) => [a] -> m [a] 
selectSurvivors :: (Genome a, RandomGen g, MonadState g m) => [a] -> m [a] 

Si usted tiene una buena correlación de bits, sólo puede definir funciones fijas en BitArrays (nótese que cada uno tendrá que tomar la función de aptitud como parámetro)

breed :: (RandomGen g, MonadState g m) => BitArray -> BitArray -> m BitArray 
mutate :: (RandomGen g, MonadState g m) => BitArray -> m BitArray 
selectParents :: (RandomGen g, MonadState g m) => (BitArray -> Int) -> [BitArray] -> m [BitArray] 
selectSurvivors :: (RandomGen g, MonadState g m) => (BitArray -> Int) -> [BitArray] -> m [BitArray] 

Answer 2

Sí, usar una clase de tipo para representar un genoma es una buena forma de hacerlo. Algo como esto:

 
class Genome a where 
    mutation :: a -> a 
    selectParents :: [a] -> [a] -> [a] 
    crossover :: a -> a -> (a, a) 
    selectSurvivors :: [a] -> [a] -> [a] 
instance Genome [a] where 
    mutation l = l 
    selectParents l1 l2 = l1 
    crossover g1 g2 = (g1,g2) 
    selectSurvivors l1 l2 = l1 
data Tree a = Leaf a | Branch [Tree a] 
instance Genome (Tree a) where 
    mutation t = t 
    selectParents l1 l2 = l1 
    crossover g1 g2 = (g1,g2) 
    selectSurvivors l1 l2 = l1 

En cuanto a generar ejemplares de un nuevo tipo de datos para cada algoritmo, puede incluir algunas instancias en la biblioteca, pero no hay problema de generar ejemplares de otras nuevas - que es el punto!