具有随机初始解的旅行商，优化算法返回意外结果

Question

我知道旅行推销员是众所周知的，但我需要一些帮助来了解为什么我的优化算法会返回意外结果。我通过随机选择城市创建了一个初始解决方案。我还创建了一个 class，其中包含一个以距离矩阵和初始解作为参数的构造函数。优化算法非常简单；它交换两个城市并检查路线距离是否有所改善，如果有所改善，则应更新最佳解决方案。这将持续 6 次迭代。问题是，即使不满足覆盖条件，似乎最好的解决方案也会被更新和覆盖。我将添加一张显示测试结果的图片运行。

似乎变量 bestSolution 被覆盖了，但 bestDistance 没有被覆盖。我一定有某种狭隘的眼光，因为即使代码非常简单，我也无法弄清楚这个。有人可以解释为什么 bestSolution 被覆盖并返回意外结果吗？

下面的代码示例：

package RandomMethod

import GreedyHeuristic
import java.util.*

fun main(args: Array<String>) {

                                           /*A  B  C*/
    val distances = arrayOf(/*A*/ intArrayOf(0, 2, 7),
                            /*B*/ intArrayOf(2, 0, 9),
                            /*C*/ intArrayOf(7, 9, 0))

    val initalSolution = findRandomRoute(distances)

    println("Initial solution: $initalSolution")
    println("Total distance: ${findTotalDistance(distances, initalSolution)}\n")

    val optimizedSolution = GreedyHeuristic(distances, initalSolution).optimize()

    println("\nOptimized solution with Greedy Heuristic: $optimizedSolution")
    println("Total distance: ${findTotalDistance(distances, optimizedSolution)}")

}

fun areAllCitiesVisited(isCityVisited: Array<Boolean>): Boolean {

    for (visited in isCityVisited) {
        if (!visited) return false
    }
    return true
}

fun findTotalDistance(distances: Array<IntArray>, orderToBeVisited: MutableList<Int>): Int {

    var totalDistance = 0

    for (i in 0..orderToBeVisited.size - 2) {
        val fromCityIndex = orderToBeVisited.get(i)
        val toCityIndex = orderToBeVisited.get(i + 1)
        totalDistance += distances[fromCityIndex].get(toCityIndex)
    }
    return totalDistance
}

fun findRandomRoute(distances: Array<IntArray>): MutableList<Int> {
    val visitedCities: Array<Boolean> = Array(distances.size, {i -> false})

    // Find starting city index. 0 = A, 1 = B, 2 = C .... N = X
    var currentCity = Random().nextInt(distances.size)
    val orderToBeVisited: MutableList<Int> = mutableListOf(currentCity)

    visitedCities[currentCity] = true

    while (!areAllCitiesVisited(visitedCities)) {

        currentCity = Random().nextInt(distances.size)

        if (!visitedCities[currentCity]) {
            orderToBeVisited.add(currentCity)
            visitedCities[currentCity] = true
        }
    }
    return orderToBeVisited
}

和class进行优化：

import java.util.*

class GreedyHeuristic(distances: Array<IntArray>, initialSoltion: MutableList<Int>) {

    val mInitialSolution: MutableList<Int> = initialSoltion
    val mDistances: Array<IntArray> = distances

    fun optimize(): MutableList<Int> {
        var bestSolution = mInitialSolution
        var newSolution = mInitialSolution
        var bestDistance = findTotalDistance(mDistances, bestSolution)
        var i = 0

        while (i <= 5) {
            println("best distance at start of loop: $bestDistance")

            var cityIndex1 = Integer.MAX_VALUE
            var cityIndex2 = Integer.MAX_VALUE

            while (cityIndex1 == cityIndex2) {
                cityIndex1 = Random().nextInt(mInitialSolution.size)
                cityIndex2 = Random().nextInt(mInitialSolution.size)
            }

            val temp = newSolution.get(cityIndex1)
            newSolution.set(cityIndex1, newSolution.get(cityIndex2))
            newSolution.set(cityIndex2, temp)

            val newDistance: Int = findTotalDistance(mDistances, newSolution)
            println("new distance: $newDistance\n")

            if (newDistance < bestDistance) {
                println("New values gived to solution and distance")
                bestSolution = newSolution
                bestDistance = newDistance
            }
            i++
        }
        println("The distance of the best solution ${findTotalDistance(mDistances, bestSolution)}")
        return bestSolution
    }

    fun findTotalDistance(distances: Array<IntArray>, orderToBeVisited: MutableList<Int>): Int {

        var totalDistance = 0

        for (i in 0..orderToBeVisited.size - 2) {
            val fromCityIndex = orderToBeVisited.get(i)
            val toCityIndex = orderToBeVisited.get(i + 1)
            totalDistance += distances[fromCityIndex].get(toCityIndex)
        }
        return totalDistance
    }

}

Answer 1

除非您特别要求，否则 Kotlin（和一般的 JVM 语言）不会复制值。这意味着，当您这样做时：

var bestSolution = mInitialSolution
var newSolution = mInitialSolution

您没有设置 bestSolution 和 newSolution 来分隔 mInitialSolution 的副本，而是让它们指向同一个 MutableList，所以改变一个会改变另一个.也就是说：您的问题不是 bestSolution 被覆盖，而是您每次修改 newSolution.

时都会不小心修改它

然后，您可以在 while 循环的每次迭代中重复使用 newSolution，而无需创建新列表。这将我们引向两件事：

因为newSolution仍然是bestSolution的别名，修改前者也会修改后者
bestSolution = newSolution 什么都不做。

如评论中所述，解决此问题的最简单方法是战略性地使用 .toMutableList()，这将强制复制 list.You 可以通过在顶部进行此更改来实现此目的：

var bestSolution = mInitialSolution.toMutableList()
var newSolution = mInitialSolution.toMutableList()

然后在循环内：

bestSolution = newSolution.toMutableList()

顺便说一句：作为一般规则，您可能应该 return 并接受 List 而不是 MutableList 除非您特别希望它成为您的功能合同的一部分将就地改变事物。在这种特殊情况下，它会迫使你要么做一些恶心的事情（比如不安全地将 mInitialSolution 转换为 MutableList，这应该会在你的脑海中敲响各种警钟），或者复制列表（这会促使您找到正确答案）

具有随机初始解的旅行商，优化算法返回意外结果

Traveling salesman with random initial solution, optimization algorithm returning unexpected result

traveling-salesman

kotlin