基于分治法的遍历搜索算法和粒子群算法的改进对太阳影子坐标的地理定位和事件确定的研究

黄鸿基,钱圳冰,冯 帆,周行洲210046) (南京邮电大学,江苏 南京

China Market - - Contents - 黄鸿基 钱圳冰 冯 帆 周行洲

[关键词]粒子群算法;遍历搜索;最小误差函数DOI 10  13939/ j  cnki  zgsc  2017  18  199 [ ]

1 引 言

太阳影子的位置和时间的确定,在地理勘测和工程应用中有很高的应用价值。研究首先根据某固定直杆在水平地面上的太阳影子顶点静态坐标数据,建立数学模型确定直杆所处的地点和日期。后通过太阳影子的动态变化视频,判断该视频所发生的大致地点。从而推广这两种算法作为确定太阳影子发生地点和时间的方法。2

基于分治法的遍历搜索算法确定静态坐标下太阳影子发生地点和时间2 1算法分析研究根据相关数据给出的太阳影子顶点坐标数据,建立合理的数学模型来确定直杆所处的地点和日期。根据附件提供的坐标和其他数据,我们可以得到不同时间点所对应的太阳影子长度。很明显,这是一个目标规划问题。可以基于太阳影子长度公示,建立寻找地点和日期的规划模型。同时,考虑到研究涉及的未知量较多,直接求解很难得到最优的结果。因此,考虑纬度、经度和杆长等因素,研究采用先模块搜索后整体遍历的思想,建立一个新的“基于分治法的遍历算法” ,寻找到准确的地理位置并确定它所对应的日期。2 2算法模型的建立步骤一:数据处理

α β h N,定义四组变量 、、 、分别代表经度、纬度、杆子高度和年份。由数学分析的相关理论和地理学的相关知识可知,一组连续的变量可以看成一组间隔无限小的离散型随机变量的线性组合。同时,在地球上,当两个经度之间相差1° 4

时,它们之间的时间相差分钟,因此,我们对数据进行了离散化处理,并且在误差范围内完全可以认为不会对模型的精确度造成影响。我们得到以下关系:

- 90°≤ α≤ 90°纬度:

0 1≤ 0  01≤ 8,( m)高度:

1≤ N≤ 365年份:步骤二:建立目标规划模型 由问题一,研究得到计算太阳影子的计算公式。若我们定Lestimate i义 i为与视频中所对应的第个时刻代入经纬度、高度、L附件日期和时间得到的太阳影子长度, i为通过对附件中的数据i进行处理得到的第个时刻的太阳影子长度。当所有时刻这两个值的平方差最小时,这个地方将有最大的概率与视频中的地点相吻合,因为同一个地点之间由于有着相同的地理参数,它们在同一时刻的太阳影子长度必定完全吻合。得到以下模型:  21 min= L - Lestimate 2附件i i ) i= 1 - 90°≤ α≤ 90° ì 1590 300- 15t2 15t1)°≤ β≤ - )° s t  4 ( ( í 0  1≤ 0  01≤ 8,( m) î 1≤ N≤ 365 min最后,对函数数值求解的精度进行限制,当误差小10- 3于时,停止遍历搜索,认为得到了最优的解决方案。步骤三:建立基于分治法的遍历算法进行优化求解1) (首先把四维向量空间划分为四个一维向量空间,分模块进行遍历搜索。2) (接着,研究按照分治法的思想,分别对四个一维变量进行遍历搜索。同时进行全局搜索寻优。3) ( 将第二步遍历寻优的结果与模型中研究要求的精度进行比较。若第二步中寻优的结果达到我们模型中所要求的精度要求时,遍历结束,否则返回第二步,进行递归的遍历求解。2  3 算法的求解利用计算机模拟,我们得到已知数据中测量所在地数据如下表所示。

[摘要]研究首先分析了经度、纬度、杆子长度和日期这几个变量的关系,通过太阳影子长度计算公式,结合误差控制的相关理论,我们定义了最小误差函数,并建立了一个目标规划模型。对于多参数的情况,研究提出“基于分治法的遍历搜索算法” ,用于求解出影子的地理位置和日期。后研究对在目标规划模型进行了合理的改进,建立了修正过的目标规划模型。通过对所收集的视频进行合理分析,以每三分钟为一个采样周期,得到了影长与时间的相关数据。同时,考虑到数据

PSO) GA) GA- PSO量大和算法复杂度高的因素,研究引入了粒子群 ( 算法,并用遗传算法 ( 对其进行了改进,形成了算法。

3 GA- PSO基于 算法对动态视频中太阳影子的大致地点的确定3  1算法分析研究在两种不同的情况下研究太阳影子的定位问题。首先,根据视频,研究可以得到在各个时间段所对应的太阳影子长度。接着,对于研究已有日期的视频部分,在目标规划模型的基础上进行改进,基于太阳影子长度公式,从而建立合理的规划模型。3 2算法模型的建立步骤一:数据处理α β,基于问题三建模的相关思路,我们定义两组变量 、分别代表经度和纬度。对数据进行了离散化处理,我们得到了以下关系: - 90°≤ α≤ 90°纬度:步骤二:建立目标规划模型在问题三我们建立的目标规划模型的基础上,我们进行L i了适当的改进。若我们定义为与视频中所对应的第 个Li时刻代入经纬度得到的太阳影子长度,为在视频中读出的i第个时刻的太阳影子长度。我们得到以下模型:  22 min= Li- L 2 ( ) i= 1 - 90°≤ α≤ 90° { s t  67  5°≤ β≤ 180° min同时,对于的精度要求,我们定义,当误差小于10- 3时,我们停止搜索,认为已经得到了最优解。GA- PSO)步骤三:用遗传算法优化粒子群算法 ( 以求得步骤二的最优解在本算法中,为了得到最优解,我们设定了迭代次数为1000次。Step1  S i假定有一个维目标搜索空间,其中第 个粒子S表示为一个 维的向量xi =( xi1, x12,…, xis), i= 1,2,…, 22 xi 3),每一个粒子是一个潜在的解。将 代入 ( 我们可i S以算出它的适应值。第个粒子飞翔的速度为 维向量,记V珗= Vi1, Vi2,…, VIS)为 ( 。在这里,我们设定每一个粒子存2储了个参数。同时,通过遗传算法的选择、交叉和遗传过i程对所有变量进行初始化,记下第个粒子迄今为止搜索到P→ =( PIS,…, PIS),的最优位置为 is 整个粒子群搜索到的最 → P =( Pbests,…, Pbests)优位置为 bests 。

P186) thecyclicinventoryroutingproblem J .4OR, 2008, (上接 [ ] 61∶ 97- 100  4 Kunpengli, Binchen, Appaiyersivakumar, Yongwu  An [ ] Inventory routingproblemwiththeobjectiveoftraveltimeminimiza  # tion J . Europeanjournalofoperationalresearch, 2014: 936- 945  [ ] 5  []赵达,李军,马丹祥,李妍峰求解硬时间窗约束下随机 i微粒当前的最好位置可由下式确定: pi( t+ 1)= pi( t)→ min( xi( t+ 1))≥ min( xi( t)) { Xi( t+ 1)→ min( xi( t+ 1))< min( xi( t )) Kennedy Eberhart根据 和 提出的相关理论,对粒子群进行以下操作: 1 v= min { v( t+ 1)= v( t)+ rand1( t)( pis( t)- + rand2( pbests( t)- t)) xis( t+ 1)= t)+ v( t+ 1 )其中, i= 1,22 s= 1, S [ ], [ ] ; rand( t) ,分别为学习因子, 为产生随机数的函数, 0,1服从 [ ]区间的均匀分布。根据上述方程组,分别对粒子群的速度和位置进行更新,若满足终止条件,则输出解,否则返回重新进行下一步′的寻优。i最终,我们便可以得到视频拍摄地点的经度和纬度,从而进行比较精确的定位。

4算法推广

GA- PSO”本模型所提出的 “算法对于解决大数据量的算法复杂度较高的问题有着较高的实用价值。该算法可以推广到人口相关数据的统计已经生产力的评估等多个领域。 参考文献: 1   []司守奎,孙兆亮数学建模算法与应用 北京 国防工业2016( 1) 出版社, 2  MATLAB []卓金武,李必文,魏永生,等 在数学建模中的M   2014( 9) 应用 [ ] 北京北京航空航天大学出版社,

61322112) [基金项目]国家自然基金(项目编号: 。1995—), [作者简介]黄鸿基 ( 男,汉族,江苏南京人,南京5G邮电大学本科生。研究方向:通信和智能算法;钱圳冰1996—), ( 男,汉族,江苏泰州人,南京邮电大学本科生。研究方1995—),向:计算机科学与技术;冯帆 ( 男,汉族,江苏南京人, 5G南京邮电大学本科生。研究方向:通信和智能算法;周行洲1995—), ( 男,汉族,江苏南京人,南京邮电大学本科生。研究方5G向: 通信和智能算法。

- J . ,2014,23需求库存路径问题的优化算法 [ ]运筹与管理1): 27- 37  ( 6 Zhenpingli, Zhiguowu  Studyontheinventoryroutingprob  [ ] lemofrefinedoildistributionbasedonworkingtimeequilibrium J . [ ] Americanjournalofoperationsresearch, 2016,6( 1): 17- 24 

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.