【www.zhuodaoren.com--百科】
模型参数优化算法(一)
环境模型参数优化方法的比较
摘要：模型参数优化是通过极小化目标函数使得模型输出和实际观测数据之间达到最佳的拟合程度. 由于环境模型本身的复杂性,常规优化算法难以达到参数空间上的全局最优. 近年来,随着计算机运算效率的快速提高,直接优化方法得到了进一步开发与广泛应用. 本文比较了CRS、SCE UA、SA 和Annealing2Simplex 等4 种算法应用于环境模型参数优化的结果和计算效率。 关键词：参数优化 环境模型 CRS 算法 SCE UA 算法 Simulated2Annealing 算法 Annealing2Simplex 算法 人们对环境系统的深入研究是建立在环境模型的广泛应用基础上的. 为了更加精确地刻画环境系统的行为,环境模型在近10 年里表现出了强烈的复杂化趋势;不同空间尺度、不同时间过程模型的耦合,进一步加剧了这一过程. 环境模型的复杂性导致了模型结构和参数可识别性问题的提出,并成为当今环境建模理论研究的热点[1 ,2 ] . 其中在不确定性的框架下,模型参数的优化是研究的一个重要方面. 解决优化问题的难度主要取决于模型参数的空间维数和模型本身的非线性特征. 一般来说,参数越多、非线性越强,优化时间和精度就越差,同时也越不能够保证优化算法是否收敛到整体最优. 传统经验表明,求解优化问题的困难主要体现为[4 ,5 ] : ①全局搜索可能收敛到多个不同的吸引域; ②每一个吸引域可能包含一个或多个局部最小值; ③目标函数在n 维参数空间上不连续; ④参数及相互间存在高度灵敏性和显著非线性干扰; ⑤在最优解的附近,目标函数往往不具有凸性。 优化算法可以分为直接算法和间接算法2大类. 间接算法(如牛顿法以及各种以牛顿法为基础的改进算法) 的局限性主要在于要求目标函数在相关值域上必须是可微的;而直接算法仅涉及目标函数值的计算,不需要计算目标函数的导数. 因此尽管后者的计算效率相对较低,但在环境问题的实际应用中,它可以有效和简洁地解决由于模型复杂性所衍生的不可微函数的优化问题. 同时,与求解问题所耗费的时间相比,通常更为关注解的结果能够在多大程度上描述系统的行为[1 , 2 ] . 所有这些使得直接算法在近年来得到了迅速发展和广泛的应用. 本文的目的在于分析和比较几种近年来渐为接受的参数直接优化算法的计算效率、计算精度及其算法稳定性. 由于直接算法本质上的随机性,以及对于不同优化问题所表现出的算法特性上的差异,因此本文仅以经典测试函数和环境水文模型为例,对几种算法进行详细的比较研究. 1 参数优化算法 模型参数的优化即是寻求一组参数,使模型的输出与实际观测数据之间按给定目标函数的度量方式达到最佳拟合,即: Min f ( ys , yobv ,θ) = f ( ys , yobv ,θ3 ) θ ∈ S (1) 式中, f ( y , θ) 为目标函数; ys 表示模型输出变量, yobv为系统观测值;θ3表示参数可行域S 上的最优参数向量. 最早提出的直接算法均是简单随机方法,这些算法除了计算效率低外,主要缺陷在于要求目标函数在邻域上必须是不相关的.[!--empirenews.page--] 控制随机搜索算法(CRS)
[10 , 11 ] 有效地克服了简单随机算法的主要缺点,在计算过程中保存指定数目的参数样本及其对应的目标函数值,引入几何学中“重心”的概念,即考虑了新点产生的随机性,又在一定程度上保证了搜索的整体性. 复合形混合演化算法( SCE UA) [4 , 5 ]所采用的竞争演化和复合形混合的概念继承了CRS 算法中全局搜索和复合形演化的思想,该方法将生物自然演化过程引入到数值计算中,模拟了生物进化的过程,提高了计算效率和全局搜索整体最优的能力. 模拟退火算法(SA) [7 , 12 ]则假设优化问题的解及其目标函数分别与固体物质的微观状态及其能量所对应,采用蒙特卡洛(Monte Carlo) 随机方法模拟固体稳定“退火”的过程,并假设优化过程中递减目标函数值的控制参数t 与“退火”过程中的温度T 所对应,对于控制参数t 的每一个值,算法持 续进行“产生新解2判断2接受/ 舍弃”的迭代过程,应用该算法的关键在于确定合理的冷却进度表. 退火单纯形算法(AS) [8 , 9 ]综合了下山单纯形方法和模拟退火法2 种优化算法,充分利用单纯形的形变信息,以一定温度T 所对应的概率接受准则来指导单纯形的映射、压缩和扩展等过程,提高了计算效率和算法稳定性. 运用直接算法进行参数优化首先要正确选取算法的内部控制参数. 一般根
据具体问题的特点,采取数值实验的方法不断测试参数“性能”,从而确定既保证算法收敛到满意的极值,又不至于使计算过于耗费时间而导致算法失效. 选择控制参数本身实际就是一个“优化”过程. 2 测试函数的优化 首先采用一个广泛使用的、具有多个局部极小值的经典函数,对上述几种优化算法的全局搜索能力进行较为全面的测试,其函数形式为: 尽管测试函数仅有x 、y 2 个变量,但其等值线却具有复杂的空间结构,即多个局部极小、值域空间上的不连续和全局最小值周围的香蕉状狭长低谷(图1) . 现已知参数全局最小值为(5 ,5) ,所对应的目标函数值为10.0。
模型参数优化算法(二)
数学建模十大经典算法
建模十大经典算法
1、蒙特卡罗算法。
该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。
2、数据拟合、参数估计、插值等数据处理算法。
比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。
3、线性规划、整数规划、多元规划、二次规划等规划类问题。
建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。 4、图论算法。
这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。【模型参数优化算法】
这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7、网格算法和穷举法。
网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8、一些连续离散化方法。
很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9、数值分析算法。
如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10、图象处理算法。
赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图
形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。
历年全国数学建模试题及解法
赛题
93A非线性交调的频率设计 93B足球队排名 94A逢山开路 94B锁具装箱问题
95A飞行管理问题
95B天车与冶炼炉的作业调度 96A最优捕鱼策略 96B节水洗衣机
97A零件的参数设计 97B截断切割的最优排列 98A一类投资组合问题 98B灾情巡视的最佳路线 99A自动化车床管理 99B钻井布局
00A DNA序列分类 00B钢管订购和运输 01A血管三维重建
01B 公交车调度问题 02A车灯线光源的优化 02B彩票问题
03A SARS的传播 03B 露天矿生产的车辆安排
04A奥运会临时超市网点设计 04B电力市场的输电阻塞管理 05A长江水质的评价和预测 05B DVD在线租赁
解法 拟合、规划
图论、层次分析、整数规划 图论、插值、动态规划 图论、组合数学 非线性规划、线性规划 动态规划、排队论、图论 微分方程、优化 非线性规划 非线性规划 随机模拟、图论 多目标优化、非线性规划 图论、组合优化 随机优化、计算机模拟 0-1规划、图论
模式识别、Fisher判别、人工神经网络 组合优化、运输问题 曲线拟合、曲面重建 多目标规划 非线性规划 单目标决策 微分方程、差分方程 整数规划、运输问题 统计分析、数据处理、优化 数据拟合、优化 预测评价、数据处理 随机规划、整数规划
06A出版资源配置
06B艾滋病疗法的评价及疗效的预测 07A中国人口增长预测 07B乘公交，看奥运 多目标规划 数据处理 图论 08A数码相机定位 08B高等教育学费标准探讨
09A制动器试验台的控制方法分析 09B眼科病床的合理安排 动态规划 10A 10B
赛题发展的特点：
1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B，某些问题需要使用计算机软件，01A。问题的数据读取需要计算机技术，如00A（大数据），01A（图象数据，图象处理的方法获得），04A（数据库数据，数据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果。 2.赛题的开放性增大 解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对数据处理上。
3.试题向大规模数据处理方向发展 4.求解算法和各类现代算法的融合
从历年竞赛题来看，常用的方法：
线性规划 整数规划 非线性规划 动态规划 层次分析法 图论方法 拟合方法 插值方法 随机方法 微分方程方法
各种算法的详解
一、蒙特卡洛算法
1、含义的理解
以概率和统计理论方法为基础的一种计算方法。也称统计模拟方法，是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法，它是将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。 2、算法实例（有很多相似的例题，包括平行线等）
在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。P落在扇形内的充要条件是 xy1 。
2
2
s1mPi，K，s=1，s1=，求Pi。 sn4
s1mmm由，知s1*s=， snnnPim而s1=，则Pi=*4
n4
已知：K=
程序：（该算法可以修改后用Mathematica计算或者Matlab）
/* 利用蒙特卡洛算法近似求圆周率Pi*/ /*程序使用：VC++6.0 */ #include<stdio.h> #include<math.h> #include<stdlib.h>【模型参数优化算法】
#define COUNT 800 /*循环取样次数，每次取样范围依次变大*/ void main() {
double x,y; int num=0; int i;
for(i=0;i<COUNT;i++) {
x=rand()*1.0/RAND_MAX;/*RAND_MAX=32767，包含在<stdio.h>中*/ y=rand()*1.0/RAND_MAX; if((x*x+y*y)<=1)
num++; /*统计落在四分之一圆之内的点数*/ }
printf("Pi值等于：%f\n",num*4.0/COUNT); }
结果：
如果加入程序：srand(time(NULL)); ，同时循环取样次数一定，让取样结果随时间变化，当取样次数为80000000时，可得6次的结果显示：
3.141290 3.141400 3.141268 3.141484 3.141358 3.141462 3、应用的范围
蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运 计算、量子热力学计算、空气动力学计算)等领域应用广泛。 4、参考书籍
[1]蒙特卡罗方法及其在粒子输运问题中的应用 [2]蒙特卡罗方法引论
二、数据拟合、参数估计、插值等数据处理算法
（1）数据拟合
在Mathematica中，用Fit对数据进行最小二乘拟合：Fit[data,funs,vars] 在Matlab中，工具箱（toolboxes）中有曲线拟合工具（curve Fitting）。 实例：
2010年苏北赛B题 温室中的绿色生态臭氧病虫害防治 中关于中华稻蝗密度与水稻减产率之间的关系可以通过数据拟合来观察（简单举例，没有考虑全部数据）【模型参数优化算法】
程序（Mathematica）：
data={{3,2.4},{10,12.9},{20,16.3},{30,20.1},{40,26.8}}; a1=Fit[data,{1,x,x^2,x^3},x]
Show[ListPlot[data,Filling->Axis],Plot[{a1},{x,0,60}]] 结果：
23
-3.68428+2.38529 x-0.0934637 x+0.00132433 x
（2）参数估计（参考书：概率论与数理统计）
参数估计为统计推断的基本问题，分为点估计和区间估计。 点估计： ①矩估计法
X连续型随机变量，概率密度f(x;1,2,n)
X为离散型随机变量 分布律P{Xx}p(x;1,2,,k)
1,2,,k为待估参数，X1,X2,Xn是来自X的样本，假设总体X的前k阶矩存在，为
模型参数优化算法(三)
浅析智能优化算法
摘 要：算法优化在许多的工程领域得到了广泛的应用，而求解线性、非线性、随机和几何规划等各种最优化的问题也得到了快速发展。智能优化算法是利用自然界中的事物与优化过程中所具有的某些相似性而进行搜索的一种搜索算法，相对于传统的优化算法，智能优化算法在求解速度等方面具有显著优点。 关键词：算法；算法优化；智能优化
中图分类号：TP301.6
优化问题有着传统优化理论和现代智能优化理论，传统的优化理论由于有着线性规划和非线性规划的数学知识的支持，目前已经在多个生产领域得到了大量的应用，但由于其必须要在获知最优解决方案的数学特征的前提，才能根据最优解决方案的数学特征设计出相对应的算法，在每一步解决步骤中必须建立在对优化问题的充分了解的基础之上，所以其具有十分大的局限性。现代智能优化理论并不需要了解优化问题的最优解的数学特征，而是对优化问题进行启发式的算法进行求最优解，其本身是一个近似算法，其并不能保证一定能够求得最优解，但是其可以在最短的时间内可以得到最接近最优解的解决方案，因此其得到了广泛的利用。根据智能优化的思想，1991年，意大利学者Dorigo根据蚂蚁觅食行为中总是沿着最优途径进行觅食的原理提出了将分布式计算、正反馈和启发式算法结合起来用来解决组合优化问题的理论。[1]国内学者李晓磊利用鱼群行为的原理提出的鱼群算法也是一种智能算法。[2]
本论文主要内容。本文将首先介绍了智能优化算法的原理，智能优化算法是模拟自然和生物现象，因为在自然界，生物总是朝着最适应环境的方向进化，根据此原理，智能优化算法能够在不知晓最优解的数学特征的前提，找出最接近最优解的优化解。然后文章将介绍一些著名的智能优化算法，例如模拟蚂蚁的算法等。最后文章将对智能优化算法的一些实际应用进行说明并对以后的研究方向进行展望。
1 智能优化算法
1.1 智能优化算法的定义。传统优化算法和智能优化算法尽管它们的原理不同，但是它们都是根据所需要优化问题的目标函数来寻找最优解，传统优化算法是根据目标函数的数学等特征来寻找最优解的，而智能优化算法是根据自然生活现象来模拟目标函数以寻找最接近最优解的优化解，智能优化算法的迭代过程必须包括以下三个步骤：第一步，在目标函数的可行范围以事先定好的寻找优化解的策略来寻找一组初始解；第二步，继续在目标函数的可行范围内按照原来的策略继续寻找优化解；第三步，判断结束条件是否满足，当满足的时候再所有解选出最优解，如果不满足，返回第二步继续执行直至结束条件满足。[3]
1.2 典型的智能优化算法分析。智能优化算法是模拟自然界的现象，在搜索过程不断调整搜索策略以便更好地进行搜索，根据所模拟的自然界的现象的不同，主要的智能优化算法有：
1.2.1 蚁群算法。蚁群算法是根据自然界的蚂蚁在觅食的过程中总是朝着食物的方向前进并在行进过程中不断调整行进路线，在其中关键的是优化解的构造策略和信息素更新策略，其实现的步骤是：第一步，将所有可行方案中的路径的信息素设置初始值；第二步，在目标函数的可行域按照解的构造策略构造一组解；第三步，按照信息素更新策略更新所有的路径信息素；第四步，判断结束条件是否满足，满足的话输出最优解，不满足的话返回到第二步进行算法的迭代。[4]
1.2.2 粒子群算法。粒子群算法是模拟自然界鸟群觅食过程而实现的，其原理是根据鸟群在觅食过程中总是朝着食物源靠近但是每一只鸟靠近食物的速度和路径可能不同，其中的关键是确定每个粒子的适用度值，粒子群算法实现的步骤有：第一步，确定每一个粒子所处的位置和速度并计算出每一个粒子的适用度值；第二步，更新全局的最优粒子和每一个粒子的局部最优；第三步，更新更新策略更新每个粒子的位置和速度；第四步，判断结束条件是否满足，满足的话就输出最优解，不满足的话转到第一步中计算每一个粒子的适用度值继续算法的迭代。
1.2.3 遗传算法。遗传算法是模拟在自然界中生物进化过程的优胜劣汰的原理，但是在其中一个优化解只是对于生物群里面的一个个体，所有的优化解的集合才是整个生物群的优化解，因此需要用一个选择、交叉和变异算子来模拟生物种群的整个进化过程，粒子算法的主要实现步骤有：第一步，对所要处理的种群进行初始化；第二步，从种群按照选择算子和一定的选择策略选出一个总数为n的个体；第三步，从种群里面任意选择出m对个体，利用交叉算子和一定的概率产生后代；第四步，在所产生的后代中按照变异算子和一定的概率进行变异；第五步，计算出每个个体的适应度值；第六步，判断结束条件是否满足，满足的话选出最优解，不满足的话则跳转到第二步继续算法的迭代。
1.2.4 模拟退火算法。模拟退火算法是模拟固体退火的整个过程，其根据的基本原理是物体内部的内能随着温度的变化而成正反应变化，当固体处于常温的时候其内部粒子就处于基态，当固体从高温温度下降的足够慢的时候其内部粒子就会处于平衡态，其用固体的内能来模拟目标函数，用温度来模拟控制参数，而用降温来模拟参数变化。模拟退火算法的主要实现步骤有：第一步，初始化，设定一个初试参数和一个初始解；第二步，在已经得到的优化解的邻域内任意选择一个新的解；第三步，根据准则来判断新解是否可以被接受或者被拒绝；第四步，判断固体是否处于平衡状态，若满足条件进行下一步，不满足的话返回到第二步继续算法的迭代；第五步，给固体降温。
1.3 智能优化算法模型分析
1.3.1 智能优化算法概率模型。智能优化算法实际上是一种搜索算法，与智能优化算法相对于的还有一种概率型的搜索算法，这就是纯随机搜索算法，纯随机搜索按照随机的均匀分布来进行搜索，基本上和枚举法没有本质上的区别，而智能优化算法是一种基于概率的采样模型，它具有如下特点：第一，其采样方式确定，目标函数是不容易直接描述其数学等方面的特征；第二，为了和纯随机采样相区别，智能优化算法采用带参数的采样模型，而且其采样模型只和当前状态有关而且可以根据采样数据进行自行改进。[5]
2 小结与工作展望
2.1 总结。本论文主要是介绍了智能优化算法，智能优化算法是在不知晓目标函数的数学特征的情况寻找最优解应用的十分广泛的算法，其主要是模拟自然界现象以便随时更新信息，寻找出最接近最优解的优化解，本文主要完成的工作有：（1）研究了一些主要的典型的智能优化算法，例如蚁群算法，粒子群算法等，研究了这些算法的原理和其模拟的是那些自然界的现象以及它们迭代的步骤；（2）研究了智能优化的采样模型，主要是研究了基于概率的模型。
2.2 下一步研究方向。本文主要是对智能优化算法的基本原理、采样模型进行了研究，下一步的研究方向主要有：（1）继续研究主要智能优化算法的实现方式，对比研究它们的优劣性；（2）继续研究智能优化算法的采样模型，重点研究概率分布密度函数等；（3）将智能优化算法结合具体事例进行研究，对理论加以论证。
参考文献：
[1]Dorigo M，Maniezzo V，Colorni A.Positive feedback as a search strategy[J].Technical Report n. 91-016，Politecnico di Milano，1991：1-20.
[2]李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践，2002（11）：32-38.
[3]汪定伟，王俊伟.智能优化方法[M].北京：高等教育出版社，2007.
[4]杨劲秋.智能优化算法评价模型研究[D].浙江大学，2011.
[5]高永超，智能优化算法的性能及搜索空间研究[D].山东大学，2007.
作者简介：刘静（1982-），女，硕士研究生，信息工程系，从事高职教育教学研究、软件开发技术方向的研究。
作者单位：湖南工程职业技术学院，长沙 410075
本文来源：http://www.zhuodaoren.com/shenghuo287669/
推荐访问:智能优化算法 蚁群优化算法