A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency

The orthogonal segment intersection search problem is stated as follows: given a setS ofn orthogonal segments in the plane, report all the segments ofS that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, inO(n) time preprocessing, a search structure of sizeO(n) so that all the segments ofS intersecting a query segment can be reported inO(k) time in the average case, wherek is the number of the reported segments. The proposed algorithm as well as existing algorithms is implemented in FORTRAN, and their practical efficiencies are investigated through computational experiments. It is shown that ourO(k) search time,O(n) space, andO(n) preprocessing time algorithm is in practice the most efficient among the algorithms tested.Supported by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture of Japan under Grant No. 62550270 (1987).     

A random direction algorithm for an intersection problem

A nonlinear SOR-type algorithm is established to find the intersection of a finite number of closed convex sets in a Hilbert space.     

A search algorithm for the traveling salesman problem

A search algorithm, based on the concepts of lexicographic search and sequential decision processes, is proposed for the solution of the traveling salesman problem. Starting with an initial trial solution, the search algorithm sequentially generates better tours until an optimal (least cost) tour is identified. The logical structure of the search algorithm is such that the computational effort required to solve a problem by the proposed approach is less than that by the branch and bound procedures.     

A hybrid search algorithm for the Whitehead Minimization problem

The Whitehead Minimization problem is a problem of finding elements of the minimal length in the automorphic orbit of a given element of a free group. The classical algorithm of Whitehead that solves the problem depends exponentially on the group rank. Moreover, it can be easily shown that exponential blowout occurs when a word of minimal length has been reached and, therefore, is inevitable except for some trivial cases.In this paper we introduce a deterministic Hybrid search algorithm and its stochastic variation for solving the Whitehead Minimization problem. Both algorithms use search heuristics that allow one to find a length-reducing automorphism in polynomial time on most inputs and significantly improve the reduction procedure. The stochastic version of the algorithm employs a probabilistic system that decides in polynomial time whether or not a word is minimal. The stochastic algorithm is very robust. It has never happened that a non-minimal element has been claimed to be minimal.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

平面选址问题的引力搜索算法求解

为求解平面选址问题,给出了一种基于引力搜索算法的求解方法。算法利用万有引力定律进行全局搜索,采用一种邻域搜索方法进行局部搜索,实现算法全局优化和局部优化的平衡。通过大量实验和与现有求解方法的比较,结果验证了算法的可行性和有效性。     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.     

A parallel hybrid local search algorithm for the container loading problem

In this contribution, a parallel hybrid local search algorithm for the three‐dimensional container loading problem (CLP) is proposed. First a simulated annealing method for the CLP is developed, which is then combined with an existing tabu search algorithm to form a hybrid metaheuristic. Finally, parallel versions are introduced for these algorithms. The emphasis is on CLP instances with a weakly heterogeneous load. Numerical tests based on the well‐known 700 test instances from Bischoff and Ratcliff are performed, and the outcome is compared with methods from other authors. The results show a high solution quality obtained with reasonable computing time.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

A novel global harmony search algorithm for task assignment problem

The objective of task assignment problem (TAP) is to minimize the sum of interprocessor communication and task processing costs for a distributed system which subjects to several resource constraints. We use a novel global harmony search algorithm (NGHS) to solve this problem, and the NGHS algorithm has demonstrated higher efficiency than the improved harmony search algorithm (IHS) on finding the near optimal task assignment. We also devise a new method called normalized penalty function method to tradeo^® the costs and the constraints. A large number of experiments show that our algorithm performs well on finding the near optimal task assignment, and it is a viable approach for the task assignment problem.     

Multi-objective orthogonal opposition-based crow search algorithm for large-scale multi-objective optimization

Neural Computing and Applications - Many engineering optimization problems are typically multi-objective in their natures and multidisciplinary with a large number of decision variables....     

A hybrid harmony search algorithm for the flexible job shop scheduling problem

