直升机搜索问题.docx

《直升机搜索问题.docx》由会员分享，可在线阅读，更多相关《直升机搜索问题.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、暑期建模培训评 阅 栏评阅号评阅情况 学员评语 教员评语暑期建模培训评 阅 栏评阅号评阅情况 学员评语 教员评语2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则(以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载)。我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料(包括网上查到的资料)，必须按照规定的参考文献的表述方式在正文引用处

2、和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示(包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等)。我们参赛选择的题号是(从A/B/C/D中选择一项填写)： B 我们的参赛报名号为(如果赛区设置报名号的话)： 所属学校(请填写完整的全名)： 中国人民解放军理工大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： (论文纸质版与电子版中的以上信息必须一致，只是电子版中无

3、需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。) 日期： 年 月 日赛区评阅编号(由赛区组委会评阅前进行编号)：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号(由赛区组委会评阅前进行编号)：赛区评阅记录(可供赛区评阅时使用)：评阅人评分备注全国统一编号(由赛区组委会送交全国前编号)：全国评阅编号(由全国组委会评阅前进行编号)：运动目标快速搜索辨识摘要护航是我军的经常性任务，具有重要意义。运用舰载直升机快速完成一定区域内可疑运动目标的搜索辨识是护航最重要的任务之一。本文讨论的问题可归结为对可疑运动目标搜索辨识的路线优化问题。针对

4、各个问题给出的不同条件，建立了相应的模型，并进行求解。问题一中，运用余弦定量得出直升机对单一可疑目标的最优搜索路线。考虑多可疑目标时，采用聚类分析的方法，将目标进行分类，得到若干聚集小区域。针对小区域内的搜索，本文建立了基于聚类分析和贪婪算法的优化模型以及基于聚类分析和模拟退火算法的优化模型两个模型。利用MATLAB求解模型并比较得到，最快搜索时间为721秒。问题二中，用两架直升机对22个运动的可疑目标进行搜索辨识。考虑到飞机的整体搜索效能由最后搜索完毕的直升机决定，则需给两架直升机合理分配任务量，使差值最小。分配方法为，先进行聚类分析，得到若干偶数个小区域。再以这些小区域的几何中心的位置分布

5、为主要因素，将小区域进行聚类分析，得到几块位置相对集中的小区域群。分类时，将这些小区域群均分成两部分，若两部分的任务量不同，需合理修正至相同。在小区域群及小区域内部的搜索，仍可以构建问题一中的模型。利用MATLAB求解得，在最优路线下，一架直升机的搜索时间为1256秒，另一架的搜索时间为1568秒。问题三中，要实现保护重要货船及搜索时间最短的双目标。先定义危险性系数，利用层次分析法得到距离和时间的影响权重。为保证安全性，先派遣一架直升机搜索辨识危险性最大的可疑船只，并且由于该机在开始的一段时间没有进行搜索辨识，应分配更少的任务量，使得搜索完毕时间差值最小。在小区域内的搜索辨识仍采用问题一的搜索

6、算法。从而保证在确保货船安全的前提下，最快搜索辨识完所有目标。利用MATLAB求解得，直升机搜索最危险目标的搜索时间为420秒，总搜索时间为1865秒，另一架的搜索时间为1920秒。关键词： 余弦定量，聚类分析，层次分析，危险性系数，贪婪算法，模拟退火1 问题重述亚丁湾护航，是中国海军在亚丁湾索马里海盗频发海域护航的一项军事行动。自2008年12月26日起，我海军已派遣10批护航编队担负护航任务。在护航期间，舰载直升机主要完成搜索目标和营救任务，特别是对于水面上可疑运动目标的搜索辨识是最重要的任务之一。 军舰在护航过程中，通常可以通过舰载雷达扫描发现50km以内的可疑目标，一旦发现可疑船只，舰

7、载直升机就会紧急起飞，执行搜索辨识这些可疑船只的任务。当直升机进入以待辨识目标为中心，半径为2km的圆型区域内即可识别可疑目标是否为海盗船。在同一时间、同一区域内会有多个运动的可疑目标，问题是如何才能够最有效地搜索辨识所有的可疑目标。军舰通常跟随需要护航的船队航行，船队的航速一般为15节，航向为正北方向。如果军舰载有两架直升机，直升机的飞行速度为250km/h，最大续航能力为2.5小时。请你们结合军舰护航的实际问题，通过建模研究下面问题： （1）现通过舰载雷达发现有10个运动的可疑目标正在接近护航船队，并即时测得这些可疑目标的相对位置、航向和航速数据如表1所示。请你们给出一架直升机最优的飞行搜

