基于问题分解的卫星测控资源蚁群优化调度方法，张娜，柯良军，针对卫星测控资源优化调度问题，以卫星可见弧段为元素建立了一种新的加权独立集模型并提出一种多空间蚁群优化算法进行求解。该算中国酗技记又在线)将卫星的可见弧段视为图的顶点,并将其按工作时段分为个子集,分别表示各卫星在相应工作时段内的任务需求之和)将约束条件转化为图的边。如果两个顶点具有资源约束关系,则将其用实线相连,称为实边;由任务需求约束造成的顶点之间的互斥关系只在当前调度过程中有效,用虚线相迕,称为虚边。)优化目标的转化:定义关于的函数并将其转化为单个顶点的权重′∑越小,可见弧段的权重值越大。因此,式()可转化为:基于此,得到问题的加权独立集数学模型为(判定形式)实例:给定图,其中∪∪,对每个顶点∈,有权重正整数且≤|,正数>问题是否包含一个大小为+++的子集,即其中使得'中的任意两个顶点之间都没有边相连,并且满足∑多空间蚁群优化算法由」问题的复杂性,传统的数学规划方法难以求解该问题。自上世纪八|年代以来,许多彷生物系统的群体智能启发式算法相继岀现,其中受自然界蚂蚁觅食行为启发而提出的蚁群优化算法具有并行性、鲁棒性、全局优化等特点,适用于求解等大规模组合优化问题。本文针对问题解空间规模大且是稀疏的、易于分解的特点,提出种多空间蚁群优化算法,在对原问题分解的基础上,建立了适用于求解该问题的启发信息、信息素模式、协调机制及蚁群搜索方式。问题分解在将转化为求解最优了集问题后,问题的解空间由顶点集合的了集构成。由于顶点之间存在冲突关系,并不是所有的子集均为问题的可行解,因此解空间是稀疏的。棖据加杈独立集模型,顶点集合由个子集构成,目标是在每个子集内找到没有边相连的顶点集合,并使其性能满足预定要求,由此可知,该问题是可分的。为了减少算法的计算复杂度,提高蚁群搜索效率,根据该问题的可分性,将其分解为多个相互约束的子优化问题,每个子问题描述为:在图=中,是否存在子集,使得中的任意两个顶点间都没有边相连,并且满足∑>同时,各子问题间存在约束关系:任意两个子集与的顶点之间不能有边相连。为了保持原问题目标不变性,各子问题的优化目标必须满足国武技记文在线这样,每个子问题的搜索空间为∈。多空间蚁群算法中的蚁群每次仅选取一个子问题进行优化,相应的搜索空间为,从而降低蚁群的拽索规模,提高搜索效率。启发信息的定义利用中丰富的时间信息改置启发信息函数。蚁群首次对某子问题的搜索空间进行搜索时,随机选择一个页点将其加入当前解,并将该顶点的测控起止时间分别作为该子空间的开始时间和结束时间。当蚁群再次进入该搜索空间时,各选顶点的加入可使其工作时间延长,将延长部分时间长度的指数函数作为启发信息。的加入使工作时间延长△=△+△(),其中,顶点的启发信息为如果顶点具有较短延长时间,则其启发信息值较大,从而获得较髙的被选中的概率。当Δ时,顶点的测控窗口完仝位于原有的持续时间内,此时它的启发信息为最大值。点模式信息素由问题的加权独立集模型可知,图的边表示相连的两个顶点相互排斥,不能为蚁群提供行走的路径:同时,问题属一类子集求解问题,子集内各元素之间不具有顺序关系,因此不需要图的边作为行走路径。鉴于此,本文采用了一种点信息素的释放方式,将信息素释放在图的顶点上。基于点模式的伪随机比例状态转移规则为:为随机比例规则7B其中,τ,η分别为顶点的信息素和启发信息。在得到一个较好解时,对所有顶点更新信息素。点模式信息素更新规则为:++p·△z其中,为第次迭代所生成的解。国武技记文在线协调机制与改进型算法不同,蚁群算法从图中某一顶点出发,逐步选取合适的顶点并入当前解,直至完成该解的构建。这种解的构造方式易于设置协调杋制,处理各子闩题间的约束条件。协调杋制如下:蚁群在某搜索空间中选取顶点为解的元素后,删除当前顶点集合中与有边相连的顶点及相应的边,确保待搜索空间内不存在与解元素相连的顶点,避免在后续搜索过程中产生不可行解。处坦后的可行搜索空间为:其中,表示在当前节点集合中所有与有边相连的顶点集合。跳跃式搜索由各子问题间的约束关系及式()可知,较早优化的子问题将有更多机会选择较好顶点。针对此情況,本文提出了一种跳跃式搜索方法。图以单只蚂蚁的搜索过程为例,给图多空间蚁群优化算法跳跃式搜索机理示意图出了跃式的搜索机理,其中各虚线椭圆表示不同的子空间。在当前时刻蚂蚁随机选取一个未完成调度的子空间,根据状态转移规则()对其进行搜索,选出一个顶点并将其加入当前解中,然后跳入随机选取的下一个子空间。蚂蚁持续在各子空间间跳跃,直至所有的子空间都完成调度安排。蚁群的这和跳跃式搜索方式,使各子空间能否被蚁群选中处于完仝随机的状态,各子空间竞争优的弧段的不确定性增加,避免陷入局部优解。算法伪代码综上所述算法伪代码如下初始化各参数:;历史最好结果=;可行搜索空间蚂蚁随机选择一个满足<的候选链表国武技记文在线蚂蚁随机选择一个顶点∈根据式()计算所有∈的启发信息值蚂蚁根据式()选取一个顶点∈由式()得+时刻的可行搜索空间;计算本次调度指标根据式()对信息素进行更新;输出历史最好结果。算法复杂性分析根据算法伪代码,在可见弧段的总数为|,任务需求总数为,俑环次的情况下,关链步骤))行的时间复杂度为,)~)行为|其中,}。所以的时间复杂度为+|。由此可知,虽然为亢备问题,但通过对问题解空间的分解,可以有效降低算法的时间复杂度。实验分析在实验仿貞阶段,采用实现,并选用中国卫星测控网四组不同调度期的数据对其进行测试。由于涉及机密,表仅给出各组数据的基本情况。每组数据中卫星数目均为颗,但其中的卫星不尽相同,具体需求也有变化。从冲突弧段对数可以看到每组数据都有很高的冲突率。表四组数据的基木情况项目编卫星数设备任务可见弧冲突弧调度期数目需求段数段对数国武技记文在线为了分析的性能,将其与在问题领域应用较多的达代修正()算法做比较。算法从一个随机生成的解出发,利用专家知识逐步对当前解进行修正,以提髙解的性能,最终获得满意解。在对比实验中,各参数的取值如下:a=,B=,p=,它们均为绎过统计实验得到的一组较好值。以为例,表给出了在其他参数取值一定,取不同值时的统计实验结果。根据表,后续实验中取值为。表从工作总时间的长短和工作时段调度的优劣两个方面给出了与算法的调度结果。在对各工作时段的调度进行评价时,与算法互为参照,如果其中者将某工作时段的工作时间诚少以上,认为该工作时段获得更优的调度安排。优的工作时段个数指其中一者比另一者优的工作时段个数。优良率指或算法结果中优的工作时段(如果两者在某工作时段的调度相似,认为两者都达到优)与总的工作时段数之比。已知总工作时段数为,设为算法结果中占优的工作时段个数,为占优的工作时段个数。算法调度计划优良率为生成的调度计划的优良率为y表取不同值时次运行结果的平均值表与算法谓度结果优良项目编总时优良总时优良时优良时间段个率段个率数数由表可见,在四组调度计划的工作总时间上,的调度结果比算法分别减中国酗技记又在线平均每个调度期减少,这在很大程度上降低了工作人员的负担,提高了设备的利用效率的四组调度结果中获得较好调度的工作时段平均优良率达,高于算法的。以上分析表明,与算法相比,在满足约東条件的基础上,能够生成工作时间更短、各工作时段内可见弧段安排更合理的调度计划(a)s070618(b)s071203080.750.7嗤0.660.650.6420010030迭代次数迭代次数(c)so71224d)S0801070.720.7温温0.680.66学0:50.640.5300100200迭代次数迭代次数图的寻优性能图以()式作为解的性能评价指标,给出了代以内探索全局优解的性能曲线。从图中可以看到,在代左右即可接近全局优解,表明对问题的分解可以有效降低算法复杂度,以较快的速度收敛到较好解。在后续迭代过程中,仍有新的优解不断被发现,这表明以跳跃式选取子优化问题的方式可以有效避免陷入局部优解,提高算法的全局搜索性能。结论以卫星可见弧段为元素的加权独立集模型及基于多空间的蚁群优化算法的结合是问题求解方法的一种新的探索。加权独立集模型给岀了问题的一般化描述,形式史为简洁。卫星测控网四组薮据的仿真结果显示,较之该领域通用的迭代修正算法,基于多空冋的蚁群优化算法能够有效处理测控冲突,对解空间的搜索能力更强,生成的测控仼务调度计划⊥作时间更短、可见弧段安排更合埋。后续⊥作将以此为基础,研究中高轨卫星及中继卫星的数学模型及调度方法参考文献刘洋,贺仁杰,谭跃进.基于约束满足的多卫星调度模犁研究[].系统工程与电子技术,中国酗技记又在线金光.卫星地面站测控资源调度模型[].系统工程与电子技术,()杨萍,杨峰,吴斌用启发式算法和基于冲突的冋跳算法求解卫星测控資源调度问题[].宇航学报邢立宁,陈英武.基于混合蚁群优化的卫星地面站系统仁务调度方法[].自动化学报,作者简介:张娜,女,年生,博士研究生,主要研究方向是和资源优化调度及群体智能算法;柯良军,男玍生,博士,主要研究方向是智能优化算法和模式识别冯祖仁,男,年生,教授,主要硏究方向是杋器人学,智能计算和模式识别