Haskell中的遗传编程

Question

Haskell中的遗传编程

haskelllispdslgenetic-programming

5

例如，有GenProg（{{link1：http://hackage.haskell.org/package/genprog}}），但它只处理数值优化，在这种情况下找到描述数据的方程。

但我需要for循环，if语句，when语句，布尔检查等。我需要能够生成命令式结构。您对此有何想法？到目前为止，我最好的选择似乎是husk-scheme，在其中可以将Scheme代码作为Haskell中的DSL运行。肯定有更好的方法吗？

- Robotijn

3

如果你能用单子(monad)来表达它，那么你可以使用 Control.Monad 中的函数，如 forM、when、guard(如果有MonadPlus)等。在 Haskell 中做这个有什么问题吗？你只需要一个能够表示你要生成的方程类型的结构即可。 - bheklilr

1

我怀疑在Haskell中做这件事没有问题，只是我似乎遇到了困难。我不知道如何从Haskell内部生成单子结构，然后使用类似于“eval”的等效方法运行它们。 - Robotijn

5

您能提供您想要生成的结构的示例吗？甚至只是对您尝试实现的内容进行更精确和技术性的描述？您是否希望获得像表示复杂代数方程的树形结构之类的东西？在Haskell中构建和操作这些类型的结构相对容易，而且您还有一个优势，即类型系统将限制有效树的范围。 - bheklilr

我想得到的是生成的命令式代码。该生成的代码使用遗传编程技术进行操作。在伪代码中，它看起来像以下内容：如果 object.xcoord < someInt 则旋转 someInt 度；当 object.distance > someInt 时移动 someInt cm；同时能够使用 for 循环、when等。 - Robotijn

这不会完全与Haskell中的内容相同。如果您对该语言中的控制结构以及如何执行有状态操作不是非常熟悉，我强烈建议查看Learn You a Haskell和Real Word Haskell，两者都可以免费在线获取，并提供了一个相当扎实的（尽管由于GHC的快速发展而略显过时）Haskell编程核心概念介绍。 - bheklilr

请查看已经给出的答案。Bheklir正在针对我认为是一个具体问题给出具体答案。请重新考虑将此主题从“等待审核”状态中移除。 - Robotijn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bheklilr · Accepted Answer

如果你正在寻找类似于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

如果你不理解这里发生的一切，没关系，这是许多复杂性通过一些内置函数轻松构建带有括号字符串的有效方式所实现的。这基本上是从文档中复制出来的。现在，如果我们打印出上面的表达式，它将看起来像：

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 monad中，因为您将生成随机值，但这应该不太困难。如果需要，这个结构应该很容易扩展，例如，如果您想添加三角函数和指数函数，您只需要更多的构造函数，在evalExpr中添加更多表达式，并在helper中添加适当的子句，以及一些概率调整。

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