Algorithmic Framework for Improving Heuristics in Stochastic, Stage-Wise Optimization Problems Jaein Choi 172 Pages Directed by Dr. Jay H. Lee and Dr. Matthew J. Realff The goal of this thesis is the development of a computationally tractable solution method for stochastic, stage-wise optimization problems. In order to achieve the goal, we have developed a novel algorithmic framework based on Dynamic Programming (DP) for improving heuristics. The propose method represents a systematic way to take a family of solutions and patch them together as an improved solution. However, patching is accomplished in state space, rather than in solution space. Since the proposed approach utilizes simulation with heuristics to circumvent the curse of dimensionality of the DP, it is named as Dynamic Programming in Heuristically Restricted State Space. The proposed algorithmic framework is applied to stochastic Resource Constrained Project Scheduling problems, a real-world optimization problem with a high dimensional state space and significant uncertainty equivalent to billions of scenarios. The real-time decision making policy obtained by the proposed approach outperforms the best heuristic applied in simulation stage to form the policy. The proposed approach is extended with the idea of Q-Learning technique, which enables us to build empirical state transition rules through simulation, for stochastic optimization problems with complicated state transition rules. Furthermore, the proposed framework is applied to a stochastic supply chain management problem, which has high dimensional action space as well as high dimensional state space, with a novel concept of implicit sub-action space that efficiently restricts action space for each state in the restricted state space. The resulting real-time policy responds to the time varying demand for products by stitching together decisions made by the heuristics and improves overall performance of the supply chain. The proposed approach can be applied to any problem formulated as a stochastic DP, provided that there are reasonable heuristics available for simulation.

The first part of this two-part thesis examines the reverse-flow operation of auto-thermal methane reforming in a microreactor. A theoretical study is undertaken to explain the physical origins of the experimentally observed improvements in the performance of the reverse-flow operation compared to the unidirectional operation. First, a scaling analysis is presented to understand the effect of various time scales existing within the microreactor, and to obtain guidelines for the optimal reverse-flow operation. Then, the effect of kinetic parameters, transport properties, reactor design and operating conditions on the reactor operation is parametrically studied through numerical simulations. The reverse-flow operation is shown to be more robust than the unidirectional operation with respect to both optimal operating conditions as well as variations in hydrogen throughput requirements. A rational scheme for improved catalyst placement in the microreactor, which exploits the spatial temperature profiles in the reactor, is also presented. Finally, a design modification of the microreactor called "opposed-flow" reactor, which retains the performance benefits of the reverse-flow operation without requiring the input / output port switching, is suggested. In the second part of this thesis, a novel simulation-based Approximate Dynamic Programming (ADP) framework is presented for optimal control of switching between multiple metabolic states in a microbial bioreactor. The cybernetic modeling framework is used to capture these cellular metabolic switches. Model Predictive Control, one of the most popular advanced control methods, is able to drive the reactor to the desired steady state. However, the nonlinearity and switching nature of the system cause computational and performance problems with MPC. The proposed ADP has an advantage over MPC, as the closed-loop optimal policy is computed offline in the form of so-called value or cost-to-go function. Through the use of an approximation of the value function, the infinite horizon problem is converted into an equivalent single-stage problem, which can be solved online. Various issues in implementation of ADP are also addressed.

