模拟退火算法之110巡逻问题.docx
- 文档编号:11097787
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:15
- 大小:317.84KB
模拟退火算法之110巡逻问题.docx
《模拟退火算法之110巡逻问题.docx》由会员分享,可在线阅读,更多相关《模拟退火算法之110巡逻问题.docx(15页珍藏版)》请在冰点文库上搜索。
模拟退火算法之110巡逻问题
警车配置及巡逻方案(2009全国研究生数学建模竞赛D题)
110警车在街道上巡弋,既能够对违法犯法分子起到震慑作用,降低犯法率,又能够增加市民的安全感,同时也加速了接处警(同意报警并赶往现场处置事件)时刻,提高了反映时效,为社会和谐提供了有力的保障.
考虑某城市内一区域,为简化问题,假定所有事发觉场均在下图的道路上.该区域内三个重点部位的坐标别离为:
(5112,4806),(9126,4266),(7434,1332)(见下图红点部位,蓝色部份为水域,道路数据见附件,相邻两个交叉路口之间的道路近似以为是直线).
某城市拟增加一批配备有GPS卫星定位系统及先进通信设备的110警车.设110警车的平均巡逻速度为20km/h,接警后的平均行驶速度为40km/h.警车配置及巡逻方案要尽可能知足以下要求:
D1.警车在接警后三分钟内赶到现场的比例不低于90%;而赶到重点部位的时刻必需在两分钟之内.
D2.使巡逻效果更显著;
D3.警车巡逻规律应有必然的隐蔽性.
请回答以下问题:
一.若要求知足D1,该区最少需要配置多少辆警车巡逻?
二.请给出评价巡逻效果显著程度的有关指标.
三.请给出知足D1且尽可能知足D2条件的警车巡逻方案及其评价指标值.
一.问题分析
本题主要讨论的是社会安全系统中警车的优化配置及巡逻方案的合理安排问题.在肯定需配置警车的数量和巡逻方案时,第一要考虑的问题应是如何在知足接警时限要求的前提下,用尽可能少的警车最大限度地覆盖城市道路.同时,需要在使巡逻效果尽可能显著的目标下对巡逻道路进行具体计划及对警车进行合理调度.另外,该问题中的模糊概念有很多,需要通过自己的理解和对资料的查询对其进行合理的假设和概念.
第一,道路的合理离散化问题和重点部位的处置问题.题目中已经明确指出假定所有事发觉场均在道路上,可是由于道路是持续的,且题目所给的数据均是交叉路口的坐标,使得处置问题存在困难,所以为了方便处置,能够将道路合理离散化,把每条道路离散成若干个点,然后把这些新增加的点作为新的路口,由此取得一张新的道路地图.另外,题目中给出了三个重点部位的坐标,这三个重点部份并非是都在交叉路口或道路上,所以在处置时需要对其进行近似处置,把不在道路上的点近似到离该点最近的道路上,然后再对该条道路进行离散化处置.如此处置后的道路地图如下所示:
图6.5.1道路离散图
第二,警车的巡逻模式问题.题目中并未明确说明在巡逻进程中警车是不是必需始终处于运动状态.若是假设警车在巡逻进程中不是始终处于运动状态,那么从花费的角度来讲或许会比较好,而且针对第一问计算出来的警车数量或许会比较少,可是从实际动身,该假设是不可行的.题目中指出警车在道路上巡逻,既能够对犯法分子起到震慑作用,又能够增加市民的安全感,同时也加速了接处警时刻,提高了反映时效.而且通过查询实际生活中警察的巡逻线路发觉,要求警车在巡逻进程中始终处于运动状态是加倍合理加倍切近实际的,如此能够使巡逻效果更显著.
第三,邻域和覆盖率概念的提出.为了处置方便,提出了邻域和覆盖率的概念.其中,每一个路口的邻域是指,以该路口为中心点,在接警后三分钟内能够抵达的路口点的集合,也就是说该邻域内任一点到中心点的最短路小于警车以接警速度行驶3分钟的路程.对于道路离散化后取得的路口点也有相同的概念.另外,还提出了覆盖率的概念.覆盖率是指所有警车在接警后3分钟内能够抵达的道路(线段)长度之和与图中所有道路总长度之比.那么把道路合理离散化后以点来考虑,则覆盖率又可概念为所有警车邻域的并集所包括的点数与总的点数之比.虽然覆盖率别离以线和点来概念有所不同,可是当离散慢慢细化后,以点概念的覆盖率也将逐渐逼近于以线概念的覆盖率.当离散细化到必然程度后,这种误差能够忽略不计.这种处置方式能够在知足精度的条件下,将问题的规模降维(由线降为点),进而难度大大降低.
第四,巡逻效果指标的理解问题.题目中要求所设计的方案使巡逻效果加倍显著,咱们以为巡逻效果指标包括覆盖率、巡逻抵达率、平均巡逻强度及其均方差等等,而平均巡逻强度及其均方差又与巡逻次数和相对人口密度值有关.其中,覆盖率上文已给出相关概念.若是在正常巡逻的线路中,至少有一辆警车抵达过某个离散道路点,则称该点为抵达点.对于整个系统,所有的抵达点数占总离散点数的比例称为该方案的巡逻抵达率.巡逻次数是指在不影响接警后抵达时刻的基础上,警车正常巡逻时各个离散道路点点的被巡逻次数.另外,由于在实际情形下不同街道的人口密度(数量)不同,在讨论巡逻效果指标时还需要考虑人口密度,人口密度大的地方需要的巡逻强度高于人口密度低的地方.假设某点的人口密度正比于该点周围必然距离内的街道密度,那么能够概念某点的相对人口密度值为:
以该点为中心,以半径r的圆所覆盖的道路的总长度.当把道路合理离散化后,其相对人口密度值即为相应圆所覆盖的离散点的个数.例如下图所示的两点A和B:
图6.5.2人口密度示用意
依照上面的概念方式,它们的人口相对密度别离为18和43.平均巡逻强度及其均方差的概念与巡逻次数和相对人口密度值有关,概念起来比较繁琐,具体方式见第四部份.综上所述,要想使巡逻效果越显著,就要相应地使覆盖率、巡逻抵达率、平均巡逻强度及其均方差的加权函数越大.
第五,巡逻规律隐蔽性的理解.题目要求警车巡逻的规律要有必然的隐蔽性,对于线路的隐蔽性,因此能够理解为线路的复杂性和无规律性.也就是说若是希望线路的隐蔽性好,就需要选择分岔道口相对较多的巡逻线路,而且同一警车每次的巡逻线路能够有些不同,主要体此刻所走的交叉路口的前后顺序方面.比如图6.5.3中的两条线路,假设它们都是属于同一点的邻域内,那么警车会选择第二条线路,而且每次巡逻时能够选择不同的走法,也就是说第一次巡逻能够选择A→B→C→D→E的走法,第二次能够选择A→C→E→D→B的走法.
图6.5.3隐蔽性解释
通过上面的分析,能够采取静态优化和动态优化相结合的方式成立模型,利用模拟退火算法和动态仿真,给出知足不同条件下的相对最优巡逻线路.主要的处置进程是:
第一对道路和重点区域进行合理离散化,使得二维的道路转化为一维的点来考虑;再按照离散化后取得的新地图计算出各个离散道路点的邻域;然后对静态进程利用模拟退火算法取得静态优化值;最后按照不同的目标和需求,通过对动态进程进行仿真,从而取得最后知足要求的动态优化值,并依照问题要求给出所需的评价值和合理的警车巡逻方案.
二.问题一的分析及结果
1.模型成立的整体思想
第一问只要求知足条件一中关于出警时刻的要求,即只需要覆盖率达到必然要求,可与巡逻效果无关,从而肯定最少需要配置的警车数量.因此能够先针对警车为静态的情形进行优化,取得静态时为达到覆盖率要求所需要的最少车数n.现在取得的n是在一个接近最优的散布下知足覆盖率的最小要求.但处于实际情形和前文中的假设,警车必需始终以必然的速度进行巡逻,那么随着时刻的演化,警车的散布是动态转变的,就有可能偏离那个优化散布,进而在某些时段内不能知足覆盖率的要求.因此,考虑动态情形时所需的最小车辆数必然大于或等于静态情形时优化取得的车辆数.对本问的处置能够采取静态和动态相结合的方式:
第一利用静态优化取得一个结果状态,包括了所需的最少车辆数和那个优化状态的车辆位置散布.第二,以那个状态作为动态仿真的初始状态,对时刻进行演化.演化的目标函数为:
(1)覆盖率的增加;
(2)三个重点部位必需被覆盖.
若是演化时段内各个时刻的覆盖率都能够达到90%的要求,且重点区域都能在两分钟内抵达,那么那个车辆数就是可行的.反之,则应增加车辆数.再利用动态仿真,优化和查验增加车辆数后是不是能知足相应条件.那个迭代进程一直到第一次知足要求为止.总的进程如下图所示:
图6.5.4问题一的优化流程
2.问题一求解的模拟退火算法
第一依照问题分析中所提到的,在道路离散化后所取得的新地图上考虑问题.设有m辆警车和N个交叉路口,对于每一个路口有一个邻域,并记第i个路口的邻域为
.咱们的目标是要寻觅m个路口,使适当每一个路口有一辆警车时,m个邻域的并集所含的点数最多.
(1)解空间:
解空间
可表示为从
当选出m个元素的所有可能组合的集合,即
初始解能够选为
.所有状态的转移都是在解空间里进行的.
(2)目标函数:
任一集合
中的元素个数计为
.现在目标函数为m个邻域的并集的元素个数的极大值,即求
(3)新解的产生.当前解
.对于任一辆车,不妨设为第i辆车,其此刻处在路口
.这时新解的产生有两种方式:
(a)邻点法:
在
的相邻点中任选一点
,新解为
;(b)邻域法:
在
的邻域内任选一点
,新解为
.在算法中将上述两种方式交替利用.
(4)目标函数差:
(5)同意准则.由于为最大优化问题,所以同意准则为:
即当
时以概率1同意新解为当前解.当
时,则以概率
同意新解为当前解.其中
为控制参数,
为冷却参数.
模拟退火算法搜索结果及分析
下表列出了在不同警车数量下通过模拟退火算法搜索取得的优化覆盖率结果:
表6.5.1模拟退火算法搜索结果
警车数目
优化覆盖率(%)
12
13
14
15
16
从表中的结果能够看出,当警车数量达到16辆时,在优化散布下已经能够知足覆盖率大于90%的要求.按照前面的分析,咱们将以那个结果为初始状态进行动态仿真优化.
3.动态优化中的仿真模型
运算机仿真模型的成立能够分为两种方式:
时刻步长法和事件步长法.时刻步长法就是依照时刻流逝的顺序,一步一步地对系统的活动进行仿真.在整个仿真进程中,时刻步长固定不变.事件步长法是以事件发生的时刻为增量,依照事件发生的顺序,一步一步地对系统的行为进行仿真,直到预订的时刻结束为止.本题要求的警车随时刻演化的巡逻方案,因此应采历时刻步长法成立仿真模型.
当采历时刻步长法做运算机仿真时,其大体步骤为:
第一选取系统的一个初始起点为仿真时钟的零点,然后按如实际问题的需要,选定一个时刻步长.于是从仿真时钟的零点开始,每推动一个时刻步长,就对系统的活动和状态依照预订的规则和目的的进行考察、分析、计算和记录,直到预定仿真结束时刻为止.
●仿真模型的成立
(1)选按时刻步长.
时刻步长可通过下述方式肯定.第一,对于输出结果的要求,仿真结果要求每一个时刻距离1分钟输出一次各警车的位置坐标,因此仿真时刻距离至少要小于1分钟,而且最好为1分钟的因子,使得每一个输出时刻同时也是仿真经历的离散时刻.第二,由于警车巡逻时可能会在路口处转弯,那么在时刻步长内警车巡逻的路程长度必需短于所有路段的最小长度.综合考虑上面两个因素,当警车巡逻速度为20km/h时,时刻步长能够取为10s.
(2)推动原则
为了解决实际问题,将道路离散化成点,这相当于增加了交叉路口的数量.按照假设,警车只有到实际的路口(即原有的交叉路口)才存在选择路径的问题.为了避免短距离的贪婪算法致使的局部最优的情形,在为警车选择线路时,考虑的不是下一个点,而是下一个实际的路口.当警车位于某个实际的交叉路口时,计算若是警车位于与该路口直接相邻的各个路口整体的覆盖率,选择覆盖率最高的方向,而且允许车在路口进行掉头.
●仿真运行结果及分析
下面的两个表格给出了仿真结果(4小时)的统计信息.表1为警车数量不同时不同覆盖率所占的百分比信息.能够看出,当有16辆警车巡逻时,覆盖率达到90%以上的时段只有%.也就是说随着时刻的演化,系统状态专门大程度上偏离了静态优化的状态结果.由于假设警车始终是处在运动状态的,故静态优化的结果并非能知足题目要求,由此能够看出静态优化算法在处置此类问题时的局限性.当车数再增加一台为17辆时,情形取得专门大的改善:
90%以下的比例只占到%.当车数达到18时,则在所有仿真时段内,90%的覆盖率目标都能够取得知足.
对于题目的不同理解会取得不同的最小车数.若是是要求在所有仿真时段内平均覆盖率达到90%,那么17辆警车既可知足要求(表6.5.2).当理解为任一时刻覆盖率达到90%,那么18辆警车为最少配置.
表6.5.2仿真结果在不同覆盖率区间的散布
覆盖率(%)
16车
17车
18车
86~87
0
0
87~88
0
0
88~89
0
0
89~90
0
90~91
91~92
0
92~93
0
93~94
0
0
表6.5.3统计信息表
百分比(%)
16车
17车
18车
平均覆盖率
90%以上时刻的比例
100
图6.5.5中给出了当警车数量为18辆时,4小时内各个警车的巡逻轨迹图.虽然这时知足了覆盖率和保护重点部位的要求,但警车巡逻的范围较小.若是将威慑作用理解为与巡逻抵达范围的大小相关的话,那么现在的巡逻方案必然不是比较好的结果.这时就需要考虑除覆盖率之外的指标对巡逻方案进行优化.
图6.5.5警车数量为18时,各个警车的巡逻轨迹
三.问题二和问题三的分析及结果
1.问题二的指标分析
由问题一的结果能够看出,若是仅仅以条件一作为优化目标,取得的巡逻轨迹并非睬想,有些警车的巡逻线路太短,仅局限在比较狭小的区域内.这时就必需考虑其它评价巡逻效果的指标.在问题分析中,已经说明了巡逻效果指标包括覆盖率、巡逻抵达率、平均巡逻强度及其均方差等等,而且给出了相应的概念.下面还需要作出较详细的讨论.
(1)覆盖率
覆盖率是一个重要的指标.在问题一中仅仅考虑了这一个指标作为优化目标.覆盖率是指所有警车在接警后3分钟内能够抵达的道路(线段)长度之和与图中所有道路总长度之比.那么把道路合理离散化后以点来考虑,则覆盖率又可概念为所有警车邻域的并集所包括的点数与总的点数之比.虽然覆盖率别离以线和点来概念有所不同,可是当离散慢慢细化后,以点概念的覆盖率也将逐渐逼近于以线概念的覆盖率.当离散细化到必然程度后,这种误差能够忽略不计.这种处置方式能够在知足精度的条件下,将问题的规模降维(由线降为点),进而难度大大降低.
简单来讲,覆盖率就是警车在同意报警后规按时刻内赶往现场处置事故的能力.覆盖率越大,警察能掌控的有效面积就越大,巡逻效果越好.覆盖率有瞬时和平均之分.对于每一个时刻,概念的覆盖率称为瞬时覆盖率,表示为
.若把一段时刻范围内的瞬时覆盖率对时刻取平均值,则称其为平均覆盖率,表示为
.
(2)巡逻抵达率
若是在正常巡逻的线路中,至少有一辆警车抵达过某个离散道路点,则称该点为抵达点.对于整个系统,所有的抵达点数占总离散点数的比例称为该巡逻方案的抵达率.若以
记录某个方案中点i是不是为抵达点,那么有:
;
则该巡逻方案的抵达率
概念为:
;
抵达率越高的话,巡逻的效果也越好.
(3)平均巡逻强度及其均方差.
若以
,
别离表示第i个离散点处的人口密度值和抵达次数,则概念第i个点的巡逻强度为
,
巡逻强度综合考虑了人口密度和抵达次数的影响因素.若某点的巡逻强度越高,则对于该点的巡逻效果越好.概念巡逻强度的原因是因为考虑整个巡逻方案的效果时,抵达次数只是片面地反映了巡逻的效果,必需要同时考虑人口密度的影响,人口密度大的地方抵达次数也会相应地越多.例如i和j两点的人口密度别离为5和2,而抵达次数别离为4和3.单独考虑抵达次数的话,这两点的抵达频度不同,应该增加抵达j点的次数,从而使得巡逻方案更好.但是若是考虑到人口密度因素,通过巡逻强度那个指标来衡量的话,那么应该增加i点的抵达次数,因为由其概念显然有:
.
理想方案的巡逻效果应使得各点的巡逻强度尽可能地均衡.为此概念平均巡逻强度及其均方差为:
;
那么对于某个巡逻方案,平均巡逻强度越大且其均方差越小,那么该方案的巡逻效果越显著.
2.问题三中模型的成立求解与结果的分析
(1)主要思想在问题二中咱们给出了衡量巡逻效果显著程度的评价指标,包括覆盖率,巡逻抵达率,平均巡逻强度及其均方差等.在本问中,咱们考虑抵达率和巡逻强度的相关指标的影响,将它们添加到目标函数中,然后通过运算机仿真优化结果.
(2)仿真模型
如上所述,在这里只需成立新的目标函数既可.考虑到巡逻抵达率和巡逻强度及其均方差之间有必然的关联性,并非是完全独立的,这二者能够被以为是类似于低阶与高阶的关系.所以在仿真的规则设计中,设
,其中
为标志变量,
为控制参数,
别离为第i个候选点的覆盖率和巡逻强度.
为相应的归一化参数.程序演化时,将以控制变量
的值为依据,
值越大的也就越优.
(3)仿真结果
由于第一问中已经求得在动态的情形下,要达到条件一的最少车辆数为18.本题在条件一的基础上新增加了条件二.由于约束条件的增多,优化结果的车辆数必然大于等于18.在本题的仿真中,将从车辆数18开始优化,研究在不同车辆数条件下巡逻效果指标的好坏.下表给出了仿真的结果:
表6.5.4问题3的仿真结果
车辆数
平均覆盖率(%)
到达率(%)
平均巡
逻强度
巡逻强度
均方差
18
20
22
24
26
28
30
为了更直观地观察这些指标随车辆数的转变关系,故将其别离进行拟合,并在下图中表示出来:
图6.5.6指标拟合
上述四幅图中,平均覆盖率,抵达率,平均巡逻强度和巡逻强度均方差随车辆数的拟合曲线别离为
.
通过这几幅图容易看出,平均覆盖率、抵达率和巡逻强度均方差都随车辆数而呈负指数转变.当车辆数增大时,前二者增大的速度变慢,而巡逻强度均方差的降低速度减慢.不同的是,平均巡逻强度随车辆数的增加而线性增加.在这种情形下,平均巡逻强度将随车辆数持续增加,不会出现优化(即收敛)的趋势,因此能够不用考虑它的影响.对于会出现收敛的其它三个指标,当车辆数达到30辆左右时,其增加率已经很小,大体趋于零(尤其是对于抵达率).要想达到更优的结果,需要的车辆数必将迅速增加.在实际中,增加巡逻车辆肯定要有必然本钱,而在本题中并未考虑那个因素.因此,车辆数不能大量的增加.基于以上分析,能够以为当警车数量达到30辆时已经达到优化目标.在图6.5.7中咱们给出了这30辆车在仿真时段内的轨迹图.能够看出,除左下角外的一小段外,大体上所有的道路都被巡逻过,达到了专门好的效果.
图6.5.7问题三中30辆车4小时的轨迹图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 110 巡逻 问题