RFE 008: 工程师（粗）Rust入门之遗传编程

 1A genetic algorithm is a form of evolution that occurs on a computer. Genetic
 2algorithms are a search method that can be used for both solving problems and
 3modeling evolutionary systems. With various mapping techniques and an
 4appropriate measure of fitness, a genetic algorithm can be tailored to evolve
 5a solution for many types of problems, including optimization of a function
 6or determination of the proper order of a sequence. Mathematical analysis
 7has begun to explain how genetic algorithms work and how best to use them.
 8Recently, genetic algorithms have been used to model several natural
 9evolutionary systems, including immune systems.
10--- Stephanie Forrest, 
11Genetic Algorithms: Principles of Natural Selection Applied to Computation,
12Science, vol. 261, 1993. DOI: 10.1126/science.8346439

1pub enum Expr {
2    Constant(f64),
3    Variable(char),
4    Unary(UnaryOp, Box<Expr>),
5    Binary(BinaryOp, Box<Expr>, Box<Expr>),
6}

1#[derive(Clone, Copy)]
2pub struct UnaryOp {
3    pub func: fn(f64) -> f64,
4    pub name: &'static str,
5}

1#[derive(Clone, Copy)]
2pub struct BinaryOp {
3    pub func: fn(f64, f64) -> f64,
4    pub name: &'static str,
5}

 1const UNARY_OPS: &[UnaryOp] = &[
 2    UnaryOp {
 3        func: f64::sin,
 4        name: "sin",
 5    },
 6    UnaryOp {
 7        func: f64::cos,
 8        name: "cos",
 9    },
10];

 1const BINARY_OPS: &[BinaryOp] = &[
 2    BinaryOp {
 3        func: |a, b| a + b,
 4        name: "+",
 5    },
 6    BinaryOp {
 7        func: |a, b| a - b,
 8        name: "-",
 9    },
10    BinaryOp {
11        func: |a, b| a * b,
12        name: "*",
13    },
14    BinaryOp {
15        func: |a, b| if b.abs() < 1e-6 { 1.0 } else { a / b },
16        name: "/",
17    },
18];

 1    pub fn generate_random_expr(depth: u32) -> Expr {
 2        let mut rng = rand::thread_rng();
 3        if depth == 0 || rng.gen_bool(0.3) {
 4            if rng.gen_bool(0.5) {
 5                Expr::Constant(rng.gen_range(-5.0..5.0))
 6            } else {
 7                Expr::Variable('x')
 8            }
 9        } else {
10            let op_type: u8 = rng.gen_range(0..=2);
11            match op_type {
12                0 => {
13                    // Unary
14                    let op = UNARY_OPS.choose(&mut rng).unwrap();
15                    let operand = Box::new(generate_random_expr(depth - 1));
16                    Expr::Unary(*op, operand)
17                }
18                _ => {
19                    // Binary
20                    let op = BINARY_OPS.choose(&mut rng).unwrap();
21                    let left = Box::new(generate_random_expr(depth - 1));
22                    let right = Box::new(generate_random_expr(depth - 1));
23                    Expr::Binary(*op, left, right)
24                }
25            }
26        }
27    }

1let op = UNARY_OPS.choose(&mut rng).unwrap();
2let operand = Box::new(generate_random_expr(depth - 1));
3Expr::Unary(*op, operand)

1let op = BINARY_OPS.choose(&mut rng).unwrap();
2let left = Box::new(generate_random_expr(depth - 1));
3let right = Box::new(generate_random_expr(depth - 1));
4Expr::Binary(*op, left, right)

1箱子装起来的东西，哪怕是垃圾，都不会被丢掉……

 1    pub fn crossover(parent1: &Expr, parent2: &Expr) -> Expr {
 2        let mut rng = rand::thread_rng();
 3        let mut p1 = parent1.clone();
 4        let p2 = parent2.clone();
 5
 6        // For simplicity, we'll just swap a random subtree.
 7        // A more robust implementation would traverse the tree and pick a node.
 8        if rng.gen_bool(0.5) {
 9            if let (Expr::Binary(_, l, _), Expr::Binary(_, _, r2)) = (&mut p1, &p2) {
10                *l = r2.clone();
11            }
12        } else if let (Expr::Binary(_, _, r), Expr::Binary(_, l2, _)) = (&mut p1, &p2) {
13            *r = l2.clone();
14        }
15        p1
16    }

 1    pub fn mutate(expr: &Expr) -> Expr {
 2        let mut rng = rand::thread_rng();
 3        let mut new_expr = expr.clone();
 4
 5        if rng.gen_bool(0.2) {
 6            // 20% chance to mutate a node
 7            // Replace a random node with a new random expression
 8            let depth = rng.gen_range(1..3);
 9            return generate_random_expr(depth);
10        }
11
12        match &mut new_expr {
13            Expr::Unary(_, a) => {
14                **a = mutate(a);
15            }
16            Expr::Binary(_, l, r) => {
17                if rng.gen_bool(0.5) {
18                    **l = mutate(l);
19                } else {
20                    **r = mutate(r);
21                }
22            }
23            _ => {}
24        }
25        new_expr
26    }

 1Final best expression: (((1.00 + cos(x)) * x) + (1.00 + (x * x)))
 2Final fitness: 0.0008
 3|Binary(+)
 4|----Binary(*)
 5|--------Binary(+)
 6|------------Constant(1.00)
 7|------------Unary(cos)
 8|-------------Variable(x)
 9|--------Variable(x)
10|----Binary(+)
11|--------Constant(1.00)
12|--------Binary(*)
13|------------Variable(x)
14|------------Variable(x)