常用算法、数据挖掘、智能优化

ANN，Artificial Neural Network，人工神经网络

SA，Simulated Annealing，模拟退火

TS，Tabu Search，禁忌搜索

PSO，Particle Swarm Optimization，粒子群优化算法

常用算法

分治法

• 递归：指子程序（函数）直接调用自己活通过一系列调用语句间接调用自已，是种描述问题和解决快问题的常用方法。

• 递归两个基本要素：

  • 边界问题：确定递归何时终止，即递归出口

  • 递归模式：大问题如何分解成小问题，即递归体

  • 示例：阶乘的定义

    

• 分治法：对于一个规模为n的问题，若该问题可以容易地解决则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解

• 步骤：分解（将原问题分解成一系列子问题）一一求解（递归地求解各子问题，若子问题足够小，则直接求解）一一合并（将子问题的解合并成原问题的解）。

• 凡是涉及到分组解决的都是分治法（二分查找、归并排序等）。

回溯法

• 回溯法：有“通用的解题法”之称，可以系统地搜素一个问题的所有解或任一解在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点触发搜索解空间树。搜索至任一结点时，总是先判断该结点是否肯定不包含问题的解，如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。

• 可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另列的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。

• 一般用于解决迷宫类的问题。

动态规划法

• 动态规划法：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

• 本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间不是相互独立的，并且不全都相同。

• 常用于求解具有某种最优性质的问题。

• 此算法会将大量精力放在前期构造表格上面，其会对每一步，列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，是通过查询这张表来得到的，动态规划法不但每一步最优，全局也最优。

贪心法

• 贪心法：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

• 局部贪心，只针对当前的步骤取最优，而非整体考虑。

• 判断此类算法，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。

经典算法题

• 背包问题：

  • 0-1背包：物品只能放进去或者不放，无法拆分。
  • 部分背包：物品可以拆分。

  

• 贪心算法：

  

其他算法

分支限界法

• 分支限界法

  • 与回溯法相似，用于在问题的解空间树上搜索问题解的算法。

• 搜索原理

  • 在分支限界法中，每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就会产生其所有儿子结点。这些儿子结点中，会舍弃导致不可行解或非最优解的儿子结点，而将其余儿子结点添加到活结点表中。接着，从活结点表中选择下一个结点作为当前扩展结点，并重复上述结点扩展过程。这一过程一直持续，直到找到所需的解或活结点表为空为止。
  • 扩展资料：
    • 活节点（Active Node）是在分支限界法（Branch and Bound）中的一个重要概念。活节点是指在问题的解空间树中，尚未被完全探索的节点，即那些可能包含问题解的节点。活节点通常是候选解的潜在来源，因此在分支限界法中，重要的工作之一是选择哪个活节点来扩展，以继续搜索解空间。
    • 在分支限界法的搜索过程中，每个活节点都有一个估计的代价或界限值（bound），用于确定是否值得继续探索该节点的子节点。如果一个活节点的界限值低于当前已知最优解的界限值，那么该节点就可以被舍弃，因为它不可能包含更优的解。只有当一个活节点的界限值有潜力比当前最优解更好时，才会继续扩展该节点，生成更多的子节点，进一步搜索解空间。
    • 因此，活节点在分支限界法中起到了筛选潜在解的作用，帮助算法朝着最优解迅速前进，减少搜索空间的规模，提高了算法的效率。活节点的管理和选择是分支限界法中的关键步骤。

• 与回溯法的区别

  1. 目标：分支限界法的目标是找到满足约束条件的解或在满足约束条件的解中找到使某一目标函数值最大或最小的解，即最优解。
  2. 搜索策略：分支限界法以广度优先或按最小耗费（最大收益）优先的方式搜索解空间树。

• 选择下一个扩展节点的类型

  • 队列式（FIFO）分支限界法：按照队列的先进先出（FIFO）原则选择下一个节点作为扩展节点。
  • 优先队列式分支限界法：根据优先队列中定义的优先级选择具有最高优先级的节点作为当前扩展节点。

概率算法

• 概率算法：在算法执行某些步骤时，可以随机地选择下一步的操作方式，允许一定的错误概率，以降低算法的复杂度，从而大幅缩短运行时间。

• 概率算法的基本特征：

  1. 对于同一问题实例，使用相同的概率算法两次可能会产生完全不同的结果。
  2. 当一个问题没有有效的确定性算法能够在合理的时间内给出解答，但可以接受小概率错误时，概率算法可以快速找到问题的解。

