Optimal Polygonal Approximation of Digital Planar Curves Using Genetic Algorithm and Tabu Search

Three heuristic algorithms for optimal polygonal approximation of digital planar curves is presented. With Genetic Algorithm (GA), improved Genetic Algorithm (IGA) based on Pareto optimal solution and Tabu Search (TS), a near optimal polygonal approximation was obtained. Compared to the famous Teh chin algorithm, our algorithms have obtained the approximated polygons with less number of vertices and less approximation error. Compared to the dynamic programming algorithm, the processing time of our algorithms are much less expensive.

Search for circular and noncircular critical slip surfaces in slope stability analysis by hybrid genetic algorithm

A local improvement procedure based on tabu search(TS) was incorporated into a basic genetic algorithm(GA) and a global optimal algorithm,i.e.,hybrid genetic algorithm(HGA) approach was used to search the circular and noncircular slip surfaces associated with their minimum safety factors.The slope safety factors of circular and noncircular critical slip surfaces were calculated by the simplified Bishop method and an improved Morgenstern-Price method which can be conveniently programmed,respectively.Comparisons with other methods were made which indicate the high efficiency and accuracy of the HGA approach.The HGA approach was used to calculate one case example and the results demonstrated its applicability to practical engineering.

Localization of Voltage Regulators in Distribution Systems by a Mixed Genetic–Tabu Search Algorithm

The optimal allocation of regulators banks in distribution systems is a merely combinatorial problem in which the best points of installation correspond to the best benefit, considering the admitted objective function, without violating and operating limits. The objective function must be chosen so that its value represents the operation state of the system. As the problem possesses combinatorial nature, its complexity will increase exponentially with the number of possibilities. Systems with large numbers of nodes and / or with the possibility of installing more than one bank require a large number of calculations to find the solution. An additional issue is the fact that the problem does not have a continuous nature, presenting discontinuity points in the objective function, limiting the application of optimization methods based on gradients. Based on the nature of the problem two optimization methods were used to solve the problem: Genetic Algorithm (GA) and modified Tabu Search (TS). The GA function will scour the search space and find regions with local minima that are candidates to be the solution. On the other hand the TS provides local search in the regions defined by GA so that the overall optimum is achieved.

A Case Study of 3D Protein Structure Prediction with Genetic Algorithm and Tabu Search

This paper describes a case study of 3D protein structure prediction of six sequences from protein data bank （PDB） by genetic algorithm and tabu search （GATS）, where off-lattice AB model is considered as a simplified model of protein structure. The lowest-energy values required for forming the native conformation of proteins are searched by GATS, and then the coarse structures （i.e., simplified structure） of the proteins are obtained according to the multiple angle parameters corresponding to the lowest energies. All the coarse structures form single hydrophobic cores surrounded by hydrophilic residues, which stay on the right side of the actual characteristic of protein structure. It demonstrates that this approach can predict the 3D protein structure effectively.

Genetic algorithm for short-term scheduling of make-and-pack batch production process

This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy all constraints while meeting demand requirement of packed products from various product families. This problem is NP-hard and the problem size is exponentially large for a realistic-sized problem. Therefore,we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromosomes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to determine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for comparison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, all heuristics show the capability to solve large instances within reasonable computational time. In all problem instances, genetic algorithm averagely outperforms ant colony optimization and Tabu search with slightly longer computational time.

A NOVEL HYBRID GENETIC ALGORITHMS AND PATTERN SEARCH TECHNIQUES FOR INDUSTRIAL PRODUCTION PLANNING

Soft computing has attracted many research scientists,decision makers and practicing researchers in recent years as powerful computational intelligent techniques,for solving unlimited number of complex real-world problems particularly related to research area of optimization.Under the uncertain and turbulence environment,classical and traditional approaches are unable to obtain a complete solution with satisfaction for the real-world problems on optimization.Therefore,new global optimization methods are required to handle these issues seriously.One such method is hybrid Genetic algorithms and Pattern search,a generic,flexible,robust,and versatile framework for solving complex problems of global optimization and search in real-world applications.

A multi-dimensional tabu search algorithm for the optimization of process planning

Computer-aided process planning （CAPP） is an essential component of computer integrated manufacturing （CIM） system. A good process plan can be obtained by optimizing two elements, namely, operation sequence and the machining parameters of machine, tool and tool access direction （TAD） for each operation. This paper proposes a novel optimization strategy for process planning that considers different dimensions of the problem in parallel. A multi-dimensional tabu search （MDTS） algo-rithm based on this strategy is developed to optimize the four dimensions of a process plan, namely, operation sequence （OperSeq）, machine sequence （MacSeq）, tool sequence （TooISeq） and tool approach direction sequence （TADSeq）, sequentially and iteratively. In order to improve its efficiency and stability, tabu search, which is incorporated into the proposed MDTS al- gorithm, is used to optimize each component of a process plan, and some neighbourhood strategies for different components are presented for this tabu search algorithm. The proposed MDTS algorithm is employed to test four parts with different numbers of operations taken from the literature and compared with the existing algorithms like genetic algorithm （GA）, simulated annealing （SA）, tabu search （TS） and particle swarm optimization （PSO）. Experimental results show that the developed algo-rithm outperforms these algorithms in terms of solution quality and efficiency.