8、索辨识策略和路线。 （2）如果在50km的范围内舰载雷达发现22个运动的可疑目标，并测得的相对位置、航向和航速如表2所示。为了快速搜索辨识这些可疑目标，可以同时起飞两架舰载直升机执行这个任务。请你们给出这两架直升机最优的飞行搜索辨识策略和路线。 （3）现在有相对位于（20，25）（km）处的重要货船请求护航保护，该货船的航速15节，航向310度。可疑目标船只如表2所示。请你们给出两架直升机最优的飞行搜索辨识策略和路线，使得所用时间尽量短，而且使对货船的潜在威胁程度最低。2 问题分析本文研究的是运动目标搜索路线优化问题。首先需要定义最优。由于可疑船只对舰队有一定危险性，越快搜索完毕越安全。因此本

9、文主要考虑搜索时间最短为优化目标，根据运动的几何关系，主要运用余弦定量，得到直升机搜索单个可疑目标时的最优搜索路线。其次，采用合适算法优化直升机对各个可疑目标的搜索辨识顺序。问题一是求一架直升机搜索十个目标的最优策略和路线。题中十个可疑目标的相对位置、航向和航速各不相同，但分析发现在一定范围内有趋同性。而直升机在搜索时，一次性搜索完临近的几个可疑目标比跳跃式的搜索要更省时间。因此，先对该十个目标进行聚类分析，得到几个小区域。由于可疑船只的速；度要比直升机小得多，直升机搜索时可疑船航行距离相对于直升机搜索的距离可以忽略不计。则聚类时可以主要考虑相对位置，忽略可疑船只的航向和航速，从而简化了问题，

10、减小了计算的复杂度。小区域内的可疑目标的位置相对集中，直升机可以依次进行搜索辨识。本文分别运用贪婪算法、遗传算法进行搜索。搜索过程中，直升机每搜索完一个小区域之后，可疑船只的相对位置会发生改变，则不能采用之前的分类。因此重新进行聚类分析，确定新的小区域分布。再根据小区域的分布情况，确定下一个搜索的区域。如此反复，直至搜索完毕，这样就能保证在每一次小区域搜索过程中，都使搜索时间最小。本题的难点在于搜索期间，可疑船只的位置时刻变化。本文采用两种解决方法。一是直升机每搜索完一个小区域之后，重新进行聚类分析，确定新的小区域分布。一是将区域分的足够细，使得在每个小区域中搜索时，可疑船只的相对位置改变可以

11、忽略不计。这样就能使得在每一次小区域搜索过程中，都使搜索时间最小。从而以局部最优逼近全局最优。问题二是在舰载雷达发现22个运动的可疑目标，并测得的相对位置、航向和航速的情况下，同时起飞两架舰载直升机进行搜索。求这两架直升机最优的飞行搜索辨识策略和路线。同样可以先进行聚类分析，得到若干偶数个小区域。再以这些小区域的几何中心的位置分布为主要因素，将小区域进行聚类分析，得到几块位置相对集中的小区域群。分类时，将这些小区域群均分成两部分，若两部分的任务量不同，需合理修正至相同。用两架直升机分别对这两部分进行搜索。在区域群及小区域内部的搜索，可以采用问题一中的搜索算法。从而使得两架直升机的搜索效能同时达

12、到最大化。同等时间内，直升机的搜索效能相同，整体搜索效能由最后搜索完毕的直升机决定。则保证两架直升机的搜索效能的差值最小就保证全局搜索效能最大，则其相应的搜索路线即为最优搜索路线。问题三是在要尽量保护重要货船的情况下，同时求出搜索时间最短的最优飞行搜索辨识策略和路线。首先确定对货船危险性最大的可疑目标。影响危险性大小的因素主要有可疑船只与货船的距离以及可疑船只追上货船的时间长短。利用层次分析法得到距离和时间的影响权重，从而定义危险性系数。用MATLAB得到各个可疑船只的危险性系数，然后选出危险性最大的可疑船只。为保证安全性，需先派遣一架直升机搜索辨识危险性最大的可疑船只。再以该可疑船只所在位置

