The maximum subarray problem (MSP) involves selection of a segment of consecutive array elements that has the largest possible sum over all other segments in a given array. The efficient algorithms for the MSP and related problems are expected to contribute to various applications in genomic sequence analysis, data mining or in computer vision etc. The MSP is a conceptually simple problem, and several linear time optimal algorithms for 1D version of the problem are already known. For 2D version, the currently known upper bounds are cubic or near-cubic time. For the wider applications, it would be interesting if multiple maximum subarrays are computed instead of just one, which motivates the work in the first half of the thesis. The generalized problem of K-maximum subarray involves finding K segments of the largest sum in sorted order. Two subcategories of the problem can be defined, which are K-overlapping maximum subarray problem (K-OMSP), and K-disjoint maximum subarray problem (K-DMSP). Studies on the K-OMSP have not been undertaken previously, hence the thesis explores various techniques to speed up the computation, and several new algorithms. The first algorithm for the 1D problem is of O(Kn) time, and increasingly efficient algorithms of O(K² + n logK) time, O((n+K) logK) time and O(n+K logmin(K, n)) time are presented. Considerations on extending these results to higher dimensions are made, which contributes to establishing O(n³) time for 2D version of the problem where K is bounded by a certain range. Ruzzo and Tompa studied the problem of all maximal scoring subsequences, whose definition is almost identical to that of the K-DMSP with a few subtle differences. Despite slight differences, their linear time algorithm is readily capable of computing the 1D K-DMSP, but it is not easily extended to higher dimensions. This observation motivates a new algorithm based on the tournament data structure, which is of O(n+K logmin(K, n)) worst-case time. The extended version of the new algorithm is capable of processing a 2D problem in O(n³ + min(K, n) · n² logmin(K, n)) time, that is O(n³) for K ≤ n/log n For the 2D MSP, the cubic time sequential computation is still expensive for practical purposes considering potential applications in computer vision and data mining. The second half of the thesis investigates a speed-up option through parallel computation. Previous parallel algorithms for the 2D MSP have huge demand for hardware resources, or their target parallel computation models are in the realm of pure theoretics. A nice compromise between speed and cost can be realized through utilizing a mesh topology. Two mesh algorithms for the 2D MSP with O(n) running time that require a network of size O(n²) are designed and analyzed, and various techniques are considered to maximize the practicality to their full potential.

It has been shown by Roger Jang in his paper titled "Adaptive-network-based fuzzy inference systems" that the Adaptive Network based Fuzzy Inference System can model nonlinear functions, identify nonlinear components in a control system, and predict a chaotic time series. The system use hybrid-learning procedure which employs the back-propagation-type gradient descent algorithm and the least squares estimator to estimate parameters of the model. However the learning procedure has several shortcomings due to the fact that * There is a harmful and unforeseeable influence of the size of the partial derivative on the weight step in the back-propagation-type gradient descent algorithm. *In some cases the matrices in the least square estimator can be ill-conditioned. *Several estimators are known which dominate, or outperform, the least square estimator. Therefore this thesis develops a new system that overcomes the above problems, which is called the "Faster Adaptive Network Fuzzy Inference System" (FANFIS). The new system in this thesis is shown to significantly out perform the existing method in predicting a chaotic time series , modelling a three-input nonlinear function and identifying dynamical systems. We also use FANFIS to predict five major stock closing prices in New Zealand namely Air New Zealand "A" Ltd., Brierley Investments Ltd., Carter Holt Harvey Ltd., Lion Nathan Ltd. and Telecom Corporation of New Zealand Ltd. The result shows that the new system out performed other competing models and by using simple trading strategy, profitable forecasting is possible.

Encouraging the use of computer algorithms by developing new algorithms and introducing uncommonly known algorithms for use on environmental science problems is a significant contribution, as it provides knowledge discovery tools to extract new aspects of results and draw new insights, additional to those from general statistical methods. Conducting analysis with appropriately chosen methods, in terms of quality of performance and results, computation time, flexibility and applicability to data of various natures, will help decision making in the policy development and management process for environmental studies. This thesis has three fundamental aims and motivations. Firstly, to develop a flexibly applicable attribute selection method, Tree Node Selection (TNS), and a decision tree assessment tool, Tree Node Selection for assessing decision tree structure (TNS-A), both of which use decision trees pre-generated by the widely used C4.5 decision tree algorithm as their information source, to identify important attributes from data. TNS helps the cost effective and efficient data collection and policy making process by selecting fewer, but important, attributes, and TNS-A provides a tool to assess the decision tree structure to extract information on the relationship of attributes and decisions. Secondly, to introduce the use of new, theoretical or unknown computer algorithms, such as the K-Maximum Subarray Algorithm (K-MSA) and Ant-Miner, by adjusting and maximizing their applicability and practicality to assess environmental science problems to bring new insights. Additionally, the unique advanced statistical and mathematical method, Singular Spectrum Analysis (SSA), is demonstrated as a data pre-processing method to help improve C4.5 results on noisy measurements. Thirdly, to promote, encourage and motivate environmental scientists to use ideas and methods developed in this thesis. The methods were tested with benchmark data and various real environmental science problems: sea container contamination, the Weed Risk Assessment model and weed spatial analysis for New Zealand Biosecurity, air pollution, climate and health, and defoliation imagery. The outcome of this thesis will be to introduce the concept and technique of data mining, a process of knowledge discovery from databases, to environmental science researchers in New Zealand and overseas by collaborating on future research to achieve, together with future policy and management, to maintain and sustain a healthy environment to live in.

