No description available.

Tree-based methods have wide applications for solving large-scale problems in electromagnetics, astrophysics, quantum chemistry, fluid mechanics, acoustics, and many more areas. This thesis focuses on their applicability for solving large-scale problems in electromagnetics. The Barnes-Hut (BH) algorithm and the Fast Multipole Method (FMM) are introduced along with a survey of important previous work. The required theory for applying those methods to problems in electromagnetics is presented with particular emphasis on the capacitance extraction problem and broadband full-wave scattering. A novel single source approximation is introduced for approximating clusters of electrostatic sources in multi-layered media. The approximation is derived by matching the spectra of the field in the vicinity of the stationary phase point. Combined with the BH algorithm, a new algorithm is shown to be an efficient method for evaluating electrostatic fields in multilayered media. Specifically, the new BH algorithm is well suited for fast capacitance extraction. The BH algorithm is also adapted to the scalar Helmholtz kernel by using the same methodology to derive an accurate single source approximation. The result is a fast algorithm that is suitable for accelerating the solution of the Electric Field Integral Equation (EFIE) for electrically small structures. Finally, a new version of FMM is presented that is stable and efficient from the low frequency regime to mid-range frequencies. By applying analytical derivatives to the field expansions at the observation points, the proposed method can rapidly evaluate vectorial kernels that arise in the FMM-accelerated solution of EFIE, the Magnetic Field Integral Equation (MFIE), and the Combined Field Integral Equation (CFIE).

Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

Financial derivatives play significant role in an investor's success. Financial option is one form of derivatives. Option pricing is one of the challenging and fundamental problems of computational finance. Due to highly volatile and dynamic market conditions, there are no closed form solutions available except for simple styles of options such as, European options. Due to the complex nature of the governing mathematics, several numerical approaches have been proposed in the past to price American style and other complex options approximately. Bio-inspired and nature-inspired algorithms have been considered for solving large, dynamic and complex scientific and engineering problems. These algorithms are inspired by techniques developed by the insect societies for their own survival. Nature-inspired algorithms, in particular, have gained prominence in real world optimization problems such as in mobile ad hoc networks. The option pricing problem fits very well into this category of problems due to the ad hoc nature of the market. Particle swarm optimization (PSO) is one of the novel global search algorithms based on a class of nature-inspired techniques known as swarm intelligence. In this research, we have designed a sequential PSO based option pricing algorithm using basic principles of PSO. The algorithm is applicable for both European and American options, and handles both constant and variable volatility. We show that our results for European options compare well with Black-Scholes-Merton formula. Since it is very important and critical to lock-in profit making opportunities in the real market, we have also designed and developed parallel algorithm to expedite the computing process. We evaluate the performance of our algorithm on a cluster of multicore machines that supports three different architectures: shared memory, distributed memory, and a hybrid architectures. We conclude that for a shared memory architecture or a hybrid architecture, one-to-one mapping of particles to processors is recommended for performance speedup. We get a speedup of 20 on a cluster of four nodes with 8 dual-core processors per node.

This thesis presents the research results on the development of a microwave tomography imaging algorithm capable of reconstructing the dielectric properties of the unknown object. Our focus was on the theoretical aspects of the non-linear tomographic image reconstruction problem with particular emphasis on developing efficient numerical and non-linear optimization for solving the inverse scattering problem. A detailed description of a novel microwave tomography method based on frequency dependent finite difference time domain, a numerical method for solving Maxwell's equations and Genetic Algorithm (GA) as a global optimization technique is given. The proposed technique has the ability to deal with the heterogeneous and dispersive object with complex distribution of dielectric properties and to provide a quantitative image of permittivity and conductivity profile of the object. It is shown that the proposed technique is capable of using the multi-frequency, multi-view, and multi-incident planer techniques which provide useful information for the reconstruction of the dielectric properties profile and improve image quality. In addition, we show that when a-priori information about the object under test is known, it can be easily integrated with the inversion process. This provides realistic regularization of the solution and removes or reduces the possibility of non-true solutions. We further introduced application of the GA such as binary-coded GA, real-coded GA, hybrid binary and real coded GA, and neural-network/GA for solving the inverse scattering problem which improved the quality of the images as well as the conversion rate. The implications and possible advantages of each type of optimization are discussed, and synthetic inversion results are presented. The results showed that the proposed algorithm was capable of providing the quantitative images, although more research is still required to improve the image quality. In the proposed technique the computation time for solution convergence varies from a few hours to several days. Therefore, the parallel implementation of the algorithm was carried out to reduce the runtime. The proposed technique was evaluated for application in microwave breast cancer imaging as well as measurement data from university of Manitoba and Institut Frsenel's microwave tomography systems.

When referring physicians decide to refer their patients to specialist care, they rarely, if ever, make a referral decision with the benefit of having access to all of the desirable information. It is therefore highly unlikely that the referring physician will make the optimal choice of specialist for that particular referral. A specialist selection optimization algorithm was developed to guarantee that the “right specialist” for each patient’s referral was chosen. The specialist selection optimization algorithm was developed based on feedback from over 120 users of the e-referral program. The developed algorithm was simulated, tested, and validated in MATLAB. Results from the MATLAB simulation demonstrate that the algorithm functioned as it was designed to. The developed algorithm provides referring physicians with an unprecedented level of support for their decision of which specialist to refer their patient to.

A simulated learning hierarchical architecture for vector classification is presented. The hierarchy used homogeneous scripted classifiers, maintaining similarity tables, and selforganising maps for the input. The scripted classifiers produced output, and guided learning with permutable script instruction tables. A large space of parametrised script instructions was created, from which many different combinations could be implemented. The parameter space for the script instruction tables was tuned using a genetic algorithm with the goal of optimizing the networks ability to predict class labels for bit pattern inputs. The classification system, known as Dura, was presented with various visual classification problems, such as: detecting overlapping lines, locating objects, or counting polygons. The network was trained with a random subset from the input space, and was then tested over a uniformly sampled subset. The results showed that Dura could successfully classify these and other problems. The optimal scripts and parameters were analysed, allowing inferences about which scripted operations were important, and what roles they played in the learning classification system. Further investigations were undertaken to determine Dura's performance in the presence of noise, as well as the robustness of the solutions when faced with highly stochastic training sequences. It was also shown that robustness and noise tolerance in solutions could be improved through certain adjustments to the algorithm. These adjustments led to different solutions which could be compared to determine what changes were responsible for the increased robustness or noise immunity. The behaviour of the genetic algorithm tuning the network was also analysed, leading to the development of a super solutions cache, as well as improvements in: convergence, fitness function, and simulation duration. The entire network was simulated using a program written in C++ using FLTK libraries for the graphical user interface.

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.