13、及原点连线为分界，将小区域分成两部分，并合理修正尽量使两架直升机搜索完所有目标的时间大致相等。由于先去搜索辨识危险性最大的可疑船只的直升机在开始的一段时间没有进行搜索辨识，则应分配其更少的任务量。在小区域内的搜索辨识仍采用问题一的搜索算法。这样用一架直升机保证货船的安全，并合理分配两架直升机的搜索任务量使得搜索时间差最小，从而保证在确保货船安全的前提下，最快搜索辨识完所有目标。 3 符号说明直升机时刻的坐标可疑船只在时刻的坐标可疑船只的速度直升机的速度直升机搜索的路线长度直升机的可辨识半径军舰护航的货船在时刻的位置船队速度4 模型假设（1）护航船队的航速为 15 节，舰载直升机飞行速度为 25

14、0 km/h，最大续航能力为 2. 5 h，其在半径为 2 km 的圆型区域内可识别可疑目标 ；（2）直升机忽略起动时间；（3）舰艇、可疑目标、护航船队的航向和航速不变；（4）直升机的辨识距离为二维空间；（5）直升机对可疑目标的截相遇采用直线方式；（6）直升机可以同时辨识进入其探测区域的所有可疑船只；（7）可疑船只对船队中的货船没有危险；5 问题一的求解5.1问题一的模型准备5.1.1搜索线路准备图1是利用excel画出的可疑船只的初始位置分布图，军舰在原点位置，直升机从原点处起飞开始搜索。当直升机进入以待辨识目标为中心，半径为2km的圆型区域内即可识别可疑目标是否为海盗船。 图1 可疑船只的

15、初始位置分布图根据相对运动概念可知，即可疑船只进入直升机半径为2km的圆型探测区域，就会被辨识。由于已知可疑船只的运行速度、方向、位置，则直升机在一点辨识完之后，能够预知到达下一个搜索目标的位置，从而使得可疑船只刚好在圆形探测区域的边界上。这样就将动态的可疑船只变为静态的。直升机飞行的最短距离由直升机的初始位置与目标在时间时所处的位置确定。ABA1B1 图2 最短识别时间的几何关系图2表示了最短识别时间的几何关系在时间内，直升机从运动到，可疑船只从运动到。则直升机至少要沿着直线飞行的距离。因此（5.1）在图2中，利用余弦定理，上面的式子可表示为（5.2）AA1B1avt+Rvit图3 最短时间

16、识别中的几何关系根据图3中最短时间识别中的几何关系，且、和都是已知常量，化简关系式就变成（5.3）所以，可由如下二次方程的根求得（5.4）如果，则上述方程有两个符号相反的根，易知（5.5）其中为方程的正根，表示超过的最小整数。如果，那么只有一条最短的识别路线；如果，那么就有无数多条可行的识别路线。5.1.2最优系数确定（1）搜索效能分析搜索效能即为在最短的时间内，尽可能快得辨识出更多的可疑船只。（2）层次分析法确定最优系数5.1.3聚类分析（1）综合考虑可疑目标的相对位置、航向和航速，利用spss软件进行聚类分析，得到图4。此时有两种分法，一是船只分为4、5、6、8和1、2、3、7、9、10两

17、类，二是分成十类。分析可知，分成两类过于粗糙，对搜索线路的优化帮助不大；分成十类，则没有参考价值。图4 可疑船只分类（2）忽略航向和航速，只考虑可疑船只的相对位置。可得图5的聚类图，船只可以分成4、5、8, 3, 6、7、9和1、2、10四类，或者3、4、5、8, 6、7、9和1、2、10三类。图5 可疑船只分类5.2问题一模型的建立5.2.1基于聚类分析和贪婪算法的优化模型在模型准备中，已经利用聚类分析将可疑船只进行了分类，分成了几块小区域。由于小区域内的可疑船只的位置相对集中，对船队的威胁程度差不多。因此小区域内的搜索，仅仅需要考虑时间问题。可以运用贪婪算法进行小区域内的搜索。贪婪算法为直

