贪婪随机自适应搜索法在电网规划中的应用

基于贪婪随机自适应搜索法(GRASP)能有效地解决电网规划的组合优化问题,其每一次迭代包含构造和局域搜索两阶段.在构造阶段,以改进线路综合有效性指标为贪婪函数,采用比例法形成限制候选列表,并随机选择元素构成可行方案.根据线路的实际效用比剔除可行方案中的冗余线路,为局域搜索提供一个简练经济的初始网络,并采用1-1交换产生邻居集来拓展搜索空间寻找局优解.所有迭代中的最好方案作为电网规划问题的最优解.对于网络规模增大所引起的“维数灾”,提出5种邻居删减技术来提高算法的解算速度.算例分析证明了该方法的可行性、有效性.

基于贪婪随机自适应搜索法的TTE通信调度算法

时间触发以太网(TTE)采用全局时间触发机制,使通信任务传输具有严格的时间确定性和无冲突性,适用于航空电子等混合关键应用领域。TTE网络提供3种不同的流量类型:具有低抖动和有界端到端延迟的时间触发(TT)流量,有限制端到端延迟的速率约束(RC)流量和无实时性保证"尽力传"(BE)流量。针对可满足性模理论(SMT)等调度算法在生成TT流量离线时刻调度表的过程中,未综合考虑TT流量路由和时刻调度表对RC流量延迟产生影响的问题,为了优化TTE网络实时性能,提出了一种基于贪婪随机自适应搜索算法的TTE通信任务调度算法。在TT流量离线调度表的生成过程中考虑了RC流量的最坏端到端延迟(WCD),在保证TT流量满足可调度性的前提下,通过路由规划和调度时刻表规划降低了RC流量的WCD。对比实验结果表明:所提算法可以有效的提升整网的实时性能,通过A380拓扑组网案例的对比分析,RC流量的平均延迟减少了14.34%。网络中流量规模越大,所提算法的收益越大。

独立任务分配的贪婪随机自适应搜索过程

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。

适合于机组组合问题的贪婪随机自适应搜索模型

提出了一种求解机组组合问题的方法——贪婪随机自适应搜索过程(greedy randomized adaptive search procedure,GRASP)。该方法迭代过程分为解的构造和局部搜索2阶段。在解的构造阶段,构造贪婪函数,形成带限制的候选列表,然后随机选择列表中的成分形成初始组合,作为局部搜索的起始解。在邻域搜索阶段,提出了一种适合于机组组合问题的变邻域算法,利用此法对邻域搜索得到局部最优解,取迭代过程中的最好局部解作为问题的最优解。算例仿真结果验证了所提方法的优越性。GRASP算法不仅为解决机组组合问题带来了新的思路和方法,同时给求解其它含复杂约束条件的组合优化问题带来了生机。

基于贪婪随机自适应过程的多类型卫星联合任务规划技术

对地观测卫星任务规划问题需要考虑侧视、星上能量、数据容量和数据传输等多种约束,是一类复杂的组合优化问题,现有研究大多对问题进行了不同程度的简化。面向多种载荷类型卫星的联合任务规划问题,考虑上述多种约束,基于贪婪随机自适应搜索过程提出了一种新的混合算法对问题进行求解。实验结果表明,该混合算法在多星联合任务规划领域是可行有效的。

基于Arena的车间作业排序问题建模方法及其仿真优化系统设计

针对车间作业排序问题的固有复杂性和目标函数难于解析求解等特点,建立了一个优化与仿真的集成系统框架,并提出了一种新的建模求解思路:首先,以通用仿真工具Arena为平台,提出虚拟抢占规则,实现了车间作业排序问题的仿真建模。然后,以贪婪随机自适应搜索算法为基础,结合高级语言VB,利用面向对象编程思想,通过Arena类库,设计了一个通用的车间作业排序问题的仿真优化系统框架,从而实现了优化和仿真的外部集成。在该框架下,可引入各种随机因素,提高对实际系统的建模与求解能力。最后,通过实例验证了该方法的有效性。

区间负荷下的输电网灵活规划方法

