Is Simulated Annealing suitable for this minimum cost problem?

Question

Leetcode 256: Paint House

I am trying to solve the this problem with the Simulated Annealing algorithm. But the result is far away from the correct answer, which is calculated with the DP method.

e.g., I made a 10x3 costs matrix as following, the correct minimum cost is 50, but the result of Simulated Annealing is 70~90 in most cases.

Briefly speaking, I constructed an initial status(a combination of houses' colors), the color of the 1st house was Red, and Blue for the 2nd one, Green for the 3rd one, Red for the 4th one, and so on. And let's assume the cost of the this combination of colors is the minimum cost.

Under the process of annealing, I choose a house randomly firstly, changed its color, and adjusted the colors of two neighbors of this house to meet the precondition of "no two adjacent houses have the same color." Then I recalculated the cost of the new combination of colors. If the new cost is less than the minimum one, the new cost will become the minimum. Otherwise, I accepted the more expensive combination if and only if rand() <= acceptanceProbability. And I repeated these steps again and again until the temperature T is near 0.

Is the SA algorithm suitable for this problem? And if the answer is YES and there are no bugs in my code, what should I tunning, the initial combination of colors, the speed of cool down, or anything else, to make the cost calculating with SA to approach the correct one.

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

Yes, this can be done with Simulated Annealing,

I will give you a straigh forward python example, few things to notice:

• I won't suggest any invalid coloring, so only propose colorings that are valid. This way SA won't spend energy/time on fixing invalid states which are so easy to verify.
• A very easy proposal: Take 1 random house, and see if we can change the color without creating a color violation

Python code:

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) ])

And run the Annealing Scheme with

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)

It will find a minimum cost of 50.

• My start Temperature is 10**4 = 10000
• My stopping Temperature is 0.01
• My alpha is .9
• I do 100 repeats, before lowering the temperature, with factor alpha.

I hope this will help you. Check that if the proposal is not accepted, the current state is not changed.