18、升机在辨识完一艘可疑船只后总是优先去搜索辨识距离最近的可疑船只。图0ABba6 船只航行图如图6，时刻，直升机位于原点，可疑船只位于点；时刻,直升机位于直线与圆的交点点，可疑船只位于圆周上的点。设在小区域中有个点。根据贪婪算法，在这段时间内，直升机飞行的距离应取直升机到该区域中所有可疑船只的辨识点中的最小距离，即（5.6），（5.7）则可建立基于聚类分析和贪婪算法的优化模型 （5.8） s.t5.2.2基于聚类分析和模拟退火算法的优化模型将直升机的初始位置编为0号，最终降落的位置编为11号。定义距离矩阵，其中表示两点的距离，则问题为从0点出发，走遍所有中间的点最后到达11点的最短路径问题。解空

19、间可表示为0,1,2，11的所有固定起点和终点的循环排列集合。即其中，每一个循环排序表示侦查10个目标的一个回路，表示在第次侦查目标。则可建立目标函数（5.9）设上一步迭代的解为，进行变换，任选序号交换成其顺序，得到新路径。此时路径差可表示为（5.10）。接受准则为（5.11）若，则接受新的路径；否则，以概率接受新的路径，即用计算机产生一个区间上均匀分布的随机数rand，若则接受。再进行降温，利用选定的降温系数进行降温，取新的温度为，本文选定。选定终止温度，当，退火过程结束。这样求得每一小区域内的最优路线，再确定小区域之间的优化路线，即可建立基于聚类分析和模拟退火算法的优化模型。5.3模型一的

20、求解5.3.1基于聚类分析和贪婪算法的优化模型的求解利用MATLAB软件求解，得总的辨识时间为502秒（这里不考虑返航），目标的具体辨识顺序为3 7 9 6 8 4 5 2 10 1。图7 问题一的最优搜索路线5.3.2基于聚类分析和模拟退火算法的优化模型的求解利用MATLAB软件求解。6 问题二的模型求解6.1问题二的模型准备问题二中有22个运动的可疑目标，并同时起飞两架舰载直升机去完成可疑船只的搜索任务。图8 问题二中可疑目标分布图忽略航向和航速，只考虑可疑船只的相对位置。同样先进行按相对位置进行聚类分析，将22个目标分成如图两块区域。 表1 区域位置分布表区域一20 22 1 14 18

21、 8 9 2 6 21 7区域二16 17 3 13 15 11 12 5 10 4 19分类图为图9则两架直飞机可分别搜索两块区域，且要使得任务尽量均衡，如果任务不均衡，再微调直线。在各区域内的搜索方式同样可以运用问题一中的搜索算法。6.2问题二的模型建立从问题一的求解来看，运用贪婪算法得到的搜索路线比运用模拟退火得到的搜索路线更优。因此在问题二的求解中，建立基于聚类分析和贪婪算法的优化模型。对于直升机1号和2号，分别建立方程（6.1）（6.2）s.t6.3问题二的模型求解利用MATLAB求解得，利用一架飞机辨识的次序为5 6 9 21 1 15 13 4 17 10 16总的辨识时间为12

22、56s。利用另一架飞机辨识的次序为8 2 22 14 7 12 11 3 19 18 20总的辨识时间是1568s。如图10，即为最优搜索路线。图10 问题二的最优搜索路线7 问题三的求解7.1问题三的模型准备问题三是在要尽量保护重要货船的情况下，同时求出搜索时间最短的两架直升机最优的飞行搜索辨识策略和路线。（1）危险性程度分析。由于无法确定哪一艘可疑船只为海盗船，因此认为每一艘是海盗船的概率相同。则货船的危险性有两个方面，一是可疑船只离货船很近，一是有更多数量的的可疑船只靠近货船。则以任意时刻可疑船只离货船的最短距离的大小和离货船较近的船只数量多少作为评判危险性的标准。优化目标为使得可疑船只

