最优化理论

一、模拟退火

算法设计步骤：
1.确定解空间、初始解
2.目标函数
3.新解产生：二变换法、三变换法
4.目标函数差
5.Metropolis接受准则

二、遗传算法

遗传算法（Genetic Algorithms，简称 GA）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。
遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。
其实现方法如下： （1） 根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。
（2） 对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。
（3） 确定进化参数群体规模M、交叉概率pc、变异概率pm、进化终止条件。 为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可能根据找出近似最优是否满足精度要求来确定。

三、粒子群算法

1.每个寻优问题的解都被想象成一只鸟，称为‘粒子’，所有的粒子都在一个D维空间进行搜索。
2.所有的粒子都由一个fitness function确定适应值以判断目前位置的好坏。
3.每一个粒子都被赋予记忆功能，能记住所搜寻到的最佳位置。
4.每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据本身的飞行经验及同伴的飞行经验进行动态调整。
5.可以看出粒子群算法的基础在于 ——信息的社会共享

四、蚁群算法

找到最短路径的蚂蚁总是最早返回巢穴，从而在路上留下了较多的激素。由于最短路径上积累了较多的激素，选择这条路径的蚂蚁就会越来越多。
两个关键公式：
第一个是转移城市概率公式：

第二个公式是信息素更新公式

五、神经网络