8

我正在尝试在 Python 中找到以下方程组的最佳解决方案：

(x-x1)^2 + (y-y1)^2 - r1^2 = 0
(x-x2)^2 + (y-y2)^2 - r2^2 = 0
(x-x3)^2 + (y-y3)^2 - r3^2 = 0

给定点 (x,y) 和半径 (r) 的值：

x1, y1, r1 = (0, 0, 0.88)
x2, y2, r2 = (2, 0, 1)
x3, y3, r3 = (0, 2, 0.75)

找到点 (x,y) 的最佳解决方案的最佳方法是什么使用上面的示例，它将是：
~ (1, 1)

4

4 回答 4

15

如果我正确理解您的问题，我认为这就是您所追求的：

from scipy.optimize import minimize
import numpy as np

def f(coord,x,y,r):
    return np.sum( ((coord[0] - x)**2) + ((coord[1] - y)**2) - (r**2) )

x = np.array([0,   2,  0])
y = np.array([0,   0,  2])
r = np.array([.88, 1, .75])

# initial (bad) guess at (x,y) values
initial_guess = np.array([100,100])

res = minimize(f,initial_guess,args = [x,y,r])

产生：

>>> print res.x
[ 0.66666666  0.66666666]

您也可以尝试最小二乘法，它需要一个返回向量的目标函数。它想要最小化这个向量的平方和。使用最小二乘法，您的目标函数将如下所示：

def f2(coord,args):
    x,y,r = args
    # notice that we're returning a vector of dimension 3
    return ((coord[0]-x)**2) + ((coord[1] - y)**2) - (r**2)

你会像这样最小化它：

from scipy.optimize import leastsq
res = leastsq(f2,initial_guess,args = [x,y,r])

产生：

>>> print res[0]
>>> [ 0.77961518  0.85811473]

这与使用minimize和重写原始目标函数基本相同：

def f(coord,x,y,r):
    vec = ((coord[0]-x)**2) + ((coord[1] - y)**2) - (r**2)
    # return the sum of the squares of the vector
    return np.sum(vec**2)

这产生：

>>> print res.x
>>> [ 0.77958326  0.8580965 ]

请注意，args与 的处理方式略有不同leastsq，并且两个函数返回的数据结构也不同。scipy.optimize.minimize有关详细信息，请参阅文档scipy.optimize.leastsq。

有关更多优化选项，请参阅scipy.optimize文档。

于 2012-10-17T20:55:29.957 回答
5

我注意到接受的解决方案中的代码不再起作用......我认为scipy.optimize自从发布答案以来可能已经改变了它的界面。我可能是错的。无论如何，我支持使用算法的建议scipy.optimize，并且接受的答案确实展示了如何（或者如果界面发生了变化，则曾经做过）。

我在这里添加了一个额外的答案，纯粹是为了建议一个使用scipy.optimize核心算法的替代包，但对于约束优化来说更加健壮。包是mystic. 其中一项重大改进是mystic提供了受限的全局优化。

首先，这是您的示例，与方式非常相似scipy.optimize.minimize，但使用了全局优化器。

from mystic import reduced

@reduced(lambda x,y: abs(x)+abs(y)) #choice changes answer
def objective(x, a, b, c):
  x,y = x
  eqns = (\
    (x - a[0])**2 + (y - b[0])**2 - c[0]**2,
    (x - a[1])**2 + (y - b[1])**2 - c[1]**2,
    (x - a[2])**2 + (y - b[2])**2 - c[2]**2)
  return eqns

bounds = [(None,None),(None,None)] #unnecessary

a = (0,2,0)
b = (0,0,2)
c = (.88,1,.75)
args = a,b,c

from mystic.solvers import diffev2
from mystic.monitors import VerboseMonitor
mon = VerboseMonitor(10)

result = diffev2(objective, args=args, x0=bounds, bounds=bounds, npop=40, \ 
                 ftol=1e-8, disp=False, full_output=True, itermon=mon)

print result[0]
print result[1]

结果如下所示：

Generation 0 has Chi-Squared: 38868.949133
Generation 10 has Chi-Squared: 2777.470642
Generation 20 has Chi-Squared: 12.808055
Generation 30 has Chi-Squared: 3.764840
Generation 40 has Chi-Squared: 2.996441
Generation 50 has Chi-Squared: 2.996441
Generation 60 has Chi-Squared: 2.996440
Generation 70 has Chi-Squared: 2.996433
Generation 80 has Chi-Squared: 2.996433
Generation 90 has Chi-Squared: 2.996433
STOP("VTRChangeOverGeneration with {'gtol': 1e-06, 'target': 0.0, 'generations': 30, 'ftol': 1e-08}")
[ 0.66667151  0.66666422]
2.99643333334