建立了区间负荷下的输电网灵活规划模型,该模型考虑负荷的不确定因素,以投资成本最小为目标,以正常情况和线路N-1情况下的网络安全为约束,求解该模型得到区间负荷下满足正常情况和线路N-1情况下系统安全的输电网规划方案。根据区间至多切负荷量的数值来判别区间负荷下电网规划方案的安全性和安全程度,使用改进的贪婪随机自适应搜索算法快速求解该模型。6节点系统和某实际77节点系统的规划结果验证了该方法的正确性和有效性。

考虑合环约束的配电网重构方法

为避免用户停电,配电网合解环操作是电网调度部门通过重构调整运行方式的重要手段。文中建立了考虑合环约束的配电网重构模型,模型以线损最小为目标,同时考虑了正常运行方式和合环运行方式下的节点电压和线路功率限值约束。提出改进的贪婪自适应搜索算法求解所建模型,采用基于戴维南等值定理的配电网合环潮流算法验证合环安全性。该方法可求得配电网重构的具体合环操作步骤,确保重构过程中无新用户停电。两个系统算例的计算结果验证了所述方法的正确性和有效性。

大邻域多约束无人机数据收集路径规划

在公网受限的应急环境中,利用无人机辅助物联网能促进传感数据的及时传递。当考虑无线通信距离时,无人机作为移动收集器在有限续航时间内收集尽可能多的传感数据的路径规划可建模为足够近定向问题(CEOP)。现有求解CEOP的算法是逐个计算目标节点的访问顺序及其邻域内的采集点,这在节点邻域较大并覆盖周围多个节点时效率低下,这些方法也没有考虑数据传输时间和无人机遥控距离等约束。为此,建立了大邻域多约束无人机数据收集路径规划的数学模型,提出了基于贪婪随机自适应搜索过程(GRASP)的GRASP-LN算法进行求解。该算法不重复计算重合的采集点,而是维护路径每个航点采集的节点集合,无人机在每个航点悬停一段时间以收集集合内节点的数据。公开的CEOP数据集的实验结果表明,GRASP-LN比GSOA、VNS和GRASP_(opt)具有更好的求解质量和更短的计算时间。与基线算法GRASP_(opt)相比,GRASP-LN的路径奖励平均提高了5.86%,最大提高了14.91%,执行时间平均减少了69%,特别在节点邻域平均覆盖4.67个以上节点时,GRASP-LN的路径奖励和稳定性均优于GRASP_(opt)。考虑数据传输时间和无人机遥控距离约束的实验验证了GRASP-LN算法对考虑这些约束的无人机数据收集路径规划问题的有效性。

一种求解有向图最小反馈节点集的搜索算法

反馈节点集问题源于组合电路的设计,在预防计算机操作系统的死锁、VLSI芯片设计、计算机程序证明以及贝叶斯推论等方面都有极其重要的应用。最小反馈节点集问题是一个NP完全问题,很难准确求解。该文在计算流程、图的约减操作以及贪婪函数3个方面对以前求解该问题的贪婪随机适应性搜索算法作了改进。实验表明改进的算法无论在计算结果方面还是在计算稳定性方面都要优于前者,同时还在一定程度上减少了计算时间。

一种求解旅行商问题的混合路径重连算法

提出一种求解旅行商问题的新型混合路径重连算法,将贪婪随机自适应搜索方法的构建机制引入到路径重连算法中,从而在搜索过程中同时考虑解的质量及分散性。在重连过程中,将向导解的属性逐步引入到起始解属性中,以快速获得该线路上的最优解,并采用动态更新参考集策略加快收敛速度。实验结果表明,该算法的解质量优于其他算法。

基于可信性理论的输电网规划

建立了基于可信性理论的输电网规划模型,得到模糊不确定负荷下的电网规划方案。将可信度的概念引入模型中,作为评价模糊不确定负荷下电网规划方案优劣的指标,该指标具有明确的物理意义和严格的数学理论基础。利用最小切负荷问题的负荷边界特性,证明了给定可信度指标下输电网规划模型的求解可等价于区间负荷下输电网规划模型的求解。使用结合区间至多切负荷量理论的贪婪随机自适应搜索算法求解该模型,可求得给定可信度指标下的输电网规划方案。新模型的求解不受模糊负荷下实际数学模型的限制,具有较好的适用性和明确的物理意义。46节点系统算例的计算结果验证了该模型和算法的有效性。

考虑发电备用容量的输电网规划

