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.

State of the art direction finding (DF) systems usually have several antennas in order to increase accuracy and robustness to certain factors. In this thesis, a three antenna DF system is built and evaluated. While more antennas give better DF performance, a three antenna system is useful for system simplicity and many of the problems in DF systems can be observed and evaluated easily. This system can be used for both azimuth and elevation direction of arrival (DOA) estimation. The system is composed of three monopole antennas, an RF front end, A/D converters and digital signal processing (DSP) units. A number of algorithms are considered, such as, three channel interferometer, correlative interferometer, LSE (least square error) based correlative interferometer and MUSIC (multiple signal classification) algorithms. Different problems in DF systems are investigated. These are gain/phase mismatch of the receiver channels, mutual coupling between antennas, multipath signals and multiple sources. The advantages and disadvantages of different algorithms are outlined.

Unit commitment is one of the most important subjects with respect to the economical operation of power systems, which attempts to minimize the total thermal generating cost while satisfying all the necessary restrictive conditions. ¡@¡@This thesis proposes a short-term thermal generating unit commitment by genetic algorithm and back propagation network. Genetic algorithm is based on the optimization theory developed from natural evolution principles, and in the optimization process, seeks a set of solutions simultaneously rather than any single one by adopting stochastic movement rule from one solution to another, which prevents restriction to fractional minimal values. Neural networks method outperforms in speed and stability. This thesis uses back propagation network method to complete neural networks and sets the optimal unit combination derived from genetic algorithm as the target output. ¡@¡@Under fixed electrical systems, instant responsiveness can be calculated by neural networks. When the systematical architecture changes, genetic algorithm can be applied to re-evaluation of the optimal unit commitment, hoping to improve the pitfalls of traditional methods. ¡@¡@This thesis takes the power system of six units for example to conduct performance assessment. The results show that genetic algorithm provides solutions closer to the overall optimal solution than traditional methods in optimizing unit commitment. On the other hand, neural networks method can not only approximate the solution obtained by genetic algorithm but also process faster than any other methods.

Walking machines may not be more common or faster than the transportations with wheels. It can¡¦t be ignored in the occasions of unknown terrain. This paper is going to discuss about how a walking machine get faster and be static stable. When the quadrupeds walk toward, the wide won¡¦t be changed. So that, longitudinal stability margin can take the place of stability margin to simplify gait problems. Meanwhile we can get the optimal gait. In the past researches, there is only one kind of walking type will be discussed in one time. This is because there are not so many relationships between different kinds of movement. If we take one step ahead to discuss the optimal gait, it will be more difficult. If there was a way to get into optimal gait from random initial position, we can connect one movement with the other. The velocity was constrained while the quadruped modal has had been made since 1968 by McGhee. We will try to change the working area to approve the performance. As to the researches of multi-legs walking machine, most of them talk about quadrupeds and hexapods. it will be less if the more legs we are talked about. To maintain stable tread, a walking machine request four legs at least. We can regard a quadruped as a unit, and divide a multi-leg working machine in to many quadrupeds. By using the method of quadruped analysis, we can simplify multi-legs gait algorithm problems.

In this study we will consider the construction of approximate optimal design for one-dimensional regression by exchange algorithm. Sufficient conditions under which an optimal design must have the minimal support points are known in Theorem 2.3.2 of Fedorov (1972). However, there are only a few cases which the analytic optimal designs are known. The exchange procedure for computing optimal designs is easily adopted to most criteria. We describe implementations for constructing the well-known special cases D-, A-, and c-optimal designs with the minimum number of support points. Examples which illustrate how the algorithm can be used to obtain these optimal designs and the performance of the algorithm are discussed. The commonly used D-, A-, and c-optimal criteria will be employed to study the convergence properties of the exchange algorithm for regression model which the set of the product of regression functions forms a Chebyshev system.

