In this thesis, we present two e cent algorithms to compute shortest path between pair of vertices in directed and undirected double-loop networks. The algorithm for undirected double-loop networks is based on the concept "packed basis" proposed by Janez Zerrovnik and Toma z Pisanski. With O(logN) preprocessing time, both algorithms need only constant time to compute the shortest path between any pair of vertices in the network. This is an improvement of the best known algorithm, which needs O(l) time, where l is the length of the path in the directed double-loop networks. These algo- rithms are useful in message routing in the double-loop networks. Once the network has been constructed, the parameters for computing the shortest paths can be computed. At the time a message is to be delivered, the algo- rithm needs only constant time to determine which edge the message should be sent.

Oligo array is a high throughput technology and is widely used in many scopes of biology and medical researches for quantitative and highly parallel measurements of gene expression. When one faulty step occurs during the synthesis process, it affects all probes using the faulty step. In this thesis, a two-phase genetic algorithm (GA) is proposed to design optimal quality control of oligo array for detecting any single faulty step. The first phase performs the wide search to obtain the approximate solutions and the second phase performs the local search on the approximate solutions to achieve the optimal solution. Besides, the proposed algorithm could hold many non-duplicate individuals and parallelly search multiple regions simultaneously. The superior searching capability of the two-phase GA helps us to find out the 275 nonequireplicate cases that settled by the hill-climbing algorithm. Furthermore, the proposed algorithm also discovers five more open issues.

The multiplex PCR experiment is to amplify multiple regions of a DNA sequence at the same time by using different primer pairs. Although, in recent years, there are lots of methods for PCR primer design, only a few of them focus on the multiplex PCR primer design. The multiplex PCR primer design is a tedious task since there are too many constraints to be satisfied. A new method for multiplex PCR primer design strategy using genetic algorithm is proposed. The proposed algorithm is able to find a set of suitable primer pairs more efficient and uses a MAP model to speed up the examination of the specificity constraint. The dry-dock experiment shows that the proposed algorithm finds several sets of primer pairs for multiplex PCR that not only obey the design properties, but also have specificity.

The objective of this thesis is to enhance the reliability analysis of Relaying systems and build-up model by Markov theory for taipower transmission lines. The set of combinatory multi-elements can be expressed a transition matrix for any pilot protection analysis. The protective reliability system need for transmission protection is introduced and the block modeling consists of protective relays, communication set and circuit breaker. The block modeling is applied for the analysis of the reliability and availability of protection systems by Markov theory, which can be need to derive the adapative maintance cycle by Markov reliability modeling. The system reliability is analysis related to the interruption of supply power. There many methods to be used for the analysis of system reliability such as state space, network. etc. The Markov modeling is more complicated and difficult, however better time-vary probability functions can be defined, for stochastic modeling, the system reliability at any time axis can be obtained by Markov transition matrix, with the time-vary Markov transition matrix. The customers served by each substation can be affected according to the states of transmission lines healthy. Althouth 80% of system faults occurs in the distribution system, transmission line faults will cause more serious service outage. According to the Kauo-Ping transmission line model in taipower, the optimal protection relay planning is solved by minimizing the overall outage cost of customer service interruption and investment protection relay equipments for transmission power systems with immune algorithm. The objective function and constraints are expressed as antigen, and all feasible solutions are expressed as antibody. The diversity of antibody is then enhanced by proximity of antigen so that the global optimization during the solution process can be obtained. It is found that the power service can be restored effectively with the optimal planning of protection relay by the proposed immune algorithm. Based on the computer simulation of protection relay planning, different protection relaying strategies optimal relay planning and customer loss, can be considered for different to enhance the reliability of protection relay system for loss interruption of customer power outage.