在系统中留有一定的发电备用容量是确保电力系统安全可靠运行的重要措施之一。文中建立了考虑发电备用容量的输电网规划模型。该模型以线路投资成本最小为目标,引入任意一台发电机故障时系统的安全性约束以确保该故障下系统的发电备用容量可以被充分利用从而维持系统的安全性;引入网络可用传输能力约束以确保负荷增长时系统的发电备用容量能够有效传输到负荷点从而维持系统的安全性。使用改进的贪婪随机自适应搜索算法求解新模型。6节点、46节点系统算例的计算结果验证了所述方法的正确性和有效性。

不确定信息下的输电网规划新模型

在传统的确定性信息下的输电网规划模型的基础上,通过增加一些新的约束,使得规划后的网络具有一定的剩余传输容量以适应未来不确定负荷的变化。在新模型中,引入了线路负载率约束,使得规划后的网络能够适应未来长时小幅度的负荷不确定性波动;引入了区域负荷增长量约束,使得规划后的网络能够适应未来短时大幅度区域负荷增长的增长地点的不确定性。使用贪婪随机自适应搜索算法可以快速有效地求解新模型。新模型的建立无需对未来不确定负荷的负荷特性进行详细的数学建模,易于求解并有着更好的适应性。46节点系统算例的计算结果验证了该模型和算法的正确性及有效性。

改进遗传算法求解VRP问题

物流配送车辆路径问题(Vehicle Routing Problem,VRP)是一类具有广泛应用的NP-Hard问题,是解决物流配送效率的关键,传统方法寻找最优解的效率低、耗时长,往往找不到满意的解,导致物流成本过高。为了提高VRP寻优效率,降低物流运送成本,对基本遗传算法改进求解VRP问题。首先建立VRP的数学模型,然后基于贪婪随机自适应算法(Greedy Randomized Adaptive Search Procedure,GRASP)改进遗传算法的邻域搜索能力,生成遗传算法初始种群,最后利用遗传算法从GRASP生成的初始种群中找到最优解。计算结果表明,所采用的改进遗传算法可以更好的求解车辆路径问题,有效降低物流运送成本。

改进微粒群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种改进微粒群优化的求解算法。首先,由基于启发式信息的贪婪随机自适应算法得到工件加工顺序,个体最优的初始值不再是随机生成的初始值,而是由该工件加工顺序转化而成;然后,对个体最优解进行了交换型局部搜索;最后,通过对Car系列和Rec系列基准的测试,表明了该算法的有效性。

基于并行GRASP的不正常航班调度算法

将并行计算与GRASP结合,设计了一种新的基于并行GRASP的不正常航班调度算法,给出了详细的算法流程与步骤;同时考虑了使用备用飞机、延误航班与取消航班等不正常航班调度策略,通过并行GRASP算法优化了构造的飞机路线和取消路线组成的初始解,给出了每架飞机新的航班路线和航班取消路线。国内一家中等规模航空公司实际算例的结果证明了算法能有效降低以往算法的时间复杂度,明显提升运算效率,可用于较大规模的不正常航班调度运算。

求解多车型校车路径问题的带参数选择机制的GRASP算法

考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。

基于GRASP算法的飞机旅客一体化恢复优化研究

针对航班调整中较常用的手段——航班取消⁃合并方法,对飞机旅客一体化恢复问题进行研究。首先,基于连接网络和旅客转机网络建立数学规划模型,然后基于贪婪随机自适应搜索方法(Greedy randomized adaptive search procedure,GRASP),设计启发式算法求解该问题,并且在算法的每一次迭代中,都能得到基于航班调整的旅客转机的最优方案。最后,通过案例证明了算法的有效性,并且说明了相对飞机和旅客先后进行恢复,飞机和旅客的一体化恢复能够有效降低恢复成本以及受干扰的旅客数量。

混合装配线平衡排产协同优化新算法

装配线平衡和产品排序是紧密相关而且对目标值存在交互影响作用的两个NP-hard问题。文中基于这两个问题的交互影响以及贪婪随机自适应算法(GRASP)比较好的收敛速度和全局满意度,设计了协同优化贪婪随机自适应算法(COGRASP),并行协同地优化混合装配线,并用实例对此算法进行了仿真研究。此外,文中还考虑了可能存在的瓶颈工序对协同优化效果的影响,将一种基于OPT思想的关键资源调度方法融入原来的COGRASP中,通过相应实例验证,取得的效果也非常好。