高空飞艇航迹规划的多种随机搜索算法

高空飞艇航迹规划的多种随机搜索算法 高空飞艇航迹规划的多种随机搜索算法 2012-07-19#############2012-07-19######2#0#12-07-19######## 胡正东 ,夏青 ,蔡洪 ()国防科技大学航天与材料 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院 ,湖南 长沙 410073 摘要 :针对高空飞艇的航迹规划问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 进行了分析和计算 。考虑到高空飞艇的飞行特征 ,首先对其航迹规划问题进行了适当 ( ) 简化 ,转变为求解巡回旅行商问题 TSP,并给出相应的数学描述 ; 然后在此基础上介绍遗传算法 、蚁群算法和模拟退火算 法 ,并运用这三种随机搜索算法求解高空飞艇最优航迹 ;最后通过仿真算例简要地分析和比较了各个随机搜索算法的性能 。 仿真结果表明以上三种随机搜索算法对于解决规模较大的高空飞艇航迹规划问题是行之有效的 ,求解效率高于传统搜索算 法 。 关键词 :高空飞艇 ,航迹规划 ,巡回旅行商问题 ,随机搜索算法 ,遗传算法 ,蚁群算法 ,模拟退火算法 中图分类号 : TP183 文献标识码 : A Ran dom Sea rch in g A lgor ithm s of Rou te P lann in g for H igh A lt itude A ir sh ip s HU Zheng - dong, X IA Q ing, CA I Hong ( )Co llege of A e ro sp ace and M a te ria l Enginee ring , N a tiona l U n ive rsity of D efence Techno logy, Changsha H unan 410073 , Ch ina A BSTRAC T:A na lysis and ca lcu la tion of rou te p lann ing of h igh a ltitude a irsh ip a re ca rrie s ou t in the p ap e r. F irstly, con side ring h igh a ltitude a irsh ip s’ fligh t cha rac te ristic s, th is p ap e r tran sfo rm s p rop e rly the rou te p lann ing p rob lem s in to TSP and p u ts fo rwa rd a co rre spond ing m a them a tica l de sc rip tion. Then, the m a in app roache s re sp ec tive ly ba sed on ge2 ne tic a lgo rithm , an t co lony a lgo rithm and sim u la ted annea ling a lgo rithm a re p re sen ted fo r sea rch ing op tim a l rou te . A nd fina lly the p e rfo rm ance of each a lgo rithm is ana lyzed b riefly by a sim u la ted exp e rim en t. The effec tivene ss of the th ree random sea rch ing a lgo rithm s fo r so lving la rge - sca le rou te p lann ing p rob lem s is illu stra ted th rough sim u la ted re2 su lts, and the ir effic iency is h ighe r than tha t of trad itiona l random sea rch ing a lgo rithm s. KEYW O RD S: H igh a ltitude a irsh ip; Rou te p lann ing; TSP; R andom sea rch ing a lgo rithm; Gene tic a lgo rithm; A n t co lony a lgo rithm; Sim u la ted annea ling a lgo rithm ,并通过仿真计算对以上各 来求解高空飞艇的航迹规划问题 1 引言 [ 1 ]种算法性能进行了比较分析 。 高空飞艇 是一种轻于空气的无 人飞行器 , 以太阳能 转化成的电能为主要能源 , 再生式燃料电池为辅助能源 , 采 2 问题描述 用电驱动螺旋桨或者新型离子推进器 ,能在 20 ,30 km 的高 高空飞艇主要用于对地观测和空间运输 ,其航迹规划的 空范围内定点悬停或低速机动飞行 。飞艇的工作时间一般 任务就是设计一条能量最省的飞行路径 ———由一系列结点 只受天气 ,故障和例行维修的限制 。与飞机相比具有覆盖范 ()包括出发点和所有目标点 所构成的闭合回路 。由于高空 围大 、荷载量大 、低 消 耗 、低 噪 声 、污 染 少 、隐 身 性 能 强 等 特 (飞行不存在空间障碍 ,若忽略外界影响 如风 、雷电 、昼夜变 点 ;与卫星相比 ,飞艇又具有空间分辨率更高 、性价比更好 、 ) 化等 ,则能量最省意味着闭合回路距离最短 。因此 ,高空飞 更安全等特点 。 ( 艇的航迹 规 划 问 题 实 质 上 就 简 化 成 著 名 的 TSP Trave ling 航迹规划是在保证完成目标任务的前提下预先进行的 )Sa le sm an P rob lem 问题 。 飞行器最优路径设计 。对于高空飞艇而言 ,由于能量获取受 [ 2 ] 。本文分别采用遗传算法 、蚁群算法和模拟退火算法 最省 到时间限制 ,因此我们一般将航迹规划的优化指标选为能量 TSP问题的描述十分简单 , 简言之 , 就是寻找一条最短 的遍历 n个结点的最短路径 , 或 者 说 搜 索 自 然 数 子 集 X = 2012-07-19#############2012-07-19######2#0#12-07-19########)({ 1, 2,?, n} X 的元素表示对n个结点的编号的一个排列 ) (取最小值 , 式中的 d V , V 表示结点 V 到结点 V 的距 i i +1 i i+1 STEP5:按照变异概率随机交换某一个体的两位基因 ,然 离 。 ; 后将个体添入新群体 () 用图语言来描述 TSP:给出一个图 G = V , E , 每边 e ? STEP6:返回 STEP2,直至满足迭代条件 , 此时的最佳个 ( ) ω E上有非负权值 e, 寻找 G的 H am ilton圈 C, 使得 C的总权 体即为所求的解 。 ω ( ) ( ) W C = e最小 。? 3. 2 蚁群算法 ()e?E C [ 6 ] () 蚁群算法 A n t Co lony A lgo rithm 是一种新的概率搜 [ 3 ] ( 几十年来 ,出现了很多近似优化算法 ,如近邻法 nea2 索算法 ,它利 用 生 物 信 息 激 素 作 为 蚂 蚁 选 择 后 续 行 为 的 依 ( ) ( ) re st ne ibhbo r、贪心算法 greedy a lgo rithm 、最近插入法 nea2 据 。即每只蚂蚁会对一定范围内其它蚂蚁散布的生物信息 ) ( ) re st in se rtion、最远插入法 fa rthe st in se rtion、双极小生成树 激素做出反应 , 依据生物信息激 素的强度在每一个道口对 ( )法 doub le m in im um sp ann ing tree等等 。近年来 ,有很多解决 多条路径选择做出概率上的判断并执行该选择 ,同时影响后 该问题的较为有效的算法不断被推出 ,例如 Hop filed 神经网 续蚂蚁的行为 ———后到者留下的信息激素会对原有的信息 络方法 、遗传算法 、蚁群算法以及模拟退火算法 。 激素进行加强 ,并如此循环下去 ,直到几乎所有的蚂蚁都走 TSP搜索空间随着结点数 n 的增加而增大 ,所有的路线 最短的路径为止 。 ( ) 组合数为 n - 1 ! /2。 5 个结 点的情形对应 12 条路线 , 10 对于航迹规划问题 ,使用蚁群算法需要注意以下三个方 个结点的情形对应 181440条路线 , 100个结点的情形则对应 [ 7 ] 面 : )1信息素的更新算法 一般有三种 : an t_quan tity模型 、 155有 4. 6663 ×10条路线 。在如此庞大的搜索空间中寻求最 优an t_de sity模型和 an t_cyc le模型 。前两种模型利用的是局部 解 ,对于 n > 30 常规方法和现有计算工具而言 ,存在诸多 的()信息 ,蚂蚁在完成一步 从一个结点到达另外一个结点 后更 计算困难 。实验 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ,对于的情况 ,遗传算法 、蚁群算法 、 模 新所有路径上 的 信 息 素 , 而 最 后 一 种 模 型 利 用 的 是 整 体 信 拟退火算法以及它们的一些改进算法能够有效地获得近 ()息 ,蚂蚁在一个循环 对所有 n个结点的访问 以后 ,更新所 () 似最优解 包括最优解 。 3 高空飞艇航迹规划的各种算法 有路径上的信息素 。因此 , 在求解 TSP 问题时 , an t_ cyc le 模 3. 1 遗传算法型性能比前面两种模型好 。 [ 4 ] ( )遗传算法 Gene tic A lgo rithm 是一种借鉴生物界自然 [ 8 ] )αβρ2蚁群算法中 、、等控制参数对算法性能有很大的 α影响 。值的大小表明留在每个结点上的信息量受重视 选择和自然遗 传 机 制 的 随 机 搜 索 算 法 , 从 任 一 初 始 种 群 出 的程度 , 其值越大 , 蚂蚁选择以前经过的路线的可能性越大 , 发 ,通过随机选择 、交叉和变异操作 ,产生一群更适应环境的 β但过大会使搜索过早陷于局部最小解 ;的大小表明启发式 个体 ,使群体进化到搜索空间越来越好的区域 ,并反复迭代 信息受重视的程度 , 其值越大 , 蚂蚁选择离它近的结点的可 直至收敛到问题的最优解 。 ρ能性也越大 ;表示 信息素的保留率 ; 如果它的值取 得 不 恰 对于航迹规划问题 ,其解的形式必定是结点编号的无重 当 ,得到的结果会很差 。这里采用参考文献 [ 8 ]给出的方法 ( )复性排序 ,因此路径表示 p a th rep re sen ta ition是处理此类问 来设置这些参数 。 题时基因编码的最自然 、最简单的表示方法 。例如 ,路径 5 - )3为了避免对同一个结点的重复访问 ,每一只蚂蚁都保 ( ) 1 - 7 - 4 - 6 - 2 - 3 可直接表示为个体 5 1 7 4 6 2 3 。这 存一个禁忌表 ,用于记录到目前为止蚂蚁已经访问过的结点 样 ,基本遗传算法的交叉操作生成的个体一般不能满足这一 集合 。禁忌表随着蚂蚁寻优过程作动态调整 。 [ 5 ] () 约束条件 。为此 , 本文改用顺序交 叉 O rde red C ro ssove r 蚁群算法求解飞艇航迹规划问题的步骤如下 : STEP1:初操作 ,即当两个父个体交叉时 ,通过选择父个体 1 的一部分 , 始 化 迭 代 次 数 N C = 0, 限 定 最 大 迭 代 次 数 保存父个体 2 中结点码的相对顺序生成新个体 。同样 ,基本 N Cm ax,设置与信息素相关的控制参数以及蚂蚁数 ; STEP2:将遗传算法中的变异算子也需要修改 ,本文通过随机交换某个 各蚂蚁置于航路的起始点 ; STEP3:按转移概率将各蚂体的两基因位来实现变异操作 。选择运算可使用轮盘选择 蚁由当前结点移动到可行的 ( )算子 ,适应度函数取式 1的倒数 。 相邻结点 , 直 到 各 只 蚂 蚁 到 达 目 标 点 , 完 成 各 自 的 候 选 航 将这一问题的遗传算法求解步骤归纳如下 : STEP1:初始 路 ; 化迭代次数 gen = 0 ,产生初始种群 ,取定交 STEP4:记录本次迭代的最佳航迹 ; 叉概率 P、变异概率 P、代沟 GA P和种群规模 N IND ,限定最 jb STEP5:根据 an t_cyc le模型更新生物信息素强度 ; STEP6:大遗传代数 gen m ax; 更新禁忌表并 返回 STEP2 , 直至满足 迭代条件 , STEP2:计算群体中个体的适应度 ; 此时的最佳航迹即为所求的解 。 STEP3:使用选择算子 ,将适应度较高的个体复制后添加 4 从物理和化学的退火过程类推得来的 。其思路为 : 首先在高 度为 1. 5602 ×10。 ) λ 温下进行搜索 ,此时各状态出现的概率相差不大 ,可以很快 3模拟退火算法 :取温降系数 = 0. 99, 初始温度 T= 0 进入“热平衡状态 ”,这时进行的是一种粗搜索 ,即大致找到 系1000, 最低温度 T= 0. 01, 容忍阈值 N stop = 200, M e tropo lis f 抽样步数 N = 1000。30次仿真的最优航迹如图 4 所示 , 航迹 统的低能区 ;随着温度的逐渐降低 ,各状态出现概率的差 距4 长度为 1. 5385 ×10。 逐渐增大 ,搜索进度不断提高 。这就可以越来越准确地找 到 在给定的参数和仿真次数情况下 , 以上三种算法的求解 网络能量函数的全局最小点 。 性能参见表 1。 在模拟退火算法的 M e tropo lis抽样过程中 ,需 要在当前 ′解的近邻子集中寻找一个新状态 v。注意到航迹规划问题 的解结构 ,本文通过随机置换当前解的若干位上的数字顺序 (来产生新解 。此外 ,为了提高算法的搜索效率 结点数 n 较 )(大的情况 和搜索精度 “概率接受 较”差的解可能导致从最 优 ) ( ) 解处跳出 ,本文作出了两点改进 : 1 温度下降次后都没 有 ( ) 改善 ,即认为能量已降到最低 ,没必要再降温 ; 2 在算法 搜 )( 索过程中保留记忆中间最优解 ,并即时更新 。代价函数 C ?( )按式 1 计算 。 下面给出模拟退火算法求解航迹规划问题的主要步骤 : ) ( STEP1:随机选择初始状态 V = V 0 ,设定初始温度 T、 0 最低温度 T和容忍阈值 N stop; f 图 1 高空飞艇航迹规划任务点坐标 ′STEP2:由状态 V 随机置 换若干位生成新状态 V , 计算 ′Δ) (() C = C V - C V ; ′ΔΔSTEP3:若 C < 0, 则 V = V , 并记录该值为 B SF; 若 C > Δ-C / T (ξ0, 则计算概率 e ,若大于随机概率阈值 服从 0 - 1 均 ′) 匀分布 ,则取 V = V,否则保持 V 不变 ; S TEP4:返回 S TEP2, 直至满足设定的抽样步数 N ; (λ) λS TEP5:降温 , 令 T?T 为小于却接近 1的常数 ; S TEP6:检查 T是否小于 T, 若小于则算法终止 , 当前的 f B S F 对应最终 输 出 解 ; 否 则 , 先 判 断 B S F 是 否 已 连 续 N stop 4 算例分析 次未更新 , 是则算法终止 , 不是则转至 S TEP2。 下面通过一个具体算例分别说明遗传算法 、蚁群算法和 模拟退火算法在高空飞艇航迹规划中的应用 :设飞艇对某一 图 2 遗传算法求解飞艇航迹规划问题 () 区域若干点 共 31 个 进行对地观测并返回 , 各点坐标如图 () 1所示 , 要求确定飞艇的能量最省 即闭合回路航迹最短 轨 表 1 高空飞艇航迹规划的算法性能比较 迹 。 最优航 平均航 求解标 算法收 算法名称 考虑到遗传算法 、蚁群算法和模拟退火算法都是基于概 迹长度 迹长度 准差 敛速度 遗传算法 15476 15903 431. 8 较慢 (率的随机搜索方法 , 每次仿真输出的最优值 不一定是精确 蚁群算法 模拟较快 15602 15619 77. 3 )解 都可能存在 差异 , 因此 , 接 下 来 的 各 种 算 法 实 验 都 给 出 退火算法 较慢 15385 15950 536. 0 30次仿真的最优航迹 。 )1遗传算法 : 取种群规模 N IN D = 200, 最 大 遗 传 代 数 从仿真结果看 , 模拟退火算法能够搜索到的最优航迹长 g enm ax = 600, 交叉概率 P= 0. 7, 变异概率 P= 0. 01、代沟 j b 度是最短的 , 遗传算法其次 , 蚁群算法最差 ; 与之相反 , 从求 GA P = 0. 9。320次仿真的最优航迹如图 2 所示 , 航迹长度为 4 解标准差一项中可以看出 , 模拟退火算法虽然得到了最好的 1. 5476 ×10。 ) 解 , 但是多次仿真的标准差也最大 , 因此其解的稳定性不好 2蚁群算法 :取蚂蚁个数 m = 31, 最大迭代次数 N Cm ax α = 200, 表征信息素重要程度的参数 = 1, 表征启发式因子 — 57 — 空飞艇的航迹规划问题 , 期望获得一条过所有任务点的最短 路径 , 从而实现能量最省 。与传统的枚举法 、分支定界法 、割 平面法及动态规划法相比 , 这三类算法虽然不能保证精确求 出最优解 , 但是能获得近似最优解已大大提高了求解效率 。 通过仿真算例可以看出 , 这三种算法对于解决飞艇的航迹规 划问题都是行之有效的 。 遗传算法 、蚁群算法和模拟退火算法都是基于概率的随 机搜索算法 , 计算结果并不唯一 , 而且算法性能往往取决于 参数的设定 , 因此 , 仅仅从前面的仿真结果来评定各种算法 图 3 蚁群算法求解飞艇航迹规划问题 的优劣是没有太多意义的 。 参考文献 : [ 1 ] 王海峰 , 宋笔锋 , 王海平. 高空飞艇定点控制关键技术及解决 ( ) 途径 [ J ]. 飞行力学 , 2003, 23 4 : 5 - 8. 2 ] [ T L u tz, P Funk, J akobiA. Considera tions on L am ina r F low for a S tra tospheric A irsh ip P la tform [ R ]. D - 70550 S tu ttga rt, Germ any, 2003. [ 3 ] 粟塔山 , 等. 最优化计算原理与算法程序设计 [M ]. 长沙 : 国 防科技大学出版 , 2002. [ 4 ] 陈国良 , 等. 遗传算法及其应用 [M ]. 北京 : 北京人民邮电出 版社 , 1996. [ 5 ] 王小平 , 曹立明. 遗传算法 [M ]. 西安 :西安交通大学出版社 , 2002. 图 4 模拟退火算法求解飞艇航迹规划问题 [ 6 ] ) ( 温文波 , 杜维. 蚁群算法概述 [ J ]. 石油自动化 , 2002, 1 : 19 - 22. ———可能这次仿真搜索到的解最好 , 下次仿真则并非如此 。 [ 7 ] M acro D origo and L M Gam ba rdella. A n t Colon ies for the T ravelling 仔细分析不难发现 , 模拟退火算法和遗传算法流程中相对较 S a lesm an P roblem [ J ]. B ioS ystem s, 1997, 43: 73 - 81. [ 8 ] 多随机操作是导致求解稳定性不如蚁群算法的主要原因 。 叶志伟 , 郑肇葆. 蚁群算法中 、、参数设置的研究 [ J ]. 武汉大 从多次仿真的最优解变化过程可以看出 , 蚁群算法的收 ( ) 学学报信息科学版 , 2004, 29 7 : 597 - 601. [ 9 ] 敛步数都在 100 以内 , 而模拟退火算法和遗传算法基本上都 高晓静 , 等. 基于模拟退火算法的航迹规划方法研究 [ J ]. 微 需要迭代 400次以上才能收敛 。在当前的参数设定下 , 三种算 ) ( 电子学与计算机 , 2000, 5 : 10 - 14. [作者简介 ] 法的仿真时间大致相同 , 因此蚁群算法的收敛速度是相对较 ( ) () 胡正东 1982 - , 男 汉族 , 四川达州人 , 国防科 快的 。当然 , 过快收敛也可能使得蚁群算法更容易陷入局部 技大学博士研究生 , 研究方向为飞行器试验分析评 最优解 。 估及数据处理 ; 从参数设置来讲 , 遗传算法的参数设置最为简单 , 理论 ( ) () 夏 青 1981 - , 女 汉族 , 吉林公主岭人 , 国防 也较为成熟 ; 模拟退火算法主要是初始温度 T的设置 , 温度 0 科技大学博士研究生 , 研究方向为飞行器试验分析 太高会延长搜索时间 , 太低往往又会漏掉全局最优点 , 由于 评估与测控技术 ; ( ) () 蔡 洪 1967 - , 男 汉族 , 湖南娄底人 , 国防科技大学教授 , 研究 目前尚无成熟的结论 , 可采用由高到低的尝试法来确定 T; 0 方向为飞行器试验试验分析评估与精度鉴定 。 蚁群算法的参数设置相对复杂 , 参数设置不当会严重影响算 法性能 , 实现这些参数的最佳匹配需要一定的技巧 。 — 58 — Your requestcould not be processed becauseof a configurationerror: "Could not connect to LDAPserver." For assistance,contact your network support team. file:///C|/Users/Administrator/Desktop/新建文本文档.txt 涵盖各行业最丰富完备的资料文献,最前瞻权威的行业动态,是专业人士的不二选择。 file:///C|/Users/Administrator/Desktop/新建文本文档.txt2012/8/26 12:19:58