极小化极大算法
Minimax算法（亦稱 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值（最小化最坏情况）的算法。 概述 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。 偽代碼 function minimax(no…
标签：#最优化算法
共 25 篇文章
群体智能
群体智能（）源于对以蚂蚁、蜜蜂等为代表的社会性昆虫的群体行为的研究。最早被用在细胞机器人系统（）的描述中。它的控制是分布式的，不存在中心控制。群体具有自组织性。 参见 协同过滤 群件和Wiki 集体行动 集体意识 集体决策 连通图 众包 控制论 全球脑 和 百猴效应 迷因 智慧圈 公开来源情报 预测市场 推荐系统 聪明行动族 社会认知优化 共识主动性 超有机体 集体智慧 * 群体的智慧
动态规划
动态规划（，简称）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量…
粒子群优化
粒子群优化（Particle Swarm Optimization, PSO），又称粒子群演算法、微粒群算法，是由 J. Kennedy 和 R. C. Eberhart 等 }}
牛顿法
牛顿法（）又称为牛顿-拉弗森方法（），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。 起源 牛顿法最初由艾萨克·牛頓在《流数法》（Method of Fluxions，1671年完成，在牛顿去世后於1736年公开发表）中提出。约瑟夫·鮑易也曾于1690年在Analysis Aequationum中提出此方法。 方法说明 首先，选择一个接近函数f(x)零点的x_0，计算相…
遗传算法
遗传算法（）是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等等。 遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色體，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应…
共轭梯度法的推导
在数值线性代数中，共轭梯度法是一种求解对称正定线性方程组 :\boldsymbol{Ax}=\boldsymbol{b} 的迭代方法。共轭梯度法可以从不同的角度推导而得，包括作为求解最优化问题的共轭方向法的特例，以及作为求解特征值问题的Arnoldi/Lanczos迭代的变种。 本条目记述这些推导方法中的重要步骤。 从共轭方向法推导 共轭梯度法可以看作是应用于二次函数最小化的共轭方向法的特例 : f(\boldsymbol{x})=\b…
量子退火
量子退火（）是一種量子漲落特性的，可以在目標函數擁有多組候選解答的情況下，找到全局最優解。量子退火主要用於解決離散空間有多個局部最小值的問題(組合優化問題)，例如尋找自旋玻璃的基態。 量子退火首先從權重相同的所有可能狀態（候選狀態）的量子疊加態開始運行，接著物理系統依含時薛丁格方程開始量子演化。根據橫向場的時間依賴強度，狀態之間產生量子穿隧，使得所有候選狀態的機率幅不斷改變，實現量子並行性。若橫向場的變化速度足夠慢，則系統會保持在接近瞬…
分支定界
分支定界（，BB）是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法，但是和穷举法所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。 该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞…
序列最小优化算法
序列最小优化算法（, SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的約翰·普拉特于1998年发明，目前被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方二次规划工具。而SMO算法较好地避免了这一问题。 问题定义 SMO算法主要用于解决支持向量机目标函数的最…
坐标下降法
坐标下降法（）是一种非梯度优化算法。算法在每次迭代中，在当前点处沿一个坐标方向进行以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系（参考）。 算法描述 坐标下降法基于的思想是多变量函数F(\mathbf{x})可以通过每次沿一个方向优化来获取最小值。与通过梯度…
维特比算法
维特比算法（）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。 维特比算法由安德鲁·维特比于1967年提出，用于在数字通信链路中解卷积以消除噪音。此算法被…
禁忌搜索
禁忌搜索（，TS，又稱禁忌搜尋法）是一種現代啟發式算法，由美國科罗拉多大学教授弗雷德·格洛弗于1986年左右提出，并于1989年实现规范化。这种搜寻法是一個用來跳脫局部最优解的搜索方法。其先创立一個初始化的方案；基于此，算法“移动”到一相邻的方案。經過許多连续的移動过程，提高解的质量。 参考文献
矩陣鏈乘積
矩阵链乘积（，或，）是可用動態規劃解决的最佳化问题。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。 因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣A、B、C和D，將可以有： ABCD = (AB)(CD) = A(BCD) = A(BC)D = ... 但括號其乘積的順序是會影響到需計算乘積所需簡單…
共轭梯度法
共轭梯度法（），是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法，它适用于系数矩阵为稀疏矩阵的线性方程组，因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。 共轭梯度法也可以用于求解无约束的最優化问题。 双共轭梯度法（）提供了一种处理非对称矩阵情况的推广。 方法的表述 设我们要求解下列线性系统 : Ax = b, 其中 n \times n…
社会认知优化
社会认知优化（Social Cognitive Optimization, SCO），又称社会认识优化算法、社会认知算法。它是一种基于社会认知理论的群体智能优化算法。 SCO算法已经被应用于非线性规划问题，布尔可满足性问题，软件可靠性分配问题，自动机制设计等。 算法 SCO算法可用于求解全局最小化问题f(x),其中x为属于问题空间S的一个问题状态（State），或称为知识点，而f为质量衡量函数。 在SCO中，由N_c个主体（Agent）…
线搜索
最优化问题中，线搜索 是一种寻找目标函数 f:\mathbb R^n\to\mathbb R 的局部最小值 \mathbf{x}^ 的近似方法。它是最基础的迭代近似方法之一，另一种是置信域方法。 线搜索近似首先找到一个使目标函数 f 下降的方向，然后计算 \mathbf{x} 应该沿着这个方向移动的步长。下降方向可以通过多种方法计算，比如梯度下降法，牛顿法和拟牛顿法。计算出的步长不一定是精确的。 应用举例 以一个梯度法作为例子，其中第四…
位元率-失真最佳化
位元率-失真最佳化（Rate–distortion optimization，簡稱RDO）是一種提升視訊壓縮效能的最佳化方法。其原理是對視訊的失真（畫面品質）與位元率（編碼所需的資料量）同時進行最佳化，以求達到一個最佳的平衡點。雖然此演算法一開始是在視訊壓縮的編碼器中被使用，但也可以用於各種多媒體編碼包含影像、視訊、音訊等等，只要編碼時會同時考慮到品質及檔案大小皆可使用。 背景 傳統視訊編碼器在做編碼決策時，是挑選出影像品質最好的畫面。…
擬牛頓法
擬牛頓法是一種以牛頓法為基礎設計的，求解非線性方程組或連續的最優化問題函數的零點或極大、極小值的算法。當牛頓法中所要求計算的雅可比矩陣或Hessian矩陣難以甚至無法計算時，擬牛頓法便可派上用場。 搜索極值 與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數f(x). f(x)的二階泰勒展開是 :f(x_k + \Delta x) \approx f(x_k) + \nabla f(x_k)^T \Delta x + \frac{1…
次梯度法
次梯度法是求解凸函数最优化（凸优化）问题的一种迭代法。次梯度法能够用于不可微的目标函数。当目标函数可微时，对于无约束问题次梯度法与梯度下降法具有同样的搜索方向。 虽然在实际的应用中，次梯度法比内点法和牛顿法慢得多，但是次梯度法可以直接应用于更广泛的问题，次梯度法只需要很少的存储需求。然而，通过将次梯度法与分解技术结合，有时能够开发出问题的简单分配算法。 基本次梯度算法 记f:\mathbb{R}^n \to \mathbb{R}为定义在…