In this paper, a novel hybrid harmony search (HHS) algorithm based on the integrated approach, is proposed for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize makespan. First of all, to make the harmony search (HS) algorithm adaptive to the FJSP, the converting techniques are developed to convert the continuous harmony vector to a kind of discrete two-vector code for the FJSP. Secondly, the harmony vector is mapped into a feasible active schedule through effectively decoding the transformed two-vector code, which could largely reduce the search space. Thirdly, a resultful initialization scheme combining heuristic and random strategies is introduced to make the initial harmony memory (HM) occur with certain quality and diversity. Furthermore, a local search procedure is embedded in the HS algorithm to enhance the local exploitation ability, whereas HS is employed to perform exploration by evolving harmony vectors in the HM. To speed up the local search process, the improved neighborhood structure based on common critical operations is presented in detail. Empirical results on various benchmark instances validate the effectiveness and efficiency of our proposed algorithm. Our work also indicates that a well designed HS-based method is a competitive alternative for addressing the FJSP.     

A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem

In the heterogeneous fixed fleet vehicle routing problem there are different types of vehicles and a given number of vehicles of each type. The resolution of this problem consists of assigning the customers to the existing vehicles and, in relation to each vehicle, defining the order of visiting each customer for the delivery or collection of goods. The objective is to minimize the total costs, satisfying customers’ requirements and visiting each customer exactly once. In this paper a tabu search algorithm is proposed and tested on several benchmark problems. The computational experiments show that the proposed algorithm produces high quality solutions within an acceptable computation time. Four new best solutions are reported for a set of test problems used in the literature.     

Clustering search algorithm for the capacitated centered clustering problem

The capacitated centered clustering problem (CCCP) consists in partitioning a set of n points into p disjoint clusters with a known capacity. Each cluster is specified by a centroid. The objective is to minimize the total dissimilarity within each cluster, such that a given capacity limit of the cluster is not exceeded. This paper presents a solution procedure for the CCCP, using the hybrid metaheuristic clustering search (CS), whose main idea is to identify promising areas of the search space by generating solutions through a metaheuristic and clustering them into groups that are then further explored with local search heuristics. Computational results in test problems of the literature show that the CS found a significant number of new best-known solutions in reasonable computational times.     

Discrete cuckoo search algorithm for the travelling salesman problem

In this paper, we present an improved and discrete version of the Cuckoo Search (CS) algorithm to solve the famous traveling salesman problem (TSP), an NP-hard combinatorial optimisation problem. CS is a metaheuristic search algorithm which was recently developed by Xin-She Yang and Suash Deb in 2009, inspired by the breeding behaviour of cuckoos. This new algorithm has proved to be very effective in solving continuous optimisation problems. We now extend and improve CS by reconstructing its population and introducing a new category of cuckoos so that it can solve combinatorial problems as well as continuous problems. The performance of the proposed discrete cuckoo search (DCS) is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.     

A fast hybrid tabu search algorithm for the no-wait job shop problem

This paper describes a hybrid tabu search algorithm dedicated to a job shop problem with a no-wait constraint with a makespan criterion. The proposed here algorithm complexity is that the superior algorithm based on the tabu search technique selects parameters controlling the work of a certain constructional algorithm. This approach limits the checked solutions only to a group of solutions being able to be generated by the structural algorithm in question. It bears serious consequences both positive, for example it limits the research scope for a small fraction of relatively extremely well quality of acceptable solutions, and negative that is the lack of possibility of finding the optimal solution. In this paper numerical researches of the proposed algorithm are conducted as well as a comparative analysis with reference to the literature algorithms of the algorithm in question is made.     

A restart local search algorithm for solving maximum set k-covering problem

The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances.

     

配送中心选址问题的和谐搜索算法

针对一类配送中心选址问题,建立了问题的数学模型,将和谐搜索算法进行改进并对问题进行求解,最后将此算法与最优保存算法(EGA)和遗传算法(GA)进行比较,验证了算法在计算结果方面的精确性和计算时间上的高效性。     

自适应布谷鸟算法及其在化工优化中的应用

动态优化问题广泛存在于化工自动控制过程中,对其求解是化工过程工业发展的一个不可忽视的环节。群智能算法求解此类优化问题时不可避免地存在后期收敛速度慢、求解精度的不高等不足,这一直是一个研究热点。针对新兴的布谷鸟算法与以上问题,提出一种变步长自适应布谷鸟搜索算法(VSACS),将基本布谷鸟搜索(CS)算法中的随机步长改进成根据迭代次数自适应调整的步长。通过15个标准测试函数的测试,结果验证了改进的算法有较快的收敛速度和较高的求解精度。最后将改进的算法用于批示反应器、管式反应器、生物反应器等3个典型的化工动态优化问题中,获得了满意的实验结果,同时也进一步表明该算法的有效性。