Cultural algorithms: a Tabu search approach for the optimization of engineering design problems

Cultural Algorithms and Tabu search algorithms are both powerful tools to solve intricate constrained engineering and large-scale multi-modal optimization problems. In this paper, we introduce a hybrid approach that combines Cultural Algorithms and Tabu search (CA–TS). Here, Tabu Search is used to transform History Knowledge in the Belief Space from a passive knowledge source to an active one. In each generation of the Cultural Algorithm, we calculate the best individual solution and then seek the best new neighbor of that solution in the social network for that population using Tabu search. In order to speed up the convergence process through knowledge dissemination, simple forms of social network topologies were used to describe the connectivity of individual solutions. This can reduce the number of needed generations while maintaining accuracy and increasing the search radius when needed. The integration of the Tabu search algorithm as a local enhancement process enables CA–TS to leap over false peaks and local optima. The proposed hybrid algorithm is applied to a set of complex non-linear constrained engineering optimization design problems. Furthermore, computational results are discussed to show that the algorithm can produce results that are comparable or superior to those of other well-known optimization algorithms from the literature, and can improve the performance and the speed of convergence with a reduced communication cost.     

求解最大割问题的多启动禁忌搜索算法

为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。     

求解作业车间调度问题的禁忌分布估计算法

为优化作业车间调度问题的解,提出一个禁忌和分布估计的混合算法。分布估计算法是一种新的进化模式,通过概率优化模型在连续空间进行求解;通过对已获得的群体进行选择操作生成优势群体,提出的分布估计算法使用单变量边缘分布算法构建概率模型,估计离散空间中的联合概率分布,从概率向量采样生成新群体;采用基于工件编号的编码和解码机制保证解的可行性。为提高局部搜索能力,算法基于禁忌搜索算法设计新的双重移动组合、块禁忌和选择策略,在搜索陷入局部最优时利用遗传算法的变异算子生成新解;算法通过混合分布估计算法和禁忌搜索算法的优点,兼具全局搜索与局部搜索能力,提高了搜索的效率和性能。通过与现有算法在典型实例上的实验结果比较,表明该算法在求解作业车间调度问题上具有可行性和有效性。     

解决图着色问题的一种新禁忌搜索算法

为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS)。该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性。     

Improved differential evolution algorithms for solving generalized assignment problem

This paper presents algorithms based on differential evolution (DE) to solve the generalized assignment problem (GAP) with the objective to minimize the assignment cost under the limitation of the agent capacity. Three local search techniques: shifting, exchange, and k-variable move algorithms are added to the DE algorithm in order to improve the solutions. Eight DE-based algorithms are presented, each of which uses DE with a different combination of local search techniques. The experiments are carried out using published standard instances from the literature. The best proposed algorithm using shifting and k-variable move as the local search (DE-SK) techniques was used to compare its performance with those of Bee algorithm (BEE) and Tabu search algorithm (TABU). The computational results revealed that the BEE and DE-SK are not significantly different while the DE-SK outperforms the TABU algorithm. However, even though the statistical test shows that DE-SK is not significantly different compared with the BEE algorithm, the DE-SK is able to obtain more optimal solutions (87.5%) compared to the BEE algorithm that can obtain only 12.5% optimal solutions. This is because the DE-SK is designed to enhance the search capability by improving the diversification using the DE's operators and the k-variable moves added to the DE can improve the intensification. Hence, the proposed algorithms, especially the DE-SK, can be used to solve various practical cases of GAP and other combinatorial optimization problems by enhancing the solution quality, while still maintaining fast computational time.     

QoS-driven multicast tree generation using Tabu search

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.     

Disassembly Sequencing Using Tabu Search

End-of-life disassembly has developed into a major research area within the sustainability paradigm, resulting in the emergence of several algorithms and structures proposing heuristics techniques such as Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Neural Networks (NN). The performance of the proposed methodologies heavily depends on the accuracy and the flexibility of the algorithms to accommodate several factors such as preserving the precedence relationships during disassembly while obtaining near- optimal and optimal solutions. This paper improves a previously proposed Genetic Algorithm model for disassembly sequencing by utilizing a faster metaheuristic algorithm, Tabu search, to obtain the optimal solution. The objectives of the proposed algorithm are to minimize (1) the traveled distance by the robotic arm, (2) the number of disassembly method changes, and (3) the number of robotic arm travels by combining the identical-material components together and hence eliminating unnecessary disassembly operations. In addition to improving the quality of optimum sequence generation, a comprehensive statistical analysis comparing the previous Genetic Algorithm and the proposed Tabu Search Algorithm is also included     

Particle Swarm Optimization and Hill Climbing for the bandwidth minimization problem

