模拟退火适用于这个最小成本问题吗？

Question

我正在尝试用模拟退火算法解决这个问题。但结果与正确答案相差甚远，正确答案是用DP方法计算出来的

例如，我做了一个10x3的成本矩阵如下，正确的最小成本是50，但是模拟退火的结果在大多数情况下是70~90。

简而言之，我构建了一个初始状态（房屋颜色的组合），第一个房子的颜色是红色，第二个是蓝色，第三个是绿色，第四个是红色，等等。并且假设这种颜色组合的成本是最低成本。

在退火的过程中，我先随机选择一个房子，改变它的颜色，调整这个房子的两个邻居的颜色，以满足“没有两个相邻的房子颜色相同”的前提。然后我重新计算了新颜色组合的成本。如果新成本小于最小值，则新成本将变为最小值。否则，我接受了更昂贵的组合当且仅当rand() <= acceptanceProbability。然后我一遍又一遍地重复这些步骤，直到温度 T 接近 0。

SA算法适合这个问题吗？如果答案是肯定的并且我的代码中没有错误，我应该调整什么，颜色的初始组合，冷却速度或其他任何东西，以使 SA 的成本计算接近正确的。

package main

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

const (
    RED   = iota // 0
    BLUE         // 1
    GREEN        // 2
)

var randSrc = rand.NewSource(time.Now().UnixNano())
var randGen = rand.New(randSrc)

func main() {
    var costs [][]int
    costs = append(costs, []int{10,  4, 11})
    costs = append(costs, []int{14,  4,  6})
    costs = append(costs, []int{ 2,  6,  2})
    costs = append(costs, []int{10,  5,  2})
    costs = append(costs, []int{16, 11,  2})
    costs = append(costs, []int{ 6, 16,  6})
    costs = append(costs, []int{ 6,  7,  2})
    costs = append(costs, []int{ 8, 15,  9})
    costs = append(costs, []int{ 9, 12, 11})
    costs = append(costs, []int{13, 15,  3})

    fmt.Println(minCost(costs))
}

func minCost(costs [][]int) int {
    // STEP1. init start status(a list of colors)
    rows := len(costs)
    colors := make([]int, rows, rows)

    for r := 0; r < rows; r++ {
        // suppose 1st house is RED, 2nd is BLUE, 3rd is GREEN, 4th is RED, ...
        colors[r] = (RED + r) % 3
    }

    // calculate initial cost
    cost := calcCosts(costs, colors)

    // STEP2. simulated annealing
    minCost := cost
    bestColors := colors

    for T := 5000000.0; T > 0.001; T = T * 0.99 {
        nextColors := next(bestColors)
        nextCost := calcCosts(costs, nextColors)

        if nextCost < minCost {
            minCost = nextCost
            bestColors = nextColors
        } else if randGen.Float64() <= acceptanceProbability(cost, nextCost, T) {
            minCost = nextCost
            bestColors = nextColors
        }
    }

    return minCost
}

// generates next candidate, another combination of colors
func next(colors []int) []int {
    rows := len(colors)
    nextColors := make([]int, rows, rows)
    copy(nextColors, colors)

    // chose 1 row randomly, change this row's color
    rr := randGen.Intn(rows) // rr in [0, rows)
    oc := nextColors[rr]     // old color of this row
    nc := randGen.Intn(3)    // random new color for this row
    for oc == nc {
        nc = randGen.Intn(3)
    }
    nextColors[rr] = nc

    // Adjust up-next and down-next's colors
    if rr-1 >= 0 {
        // up-next exists
        neighbourColor := nextColors[rr-1]
        for neighbourColor == nc {
            neighbourColor = randGen.Intn(3) //  [0,n)
        }
        nextColors[rr-1] = neighbourColor
    }
    if rr+1 <= rows-1 {
        // down-next exists
        neighbourColor := nextColors[rr+1]
        for neighbourColor == nc {
            neighbourColor = randGen.Intn(3) //  [0,n)
        }
        nextColors[rr+1] = neighbourColor
    }

    return nextColors
}

func calcCosts(costs [][]int, colors []int) int {
    cost := 0
    for r, row := range costs {
        cost += row[colors[r]]
    }

    return cost
}

func acceptanceProbability(cost int, nextCost int, T float64) float64 {
    if cost > nextCost {
        return 1.0
    }

    p := math.Exp(float64(cost-nextCost) / T)   // cost - next <= 0
    return p
}

Answer 1

是的，这可以通过模拟退火来完成，

我会给你一个直截了当的例子python，有几点需要注意：

我不会建议任何无效的着色，所以只建议有效的着色。这样 SA 就不会花费 energy/time 来修复很容易验证的无效状态。
一个非常简单的建议：取 1 个随机房子，看看我们能否在不造成颜色冲突的情况下改变颜色

Python代码：

import frigidum

houses = [{ 'cost' : (10,  4,11) },
        { 'cost' : (14,  4, 6) },
        { 'cost' : ( 2,  6, 2) },
        { 'cost' : (10,  5, 2) },
        { 'cost' : (16, 11, 2) },
        { 'cost' : ( 6, 16, 6) },
        { 'cost' : ( 6,  7, 2) },
        { 'cost' : ( 8, 15, 9) },
        { 'cost' : ( 9, 12,11) },
        { 'cost' : (13, 15, 3) },]


def valid_new_colors_for_house( n, color_pallet ):
    if n == 0:
        return list( set([0,1,2]) - set( [color_pallet[1], color_pallet[n]] ) )
    if n == len(color_pallet) - 1:
        return list( set([0,1,2]) - set( [color_pallet[n], color_pallet[n-1]] ) )
    
    valid_colors = list( set([0,1,2]) - set( [color_pallet[n-1],color_pallet[n],color_pallet[n+1]] ) )
    
    return valid_colors


import random

def start_state():
    return [0,1,0,1,0,1,0,1,0,1]

def swap_random_color( color_pallet ):
    random_house = random.randint(0,len(color_pallet)-1)
    
    valid_colors = valid_new_colors_for_house(random_house, color_pallet)
    
    while len(valid_colors) < 1 :
        random_house = random.randint(0,len(color_pallet)-1)
        valid_colors = valid_new_colors_for_house(random_house, color_pallet)
    
    new_color = random.choice(valid_colors)
    
    color_pallet[ random_house ] = new_color
    
    return color_pallet

def color_cost(color_pallet):
    global houses
    
    return sum([ h['cost'][p] for h,p in zip(houses,color_pallet) ])

和运行退火方案

import frigidum

import random

import frigidum

import random

local_opt = frigidum.sa(random_start=start_state, 
                        neighbours=[swap_random_color], 
                        objective_function=color_cost, 
                        T_start=10**4, 
                        T_stop=0.01, 
                        repeats=10**2,
                        alpha=.9,
                        copy_state=frigidum.annealing.copy)

它将找到最小成本 50。

我的起始温度是 10**4 = 10000
我的停止温度是 0.01
我的 alpha 是 .9
我重复 100 次，然后降低温度，使用系数 alpha。

希望对您有所帮助。检查如果提案不被接受，则当前状态没有改变。

模拟退火适用于这个最小成本问题吗？

Is Simulated Annealing suitable for this minimum cost problem?

algorithm

simulated-annealing

traveling-salesman