并行机间歇过程生产调度的遗传局部搜索算法

研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.     

最小赋权支配集的迭代禁忌搜索算法

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。     

针对移动云计算任务迁移的快速高效调度算法

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。     

MAX-SAT问题一种改进的局部搜索算法

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的。本文提出了用单纯形法产生“初始概率”（每个变量取1的概率）,用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度。通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。     

一种基于Levy飞行的改进蝗虫优化算法

蝗虫优化算法是一种元启发式优化算法,能够用于解决任务调度问题。已有的改进蝗虫优化算法缺乏随机性,跳出局部最优的能力较弱,改进效果不够显著。针对这一问题,本文提出一种基于Levy飞行的改进蝗虫优化算法（LBGOA）。该算法引入基于Levy飞行的局部搜索机制增强算法的随机性,并采用基于线性递减参数的随机跳出策略来提高算法跳出局部最优的能力。CEC测试实验结果表明,所提出的算法拥有较强的搜索能力,在30个测试函数结果中能够获得17个最优解和6个次优解。将所提出的改进算法应用于边缘计算中的任务调度问题。任务调度仿真实验结果表明,所提出的算法能够有效提高搜索效果,相比GOA、OBLGOA、WOA、ALO、DA和PSO算法,LBGOA的搜索效果分别提升7.4%、7.5%、4.8%、27.7%、29.9%和20.7%。     

A spy search mechanism for memetic algorithm in dynamic environments

Searching within the sample space for optimal solutions is an important part in solving optimization problems. The motivation of this work is that today’s problem environments have increasingly become dynamic with non-stationary optima and in order to improve optima search, memetic algorithm has become a preferred search method because it combines global and local search methods to obtain good solutions. The challenge is that existing search methods perform the search during the iterations without being guided by solid information about the nature of the search environment which affects the quality of a search outcome. In this paper, a spy search mechanism is proposed for memetic algorithm in dynamic environments. The method uses a spy individual to scope out the search environment and collect information for guiding the search. The method combines hyper-mutation, random immigrants, hill climbing local search, crowding and fitness, and steepest mutation with greedy crossover hill climbing to enhance the efficiency of the search. The proposed method is tested on dynamic problems and comparisons with other methods indicate a better performance by the proposed method.     

A genetic algorithm for multiprocessor scheduling

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented     

一种改进的警示传播算法求解Max-SAT问题

Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。     

批量无等待调度问题的微粒群蛙跳混合优化算法*

将离散微粒群与蛙跳算法相结合解决以最大完工时间为指标的批量无等待流水线调度问题.结合微粒群算法较强的全局收敛能力和蛙跳算法较强的深度搜索能力,设计了三种混合算法,平衡了算法的全局开发能力和局部探索能力.对随机生成不同规模的实例进行了广泛的实验,仿真实验结果的比较表明了所得混合算法的有效性和高效性.     

基于小波精英解学习和多角度搜索的新型阴阳平衡优化算法

针对基本阴阳平衡优化算法计算精度低和优化速度慢等问题,提出一种新型阴阳平衡优化算法.首先,设计小波精英解学习策略,充分利用精英解的进化信息产生高质量的解,用于算法的全局勘探和局部开发;然后,将搜索角度引入解更新方程中,以实现对算法搜索空间的全方位搜索,并对所提出算法的收敛性进行理论分析;最后,采用连续优化测试函数和瓶颈旅行商问题进行数值实验,并将所提出算法与多种智能优化方法进行比较.实验结果表明,所提出算法具有更好的优化性能.     

带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法.该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计.为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率.实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002％,优于对比算法.     

GSAGA: A hybrid algorithm for task scheduling in cloud infrastructure

Cloud computing is becoming a very popular form of distributed computing, in which digital resources are shared via the Internet. The user is provided with an overview of many available resources. Cloud providers want to get the most out of their resources, and users are inclined to pay less for better performance. Task scheduling is one of the most important aspects of cloud computing. In order to achieve high performance from cloud computing systems, tasks need to be scheduled for processing by appropriate computing resources. The large search space of this issue makes it an NP-hard problem, and more random search methods are required to solve this problem. Multiple solutions have been proposed with several algorithms to solve this problem until now. This paper presents a hybrid algorithm called GSAGA to solve the Task Scheduling Problem (TSP) in cloud computing. Although it has a high ability to search the problem space, the Genetic Algorithm (GA) performs poorly in terms of stability and local search. It is therefore possible to create a stable algorithm by combining the general search capacities of the GA with the Gravitational Search Algorithm (GSA). Our experimental results indicate that the proposed algorithm can solve the problem with higher efficiency compared with the state-of-the-art.

     

