Haskell中的遗传编程
红杏出墙的爱_408 发布于 2022-12-18 20:20例如,有GenProg(http://hackage.haskell.org/package/genprog),但这仅涉及数值优化,在这种情况下,找到描述数据的等式.
但我需要循环,if语句,语句,布尔检查等.我需要能够生成命令式结构.有什么想法吗？到目前为止,我最好的选择似乎是husk-scheme,我可以在Haskell中将Scheme代码作为DSL运行.当然必须有更好的方法吗？
-
如果你正在寻找类似于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表达式的内容.
2022-12-18 20:23 回答
火云邪神
京公网安备 11010802041100号