Building a rule-based classification system for a training data set is an important research topic in the area of data mining, knowledge discovery and expert systems. Recently, the GA-based fuzzy approach is shown to be an effective way to design an efficient evolutionary fuzzy system. In this thesis a three layers genetic algorithm with Simulated Annealing for selecting a small number of fuzzy if-then rules to building a compact fuzzy classification system will be proposed. The rule selection problem with three objectives: (1) maximize the number of correctly classified patterns, (2) minimize the number of fuzzy if-then rules, and (3) minimize the number of required features. Genetic algorithms are applied to solve this problem. A set of fuzzy if-then rules is coded into a binary string and treated as an in-dividual in genetic algorithms. The fitness of each individual is specified by three ob-jectives in the combinatorial optimization problem. Simulated annealing (SA) is op-tionally cooperated with three layers genetic algorithm to effectively select some layer control genes. The performance of the proposed method for training data and test data is ex-amined by computer simulations on the iris data set and spiral data set, and comparing the performance with the existing approaches. It is shown empirically that the pro-posed method outperforms the existing methods in the design of optimal fuzzy sys-tems.

When we use the FDTD method to analyze electromagnetic problems, it has to properly discretize the space and time. Automeshing can non-uniformly discretize the simulated structure and generate gradual grids. To improve the efficiency of automeshing, we optimize the parameter of automeshing using the genetic algorithm. Without sacrificing accuracy, it searches a suitable ratio to reduce the generated grids and to save simulation time. At last, we optimize the PIFA using genetic algorithm and search automatically the height of the substrate and the feed position in order to obtain optimal performance. When we use the genetic algorithm, it is the key point to define an objective function evaluating the fitness of the optimized problem. It is important that the function has to appropriately describe the performance at that time.

In airline industry scheduling problems, the aircraft routing and the aircrew pairing problems are highly related to fueling and personnel costs. When performing aircraft routing and aircrew pairing, several objectives, such as the ground-turn around time, flow balance, transition time, number of deadheads, number of layovers, flying time, and flight duty period should be considered. It is difficult to optimize these conflicting objectives simultaneously. Many issues are yet to be solved as follows. 1. Most researches related to the aircraft routing and aircrew pairing problems use set partitioning or set covering models. Planners must (1) enumerate several possible subsets of flights, (2) assign costs, and (3) check feasibilities simultaneously. This is time-consuming since the numbers of whole subsets are exponential values to the problem size. 2. The number of enumerated subsets is usually too small to cover the whole solution space. Therefore, even if the optimal solution is found, it is just a local optimal solution of the enumerated subsets. 3. When using traditional optimization algorithms to find a combination of these subsets with minimal cost, it should be ensured that all flights should be covered exactly once. This causes the overheads of checking the number of coverage. 4. In traditional solution methods, the number of required aircrafts and crewmembers cannot be pre-specified since these numbers can only be obtained when the optimization algorithm is completed. 5. All enumerated subsets should be assigned cost values according to various objectives, such as transition time, number of deadheads, number of layovers, flying time, and flight duty period. The cost values are difficult to assign since it is highly dependent on domain knowledge, and usually nonlinear. Also, inappropriate cost values will cause bias in optimization, and ambiguity among all factors due to single objective formulation. Hence, to overcome these problems, we propose several enhancements in both formulation and the solution stages. In the formulation stage, we propose a novel permutation-based model with multiple objectives, which has the following features. 1. The proposed permutation-based model can save the overheads of pre-enumerating possible sub-solutions 2. The permutation-based model can cover the whole solution space. Hence, it has more chance to find out the global optimal solution. 3. The proposed permutation-based model can ensure that each flight can be covered exactly once to save the overheads of checking the number of coverage. 4. The proposed permutation-based model can provide a new way to pre-specify the number of aircrafts or group number of crewmembers. 5. Taking the advantage of multiobjective formulation, various objectives are considered separatively instead of assigning cost values. All objective can be considered individually even if they have different definitions of optimality or scales. In the solution stage, we apply the MOI-based MGA (MMGA) to solve the problems of aircraft routing and crew pairing. MMGA is originally proposed to solve numerical controller design problem. By using MMGA, designers can configure the ranges of solutions via adjusting an auxiliary vector of performance indices. To make MMGA more suitable for solving the aircraft routing and aircrew pairing problems, some enhancements are added, such as chromosome encoding scheme, repairing strategy, crossover, and mutation operations. This approach has following features. 1. In both aircraft routing and aircrew pairing problems, the permutation-based encoding scheme, which is the same as the formulation model, can ensure all flights be covered once. 2. Moreover, in the crew pairing problem, the sectional permutation-based encoding scheme, which divides the flights into three sections, such as earlier flights, later flights, and floating flights, can enhance MMGA to find out optimal solutions which satisfy the flight duty period objective. 3. Also, to overcome the large violations caused by random generation of candidate solutions, we use a repairing strategy, which repairs all generated solutions by reordering the sequences of flights according to departure times. 4. The sectional order-based crossover can have a more stable evolution than the widely-used partial mapped crossover. Also, it can make the newborn offspring keep the features of three sections defined in the encoding scheme. 5. Also, the sectional mutation can inherit the advantages of the widely-used reciprocal mutation and keep the features of three sections defined in the encoding scheme. In the aircraft routing problem, experiments show that MMGA can find out optimal flight schedules under the condition of sufficient aircrafts. On the other aspect, when the number of aircrafts is insufficient, planners can modify the obtained solutions by a little retiming process when the number of violations is small. In the aircrew pairing problem, experiments indicate the proposed approach can solve the aircrew pairing problem with minimal group number of crewmembers which is verified by a branch-and-bound approach. By using MMGA, the problems of aircraft routing and aircrew pairing can be solved efficiently and effectively. In other words, planners can solve these problems in a short time period instead of enumeration and feasibility checking by traditional methods. Via the proposed approach, planners can further consider more important issues, such as to suggest better schedules with lower cost and higher benefit.

