基于光纤-无线网络的协同计算卸载算法

随着无源光网络的发展,光纤-无线网络能同时支持集中式云和边缘云计算技术,成为一种具有发展前景的网络结构。但是,现有的基于光纤-无线网络的任务协同计算卸载研究主要以最小化移动设备的能耗为目标,忽略了实时性高的任务的需求。针对实时性高的任务,提出了以最小化任务的总处理时间为目标的集中式云和边缘云协同计算卸载问题,并对其进行形式化描述。同时,通过将该问题归约为装箱问题,从而证明其为NP难解问题。提出一个启发式协同计算卸载算法,该算法通过比较不同卸载策略的任务处理时间,优先选择时间最短的任务卸载策略。同时,提出一个定制的遗传算法,获得一个更优的任务卸载策略。实验结果表明,与现有的算法相比,本文提出的启发式算法得到的任务卸载策略平均减少4.34%的任务总处理时间,而定制的遗传算法的卸载策略平均减少18.41%的任务总处理时间。同时,定制的遗传算法的卸载策略与本文提出的启发式算法相比平均减少14.49%的任务总处理时间。     

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

异构系统中DAG任务调度的双螺旋结构遗传算法

任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗传算法.算法将遗传算法和启发式方法有机地结合,首先针对任务图的数据依赖关系,采用启发式方法,控制遗传算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列;然后模仿碱基互补配对方法,利用启发式异构环境下最早完成时间算法,实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机任务图和真实问题任务图的仿真实验表明,所提出的算法在调度性能上明显优于启发式算法,最大完成时间平均减少10.1%.     

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验，提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试，所得结果的平均面积未利用率为0.28%，平均计算时间为17.86s，并且还得到了其中8个实例的最优解。测试结果表明，该算法对求解矩形packing问题相当有效。     

基于自适应变异粒子群优化的SVM在混合气体分析中的应用

针对混合气体定量分析中,支持向量机建模的参数难以确定、红外光谱数据计算量过大以及气体间交叉干扰等问题。提出了一种自适应变异粒子群优化的支持向量机方法,用于建立基于红外光谱的多组分混合气体定量分析模型。混合气体主要由浓度范围在0.5%~8%的CO、3.6%~12.5%的CO2及200×10-6~3270×10-6的C3H8三种组分气体组成。利用粒子群优化算法对支持向量机建模中的参数进行优化选择,并与遗传算法优化的支持向量机作对比。实验表明,采用此方法建模所用时间为39.524 s,遗传算法为26.272 s;针对CO2独立建模的预测结果,粒子群优化算法均方差为0.000123758,遗传算法均方差为2.14952。在建模时间略高的情况下,粒子群优化算法预测结果均方差明显低于遗传算法。     

求解PDPTW问题的快速启发式算法

提出了一种解决有时间窗口装卸货问题（PDPIW）的快速启发式算法．该算法基于局域搜索和随机扰动的思想,以减少车辆数目为主要目标,采用了启发式的搜索方法并加入了随机扰动以跳出局部最小点。该算法可以在很短的时间内显著地提高解的质量,这是仅以减少总路程为主要目标的局域搜索和现代启发式算法不能达到的。对标准算例的测试和与禁忌搜索算法计算结果的比较,表明该算法对于求解此类有时间窗口装卸货问题比传统的启发式算法在计算速度和减少车辆数目上更具优势。     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

求解CARP-RP-ML问题的改进算法

传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此,提出改进的启发式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上,构造问题的可行解;遗传算法利用分割算法计算其个体适应值,确定对应的可行车辆路径及补给位置,并用局部搜索作为变异算子,进一步扩大搜索空间。数值实验结果表明,与启发式算法相比,遗传算法能更有效地求解CARP-RP-ML问题。     

基于多边形边界约简的启发式在线时间序列表示算法

提出了一种新颖的可在线计算的时间序列启发式算法。算法具有多边形约简算法相同的优良的近似质量，并可在固定数据缓冲区空间内在线运算。用启发式搜索方法自动获取最佳分段数。在随机时间序列上仿真试验证明算法有很高的逼近质量和较低的计算复杂性。     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

分布式数据库数据分布模型的启发式算法

本文提出了以最小代价为目标的分布式数据库数据分布模型求解的启发式算法，利用数据分布的启发信息，将互相有紧密联系的ｎ个关系的数据分布问题分解为具有较松散联系的ｎ个关系的分布问题，并进行迭代调整，使算法的时间复杂度大为降低，算法精度也接近优化程度。     

Determining the Natural Frequency of Cantilever Beams Using ANN and Heuristic Search

An artificial neural network (ANN) is used to model the frequency of the first mode, using the beam length, the moment of inertia, and the load applied on the beam as input parameters on a database of 100 samples. Three different heuristic optimization methods are used to train the ANN: genetic algorithm (GA), particle swarm optimization algorithm and imperialist competitive algorithm. The suitability of these algorithms in training ANN is determined based on accuracy and runtime performance. Results show that, in determining the natural frequency of cantilever beams, the ANN model trained using GA outperforms the other models in terms of accuracy.     