Parametric Optimization Design of Aircraft Based on Hybrid Parallel Multi-objective Tabu Search Algorithm

For dealing with the multi-objective optimization problems of parametric design for aircraft, a novel hybrid parallel multi-objective tabu search （HPMOTS） algorithm is used. First, a new multi-objective tabu search （MOTS） algorithm is proposed. Comparing with the traditional MOTS algorithm, this proposed algorithm adds some new methods such as the combination of MOTS algorithm and ＂Pareto solution＂, the strategy of ＂searching from many directions＂ and the reservation of good solutions. Second, this article also proposes the improved parallel multi-objective tabu search （PMOTS） algorithm. Finally, a new hybrid algorithm--HPMOTS algorithm which combines the PMOTS algorithm with the non-dominated sorting-based multi-objective genetic algorithm （NSGA） is presented. The computing results of these algorithms are compared with each other and it is shown that the optimal result can be obtained by the HPMOTS algorithm and the computing result of the PMOTS algorithm is better than that of MOTS algorithm.

Genetic Tabu Search for the Multi-Objective Knapsack Problem

We introduce a hybrid algorithm for the 01 multidimensional multi-objective knapsack problem. This algorithm, called GTS MOKP, combines a genetic procedure and a tabu search operator. The algorithm is evaluated on 9 well-known benchmark instances and shows highly competitive results compared with two state-of-the-art algorithms.

Application of Interval Algorithm in Rural Power Network Planning

Rural power network planning is a complicated nonlinear optimized combination problem which based on load forecasting results, and its actual load is affected by many uncertain factors, which influenced optimization results of rural power network planning. To solve the problems, the interval algorithm was used to modify the initial search method of uncertainty load mathematics model in rural network planning. Meanwhile, the genetic/tabu search combination algorithm was adopted to optimize the initialized network. The sample analysis results showed that compared with the certainty planning, the improved method was suitable for urban medium-voltage distribution network planning with consideration of uncertainty load and the planning results conformed to the reality.

A Hybrid Multi-Objective Evolutionary Algorithm for Optimal Groundwater Management under Variable Density Conditions

In this paper, a new hybrid multi-objective evolutionary algorithm （MOEA）, the niched Pareto tabu search combined with a genetic algorithm （NPTSGA）, is proposed for the management of groundwater resources under variable density conditions. Relatively few MOEAs can possess global search ability contenting with intensified search in a local area. Moreover, the overall searching ability of tabu search （TS） based MOEAs is very sensitive to the neighborhood step size. The NPTSGA is developed on the thought of integrating the genetic algorithm （GA） with a TS based MOEA, the niched Pareto tabu search （NPTS）, which helps to alleviate both of the above difficulties. Here, the global search ability of the NPTS is improved by the diversification of candidate solutions arising from the evolving genetic algorithm population. Furthermore, the proposed methodology coupled with a density-dependent groundwater flow and solute transport simulator, SEAWAT, is developed and its performance is evaluated through a synthetic seawater intrusion management problem. Optimization results indicate that the NPTSGA offers a tradeoff between the two conflicting objectives. A key conclusion of this study is that the NPTSGA keeps the balance between the intensification of nondomination and the diversification of near Pareto-optimal solutions along the tradeoff curves and is a stable and robust method for implementing the multi-objective design of variable-density groundwater resources.

Integrated generation-transmission expansion planning for offshore oilfield power systems based on genetic Tabu hybrid algorithm

To address the planning issue of offshore oil-field power systems, an integrated generation-transmission expansion planning model is proposed. The outage cost is considered and the genetic Tabu hybrid algorithm(GTHA)is developed to find the optimal solution. With the proposed integrated model, the planning of generators and transmission lines can be worked out simultaneously,which outweighs the disadvantages of separate planning,for instance, unable to consider the influence of power grid during the planning of generation, or insufficient to plan the transmission system without enough information of generation. The integrated planning model takes into account both the outage cost and the shipping cost, which makes the model more practical for offshore oilfield power systems. The planning problem formulated based on the proposed model is a mixed integer nonlinear programming problem of very high computational complexity, which is difficult to solve by regular mathematical methods. A comprehensive optimization method based on GTHA is also developed to search the best solution efficiently.Finally, a case study on the planning of a 50-bus offshore oilfield power system is conducted, and the obtained results fully demonstrate the effectiveness of the presented model and method.

A Comparison of Three Heuristic Algorithms for Molecular Docking

