g******i
发帖数: 251 | 1 如果我要从1到100中按照某些标准找出最佳的3个的组合。一个笨笨的方法是：
1. 先随意固定两个: A, B
2. 找到最佳的 C1 和 A, B 组合
3. 让 A = B, B= C1, 然后重复第二步，找到最佳的C2
4. 这样继续下去，直到每次找到的最佳 C(i) 都和 drop 的一样。这样就找到了一组
最佳组合：A(j), B(j), C(j)
我想请教的是这样找到的是不是一定是最佳的？（好像就是问是不是完备的？）
这种方法是不是和最开始的设定有关？即是否和初始设定有关？
谢谢？（或者大牛们推荐看个什么东西也行） |
b****d
发帖数: 1311 | 2 这可以达到一个局部最佳。
简单点，按你的方法来找最佳的两个的组合。
先固定X，再变Y使得（X,Y）最佳。再变X成X1使得（X1，Y)最佳。。。
想象在XY平面上有个山地模型，其中有几个山谷。
你最终会达到其中一个谷底。
这个谷底和初始有关，未必是全局最佳。
【在 g******i 的大作中提到】
: 如果我要从1到100中按照某些标准找出最佳的3个的组合。一个笨笨的方法是：
: 1. 先随意固定两个: A, B
: 2. 找到最佳的 C1 和 A, B 组合
: 3. 让 A = B, B= C1, 然后重复第二步，找到最佳的C2
: 4. 这样继续下去，直到每次找到的最佳 C(i) 都和 drop 的一样。这样就找到了一组
: 最佳组合：A(j), B(j), C(j)
: 我想请教的是这样找到的是不是一定是最佳的？（好像就是问是不是完备的？）
: 这种方法是不是和最开始的设定有关？即是否和初始设定有关？
: 谢谢？（或者大牛们推荐看个什么东西也行）
|
g******i
发帖数: 251 | 3 谢谢，这也是我担心的。
那怎样才能找到全局的最佳呢？
【在 b****d 的大作中提到】
: 这可以达到一个局部最佳。
: 简单点，按你的方法来找最佳的两个的组合。
: 先固定X，再变Y使得（X,Y）最佳。再变X成X1使得（X1，Y)最佳。。。
: 想象在XY平面上有个山地模型，其中有几个山谷。
: 你最终会达到其中一个谷底。
: 这个谷底和初始有关，未必是全局最佳。
|
b****d
发帖数: 1311 | 4 I don't know any way other than enumeration.
【在 g******i 的大作中提到】
: 谢谢，这也是我担心的。
: 那怎样才能找到全局的最佳呢？
|
c***r
发帖数: 63 | 5 (我不做LP，但)感觉你的方法有点像simplex，它不能保证找到一般问题的global
optimum
一般的(也是非线性的)，因为没有额外的信息，要找到global optimum只能靠穷举法
为加快搜索速度，可利用问题相关的评估函数来减枝(貌似研究界有人用A-star做这个)
【在 g******i 的大作中提到】
: 谢谢，这也是我担心的。
: 那怎样才能找到全局的最佳呢？
|
A*******r
发帖数: 768 | 6 想一想simplex method如何避免循环的例子就是这个问题的一个很好的反例。局部最优
解其实在实际应用中问题不是很大。因为全局最优化的例子都是特别设计的。一般没有
那么变态。 |
a****t
发帖数: 5 | 7 这种问题用经典的优化算法容易找到局部最优，不过用演化计算可能凑效。可以看看关
于swarm的相关知识。
【在 b****d 的大作中提到】
: 这可以达到一个局部最佳。
: 简单点，按你的方法来找最佳的两个的组合。
: 先固定X，再变Y使得（X,Y）最佳。再变X成X1使得（X1，Y)最佳。。。
: 想象在XY平面上有个山地模型，其中有几个山谷。
: 你最终会达到其中一个谷底。
: 这个谷底和初始有关，未必是全局最佳。
|
D*******a
发帖数: 3688 | 8 no free lunch ya
【在 a****t 的大作中提到】
: 这种问题用经典的优化算法容易找到局部最优，不过用演化计算可能凑效。可以看看关
: 于swarm的相关知识。
|
|
a****t
发帖数: 5 | 9 "An illustration of the no-free-lunch theorem, showing the performance of a
highly specialized algorithm and a general-purpose one. Note that both
algorithms perform—on average—equally well as they are applied to
different problems." Wikipedia (2006)
"...for any [optimization] algorithm, any elevated performance over one
class of problems is exactly paid for in performance over another class."
Wolpert and Macready (1997)
Here we just apply a special algorithm to a constant problem. |
