Генетическое программирование в Haskell

Question

Например, есть GenProg (http://hackage.haskell.org/package/genprog), но это касается только численной оптимизации, в этом случае нахождения уравнения, которое описывает данные.

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

Answer 1

Если вы ищете нечто похожее на S-выражения, это довольно легко смоделировано в Haskell. Скажем, к примеру, мы хотим, чтобы представить простые алгебраические уравнения с переменными, такими как

x + 5/(y * 2 - z) 

Это может быть представлено простым AST в Haskell, в частности, мы можем реализовать его как

data Expr 
    = Lit Double  -- Literal numbers 
    | Var Char   -- Variables have single letter names 
    | Add Expr Expr  -- We can add things together 
    | Sub Expr Expr  -- And subtract them 
    | Mul Expr Expr  -- Why not multiply, too? 
    | Div Expr Expr  -- And divide 
    deriving (Eq) 

Этом позволим нам выразить приведенное выше уравнение как

Add (Var 'x') (Div (Lit 5) (Sub (Mul (Var 'y') (Lit 2)) (Var 'z'))) 

Но это довольно неудобно писать и читать трудно. Давайте начнем работать некоторые Show магии, так что он получает довольно напечатал:

instance Show Expr where 
    showsPrec n (Lit x) = showParen (n > 10) $ showsPrec 11 x 
    showsPrec n (Var x) = showParen (n > 10) $ showChar x 
    showsPrec n (Add x y) = showParen (n > 6) $ showsPrec 7 x . showString " + " . showsPrec 7 y 
    showsPrec n (Sub x y) = showParen (n > 6) $ showsPrec 7 x . showString " - " . showsPrec 7 y 
    showsPrec n (Mul x y) = showParen (n > 7) $ showsPrec 8 x . showString " * " . showsPrec 8 y 
    showsPrec n (Div x y) = showParen (n > 7) $ showsPrec 8 x . showString "/" . showsPrec 8 y 

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

x + 5.0/(y * 2.0 - z) 

Теперь для упрощения построения этих выражений. Так как они в значительной степени числовыми, мы можем реализовать Num (для abs и signum кроме) и Fractional:

instance Num Expr where 
    fromInteger = Lit . fromInteger 
    (+) = Add 
    (-) = Sub 
    (*) = Mul 
    abs = undefined 
    signum = undefined 

instance Fractional Expr where 
    (/) = Div 
    fromRational = Lit . fromRational 

Теперь можно ввести из выражения сверху, как

Var 'x' + 5/(Var 'y' * 2 - Var 'z') 

Это, по крайней мере, гораздо проще визуально разобрать, даже если мы должны вручную указывать переменные.

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

import Data.Map (Map) 
import qualified Data.Map as M 

type Env = Map Char Double 

И теперь это только основные сопоставления с образцом (наряду с вспомогательной функцией)

import Control.Applicative 

binOp :: (Double -> Double -> Double) -> Expr -> Expr -> Env -> Maybe Double 
binOp op x y vars = op <$> evalExpr x vars <*> evalExpr y vars 

evalExpr :: Expr -> Env -> Maybe Double 
evalExpr (Lit x) = const $ Just x 
evalExpr (Var x) = M.lookup x 
evalExpr (Add x y) = binOp (+) x y 
evalExpr (Sub x y) = binOp (-) x y 
evalExpr (Mul x y) = binOp (*) x y 
evalExpr (Div x y) = binOp (/) x y 

Теперь мы можем использовать evalExpr для оценки выражения на нашем мини-языке с заменой переменных. Вся обработка ошибок, если есть неопределенная переменная, выполняется монадой Maybe, и мы даже смогли сократить повторение, сделав аргумент среды неявным. Все это довольно стандартно для простого выражения DSL.

Итак, для забавного бита, генерирующего случайные выражения и (в конечном итоге) мутации. Для этого нам понадобится System.Random. Мы хотим иметь возможность генерировать выражения различной сложности, поэтому мы выражаем их грубо. Поскольку это случайность, есть шанс, что мы получим более короткие или более глубокие деревья, чем указано. Вероятно, это будет то, что вы захотите настроить и настроить, чтобы получить желаемые результаты. Во-первых, потому что у меня дальновидность, написав уже этот код, давайте определим два помощника для генерации случайных буквальным и случайную переменную:

randomLit, randomVar :: IO Expr 
randomLit = Lit <$> randomRIO (-100, 100) 
randomVar = Var <$> randomRIO ('x', 'z') 

Ничего возбуждающий здесь, мы получаем двойники от -100 до 100, и выше до 3 переменных. Теперь мы можем генерировать большие деревья выражений.

generateExpr :: Int -> IO Expr 
-- When the depth is 1, return a literal or a variable randomly 
generateExpr 1 = do 
    isLit <- randomIO 
    if isLit 
     then randomLit 
     else randomVar 
-- Otherwise, generate a tree using helper 
generateExpr n = randomRIO (0, 100) >>= helper 
    where 
     helper :: Int -> IO Expr 
     helper prob 
      -- 20% chance that it's a literal 
      | prob < 20 = randomLit 
      -- 10% chance that it's a variable 
      | prob < 30 = randomVar 
      -- 15% chance of Add 
      | prob < 45 = (+) <$> generateExpr (n - 1) <*> generateExpr (n - 1) 
      -- 15% chance of Sub 
      | prob < 60 = (-) <$> generateExpr (n - 1) <*> generateExpr (n - 1) 
      -- 15% chance of Mul 
      | prob < 75 = (*) <$> generateExpr (n - 1) <*> generateExpr (n - 1) 
      -- 15% chance of Div 
      | prob < 90 = (/) <$> generateExpr (n - 1) <*> generateExpr (n - 1) 
      -- 10% chance that we generate a possibly taller tree 
      | otherwise = generateExpr (n + 1) 

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

---

Итак, помните, что мы можем все-таки матч шаблона на конструкторах этого Expr типа для других операций, например, замена узлов, их замены, или измерения глубины. Для этого вам просто нужно рассматривать его как любой другой тип двоичного дерева в Haskell, за исключением того, что он имеет 2 конструктора листа и 4 конструктора узлов. Что касается мутаций, вам придется писать код, который пересекает эту структуру и выбирает, когда нужно менять узлы и что их менять. Он будет жить в монаде IO, так как вы будете генерировать случайные значения, но это не должно быть слишком сложно. Эта структура должна быть довольно легко расширяться по мере необходимости, например, если вы хотите добавить триггерные функции и возведение в степень, вам просто нужно больше конструкторов, больше выражений в evalExpr и соответствующие предложения в helper, а также некоторые корректировки вероятности.

Вы можете получить полный код для этого примера here. Надеюсь, это поможет вам понять, как сформулировать что-то вроде S-выражений в Haskell.