写在前面：不建议观看，会烂尾的

1.马氏链：状态空间指的是随机变量的取值范围，xi称为一个状态，应用背景在现在的条件下下一状态发生的概率，比如退火，他的条件概率可化简为：

且n+m时刻的概率只与间隔时间m和状态i，j有关即：

这个新概率叫m步转移概率，ij当行列就有m步为变量的转移矩阵。显然遍历整个状态空间当然概率和是1

特殊的如果移动0步，规定i=j时概率是1，不相等为0

那该如何知道概率p呢？可以由过往经验如退火算法，也可以由数据规律：即找出所有的可能的状态取值，如何列出这些取值之间的跳转如00，01，10，11.通常认为步数是1，在步数是1的情况下找出所有跳转次数，然后认准是从哪里开始跳的，如果要近似00跳转的概率则找出所有从0开始跳的概率和当分母即00，01。分子是00即可。

其他还有很多定理和衍生概率，这里就不介绍了只是简单讲讲而已。应用马尔可夫链的计算方法进行马尔可夫分析， 主要目的是根据某些变量现在的情况及其变动趋向，来预测它在未来某特定区间可能产生的变动，作为提供某种决策的依据。

2.蒙特卡洛：
又称随机抽样或统计试验法，基本思想是频率代替概率，算术平均代替期望（其实就是用数据代替理论推导中未知的值，而这些未知的值往往在概率论中有公式）。

通常来讲，先从实际问题抽象出随机变量X，通过试验得到算术平均值当期望（考研时学过根据数定律数据要够大且每次都是独立同分布），后面也相应可以算出置信度和误差（降低方差和增大N都可以降低误差）。

效率概念：等于方差*观察子样花费时间

优点：受限小，收敛速度和维数无关但是慢因此高维情况使用效果好，误差容易确定但是误差确定是在给定置信度的情况下计算的

3.matlab语法：

矩阵操作：缺省y（：，：）表示取全部，前行后列，1：2：8表示第1到第8，步长2

矩阵变换：x=x（：）；默认列向量，因此要行向量得转置，拉成列向量时先第一列后第二列按列放数据

矩阵拼接：拉成列向量，矩阵操作后面加的是圆括号，矩阵给出是方括号，因此要拼接是【x y】

水平拼接用逗号或者空格都行，要增加行的话就得用；分隔。

inf为无穷大常量

4.这些优化算法核心是跳出方向的设置而不是跳出条件的判断，目前状态的领域应该怎么确定。而模拟退火的则是模拟退火通过一个预先定义的“邻域函数”，从当前解的“邻近”解中随机选择一个候选解，作为可能的“跳出方向”。 这我觉得是最关键的，这个领域是人为定义的扰动，比如在下面的TSP问题中就有一个规则。这个规则是因问题而定的，和退火系数起始问题共同影响着最后出来的结果质量。

TSP路径反转形成新解。

5.遗传算法

模拟自然界，初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体。

通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化。

需要确定种群数量，遗传代数，交叉率（一般是1），变异率。

与模拟退火不同，假如种群数量是500，那就得先给出500条路径（初始解）（TSP问题）作为父代，然后若是求最小值，则min（500个父代）这个min函数叫做适应度函数，用于评估优秀个体。

然后从里面选两个个体（解）出来划定第i个位置为交叉点，交叉点前面不懂后面交换。交叉方式多种多样这里只是一种。然后还可以跳出个别点交换位置叫做变异。

500个父代每两个凑组交换生成子代，再在子代中按照变异率选个别个体变异后生成变异体，变异体，子代，父代中按照适应度函数选出优秀种群作为新父代。

6.禁忌搜索算法

禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点

是组合优化算法的一种，组合优化：是一种大的学科类别

核心特征： 离散决策、有限解空间、目标是最小化或最大化某个目标函数。

由于上述都是用距离描述邻域，在组合优化则有一个更高层次的抽象概念邻域：

D 表示决策变量的定义域， F表示可行解区域， F 中的任何一个元素称为该问题的可行解， f 表示目标函数。

候选集合：

禁忌表：禁忌表中的两个主要指标是禁忌对象和禁忌长度，，一般是给禁忌对象x一个禁忌长度t，当迭代次数超过t次时禁忌对象x被解禁。

评价函数：评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值
来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标，但有时为了方便或易于计算，会采用其他函数来取代目标函数。

特赦规则：字面意思

记忆频率信息：一个最优值出现的频率辅助判断是否停止迭代或解禁元素

P类问题是可以找到一个能在多项式时间内解决它的算法。

NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。