如何优化涉及 max 的函数

Question

我在最小化一个简单但略有特殊的功能时遇到问题。我有 scipy.optimize.minimize 但无法获得一致的结果。这是完整的代码：

from math import log, exp, sqrt
from bisect import bisect_left
from scipy.optimize import minimize
from scipy.optimize import Bounds
import numpy as np


def new_inflection(x0, x1):
    return log((exp(x0)+exp(x1) + sqrt(exp(2*x0)+6*exp(x0+x1)+exp(2*x1)))/2)


def make_pairs(points):
    new_points = []
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            new_point = new_inflection(points[i], points[j])
            new_points.append(new_point)
    return new_points


def find_closest_number(numbers, query):
    index = bisect_left(numbers, query)
    if index == 0:
        return numbers[0]
    if index == len(numbers):
        return numbers[-1]
    before = numbers[index - 1]
    after = numbers[index]
    if after - query < query - before:
        return after
    else:
        return before

    
def max_distance(target_points):
    pair_points = make_pairs(target_points)
    target_points = sorted(target_points)
    dists = []
    return max(abs(point - find_closest_number(target_points, point)) for point in pair_points)



num_points = 20
points = np.random.rand(num_points)*10
print("Starting score:", max_distance(points))
bounds = Bounds([0]*num_points, [num_points] * num_points)
res = minimize(max_distance, points, bounds = bounds, options={'maxiter': 100}, method="SLSQP")
print([round(x,2) for x in res.x])
print(res)

每次我运行它都会得到完全不同的结果。尽管输出说是这样Optimization terminated successfully。输出示例：

 message: Optimization terminated successfully
 success: True
  status: 0
     fun: 0.4277378933292031
       x: [ 5.710e+00  1.963e+00 ...  1.479e+00  6.775e+00]
     nit: 15
     jac: [ 0.000e+00  0.000e+00 ...  0.000e+00  0.000e+00]
    nfev: 364
    njev: 15

有时我得到的结果低至 0.40，有时则高达 0.51。

有没有办法在Python中正确优化这个函数？

Answer 1

这里的问题是，您正在通过尝试同时优化 20 个变量来探索巨大的非凸搜索空间，因此常用的优化方法（例如梯度下降相关等）可能会陷入局部最小值。在您的情况下，由于您每次都从随机坐标开始，因此每次都会以不同的局部最小值结束。

如果问题没有解析解，就没有优化器（至少我知道）可以解决这类问题并保证你处于全局最小值，但这并不意味着我们可以获得很好的结果近似值。

方法一

尝试更适合非凸高维空间优化的不同类型的算法，在 scipy 中，您有一个全局优化器函数：

from scipy import optimize
optimize.shgo(eggholder, bounds)

就我而言，这非常慢，但也许它可以帮助你。

更新：全局优化器 basshopping 似乎可以更快地给出好的结果：

from scipy.optimize import basinhopping
res = basinhopping(max_distance, points, minimizer_kwargs={"method": "SLSQP", "bounds": bounds}, niter=100)
print([round(x,2) for x in res.x])
print(res)

使用此优化器，您还可以始终达到 3.9 的适应度。

方法二

我会尝试使用pygad遗传算法，这是我的试验，它达到 3.9 的适应度并始终低于 4.1 （尽管我更改了优化器的符号）。

import pygad

def fitness_func(solution, solution_idx):
    return -max_distance(solution)

fitness_function = fitness_func

num_generations = 500
num_parents_mating = 5

sol_per_pop = 100
num_genes = len(points)

init_range_low = 0
init_range_high = 20

parent_selection_type = "sss"
keep_parents = 5

crossover_type = "single_point"

mutation_type = "random"
mutation_percent_genes = 10

ga_instance = pygad.GA(num_generations=num_generations,
                       num_parents_mating=num_parents_mating,
                       fitness_func=fitness_function,
                       sol_per_pop=sol_per_pop,
                       num_genes=num_genes,
                       gene_space = {'low': 0, 'high': 20},
                       init_range_low=init_range_low,
                       init_range_high=init_range_high,
                       parent_selection_type=parent_selection_type,
                       keep_parents=keep_parents,
                       crossover_type=crossover_type,
                       mutation_type=mutation_type,
                       mutation_percent_genes=mutation_percent_genes)

ga_instance.run()

显示解决方案：

solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("Parameters of the best solution : {solution}".format(solution=solution))
print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))
# plots the optimization process
ga_instance.plot_fitness(title="PyGAD with Adaptive Mutation")

方法三

可能是最糟糕的想法，但也可能是您需要的一切，只需迭代您已有的算法多次，使用不同的初始条件保存最佳解决方案。

更新正如OP评论的那样，与此有点相似的是算法bashopping正在做的事情（稍微复杂一点），但它归档了非常好的结果，请参阅方法一。

结论

在像这样的问题中，要使优化算法获得一致的结果，你几乎无能为力（如果不修复种子，我强烈反对），但至少你可以选择一种更适合任务最大化的算法搜索空间，因此您越来越接近全局最小值。

另一方面，您应该注意到，可能存在具有相同适应度的多个/无限解决方案，但看起来可能非常不同，特别是如果问题中存在隐藏的对称性，例如这个问题在排列下似乎不变，因此它会使感觉对解决方案列表进行排序。同样，在这种情况下，20 个数字中的一个元素的微小变化并不一定会改变适应度。