1

为什么我的程序会产生越来越差的解决方案并这么早收敛？

我最近一直在阅读优化和各种元启发式技术，最近我决定尝试实施模拟退火，如本文所述。

我相信我对这个理论已经足够了解了。

存在由以下函数引导的接受概率

 math.exp(-cost_delta/temp)

其中成本增量是当前解决方案的“成本”与新随机生成的建议解决方案的成本之间的差异。成本增量越大，您的新解决方案被接受的可能性就越低，并且随着迭代次数的增加以及您的温度“冷却”并接近 0，新解决方案被接受的变化越来越小。

您的成本取决于您想要最小化或最大化的某个目标函数，并且您的目标函数将根据您的问题而改变。

我实现了帖子和维基百科中提到的模拟退火功能：

def simulated_annealing(initial_state):
current_state = initial_state
current_cost = cost_of_state(current_state)
temp = 3.0
num_iteration = 0

while current_cost > 0:
    neighbour = get_random_neighbour(current_state)
    neighbour_cost = cost_of_state(neighbour)

    cost_delta = neighbour_cost - current_cost

    if cost_delta <= 0 or random.random() < math.exp(-cost_delta/temp):
        current_state = neighbour
        current_cost = neighbour_cost

    print('current cost: '+str(current_cost))
    print('Num of iterations: '+str(num_iteration))

    num_iteration += 1
    if num_iteration % 500 == 0 and temp > 0.10:
        temp -= 0.10

return current_state, num_iteration

以及获取随机邻居的函数：

def get_random_neighbour(current_state):
neighbour = [house[:] for house in current_state]

i = random.randint(0, 4)
mRange = []
mRange.extend(range(0, i))
mRange.extend(range(i+1, 4))
j = random.choice(mRange)
#j = random.randint(0, 4)#.randint(opp1, opp2)

attr_idx = random.randint(0, 4)

neighbour[i][attr_idx] = neighbour[j][attr_idx]
neighbour[j][attr_idx] = neighbour[i][attr_idx]

return neighbour

并根据一些目标函数计算当前状态的成本：

def cost_of_state(state):
cost = 15

for i , h in enumerate(state):
    cost -= sum([
        h[nat] == 'brit' and h[col] == 'red',
        h[nat] == 'swede' and h[ani] == 'dog',
        h[nat] == 'dane' and h[bev] == 'tea',
        i< 4 and h[col] == 'green' and state[i+1][col] == 'white',
        h[col] == 'green' and h[bev] == 'coffee',
        h[cig] == 'pall mall' and h[ani] == 'bird',
        h[col] == 'yellow' and h[cig] == 'dunhill',
        i == 2 and h[bev] == 'milk',
        i == 0 and h[nat] == 'norwegian',
        h[cig] == 'blends' and ((i > 0 and state[i-1][ani] == 'cat') or (i < 4 and state[i+1][ani] == 'cat')),
        h[ani] == 'horse' and ((i > 0 and state[i-1][cig] == 'dunhill') or (i < 4 and state[i-1][cig] == 'dunhill')),
        h[cig] == 'blue master' and h[bev] == 'root beer',
        h[nat] == 'german' and h[cig] == 'prince',
        h[nat] == 'norwegian' and ((i > 0 and state[i-1][col] == 'blue') or (i < 4 and state[i+1][col] == 'blue')),
        h[cig] == 'blends' and ((i > 0 and state[i-1][bev] == 'water') or (i < 4 and state[i+1][bev] == 'water')),
    ])

return cost

以及测试/运行所有内容的代码：

nationalities = ['dane', 'brit', 'swede', 'norwegian', 'german']
colors = ['yellow', 'red', 'white', 'green', 'blue']
animals = ['horse', 'cat', 'bird', 'fish', 'dog']
beverages = ['water', 'tea', 'milk', 'coffee', 'root beer']
cigars = ['pall mall', 'prince', 'blue master', 'dunhill', 'blends']

attributes = [nationalities, colors, animals, beverages, cigars]
num_houses = 5

nat = 0
col = 1
ani = 2
bev = 3
cig = 4

initial = []

for i in range(0, num_houses):
    initial.append([attr[i] for attr in attributes])

random.seed(100)

solution, iterations = simulated_annealing(initial)

for house in solution:
    print(house)

print('Number of iterations:', iterations)

现在，我的问题是，当我运行所有程序时，当我实际运行我的程序时，我只看到一些状态变化。下面你可以看到我从前 10 次迭代中得到的输出。

current cost: 11
Num of iterations: 0
current cost: 11
Num of iterations: 1
current cost: 11
Num of iterations: 2
current cost: 10
Num of iterations: 3
current cost: 10
Num of iterations: 4
current cost: 10
Num of iterations: 5
current cost: 10
Num of iterations: 6
current cost: 11
Num of iterations: 7
current cost: 11
Num of iterations: 8
current cost: 11
Num of iterations: 9
current cost: 11
Num of iterations: 10
current cost: 11

到第 65 次迭代时，我的解决方案实际上变得更糟，事情似乎停滞不前：

urrent cost: 12
Num of iterations: 63
current cost: 12
Num of iterations: 64
current cost: 13
Num of iterations: 65
current cost: 13
4

0 回答 0