Search Results (1 - 8 of 8 Results)

Sort By  
Sort Dir
 
Results per page  

Liu, YatingMotif Selection via a Tabu Search Solution to the Set Cover Problem
Master of Science (MS), Ohio University, 2017, Computer Science (Engineering and Technology)
Transcription factors (TFs) regulate gene expression through interaction with specific DNA regions, called transcription factor binding sites (TFBSs). Identifying TFBSs can help in understanding the mechanisms of gene regulation and the biology of human diseases. Motif discovery is the traditional method for discovering TFBSs. However, current motif discovery tools tend to generate a number of motifs that is too large to permit a biological validation. To address this problem, the motif selection problem is introduced. The aim of the motif selection problem is to select a small set of motifs from the discovered motifs, which cover a high percentage of genomic input sequences. Tabu search, a metaheuristic search method based on local search, is introduced to solve the motif selection problem. The performance of the proposed three motif selection methods, tabu-SCP, tabu-PSC and tabu-PNPSC, were evaluated by applying them to ChIP-seq data from the ENCyclopedia of DNA Elements (ENCODE) project. Motif selection was performed on 46 factor groups which include 158 human ChIP-seq data sets. The results of the three motif selection methods were compared with Greedy, enrichment method and relax integer liner programming (RILP). Tabu-PNPSC selected the smallest set of motifs with the highest overall accuracy. The average number of selected motifs was 1.37 and the average accuracy was 72.47%. Tabu-PNPSC was used to identify putative regulatory element binding sites that are in response to the overproduction of small RNAs RyfA1 in the bacteria Shigella dysenteriae. Six motifs were selected by tabu-PNPSC and the overall accuracy was 75.5%.

Committee:

Lonnie Welch (Advisor)

Subjects:

Bioinformatics; Computer Science

Keywords:

motif selection; tabu search; set cover problem

Ganapathy, SubhashiniHUMAN-CENTERED TIME-PRESSURED DECISION MAKING IN DYNAMIC COMPLEX SYSTEMS
Doctor of Philosophy (PhD), Wright State University, 2006, Human Factors Engineering
Many real-world applications are complex, dynamic, and uncertain. Human operators play an important role in ensuring the safety and in achieving operational effectiveness in such systems. During task performance, both humans and computerized processes bring in varying strengths and limitations. Research on human-centered automation in aviation, satellite ground control, and nuclear power plant control has resulted in broad guidelines on system design involving human and computerized processes in supervisory control. However, problems such as increased human error, lack of situational awareness, and opacity from poorly automated systems remain, particularly in scenarios where human operators must make decisions in time-pressured planning. While anecdotal evidence does exist that interactive systems are better than completely manual or completely automated systems, there is a lack of systematic studies of human-centered modeling in joint cognitive systems. This research addresses the issue of joint cognitive problem solving for a class of problems related to supervisory control of vehicle routing. The key research question addressed by this study is whether a human integrated approach helps in better generation of alternatives and better evaluation of alternatives that would potentially lead to better solutions to problems. Empirical results from a simulated military mission indicate that the human integrated approach resulted in better overall performance when compared to purely automated solutions for vehicle routing problems considered in this research study. Specifically, significantly more high priority targets were covered in the human integrated approach compared to the automated solution without any significant degradation with respect to all the other dependent measures including percentage of total targets covered, low priority targets covered, total targets covered in threat zone, high priority targets covered in threat zone, and low priority targets covered in threat zone. Results also indicated that that the graphical representation of the alternatives leads to quicker evaluation time than tabular representation. One of the primary contributions of this research is a framework to demonstrate the rationale of using joint cognitive systems in time-pressured decision making. Some of the other contributions include a methodology for the evaluation of alternatives in a cognitively effective manner, and a baseline to compare results of future studies in interactive modeling.

Committee:

S Narayanan (Advisor)

Keywords:

Interactive Modeling; Generation of Alternatives; Tabu Search; Human Computer Interaction; Vehicle Routing; Generation of Alternatives; Automation Issues

SHARMA, VIKASQUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION
MS, University of Cincinnati, 2001, Engineering : Computer Engineering
The abundance of difficult combinatorial optimization problems in practical settings such as telecommunications, financial planning and VLSI design automation has motivated the development of powerful optimization techniques. Simulated Annealing, Genetic algorithms, Network Flow and other heuristics have long been explored for solvingthese problems. During the recent years, miniaturization of the chip sizes and increasing densities of logic have posed a continuous design-related challenge to the VLSI design automation community. Promising results have been reported from the application of Tabu Search algorithm to VLSI circuit partitioning, floorplanning, placement and routing. Tabu Search leverages the ability to store solutions already visited and to make strategic solutions on the basis of the stored information for achieving optimal solutions. This thesis presents a quantitative analysis of the various parameters of Tabu Search. In particular, we look at the techniques of moving out of the current search space called diversification methodologies and strategies for determining the best solution in the current search space called intensification methodologies. This is achieved by applying a tabu tenure on the moves, thus forbidding execution of certain moves for some iterations. In addition, we generate a candidate list of moves for selecting moves for future executions. Our approach makes use of a Tabu Search-based Force Directed placement technique. We perform physical placements of VLSI circuits on a two-dimensional array. In the first step, the circuit cells are placed randomly and their respective tendencies to move in all the four directions are computed. This is followed by selection of the moves for swap on the basis of candidate list implementations. Intensification and diversification phases are repeated alternately. An optimized ratio of the number of iterations of intensification and diversification phases ensures good quality solutions with low processing time. We have demonstrated that our Tabu Search-based placement approach achieves a speed up ranging from 5 to 17 times over a similarly implemented Simulated Annealing-based placement algorithm, depending on the circuit size.