In this paper, the problem of reducing the bandwidth of sparse matrices by permuting rows and columns is addressed and solved with a new hybrid heuristic which combines the Particle Swarm Optimization method with Hill Climbing (PSO-HC). This hybrid approach exploits a compact PSO in order to generate high-quality renumbering which is then refined by means of an efficient implementation of the HC local search heuristic. Computational experiments are carried out to compare the performance of PSO-HC with the well-known GPS algorithm, as well as some recently proposed methods, including WBRA, Tabu Search and GRASP_PR. PSO-HC proves to be extremely stable and reliable in finding good solutions to the bandwidth minimization problem, outperforming the currently known best algorithms in terms of solution quality, in reasonable computational time.     

Combining meta-learning and search techniques to select parameters for support vector machines

Support Vector Machines (SVMs) have achieved very good performance on different learning problems. However, the success of SVMs depends on the adequate choice of the values of a number of parameters (e.g., the kernel and regularization parameters). In the current work, we propose the combination of meta-learning and search algorithms to deal with the problem of SVM parameter selection. In this combination, given a new problem to be solved, meta-learning is employed to recommend SVM parameter values based on parameter configurations that have been successfully adopted in previous similar problems. The parameter values returned by meta-learning are then used as initial search points by a search technique, which will further explore the parameter space. In this proposal, we envisioned that the initial solutions provided by meta-learning are located in good regions of the search space (i.e. they are closer to optimum solutions). Hence, the search algorithm would need to evaluate a lower number of candidate solutions when looking for an adequate solution. In this work, we investigate the combination of meta-learning with two search algorithms: Particle Swarm Optimization and Tabu Search. The implemented hybrid algorithms were used to select the values of two SVM parameters in the regression domain. These combinations were compared with the use of the search algorithms without meta-learning. The experimental results on a set of 40 regression problems showed that, on average, the proposed hybrid methods obtained lower error rates when compared to their components applied in isolation.     

独立任务分配的贪婪随机自适应搜索过程

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。     

Multi-dimensional visual tracking using scatter search particle filter

Multi-dimensional visual tracking (MVT) problems include visual tracking tasks where the system state is defined by a high number of variables corresponding to multiple model components and/or multiple targets. A MVT problem can be modeled as a dynamic optimization problem. In this context, we propose an algorithm which hybridizes particle filters (PF) and the scatter search (SS) metaheuristic, called scatter search particle filter (SSPF), where the optimization strategies from SS are embedded into the PF framework. Scatter search is a population-based metaheuristic successfully applied to several complex combinatorial optimization problems. The most representative optimization strategies from SS are both solution combination and solution improvement. Combination stage enables the solutions to share information about the problem to produce better solutions. Improvement stage makes also possible to obtain better solutions by exploring the neighborhood of a given solution. In this paper, we have described and evaluated the performance of the scatter search particle filter (SSPF) in MVT problems. Specifically, we have compared the performance of several state-of-the-art PF-based algorithms with SSPF algorithm in different instances of 2D articulated object tracking problem and 2D multiple object tracking. Some of these instances are from the CVBase’06 standard database. Experimental results show an important performance gain and better tracking accuracy in favour of our approach.     

A hybrid Differential Evolution—Tabu Search algorithm for the solution of Job-Shop Scheduling Problems

The Job-Shop Scheduling Problem (JSSP) has drawn considerable interest during the last decades, mainly because of its combinatorial characteristics, which make it very difficult to solve. The good performances attained by local search procedures, and especially Nowicki and Smutnicki's i-TSAB algorithm, encouraged researchers to combine such local search engines with global methods. Differential Evolution (DE) is an Evolutionary Algorithm that has been found to be particularly efficient for continuous optimization, but which does not usually perform well when applied to permutation problems. We introduce in this paper the idea of hybridizing DE with Tabu Search (TS) in order to solve the JSSP. A competitive neighborhood is included within the TS with the aim of determining if DE is able to replace the re-start features that constitute the main strengths of i-TSAB (i.e., a long-term memory and a path-relinking procedure). The computational experiments reported for more than 100 JSSP instances show that the proposed hybrid DE–TS algorithm is competitive with respect to other state-of-the-art techniques, although, there is still room for improvement if the adequacy between the solution representation modes within DE and TS is properly stressed.     

大规模MIMO系统中优化导频分配方案研究

针对大规模MIMO系统中小区间干扰而导致的导频污染问题,提出了基于IGTSA（Improved Greedy and Tabu Search Algorithm,改进贪婪禁忌搜索算法）和基于CA（Competition Algorithm,竞争算法）的导频分配方案。提出的ITSA是将遗传算法中的变异操作加入禁忌算法来避免其陷入局部最优解,提升全局搜索能力。为更好地实现全局搜索与局部搜索的协调统一,引入CA进一步优化以系统可达和速率达到最大为目标的导频分配方案。相比于局部搜索算法,如GA（Greedy Algorithm,贪婪算法）和TSA（Tabu Search Algorithm,禁忌搜索算法）,所提出的方案能获得更优的系统性能。仿真结果和分析证明了算法的有效性。     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

An Evolutionary Parallel Tabu Search approach for distribution systems reinforcement planning

