F# - 在 F# 中编写 (GA) 评估函数

Question

背景:
我目前正在 F# 中研究遗传算法 (GA)。
（我有很强的 C# 背景，现在只使用 F# 一天）

问题：
我有一个错误评估函数来确定建议的解决方案的有效性。
让我们假设一个简化的错误算法：

Calculate how may digits in the sequence are larger than their successor

我们以[1;6;3;6;8;9;5;]为例。

所以答案是 2 因为 6>3 和 9>5.

我目前的尝试：
这是一次失败的尝试，但我希望它可以作为帮助我的起点：

let proposedSolution = [1;6;3;6;8;9;5;]

for y in [0..proposedSolution.Length-2] do 
    printf "%d = (%d,%d) " y proposedSolution.[y] proposedSolution.[y+1] 
    if ( proposedSolution.[y] > proposedSolution.[y+1]) then printfn "!" else printfn "*"

结果：

val proposedSolution : int list = [1; 6; 3; 6; 8; 9; 5]

> 
0 = (1,6) *
1 = (6,3) !
2 = (3,6) *
3 = (6,8) *
4 = (8,9) *
5 = (9,5) !

所以我需要以某种方式将 * 和 ! 映射到 1 和 0 并对它们求和，但是我上面的代码可能无法实现。

问题：
我如何使用 F# 以正确的方式编写此代码？
谢谢！

Answer 1

最后我得到了解决方案：

let answer = 
    [0..proposedSolution.Length-2]
        |> List.map (fun x -> if proposedSolution.[x] > proposedSolution.[x+1] then 1 else 0)  
        |> List.sum

这样好还是可以改进？

Answer 2

您可以在列表中进行模式匹配以像这样计算：

let rec mismatchs xs =
    match xs with
    | [] | [_]  -> 0
    | (a::b::t) -> (if a > b then 1 else 0) + mismatchs (b::t)

一个小问题是，该函数不是尾递归的，因此您会遇到较大列表的问题。使其成为尾递归的常用方法是使用累加器：

let mismatchs xs =
    let rec mismatchs' xs acc =
        match xs with
        | [] | [_]  -> acc
        | (a::b::t) -> mismatchs (b::t) (if a > b then acc+1 else acc)
    mismatchs' xs 0

当然你也可以 fold:

let mismatchs xs =
    List.fold 
        (fun (last,acc) x -> 
            if last > x 
            then (x,acc+1) 
            else (x,acc)) 
        (0,0) xs
    |> snd

这里状态只记住最后看到的值以及错误的累积值。

如果你愿意，你甚至可以划分问题：首先用1标记所有问题-地方（另一个是0）：

let markProblems xs =
    xs
    |> Seq.scan 
        (fun (last, _) x -> 
            if last > x 
            then (x, 1) 
            else (x, 0)) 
        (0,0)
    |> Seq.map snd

然后 sum 他们向上：

let mismatchs xs = 
    markProblems xs
    |> Seq.sum

remark 以上两个假设，您有正整数作为输入 - 如果不是，您应该在 (0,0) 中创建第一个 0（初始state) 比任何其他可能的值都小 - 例如 (System.Int32.MinValue, 0)

在每种情况下，答案都是：

let proposedSolution = [1;6;3;6;8;9;5;]
let answer = mismatchs proposedSolution // = 2

Answer 3

由于您处理的是整数对，因此使用起来更容易 List.pairwise。然后将您的输入数据转换为整数元组列表：

proposedSolution 
    |> List.pairwise
val it : (int * int) list = [(1, 6); (6, 3); (3, 6); (6, 8); (8, 9); (9, 5)]

获得元组列表后，您可以用不同的方式计算结果。例如使用 countBy:

proposedSolution
    |> List.pairwise
    |> List.countBy (fun (a,b) -> a > b)
val it : (bool * int) list = [(false, 4); (true, 2)]

或fold得到所有匹配对：

proposedSolution
    |> List.pairwise
    |> List.fold (fun l (a,b) -> if (a>b) then (a,b)::l else l) []
val it : (int * int) list = [(9, 5); (6, 3)]

如果您正在处理大型数据集，那么您应该使用 Seq 而不是列表。例如：

let rnd = new System.Random(1234) // use fixed seed to generate same data set
#time
Seq.init 1000000 (fun _ -> rnd.Next(10))
    |> Seq.pairwise
    |> Seq.countBy (fun (a, b) -> a > b)
    |> Seq.toList   // force evalutation of sequence
val it : (bool * int) list = [(false, 550219); (true, 449780)]
Real: 00:00:00.462, CPU: 00:00:00.453, GC gen0: 38, gen1: 0, gen2: 0

Answer 4

这是一个使用窗口的解决方案。它 returns 罪魁祸首值，然后您可以轻松地将它们相加作为答案。

let values = [1;6;3;6;8;9;5]

let largerInSeq s =
  s
  |> Seq.windowed 2
  |> Seq.fold (fun acc t -> if t.[1] < t.[0] then t::acc else acc) []

values |> largerInSeq |> printfn "%A"
values |> largerInSeq |> Seq.length

[[|9; 5|]; [|6; 3|]]
val it : int = 2

F# - 在 F# 中编写 (GA) 评估函数

F# - writing an (GA) evaluation function in F#

f#