Committee:

Dr. Karen C. Davis (Advisor)

Keywords:

Tabu; tabu tenure; tenure; candidate list; Tabu Search; Wirelength; Algorithm

Iyer, Krishnakumar RTabu search algorithm for a thermal aware VLSI floorplanning application
MS, University of Cincinnati, 2013, Engineering and Applied Science: Electrical Engineering
Every new process technology results in an increase in power density on chips. The cost of keeping the temperature of the chip low enough to sustain a high reliability increases consequently. Apart from the power and thermal effects associated with each functional block, the placement of the blocks affects the creation of thermal hotspots and reduces the reliability of the chip. Apart from the area and wire length based quality evaluation of a good floorplan, thermal penalties need to be taken into account. This thesis implements the tabu search algorithm for a thermal aware version of the VLSI floorplanning problem by employing diversification techniques to achieve global optima and strategies called intensification technique to determine the best solutions at a local level. We use these techniques and leverage the memory enabled tabu search to reduce the search space not only for placement of the blocks but also evaluation of the shapes and aspect ratios and thermal effects of the blocks in the floorplan. The additional constraint of geometry associated with the floorplanning problem, which differentiates it from the placement problem is represented using a B* tree data structure. Randomization for short and long term memory of the tabu lists and in the moves enables the algorithm to perform hill climbing and prevents it from being stuck at a local optimum and allows it to aspire to a global optimum. We use the MCNC benchmarks as the inputs to our experiment. The project requires a tool to evaluate the thermal effects of a floorplan. We use a tool called Hotspot, developed by the University of Virginia, to evaluate thermal costs. Hotspot is an accurate thermal modeling tool extensively used in architectural modeling. Its main benefit is its compatibility with power models often used in the computer architecture academic community.

Committee:

Carla Purdy, Ph.D. (Committee Chair); Raj Bhatnagar, Ph.D. (Committee Member); Wen Ben Jone, Ph.D. (Committee Member)

Subjects:

Electrical Engineering

Keywords:

Hotspot;Floorplanning;Thermal awareness;MCNC;Tabu search

Khambhampati, Surya SudhaA Tabu Search Heuristic for Multi-Period Clustering to Rationalize Delivery Operations
Master of Science in Engineering (MSEgr), Wright State University, 2008, Industrial and Human Factors Engineering
Delivery operations use centralized warehouses to serve geographically distributed customers. Resources (e.g. personnel, trucks, stock, and equipment) are scheduled from the warehouses to distributed locations with the aim of: (a) meeting customer demands and, (b) rationalizing delivery operation costs. My thesis investigates the problem of clustering customers based on their geographical vicinity and their multi-period demands, while optimally scheduling resources. The problem addresses with-and-without capacity constraints of vehicles at the warehouse. This problem is proven to be NP-Hard. Hence, solutions using state-of-the-art exact methods such as branch and bound are not pertinent due to the computation complexity involved. We develop a K-means clustering algorithm for the initial solution and a tabu search heuristic that combines three advanced neighborhood search algorithms: (i) shift move, (ii) shift move with supernodes, and (iii) ejection chain with supernodes, to accelerate convergence.

Committee:

Xinhui Zhang, PhD (Advisor); Raymond Hill, PhD (Committee Member); Frank Ciarallo, PhD (Committee Member)

Subjects:

Operations Research

Keywords:

Tabu Search; Clustering

Aleman, Rafael E.A Guided Neighborhood Search Applied to the Split Delivery Vehicle Routing Problem
Doctor of Philosophy (PhD), Wright State University, 2009, Engineering PhD

The classic vehicle routing problem considers the distribution of goods to geographically scattered customers from a central depot using a homogeneous fleet of vehicles with finite capacity. Each customer has a known demand and can be visited by exactly one vehicle. Each vehicle services the assigned customers in such a way that all customers are fully supplied and the total service does not exceed the vehicle capacity. In the split delivery vehicle routing problem, a customer can be visited by more than one vehicle, i.e., a customer demand can be split between various vehicles. Allowing split deliveries has been proven to potentially reduce the operational costs of the fleet.