23、离货船的最短距离最大，即（7.1）其中（7.2）（2）危险区域确定直升机在选择要搜索的小区域时，应优先考虑危险程度；直升机在小区域内搜索时应优先考虑距离。直升机开始搜索时，根据各小区域距离船队的平均距离定出危险1号区和危险2号区。两架直升机分别同时去搜索1、2号危险区。当其中一架直升机完成小区域搜索后，重新根据各小区域距离船队的平均距离定出危险3号区和危险4号区，先搜索完毕的直升机先去搜索3号，另一架去搜索4号危险区。先选择一个区域，计算该区域内的可疑船只到船队的平均距离。如图，在小区域中有三艘可疑船只，平均距离为（7.3）其中分别为点到1,2,3的距离。比较计算得出的所有平均距离，相互进行比

24、较，得到平均距离最小和第二小的两个区域。A123图11本题中货船有两处，一处在军舰跟随的舰队中，一处在坐标为处。有军舰跟随的货船可视为安全货船，坐标为处的货船为需保护货船。因此要派遣一架直升机先飞往需保护的货船附近的1号危险区7.2问题三的模型建立记货船的速度为，它的初始位置为，航向为，则货船航行的轨迹方程为（7.4）.记某个可疑目标的速度为，它的初始位置为，航向为，则该可疑目标航行的轨迹方程为（7.5），任意时刻可疑目标与货船的距离（7.6）求（7.6）式的最小值及对应的时间，利用（）就可以判断出该可疑目标对货船是否有威胁。7.3问题三的模型求解利用Matlab软件求解（程序见附录），我们求

25、得的22个可疑目标的（）数据见表2。表2 可疑目标与货船之间的最短距离数据编号时间（s）最短距离（km）威胁系数危险情况1539311.81872495924.51663486317.1033425154.6367540713.89296290113.56797472517.21418332816.4358933728.41841034299.539111471014.084412165338.65141323546.541514545718.63451526296.890016336013.11321731462.02431870961.380019296636.365920154329.1

26、18721177110.6286威胁最大22427521.2473我们先利用一架飞机首先辨识目标21，然后依次按照问题（1）中的规则辨识其余目标。一架直升机的辨识次序为21 9 6 8 5 10 17 4 13 另一架自身机的辨识次序为 15 16 3 11 7 19 14 12 2 22 18 1 20辨识目标21需要432秒，总的辨识时间为1865秒，另一架的总的辨识时间为1920秒。如图12即为最优路线。图12 问题三的最优搜索路线8 模型的结论分析（1）问题一解得的总的辨识时间为502秒（这里不考虑返航），目标的具体辨识顺序为3 7 9 6 8 4 5 2 10 1结果比较合理。（2）

27、问题二解得一架直升机的辨识次序为5 6 9 21 1 15 13 4 17 10 16总的辨识时间为1280s。利用另一架飞机辨识的次序为8 2 22 14 7 12 11 3 19 18 20总的辨识时间是1440s。则总的辨识时间应取较大的时间值。（3）问题三解得，保证安全的直升机的辨识目标的次序为21 9 6 8 5 10 17 4 13 15 16 进行快速搜索的直升机的辨识目标顺序为 3 11 7 19 14 12 2 22 18 1 20总共需要时间2330秒9 模型的优缺点分析与改进9.1模型的优缺点1.模型的优点（1）建立的模型有成熟的理论基础，有相应的软件支持，可信度较高。（

28、2）问题一所建立的模型原理简单，通俗易懂，求解简单易行。（3）模型假设比较贴合实际，对实际情况具有较强的指导意义。2.模型的缺点（1）进行聚类分析时，分几类的标准不够明确。（2）模型的部分假设比较理想化。9.2模型的改进（1）在直升机搜索的过程中，应该考虑一次同时辨识两个以上可疑船只的情况。（2）在实际护航任务中，应该考虑可疑船只对船队中货船的危险性。参考文献1李长明,舰载直升机反潜搜索最佳方案优选模型及应用J，科学技术与工程,16711815,2013。2孙向军,基于粒子群优化的反潜搜索研究J，火力与指挥控制，3240，19933占科鹏,航空反潜搜索区域优化问题J，火力与指挥控制，16,18,20144卫翔,反潜搜索方案的形式化描述与效能计算J，科学技术与工程，7181,19955袁俊华,运动目标快速搜索辨识的路径规划J，科学技术与工程，356358,20026张圣云,反潜飞机对潜搜索法研究J，火力与指挥控制，6876,20057战凯,对策论在航空反潜搜索效能评估中的应用研究J，科学技术与工程，113120,1998