• 四类概率算法：

  • 数值概率算法：用于解决数值问题。
  • 蒙特卡洛算法：用于精确解问题。
  • 拉斯维加斯算法：保证不会产生不正确的解。
  • 舍伍德算法：总是能够找到问题的正确解。

• 概率算法的特点：

  1. 输入分为两部分：概率算法的输入包含原问题的输入数据和用于进行随机选择的随机数序列。

  2. 随机选择：概率算法在执行过程中会进行一次或多次的随机选择，根据随机值来决定算法的执行路径。

  3. 不确定性结果：概率算法的结果不能保证一定是正确的，但可以限制出错的概率。

  4. 不同运行结果：对于相同的输入实例，在不同的运行过程中，概率算法可以产生不同的结果，因此，相同输入实例的执行时间可能会有所不同。

近似算法

• 近似算法：解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低

• 虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解。

• 为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间的相差成都。显然，这个差别越小，近似算法越具有实用性。

• 衡量近似算法性能的两个标准：

  1. 算法的时间复杂度。近似算法的时间复杂度必须是多项式阶的，这是近似算法的基本目标。
  2. 解的近似程度。近似最优解的近似程度也是设计近似算法的重要目标。近似程度与近似算法本身、问题规模，乃至不同的输入实例有关。

数据挖掘算法

概述

• 分析爆炸式增长的各类数据的技术，以发现隐含在这些数据中的有价值的信息和知识。数据挖掘利用及其学习方法对多种数据进行分析和挖掘。其核心是算法主要功能包括分类、回归、关联规则和聚类等。

分类

• 分类：是一种有监督的学习过程，根据历史数据预测未来数据的模型

• 分类的数据对象属性：一般属性、分类属性或目标属性。

• 分类设计的数据：训练数据集、测试数据集：未知数据。

• 数据分类的两个步骤：学习模型（基于训练数据集采用分类算法建立学习模型）、应用模型（应用测试数据集的数据到学习模型中，根据输出来评估模型的好坏以及将未知数据输入到学习模型中，预测数据的类型）。

• 分类算法：决策树归纳（自顶向下的递归树算法）、朴素贝叶斯算法、后向传播BP、支持向量机SVM

频繁模式和关联规则挖掘

• 频繁模式和关联规挖掘：挖掘海量数据中的频繁模式和关联规则可以有效地指导企业发现交义销售机会、进行决策分析和商务管理等。（沃尔玛-啤酒尿布故事）

• 首先要求出数据集中的频繁模式，然后由频繁模式产生关联规则。

• 关联规则挖掘算法：类Apriori算法、基于频繁模式增长的方法如FP-growthh，使用垂直数据格式的算法，如ECLAT。

聚类

• 聚类：是一种无监督学习过程。根据数据的特征，将相似的数据对象归为一类，不相似的数据对象归到不同的类中。物以类聚，人以群分。

• 典型算法：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于统计模型的方法

• 数据挖掘的应用：信用分析、定向促销顾客的分类与聚类等。

智能优化算法

概念

• 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。

人工智能与深度学习

• 人工神经网络ANN：一个以有向图为拓扑结构的动态系统，通过对连续或断续的输入作状态响应而进行信息处理。从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络。

• 深度学习的概念源于人工神经网络的研究，是机器学习研究中的一个新的领域。

算法

• 遗传算法：源于模拟达尔文的“优胜劣汰，适者生存”的进化论和孟德尔·摩根的遗传变异理论。

  • 在迭代过程中保持已有的结构，同时寻找更好的结构。其本意是在人工适应系统中设计一种基于自然的演化机制。

• 模拟退火算法SA：求解全局优化算法。

  • 基本思想来源于物理退火过程，包括三个阶段：加温阶段、等温阶段、冷却阶段。将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

• 禁忌搜索算法TS：模拟人类智力过程的一种全局搜索算法，是对局部邻域搜索的一种扩展。\

  • 从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

• 蚁群算法：是一种用来寻找优化路径的概率型算法。

  • 单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成了一种类似正反馈的机制。这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
  • 用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

• 粒子群优化算法PSO：又称为鸟群觅食算法，在鸟群觅食飞行时，在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适宜的距离。通过对类似生物群体行为的研究，发现生物群体中存在着一种信共享机制，为群体的进化提供了一种优势，这就是基本粒子群算法形成的基础。

  • 设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在哪里，但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻离食物最近的鸟的周围区域。
  • PSO从这种模型中得到启发并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值（fitness value），每个粒子还有一个速度，决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
  • PSO初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个是粒子本身所找到的最优解，这个解叫做个体极值 pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gBest。还可以选择只使用其中一部分粒子作为粒子的邻居，那么在所有邻居中的极值就是局部极值。