Solution of any search problem lies in its search space. A search is a systematic examination of candidate solutions of a search problem. In this thesis, we present a search heuristic that we can cr-smodels. cr-smodels prunes the search space to quickly reach to the solution of a problem. The idea is to pick an atom for branching , that lowers the growth rate of the linear recurrence and thuse, minimizes the remaining search space. Our goal in developing cr-smodels is to develop a search heuristic that is efficient on a wide range of problems. Then, we test cr-smodels over a wide range of randomly generated benchmarks. we observed that often randomly generated graphs with no Hamiltonian cycle were trivial to solve. Since, Hamiltonian cycle is an important benchmark problem, my other goal is to develop techniques that generate hard instances of graphs with no Hamiltonian cycle.

Minicells are small manufacturing cells dedicated to an option family and organized in a multi-stage configuration for mass customization manufacturing. Product variants, depending on the customization requirements of each customer, are routed through the minicells as necessary. For successful mass customization, customized products must be manufactured at low cost and with short turn around time. Effective scheduling of jobs to be processed in minicells is essential to quickly deliver customized products. In this research, a genetic algorithm based approach is developed to schedule jobs in a minicell configuration by considering it as a multi-stage flow shop. A new crossover strategy is used in the genetic algorithm to obtain a minimum flow time schedule.

Regression models with correlated errors lead to nonadditivity of the information matrix. This makes the usual approach of design optimization (approximation with a continuous design, application of an equivalence theorem, numerical calculations by a gradient algorithm) impossible. A method is presented that allows the construction of a gradient algorithm by altering the information matrices through adding of supplementary noise. A heuristic is formulated to circumvent the nonconvexity problem and the method is applied to typical examples from the literature. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

Taking the advantage of the high-throughput Single Nucleotide Polymorphism (SNP) genotyping technology, Genome-Wide Association Studies (GWASs) are regarded holding promise for unravelling complex relationships between genotype and phenotype. GWASs aim to identify genetic variants associated with disease by assaying and analyzing hundreds of thousands of SNPs. Traditional single-locus-based and two-locus-based methods have been standardized and led to many interesting findings. Recently, a substantial number of GWASs indicate that, for most disorders, joint genetic effects (epistatic interaction) across the whole genome are broadly existing in complex traits. At present, identifying high-order epistatic interactions from GWASs is computationally and methodologically challenging. My dissertation research focuses on the problem of searching genome-wide association with considering three frequently encountered scenarios, i.e. one case one control, multi-cases multi-controls, and Linkage Disequilibrium (LD) block structure. For the first scenario, we present a simple and fast method, named DCHE, using dynamic clustering. Also, we design two methods, a Bayesian inference based method and a heuristic method, to detect genome-wide multi-locus epistatic interactions on multiple diseases. For the last scenario, we propose a block-based Bayesian approach to model the LD and conditional disease association simultaneously. Experimental results on both synthetic and real GWAS datasets show that the proposed methods improve the detection accuracy of disease-specific associations and lessen the computational cost compared with current popular methods.

In telecommunication, the series of mobile network exceptions is a processwhich exhibits surges and bursts. The bursty part is usually caused by systemmalfunction. Additionally, the mobile network exceptions are often timedependent. A model that successfully captures these aspects will make troubleshootingmuch easier for system engineers. The Hidden Markov Model(HMM) is a good candidate as it provides a mechanism to capture both thetime dependency and the random occurrence of bursts. This thesis focuses onan application of the HMM to mobile network exceptions, with a case study ofEricsson’s Dropped Call data. For estimation purposes, two methods of maximumlikelihood estimation for HMM, namely, EM algorithm and stochasticEM algorithm, are used.

Locomotion automation is a very challenging and complex problem to solve. Besides the obvious navigation problems, there are also problems regarding the environment in which navigation has to be performed. Terrains with obstacles such as rocks, steps or high inclinations, among others, pose serious difficulties to normal wheeled vehicles. The flexibility of legged locomotion is ideal for these types of terrains but this alternate form of locomotion brings with it its own challenges to be solved, caused by the high number of degrees of freedom inherent to it. This problem is usually computationally intensive, so an alternative, using simple and hardware amenable bio-inspired systems, was studied. The goal of this thesis was to investigate if using a biologically inspired learning algorithm, integrated in a fully biologically inspired system, can improve its performance on irregular terrain by adapting its gait to deal with obstacles in its path. At first, two different versions of a learning algorithm based on unsupervised reinforcement learning were developed and evaluated. These systems worked by correlating different events and using them to adjust the behaviour of the system so that it predicts difficult situations and adapts to them beforehand. The difference between these versions was the implementation of a mechanism that allowed for some correlations to be forgotten and suppressed by stronger ones. Secondly, a depth from motion system was tested with unsatisfactory results. The source of the problems are analysed and discussed. An alternative system based on stereo vision was implemented, together with an obstacle detection system based on neuron and synaptic models. It is shown that this system is able to detect obstacles in the path of the robot. After the individual systems were completed, they were integrated together and the system performance was evaluated in a series of 3D simulations using various scenarios. These simulations allowed to conclude that both learning systems were able to adapt to simple scenarios but only the one capable of forgetting past correlations was able to adjust correctly in the more complex experiments.

Session ID: SA-G4-2 / Joint 4th International Conference on Soft Computing and Intelligent Systems and 9th International Symposium on advanced Intelligent Systems, September 17-21, 2008, Nagoya University, Nagoya, Japan