Dissertations / Theses on the topic 'Tabu Search'
To see the other types of publications on this topic, follow the link: Tabu Search.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Tabu Search.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Whittley, Ian Murray. "Tabu search-revisited." Thesis, University of East Anglia, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.251720.
Full text
2
Slomka, Frank. "Mehrkriterienoptimierung verteilter Echtzeitsysteme mit Tabu-Search /." Düssdeldorf : VDI-Verl, 2002. http://www.gbv.de/dms/bs/toc/35430979x.pdf.
Full text
3
Al-Hamad, Khaled. "Tabu search for ship routing and scheduling." Thesis, Brunel University, 2006. http://bura.brunel.ac.uk/handle/2438/5071.
Full textAbstract:
This thesis examines exact and heuristic approaches to solve the Ship Routing and Scheduling Problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous vessels. Constraints relate to delivery time windows imposed by customers, the time horizon by which all deliveries must be made and vessel capacities. The objective is to minimise the overall operation cost, where all customers are satisfied. Two types of routing and scheduling are considered, one called single-cargo problem, where only one cargo can be loaded into a ship, and the second type called multi-cargo problem, where multiple products can be carried on a ship to be delivered to different customers. The exact approach comprises two stages. In the first stage, a number of candidate feasible schedules is generated for each ship in the fleet. The second stage is to model the problem as a set partitioning problem (SPP) where the columns are the candidate feasible schedules obtained in the first stage. The heuristic approach uses Tabu Search (TS). Most of the TS operations, such as insert and swap moves, tenure, tabu list, intensification, and diversification are used. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the tabu search such as tenure and neighbourhood size. The results showed that the average of the solution gap between TS solution and SPP solution is up to 28% (for small problems) and up to 18% for large problems. However, obtaining an optimal solution requires a large amount of computer time to produce the solution compared to obtaining approximate solutions using the TS approach. The use of Tabu Search for SRSP is novel and the results indicate that it is viable approach for large problems.
4
Cruz, António Manuel Costa. "IMRT beam angle optimization using Tabu search." Master's thesis, Universidade de Aveiro, 2014. http://hdl.handle.net/10773/17714.
Full textAbstract:
Mestrado em Matemática e AplicaçõesO número de pacientes com cancro continua a crescer no mundo e a Organização Mundial da Saúde considerou mesmo esta como uma das principais ameaças para a saúde e o desenvolvimento humano. Dependendo da localização e das especi cidades do tumor, existem muitos tratamentos que podem ser usados, incluindo cirurgia, quimioterapia, imunoterapia e radioterapia. A Radioterapia de Intensidade Modulada (IMRT | Intensity Modulated Radiation Therapy) é uma das modalidades mais avançadas de radioterapia, onde a otimização pode ter um papel importante no que diz respeito à qualidade do tratamento aplicado. Em IMRT, o feixe de radiação pode ser visto como se fosse constituído por vários pequenos feixes, pelo uso de um colimador multifolhas, que permite que a intensidade seja modulada. Este complexo problema de otimização pode ser dividido em três subproblemas, que estão relacionados entre si e que podem ser resolvidos sequencialmente. Para cada paciente, os ângulos de onde a radiação ir a ocorrer têm de ser determinados (problema geométrico | otimização angular). Depois, para cada um desses ângulos, o mapa de intensidades (ou fluências) tem de ser calculado (problema das intensidades | otimização das fluências). Finalmente, e necessário determinar o comportamento do colimador multifolhas, de forma a garantir que as intensidades são, de facto, atribuídas (problema de realiza ção). Em cada um destes problemas de otimização, a qualidade do tratamento atribuído depende dos modelos e algoritmos usados. Neste trabalho, a nossa atenção estará particularmente focada na otimização angular, um problema conhecido por ser altamente não-convexo, com muitos mínimos locais e com uma função objetivo que requer muito tempo de computação para ser calculada. Tal significa, respetivamente, que os algoritmos que sejam baseados no cálculo de gradientes ou que requeiram muitas avaliações da função objetivo podem não ser adequados. Assim, os procedimentos metaheurísticos podem ser uma boa alternativa para abordar este problema, visto que são capazes de escapar de mínimos locais e são conhecidos por conseguirem calcular boas soluções em problemas complexos. Neste trabalho ser a descrita uma aplicação para Pesquisa Tabu. Serão ainda apresentados os testes computacionais realizados, considerando dez casos clínicos de pacientes previamente tratados por radioterapia, pretendendo-se mostrar que a Pesquisa Tabu e capaz de melhorar os resultados obtidos através da solução equidistante, cujo uso e comum na prática clínica.
The number of cancer patients continues to grow worldwide and the World Health Organization has even considered cancer as one of the main threats to human health and development. Depending on the location and speci cities of the tumor, there are many treatments that can be used, including surgery, chemotherapy, immunotherapy and radiation therapy. Intensity Modulated Radiation Therapy (IMRT) is one of the most advanced radiation therapy modalities, and optimization can have a key role in the quality of the treatment delivered. In IMRT, the radiation beam can be thought of as being composed by several small beams, through the use of a multileaf collimator, allowing radiation intensity to be modulated. This complex optimization problem can be divided in three related subproblems that can be solved sequentially. For each patient, the angles from which the radiation will be delivered have to be determined (geometric problem | beam angle optimization). Then, for each of these angles, the radiation intensity map is calculated ( uence or intensity optimization). Finally, it is necessary to determine the behavior of the multileaf collimator that guarantees that the desired radiation intensities are, indeed, delivered (realization problem). In each of these optimization problems, the quality of the treatment delivered depends on the models and algorithms used. In this work the attention will be focused in beam angle optimization, a problem known to be highly non{convex, with many local minima and with an objective function that is time expensive to calculate, which, respectively, means that algorithms that are gradient{based or that require many objective function evaluations will not be adequate. Metaheuristics can be the right tool to tackle this problem, since they are capable of escaping local minima and are known to be able to calculate good solutions for complex problems. In this work, an application of Tabu Search to beam angle optimization is described. Computational results considering ten clinical cases of head{and{neck cancer patients are presented, showing that Tabu Search is capable of improving the equidistant solution usually used in clinical practice.
5
Stepanenko, Svetlana. "Global Optimization Methods based on Tabu Search." Doctoral thesis, kostenfrei, 2008. http://www.opus-bayern.de/uni-wuerzburg/volltexte/2008/3060/.
Full text
6
SHARMA, VIKAS. "QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION." University of Cincinnati / OhioLINK, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin990820742.
Full text
7
Achan, Kannan. "Tabu search in multi-hop optical network design." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0013/MQ52497.pdf.
Full text
8
Lightner, Carin Ann. "A Tabu Search Approach to Multiple Sequence Alignment." NCSU, 2008. http://www.lib.ncsu.edu/theses/available/etd-05312008-191232/.
Full textAbstract:
Sequence alignment methods are used to detect and quantify similarities between different DNA and protein sequences that may have evolved from a common ancestor. Effective sequence alignment methodologies also provide insight into the structure function of a sequence and are the first step in constructing evolutionary trees. In this dissertation, we use a tabu search approach to multiple sequence alignment. A tabu search is a heuristic approach that uses adaptive memory features to align multiple sequences. The adaptive memory feature, a tabu list, helps the search process avoid local optimal solutions and explores the solution space in an efficient manner. We develop two main tabu searches that progressively align sequences. A randomly generated bifurcating tree guides the alignment. The objective is to optimize the alignment score computed using either the sum of pairs or parsimony scoring function. The use of a parsimony scoring function provides insight into the homology between sequences in the alignment. We also explore iterative refinement techniques such as a hidden Markov model and an intensification heuristic to further improve the alignment. This approach to multiple sequence alignment provides improved alignments as compared to several other methods.
9
Lin, Yu-Min. "Tabu Search and Genetic Algorithm for Phylogeny Inference." NCSU, 2008. http://www.lib.ncsu.edu/theses/available/etd-10092008-235130/.
Full textAbstract:
Phylogenetics is the study of evolutionary relations between different organisms. Phylogenetic trees are the representations of these relations. Researchers have been working on finding fast and systematic approaches to reconstruct phylogenetic trees from observed data for over 40 years. It has been shown that, given a certain criterion to evaluate each tree, finding the best fitted phylogenetic trees among all possible trees is an NP-hard problem. In this study, we focus on the topology searching techniques for the maximum-parsimony and maximum-likelihood phylogeny inference. We proposed two search methods based on tabu search and genetic algorithms. We first explore the feasibility of using tabu search for finding the maximum-parsimony trees. The performance of the proposed algorithm is evaluated based on its efficiency and accuracy. Then we proposed a hybrid method of the tabu search and genetic algorithm. The experimental results indicate that the hybrid method can provide maximum-parsimony trees with a ggood level of accuracy and efficiency. The hybrid method is also implemented for finding maximum-likelihood trees. The experimental results show that the proposed hybrid method produce better maximum-likelihood trees than the default-setting dnaml program in average on the tested data sets. On a much larger data set, the hybrid method outperforms the default-setting dnaml program and has equally good performance as the dnaml program with the selected jumble option.
10
黃頌詩 and Chung-sze Wong. "Tabu search-based techniques for clustering data sets." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2001. http://hub.hku.hk/bib/B42576556.
Full text
11
Wong, Chung-sze. "Tabu search-based techniques for clustering data sets." Click to view the E-thesis via HKUTO, 2001. http://sunzi.lib.hku.hk/hkuto/record/B42576556.
Full text
12
Malleypally, Vinaya. "Parallelizing Tabu Search Based Optimization Algorithm on GPUs." Scholar Commons, 2018. https://scholarcommons.usf.edu/etd/7638.
Full textAbstract:
There are many combinatorial optimization problems such as traveling salesman problem, quadratic-assignment problem, flow shop scheduling, that are computationally intractable. Tabu search based simulated annealing is a stochastic search algorithm that is widely used to solve combinatorial optimization problems. Due to excessive run time, there is a strong demand for a parallel version that can be applied to any problem with minimal modifications. Existing advanced and/or parallel versions of tabu search algorithms are specific to the problem at hand. This leads to a drawback of optimization only for that particular problem. In this work, we propose a parallel version of tabu search based SA on the Graphics Processing Unit (GPU) platform. We propose two variants of the algorithm based on where the tabu list is stored (global vs. local). In the first version, the list is stored in the global shared memory such that all threads can access this list. Multiple random walks in solution space are carried out. Each walk avoids the moves made in rest of the walks due to their access to global tabu list at the expense of more time. In the second version, the list is stored at the block level and is shared by only the block threads. Groups of random walks are performed in parallel and a walk in a group avoids the moves made by the rest of the walks within that group due to their access to shared local tabu list. This version is better than the first version in terms of execution time. On the other hand, the first version finds the global optima more often. We present experimental results for six difficult optimization functions with known global optima. Compared to the CPU implementation with similar workload, the proposed GPU versions are faster by approximately three orders of magnitude and often find the global optima.
13
Liu, Wen-Hsing. "Tabu search heuristics for the dynamic facility layout problem." Morgantown, W. Va. : [West Virginia University Libraries], 2005. https://eidr.wvu.edu/etd/documentdata.eTD?documentid=3973.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2005.Title from document title page. Document formatted into pages; contains vii, 88 p. : ill. Includes abstract. Includes bibliographical references (p. 83-88).
14
Zekaoui, Latifa. "Mixed covering arrays on graphs and tabu search algorithms." Thesis, University of Ottawa (Canada), 2006. http://hdl.handle.net/10393/27433.
Full textAbstract:
Covering arrays are combinatorial objects that have been successfully applied in the design of test suits for testing software, networks and circuits. Mixed covering arrays on graphs are new generalizations of both mixed covering arrays and covering arrays on graphs.
In this thesis, we give new theoretical results and constructions for mixed covering arrays on graphs. First, we extend to the mixed case the work done by Meagher and Stevens [31], which uses graph homomorphisms for covering arrays on graphs. Second, we study covering arrays on special classes of graphs. In particular, we solve to optimality the case in which G is a tree, a cycle or a bipartite graph, as well as give results for wheels and cubic graphs. We also provide general graph operations that preserve the size of a balanced covering array.
In the second part of the thesis, we do a complete experimental study of two tabu search algorithms for covering array construction. POT is a variation of the algorithm given by Stardom [40] while PAT is an implementation of the algorithm proposed by Nurmela [35]. We conclude that they provide effective methods for constructing covering arrays of moderate size. In particular, POT and PAT improve upper bounds for 18 sets of parameters for covering arrays.
15
Bozkaya, Burcin. "Political districting, a tabu search algorithm and geographical interfaces." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0024/NQ39508.pdf.
Full text
16
Coombes, Neil Edwin. "The reactive tabu search for efficient correlated experimental designs." Thesis, Liverpool John Moores University, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.275932.
Full text
17
Hussin, Naimah Mohd. "Tabu search based hyper-heuristic for examination timetabling problem." Thesis, University of Nottingham, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.423286.
Full text
18
Benjamin, Aida Mauziah. "Metaheuristics for the waste collection vehicle routing problem with time windows." Thesis, Brunel University, 2011. http://bura.brunel.ac.uk/handle/2438/5254.
Full textAbstract:
In this thesis there is a set of waste disposal facilities, a set of customers at which waste is collected and an unlimited number of homogeneous vehicles based at a single depot. Empty vehicles leave the depot and collect waste from customers, emptying themselves at the waste disposal facilities as and when necessary. Vehicles return to the depot empty. We take into consideration time windows associated with customers, disposal facilities and the depot. We also have a driver rest period. The problem is solved heuristically. A neighbour set is defined for each customer as the set of customers that are close, but with compatible time windows. This thesis uses six different procedures to obtain initial solutions for the problem. Then, the initial solutions from these procedures are improved in terms of the distance travelled using our phase 1 and phase 2 procedures, whereas we reduce the number of vehicles used using our vehicle reduction (VR) procedure. In a further attempt to improve the solutions three metaheuristic algorithms are presented, namely tabu search (TS), variable neighbourhood search (VNS) and variable neighbourhood tabu search (VNTS). Moreover, we present a modified disposal facility positioning (DFP), reverse order and change tracking procedures. Using all these procedures presented in the thesis, four solution procedures are reported for the two benchmark problem sets, namely waste collection vehicle routing problems with time windows (VRPTW) and multi-depot vehicle routing problem with inter-depot routes (MDVRPI). Our solutions for the waste collection VRPTW problems are compared with the solutions from Kim et al (2006), and our solutions for the MDVRPI problems are compared with Crevier et al (2007). Computational results for the waste collection VRPTW problems indicate that our algorithms produce better quality solutions than Kim et al (2006) in terms of both distance travelled and number of vehicles used. However for the MDVRPI problems, solutions from Crevier et al (2007) outperform our solutions.
19
Osman, Ibrahim Hassan. "Metastrategy : simulated annealing and tabu search for combinatorial optimization problems." Thesis, Imperial College London, 1991. http://hdl.handle.net/10044/1/7596.
Full text
20
Richards, Evelyn Winnifred. "A tabu search method for a tactical forest planning problem." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/NQ31532.pdf.
Full text
21
Wassan, Niaz Ahmed. "Tabu search metaheuristics for a class of vehicle routing problems." Thesis, University of Kent, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.263742.
Full text
22
Iyer, Krishnakumar R. "Tabu search algorithm for a thermal aware VLSI floorplanning application." University of Cincinnati / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1384426610.
Full text
23
Jaramillo, Juan R. "A tabu search approach for the dynamic space allocation problem." Morgantown, W. Va. : [West Virginia University Libraries], 2002. http://etd.wvu.edu/templates/showETD.cfm?recnum=2712.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2002.Title from document title page. Document formatted into pages; contains xi, 87 p. : ill. Includes abstract. Includes bibliographical references (p. 84-87).
24
Khambhampati, Surya Sudha. "A Tabu Search Heuristic for Multi-Period Clustering to Rationalize Delivery Operations." Wright State University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=wright1210959864.
Full text
25
Šidla, Donatas. "Ruošinių realizacijos optimizavimo procedūrų sudarymas ir tyrimas." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2004. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2004~D_20040530_221515-42762.
Full textAbstract:
The object of Master Thesis is the creation and research optimization of blank realization procedures. Four main parts comprise the thesis: analysis of the problem, theoretical solutions, research and outcomes, conclusions and recommendations. Optimization methods, their advantages and limitations have been analyzed in the first part. The most appropriate optimization method for problem solving was selected. Designed optimization methods have been presented in the theoretical solutions part: exhaustive search, tabu search and a new one, presented by the author. A program was created for comparison of these methods. In the third part of the thesis outcomes of the research are presented. Designed methods were tested and compared by their routes length, process time, computations duration and other parameters. Conclusions of the thesis and recommendations for implementation of analyzed procedures have been presented in the part of conclusions. Literature in Lithuanian, English was used in preparing the thesis. There are 19 tables and 29 pictures in the thesis.
26
Liu, Jiamin. "Novel approaches to container loading : from heuristics to hybrid tabu search." Thesis, University of Bedfordshire, 2008. http://hdl.handle.net/10547/295765.
Full textAbstract:
This work investigates new approaches to the container loading problem which address the issue of how to load three-dimensional, rectangular items (e.g. boxes) into the container in such a way that maximum utilisation is made of the container space. This problem occurs in several industry sectors where the loading approach places cargo effectively into aeroplanes, ships, trailers or trucks in order to save considerable cost. In carrying out this work, the investigation starts by developing a new heuristic approach to the two-dimensional bin packing problem, which has lower complexity than container loading in the aspects of constraints and geometry. A novel approach, including the heuristic strategies and handling method for remaining areas, is developed that can produce good results when testing with benchmark and real world data. Based on the research for two-dimensional bin packing, a novel heuristic approach is developed to deal with the container loading problem with some practical constraints. The heuristic approach to container loading also includes heuristic strategies and the handling of remaining spaces. The heuristic strategies construct effective loading arrangements where combinations of identical or different box types are loaded in blocks. The handling method for remaining spaces further improves the loading arrangements through the representation, partitioning and merging of remaining spaces. The heuristic approach obtains better volume utilisation and the highest stability compared with other published heuristic approaches. However, it does not achieve as high a volume utilisation as metaheuristic approaches, e.g. genetic algorithms and tabu search.To improve volume utilisation, a new hybrid heuristic approach to the container loading problem is further developed based on the tabu search technique which covers the encoding, evaluation criterion and configuration of neighbourhood and candidate solutions. The heuristic strategies as well as the handling method for remaining spaces developed in the heuristic approach are used in this new hybrid tabu search approach. It is shown that the hybrid approach has better volume utilisation than the published approaches under the condition that all loaded boxes with one hundred per cent support from below. In addition, the experimental results show that both the heuristic and hybrid tabu search approaches can also be applied to the multiple container loading problem.
27
Lin, Juei Yang, and 林睿暘. "Enhanced Parallel Tabu Search." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/34616811717440382778.
Full textAbstract:
碩士國立清華大學
工業工程與工程管理學系
89
Tabu search is a widely used heuristic search method. One of the main components of tabu search is tabu list, which makes several latest moves forbidden in order to escape from a small loop. The algorithm starts from an initial solution, and moves the current solution to the best neighborhood which is not forbidden. These iterations will be repeated until the terminating condition is reached. There are two main drawbacks in the traditional tabu search. First, tabu search only provides an approximate solution. There is no way to know the quality of the obtained solutions. Second, although tabu list helps the search avoiding a small cycling problem, it cannot prevent a previously searched area to be searched again or forming a large cycle. The computation efficiency of a tabu search can be improved by implementing a parallel tabu search, which uses multiple processors to search in parallel. In the study, we propose an enhanced parallel tabu search, which attempts to compute more efficiently and conquer the two drawbacks mentioned above. The ratio of finding the old local optimum solutions may suggest the confidence level of the best solution we find at the end of search. Also, the historical memory of local optimum solutions helps us to avoid searching old areas again. To validate the efficiency of the new approach, we will use a series of number sequencing problems. In addition, we apply statistical method to test the suggested relationship between the ratio of old local optimum and the confidence level of the obtained solution. The result of experiments shows that it takes less time for the enhanced parallel tabu search to find global optimum solutions than conventional one. The ratio of finding the old local optimums does not precisely estimates the confidence level of the best solution. However, our results show that the probability of finding the global optimal solutions should be larger than the computed ratio. 1.1研究背景 1 1.2研究動機 1 1.3研究架構 3 第2章 文獻回顧 4 2.1塔布搜尋法 4 2.2平行塔布搜尋法 9 2.3塔布搜尋效率的改善方法 11 第3章 方法構建 13 3.1改進之平行塔布搜尋法 13 3.1.1子空間的定義 13 3.1.2隨機起始解 14 3.1.3長期記憶結構 15 3.1.4落入涵蓋區域的比率 16 3.2改進之平行處理演算法 19 3.3改進之平行塔布搜尋法的優點 23 第4章 實驗設計與分析 24 4.1問題描述 24 4.1.1多個處理器的模擬方法 24 4.1.2數字排序問題 25 4.2 求解數字排序問題的改進之平行塔布搜尋法的設定 26 4.3 離開舊區域最佳解後脫離方向的比較 27 4.4涵蓋比率的實驗設計 29 4.4.1落入涵蓋區域的比率的實驗 29 4.4.2驗證子空間是否為均勻的分佈 32 4.5比較搜尋速度的實驗結果與分析 35 第5章 結論與未來展望 38 參考文獻 39
28
Guo, Jiawei. "Tabu search heuristics for hypercube embedding." Thesis, 1992. http://spectrum.library.concordia.ca/4381/1/MM73691.pdf.
Full text
29
Lai, Yu-Hsin, and 賴侑新. "Tabu Search Method for Flexible Job." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/69677365782555015794.
Full textAbstract:
碩士國立清華大學
工業工程與工程管理學系
91
Nowicki and Smutnicki【1996】reported an improved tabu search method called fast tabu search algorithm to solve job shop scheduling problem. When the definition of move is that x and y are successive operations on certain machine, and x and y are on a critical path, the move is to swap x and y. The fast tabu search algorithm can reduce the neighborhood size. Therefore, the fast tabu search algorithm can obtain a good solution of job shop problem in a shorter time. The difference between flexible job shop problem and job shop problem is that, in flexible job shop problem, a machine type may consist of identical parallel machines. Because of this characteristic, the algorithm for job shop problem is not suitable for solving flexible job shop problem. This study combines tabu search, fast tabu search algorithm, and the proposed superior critical path algorithm to solve flexible job shop problem. This study hopes to develop an algorithm that can find a good solution in a short time. Computational experiments show that the algorithm can solve large size flexible job shop problem and find a good solution in a short time. Keywords: job shop problem, flexible job shop problem, tabu search, fast tabu search algorithm, superior critical path algorithm.
30
Santos, Nicolau Filipe Barbosa Veludo dos. "Tabu search for minimizing total tardiness." Master's thesis, 2012. https://repositorio-aberto.up.pt/handle/10216/65405.
Full text
31
Santos, Nicolau Filipe Barbosa Veludo dos. "Tabu search for minimizing total tardiness." Dissertação, 2012. https://repositorio-aberto.up.pt/handle/10216/65405.
Full text
32
Lai, Jian-Min, and 賴建銘. "Tabu Search for Finding Optimal Evolutionary Trees." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/vhhah2.
Full textAbstract:
碩士銘傳大學
資訊管理學系碩士班
92
This paper presents a tabu search algorithm for constructing evolutionary trees based on maximum likelihood and parsimony criterion. Since the problem of finding the optimum maximum likelihood and parsimony evolutionary tree has been found to be NP-hard, most existing methods seek for near optimal solution using heuristics. It is well known that the solutions obtained using meta-heuristics usually significantly outperform those obtained using heuristic methods; we therefore apply the tabu search, which is one of the instances of meta-heuristics, to approach the maximum likelihood and parsimony evolutionary tree. The experimental results manifest that the likelihood value of the evolutionary tree derived from the tabu search is higher than that of the tree yielded by default Phylip, which is the most popular freeware to compute evolutionary trees, and is also comparable to that of the tree yielded by Phylip using optimal parameter setting, showing that the proposed method is feasible.
33
Lin, Chun-Hao, and 林俊豪. "Tabu Search for Discrete Simulation Optimization Problems." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/yw7j89.
Full textAbstract:
碩士中原大學
工業工程研究所
93
The optimization problems can be categorized into two types: continuous and discrete, base on the decision variables. We also discuss the simulation and numerical analysis. Now we consider mainly discrete simulation optimization problems. The simulation optimization problems, finding the optimal point using only estimates of the function values. Such problems occur in system design with simulation applications. The decision variables are controllable system parameters and objective function is the associate system cost to be minimized. Due to the complexity in the simulation system, the objective function values can not be computed numerically but can be estimated through simulation experiments. We propose the TSDRA algorithm for solving discrete simulation optimization problems. This algorithm combines the Dependent Retrospective Approximation (DRA) procedure and Tabu Search (TS). The main idea of DRA algorithm is to iteratively solve a sequence of sample-path problems with increasing sample size. Each sample-path problem is then solved by the heuristic tabu search (TS). We consider two performance indexes in this research: first is sensitivity analysis of the algorithm parameters, second is comparison of TSDRA to six existing algorithms --- MSSA, SRS, MSSR, MSSC, GADRA and SADRA---. Both studies use MSEf and CP as algorithm performance measures, where MSEf is the mean square error in the function value and CP is the number of convergent paths out of replications (a convergent path is one that terminates with the true optimal point). Algorithms with small MSEf and big CP are preferred. The simulation results also show that M/M/1 system is one dimension. In tabu search, long as search it from the large iterations, can reach best solution. Uni-model system is two dimensions, so that it will produce the cycle. TSDRA will get small MSEf than SADRA and GADRA, But SADRA ( ) get a good CP value.
34
Lai, Ya-Chao, and 賴雅昭. "Automaic Playlist Generation by Applying Tabu Search." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/54423813152069105266.
Full textAbstract:
碩士輔仁大學
資訊工程學系
97
In this thesis, we discuss the problem of playlist generation. To capture a user’s listening preference and recommend a meaningful playlist, we apply the sequential pattern mining with multiple minimum supports algorithm (MMS-PS) to generate constraints. Given a set of generated constraints, we apply Tabu Search to generate playlists which match constraints as much as possible. Finally, we implement our prototype and carry out experiments.
35
劉玉山. "Using Tabu Search for Finding Consensus Sequence." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/07094808649625506348.
Full textAbstract:
碩士樹德科技大學
資訊管理研究所
92
A consensus sequence captures the common features of a set of sequences. Consensus sequences are important in various DNA sequencing applications and are a convenient way to characterize a family of molecules. The search of such a sequence is an NP-Complete problem and, therefore, no efficient algorithms to search the sequence can be designed. Tabu Search has been used in a wide variety of applications to find solutions for NP-Complete problems. In this paper, we use a variant of Tabu search to find a consensus sequence. The method may be viewed as consisting of two alternating phases, an Improving Phase and a Mixed Phase. And the resulting consensus sequences can be used to induce a multiple sequence alignment. The proposed approach has been experimented on real sequences and simulated sequences. The experimental results are compared with ClustalW to illustrate the effectiveness of the proposed approach.
36
Juo, Huei-Lung, and 卓輝龍. "Automated Program Flaw Finding Using Tabu Search." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/80858272955124046704.
Full textAbstract:
碩士銘傳大學
資訊管理研究所
90
Software testing is an expensive process, typically consuming at least 50 percent of the total costs involved in developing software, while adding nothing to the functionality of the product. One of the major costs in a software project is the construction of test-data. If test-data can effectively construction, it can reduce the software development cost. Many techniques for automated test data construction have been developed. Their main idea is transforming the software testing problem into a test data searching problem, and then employing meta-heuristic algorithms to find out target test data effectively. As the complexity and variety of software, the new search problem is more complex and harder than other searching problems employing meta-heuristic algorithms. Most current methods propose only a basic structure for automatic software testing, they does not discuss how to making use of special properties of software to effectively guiding the searching process. The thesis develops a method that extends currently proposed automatic software testing methods. The method employs Tabu search as basis and proposes some strategies based on software properties to improve the effectiveness of automatic test data generation. The strategies proposed include: calculating next move using current cost, calculating next move using distance effectiveness, a strategy for solving cost plateau, and input variable selection. Many combinations of these strategies are also experimented to improve flaw-finding efficiency.
37
Liao, Li-Man, and 廖麗滿. "Tabu search methods for the scheduling problem." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/93209179030069227130.
Full textAbstract:
博士國立臺灣科技大學
工業管理系
89
Three prominent techniques, genetic algorithm (GA), simulated annealing (SA) and tabu search (TS), for finding near optimal solutions to combinatorial optimization problems have been used widely. These techniques are called meta-heuristics or general heuristics. In this research, we first introduce a basic version of each method, give indications about tuning parameters, and compare them. Then we select one of the three methods, tabu search, to solve two scheduling problems. The first problem is a single-machine scheduling problem with major and minor setups; the second problem is a permutation flow-shop scheduling problem with multiple objectives. We propose heuristics based on TS to compare with the existing heuristics. For the first problem, we apply dynamic programming (DP) and TS to develop two heuristics, respectively. The performances of both heuristics dealing with small- or medium-sized problems are well. But for large-sized problems, the heuristic based on DP often traps in local optimum. Therefore, we try to deploy TS technique to overcome the problem. The TS based heuristic uses block neighborhoods and diversification. According to computational results, the performance of TS based heuristic is superior to the DP based heuristic. The second problem, flow shop scheduling with multiple objectives, is frequently encountered in practice. We also develop a TS based heuristic to solve the problem. In particular, two problems with triple-criteria are under consideration, i.e., the minimization of makespan, total flow time, and total idle time, and the minimization of makespan, total flow time, and total tardiness. A heuristic based on TS technique is developed for the problems. The heuristic suggests a simple technique for generating neighborhoods of a given sequence and adopts a combined scheme for intensification and diversification, using frequency-based memory to search a new region. Computational results show that the heuristic is better than two existing genetic algorithm based heuristics.
38
PING, YEH HSIN, and 葉心蘋. "Applying Tabu Search on the Sequential Ordering Problem." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/68982205019882232694.
Full textAbstract:
碩士元智大學
工業工程研究所
87
The purpose of this research is to develop a Tabu Search heuristic algorithm for the Sequential Ordering Problem (SOP), which sometimes is referred to as the Traveling Salesman Problem with Precedence Constraints. Two tour construction heuristics, namely, nearest neighborhood and random selection, are used to find an initial feasible tour of the problem, and two tour improvement procedures, namely, two-swap and one-point move, are used to improve the initial tour. In our research, the Taguch''s method is used to find the most suitable values of the parameters in the proposed Tabu heuristic. The parameters include the tour construction methods, tour improvement procedures, maximum number of iterations, maximum number of continual failures, and the length of the Tabu list. Our experimental result shows that nearest neighborhood plus one-point move will deliver a better result. Our Tabu heuristic has an average error of 9.53% as compared to the best solution values in the SOP test problems of the TSPLIB.
39
"An improved tabu search for airport gate assignment." 2009. http://library.cuhk.edu.hk/record=b5896584.
Full textAbstract:
Kwan, Cheuk Lam.Thesis (M.Phil.)--Chinese University of Hong Kong, 2009.
Includes bibliographical references (p. 115-118).
Abstract also in Chinese.
Chapter 1 --- Introduction --- p.9
Chapter 1.1 --- The Gate Assignment Problem --- p.9
Chapter 1.2 --- Contributions --- p.10
Chapter 1.3 --- Formulation of Gate Assignment Problem --- p.11
Chapter 1.4 --- Organization of Thesis --- p.13
Chapter 2 --- Literature Review --- p.15
Chapter 2.1 --- Introduction --- p.15
Chapter 2.2 --- Formulations of Gate Assignment Problems --- p.15
Chapter 2.2.1 --- Static Gate Assignment Model --- p.16
Chapter 2.2.1.1 --- Total Passenger Walking Distance --- p.17
Chapter 2.2.1.2 --- Waiting Time --- p.20
Chapter 2.2.1.3 --- Unassigned Flights --- p.21
Chapter 2.2.2 --- Stochastic and Robust Gate Assignment Model --- p.22
Chapter 2.2.2.1 --- Idle Time --- p.22
Chapter 2.2.2.2 --- Buffer Time --- p.23
Chapter 2.2.2.3 --- Flight Delays --- p.23
Chapter 2.2.2.4 --- Gate Conflicts --- p.24
Chapter 2.3 --- Solution Methodologies --- p.25
Chapter 2.3.1 --- Expert System Approaches --- p.25
Chapter 2.3.2 --- Optimization --- p.27
Chapter 2.3.2.1 --- Exact Methods --- p.27
Chapter 2.3.2.2 --- Heuristic Approaches --- p.28
Chapter 2.3.2.3 --- Meta-Heuristics Approaches --- p.29
Chapter 2.3.2.4 --- Tabu Search and Path Relinking --- p.31
Chapter 2.4 --- Current Practice of Gate Assignment Problems --- p.32
Chapter 2.5 --- Summary --- p.32
Chapter 3 --- Tabu Search --- p.34
Chapter 3.1 --- Introduction --- p.34
Chapter 3.2 --- Mathematical Model --- p.34
Chapter 3.3 --- Principles of Tabu Search --- p.36
Chapter 3.4 --- Neighborhood Structures --- p.38
Chapter 3.4.1 --- Insert Move --- p.38
Chapter 3.4.2 --- Exchange Move --- p.39
Chapter 3.5 --- Short Term Memory Structure --- p.41
Chapter 3.6 --- Aspiration Criterion --- p.42
Chapter 3.7 --- Intensification and Diversification Strategies --- p.43
Chapter 3.8 --- Tabu Search Framework --- p.45
Chapter 3.8.1 --- Initial Solution --- p.45
Chapter 3.8.2 --- Tabu Search Algorithm --- p.46
Chapter 3.9 --- Computational Studies --- p.52
Chapter 3.9.1 --- Parameters Tuning --- p.52
Chapter 3.9.1.1 --- Fine-tuning a Tabu Search Algorithm with Statistical Tests --- p.53
Chapter 3.9.1.2 --- Tabu Tenure --- p.54
Chapter 3.9.1.3 --- Move Selection Strategies --- p.56
Chapter 3.9.1.4 --- Frequency of Exchange Moves --- p.59
Chapter 3.9.2 --- Comparison the Fine-tuned TS with original TS --- p.62
Chapter 3.10 --- Conclusions --- p.63
Chapter 4 --- Path Relinking --- p.65
Chapter 4.1 --- Introduction --- p.65
Chapter 4.2 --- Principles of Path Relinking --- p.65
Chapter 4.2.1 --- Example of Path Relinking --- p.66
Chapter 4.3 --- Reference Set --- p.68
Chapter 4.3.1 --- Two-Reference-Set Implementation --- p.71
Chapter 4.3.1.1 --- Random Exchange Gate Move --- p.72
Chapter 4.4 --- Initial and Guiding Solution --- p.73
Chapter 4.5 --- Path-Building Process --- p.74
Chapter 4.6 --- Tabu Search Framework with Path Relinking --- p.78
Chapter 4.6.1 --- Computational Complexities --- p.82
Chapter 4.7 --- Computational Studies --- p.82
Chapter 4.7.1 --- Best Configuration for Path Relinking --- p.83
Chapter 4.7.1.1 --- Reference Set Strategies and Initial and Guiding Criteria --- p.83
Chapter 4.7.1.2 --- Frequency of Path Relinking --- p.86
Chapter 4.7.1.3 --- Size of Volatile Reference Set --- p.87
Chapter 4.7.1.4 --- Size of Non-volatile Reference Set --- p.89
Chapter 4.7.2 --- Comparisons with Other Algorithms --- p.94
Chapter 5 --- Case Study --- p.98
Chapter 5.1 --- Introduction --- p.98
Chapter 5.2 --- Airport Background --- p.98
Chapter 5.2.1 --- Layout of ICN --- p.98
Chapter 5.3 --- Data Preparation --- p.99
Chapter 5.3.1 --- Passenger Data --- p.103
Chapter 5.4 --- Computational Studies --- p.104
Chapter 5.4.1 --- Experiments without Airline Preference --- p.104
Chapter 5.4.2 --- Experiments with Airline Preference --- p.106
Chapter 5.4.2.1 --- Formulation --- p.106
Chapter 5.4.2.2 --- Results --- p.108
Chapter 5.5 --- Conclusion --- p.111
Chapter 6 --- Conclusion --- p.112
Chapter 6.1 --- Summary of Achievement --- p.112
Chapter 6.2 --- Future Developments --- p.113
Bibliography --- p.115
Appendix --- p.119
Chapter 1. --- Friedman´ةs Test --- p.119
Chapter 2. --- Wilcoxon's Signed Rank Test for Paired Observation --- p.120
Chapter 3. --- Hybrid Simulated Annealing with Tabu Search Approach --- p.121
Chapter 4. --- Arrival Flight Data of Incheon International Airport --- p.122
Chapter 5. --- Departure Flight Data of Incheon International Airport --- p.139
40
Lee, Jun-ying, and 李俊穎. "Tabu Search Heuristic for Period Vehicle Routing Problem." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/fzvwh3.
Full textAbstract:
碩士大同大學
資訊經營學系(所)
93
The Vehicle Routing Problem (VRP) under capacity and distance restrictions involves the design of minimum cost delivery routes for a fleet of vehicles, originating and terminating at a central depot, which serves a set of customers. This thesis present Tabu search algorithm for the Period Vehicle Routing Problem, the problem not only designs vehicle routes to meet required service levels for customers but also minimize distribution costs over a given several day period of time . The VRP belongs to the class of NP-hard problems, and polynomial time algorithms for finding optimal solutions are unlikely to exist. Hence, there have been few attempts to solve it optimally among an exact algorithm based on branch and bound procedures. The branch and bound approach address small VRP adequately up to 50 customers with 8 vehicles, the approach to solve big VRP must spend the maximum of greatest time and cost. Due to limited success of exact methods, considerable attention and research effort have been devoted to the development of efficient heuristics algorithm which can provide near optimal solutions for large-sized problems in limited time. But heuristic algorithm yielding solutions whose quality often not good enough. In this thesis, applied linear programming and Savings procedure to find an initial feasible solution of PVRP, then use Tabu search to improve the One-point movement algorithm, finding improved solutions whose quality significantly surpasses that obtained by traditional heuristics.
41
Chang, Wu Chia, and 吳佳璋. "The Application of Tabu Search in FMS Scheduling." Thesis, 1998. http://ndltd.ncl.edu.tw/handle/23977767549291429454.
Full textAbstract:
碩士大葉大學
工業工程研究所
86
In this research, Tabu Search heuristic algorithm is presented to deal with the Flexible Manufacturing System (FMS) sceduling problems with the due date constraints in anticipation to minimum the mean tardiness of thesystem. The approach is studied in three phases. First, for the mean tardinesscriterion, a job-oriented heuristic (JOH) is constructed to solve the addressed FMS scheduling problem. Then an experiment is designed to checkthe best combination of tabu list size and ending iteration number. Finally,the Tabu Search with long-term memory construction is developed to improvethe performance quality. The performance of the designed algorithm willcompared with the Tabu Search heuristic using short-term memory construction. Through the statistical analysis to show the superior of the constructedheuristic.
42
Huang, An Der, and 黃安德. "Tabu Search Heuristics for Linear Bilevel Programming Problem." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/59910435378572610076.
Full text
43
Ciarleglio, Michael Ian 1979. "Modular Abstract Self-learning Tabu Search (MASTS) : metaheuristic search theory and practice." 2008. http://hdl.handle.net/2152/18086.
Full textAbstract:
MASTS is an extensible, feature rich, software architecture based on tabu search (TS), a metaheuristic that relies on memory structures to intelligently organize and navigate the search space. MASTS introduces a new methodology of rule based objectives (RBOs), in which the search objective is replaced with a binary comparison operator more capable of expressing a variety of preferences. In addition, MASTS supports a new metastrategy, dynamic neighborhood selection (DNS), which “learns” about the search landscape to implement an adaptive intensification-diversification strategy. DNS can improve search performance by directing the search to promising regions and reducing the number of required evaluations. To demonstrate the flexibility and range of capabilities, MASTS is applied to two complex decision problems in conservation planning and groundwater management. As an extension of MASTS, ConsNet addresses the spatial conservation area network design problem (SCANP) in conservation biology. Given a set of possible geographic reserve sites, the goal is to select which sites to place under conservation to preserve unique elements of biodiversity. Structurally, this problem resembles the NP-hard set cover problem, but also considers additional spatial criteria including compactness, connectivity, and replication. Modeling the conservation network as a graph, ConsNet uses novel techniques to quickly compute these spatial criteria, exceeding the capabilities of classical optimization methods and prior planning software. In the arena of groundwater planning, MASTS demonstrates extraordinary flexibility as both an advanced search engine and a decision aid. In House Bill 1763, the Texas state legislature mandates that individual Groundwater Conservation Districts (GCDs) must work together to set specific management goals for the future condition of regional groundwater resources. This complex multi-agent multi-criteria decision problem involves finding the best way to meet these goals considering a host of decision variables such as pumping locations, groundwater extraction rates, and drought management policies. In two separate projects, MASTS has shaped planning decisions in the Barton Springs/Edwards Aquifer Conservation District and Groundwater Management Area 9 (GMA9). The software has been an invaluable decision support tool for planners, stakeholders, and scientists alike, allowing users to explore the problem from a multicriteria perspective.text
44
Johnson, Gregory Phillip. "A tabu search methodology for spacecraft tour trajectory optimization." Thesis, 2014. http://hdl.handle.net/2152/28315.
Full textAbstract:
A spacecraft tour trajectory is a trajectory in which a spacecraft visits a number of objects in sequence. The target objects may consist of satellites, moons, planets or any other body in orbit, and the spacecraft may visit these in a variety of ways, for example flying by or rendezvousing with them. The key characteristic is the target object sequence which can be represented as a discrete set of decisions that must be made along the trajectory. When this sequence is free to be chosen, the result is a hybrid discrete-continuous optimization problem that combines the challenges of discrete and combinatorial optimization with continuous optimization. The problem can be viewed as a generalization of the traveling salesman problem; such problems are NP-hard and their computational complexity grows exponentially with the problem size. The focus of this dissertation is the development of a novel methodology for the solution of spacecraft tour trajectory optimization problems. A general model for spacecraft tour trajectories is first developed which defines the parameterization and decision variables for use in the rest of the work. A global search methodology based on the tabu search metaheuristic is then developed. The tabu search approach is extended to operate on a tree-based solution representation and neighborhood structure, which is shown to be especially efficient for problems with expensive solution evaluations. Concepts of tabu search including recency-based tabu memory and strategic intensification and diversification are then applied to ensure a diverse exploration of the search space. The result is an automated, adaptive and efficient search algorithm for spacecraft tour trajectory optimization problems. The algorithm is deterministic, and results in a diverse population of feasible solutions upon termination. A novel numerical search space pruning approach is then developed, based on computing upper bounds to the reachable domain of the spacecraft, to accelerate the search. Finally, the overall methodology is applied to the fourth annual Global Trajectory Optimization Competition (GTOC4), resulting in previously unknown solutions to the problem, including one exceeding the best known in the literature.text
45
McKinzie, Kaye Barnes J. Wesley. "A tabu search approach to strategic mobility mode selection." 2005. http://repositories.lib.utexas.edu/bitstream/handle/2152/2033/mckinziek71844.pdf.
Full text
46
Lambert, Garrett Randall. "A tabu search approach to the strategic airlift problem." Thesis, 2004. http://hdl.handle.net/2152/1349.
Full text
47
McKinzie, Kaye. "A tabu search approach to strategic mobility mode selection." Thesis, 2005. http://hdl.handle.net/2152/2033.
Full text
48
Hsia, Wan-Chun, and 夏萬春. "The study of vehicle scheduling by tabu search algorithm." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/35075307760370223076.
Full textAbstract:
碩士國立高雄第一科技大學
機械與自動化工程系
89
Bus is one of the major vehicles for domestic public transportation. Its operation affects not only people’s daily life but also the profit of the operator. To improve the operation efficiency it needs to work on the hardware facilities as well as the vehicle scheduling. The vehicle scheduling means the operator manages the vehicles in accordance with the operation timetable and the capacity of depots. The vehicle scheduling determines the efficiency of facilities usage, timetable drafting, and staff assigned, as well as affects the cost, services and competitiveness of the operator. This study designs a mathematical model by communicating with the operators and considering the capacity and needs of vehicles to design the schedule for each driver so as to rationalize the workload of drivers and slack time of vehicles. This study then uses the tabu search which characterize its search and memory ability to develop the heuristic algorithm for vehicle scheduling in terms of schedule transfer and exchange. This study then applies this method to the schedules of the Kinmen Bus Administration and shows all timetables can fit the expectation.
49
Lee, Hrong-Ru, and 李宏儒. "A study on tabu search for the clustering problem." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/82375685574808529624.
Full textAbstract:
碩士輔仁大學
數學系研究所
87
The clustering analysis is the most typical one of the combinatorial optimization problems. Since traditional mathematical programming could not be applied easily to obtain optimized solution within a reasonable time frame, Heuristics method becomes a general and fast approach to this problem. Tabu search, a high-level meta-heuristic, is particularly used in solving the combinatorial optimization problem. The clustering operation classifies n objects into m groups whose members are similar in the interesting features. The features of an object are represented as a point within a q-dimensional Euclidean space. The distance between a point and the center of its group indicates fitness of the object within the group. The objective divides these objects into groups such that total sum of these distances is minimized. There are many local minimums in the problem. In this thesis, four trial solution approaches, Pdacay, Mpdecay, DP and MDP, will be proposed to escape from the trap of local minima and improve the effectiveness of the Tabu search.
50
Chao, Wen-Chi, and 趙文琦. "Using improved tabu search for the facility layout problem." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/28063114304467808216.
Full textAbstract:
碩士立德管理學院
應用資訊研究所
95
The facility layout problem is a part of the application in the artificial intelligence. It is belong to the combinatorial optimization and quadratic assignment problem. For many artificial intelligence tools, the tabu search algorithm is widely applied to a lot of combinatorial optimization problems. In this research, an improved tabu search algorithm is developed to solve a NP-complete problem in the facility layout problem. The approach on the two facilities layout problems is examined. The first one is a construction site layout problem, and the second one is a hospital facility layout problem. In order to get better layout result, this research has tried the different setting in this algorithm by altering the values of parameters. This research can provide a good algorithm to solve the quadratic assignment problem in facility layout arrangement.