A genetic algorithm for the optimal sequential partitioning problem

The optimal sequential problem is defined as the problem of finding the minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relationships among the elements are satisfied. A heuristic algorithm based on tabu search has been proposed for this problem [2]. However, there is a tendency for the solutions obtained by tabu search to become trapped in bad local optima in parallel graphs with random edge costs. In this paper we present a genetic algorithm for the optimal sequential partitioning problem. We develop an effective two‐point partial order crossover satisfying sequential conditions, which preserve better blocks that have a larger sum of edge costs. In this crossover we introduce the roulette selection method to escape local optima. We also assess the effectiveness of the algorithm. The results show that this proposed algorithm outperforms any other algorithm using tabu search in terms of solution quality. © 2001 Scripta Technica, Electr Eng Jpn, 135(4): 43–51, 2001     

Tabu search algorithm for network synthesis

Large scale combinatorial problems such as the network expansion problem present an amazingly high number of alternative configurations with practically the same investment, but with substantially different structures (configurations obtained with different sets of circuit/transformer additions). The proposed parallel tabu search algorithm has shown to be effective in exploring this type of optimization landscape. The algorithm is a third generation tabu search procedure with several advanced features. This is the most comprehensive combinatorial optimization technique available for treating difficult problems such as the transmission expansion planning. The method includes features of a variety of other approaches such as heuristic search, simulated annealing and genetic algorithms. In all test cases studied there are new generation, load sites which can be connected to an existing main network: such connections may require more than one line, transformer addition, which makes the problem harder in the sense that more combinations have to be considered     

Assignment problem for system with precedence relationships among elements

We have studied the problem of assign elements to an ordered sequence of stations such that the precedence relations are satisfied. At this time, we can obtain the best evaluation value decided under certain constrained conditions to the assignment. This kind of problem includes the line balancing problem. In addition, this can be adjusted to various problems by changing the constrained condition and objective function. These problems can be shown as sequential partitions of the nodes of a directed acyclic graph into subsets. We especially consider the problem of finding a minimum total cost of the cut edge under the restriction of the size of block. In this paper, we propose the general framework for sequential partitions of directed acyclic graphs. We also describe an efficient algorithm that can be used to reduce computational requirements and, possibly, storage. We estimate that the complexity of the algorithm is the polynomial order, if structure of directed acyclic graphs is near parallel. © 1997 Scripta Technica, Inc. Electr Eng Jpn, 121(2): 54–62, 1997     

A new genetic-based tabu search algorithm for unit commitment problem

This paper presents a new algorithm based on integrating the use of genetic algorithms and tabu search methods to solve the unit commitment problem. The proposed algorithm, which is mainly based on genetic algorithms incorporates tabu search method to generate new population members in the reproduction phase of the genetic algorithm. In the proposed algorithm, genetic algorithm solution is coded as a mix between binary and decimal representation. A fitness function is constructed from the total operating cost of the generating units without penalty terms. In the tabu search part of the algorithm, a simple short term memory procedure is used to counter the danger of entrapment at a local optimum by preventing cycling of solutions, and the premature convergence of the genetic algorithm. A significant improvement of the proposed algorithm results, over those obtained by either genetic algorithm or tabu search, has been achieved. Numerical examples also showed the superiority of the proposed algorithm compared with two classical methods in the literature.     

Large-scale var optimization and planning by tabu search

A generalization on the tabu search method, recently developed for combinatorial optimization problems, is described in this paper. The novel version of the tabu search method can be used to solve a larger class of combinatorial optimization problems. Application of this method to var optimization and planning, which is formulated as a nonlinear large-scale mixed integer programming problem with non-differentiable objective function, is demonstrated. Judicious engineering judgment which is essential for a successful application of the proposed tabu search is developed. Simulation results of a real-world power system are included. A simulation comparison is done between the proposed method and the simulated annealing method, which is currently one of the most popular method for combinatorial optimization problem.     

机组优化组合问题的随机tabu搜索算法

针对机组组合问题的特点，作者对tabu搜索策略和模拟退火算法(SA)的组合算法——随机tabu搜索策略的编码方式、移动规则和tabu表的构造等作了适应性的改进，并对实际机组组合算例进行了求解。仿真结果表明，tabu-SA组合算法有效地结合了SA算法的大规模寻优特性和tabu搜索的局部搜索能力强的特点，能快速搜索到高质量的系统优化解。而且随机tabu搜索算法具有框架性算法不易陷入局部最优的特点，易于与其他算法结合来构造新的高效组合算法。     

基于Tabu方法的配电电容器投切策略

本文首先给出电网电容器优化投切策略的混合整数规划模型。然后应用Ｔａｕｂ Ｓａｅｒａｃｈ优化方法解决混合整数规划模型。通过对算例的演算证明,Ｔａｂｕ Ｓｅａｒｃｈ方法能够有效地处理整数约束和不可微的目标函数。     

基于改进蜂群算法的工业机器人路径规划研究