The Denial-of-Service (DoS) attacks with the source IP address spoofing techniques has become a major threat to the Internet. An intrusion detection system is often used to detect DoS attacks and to coordinate with the firewall to block them. However, DoS attack packets consume and may exhaust all the resources, causing degrading network performance or, even worse, network breakdown. A proactive approach to DoS attacks is allocating the original attack host(s) issuing the attacks and stopping the malicious traffic, instead of wasting resources on the attack traffic. In this research, an ant-based traceback approach is proposed to identify the DoS attack origin. Instead of creating a new type or function needed by the router or proceeding the high volume, find-grained data, the proposed traceback approach uses flow level information to spot the origin of a DoS attack. Two characteristics of ant algorithm, quick convergence and heuristic, are adopted in the proposed approach on finding the DoS attack path. Quick convergence efficiently finds out the origin of a DoS attack; heuristic gives the solution even though partial flow information is provided by the network. The proposed method is validated and evaluated through the preliminary experiments and simulations generating various network environments by network simulator, NS-2. The simulation results show that the proposed method can successfully and efficiently find the DoS attack path in various simulated network environments, with full and partial flow information provided by the network.

In this thesis, we propose and evaluate algorithms for solving the worst-case-coverage deployment problem in ad-hoc wireless sensor networks. The worst-case-coverage deployment problem is to deploy additional sensors in the wireless sensor field to optimize the worst-case coverage. We derive a duality theorem that reveals the close relation between the maximum breach path and the minimum Delaunay cut. The duality theorem is similar to the well-known max-flow-min-cut theorem in the field of network optimization. The major difference lies in the fact that the object function we study in this paper is nonlinear rather than linear. Based on the duality theorem, we propose an efficient dual algorithm to solve the worst-case-coverage deployment problem. In addition, we propose a genetic algorithm for deploying a number of additional sensors simultaneously. We use analytical proofs and simulation results to justify the usage of the proposed approaches.

First, we study a Poisson model a polluted random screen. In this model, the defects on random screen are assumed Poisson-distribution and overlapped. The transmittance effects of overlapping defects are multiplicative. We can compute the autocorrelation function of the screen is obtained by defects' density, radius, and transmittance. Using the autocorrelation function, we then restore the telescope astronomy images. These image signals are generally degraded by their propagation through the random scattering in atmosphere. To restore the images, we estimate the three key parameters by three methods. They are expectation- maximization (EM) method and two Maximum-Entropy (ME) methods according to two different definitions. The restoration are successful and demonstrated in this thesis.

The thesis illustrates the development of DSP-based ¡§Relativity Gene Algorithm For Multiple Faces Recognition System＂. The recognition system is divided into three systems: Ellipsoid location system of multiple human faces, Feature points and feature vectors extraction system, Recognition system algorithm of multiple human faces. Ellipsoid location system of multiple human faces is using CCD camera or digital camera to capture image data which will be recognized in any background, and transmitting the image data to SRAM on DSP through the PPI interface on DSP. Then, using relatively genetic algorithm with the face color of skin and ellipsoid information locate face ellipses which are any location and size in complex background. Feature points and feature vectors extraction system finds facial feature points in located human face by many image process skills. Recognition system algorithm of multiple human faces is using decision by majority. Using characteristic vectors compares every vector in the database. Then, we draw out the highest ID. The recognizable result is over. The experimental result of the developed recognition system demonstrates satisfied and efficiency.

The current study has applied the Genetic Algorithm (GA) for the boundary parameters calibration in the hydrodynamic-based tidal model. The objective is to minimize the deviation between the estimated results acquired from the simulation model and the real tidal data along Taiwan coast. The manual trial-error has been widely used in the past, but such approach is inefficient due to the complexity posed by the tremendous amounts of parameters. Fortunately, with the modern computer capability, some automatic searching processes, in particular GA, can be implemented to handle the large data set and reduce the human subjectivity when conducting the calibration. Besides, owing to the efficient evolution procedures, GA can find better solutions in a shorter time compared to the manual approach. Based on the preliminary experiments of the current study, the integration of GA with the hydrodynamic-based tidal model can improve the accuracy of simulation.

Since the cost of software testing has continuously accounted for large proportion of the software development total cost, automatic test data generation becomes a hot topic in recent software testing research. These researches attempt to reduce the cost of software testing by generating test data automatically, but they are discussed only for the single version programs not for the programs which are needed re-testing after changing. On the other hand, the regression testing researches discuss about how to re-test programs after changing, but they don¡¦t talk about how to generate test data automatically. Therefore, we propose an automatic test data evolution strategy in this paper. We use the method of regression testing to find out the part of programs which need re-testing, then automatic evolutes the test data by hybrid genetic algorithm. According to the experiment result, our strategy has the same or better testing ability but needs less cost than the other strategies.