Three heuristic algorithms: simulated annealing, genetic algorithm, and Tabu search were compared to molecular docking procedure using 3 protein-ligand systems. Statistical analysis of the results indicated that the Tabu search showed the best performance in terms of locating solutions close to the crystallographic ligand conformation. From the comparisons, a hybrid search algorithm was proposed, which gave superior results compared with any one of the algorithms alone.

基于Tabu搜索方法的电力系统无功优化

将 Tabu搜索方法用于电力系统无功优化 ,采用二进制和十进制编码 2种方案。对IEEE30节点系统和 1 2 5节点山东省某地区电网进行了优化计算 ,并与简单遗传算法、结合模拟退火的遗传算法进行了比较 ,结果表明 Tabu搜索方法具有更强的全局寻优能力 ,可用于运行方式安排 。

基于遗传算法与Tabu搜索的拆卸序列优化算法

为研究废弃装配体的拆卸序列优化,首先提出了建立装配体的干涉—自由矩阵,作为描述其结构的数学模型.其次,运用遗传算法原理,提出面向装配体拆卸序列自动生成及优化的计算模型.依据初始输入的若干拆卸序列和其它控制参数,由程序搜寻几何上可行的最佳拆卸序列.这里是以装配体在拆卸过程中具有最少的换向次数为优化目标.最后,鉴于遗传计算的未熟早敛问题,提出建立Tabu搜索与遗传算法的组合优化算法.通过把Tabu搜索的集中与分散策略引入遗传算法,可望获得更加健壮的搜索行为.大量的实例验证表明,用这种方法解决装配体拆卸序列的优化问题,所生成的可行拆卸序列在适应度函数值、数量、分布范围等方面均优于单纯的由遗传算法生成的结果.

基于Tabu搜索与遗传算法研究拆卸序列优化

针对废弃装配体的拆卸序列优化,提出建立描述装配体结构的干涉自由矩阵以及“拆卸楔”的概念和算法,据此计算各个零件从装配体上可以拆卸下来的方向和次序.鉴于遗传计算过程中,其邻域往往过早地收敛于局部优化点上,于是将Tabu搜索组合到遗传算法之中.实例验证表明,用这种组合优化方法解决装配体拆卸序列优化问题,所生成的可行拆卸序列在适应度函数值、数量、分布范围等方面均优于单纯的由遗传算法生成的结果.

A Hybrid Algorithm for Optimizing Multi-Modal Functions

A new genetic algorithm is presented based on the musical performance. The novelty of this algorithm is that a new genetic algorithm, mimicking the musical process of searching for a perfect state of harmony, which increases the robustness of it greatly and gives a new meaning of it in the meantime, has been developed, Combining the advantages of the new genetic algorithm, simplex algorithm and tabu search, a hybrid algorithm is proposed. In order to verify the effectiveness of the hybrid algorithm, it is applied to solving some typical numerical function optimization problems which are poorly solved by traditional genetic algorithms. The experimental results show that the hybrid algorithm is fast and reliable.

机组组合的混合编码遗传/tabu搜索组合算法

通过对遗传算法和tabu搜索的各自运算特性进行分析,文章提出了一种混合编码遗传算法与tabu搜索策略结合的组合算法,并运用组合算法对机组优化组合问题进行了求解。组合算法较好的结合了遗传算法的大规模寻优特性与tabu搜索的强局部搜索能力的特点,较大地减小了算法陷入局部最优的概率,能快速搜索到高质量的系统优化解;而且算法所采用的混合编码策略避免了每一迭代步上的负荷经济分配计算,大大地减少了计算量,提高了搜索速度。实例仿真结果表明,这种组合算法是有效的。

一种结合Tabu搜索的非线性遗传算法研究

利用Tabu搜索的强大局部搜索性能,提出一种新的非线性遗传算法.该方法将Tabu搜索技术内嵌于遗传算子中,构造了基于Tabu搜索的非线性杂交及变异算子,它能有效地提高算子的局部搜索能力,通过实例仿真证明了该算法的有效性;同时,以"平均截止代数"和"平均截止代数分布熵"作为评价指标,对该方法的优化效率进行研究,定量评价了该方法的优化效率,通过与实数遗传算法进行比较,说明了该方法的优化效率高于实数遗传算法.

一种结合Tabu搜索的自适应遗传算法研究

针对标准遗传算法(SGA)在全局优化问题中容易出现早熟和收敛速度慢,提出了一种TS-AGA算法。新算法通过将禁忌搜索(TS)和自适应遗传算法(AGA)相结合。以自适应遗传算法(AGA)为基础,用遗传算法进行全局搜索,用禁忌搜索法(TS)作局部搜索,可以加快收敛速度,同时可以抑制早熟现象,避免过早收敛到局部最优。测试函数仿真结果表明,新算法能很好的抑制早熟收敛,同时在计算速度和计算结果方面都有改进,是一种快速有效的优化算法。