针对工业机器人在复杂环境中运动的避障及路径优化问题,提出基于改进人工蜂群算法的工业机器人避障路径规划策略。首先针对传统人工蜂群算法搜索能力不足且容易陷入局部最优的问题,将禁忌搜索思想引入到人工蜂群算法最优解搜索过程中,形成了基于禁忌搜索的改进型人工蜂群算法,然后将其应用到工业机器人的路径规划问题中,并进行了仿真实验。结果表明,改进后的方法能够得到最优的路径,且寻优速度快、过程稳定。该方法可用于解决工业机器人路径规划问题。     

基于Tabu搜索的配电网络重构算法

配电网络重构是一个非常复杂的、大规模的组合优化问题。该文提出了一种非常有效的、鲁棒性很好的算法来求解正常运行条件下配电网络的重构问题,以减少网络中的能量损失费用。该算法基于Tabu搜索方法(TS)。作为现代启发式方法家族中的重要一员,Tabu搜索方法是近几年来发展起来的用于求解组合最优问题的一种通用算法。文中详细阐述了用于配电网络重构问题时Tabu搜索方法中各成员的设计。为了证明该文方法的可行性和有效性,还研究了3个不同规模的IEEE测试网络的重构问题。结果表明,该文提出的方法是一种非常有效的方法。     

用于配电网规划的改进遗传算法

针对传统遗传算法易于陷入局部最优解和随着配电网规模的扩大搜索效率降低的问题,借鉴协同进化思想提出了基于协同遗传算法的配电网规划算法。通过对目标函数进行处理引入了多个物种,并采用简单遗传算法和考虑进化稳定的改进多种群遗传算法分别对不同的物种进行操作,通过转移优秀个体实现了物种间的协同作用。同时为解决遗传算法应用于配电网规划时产生的大量不可行解的问题,借助图论知识和搜索技术给出了不可行解的修复方案,通过对孤岛、孤链和环进行修复,将非辐射状网络修复为辐射状网络。算例结果验证了该算法的实用性和有效性。     

Integrating genetic algorithms, tabu search, and simulatedannealing for the unit commitment problem

This paper presents a new algorithm based on integrating genetic algorithms, tabu search and simulated annealing methods to solve the unit commitment problem. The core of the proposed algorithm is based on genetic algorithms. Tabu search is used to generate new population members in the reproduction phase of the genetic algorithm. A simulated annealing method is used to accelerate the convergence of the genetic algorithm by applying the simulated annealing test for all the population members. A new implementation of the genetic algorithm is introduced. The genetic algorithm solution is coded as a mix between binary and decimal representation. The fitness function is constructed from the total operating cost of the generating units without penalty terms. In the tabu search part of the proposed algorithm, a simple short-term memory procedure is used to counter the danger of entrapment at a local optimum, and the premature convergence of the genetic algorithm. A simple cooling schedule has been implemented to apply the simulated annealing test in the algorithm. Numerical results showed the superiority of the solutions obtained compared to genetic algorithms, tabu search and simulated annealing methods, and to two exact algorithms     

基于麻雀搜索的协同定位算法研究

无线传感器网络的定位问题可以转化为适应度函数最优问题,并通过经典的麻雀搜索算法进行求解。然而该算法所用的适应度函数并未使用未知节点之间的测量距离数据,从而导致定位精度的提升有限。为了解决这一问题,提出了一种基于麻雀搜索的协同定位算法。该算法主要包括两个搜索阶段：粗略搜索和精细搜索。在粗略搜索阶段,未知节点到锚节点之间的测量距离数据被用于确定未知节点的初始位置。在精细搜索阶段,未知节点之间的测量距离数据被用来确定未知节点的精确位置。首先,采用Cat混沌映射方法来保证初始种群的均匀分布,从而有助于确定最佳位置。其次,构建了两种不同的适应度函数,一种用于粗略搜索,另一种用于精细搜索。其中,用于精细搜索的适应度函数利用未知节点之间的测量距离数据来提高定位精度。最后,提出了一种新的精细搜索方法,以避免协同定位结果收敛到局部最优位置。通过对仿真和实测数据进行分析,验证了所提方法的有效性。     

基于并行禁忌搜索算法的配电网重构

为更好地实现配电网重构,引入了分治法,进而提出了采用并行禁忌搜索算法实现重构的方法.将配电网简化为只含支路组的环网,并给出了配电网重构的必要条件.重构时,首先选择断开的支路组,采用深度优先搜索算法形成父子链表;然后引入可降低复杂度的分治思想,以可断开支路组为解空间进行分组,应用多处理器进行并行禁忌搜索.算例结果验证了该方法的有效性.     

基于遗传禁忌搜索算法的PMU布点配置

