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

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

基于免疫粒子群算法的多星观测调度研究

多星观测调度是一个复杂的组合优化问题,且为NP难题.目前常用解决方法是采用智能搜索算法在搜索空间寻找近似最优解.针对上述问题,首先探讨了国内外成像侦察卫星调度算法的研究现状,然后阐述了传统微粒子群优化算法与免疫粒子群优化算法的特点,并对带有多个时间窗口约束的多星观测问题建立了数学模型.在此基础上,提出一种用于解决多星观测调度问题的免疫粒子群算法.实验结果表明,免疫算法收敛速度快,可以很好地逼近精确解,并具有较强的搜索能力.     

成像卫星星地联合成像调度

成像卫星星地联合调度问题,涉及调度对象众多,约束条件复杂,需要考虑任务的观测、回传2个过程,是一个具有两层时间窗口约束的双层优化问题,统一建模困难。根据问题的特点,采用基于阶段优化的方式,降低了问题的复杂性。把问题分为观测调度阶段和数据回传调度阶段,分别给出了优化目标和约束条件,建立了基于阶段优化的成像卫星星地联合调度模型,实现了从任务观测到数据回传的全过程调度。仿真实例表明,该方法能够有效解决多星多站的协同任务调度问题。     

置换表示方法求解多卫星多地面站调度问题

针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.     

基于模拟谐振子算法的多项目调度

针对资源受限多项目调度问题(RCMPSP),介绍了一种模拟谐振子算法。算法通过模拟简谐振动系统中势能状态的变化,从经典简谐振动阶段过渡到量子振动阶段,从而实现全局搜索到局部搜索的变化过程;同时,两阶段的搜索形式使算法的收敛精度和搜索效率得到了保证。采用基于排列的方法和串行项目进度生成机制,结合多项目的任务列表,可以保证所得调度方案满足项目优先关系约束。运用标准测试函数对算法进行了测试,结果表明算法具有高质量的搜索效率和精度。最后给出了三组多项目调度算例。     

基于Petri网和混合蚁群算法的多星成像调度

提出一种基于综合指标Petri网和混合蚁群算法的多星成像调度策略。在综合指标Petri网变迁中引入指标信息,处理多星并发观测和卫星资源竞争关系、反映卫星能量和存储等约束,使得问题描述更直观和完备。设计一种嵌入局部搜索技术的蚁群优化算法,通过启发式信息综合变迁中的指标,引导蚂蚁进行全局搜索。仿真实例结果表明,该策略能有效求解多星成像调度问题,实现全局搜索和快速收敛的平衡。     

TSP问题的一种改进的GRASP算法

本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。实验结果表明,本文提出的GRASP能够在合理的时间内得到很好的解,并且解的质量优于M~rinakis等提出的扩展邻域GRASP算法得到的解。     

资源受限多项目调度问题的两阶段算法

在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限多目标项目调度问题模型.该模型是对传统多模式资源约束项目调度问题更接近研发项目群实际的扩展.针对模型提出两阶段优化算法,第1阶段是项目时序约束优化阶段,采用蚁群算法(ACO)进行任务列表的优化求解,通过对信息素增量规则的改进、串联进度生成机制(SSGS)及资源冲突消解策略的使用,使蚁群算法的求解效率和质量得以提高;第2阶段是资源约束优化阶段,以第1阶段求得的优化任务列表为输入,逐项对人力资源约束进行核查与调整,最终生成项目调度的优化方案.数值实验表明,考虑胜任力差异的数学优化模型更符合研发项目群管理实践,同时两阶段算法在求解质量方面具有良好性能.     

基于改进烟花算法的密集任务成像卫星调度方法

传统卫星调度模型一般比较简单,当问题规模较大、任务比较集中时,往往会出现任务之间相互排斥,任务收益较低等缺点。针对这个问题,提出一种基于改进烟花算法（IFWA）的密集任务成像卫星调度方法。该方法在分析密集任务处理及成像卫星观测特点的基础上,首先对任务进行合成约束分析,然后基于合成任务综合考虑成像卫星可观测时间、任务间姿态调整时间、成像卫星能量和容量等约束因素,建立基于任务合成的多星密集任务调度约束满足问题（CSP）模型,最后改进烟花算法对该模型进行求解,利用精英选择策略在保证种群多样性同时加快了算法的收敛,得到较优的卫星调度方案。仿真结果表明该模型相比没有考虑任务合成因素,收益平均增加30%~35%,改进算法后效率上提升32%~45%,有效保证了调度方案的可行性和有效性。     

基于改进蚁群算法的成像卫星调度方法

成像卫星调度问题中约束条件数量众多且复杂,战场环境中,快速决策的要求增加了成像卫星任务调度的难度。针对这个问题,提出了一种加入精英策略的改进蚁群算法的多卫星成像调度方法,对算法的状态转移规则、信息素更新规则做了详细描述;并提出了基于启发式规则的任务路径处理流程,以此产生调度方案,评价路径优劣,反馈给蚂蚁路径搜索阶段。通过实例计算,并与贪婪算法和遗传算法结果对比,说明本方法能够获得更高质量的求解结果。     

