寻找最小化代价函数的 n 元组

Question

假设有三个变量取离散整数值，比如w1 = {1,2,3,4,5,6,7,8,9,10,11,12}，w2 = {1 ,2,3,4,5,6,7,8,9,10,11,12}, w3 = {1,2,3,4,5,6,7,8,9,10,11, 12}。任务是从每个集合中选择一个值，使得生成的三元组最小化一些（黑匣子，计算量大）成本函数。

我已经在 Matlab 中尝试过代理优化，但我不确定它是否合适。我也听说过模拟退火，但没有发现适用于此实例的实现。

除了穷举搜索，还有什么算法可以解决这个组合优化问题？

如有任何帮助，我们将不胜感激。

Answer 1

尝试三个值的所有可能组合，看看哪个成本最低。

Answer 2

Simulated Annealing(SA)的requirement/benefit，就是objective表面有些光滑，也就是我们可以接近一个解

对于一个完全随机的尖顶表面——你不妨做一个随机搜索
如果一切顺利，甚至有时，尝试 SA 是有意义的。

想法是（有时）仅更改 3 个值中的 1 个，我们对 blackbox 函数的影响很小。

这是一个使用模拟退火的基本示例，在 Python

中使用 frigidum

import numpy as np

w1 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )
w2 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )
w3 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )

W = np.array([w1,w2,w3])

LENGTH = 12

我使用 Rastrigin 函数定义了一个黑盒。

def rastrigin_function_n( x ):
    """
        N-dimensional Rastrigin
    
        https://en.wikipedia.org/wiki/Rastrigin_function
        
        x_i is in [-5.12, 5.12]
    """
    A = 10
    n = x.shape[0]
    
    return A*n + np.sum( x**2- A*np.cos(2*np.pi * x) )
 
def black_box( x ):
    """
        Transform from domain [1,12] to [-5,5]
        to be able to push to rastrigin
    """
    x = (x - 6.5) * (5/5.5)
    
    return rastrigin_function_n(x)

模拟退火需要修改状态 X。我们跟踪索引而不是直接 taking/modifying 值。这简化了创建新提案的过程，因为索引始终是一个整数，我们可以简单地 add/subtract 1 modulo LENGTH.

def random_start():
    """
        returns 3 random indices
    """
    return np.random.randint(0, LENGTH, size=3)

def random_small_step(x):
    """
        change only 1 index
    """
    d = np.array( [1,0,0] )
    if np.random.random() < .5:
        d = np.array( [-1,0,0] )
        
    np.random.shuffle(d)
    return (x+d) % LENGTH

def random_big_step(x):
    """
        change 2 indici
    """
    d = np.array( [1,-1,0] )        
    np.random.shuffle(d)
    
    return (x+d) % LENGTH

def obj(x):
    """
        We have a triplet of indici,
        
        1. Calculate corresponding values in W = [w1,w2,w3]
        2. Push the values in out black-box function
    """
    indices = x
    values = W[np.array([0,1,2]), indices]
    
    return black_box(values)

并向其抛出一个 SA 方案

import frigidum

local_opt = frigidum.sa(random_start=random_start, 
                        neighbours=[random_small_step, random_big_step], 
                        objective_function=obj, 
                        T_start=10**4, 
                        T_stop=0.000001, 
                        repeats=10**3, 
                        copy_state=frigidum.annealing.naked)

我不确定这个函数的最小值应该是多少，但它找到了一个 objective with 47.9095 with indicis np.array([9, 2, 2])

编辑：

对于frigidum改变冷却时间表，使用alpha=.9。我的经验是，冷却方案效果最好的所有实验工作都不会超过重量，只需让它运行长一点。您提出的乘法（有时称为几何乘法）是标准乘法，也是在 frigidum 中实现的。所以要实现 Tn+1 = 0.9*Tn 你需要一个 alpha=.9。请注意，此冷却步骤是在 N 次重复后完成的，因此如果重复次数=100，它将首先进行 100 次提议，然后再以因子 alpha
降低温度
当前状态的简单变化通常效果最好。由于最好的做法是将初始温度设置得足够高以使大多数提案 (>90%) 被接受，因此步长小并不重要。但如果您担心它太小，请尝试 2 或 3 个变体。 Frigidum接受proposal functions列表，组合可以相互强制。
我没有使用 MINLP 的经验。但即便如此，那么多次实验也能让我们大吃一惊。所以如果 time/cost 是小到给 table 带来另一个竞争对手，是的！

寻找最小化代价函数的 n 元组

Finding n-tuple that minimizes expensive cost function

optimization

combinations

combinatorics