An improved algorithm for the longest common subsequence problem

The Longest Common Subsequence problem seeks a longest subsequence of every member of a given set of strings. It has applications, among others, in data compression, FPGA circuit minimization, and bioinformatics. The problem is NP-hard for more than two input strings, and the existing exact solutions are impractical for large input sizes. Therefore, several approximation and (meta) heuristic algorithms have been proposed which aim at finding good, but not necessarily optimal, solutions to the problem. In this paper, we propose a new algorithm based on the constructive beam search method. We have devised a novel heuristic, inspired by the probability theory, intended for domains where the input strings are assumed to be independent. Special data structures and dynamic programming methods are developed to reduce the time complexity of the algorithm. The proposed algorithm is compared with the state-of-the-art over several standard benchmarks including random and real biological sequences. Extensive experimental results show that the proposed algorithm outperforms the state-of-the-art by giving higher quality solutions with less computation time for most of the experimental cases.     

A hybrid column generation with GRASP and path relinking for the network load balancing problem

In this paper, a hybrid meta-heuristic is proposed which combines the GRASP with path relinking method and Column Generation. The key idea of this method is to run a GRASP with path relinking search on a restricted search space, defined by Column Generation, instead of running the search on the complete search space of the problem. Moreover, column generation is used not only to compute the initial restricted search space but also to modify it during the whole algorithm. The proposed heuristic is used to solve the network load balancing problem: given a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, the network load balancing problem is the determination of a routing path for each traffic commodity such that the network load balancing is optimized, i.e., the worst link load is minimized, among all such solutions, the second worst link load is minimized, and continuing in this way until all link loads are minimized. The computational results presented in this paper show that, for the network load balancing problem, the proposed heuristic is effective in obtaining better quality solutions in shorter running times.     

Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with CUDA

In this paper we propose an improved algorithm to search optimal solutions to the flow shop scheduling problems with fuzzy processing times and fuzzy due dates. A longest common substring method is proposed to combine with the random key method. Numerical simulation shows that longest common substring method combined with rearranging mating method improves the search efficiency of genetic algorithm in this problem. For application in large-sized problems, we also enhance this modified algorithm by CUDA based parallel computation. Numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU. Based on the modified algorithm invoking with CUDA scheme, we can search satisfied solutions to the fuzzy flow shop scheduling problems with high performance.     

An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.     

An algorithm for production planning in a flexible production system

In this paper, we consider the problem of determining the production rate, production batch size, and production sequence when production rate, setup cost, and unit processing cost are sequence-dependent. Using a standard lot sizing model with backorder, a tabu search algorithm for solving this problem is proposed. The algorithm is tested on some random test problems and its performance is compared with random sequencing. Computational results show that the proposed algorithm is very efficient.     

求解PDPTW问题的快速LNS算法

提出了一种解决有时间窗口的装卸货问题（PDPTW）的快速大规模领域搜索（LNS）算法。该算法基于大规模邻域搜索理论和随机扰动思想,在第一阶段主要以减少车辆为目标,第二阶段对第一阶段得到的解优化总路程长度。该算法能在较短时间内显著提高初始解的质量．克服了单纯以车辆数目或以总路程长度为目标的算法所得到解的局限性。通过标准算例的测试和同禁忌搜索的比较表明,该算法在求解PDPTW问题时,在计算时间和优化整体目标上更具优势。     

云计算中基于改进的布谷鸟算法的资源调度

云计算的资源调度一直以来都是研究的重点,引入布谷鸟算法来解决资源分配问题,首先描述云计算资源模型,其次针对该算法存在局部收敛速度快,容易造成局部最优值的问题,采用三个方面来改进,其一采用变长因子进行调整,减小探索求解质量之间的差别;其二使用差分变异策略更新鸟窝位置;其三使用基于Coelho的混沌全局搜素和局部搜索避免了Levy的随意扰动.通过测试函数说明表明本文算法的性能优于基本布谷鸟算法, Cloudsim仿真平台说明本文的算法在消耗时间,成本和用户满意度方面具有明显的优势.     

改进Memetic算法求解集装箱码头泊位岸桥调度问题

针对集装箱码头泊位岸桥调度这一NP难题,提出了一种改进的Memetic算法。算法中采用三层染色体结构表示个体,通过改进顺序交叉算子和基于领域搜索的变异算子以避免个体超出可行域,在交叉和变异后采用改进的模拟退火策略进行局部搜索。试验算例表明该算法收敛速度较快,且能获得较好的满意解。