This study efficiently solves the split delivery vehicle routing problem using three new approaches. In the first approach, the problem is solved in two stages. During the first stage, an initial solution is found by means of a greedy approach that can produce high quality solutions comparable to those obtained with existing sophisticated approaches. The greedy approach is based on a novel concept called the route angle control measure that helps to produce spatially thin routes and avoids crossing routes. In the second stage, this constructive approach is extended to an iterative approach using adaptive memory concepts, and then a variable neighborhood descent process is added to improve the solution obtained.

A new solution diversification scheme is presented in the second approach based on concentric rings centered at the depot that partitions the original problem. The resulting sub-problems are then solved using the greedy approach with route angle control measures. Different ring settings produce varied partitions and thus different solutions to the original problem are obtained and improved via a variable neighborhood descent.

The third approach is a learning procedure based on a set or population of solutions. Those solutions are used to find attractive attributes and construct new solutions within a tabu search framework. As the search progresses, the existing population evolves, better solutions are included in it whereas bad solutions are removed from it. The initial set is constructed using the greedy approach with the route angle control measure whereas new solutions are created using an adaptation of the well known savings algorithm of Clarke and Wright (1964) and improved by means of an enhanced version of the variable neighborhood descent process. The proposed approaches are tested on benchmark instances and results are compared with existing implementations.

Committee:

Raymond R. Hill, PhD (Advisor); Xinhui Zhang, PhD (Committee Member); James T. Moore, PhD (Committee Member); George G. Polak, PhD (Committee Member); Zhiqiang Wu, PhD (Committee Member)

Subjects:

Engineering; Industrial Engineering; Operations Research; Transportation

Keywords:

vehicle routing; split delivery; variable neighborhood descent; adaptive memory; greedy approach; diversification; tabu search

Hua, LiyanShortest Path - Capacitated Maximum Covering Problems
Doctor of Philosophy, The Ohio State University, 2010, Business Administration

I study the shortest path - capacitated maximum covering problem (SP-CMCLP). Current, ReVelle and Cohon (1985) first studied the un-capacitated version of this problem. The two objectives of the problem are the minimization of the path length from a predetermined starting node to a predetermined terminal node and the maximization of the total demand covered by the facilities located at the nodes in the path. They solved a special case in which a demand can be covered only if it is located on the path. I solve the general model. I also introduce facility capacity constraints, new algorithms and new demand coverage structures to this problem.

I decompose the problem into a k-shortest path problem (kSP) and a capacitated maximum covering problem (CMCLP). The k-shortest path problem is solved by a path deletion algorithm. The capacitated maximum covering problem is solved by various heuristics and meta-heuristics including lagrangian relaxation, two versions of Tabu search and a simulated annealing method.

To the knowledge of the author, the Tabu search and simulated annealing methods introduced are the first meta-heuristics developed for the capacitated maximum covering problem. In these meta-heuristics, I use four neighborhood structures. These are 1) one-interchange which exchanges an selected facility with an unselected facility, 2) client shift which shifts a satisfied demand from one selected facility to another selected facility, 3) demand swap (or demand reallocation) which swaps one (or more) assigned demand node (nodes) with one (or more) unassigned demand node (nodes) within the coverage distance of a selected facility site, 4) demand addition which adds one or more unassigned demand to a selected facility. I design an embedded meta-heuristic procedure which has inner loops of single neighborhoods and an outer loop of multiple alternate inner loops. I design a heuristic method and a penalty method for the demand allocation sub-problem in the embedded Tabu search. In the penalty method, I use surrogate relaxation and add a penalty term to the objective function for the violated capacity constraints. An embedded simulated annealing method with temperature vibration is also designed using heuristic demand allocation.

I solve a new version of the shortest path - capacitated maximum covering problem with tree coverage structure (SP-CMCLP-TREE). Demand is supplied by sub-paths on a minimum spanning tree constructed from an underlying network. A demand is counted as covered if the total arc length of a path from the demand to a facility site is within coverage distance and the demand can be satisfied only if all the intermediate demand nodes on the path are satisfied.

Computational results for networks selected from literature show the effectiveness of the heuristics. Tabu search performs the best in solution quality, while Lagrangian relaxation and simulated annealing generate solutions of satisfactory quality using less time. Different path-coverage structures are used based on the properties of the networks. Tree demand coverage structure works better than traditional coverage structure for large partial networks. The impact of different network parameters are also studied.

Committee:

John R. Current, PhD (Advisor); David A. Schilling, PhD (Committee Member); Keely L. Croxton, PhD (Committee Member)

Subjects:

Management; Operations Research

Keywords:

Shortest Path; Capacitated Maximum Covering Problem; Decomposition; Tabu Search; Simulated Annealing; Path Coverage Structure; Tree

Zhang, XuemeiSimulation-optimization in real-time decision making
Master of Science (MS), Ohio University, 1997, Industrial and Manufacturing Systems Engineering (Engineering)
Simulation-optimization in real-time decision making

Committee:

Thomas Lacksonen (Advisor)

Keywords:

Real-Time Simulation; Real-Time Decision Making; Tabu Search Short-Term Memory Component