我正在尝试使用 Scala 以不可变的方式对 NSGA2 中使用的 Deb 的快速非支配排序算法 (NDS) 进行编码。
但问题似乎比我想象的要困难，所以我在这里简化了问题以制作 MWE。
想象一下人口 Seq[A] , 和每个 A元素是 decoratedA带有一个包含指向群体中其他元素的指针的列表 Seq[A] .
一个函数evalA(a:decoratedA)取列表linkedA它包含和递减每个值。
接下来我取一个子集列表 decoratedAPopulation人口A，并调用evalA在各个。我有一个问题，因为在此子集列表中的元素的每次迭代之间 decoratedAPopulation ，我需要更新我的人口 A与新 decoratedA和新的更新 linkedA它包含...
更成问题的是，如果链接元素发生变化，人口中的每个元素都需要更新“linkedA”以替换链接元素......
嗯，如您所见，以这种方式保持所有链表同步似乎很复杂。我提出了另一个解决方案底部，它可能需要在每个 EvalA 之后递归返回替换元素的新种群。
我怎样才能以不变的方式正确地做到这一点？
以可变的方式编写代码很容易，但我没有找到以不可变的方式执行此操作的好方法，您有这样做的方法或想法吗？
object test extends App{
case class A(value:Int) {def decrement()= new A(value - 1)}
case class decoratedA(oneAdecorated:A, listOfLinkedA:Seq[A])
// We start algorithm loop with A element with value = 0
val population = Seq(new A(0), new A(0), new A(8), new A(1))
val decoratedApopulation = Seq(new decoratedA(population(1),Seq(population(2),population(3))),
new decoratedA(population(2),Seq(population(1),population(3))))
def evalA(a:decoratedA) = {
val newListOfLinked = a.listOfLinkedA.map{e => e.decrement()
new decoratedA(a.oneAdecorated,newListOfLinked)}
}
def run()= {
//decoratedApopulation.map{
// ?
//}
}
}
更新 1:
关于初始算法的输入/输出。
Deb算法的第一部分(步骤1到步骤3)分析一个Individual列表，并计算每个A:(a)支配计数，支配我的A的数量(A 的
value 属性)(b)A 的列表(listOfLinkedA)。所以它返回
decoratedA 的人口完全初始化，对于第 4 步(我的问题)的入口，我采用第一个非支配前沿，参见。 decoratedA 的元素子集与 A值 = 0。我的问题从这里开始，列表为
decoratedA与 A值 = 0;我通过计算每个 listOfLinkedA 在这个列表中搜索下一个前面每一个 A 在第 4 步到第 6 步之间的每次迭代中，我需要计算一个新的
B decoratedA的子集列表与 A value = 0。对于 each ，我首先将每个元素的支配计数属性递减为 listOfLinkedA ，然后我过滤得到等于0的元素。A步骤6结束，B保存到列表List[Seq[DecoratedA]] ，然后我用 B 重新开始到第 4 步，并计算一个新的 C ， 等等。在我的代码中类似的东西，我调用
explore()对于 B 的每个元素, 与 Q最后等于 decoratedA 的新子集与 value (这里的健身)= 0:case class PopulationElement(popElement:Seq[Double]){
implicit def poptodouble():Seq[Double] = {
popElement
}
}
class SolutionElement(values: PopulationElement, fitness:Double, dominates: Seq[SolutionElement]) {
def decrement()= if (fitness == 0) this else new SolutionElement(values,fitness - 1, dominates)
def explore(Q:Seq[SolutionElement]):(SolutionElement, Seq[SolutionElement])={
// return all dominates elements with fitness - 1
val newSolutionSet = dominates.map{_.decrement()}
val filteredSolution:Seq[SolutionElement] = newSolutionSet.filter{s => s.fitness == 0.0}.diff{Q}
filteredSolution
}
}
算法结束，我有一个最终的 seq 列表
decoratedA List[Seq[DecoratedA]]其中包含我计算的所有前沿。更新 2
从该示例中提取的值示例。
我只取帕累托前沿(红色)和 {f,h,l} 下一个前沿，支配计数 = 1。
case class p(x: Int, y: Int)
val a = A(p(3.5, 1.0),0)
val b = A(p(3.0, 1.5),0)
val c = A(p(2.0, 2.0),0)
val d = A(p(1.0, 3.0),0)
val e = A(p(0.5, 4.0),0)
val f = A(p(0.5, 4.5),1)
val h = A(p(1.5, 3.5),1)
val l = A(p(4.5, 1.0),1)
case class A(XY:p, value:Int) {def decrement()= new A(XY, value - 1)}
case class ARoot(node:A, children:Seq[A])
val population = Seq(
ARoot(a,Seq(f,h,l),
ARoot(b,Seq(f,h,l)),
ARoot(c,Seq(f,h,l)),
ARoot(d,Seq(f,h,l)),
ARoot(e,Seq(f,h,l)),
ARoot(f,Nil),
ARoot(h,Nil),
ARoot(l,Nil))
算法返回
List(List(a,b,c,d,e), List(f,h,l))更新 3
2 小时后，出现了一些模式匹配问题(Ahum...)，我回来了一个完整的例子，它自动计算被支配的计数器，以及每个 ARoot 的 child 。
但我有同样的问题，我的 child 列表计算并不完全正确，因为每个元素 A 可能是另一个 ARoot child 列表的共享成员，所以我需要考虑你的答案来修改它:/此时我只计算
Seq[p] child 名单，我需要 seq[A] 的列表 case class p(x: Double, y: Double){
def toSeq():Seq[Double] = Seq(x,y)
}
case class A(XY:p, dominatedCounter:Int) {def decrement()= new A(XY, dominatedCounter - 1)}
case class ARoot(node:A, children:Seq[A])
case class ARootRaw(node:A, children:Seq[p])
object test_stackoverflow extends App {
val a = new p(3.5, 1.0)
val b = new p(3.0, 1.5)
val c = new p(2.0, 2.0)
val d = new p(1.0, 3.0)
val e = new p(0.5, 4.0)
val f = new p(0.5, 4.5)
val g = new p(1.5, 4.5)
val h = new p(1.5, 3.5)
val i = new p(2.0, 3.5)
val j = new p(2.5, 3.0)
val k = new p(3.5, 2.0)
val l = new p(4.5, 1.0)
val m = new p(4.5, 2.5)
val n = new p(4.0, 4.0)
val o = new p(3.0, 4.0)
val p = new p(5.0, 4.5)
def isStriclyDominated(p1: p, p2: p): Boolean = {
(p1.toSeq zip p2.toSeq).exists { case (g1, g2) => g1 < g2 }
}
def sortedByRank(population: Seq[p]) = {
def paretoRanking(values: Set[p]) = {
//comment from @dk14: I suppose order of values isn't matter here, otherwise use SortedSet
values.map { v1 =>
val t = (values - v1).filter(isStriclyDominated(v1, _)).toSeq
val a = new A(v1, values.size - t.size - 1)
val root = new ARootRaw(a, t)
println("Root value ", root)
root
}
}
val listOfARootRaw = paretoRanking(population.toSet)
//From @dk14: Here is convertion from Seq[p] to Seq[A]
val dominations: Map[p, Int] = listOfARootRaw.map(a => a.node.XY -> a.node.dominatedCounter) //From @dk14: It's a map with dominatedCounter for each point
val listOfARoot = listOfARootRaw.map(raw => ARoot(raw.node, raw.children.map(p => A(p, dominations.getOrElse(p, 0)))))
listOfARoot.groupBy(_.node.dominatedCounter)
}
//Get the first front, a subset of ARoot, and start the step 4
println(sortedByRank(Seq(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)).head)
}
最佳答案
谈谈你的分界线问题(更新2后):
val (left,right) = population.partition(_.node.value == 0)
List(left, right.map(_.copy(node = node.copy(value = node.value - 1))))
不需要在这里改变任何东西。
copy 将复制除您使用新值指定的字段之外的所有内容。说到代码，新的副本会链接到同一个子列表，但是新的value = value - 1 .附言我有一种感觉，你可能真的想做这样的事情:
case class A(id: String, level: Int)
val a = A("a", 1)
val b = A("b", 2)
val c = A("c", 2)
val d = A("d", 3)
clusterize(List(a,b,c,d)) === List(List(a), List(b,c), List(d))
实现很简单:
def clusterize(list: List[A]) =
list.groupBy(_.level).toList.sortBy(_._1).map(_._2)
测试:
scala> clusterize(List(A("a", 1), A("b", 2), A("c", 2), A("d", 3)))
res2: List[List[A]] = List(List(A(a,1)), List(A(b,2), A(c,2)), List(A(d,3)))
P.S.2.请考虑更好的命名约定，例如 here .
谈论一些复杂结构中的“变异”元素:
“不可变变异”一些共享(结构的部分之间)值的想法是将你的“变异”与结构分开。或者简单地说，分而治之:
编码:
case class A(v: Int)
case class AA(a: A, seq: Seq[A]) //decoratedA
def update(input: Seq[AA]) = {
//shows how to decrement each value wherever it is:
val stats = input.map(_.a).groupBy(identity).mapValues(_.size) //domination count for each A
def upd(a: A) = A(a.v - stats.getOrElse(a, 0)) //apply decrement
input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse and "update" original structure
}
所以，我引入了新的
Map[A, Int]结构，显示如何修改原始结构。此方法基于 Applicative Functor 的高度简化版本概念。一般情况下，应该是Map[A, A => A]甚至 Map[K, A => B]甚至 Map[K, Zipper[A] => B] 作为应用仿函数( input <*> map )。 *Zipper(参见 1 , 2 )实际上可以为您提供有关当前元素上下文的信息。笔记:
A具有相同值的 s 相同；这是 case classess 的默认行为，否则您需要提供一些额外的 id的(或重新定义 hashCode/equals)。 AA(AA(AA(...)))) - 只需制作 stats和 upd递归，如果递减的权重取决于嵌套级别 - 只需将嵌套级别作为参数添加到递归函数中。 A(3) 的，属于 A(3) ) - 添加父节点作为 stats 的一部分的键并在 upd 期间分析它. input(1)来自 input(0) - 你应该使用 foldLeft部分统计数据作为累加器:val stats = input.foldLeft(Map[A, Int]())((partialStats, elem) => partialStats ++ analize(partialStats, elem)) 顺便说一句，需要
O(N)此处(线性内存和 CPU 使用率)例子:
scala> val population = Seq(A(3), A(6), A(8), A(3))
population: Seq[A] = List(A(3), A(6), A(8), A(3))
scala> val input = Seq(AA(population(1),Seq(population(2),population(3))), AA(population(2),Seq(population(1),population(3))))
input: Seq[AA] = List(AA(A(6),List(A(8), A(3))), AA(A(8),List(A(6), A(3))))
scala> update(input)
res34: Seq[AA] = List(AA(A(5),List(A(7), A(3))), AA(A(7),List(A(5), A(3))))
关于list - 当您将相互链接的对象影响到此列表时如何维护不可变列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29550069/