In this paper a new meta-heuristic optimisation technique is proposed. The method is based on the Parallel Tabu Search (PTS) algorithm and the application is the optimal electrical distribution systems reinforcement planning through the installation of photovoltaic plants, parallel cables, capacitor banks and transformers. The issue is a combinatorial optimisation problem; the objective function is a non-linear expression of a large number of variables. In these cases, meta-heuristics have proved to work well and one of the most efficient is the Tabu Search algorithm. For large-scale problems, parallelisation improves Tabu Search computational efficiency as well as its exploration ability. In this paper, an enhanced version of PTS, Evolutionary Parallel Tabu Search (EPTS), is proposed. It performs reproduction operators on sub-neighbourhoods directing the search towards more promising areas of the search space. The problem of distribution systems reinforcement planning has been studied in detail and the results of the application show that the EPTS outperforms the PTS and Particle Swarm Optimisation algorithms.The algorithm's performance is also tested on mathematical test functions and other properties of the proposed algorithm are examined.     

A New Composite Algorithm for Clustering Problems

This paper presents a composite algorithm for solving a class of clustering problems. A quadratic programming formulation of these problems is considered to be solved by the proposed algorithm. In this algorithm a class of non-convex optimization techniques is applied to an approximated variation of the problem and subsequently a local search scheme is incorporated for the final improvement of obtained solutions. The efficiency of the proposed algorithm is evaluated in comparison with Simulated Annealing and Tabu Search algorithms by exploiting a series of real life data from the literature as well as randomly generated data.     

Sampling-based online motion planning for mobile robots: utilization of Tabu search and adaptive neuro-fuzzy inference system

Despite the proven advantages of sampling-based motion planning algorithms, their inability to handle online navigation tasks and providing low-cost solutions make them less efficient in practice. In this paper, a novel sampling-based algorithm is proposed which is able to plan in an unknown environment and provides solutions with lower cost in terms of path length, runtime and stability of the results. First, a fuzzy controller is designed which incorporates the heuristic rules of Tabu search to enable the planner for solving online navigation tasks. Then, an adaptive neuro-fuzzy inference system (ANFIS) is proposed such that it constructs and optimizes the fuzzy controller based on a set of given input/output data. Furthermore, a heuristic dataset generator is implemented to provide enough data for the ANFIS using a randomized procedure. The performance of the proposed algorithm is evaluated through simulation in different motion planning queries. Finally, the proposed planner is compared to some of the similar motion planning algorithms to support the claim of superiority of its performance.

     

一种禁忌搜索算法在二维HP非格模型中的应用

禁忌搜索算法是一种启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题,本文探讨将一种记忆的禁忌搜索算法应用于求解蛋白质结构预测问题。文中首先介绍了一种二维HP非格模型,此模型最后可以归结为一个全局优化问题,然后介绍了记忆的禁忌搜索算法在其中的应用,通过与PERM（Pruned—Enriched—Rosenbluth Method）比较,发现禁忌算法能得到较好的实验结果,经分析发现虽然二维HP非格模型很简单,但却能反映蛋白质结构的一些简单的性质,即在蛋白质结构中,疏水性氨基酸形成束,总是被极性氨基酸包围。数值实验表明该算法对于蛋白质结构预测是可行有效的。     

极小化加权完工时间的多资源工序的资源分配问题

针对现实中广泛存在的多资源工序的资源分配问题,考虑基于资源使用的优先次序约束,以最小化加权完工时间为优化目标,构建一类新的资源分配混合整数线性规划模型.其次,提出Benders分解和禁忌搜索的混合算法,该混合算法以Benders分解为基本框架,将原问题分为提供资源分配方案的主问题和计算工序加权完工时间的子问题,并通过改进数学模型和添加禁忌搜索提高混合算法的收敛速度.最后,通过300个随机仿真算例测试结果表明,在相同时间下求解小规模问题时,所提的Benders分解混合算法能获得距离商业求解器CPLEX最优解平均差距为0.86%的满意解;在求解大规模问题时,所提出的算法的性能表现优于CPLEX、禁忌搜索算法、变邻域搜索算法和Benders分解嵌入遗传算法的混合方法,能给出更好的资源分配方案,与CPLEX相比,上界和下界分别改善了4.74%和9.62%.     

Modified Cuckoo Search Algorithm to Solve Economic Power Dispatch Optimization Problems

A modified cuckoo search (CS) algorithm is proposed to solve economic dispatch (ED) problems that have nonconvex, non-continuous or non-linear solution spaces considering valve-point effects, prohibited operating zones, transmission losses and ramp rate limits. Comparing with the traditional cuckoo search algorithm, we propose a self-adaptive step size and some neighbor-study strategies to enhance search performance. Moreover, an improved lambda iteration strategy is used to generate new solutions. To show the superiority of the proposed algorithm over several classic algorithms, four systems with different benchmarks are tested. The results show its efficiency to solve economic dispatch problems, especially for large-scale systems.