This paper proposed a hierarchical hybrid algorithm for traveling salesman problem (TSP) according to the idea of divide-and-conquer. The TSP problem is decomposed into a few subproblems with small-scale nodes by dens...
详细信息
This paper proposed a hierarchical hybrid algorithm for traveling salesman problem (TSP) according to the idea of divide-and-conquer. The TSP problem is decomposed into a few subproblems with small-scale nodes by density peaks clustering algorithm. Every subproblem is resolved by ant colony optimization algorithm, this is the lower layer. The center nodes of all subproblems constitute a new TSP problem, which forms the upper layer. All local tours of these subproblems are joined to generate the initial global tour in the same order that the center nodes are traversed in the upper layer TSP problem. Finally, the global tour is optimized by k-opt algorithms. Thirty benchmark instances taken from TSPLIB are divided into three groups on the basis of problem size: small-scale, large-scale, and very large-scale. The experimental result shows that the proposed algorithm can obtain the solutions with higher accuracy and stronger robustness, and significantly reduce runtime, especially for the very large-scale TSP problem.
The generalized traveling salesman problem(GTSP) is a typical combinatorial optimization problem. Many practical problems involving the allocation and optimization of multiple tasks can be reduced to the generalized t...
详细信息
ISBN:
(纸本)9781728101057
The generalized traveling salesman problem(GTSP) is a typical combinatorial optimization problem. Many practical problems involving the allocation and optimization of multiple tasks can be reduced to the generalized traveling salesman problem. A modified ant colony optimization is proposed for GTSP. The modified ant colony algorithm combines 2-optalgorithm to minimize the total path length, while considering the task balance of different travelers. Simulation results show that the modified ant colony optimization has good optimization accuracy and stability in solving the generalized traveling salesman problem.
Finite Impulse Response (FIR) digital filters are widely used due to their capabilities of low computational load, stability and linear phase. Most traditional design approaches can not control with enough accuracy th...
详细信息
ISBN:
(纸本)9789082797015
Finite Impulse Response (FIR) digital filters are widely used due to their capabilities of low computational load, stability and linear phase. Most traditional design approaches can not control with enough accuracy the frequency response of the designed filter. For this reason, we propose the use of a memetic algorithm along with a weighted fitness function, to estimate optimized filter coefficients that best approximate ideal specifications. Results have been compared to both traditional methods (mainly windowing and the Parks-McClellan algorithm) as well as to several bio-inspired techniques. Numerical results show that proposed method achieves better fit to filter specifications, a larger attenuation in the stop band and a narrower transition band, at the expense of slightly increasing the pass-band ripple (0.5 - 0.7 dB), the later in about 68% of the cases.
This paper proposed a novel hybrid algorithm for path planning at macroscopic level for autonomous climbing robot. The path planning is an Asymmetric Traveling Salesman Problem (ATSP). The problem can be decomposed in...
详细信息
ISBN:
(纸本)9781538695944
This paper proposed a novel hybrid algorithm for path planning at macroscopic level for autonomous climbing robot. The path planning is an Asymmetric Traveling Salesman Problem (ATSP). The problem can be decomposed into some groups with small-scale points by Density Peaks Clustering algorithm (DPC), and these groups are divided into two types based on the node distribution: dense groups and sparse groups. Then local paths for all groups are solved by Ant Colony optimization algorithm (ACO) and merged at the nearest pair of points between the two adjacent groups to generate the initial global path. At last, the final global path is obtained after optimizing by k-opt algorithms. The proposed algorithm is tested on nine benchmark instances compared with four other algorithms. Simulation experiment result shows that the proposed algorithm can provide the solution with higher accuracy and shorter runtime.
暂无评论