资源描述:
《重庆大学数学软件实验报告(周先东)》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、实验课程名称:数学软件开课学院及实验室:数理学院2007年04月27日学院数理学院年级、专业、班运筹学y控制论姓名周先东成绩实验项目名称借助数学软件,利用粒了群优化算法(PSO)求解复杂曲面上的最短路径指导教师肖剑一、实验问题的提出求给定曲面上的两定点沿111!面的最短路径,是理论与实际领域都I•分关注的问题。在公路、铁路的布局,电力、通信线路,输水、输油管道的架设等大规模的工程规划问题中,能否求得良好的路径,将对整个丄程的成本以及投入运营后的开支产生重耍影响。二、实验问题的分析由于曲面最短路径问题表述简单而意义重大,数学史上对其冇过长期
2、的研究,其一般的思想是用变分方法求得解析解。这些算法往往极度依赖于描述曲面的函数形式,鲁棒性一般极不理想,而且往往难于处理约束。然而,现实的问题,特别是地形之类的曲而极为复朵,且由观测数据拟合而成,有的直接就是一组离散的数据,远非经典数学研究的那些性态优良的曲面可比。对于复杂的曲面,日前已经有人将先进的启发式概率搜索思想引入来解决路径寻优的问题中。在此基础上,这里提出了一种能够将问题转化到运川随机搜索方法的问题上來的模型,从而解决更一般的复杂]11
3、面上最短路径问题。即通过对Illi面上Illi线同平面上射影曲线的一一对应关系的分析,用离
4、散化的思想提出了一个解决该问题的离散化模型,从而将复杂曲面上路径寻优问题转化为了多元的单FI标优化问题,使得随机搜索算法(模拟退火法、遗传算法,PSO算法等)能够在该问题中发挥作用。三、实验问题的求解1模型建立对于连续的单值曲而G(x,y,z)=0,G上的一切曲线「,必定能够在X0Y平而上找到—•条与其对应的投影
5、
6、
7、
8、线L,并且是唯一的。对于平面上的
9、11
10、线L,我们可以将其离散化成若干段线段连接成的曲线,对于这些线段,我们可以再次细分并通细分得到的点的X、Y处标和G(兀,y,z)=0来求得这些小段所对应的曲而上曲线段的长度,将所有的这
11、些小段的长度累加起来也就是曲线L在曲而上对应的曲线「的长度。由此问题就转化为求函数R==/(刃』2,…儿)的最小值的约束优化问题其中Amin(x,.)<%12、量的区间Z内,通过vdmax=ky(lmax來设置最大速度,这里k是0.1至U1.0之间的一个数。PSO算法流程:1、输入相关参数(初始粒了群数目,粒了的维数,最人迭代次数,最人初始速度,粒子各维的上下限)。2、初始化微粒群(包括微粒的速度和位置)。3、计算初始各个微粒的适应值。4、比较适应值得到初始局部和全局最好位證5、根据飞行算了更新各微粒的速度和位置。6、计算新粒子群中各个微粒的适应值。7、通过比较适应值更新局部和全局最好位置。8、如果迭代达到最人次数,终止运行并输出最优解信息;否则转5。四、实验结果分析验证实例采用搜索空间D为10
13、0x100单位的正方形区域,用函数模拟实际地形,函数构造如下:相关参数为:xc=[2564347794651593];yc=[8728539255241114];p二[1.523231.533];q=[1.53.52231.523];u=[306521611131113];v=f201213251491311];h=[5719-323824-22-14-17];求给定的两点(x(),y())=(5,92),gyj=(95,9)间的最短路径。本例在构造适应度函数时,将x区间设置为[5,951,其中按实际意义将y的区间定为[9,921o以10
14、为步长将x区间起进行了9等分,而后用进一步离散化的方法构造曲线长度函数作为适应度函数。程序运行输入参数:粒子维数为8,粒子各维边界都是[9,92],最大速度为0.2,5,c2对于这样的约束优化问题,由于f不是简单的函数并且在实际问题小人多数Illi面函数都是非常复杂的,有的曲面可能是一些离散的数据构成的函数。2运用PSO算法求解本实验是将冃标函数f(yi,y2,...,yn)的一个解Y二(yhy2,...,yn)看作PSO算法中一个粒子,其空间维数为n,每个粒子的位置被限制在Y的各个分量的区间Z内,通过vdmax=ky(lmax來设置最大
15、速度,这里k是0.1至U1.0之间的一个数。PSO算法流程:1、输入相关参数(初始粒了群数目,粒了的维数,最人迭代次数,最人初始速度,粒子各维的上下限)。2、初始化微粒群(包括微粒的速度和位置