遗传编程在Haskell中 [英] Genetic Programming in Haskell

问题描述

GenProg（ http://hackage.haskell.org/package/genprog ）例如，但只处理数值优化，在这种情况下找到描述数据的公式。

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

解决方案

如果您正在寻找类似于S表达式的东西，在Haskell。举例来说，我们想用变量来表示简单的代数方程，比如 $ b

x + 5 /（y * 2 - z）


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

data Expr
= Lit Double - 文字数字
| Var Char - 变量有单个字母名称
|添加Expr Expr - 我们可以将所有东西加在一起
| Sub Expr Expr - 并将它们减去
| Mul Expr Expr - 为什么不能相乘呢？
| Div Expr Expr - 除以
派生（Eq）


这会让我们表达上面的方程式为

Add（Var'x'）（Div（Lit 5）（Sub Mul（Var'y'）（Lit 2））（Var'z'）））


但编写起来相当笨拙，难以阅读。让我们开始工作一些 Show magic，以便它可以打印出来：



 实例显示expr其中
 showsPrec N（点亮X）= showParen（N大于10）$ showsPrec 11×
 showsPrec N（无功X）= showParen（N> 10）$ showChar x 
 showsPrec n（Add xy）= showParen（n> 6）$ showsPrec 7 x。 showString+。 showsPrec 7 y 
 showsPrec n（Sub x y）= showParen（n> 6）$ showsPrec 7 x。 showString - 。显示Prec 7 y 
显示Prec n（Mul x y）= showParen（n> 7）$显示Prec 8 x。 showString*。 showsPrec 8 y 
 showsPrec n（Div x y）= showParen（n> 7）$ showsPrec 8 x。 showString/。 showsPrec 8 y 
  

如果您不理解这里所发生的一切，没关系，这是很多通过一些内置函数来简化复杂化，以便在其中正确构建带括号的字符串并有效地构建所有有趣的东西。它几乎是从 Text.Show 中的文档中复制出来的。现在，如果我们从上面打印出我们的表达式，它会看起来像

$ b

x + 5.0 / （y * 2.0 - z）


现在简化构建这些表达式。由于它们的数值很大，我们可以实现 Num （除了 abs 和 signum ）和小数：



  instance Num Expr其中
 fromInteger = Lit。 fromInteger 
（+）= Add 
（ - ）= Sub 
（*）= Mul 
 abs = undefined 
 signum = undefined 
 
实例Fractional Expr其中
（/）= Div 
 fromRational = Lit。 fromRational 
  

现在我们可以从上面输入表达式作为



  Var'x'+ 5 /（Var'y'* 2  -  Var'z'）
  
 
 
 
即使我们必须手动指定变量，这至少在视觉上更容易解析。
 
 
 
现在我们有了漂亮的输入和输出，让我们专注于评估这些表达式。由于我们在这里有变量，所以我们需要一些将变量与值相关联的环境
  import Data.Map（Map）
将合格的Data.Map导入为M 
 
类型Env = Map Double Double 
  
 $ b $ p现在它只是基本的模式匹配（以及一个辅助函数）
 
 
  import Control.Applicative 
 
 binOp ::（Double  - > Double  - > Double） - > Expr  - > Expr  - > Env  - >也许Double 
 binOp op x y vars = op< $> evalExpr x vars< *> evalExpr y vars 
 
 evalExpr :: Expr  - > Env  - >也许双人间
 evalExpr（点亮X）=常数$仅售X 
 evalExpr（VAR X）= M.lookup X 
 evalExpr（添加XY）= binOp（+）XY 
 evalExpr （Sub xy）= binOp（ - ）xy 
 evalExpr（Mul xy）= binOp（*）xy 
 evalExpr（Div xy）= binOp（/）xy 
  
现在我们可以使用 evalExpr 来评估带有变量替换的迷你语言表达式。如果有一个未定义的变量，所有错误处理由 Maybe  monad完成，我们甚至可以通过隐含环境参数来减少重复。这对于一个简单的表达式DSL来说都是相当标准的。 
 
 
 
 
 
所以对于有趣的位，生成随机表达式和（最终）突变。为此，我们需要 System.Random 。我们希望能够生成不同复杂度的表达式，所以我们将以粗略的深度表达它。由于它是随机的，因此我们可能会得到比指定的更短或更深的树。这可能是你想调整和调整以获得你想要的结果的东西。首先，因为我已经有了编写这段代码的远见，所以我们定义两个助手来生成一个随机文本和一个随机变量： 
 
 
  randomLit，randomVar :: IO Expr 
 randomLit = Lit <$> randomRIO（-100,100）
 randomVar = Var< $> randomRIO（'x'，'z'）
  
这里没有什么令人兴奋的，我们在-100和100，最多3个变量。现在我们可以生成大型的表达式树了。
  generateExpr :: Int  - > IO Expr 
  - 深度为1时，随机返回一个文字或变量
 generateExpr 1 = do 
 isLit < -  randomIO 
 if is 
 then randomLit 
 else randomVar 
  - 否则，使用助手生成树
 generateExpr n = randomRIO（0，100）>> = helper 
其中
 helper :: Int  - > IO Expr 