This dissertation develops and evaluates a new adaptive traffic signal control system for arterials. This control system is based on reinforcement learning, which is an important research area in distributed artificial intelligence and has been extensively used in many applications including real-time control. In this dissertation, a systematic comparison between the reinforcement learning control methods and existing adaptive traffic control methods is first presented from the theoretical perspective. This comparison shows both the connections between them and the benefits of using reinforcement learning. A Neural-Fuzzy Actor-Critic Reinforcement Learning (NFACRL) method is then introduced for traffic signal control. NFACRL integrates fuzzy logic and neural networks into reinforcement learning and can better handle the curse of dimensionality and generalization problems associated with ordinary reinforcement learning methods. This NFACRL method is first applied to isolated intersection control. Two different implementation schemes are considered. The first scheme uses a fixed phase sequence and variable cycle length, while the second one optimizes phase sequence in real time and is not constrained to the concept of cycle. Both schemes are further extended for arterial control, with each intersection being controlled by one NFACRL controller. Different strategies used for coordinating reinforcement learning controllers are reviewed, and a simple but robust method is adopted for coordinating traffic signals along the arterial. The proposed NFACRL control system is tested at both isolated intersection and arterial levels based on VISSIM simulation. The testing is conducted under different traffic volume scenarios using real-world traffic data collected during morning, noon, and afternoon peak periods. The performance of the NFACRL control system is compared with that of the optimized pre-timed and actuated control. Testing results based on VISSIM simulation show that the proposed NFACRL control has very promising performance. It outperforms optimized pre-timed and actuated control in most cases for both isolated intersection and arterial control. At the end of this dissertation, issues on how to further improve the NFACRL method and implement it in real world are discussed.

Cells behave as complex systems with regulatory processes that make use of many elements such as switches based on thresholds, memory, feedback, error-checking, and other components commonly encountered in electrical engineering. It is therefore not surprising that these complex systems are amenable to study by engineering methods. A great deal of effort has been spent on observing how cells store, modify, and use information. Still, an understanding of how one uses this knowledge to exert control over cells within a living organism is unavailable. Our prime objective is "Personalized Cancer Therapy" which is based on characterizing the treatment for every individual cancer patient. Knowing how one can systematically alter the behavior of an abnormal cancerous cell will lead towards personalized cancer therapy. Towards this objective, it is required to construct a model for the regulation of the cell and utilize this model to devise effective treatment strategies. The proposed treatments will have to be validated experimentally, but selecting good treatment candidates is a monumental task by itself. It is also a process where an analytic approach to systems biology can provide significant breakthrough. In this dissertation, theoretical frameworks towards effective treatment strategies in the context of probabilistic Boolean networks, a class of gene regulatory networks, are addressed. These proposed analytical tools provide insight into the design of effective therapeutic interventions.

In power system reliability analysis, state space pruning has been investigated to improve the efficiency of the conventional Monte Carlo Simulation (MCS). New algorithms have been proposed to prune the state space so as to make the Monte Carlo Simulation sample a residual state space with a higher density of failure states. This thesis presents a modified Genetic Algorithm (GA) as the state space pruning tool, with higher efficiency and a controllable stopping criterion as well as better parameter selection. This method is tested using the IEEE Reliability Test System (RTS 79 and MRTS), and is compared with the original GA-MCS method. The modified GA shows better efficiency than the previous methods, and it is easier to have its parameters selected. This thesis also presents a Dynamic Programming (DP) algorithm as an alternative state space pruning tool. This method is also tested with the IEEE Reliability Test System and it shows much better efficiency than using Monte Carlo Simulation alone.

A subsequence is obtained by deleting zero or more symbols from a given sequence. For given two sequences, the longest common subsequence problem is to find a common subsequence whose length is the longest. The constrained longest common subsequence (CLCS) problem is to find a longest common subsequence that contains a specific subsequence. Note a CLCS may be shorter than an LCS. In this thesis, we propose a dynamic programming algorithm for solving the CLCS problem. The time complexity is O(pmn), where m and n are the lengths of the given sequences and p is the length of the constraint sequence. Our algorithm can also be applied to solve the constrained sequence alignment problem, which is a sequence alignment problem with the requirement that some specific symbols must be aligned together.