将遗传算法GA（Genetic Algorithm）和禁忌搜索算法TS（Tabu search）相结合,提出一种遗传禁忌搜索算法GATS ( Genetic Algorithm & Tabu search)用于相量测量单元优化配置。GATS算法结合了遗传算法的随机搜索能力、并行性和禁忌搜索算法的记忆功能,有效地解决了遗传算法的爬山能力差、早熟的问题,提高了收敛速度及优化质量;同时遗传算法的种群操作,保留了遗传算法的多出发点的优势,弥补了禁忌搜索的单一单操作缺乏并行性的弱点。在约束条件处理时,采用了不可行解启发性修复方法,提高了算法的优化效果。基于图论的深度优先方法用于系统可观性分析。将GATS算法应用于优化相量测量装置安装地点选择,实现了安装地点最少,而整个系统可观的目标。通过算例证明了算法的有效可靠。     

无线传感网络节点能效性测量优化方法

本文研究了无线传感网络节点能效性测量优化问题.给出了无线传感网络分簇式拓扑结构和节点概率检测模型,建立了网络测量覆盖率指标和通信能耗指标.遗传算法和微粒群算法在节点能效性测量优化时存在容易陷入局部最优和精度不高的缺点.将禁忌搜索算法和遗传算法结合,增强了遗传算法的全局搜索能力.仿真实验证明,采用遗传-禁忌搜索算法进行节点能效性测量优化时,网络测量覆盖率更高,通信能耗更小,优化效果更好.     

面向边缘计算的人工鱼群搜索任务调度

如何将计算任务分配到合适的边缘计算资源上进行计算,以满足边缘计算环境下用户的计算需求、提高用户任务请求 的服务质量,是边缘计算中面临的关键问题。 本文提出一种基于人工鱼群搜索的边缘计算任务调度方法(AFETSA)。 将人工 鱼群搜索算法和边缘计算任务调度模型相结合,采用非线性递减函数动态地调整人工鱼的视野范围和步长,以提高启发式任务 调度算法的全局搜索能力,降低任务的计算时延;同时与禁忌搜索算法进行融合,通过引入忌禁表,在每一次迭代中防止算法陷 入局部最优,提高算法的寻优能力。 CloudSim3. 0 仿真平台实验评测结表明,本文所提 AFETSA 方法和已有的 AFSA、ACO 和 PSO 这 3 种调度算法相比,在任务执行时间、算法稳定性、负载均衡方面都有明显的提升,可充分利用边缘服务器计算资源,提 升计算任务的计算性能,有效解决边缘计算中任务调度不均导致的时延过高和负载不均衡问题。     

基于自适应多种群遗传算法的配电网规划

针对传统遗传算法易于陷入局部最优解和随着配电网规模的扩大搜索效率降低的问题,借鉴多种群和自适应思想,提出了基于自适应多种群遗传算法的配电网规划算法。通过对目标函数进行处理,引入了多个物种,并采用自适应遗传算法和考虑进化稳定的改进多种群遗传算法分别对不同的物种进行操作,通过转移优秀个体,实现了物种之间的协同作用。同时为解决遗传算法应用于配电网规划时产生的大量不可行解的问题,借助图论知识和搜索技术给出了不可行解的修复方案,通过对孤岛,孤链和环进行修复,将非辐射状网络修复为辐射状网络。算例结果验证了该算法的实用性和有效性。     

Nonconvex economic dispatch by integrated artificial intelligence

This paper presents a new algorithm by integrating evolutionary programming (EP), tabu search (TS) and quadratic programming (QP) methods to solve the nonconvex economic dispatch problem (NED). A hybrid EP and TS were used for quality control, and Fletcher's quadratic programming technique for solving. EP and TS determines the segment of a cost curve used, which is piecewise quadratic natured. Operation constraints are modeled as linear equality or inequality equations, resulting in a typical QP problem. Fletcher's QP was chosen to enhance the performance. The fitness function is constructed from priorities without penalty terms. Numerical results show that the proposed method is more effective than other previously developed evolutionary computation algorithms     

An improved tabu search for economic dispatch with multiple minima

This paper develops an improved tabu search algorithm (ITS) for economic dispatch (ED) with noncontinuous and nonsmooth cost functions. ITS employs a flexible memory system to avoid the entrapment in a local minimum and developed the ideal of "distance" to the fitness to accelerate optimization. The new approach extends simple tabu search algorithm (STS) to real valued optimization problem and applies parallelism to weaken the dependence of the convergence rate of modified tabu search algorithm (NITS) on the initial condition. Effectiveness of the method was compared with many conventional methods. Results show that the proposed algorithm can provide accurate solutions with reasonable performance and has a great potential for other applications in the power system     

改进禁忌搜索算法在地区电网故障诊断中的研究

禁忌搜索算法在电网故障诊断中已有应用,但其往往为了确保更多的有效搜索,却需要较多的计算时间,无法很好的满足电网故障诊断对实时性的要求。本文在禁忌搜索算法中引入一个较简单的跳出全禁忌的方法,使其能够较快的搜索到所有的全局最优解,并用一个含152节点的系统各种类型的故障证明了改进算法的有效性。