序列的通用操作

Question

我正在做这个简单的项目，我想制作一个遗传算法来为某个适应度函数找到接近最优的值。简而言之，它看起来像这样：

class Individual[T](val underlying: T, val fitnessFunc: T => Double) {
    lazy val fitness: Double = fitnessFunc(underlying)
    def update(x: T): Individual[T] = new Individual[T](x, fitnessFunc)
}

class Population[T](individuals: Seq[Individual[T]]) {
    def best: Individual[T] = individuals.tail.foldLeft(individuals.head)((b, a) => if(b.fitness > a.fitness) b else a) // not sure if this is the best way btw
}

trait GeneticAlgorithm[T] {
    def select(p: Population[T]): Individual[T]
    def crossover(i1: Individual[T], i2: Individual[T]): (Individual[T], Individual[T])
    def mutate(i: Individual[T]): Individual[T]
    def evolve(p: Population[T]): Population[T] {
        ...
    }
}

通过这种方式，我可以专门为特定类型 T 创建 GeneticAlgorithm 的实现。我现在正忙于创建一些选择、交叉和变异策略的实现。

然而，当 T 是一个序列时，我运行遇到了问题。对于这种类型，我想要一个变异策略，例如，只是一个有一定机会的随机洗牌：

object Mutation {
    def shuffleVector(p: Double): Individual[Vector[_]] => Individual[Vector[_] = (i: Individual[Vector[_]) => {
        if (math.random < p) i.update(scala.util.Random.shuffle(i.underlying)) else i
    }
}

除了它特定于 Vector 而不是任何序列这一事实之外，它编译得很好。我使用存在类型的原因是我不关心 Vector 是什么类型。

然而，当我想使用它时，我运行遇到了问题。例如，当我想优化一个整数向量时：

val ga = new GeneticAlgorithm[Vector[Int]] {
    ...
    override def mutate(i: Individual[Vector[Int]]): Individual[Vector[Int]] = Mutation.shuffleVector(0.5)(i)
    ...
}

我收到错误：Expression of type Individual[Vector[_]] doesn't conform to expected type Individual[Vector[Int]]。

除了一些其他可以解决的问题之外，解决这个问题的正确方法是什么？我怀疑它必须与 coveriancy 做一些事情，但还不确定。一直忙于学习 Scala 的方法...;-)

Answer 1

首先，不是你问的，而是...

individuals.tail.foldLeft(individuals.head)((b, a) => if(b.fitness > a.fitness) b else a)

something.tail.foldLeft(something.head)(f)等同于something.reduce(f)。

此外，您的代码片段实际上相当于 individuals.maxBy(_.fitness)

现在，要回答您的问题，解决方案很简单：只需将随机播放函数设为通用即可：

def maybeShuffle[T](p: Double, xs: Seq[T]): Seq[T] = 
  if(math.random < p) scala.util.Random.shuffle(xs) else xs

Answer 2

这实际上可能是使用下划线作为存在类型的 shorthand 实际上不会产生明显结果的情况之一。

Individual[Vector[_]]

翻译成

Individual[Vector[T]] forSome {type T}

不同于

Individual[Vector[T] forSome {type T}]

这可能就是您的想法。

我认为如果您更改方法的签名，错误就会消失。

序列的通用操作

Generic operations on sequences

collections

types

scala

covariance