助手概率
  -  20％可能是一个字面值
 |概率< 20 = randomLit 
  -  10％可能是变量
 |概率< 30 = randomVar 
  -  15％的机会添加
 |概率< 45 =（+）< $> generateExpr（n-1）* generateExpr（n  -  1）
  -  15％的可能性Sub 
 |概率< 60 =（ - ）< $> generateExpr（n-1）* generateExpr（n  -  1）
  -  Mul 
 | 15％的概率概率< 75 =（*）< $> generateExpr（n-1）* generateExpr（n  -  1）
  -  Div 
 |的概率为15％概率< 90 =（/）< $> generateExpr（n-1）* generateExpr（n  -  1）
  - 我们有10％的机会产生可能较高的树
 |否则= generateExpr（n + 1）
  
这个函数的大部分只是指定给定的概率节点将生成，然后为每个运算符生成左右节点。我们甚至必须使用普通的算术运算符，因为我们已经超载了 Num ，这很方便！ 
 
 
 
 
 
现在，请记住，我们仍然可以在< Expr 类型的构造函数上对其他操作进行模式匹配，例如替换节点，交换它们或测量深度。为此，除了具有2个叶构造函数和4个节点构造函数之外，您只需将其作为Haskell中的任何其他二进制树类型处理即可。至于突变，您必须编写遍历此结构的代码，并选择何时交换节点以及将它们交换出去。它将存在于 IO  monad中，因为您将生成随机值，但它不应太难。这个结构应该很容易根据需要进行扩展，比如如果你想添加trig函数和指数，你只需要更多的构造函数，更多的表达式在 evalExpr 中，和 helper 中的适当的子句，以及一些概率调整。 
 
 
你可以得到这个例子的完整代码此处。希望这可以帮助您了解如何在Haskell中构建像S表达式之类的东西。
 
There is GenProg (http://hackage.haskell.org/package/genprog) for example, but that only deals with numerical optimization, in this case finding an equation that describes the data. 

But I require for loops, if statements, when statements, Boolean checks etc. I need to be able to generate imperative structures. Any thought on this? My best options so far seem to be husk-scheme where I can run Scheme code as a DSL in Haskell. Surely there must be better ways?
解决方案
If you're looking for something akin to S-expressions, this is fairly easily modeled in Haskell.  Say, for example, we want to represent simple algebraic equations with variables, such as
x + 5 / (y * 2 - z)
This can be represented by a simple AST in Haskell, in particular we can implement it as
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)
This would let us express the equation above as
Add (Var 'x') (Div (Lit 5) (Sub (Mul (Var 'y') (Lit 2)) (Var 'z')))
But this is rather clunky to write and difficult to read.  Let's start by working some Show magic so that it gets pretty printed:
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
If you don't understand everything going on here, that's ok, it's a lot of complication made easy by some built in functions for efficiently building strings with parentheses in them properly and all that fun stuff.  It's pretty much copied out of the docs in Text.Show.  Now if we print out our expression from above, it'll look like
x + 5.0 / (y * 2.0 - z)
Now for simplifying building these expressions.  Since they're pretty much numeric, we can implement Num (except for abs and signum) and Fractional:
instance Num Expr where
    fromInteger = Lit . fromInteger
    (+) = Add
    (-) = Sub
    (*) = Mul
    abs = undefined
    signum = undefined

instance Fractional Expr where
    (/) = Div
    fromRational = Lit . fromRational
Now we can input out expression from above as
Var 'x' + 5 / (Var 'y' * 2 - Var 'z')
This is at least much easier to visually parse, even if we have to specify the variables manually.

Now that we have pretty input and output, let's focus on evaluating these expressions.  Since we have variables in here, we'll need some sort of environment that associates a variable with a value
import Data.Map (Map)
import qualified Data.Map as M

type Env = Map Char Double
And now it's just basic pattern matching (along with a helper function)
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
Now we can use evalExpr to evaluate an expression in our mini-language with variable substitution.  All the error handling if there's an undefined variable is done by the Maybe monad, and we were even able to cut down on repetition by making the environment argument implicit.  This is all pretty standard for a simple expression DSL.



So for the fun bit, generating random expressions and (eventually) mutations.  For this, we'll need System.Random.  We want to be able to generate expressions of varying complexity, so we'll express it in rough depth.  Since it's random, there is a chance that we'll get shorter or deeper trees than specified.  This will probably be something that you'll want to tweak and tune to get your desired results.  First, because I have the foresight of having written this code already, let's define two helpers for generating a random literal and a random variable:
randomLit, randomVar :: IO Expr
randomLit = Lit <$> randomRIO (-100, 100)
randomVar = Var <$> randomRIO ('x',  'z')
Nothing exciting here, we get doubles between -100 and 100, and up to 3 variables.  Now we can generate large expression trees.
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)
The bulk of this function is just specifying the probabilities that a given node will be generated, and then generating the left and right nodes for each operator.  We even got to use the normal arithmetic operators since we overloaded Num, how handy!



Now, remember that we can still pattern match on the constructors of this Expr type for other operations, such as replacing nodes, swapping them, or measuring the depth.  For this, you just have to treat it as any other binary tree type in Haskell, except it has 2 leaf constructors and 4 node constructors.  As for mutations, you'll have to write code that traverses this structure and chooses when to swap out nodes and what to swap them out with.  It'll live within the IO monad since you'll be generating random values, but it shouldn't be too difficult.  This structure should be pretty easy to extend as need be, such as if you wanted to add trig functions and exponentiation, you'd just need more constructors, more expressions in evalExpr, and the appropriate clauses in helper, along with some probability adjustments.

You can get the full code for this example here.  Hope this helps you see how to formulate something like S-expressions in Haskell.

                        
这篇关于遗传编程在Haskell中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！