Haskell의 유전 프로그래밍

Question

예를 들어 GenProg (http://hackage.haskell.org/package/genprog)가 있지만이 경우 수치 최적화 만 수행합니다.이 경우에는 데이터를 설명하는 방정식을 찾습니다.

하지만 루프, if 문, when 문, 부울 체크 등이 필요합니다. 명령 구조를 생성 할 수 있어야합니다. 이것에 대한 어떤 생각? 지금까지의 최선의 선택 사항은 Haskell에서 Scheme 코드를 DSL로 실행할 수있는 husk-scheme 인 것 같습니다. 확실히 더 좋은 방법이 있어야합니까?

Answer 1

S- 표현식과 비슷한 것을 찾고 있다면, 이것은 하스켈에서 상당히 쉽게 모델링됩니다. 예를 들어, 우리는 이러한

x + 5/(y * 2 - z) 

이것은 하스켈 간단한 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) 

다음 표현식을 간단하게 만들 수 있습니다. 그들은 꽤 많은 숫자입니다 때문에, 우리는 (abs 및 signum 제외) Num 및 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 유형의 생성자에 패턴 일치를 할 수 있음을 기억하십시오. 이를 위해 하스켈에서 다른 2 진 트리 유형으로 취급해야합니다. 단, 2 리프 생성자와 4 노드 생성자가 있어야합니다. 돌연변이에 관해서는, 당신은이 구조를 가로 지르는 코드를 작성해야하고 노드를 교체 할시기와 교체 할 대상을 선택해야합니다. 랜덤 값을 생성 할 것이므로 IO 모나드 안에 살게 될 것입니다. 그러나 너무 어렵지 않아야합니다. 이 구조체는 trig 함수와 지수 연산을 추가하려는 경우와 같이 evalExpr에 더 많은 생성자와 더 많은 표현식이 필요하며 일부 확률 조정과 함께 helper에 해당 절이 필요하면 필요에 따라 확장하기가 매우 쉬워야합니다.

이 예에 대한 전체 코드는 here입니다. Haskell에서 S-expressions과 같은 것을 공식화하는 방법을 배우는 데 도움이되기를 바랍니다.