The k-LCS problem is to find the longest common subsequence (LCS) of k input sequences. It is difficult while the number of input sequences is large. In the past, researchers focused on finding the LCS of two sequences (2-LCS). However, there is no good algorithm for finding the optimal solution of k-LCS up to now. For solving the k-LCS problem, in this thesis, we first propose a mixed algorithm, which is a combination of a heuristic algorithm, genetic algorithm (GA) and ant colony optimization (ACO) algorithm. Then, we propose an enhanced ACO (EACO) algorithm, composed of the heuristic algorithm and matching pair algorithm (MPA). In our experiments, we compare our algorithms with expansion algorithm, best next for maximal available symbol algorithm, GA and ACO algorithm. The experimental results on several sets of DNA and protein sequences show that our EACO algorithm outperforms other algorithms in the lengths of solutions.

Genetinių algoritmų panaudojimo galimybės ir paplitimas nuolat didėja. Daugelyje nagrinėtų mokslinių darbų, genetiniai algoritmai yra naudojami uždavinių optimizavimui. Optimizavimui naudojama daug skirtingų metodų. Sprendžiant konkretų uždavinį mokslinėje literatūroje paprastai pritaikoma keletas metodų tam, kad būtų pagerinti gauti rezultatai, t.y., išbandoma keletas strategijų. Deja, nepavyko rasti tyrimų, kaip tos pačios genetinės paieškos strategijos gali būti pritaikytos kitoms analogiškoms problemoms spręsti. Šiame darbe pateikiama probleminės srities apžvalga, tyrimo aprašymas bandymų rezultatai ir išvados. / The use of genetic algorithms considerably increases. In some research works GA‘s are investigated to optimize graph problems. There are many different strategies for GA optimization. Unfortunately, there are no investigations if a strategy, suitable for a particular graph problem, will be useful solving other graph problems. In this work I originated, described and developed some GA learning strategy elements. Also I developed some that are available in other research works. These elements are: generation of initial population, selection of individuals, mutation, crossover and some other parameters. All possible strategies (about 300) are tested in this work for three graph problems: shortest path, longest path and traveling salesman problem. Results are summarized and described.

No description available.

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.

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.

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.

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

The present work investigates the applicability of Genetic Algorithms (GA) to the problem of signal propagation in Native Neuronal Networks (NNNs). These networks are comprised of neurons, some of which receive input signals. The signals propagate though the network by transmission between neurons. The research focuses on the regeneration of the output signal of the network without knowing the original input signal. The computational complexity of the problem is prohibitive for the exact computation. We propose to use a heuristic approach called Genetic Algorithm. Three algorithms are developed, based on the GA technique. The developed algorithms are tested on two different networks with varying input signals. The results obtained from the testing indicate significantly better performance of the developed algorithms compared to the Uniform Random Search (URS) technique, which is used as a control group. The importance of the research is in the demonstration of the ability of GA-based algorithms to successfully solve the problem at hand.

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.

In this thesis, we consider joint beamforming, power, and channel allocation in a multi-user and multi-channel underlay cognitive radio network (CRN). In this system, beamforming is implemented at each SU-TX to minimize the co-channel interference. The formulated joint optimization problem is a non-convex, mixed integer nonlinear programming (MINLP) problem. We propose a solution which consists of two stages. At first, given a channel allocation, a feasible solutions for power and beamforming vectors are derived by converting the problem into a convex form with an introduced optimal auxiliary variable and semidefinite relaxation (SDR) approach. Next, two explicit searching algorithms, i.e., genetic algorithm (GA) and simulated annealing (SA)-based algorithm are proposed to determine optimal channel allocations. Simulation results show that beamforming, power and channel allocation with SA (BPCA-SA) algorithm achieves a close optimal sum-rate with a lower computational complexity compared with beamforming, power and channel allocation with GA (BPCA-GA) algorithm. Furthermore, our proposed allocation scheme shows significant improvement than zero-forcing beamforming (ZFBF).