Хаскелл: аннотация генетического алгоритма

Я новичок в мире программирования Haskell, и я режу зубы по простому генетическому алгоритму для поиска хороших решений для проблемы с Traveling Salesman. Я представляю решения как перестановки на целых числах, и поэтому у меня есть синоним этого типа

type Genome = [Int]

Сам алгоритм представляет собой набор функций, которые работают на решениях:

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

Я не уверен, насколько мой код имеет отношение к моему вопросу, поэтому, пожалуйста, спросите, нужны ли дополнительные данные. Одна вещь, о которой стоит упомянуть, заключается в том, что вышеперечисленные типы подписей фактически упрощены, я фактически использую государственную монаду для переноса StdGen, поэтому все эти функции фактически возвращают вычисления с учетом состояния.

Есть несколько вещей, которые я хотел бы сделать с этим, но не могу оторвать голову. Я хочу, чтобы можно было выбрать разные представления для решений, мне кажется, что это было бы естественным местом для использования класса типа, так что Genome будет типом класса и [Int] конкретным экземпляром этого Genome.

Теперь я хочу иметь возможность экспериментировать с реализациями, и я хочу иметь возможность использовать код в других проектах. Использование такого типа типа потребует, чтобы каждый новый алгоритм, который я создал, потребовал бы, чтобы я создал еще один экземпляр Genome, это хороший способ создать библиотеку?

Один вопрос с бонусом, просто вещь, которая беспокоила меня, - это какой-то способ создать нечто вроде синонима типа для функции, чтобы, если я пишу функцию, которая принимает функции в качестве аргументов, я могу написать синоним, а не вся сигнатура типа функции, т.е. что-то вроде следующего будет работать.

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

Правильно, надеюсь, что достаточно ясное объяснение проблемы, чувствую, что я пропустил действительно очевидный ответ, но он не выскочил на меня. Приветствия

Ответы

Ответ 1

К сожалению, идеальное решение обычно зависит от вашей проблемной области. В этом сообщении в блоге говорится о подходе типа и побитовом подходе. Я лично считаю, что гибридный подход лучше всего, если вы хотите гибкости. Если есть хорошее побитовое сопоставление, вы можете определить его, и реализация получена из этого, в противном случае вы можете реализовать кроссовер и мутировать вручную.

ja метод на самом деле не собирается работать. Некоторым из ваших функций генома понадобится случайный ввод, который вы можете получить, запустив в государственной монаде с генератором случайных чисел как этот поток

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

Затем у вас есть общие функции, которые работают с наборами геномов, независимо от реализации.

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

Если у вас есть хорошее сопоставление бит, вы можете просто определить фиксированные функции в BitArrays (обратите внимание, что каждый из них должен принимать функцию фитнеса в качестве параметра)

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]

Ответ 2

Да, использование класса типа для представления генома - хороший способ. Что-то вроде этого:

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

Что касается установки нового типа данных для каждого алгоритма, вы можете включить несколько экземпляров в свою библиотеку, но нет никаких проблем с созданием новых - что точка!