Haskell: abstraer un algoritmo genético

evolutionary-algorithm

Question

Soy nuevo en el mundo de la programación de Haskell y me estoy cortando los dientes con un algoritmo genético simple para encontrar buenas soluciones al problema del vendedor ambulante. Estoy representando las soluciones como permutaciones en enteros y por eso tengo este tipo de sinónimo

type Genome = [Int]

El algoritmo en sí es un conjunto de funciones que operan en las soluciones:

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

No estoy seguro de qué 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 simplificadas, de hecho, estoy usando la mónada estatal para transportar un StdGen modo que todas estas funciones realmente devuelven cálculos estadísticos.

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

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

Una pregunta adicional, solo una cosa que me ha estado molestando, es la posibilidad de crear algo así como un sinónimo de tipo para una función, de modo que si escribo una función que toma las funciones como argumentos, puedo escribir el sinónimo en lugar de todo el tipo. Firma de la función, es decir, para que funcione algo como lo siguiente.

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

Bien, espero que esa sea una explicación lo suficientemente lúcida del problema, siento que me he perdido la respuesta realmente obvia pero que no se me ha ocurrido. Aclamaciones

Answer 1

Desafortunadamente, la solución ideal generalmente depende de su dominio del problema. Esta publicación del blog habla sobre el enfoque de typeclass y el enfoque a nivel de bits. Personalmente creo que un enfoque híbrido es mejor si quieres flexibilidad. Si existe una buena asignación de bits, puede definirla y la implementación se deriva de eso, de lo contrario, puede implementar el cruce y mutar manualmente.

El método de ja en realidad no va a funcionar. Algunas de las funciones de su genoma necesitarán una entrada aleatoria, que puede obtener ejecutándose en la mónada estatal con un generador de números aleatorios como este hilo

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

Luego tiene funciones comunes que operan en conjuntos de genomas, independientemente de la implementación.

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

Si tiene una buena asignación de bits, puede definir funciones fijas en BitArrays (observe 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 tipos para representar un genoma es una buena forma de proceder. 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 la creación de una instancia de un nuevo tipo de datos para cada algoritmo, puede incluir algunas instancias en su biblioteca, pero no hay problema en la creación de instancias nuevas, ¡ese es el punto!