数学建模社区-数学中国

标题: 简单介绍一些优化计算方法 [打印本页]

作者: 普大帝 时间: 2022-7-16 16:58
标题: 简单介绍一些优化计算方法

1 遗传算法
遗传算法（Genetic Algorithm）是模拟生物学上达尔文进化论的自然选择、遗传和变异现象的算法模型，它可以通过模拟自然进化过程来搜索一个优化问题的最优解.遗传算法仿照基因编码的工作把优化问题的决策变量进行编码，如二进制编码，所有变量的编码合成染色体.遗传算法从代表问题可能的解集的一个种群开始，这里一个种群是由经过基因编码的一定数目的个体即染色体组成.染色体内部表现，即基因型，是某种基因组合，它决定了个体的形状的外部表现，在优化问题中即最优性.从初代种群开始，通过遗传或者变异，也就是各种算法操作，产生以后的各代种群：各代种群按照适者生存和优胜劣汰的原理，以最优性来比较，逐代演化出越来越好的近似解.这个过程将导致种群像自然进化一样而产生的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为原问题的近似最优解.
以TSP问题为例，我们可以进行如下的编码.TSP问题的每个可能的解是1～N的一个排列，因此一个编码就是这样的一个排列，而一代中的种群就是若干个不同排列的集合.
一个排列的适应度可以很容易地定义为该排列对应的总行程的倒数，这样总行程越小的排列，其适应度越高.
那么，不同编码组如何进行遗传和变异呢?比如，父代有两个个体，如下所示（N=7）.

假定我们简单地以中间3个基因（横线画出）交换，则会得到（1,4,1,5,7,2,6）这样非法的个体，它实际上不是1～7的一个排列.有许多方式可以用来变换得到合法的表示，比如固定P2中画出的1,5,7不动，把其余基因2,3,4,6按序从后排出，可以得到4,6,1,5,7,2,3，或者按照P1中余下的基因的顺序，可以得到2,4,1,5,7,3,6，这里未画出线的4个基因的数字大小关系和P1中对应位置的4个基因是一样的.
变异的方式较为简单，例如，按照概率选取其中的一个基因，随机插入其他位置，或者随机与另一个基因互换.例如，考虑P1，我们可以得到（1,3,4,2,5,6,7），或者（1,7,2,5,6,3,4）.
4.6.2 模拟退火算法
模拟退火算法（Simulated Annealing）是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其模拟物理中晶体物质的退火过程与一般组合优化问题之间的相似性，来搜索组合优化问题的全局解.模拟退火算法从某一较高初温出发，伴随温度参数的不断降低，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，它可以在局部最优解时按照一定概率跳出，并最终趋于全局最优.模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能，目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域.
模拟退火算法的基本框架如下.
（1）初始化：给定充分大的初始温度T，初始解状态S（算法迭代的起点），每个T值的迭代次数L，温度降低比例ρ.
（2）对k=1,2,…,L执行第（3）～第（6）步操作.
（3）产生新解S′.
（4）计算增量Δt′=C（S′）-C（S），其中C（S）为评价函数.
（5）若Δt′＜0，则接受S′作为新的当前解，否则以概率exp（-Δt′/T）接受S′作为新的当前解.
（6）如果满足终止条件，则输出当前解作为最优解，结束程序.终止条件通常取为连续若干个新解都没有被接受时终止算法.
（7）T逐渐减少，T←ρT，然后转第（2）步.
4.6.3 启示性算法
启示性方法是一种可以用来加速搜寻过程但并不保证能达到最优解的方法，但一般比较简单，可以找到一些较优的解.
例如，针对TSP问题，我们可以有如下启示性方法.考虑前面的路径P1:（1,4,2,5,6,3,7），选中2组相邻的顶点，可以有P1:（1,4,2,5,6,3,7），如图1所示.

图1启示性算法示意图
我们可以考虑把原来的5-6和1-4的两条边替换为1-5和4-6，如果新形成的路线更短.这种替换方式可以一直不停地进行：随机选取2组相邻的顶点，进行同样的尝试，直至任意替换找不到更优的路线.当然这不能保证得到最优解，但一般都会得到一个不错的答案.
数学上也很简单，考虑右边的单个顶点4,2,5，这样的替换相当于这3个顶点在原来路线中反序，所以新的路线是（1,5,2,4,6,3,7）.这种启发性搜寻的方式也可以在3组顶点中进行，当然也可以考虑其他的改进方法.

4 蚁群算法
蚁群算法模拟蚂蚁觅食的过程，是一种用来在图中寻找最优路径的概率型算法.蚂蚁采用的方法是全体在蚁巢的周围区域进行地毯式搜索，它们之间通过分泌化学物质在爬过的路径上而取得联系，这种化学物质叫作信息素（Pheromone）.刚开始离开蚁巢的时候，蚂蚁可能有几条路径可选择.这些路径被选择的机会相当，蚂蚁在爬过这些路径时都留下了信息素.但是较短的路径所需要的时间就少，而信息素会挥发，所以蚂蚁留在较短路径上的信息素浓度就高.于是，后来的蚂蚁就有较多的机会选择短的路径作为它的最佳路径，即使它们已经找到食物，也将选择这些较短路径返回蚁巢.而从蚁巢里出发的蚂蚁们也越来越倾向于较短路径，在这样的趋势下，较长的路径上的蚂蚁越来越少，最后所有蚂蚁都会堆集在最短的路径上.
实现蚁群算法一般需要设置迭代次数、蚂蚁个数、信息素挥发速度，以及算法所需的其他一些参数.
5 演示
一个售货商在几个城市中旅行并兜售他的商品，他想要到每个城市去一次，并最终回到自己居住的城市.已经给定这些城市两两之间的距离，问这个售货商如何规划自己的旅行计划可以使得总行程最短.
旅行售货商问题简称为TSP 问题（the Travelling Salesman Problem），是一个很典型的NP完全问题，于20世纪30年代提出并被许多科学家和工程师关注.该问题有各种不同类型的算法，并同时具有不同的测试数据，用来评估对应的或潜在的算法的不足之处.
一个TSP问题在数学上可以如下形式提出：给定N个城市的坐标（xi,yi）,i=1,2,…,N，寻找旅行售货商的一个旅行计划即需要找到1～N的一个排列π1,π2,…,πN，使得旅行售货商的总行程最短

其中，N+1的下标等同于1.
如果想要得到该问题的精确解，一般地，我们需要穷举所有的排列，该数量达到N!，即便考虑到出发的城市可以任意固定一个，那也有（N-1）!.
我们分别采用遗传算法、模拟退火算法、启示性算法和蚁群算法来求解TSP 问题.假设该售货商想去37个城市，这37个城市的相对位置如2中“○”所示，要到37个城市并且路程最短，我们分别可以得到上述4个算法的近似解，如图2所示.

图2 蚁群算法近似解图

作者: 1051373629 时间: 2022-10-22 09:55
感谢楼主的资料

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)