最优化算法

之前做特征选择，实现过基于群智能算法进行最优化的搜索，看过一些群智能优化算法的论文，在此做一下总结。

在生活或者工作中存在各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。

工程设计中最优化问题（optimalization problem）的一般提法是要选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。因此，最优化问题通常可以表示为数学规划形式的问题。进行工程优化设计时，应将工程设计问题用上述形式表示成数学问题，再用最优化的方法求解。这项工作就是建立优化设计的数学模型。

最优化问题分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间的连续变量，而组合优化的对象则是解空间中的离散状态。其中典型的组合优化问题有旅行商(Traveling salesman problem,TSP)问题、加工调度问题(Scheduling problem,如Flow-shop,Job-shop)、0-1背包问题(Knapsack problem)、装箱问题(Bin packing problem)、图着色问题(Graph coloring problem)、聚类问题(Clustering problem)等。

最优化算法

根据自己对最优化的理解，采用最优化算法解决实际问题主要分为下列两步：

建立数学模型。对可行方案进行编码（变量），约束条件以及目标函数的构造。

最优值的搜索策略。在可行解（约束条件下）搜索最优解的方法，有穷举、随机和启发式搜索方法。

最优化算法有三要素：变量（Decision Variable）、约束条件（Constraints）和目标函数（Objective function）。最优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解。

优化问题相关算法有如下分类：

精确算法(绝对最优解)

精确算法包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法，其算法计算复杂性一般很大，只适合于求解小规模问题，在工程中往往不实用。

启发式算法（近似算法）

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。

领域搜索算法。从任一解出发，对其领域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性搜索法。

局部领域搜索法（也称爬山法）。以局部优化策略在当前解的领域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；接受当前邻域中的最好解作为下一当前解的最陡下降法等。

指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索，如SA、GA、EP、ES和TS等.

个体启发（寻找相对最优）

特点：每次输出的是相同的。从一个解开始，寻找最优，易陷入局部最优。

爬山算法

算法思想：从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。

其实就是，在初始值的附近，找到最大的一个。

优点

容易理解，容易实现，具有较强的通用性；

局部开发能力强，收敛速度很快

缺点

全局开发能力弱，只能搜索到局部最优解；

搜索结果完全依赖于初始解和邻域的映射关系。

禁忌算法(Tabu Search，TS)

基本思想：基于爬山算法的改进，标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局 大专栏 最优化算法——常见优化算法分类及总结部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域

特点：

避免在搜索过程中的循环

只进不退的原则,通过禁忌表实现

不以局部最优作为停止准则

邻域选优的规则模拟了人类的记忆功能

禁忌表：用于防止搜索出现循环

记录前若干步走过的点、方向或目标值，禁止返回

表是动态更新的

表的长度称为Tabu-Size

禁忌表的主要指标（两项指标）

禁忌对象：禁忌表中被禁的那些变化元素

禁忌长度：禁忌的步数

禁忌对象（三种变化）

以状态本身或者状态的变化作为禁忌对象

以状态分量以及分量的变化作为禁忌对象

采用类似的等高线做法，以目标值变化作为禁忌对象

禁忌长度:可以是一个固定的常数(T=c),也可以是动态变化的，可按照某种规则或公式在区间内变化。

禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；

禁忌长度过长，候选解全部被禁忌，造成计算时间较大，也可能造成计算无法继续下去。

参考：

禁忌搜索算法(Tabu Search)

禁忌搜索算法详解

贪婪算法

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

基本都要先排序，从排序的开始那个依次判断，符合就留下不符合就去掉。

模拟退火(simulated annealing，SA)

模拟退火算法作为局部搜索算法的扩展，在每一次修改模型的过程中，随机产生一个新的状态模型，然后以一定的概率选择邻域中能量值大的状态．这种接受新模型的方式使其成为一种全局最优算法，并得到理论证明和实际应用的验证．SA虽然在寻优能力上不容置疑，但它是以严密的退火计划为保证的，具体地讲，就是足够高的初始温度、缓慢的退火速度、大量的迭代次数及同一温度下足够的扰动次数。

用兔子的故事来说：兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。

其实就是，先用初始值进行随机更新，记录每次更新的值，最后取历史记录中最大的值。

参考：模拟退火算法

群体智能（全局最优）

类别：

粒子群算法(PSO)

蚁群算法(ACO)

人工蜂群算法(ABC)

人工鱼群算法(AFSA)

混洗蛙跳算法(SFLA)

烟花算法(FWA)

细菌觅食优化(BFO)

萤火虫算法(FA)

特点：

全局寻优

每次的解都不同

时间较长

智能计算包括：

进化算法（EC），如遗传算法。

模糊逻辑

群智能(SI)算法

人工免疫系统(AIS)

人工神经网络(ANN)

参考：

最优化问题及其分类

遗传算法

《MATLAB神经网络30个案例分析》的13个案例中的GA优化SVM参数

手把手教你实现SVM算法（一）

遗传算法学习笔记（一）：常用的选择策略

粒子群算法介绍（讲解的很清晰，将PSO的算法原理、算法特点以及参数的设置）