A reactive GRASP for a commercial territory design problem with multiple balancing requirements

In this paper we present a reactive GRASP approach to a commercial territory design problem motivated by a real-world application in a beverage distribution firm. The mathematical framework includes, as planning criteria, minimizing a measure of territory dispersion, balancing the different node activity measures among territories and territory contiguity. The proposed GRASP approach incorporates several features such as reactivity, by allowing self-adjustment of the restricted candidate list quality parameter, and filtering, which avoids executing the local search phase in unpromising bad solutions generated by the construction phase. The algorithm has been tested in several data sets. The results show the effectiveness of the proposed approach. It was observed that the reactivity and the filtering proved very useful in terms of feasibility with respect to the balancing constraints, and find more robust solutions when tested over the basic GRASP. The local search scheme proved to be very effective as well. Moreover, the proposed approach obtained solutions of much better quality (in terms of both its dispersion measure and its feasibility with respect to the balancing constraints) than those found by the firm method in relatively fast computation times.     

A guided reactive GRASP for the capacitated multi-source Weber problem

The capacitated multi-source Weber problem entails finding both the locations of capacitated facilities on a plane and their customer allocations. A framework that uses adaptive learning and functional representation to construct the restricted candidate list (RCL) within a greedy randomized adaptive search procedure (GRASP) is put forward. An implementation of restricted regions that forbids new facilities to be located too close to the previously found facilities is also embedded into the search to build up the RCL more efficiently. The performance of this GRASP based approach is tested on three classes of instances with constant and variable capacities. Very competitive results are obtained when compared to the best known results from the literature.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

A greedy random adaptive search procedure for the weighted maximal planar graph problem

The weighted maximal planar graph (WMPG) problem seeks to find a subgraph from a given weighted complete graph such that the subgraph is planar—it can be embedded on the plane without any arcs intersecting. The subgraph is maximal—no additional arc can be added to the subgraph without destroying its planarity and it also has the maximal sum of arc weights. In this paper, the main objective is to develop, implement and empirically analyse a new greedy random adaptive search procedure (GRASP) to solve the WMPG problem. A dynamic strategy to update the restricted candidate list is proposed. An efficient data structure is developed for the Green&Al-Hakim (GH) construction heuristic. The data structure reduces the GH complexity from O(n³) to O(n²). The GH heuristic with the data structure is then integrated with advanced moves neighbourhood to develop an efficient GRASP implementation. Further, we investigate the behaviour of GRASP parameters in relation to the problem's characteristics. Finally, the developed algorithms are compared with the best-known procedures in the literature on a set of 100 test instances of sizes varying from 20 to 100 nodes.     

A path cost-based GRASP for minimum independent dominating set problem

The minimum independent dominating set problem (MIDS) is an extension of the classical dominating set problem with wide applications. In this paper, we describe a greedy randomized adaptive search procedure (GRASP) with path cost heuristic for MIDS, as well as the classical tabu mechanism. Our novel GRASP algorithm makes better use of the vertex neighborhood information provided by path cost and thus is able to discover better and more solutions and to escape from local optimal solutions when the original GRASP fails to find new improved solutions. Moreover, to further overcome the serious cycling problem, the tabu mechanism is employed to forbid some just-removed vertices back to the candidate solution. Computational experiments carried out on standard benchmarks, namely DIMACS instances, show that our algorithm consistently outperforms two MIDS solvers as well as the original GRASP.

     

A GRASP metaheuristic for microarray data analysis

The Weighted Gene Regulatory Network (WGRN) problem consists in pruning a regulatory network obtained from DNA microarray gene expression data, in order to identify a reduced set of candidate elements which can explain the expression of all other genes. Since the problem appears to be particularly hard for general-purpose solvers, we develop a Greedy Randomized Adaptive Search Procedure (GRASP) and refine it with three alternative Path Relinking procedures. For comparison purposes, we also develop a Tabu Search algorithm with a self-adapting tabu tenure. The experimental results show that GRASP performs better than Tabu Search and that Path Relinking significantly contributes to its effectiveness.     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

基于有序事件列表的高效复杂事件匹配算法

针对现有的复杂事件匹配处理方法存在的匹配代价高的问题,提出了一种利用事件缓冲区（有序事件列表）进行递归遍历的复杂事件匹配算法ReCEP。不同于现有方法利用自动机在事件流上进行匹配,该算法将复杂事件查询模式中的约束条件分解为不同类型,再在有序列表上对不同约束分别进行递归校验。首先,根据查询模式将相关事件实例按照事件类型进行缓存;其次,在有序列表上对事件实例执行查询过滤操作,并给出了一种基于递归遍历的算法来确定初始事件实例并且获取候选序列;最后,对候选序列的属性约束进行进一步的校验。基于股票交易模拟数据进行的实验测试和分析的结果表明,与当前主流的匹配方法 SASE和Siddhi相比,ReCEP算法能够有效地减少查询匹配的处理时间,总体性能上均更优,查询匹配效率提升了8.64%以上。可见,所提出的复杂事件匹配方法能够有效提高复杂事件匹配的效率。