Haskell: абстракция генетического алгоритма - PullRequest
Новая
       1

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

17 голосов
/ 16 февраля 2011

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

type Genome = [Int]

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

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

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

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

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

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

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

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

Ответы [ 2 ]

7 голосов
/ 19 февраля 2011

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

Метод 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 голосов
/ 16 февраля 2011

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

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

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

...