Pricing decision is the minority of all important decisions which can apparently influence a firm's profit-making within extremely short time. In an era of meagre profit, firms cannot stand any more injury caused of mistake at pricing. However, lots of managers still make pricing decision according to their experience or the action of other competitors without any mechanism of price-determining based on their firms' resource condition. The subject of this research is to probe the abiding price-reducing strategy for fashion appearing firms. Fashion apparel is a kind of commodities with seasonality and popularity, and is an example of all perishable goods. For all sorts of characteristic such as the need for long lead time before production, short time span for sale , and the low salvage value after season...etc., it makes firms reduce price to close out inventories by the end of seasons to evade value loss. When it comes to price-reducing, the fashion apparel is quite different from other commodities. It is a kind of commodity which has speciality of phased and monotonicity on price reduction. Therefore, it lacks two kinds of elasticity which are price-adjusting at any time and adjusting the price range at will. For the characteristic of close interdependence between product and time, and the normal demand on price-reducing, fashion apparel firms need some decision tools which are more fast, correct, and practical than any other ones. With two main parameters which are 'the levels of unsold inventory' and ' the length of season remaining ' along with two parameters which are 'discount factor' and ' the salvage value after season ', this research constructs out an stochastic dynamic programming model to maximize the expect profit and offer an program for calculating the optimal price-reduced range and time. After the analysis of generality and sensitivity with this model, it is found that the characteristics of this model are in conformity with theoretical research and real phenomenon of market. Besides, it is suitable for various kinds of price elastic demand. Hence, this model can be proved to be able to extend to other similar industries with the same nature.

In recent years, RNA structural comparison becomes a crucial problem in bioinformatic research. Generally, it is a popular approach for representing the RNA secondary structures with arc-annotation sets. Several methods can be used to compare two RNA structures, such as tree edit distance, longest arc-preserving common subsequence (LAPCS) and stem-based alignment. However, these methods may be helpful only for small RNA structures because of their high time complexity. In this thesis, we propose a simplified method to compare two RNA structures in O(mn)time, where m and n are the lengths of the two RNA sequences, respectively. Our method transforms the RNA structures into specific sequences called object sequences, then compare these object sequences to find their common substructures. We test our comparison method with 118 RNA structures obtained from RNase P Database. For any two structures, we try to identify whether they are in the same family by both structure comparison and sequence comparison. In our experiment, we find that our method for comparing RNA structures can yield better hit rates and is faster than the traditional method to compare the RNA sequences. Therefore, our approach for comparing RNA secondary structures is more sensitive in biology and more efficient in time complexity.

Mass Rapid Transit(MRT) plays a very important role for the city development,the investment cost is very expensive. It is necessary to derive the MRT system planning by considering the service reliability and performance index according to the forecast of annual ridership. With the less ridership as compared to Taipei MRT network, Kaohsiung MRT has to be developed to achieve the most cost effective investment of power supply and rolling stock planning. This thesis is to investigate the proper expansion planning of traction substations (TSS) for an electrified mass rapid transit system. The motion equation of train sets is used to solve the mechanical power consumption at each time snapshot according to the operation timetable, the passenger ridership and various types of operation resistance. The mathematical models of power converters in traction substations for different operation modes have been derived. With all train sets operated along the main line, the AC/DC load flow analysis is performed to find power demand of all traction substations for annual system peak operation over the study period. The objective function is formulated by considering both the voltage drop of train sets and investment cost of traction substations as the equivalent cost of all feasible states of each year. By performing the dynamic programming (DP) and immune algorithm (IA), the expansion planning of traction substations to achieve the minimum overall cost has been solved by identifying the optimal capacity and locations of new traction substations to be committed at each year.

The Human Genome Project completed in 2003 and the draft of human genome sequences were also yielded. It has been known that any two human gnomes are almost identical, and only very little difference makes human diversities. Single nucleotide polymorphism (SNP) means that a single-base nucleotide changes in DNA. A SNP sequence from one of a pair of chromosomes is called a haplotype. In this thesis, we study how to reconstruct a pair of chromosomes from a given set of fragments obtained by DNA sequencing in an individual. We define a new problem, the chromosome pair assembly problem, for the chromosome reconstruction. The goal of the problem is to find a pair of sequences such that the pair of output sequences have the minimum mismatch with the input fragments and their lengths are minimum. We first transform the problem instance into a directed multigraph. And then we propose an efficient algorithm to solve the problem. We apply the ACO algorithm to optimize the ordering of input fragments and use dynamic programming to determine SNP sites. After the chromosome pair is reconstructed, the two haplotypes can also be determined. We perform our algorithm on some artificial test data. The experiments show that our results are near the optimal solutions of the test data.