Haskell中的遗传编程

Question

例如,有GenProg(http://hackage.haskell.org/package/genprog),但这仅涉及数值优化,在这种情况下,找到描述数据的等式.

但我需要循环,if语句,语句,布尔检查等.我需要能够生成命令式结构.有什么想法吗？到目前为止,我最好的选择似乎是husk-scheme,我可以在Haskell中将Scheme代码作为DSL运行.当然必须有更好的方法吗？

Answer 1

如果你正在寻找类似于S表达式的东西,这在Haskell中相当容易建模.比如说,我们想要用变量表示简单的代数方程,例如

x + 5 / (y * 2 - z)

这可以用Haskell中的简单AST表示,特别是我们可以实现它

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变量替换来评估我们的迷你语言中的表达式.如果有一个未定义的变量的所有错误处理都由Maybemonad 完成,我们甚至可以通过隐含环境参数来减少重复.这对于简单的表达式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个节点构造函数.至于突变,你必须编写遍历这个结构的代码,并选择何时交换节点以及将它们交换出来的内容.它将存在于IOmonad中,因为你将生成随机值,但它不应该太难.这个结构应该很容易根据需要扩展,例如,如果你想添加trig函数和取幂,你只需要更多的构造函数,更多的表达式evalExpr和相应的子句helper,以及一些概率调整.

您可以在此处获取此示例的完整代码.希望这有助于您了解如何在Haskell中制定类似S表达式的内容.