英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
启发式、经验法则和80/20命题
by Yu-Chi Ho1应用科学
哈佛大学
毫不夸张地说，现实世界充满了复杂的决策和优化问题我们无法解决。虽然关于优化和决策的文献是巨大的，但是很多具体的分析结果与可能被称为基于计算的方法有关。按顺序逐次逼近一个最优(比方说，最小)的概念。基于当地信息的改进常常被“滑雪下山”的比喻所吸引。坡度、曲率和最陡的轨迹的概念。下降都需要衍生品的概念，并且是基于更多或更多的存在不平滑的响应面。有多种可行的第一阶和二阶算法对任意多维度的最优(最小)的迭代确定方向响应或性能的表面。
实际决策问题引入了约束和不确定性的附加困难。在优化对于等式或不等式约束，有两个问题。首先,我们有将改进的方向投射到有效的约束上的问题。问题是找到一个既改进又可行的方向。其次,当有许多限制，我们必须有有效的簿记以跟踪有效和。无效的约束以及它们如何随着优化的进行而改变角色。旋转步骤线性规划的单纯形法是一个突出的例子。最近,我们提倡非线性转换作为避免处理不平等的一种手段。约束直接导致了一系列的内部点方法Fabusovich 1992，在非线性等式定义的某些流形上的梯度方法约束。过去几十年的数学编程文献都在研究这些广泛的问题。
不确定性的存在带来了额外的计算负担。通常一个人不能明确地和/或分析地排除噪音或不确定性。因此有一个问题对优化变量的任意选择的平均性能值进行估计。最小化估计误差，收紧估计的置信区间，以及概率收敛到真正的最优是关键问题。仿真领域为a。在工程设计中处理此类估计问题的特殊统计分支。离散事件动态系统的仿真是研究的一个重要课题。
最后，计算方法的性质，当然限制了我们相对的optima。全球结果可以通过假设(例如，响应面为凸或由多个开始点(希望没有太多相对的optima权衡是多少。一个人愿意承担，并且通过本地来确定全局最优的概率迭代计划。
然而，上述言论不应被视为贬低计算的方法。因为熟悉，我们经常忘记了微积分的真正力量。一种声明如导数f(x)equiv;x2 f(x)equiv;(1/2)x代表信息的整个范围变量-infin;lt; x lt;infin;。它表示在稠密集上的并行计算。在这个意义上，是电流。狂怒涉及大规模并行计算机只开始近似于单个变量的计算在一个小的有限非密集集合的变量的范围。看问题另一种方式。当微积分变得不适用时会发生什么呢?例子比比皆是:在信号处理噪声下的两个相邻频率的识别(一个非常的问题)。大量的相对优化问题，最大限度地减少调度延迟的组合问题。生产(无微积分和np困难)，离散参数设计问题在计算机通信。系统(巨大的选择空间)和每天复杂的决策。职业、家庭、金融等问题，我们所有人都面临着巨大、离散和非参数的问题选择。从理论上讲，我们知道这些问题大部分都属于。NP-complete的复杂度类别，即高效的算法是非常不可能的。将会找到这些任意尺寸问题的解决方案。如果我们把微积分看成是一种能力。在稠密集上并行计算，几乎任何优化问题都是不足为奇的。当微积分不再适用时“很难”。
在这一连串的np完全问题上，在实践中我们面临的时间有限。决策、有限的计算预算和有限的分析能力。这往往迫使我们诉诸启发式、经验法则和其他一些特别的方法，如直觉或直觉帮助我们做出决定。这里的想法是放弃本地信息。因为微积分是不适用的，或者因为它是无用的。相反类似的比喻是“to”鸟瞰地形。第一步总是随机地评估一组。可能的候选人在整个搜索空间，然后使用获得的全球信息。在下一步中细化搜索。如果任何一个都是全球性的，那么这个迭代就是我们表示人工智能方法、遗传算法、模拟退火、启发式等随机化策略。基于搜索methodologies3。
此外，一些研究人员还认为复杂的决策问题是存在的。从根本上说，不能以传统的方式进行分析[Dreyfus amp; Dreyfus 1989, Zadeh]。为了应对这种复杂局面，必须制定不同的知识基础问题。最后我们还应该注意到到目前为止，我们只限制了我们的讨论集中(或一个人)优化问题。一分钟以上的决策者是涉及到我们进入了博弈论、分权和信息复杂性的领域。这似乎带来了额外的难以克服的困难[欧文1969，荷-楚1974]。
另一方面我们可以认为，在平衡的问题上我们仍然设法应付。这些复杂的问题似乎不符合量化和启发式、直觉和规则或多或少是成功的最后手段，虽然不一定是最优的方法。事实上他们的持续存在和使用可以作为他们的证据内在的效用。这条注释试图解释为什么amp;从什么意义上说成功的。
例如，我们有200个有序的替代方案来评估。我们盲目地选择12从这200个选项中选出一个，然后问' 12个选中的概率是多少'替代方案实际上至少有一种选择在前12名中?令人吃惊的答案是0.5或one-half4。如果数字12变为35那么找到一个“好”的概率在上述声明中有一种替代方法[Ho-Sreenivas-Vakili 1992]。言外之意以上的事实是:上述的中心思想是顺序优化。在Ho-Sreenivas-Vakili(1992)我们第一次提出的观点是，相对顺序(而不是基数)。在一般决策问题中，各种替代方案的性能是相当健壮的。估算噪音。在估计的顶级替代方案中，真正的顶级替代方案的数量。即使在很大的估计误差的情况下，性能值也会相当可观吗?的替代方案。在上述随机选择的例子中，等价的。估计噪声有无限的方差。如果另一方面方差不是无限的，也就是是否有一些偏向于实际的好的选择而不是轻微的，那么我们只能改进?
缩小搜索范围的可能性和帮助。这就是我们的概率论证的要点。在复杂的决策问题中，启发式等的效用。它并不是说启发式总是有效的。在一个给定的情况;它不能免除我们寻找好的启发式;它没有向我们保证全球最佳;但它确实说，知识有助于平均，而一个人没有进行彻底的搜索以找到好的替代方案。从“满意”与“优化”的观点来看，这样的结果往往是足够的[Simon 1955]让我们更具体一点。
假设我们考虑的N个选项是线性有序的从1,2，. .N和1最优。然而我们只能通过i.i.d.统一地观察到真实的表现分布式(0 W)噪音,即。，观察到的最佳选择可能并不是真正的最佳选择观测噪声。我们考虑在最上面的g，也就是。，1,2，hellip;g是令人满意。现在，我们在观察到的性能的最高r/N%的范围内进行选择。一个问题:这个减少的子集r/N，至少包含d/g %的概率是多少?令人满意的选择呢?
如果我们能证明这个概率对于r/N的合理值是有意义的。在高W/N下的d/g，可以找到一个合理的、定量的理论依据。启发式和其他近似法则。为了得到一些有意义的见解问题，我们固定r/N, 20%， g=10，并绘制(通过蛮力模拟)概率为a。噪声对信号比的函数，W/N，由不同的d值参数化，显示出来。在图1中，N= 1000。值得注意的是，即使噪声信号比2大，概率也是一样高。0.7的前10个选项中有40%将被包含在减少的子集中。的概率如果我们只要求10%的前10个备选方案被包含，那么就可以提高到基本确定性。换句话说，在相当大的噪声下(W/N=2)减少5倍的选择集(r/N =0.2)不影响找到一个好的选择的机会。类似的结果也可以得到N的值。
我们可以得出的结论是:假设我们同时评估一大堆备选方案。大约并按照这个近似的估计来排序。然后，我们很有可能找到真正的好替代品。我们把自己限定在观察到的最佳选择的前r/N%。
把这作为启发式和其他近似值使用的理由似乎是合理的。可供选择的经验法则。换句话说，如果我们使用一些经验法则。启发式比盲选择好，我们必须能够取得与图1相似的结果。在特别地，我们提出一个可能基于启发式推理的决策规则。随机化简单地定义了在许多情况下选择另一种选择的概率。如果我们能根据图2所示的一些参数，对决策规则的“良”进行参数化。然后我们可以利用启发式规则来研究选择一个好的子集的概率。特别是,我们可以研究出，在所有可能的设计中，有多少设计应该使用这样的设计。确保挑选一个好的设计或决定的规则。如果这一减少的选择子集将会受到更详细的解释，这一点尤其正确。准确的分析，例如更详细的模拟，应用遗传算法[Goldberg]1989等。
我们提出了许多尝试和真实的方法来解释我们如何处理复杂性基础上,例如,
1。80/20规则的许多化身，例如，20%的努力得到80%的结果。结果，80%的资金是在项目持续时间的前20%进行的，最后的20%总是最难的。地球上80%的土地被20%的土地所控制。soveriegn国家80%的时间只需要访问20%的数据库。
2。将一个大问题分解为一组较小的可管理大小的问题。考虑到每个子集的优点是缩小搜索范围的可行方法。选择，例如常青藤联盟大学常用的录取程序。
3所示。启发式方法通常只对一小部分替代方案进行评估。许多可能的替代品。但是如果这些方法是好的，你很可能会来好的决策。
4所示。对optima的追求略有放松，使np硬度在许多地方消失。组合优化问题[Rabin, Karp 1976]
事实上，如果我们从这个小练习中推断，我们注意到成功的成分。启发式通常取决于我们在上述讨论中涉及到的三个特征:
- 垂直结构相对较少。这些想法很容易理解。顺序优化当然很容易理解和实现。然而,它是通用的和完全通用。
- 硬件的进步使实际的实现和计算成为可能。评估一组替代方案可以非常有效地并行执行电脑，因为我们通常处理的是参数不同但结构相似模型或功能。这是SIMD机器或SPMD计算的理想设置环境[Vakili-Mollamustaflaglu-Ho 1992]。
(iii)提出一个更温和的问题——满意与优化。
我们规定，在顶部g组的任何东西都是令人满意的。我们不坚持寻找最优与统计文献中的排名和选择有关[Santner-Tamhane 1984]。这使得置信概率高到足够有趣和有用。
我们也注意到其他当前流行的主题，如模糊控制，神经网络、人工智能和软计算有着相似的特性。
结论
在本文中，我们提供了一个视角，为优化研究指明了一个新的方向。提供了在决策中使用启发式的基本原理。我们认为询问a是值得的更软的问题在很大的一类复杂问题中。然而我们并不提倡。许可证的草率和停止寻找好的启发式。的确我们的意图是指向量化启发式的可能性。
参考文献
bull; Dreyfus, H amp; Dreyfus, S. Mind over Machine: the Role of Human Intuition and Expertise in the Era of computers, Free Press 1989,
bull; Faybusovich, L. “Dynamical Systems That Solve Linear Programming Problems” Proc. of the IEEE Conference on Decision and Control, Tucson AZ, Dec. 1992
bull; Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning, AddisonWesley 1989
bull; Ho, Y.C. and Chu, K.C. “Information Structure in Dynamic Multi-person Control Problems” Automatica, 10, 341-351 (1974)
bull; Ho, Y.C., Sreenivas, R., Vakili, P., “Ordinal optimization in DEDS” , J. of DEDS, 2, #1, 1992, 61-88
bull; Karmarker, N. “A New Polynominal time Algorithm for Linear Programming” Combinatorica, 4, 373-395, 1984
bull; Karp, R., “Probabilistic Algorithms in Combinatorial Search Problems”, in Algorithms and Complexity: New Directions and Recent Results, J. Traub (Ed) Academic Press 1976, 1-20
bull; G. Owen, Game Theory, Saunders 1969
bull; Rabin, M. “Probabilistic Algorithms” in Algorithms and Complexity: New Directions and Recent Results, J. Traub (Ed) Academic Press 1976, 21-40
bull; Santner, T.J., and Tamhane, A.C., Design of Experiments: Ranking and Selection, M. Dekker (1984).
bull; Simon, H. “A Behavior Model of Rational Choice” Q.J. of Economics , 59, 99-118, 1955
bull; Vakili, P., Mollamustaflaglu, L, Ho, Y.C. “Massively Parallel Simulation of a Class Of discrete Event Systems” Proc. of IEEE Frontiers of MPC lsquo;92 Symposium, Washington DC 1992
bull; Zadeh, L. “Fuzzy Sets as a Basis for a Theory of Possibility”, Fu
全文共5876字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11843]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