Adaptive task allocation for multi-UAV systems based on bacteria foraging behaviour

The foraging behaviour of bacteria in colonies exhibits motility patterns that are simple and reasoned by stimuli. Notwithstanding its simplicity, bacteria behaviour demonstrates a level of intelligence that can feasibly inspire the creation of solutions to address numerous optimisation problems. One such challenge is the optimal allocation of tasks across multiple unmanned aerial vehicles (multi-UAVs) to perform cooperative tasks for future autonomous systems. In light of this, this paper proposes a bacteria-inspired heuristic for the efficient distribution of tasks amongst deployed UAVs. The usage of multi-UAVs is a promising concept to combat the spread of the red palm weevil (RPW) in palm plantations. For that purpose, the proposed bacteria-inspired heuristic was utilised to resolve the multi-UAV task allocation problem when combating RPW infestation. The performance of the proposed algorithm was benchmarked in simulated detect-and-treat missions against three long-standing multi-UAV task allocation strategies, namely opportunistic task allocation, auction-based scheme, and the max-sum algorithm, and a recently introduced locust-inspired algorithm for the allocation of multi-UAVs. The experimental results demonstrated the superior performance of the proposed algorithm, as it substantially improved the net throughput and maintained a steady runtime performance under different scales of fleet sizes and number of infestations, thereby expressing the high flexibility, scalability, and sustainability of the proposed bacteria-inspired approach.     

双渠道二级供应链库存分配与控制问题研究

针对由仓库和多个零售商组成的二级供应链问题,考虑仓库面临零售商和网络销售两种渠道以及不同零售商的优先级不同的情况,建立解析模型。以最小化供应链总成本为目标,设计一种改进型遗传算法,并提出一种两阶段分配策略求解模型。以实际数据为例,对模型在供应链库存分配与控制问题中的应用进行实例验证,结果表明,所提出策略所得解优于改进的先到先服务（FCFS）策略,并且与Cplex所得精确解的GAP小于10%。数值试验表明所提出的策略能够有效地分配库存,所提出的算法能够有效地求得库存策略的各个参数。     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

A genetic algorithm to solve the storage space allocation problem in a container terminal

In this paper, an efficient genetic algorithm (GA) is presented to solve an extended storage space allocation problem (SSAP) in a container terminal. The SSAP is defined as the temporary allocation of the inbound/outbound containers to the storage blocks at each time period with aim of balancing the workload between blocks in order to minimize the storage/retrieval times of containers. An extended version of a SSAP proposed in the literature is considered in this paper in which the type of container affects on making the decision on the allocation of containers to the blocks. In real-world cases, there are different types (as well as different sizes) of containers consisting of several different goods such as regular, empty and refrigerated containers. The extended SSAP is solved by an efficient GA for real-sized instances. Because of existing the several equality constraints in the extended model, the implementation of the GA in order to quick and facilitate achieve to the feasible solutions is one of the outstanding advantages of this paper. The performance of the extended model and proposed GA is verified by a number of numerical examples.     

一种基于QoS的自适应网格失效检测器

失效检测器是构建可靠的网格计算环境所必需的基础组件之一.由于网格中存在大量对失效检测有着不同QoS需求的分布式应用,对于一个网格失效检测器来说,为保持其有效性和可扩展性,应该既能够准确提供应用程序所需的失效检测QoS,又能够避免为满足不同QoS而设计多套失效检测器所产生的多余负载.基于QoS基本评价指标,采用PULL模式主动检测策略实现了一种新的失效检测器--GA-FD(adaptive failure detector for grid),可以同时支持多个应用程序定量描述的QoS需求,不需要关于消息行为和时钟同步的任何假设.同时,证明了GA-FD在部分同步模型下可实现一个◇P类的失效检测器,并给出了相应的实验及数据.     

云中心异构服务器能耗受限下的性能优化策略

为了解决云中心能耗受限下性能优化和异构服务器之间的能耗分配问题,提出了基于M/GI/1-PS排队系统的云中心能耗—性能优化模型,并通过拉格朗日乘数法进行求解,并给出计算云中心最快平均响应时间的OPT算法。同时通过大量数值仿真实验将OPT算法与常用的启发式能耗分配方法进行对比。数值仿真结果表明：本文提出的OPT算法在相同能耗下可获得最优的平均响应时间,同时通过能耗—性能变化曲线,可为云中心优化资源配置提供理论依据和参考数据。     

异构多核计算系统的Codelet任务调度策略

Codelet数据流计算模型在处理大规模并行计算任务时效果显著,但该模型目前缺少在异构多核环境中的任务调度策略。因此,提出了一种在异构多核环境下基于蚁群算法的Codelet任务调度策略。该调度策略将启发式算法与蚁群算法相融合,在发挥各自优势的同时克服了启发式算法不能得出最优解的缺陷以及蚁群算法初始信息匮乏的问题。实验结果表明,智能蚁群任务调度策略相比Codelet运行时系统中原生的动态调度和静态调度策略具有更高的执行效率。