共查询到20条相似文献,搜索用时 203 毫秒
1.
A Tabu Search Algorithm for the Quadratic Assignment Problem 总被引:1,自引:0,他引:1
Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances. 相似文献
2.
Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem 总被引:1,自引:0,他引:1
Manuel López-Ibáñez Luís Paquete Thomas Stützle 《Journal of Mathematical Modelling and Algorithms》2006,5(1):111-137
We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling
multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu
search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated
for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The
experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the
algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance
of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time
is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant.
This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science
Department of Darmstadt University of Technology, Germany 相似文献
3.
A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn
2 processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time. 相似文献
4.
In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search
algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about
the best solutions found and new initial solutions for tabu search. The rapid production of a good solution from the tabu
search process provides the branch-and-bound process with a better feasible solution to accelerate the elimination of subproblems
that do not contain an optimal solution. The new initial solution produced from the subproblem with a least-cost lower bound
of the branch-and-bound method suggests the best potential area for tabu search to explore. We use a master-slave model to
reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as
the master process to control the exchange of information and the termination of computation. Several tabu search processes
are executed simultaneously as the slave processes and cooperate by asynchronously exchanging information on the best solutions
found and the new initial solutions by the master process of branch-and-bound. Based on the computation experiments of solving
traveling salesman problems (TSP), the proposed heterogeneous parallel search algorithm outperforms a conventional parallel
branch-and-bound method and a conventional parallel tabu search. We also present the computational results showing the efficiency
of heterogeneous cooperative parallel search when we use more processors to accelerate search time. Thus, the proposed heterogeneous
parallel search algorithm achieves linear accelerations. 相似文献
5.
This paper studies the learning process in an ant colony optimization algorithm designed to solve the problem of ordering cars on an assembly line (car-sequencing problem). This problem has been shown to be NP-hard and evokes a great deal of interest among practitioners. Learning in an ant algorithm is achieved by using an artificial pheromone trail, which is a central element of this metaheuristic. Many versions of the algorithm are found in literature, the main distinction among them being the management of the pheromone trail. Nevertheless, few of them seek to perfect learning by modifying the internal structure of the trail. In this paper, a new pheromone trail structure is proposed that is specifically adapted to the type of constraints in the car-sequencing problem. The quality of the results obtained when solving three sets of benchmark problems is superior to that of the best solutions found in literature and shows the efficiency of the specialized trail. 相似文献
6.
The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP.
ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two
major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated
chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback
mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO
phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the
next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose
a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We
report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested
and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%.
This work was supported in part by the National Science Council, R.O.C., under Contract NSC 91-2213-E-005-017. 相似文献
7.
Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this
paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension
of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose
the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore,
a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark
problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches
to the problem. 相似文献
8.
9.
In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this. 相似文献
10.
A comparison of local search methods for flow shop scheduling 总被引:1,自引:0,他引:1
Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing. 相似文献
11.
Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems 总被引:2,自引:0,他引:2
A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing. 相似文献
12.
Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner. 相似文献
13.
Siamak Noori S. Farid Ghannadpour 《Journal of Mathematical Modelling and Algorithms》2012,11(2):159-179
This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau??s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature. 相似文献
14.
Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies. 相似文献
15.
This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search. 相似文献
16.
Akbar Karimi Hadi Nobahari Patrick Siarry 《Computational Optimization and Applications》2010,45(3):639-661
A new hybrid optimization method, combining Continuous Ant Colony System (CACS) and Tabu Search (TS) is proposed for minimization
of continuous multi-minima functions. The new algorithm incorporates the concepts of promising list, tabu list and tabu balls
from TS into the framework of CACS. This enables the resultant algorithm to avoid bad regions and to be guided toward the
areas more likely to contain the global minimum. New strategies are proposed to dynamically tune the radius of the tabu balls
during the execution and also to handle the variable correlations. The promising list is also used to update the pheromone
distribution over the search space. The parameters of the new method are tuned based on the results obtained for a set of
standard test functions. The results of the proposed scheme are also compared with those of some recent ant based and non-ant
based meta-heuristics, showing improvements in terms of accuracy and efficiency. 相似文献
17.
Scheduling problems in real systems often require sequence-dependent setup times. The topic of sequence-dependent setup times has not been addressed adequately, and improved competitiveness is thus not achieved. This study proposes a hybrid approach that takes advantage of simulated annealing (SA) and tabu search (TS) to solve single-machine tardiness problems with sequence-dependent setup times. To verify the proposed approach, experiments were conducted on benchmark problem sets that included both the weighted and un-weighted tardiness problems. The results show that the performance of the hybrid approach is superior to that of the SA, genetic algorithm, TS and ant colony optimization approaches, and is comparable with the Tabu-VNS approach. And the proposed approach found new upper bound values for many benchmark problems with an acceptable computational time. 相似文献
18.
C Gagné M Gravel S Morin W L Price 《The Journal of the Operational Research Society》2008,59(8):1077-1090
This paper compares different ant colony optimization algorithms for solving the NP-hard car-sequencing problem, which is of great practical interest. The five algorithms that are compared are the Ant System (AS), the Elitist AS, the Rank-Based AS, the Max–Min AS and the Ant Colony System. These algorithms, which are well known in the literature, differ in the way in which the pheromone trail is managed. The comparative analysis seeks to identify which algorithm best manages the learning process in solving the car-sequencing problem. Moreover, we propose a new structure for the pheromone trail specifically designed to take advantage of the type of constraints found in the car-sequencing problem. The quality of the results obtained with this new form of learning for three problem sets drawn from the literature is superior to that of the best results published and demonstrates the efficiency of this new trail structure. 相似文献
19.
N Wassan 《The Journal of the Operational Research Society》2007,58(12):1630-1641
A heuristic approach based on a hybrid operation of reactive tabu search (RTS) and adaptive memory programming (AMP) is proposed to solve the vehicle routing problem with backhauls (VRPB). The RTS is used with an escape mechanism which manipulates different neighbourhood schemes in a sophisticated way in order to get a continuously balanced intensification and diversification during the search process. The adaptive memory strategy takes the search back to the unexplored regions of the search space by maintaining a set of elite solutions and using them strategically with the RTS. The AMP feature brings an extra robustness to the search process that resulted in early convergence when tested on most of the VRPB instances. We compare our algorithm against the best methods in the literature and report new best solutions for several benchmark problems. 相似文献
20.
Hari K. Rajagopalan F. Elizabeth Vergara Cem Saydam Jing Xiao 《European Journal of Operational Research》2007
This article employs a statistical experimental design to guide and evaluate the development of four meta-heuristics applied to a probabilistic location model. The meta-heuristics evaluated include evolutionary algorithm, tabu search, simulated annealing, and a hybridized hill-climbing algorithm. Comparative results are analyzed using ANOVA. Our findings show that all four implementations produce high quality solutions. In particular, it was found that on average tabu search and simulated annealing find their best solutions in the least amount of time, with relatively small variability. This is especially important for large-size problems when dynamic redeployment is required. 相似文献