如前所述，in 的选择lambda会reduced影响优化器找到的点，因为方程没有实际的解。

mystic还提供将符号方程转换为函数的能力，其中生成的函数可以用作目标或惩罚函数。这是同样的问题，但使用方程作为惩罚而不是目标。

def objective(x):
    return 0.0

equations = """
(x0 - 0)**2 + (x1 - 0)**2 - .88**2 == 0
(x0 - 2)**2 + (x1 - 0)**2 - 1**2 == 0
(x0 - 0)**2 + (x1 - 2)**2 - .75**2 == 0
"""

bounds = [(None,None),(None,None)] #unnecessary

from mystic.symbolic import generate_penalty, generate_conditions
from mystic.solvers import diffev2

pf = generate_penalty(generate_conditions(equations), k=1e12)

result = diffev2(objective, x0=bounds, bounds=bounds, penalty=pf, \
                 npop=40, gtol=50, disp=False, full_output=True)

print result[0]
print result[1]

结果：

[ 0.77958328  0.8580965 ]
3.6473132399e+12

结果与以前不同，因为应用的惩罚与我们之前应用的不同reduced。在mystic中，您可以选择要应用的惩罚。

有人指出，方程没有解。您可以从上面的结果中看到，结果受到了严重的惩罚，因此这很好地表明了没有解决方案。但是，mystic有另一种方法可以在没有解决方案的情况下看到。而不是应用一个更传统的penalty，它惩罚违反约束的解决方案......mystic提供了一个constraint，它本质上是一个内核转换，它删除了所有不满足常量的潜在解决方案。

def objective(x):
    return 0.0

equations = """
(x0 - 0)**2 + (x1 - 0)**2 - .88**2 == 0
(x0 - 2)**2 + (x1 - 0)**2 - 1**2 == 0
(x0 - 0)**2 + (x1 - 2)**2 - .75**2 == 0
"""

bounds = [(None,None),(None,None)] #unnecessary

from mystic.symbolic import generate_constraint, generate_solvers, simplify
from mystic.symbolic import generate_penalty, generate_conditions    
from mystic.solvers import diffev2

cf = generate_constraint(generate_solvers(simplify(equations)))

result = diffev2(objective, x0=bounds, bounds=bounds, \
                 constraints=cf, \
                 npop=40, gtol=50, disp=False, full_output=True)

print result[0]
print result[1]

结果：

[          nan  657.17740835]
0.0

本质nan上表明没有有效的解决方案。

仅供参考，我是作者，所以我有一些偏见。但是，mystic它的存在时间几乎与scipy.optimize. 关键是，如果您需要一个更灵活、更强大的约束非线性优化器，我建议mystic.

于 2017-04-02T20:23:19.100 回答
1

这些方程可以看作是描述二维空间中三个圆圆周上的所有点。解决方案将是圆圈截取的点。

它们的圆的半径之和小于它们的中心之间的距离，所以圆不重叠。我在下面绘制了圆圈以按比例缩放： 几何解

没有满足这个方程组的点。

于 2012-10-17T21:30:04.147 回答
0

我通过以下方式制作了一个示例脚本。请注意，最后一行将找到最佳解决方案 (a,b)：

import numpy as np
import scipy as scp
import sympy as smp
from scipy.optimize import minimize

a,b = smp.symbols('a b')
x_ar, y_ar = np.random.random(3), np.random.random(3)
x = np.array(smp.symbols('x0:%d'%np.shape(x_ar)[0]))
y = np.array(smp.symbols('y0:%d'%np.shape(x_ar)[0]))
func = np.sum(a**2+b**2-x*(a+b)+2*y)
print func
my_func = smp.lambdify((x,y), func)
print 1.0/3*my_func(x_ar,y_ar)
ab = smp.lambdify((a,b),my_func(x_ar,x_ar))
print ab(1,2)

def ab_v(x):
   return ab(*tuple(x))

print ab_v((1,2))

minimize(ab_v,(0.1,0.1))

输出是：

3*a**2 + 3*b**2 - x0*(a + b) - x1*(a + b) - x2*(a + b) + 2*y0 + 2*y1 + 2*y2
1.0*a**2 - 0.739792011558683*a + 1.0*b**2 - 0.739792011558683*b    +0.67394435712335


12.7806239653
12.7806239653
Out[33]:
  status: 0
 success: True
 njev: 3
 nfev: 12
 hess_inv: array([[1, 0],
   [0, 1]])
 fun: 3.6178137388030356
 x: array([ 0.36989601,  0.36989601])
 message: 'Optimization terminated successfully.'
 jac: array([  5.96046448e-08,   5.96046448e-08])
于 2016-05-26T07:30:16.910 回答