java - Scala 遗传算法 (GA) 库中的模拟二进制交叉 (SBX) 交叉运算符

Question

我在一个非常小的研究团队中工作，在 Scala 中创建/调整遗传算法库以使用 Scientific Worklow System 进行分布式计算，在我们的案例中，我们使用开源 OpenMole 软件 (http://www.openmole.org/)。

最近，我尝试理解并重新实现在 JMetal Metaheuristics 库 (http://jmetal.sourceforge.net/) 中编写的 SBX 交叉运算符，以使其适应我们的 Scala 库中的功能版本。

我写了一些代码，但我需要我们的建议或您对定义到 java 库中的 SBX 的验证，因为源代码 (src in svn) 似乎不等于此处编写的原始方程式:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.7291&rep=rep1&type=pdf第 30 页，附件 A

第一个问题，我不明白 JMetal 的 java 版本，为什么他们使用两个不同的 beta 值？!

• beta1 在等式中使用 min[(y1 - yL), ...] 和
的第一个参数
• beta2 使用 min [..., (yu - y2)]) 的第二个参数

Beta 1 和 2 用于计算 alpha 值和两个(所以这里和在 jmetal 中我们也有两个不同的 alpha 值 alpha1 和 2)...

同样的问题/问题，我们在 jmetal 中对 betaq(java 代码)或 Deb 方程进行了两次计算，结果为:

第二个问题，符号是什么意思？ SBX 伪算法中(2)和(3)过程中使用的，与简单beta 的区别？特别是当我们想要计算交叉 parent 的 child /后代时，就像这里一样:

编辑

• 更正 no-op if/else block

• jmetal 的代码作者给我 Nsga-II 算法原始源代码的链接，他解释说 Deb 对 SBX 的描述与他的实现不同:/

  http://www.iitk.ac.in/kangal/codes.shtml

  我不明白 jmetal 和原始源代码中的描述和实现之间的区别，你有解释吗？

• 正确的 if/else 返回 map

开始翻译成scala

  class SBXBoundedCrossover[G <: GAGenome, F <: GAGenomeFactory[G]](rate: Random => Double = _.nextDouble) extends CrossOver [G, F] {

  def this(rate: Double) = this( _ => rate)

  def crossOver (genomes : IndexedSeq [G], factory: F) (implicit aprng : Random) = {
    val g1 = genomes.random
    val g2 = genomes.random
    val crossoverRate = rate(aprng)
    val EPS =  1.0e-14
    val numberOfVariables = g1.wrappedValues.size
    val distributionIndex = 2

    val variableToMutate = (0 until g1.wrappedValues.size).map{x => !(aprng.nextDouble < 0.5)}

    //crossover probability
    val offspring = {

      if (aprng.nextDouble < crossoverRate) {      
        (variableToMutate zip (g1.wrappedValues zip g2.wrappedValues)) map {
          case (b, (g1e, g2e)) =>
            if(b) {
              if (abs(g1e - g2e) > EPS){

                val y1 = min(g1e, g2e)
                val y2 = max(g2e, g1e)

                var yL = 0.0 //g1e.getLowerBound
                var yu = 1.0 //g1e.getUpperBound  
                var rand = aprng.nextDouble   // ui

                var beta1 = 1.0 + (2.0 * (y1 - yL)/(y2 - y1))
                var alpha1 = 2.0 - pow(beta1,-(distributionIndex+1.0))
                var betaq1 = computebetaQ(alpha1,distributionIndex,rand)

                //calcul offspring 1 en utilisant betaq1, correspond au β barre
                var c1 = 0.5 * ((y1 + y2) - betaq1 * (y2 - y1)) 

                // -----------------------------------------------

                var beta2 = 1.0 + (2.0 * (yu - y2) / (y2 - y1))
                var alpha2 = 2.0 - pow(beta2, -(distributionIndex + 1.0))

                var betaq2 = computebetaQ(alpha2,distributionIndex,rand)

                //calcul offspring2 en utilisant betaq2
                var c2 = 0.5 * ((y1 + y2) + betaq2 * (y2 - y1))

                if (c1 < yL) c1 = yL
                if (c1 > yu) c1 = yu

                if (c2 < yL) c2 = yL
                if (c2 > yu) c2 = yu   

                if (aprng.nextDouble <= 0.5) {
                  (c2,c1)
                } else {
                  (c1, c2) 
                }

              }else{
                (g1e, g2e)
              }

            }else{
              (g2e, g1e)
            }
        }

      }else{
        // not so good here ...
        (g1.wrappedValues zip g2.wrappedValues)
      }
    }
    (factory.buildGenome(offspring.map{_._1}),  factory.buildGenome(offspring.map{_._2}))
  }

  def computebetaQ(alpha:Double,  distributionIndex:Double,  rand:Double):Double = { 
    if (rand <= (1.0/alpha)){
      pow ((rand * alpha),(1.0 / (distributionIndex + 1.0)))
    } else {
      pow ((1.0 / (2.0 - rand * alpha)),(1.0 / (distributionIndex + 1.0)))
    } 
  }

非常感谢您的建议，或者帮助解决这个问题。

回复

Answer 1

Reyman64，你的问题正是我一直在寻找的答案。谢谢。

我拿了你链接的论文和 Deb 的实现代码，并试图理解两者。为此，我几乎对每一行代码都进行了注释。它们仅在 beta 的计算上有所不同。

由于 Deb 在他的 NSGA-II 实现中使用了这个代码，我将坚持使用这个版本的算法。

如果有人和我有同样的情况(不了解如何实现 SBX)，我在下面的要点中留下了我的评论，看看。

https://gist.github.com/Tiagoperes/1779d5f1c89bae0cfdb87b1960bba36d