元启发算法简单介绍

元启发算法简单介绍

概念：元启发算法是一类算法概念的集合，它可以用来定义应用于一个大范围内不同问题的各种启发式方法。换句话说，元启发算法可以看做是一种多用途的启发式算法，它用来指导潜在与问题相关的启发式方法朝着可能含有高质量解的搜索空间进行搜索。因此元启发算法是一种需要较少的修改就可以应用于不同优化问题的通用算法框架。

用途：解决复杂的组合优化问题

现存的几个算法例子：

模拟退火算法：模拟固体降温的一个算法

Simulated annealing SA

在物理上，固体在退火（降温）的过程中，在每一个温度上都会有一个比较稳定的能量状态，当用较长的时间（就是缓慢的降温）可以逐渐获得一个处于最小能量状态的晶格结构。

整个过程就是：融化固体，缓慢降温到t，固体自动的在温度t上稳定到一个能量状态，再降温固体又会稳定在一个新的能量状态上，并且这个能量状态一般会比上一个底，逐渐降温最后固体就会稳定在最小能量状态上。

算法的模拟：

1用参数T来模拟温度，s问题的初始解，f（s）表示状态，用来模拟能量状态

2由T开始降温到T1,通过一个固定的算法得到s1，

3比较f（s）与f(s1)如果f（s1）就接受s1为新解，否侧以一定的概率接受s1，如果不接受就再计算一个s1.

4此时的状态是T1,s1，在这基础上再执行2，3一样的流程

5直到T降到最低值，此时得到一个s就是理论上的最优解。

例子：

一般T是随便给出的一个值没有什么具体的意义，s是给出的组合优化的解空间中的随便的一个值，f（s）函数是用来衡量s对应的目标值，从s计算得到s1根据问题的不同适当的选择，

接受概率：P（s，s1，T）=1     ，f（s1） 

          P（s，s1，T）=   ，f（s1）>f(s)

 

 

进化计算：模拟生物种群优胜劣汰的一个算法

生成初始种群          （从解空间中随便的选出n个个体）

计算个体的适应值       （模拟的是适者生存）

返回当前最好的个体     （适应的个体） 

重复合并两个或大多个体形成一个或多个新的个体   （模拟繁殖）

对个体引入一个随机变动         （模拟变异）

从当前种群得到一个新的种群      （进化的结果数量是n）

判断种群中是否有满足期望的个体，如果寻在就结束

否侧反复执行上述过程得到一个优秀的种群从中得到最好的个体

蚁群优化：模拟蚂蚁协作完成最短路径的一个算法

蚂蚁是简单的生物，众多蚂蚁组成一个社群，这些蚂蚁之间通过信息素进行情报传递，信息素反应了环境的状况，蚂蚁会对这种信息进行正反馈，从而使得蚁群对环境做出正确的反应。

蚂蚁算法的应用非常广泛，而且产生了很多扩展的复杂的蚂蚁算法。

一般的算法：

蚂蚁优化可以看成是以下三个过程的相互作用：

蚂蚁构建解：通过使蚂蚁移动到相应的构建图上的临近点，从而使一群蚂蚁并行异步的访问所考虑的问题的临近状态。蚂蚁根据信息素和启发式信息，采用一个随机局部决策方法选择移动下一步。这样蚂蚁就可以逐步的建立起优化的解。一但一个蚂蚁建立了一个解，或是在构建的期间，蚂蚁将对（部分）解进行评估，以便在信息素更新阶段使用该部分解来确定释放的信息的多少。

更新信息素：就是修改信息素浓度的过程。信息可能会因为蚂蚁对信息素的修改使的浓度增加，也可能因为蒸发而减少。从实际的角度看信息素的增加会增加蚂蚁访问这条路经的概率，信息素的蒸发的作用是避免朝着并非最佳解的空间过早的收敛。

后台执行：执行单一蚂蚁不能完成的集中行动。后台执行的例子有局部优化过程的执行和全局信息的执行。

 

蚂蚁优化的一般使用步骤

构建图：点边集合

约束：与实际的问题相关的确定约束条件

信息素和启发式信息：影响蚂蚁选择路径的概率

解的构建：把复合的点添加到路径中

 

 

 附：

 

　组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn}为所有状态构成的解空 间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)＝minC(si)。组合优化往往涉及排序、分 类、筛选等问题，它是运筹学的一个重要分支。

典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存 储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”

组合优化的困难所在是我们建立的数学模型只能对解进行验证却不能求解，要想达到预想的结果只能在解空间一个一个的实验。当解空间很大的时候这种逐步验证的方法在时间和空间上都是不允许的。所以人们期望通过一些局部验证的方法朝着局部优化的方向前进，虽然有可能得到的结果不是最优的，但这是解决这种问题的可接受方法，结果往往也是可接受的。在现有的解决组合优化的算法当中，主要的是确定性算法和近似算法，例如爬山算法，但这些算法本身存在着太过于依靠局部信息进行迭代运算，导致结果往往是局部性的最优解，为了克服这种弱点，提出了启发式算法，以及更加一般的元启发式算法。