In order to understand the structural and electronic properties of titanium oxide nanoparticles of different sizes, the FIRE algorithm combining the simulated annealing method is employed to find the structures of TinO2n (n=1¡Ð6) nanoparticles with the global minimum potential energy. To deeply understand electronic properties, the relaxation structures of TinO2n (n=1¡Ð6) nanoparticle from previous method will be recalculated by density functional theory (DFT) method. The Fukui function, Frontier Molecular Orbital and density of state of TinO2n (n=1¡Ð6) nanoparticles are discussed for understanding the size effect of TiO2 nanoparticles on chemical reactivity. The adsorption and dissociation energy mechanism of the HN3 molecule and its fragments are also discussed and are compared with the mechanism about HN3 on the anatase surface.

With the improvement of biological techniques, the amount of biosequences data, such as DNA, RNA and protein sequences, are growing explosively. It is almost impossible to handle such huge amount of data purely by manpower. Thus the requirement of the great computing power is essential. There are some ways to treat biosequence data, finding identical biosequences, searching similar biosequences, or mining the signature of biosequences. All of these are based on the same problems, the biosequence alignment problems. In this dissertation, we shall study the biosequence alignment problems to raise the biological meaning of the optimal or near-optimal alignments since the biologists and computer scientists sometimes argue the biological meaning of the mathematically optimal alignment obtained based on some scoring functions. We first study the methods to improve the optimal alignment of two given biosequences. Since usually the optimal alignment is not unique, there should exist the best one among the optimal alignments, and we try to extract this by defining some other criteria to judge the goodness of the alignments when the traditional methods cannot decide which is the better one. Two algorithms are proposed for solving the newly defined biosequence alignment problems, the smoothest optimal alignment and the most conserved optimal alignment problems. Some other criteria are also discussed since most of them can be solved in a similar way. Then we notice that the most biologically meaningful alignment may not be the optimal one since there is no perfect scoring matrix. We address our candidates in those near-optimal alignments, and present a tracing marking function to get all near-optimal alignments and use the criterion "the most conserved" to filter it, which is named as the near-optimal block alignment (NBA) problem. Finally, as everybody knows that existing scoring matrices are not perfect at all, we try to figure out how we choose the winner when multiple scoring matrices are applied. We define some reasonable schemes to decide the winner alignment. In this dissertation, we solve and discuss the algorithms for near-optimal alignment problems on biosequences. In the future, we would like to do some experiments to support or reject these concepts.