群体智能简介ppt（粒子群和人工蚁群优化）

优化算法分类

最优化算法——常见优化算法分类及总结的更多相关文章

常见优化算法统一框架下的实现：最速下降法，partan加速的最速下降法，共轭梯度法，牛顿法，拟牛顿法，黄金分割法，二次插值法

常见优化算法实现 这里实现的主要算法有: 一维搜索方法: 黄金分割法 二次差值法 多维搜索算法 最速下降法 partan加速的最速下降法 共轭梯度法 牛顿法 拟牛顿法 使用函数表示一个用于优化的目标, ...

一小部分机器学习算法小结: 优化算法、逻辑回归、支持向量机、决策树、集成算法、Word2Vec等

优化算法 先导知识:泰勒公式 \[ f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n \] 一阶泰勒展开: \[ f(x)\approx ...

[算法] 常见排序算法总结(C语言版)

常见排序算法总结 本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序.插入排序.归并排序.希尔排序.快速排序等.算法性能比较如下图所示: 1 冒泡排序 基本原 ...

单源最短路径问题(dijkstra算法 及其 优化算法(优先队列实现))

#define _CRT_SECURE_NO_WARNINGS /* 7 10 0 1 5 0 2 2 1 2 4 1 3 2 2 3 6 2 4 10 3 5 1 4 5 3 4 6 5 5 6 9 ...

LeetCode Linked List Cycle II 和I 通用算法和优化算法

Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cyc ...

优化算法——拟牛顿法之L-BFGS算法

一.BFGS算法 在"优化算法--拟牛顿法之BFGS算法"中,我们得到了BFGS算法的校正公式: 利用Sherman-Morrison公式可对上式进行变换,得到 令,则得到: 二. ...

深度学习剖根问底: Adam优化算法的由来

在调整模型更新权重和偏差参数的方式时,你是否考虑过哪种优化算法能使模型产生更好且更快的效果?应该用梯度下降,随机梯度下降,还是Adam方法? 这篇文章介绍了不同优化算法之间的主要区别,以及如何选择最佳 ...

基于均值坐标(Mean-Value Coordinates)的图像融合算法的优化实现

目录 1. 概述 2. 实现 2.1. 原理 2.2. 核心代码 2.3. 第二种优化 3. 结果 1. 概述 我在之前的文章<基于均值坐标(Mean-Value Coordinates)的图像 ...

机器学习算法-logistic回归算法

Logistic回归算法调试 一.算法原理 Logistic回归算法是一种优化算法,主要用用于只有两种标签的分类问题.其原理为对一些数据点用一条直线去拟合,对数据集进行划分.从广义上来讲这也是一种多元 ...

随机推荐

可能对Flutter应用程序开发有用的代码/库/专有技术列表

当我开始使用Flutter实施该应用程序时,我开始担心“如何最好地编写?”以及“如何使其更好地放置?”. 在这种情况下,您将需要参考GitHub上发布的代码和应用程​​序. 因此,我收集了似乎对Flu ...

Spring Cloud Alibaba 教程 | Nacos（六）

集群模式部署 前面我们已经学习了Nacos作为注册中心.配置中心的相关功能,但是我们之前启动Nacos是通过单实例模式启动的,只适合在学习和开发阶段,生产环境需要保证Nacos的高可用,所以今天我们来 ...

BP算法推导python实现

def sigmoid(inX): return 1.0/(1+exp(-inX)) '''标准bp算法每次更新都只针对单个样例,参数更新得很频繁sdataSet 训练数据集labels 训练 ...

Codeforces 1294C - Product of Three Numbers

题目大意: 给定一个n,问是否存在3个互不相同的,大于等于2的整数,满足a*b*c=n 解题思路: 可以把abc其中任意两个看作一个整体,例如a*b=d,那么可以发现d*c=n 所以d和c是n的因子 ...

新年在家学java之基础篇-高级类的特性

继承 extends 子类的共性代码都是继承自父类的,每个子类只要写自己特有的代码 class 子类 extends 父类 继承提高了代码的复用性,提供了多态的前提,但是不要为了某个功能去继承 子类不 ...

sftp安装（linux）

--整理于网络 1. 查看openssh版本ssh -Vopenssh版本必须大于4.8p12. 创建sftp组groupadd sftp3. 创建sftp用户useradd -g sftp -s / ...

16）PHP, set_include_path

代码展示:

第一个----关于GPIO的总结

首先,自己本来报的是单片机的 ,但是因为队友的脑残,给我报成了嵌入式,哎,惨啊,就得从头看这个云里雾里的东西,但是没办法,都报名了 不能呢个交白卷,不然自己就是逃兵了,还有20天就比赛了 我得加 ...

html 基础笔记

html 1,一套规则,浏览器认识的规则 2,开发者: 学习Html规则 开发后台程序: -写Html文件(充当模板的作用) -数据库获取数据,然后替换到html文件的指定位置(web框架) 3,本地 ...

阿里云zabbix的python脚本

由于阿里云只能用465端口.所以这个zabbix的脚本修改成了465端口的python脚本. 修改于https://www.jianshu.com/p/9d6941dabb47 #!/usr/bin/ ...