Study On Intelligent Computational Methods And Applications To Combinatorial Optimization Problems

This thesis is devoted to some theories and application studies based on the genetic algorithm and kernel method for pattern analysis. Researches focus on a clonal selection-based memetic algorithm for solving Job-Shop Scheduling Problem (JSSP), generalized chromosome genetic algorithm (GCGA) for solving classical traveling salesman problems (CTSP), and kernel-based principal component analysis for assessing the financial performance of listed companies. The main contents are summarized as follows:(1) Study on the Job Shop Scheduling Problems (JSSP). JSSP could be described as processing n work pieces in m machines, all the work pieces must go through scheduled pathways (i.e. the technique constraints of work pieces) throughout all the m machines and certain processing time is needed in every machine. The mission of scheduling algorithm is how to arrange a schedule of the processing sequence of work pieces in every machine logically which is optimal for certain performance index and satisfies the technique constraints. As a typical NP-hard problem, most existing intelligent computing methods could reach the approximate optimal solution at least, whereas single algorithms cannot exert its advantages completely. This thesis presents a hybrid of two or even more algorithms to utilize the advantages of all involved algorithms as completely as possibly. A clonal selection based memetic algorithm with operation-based representation is presented for solving job shop scheduling problems. To search for the best solutions, a recombination operation is proposed. And then a complete framework of memetic algorithm for job shop scheduling problems is designed, in which clonal selection and simulated annealing are used as global search and local search methods, respectively. In order to ensure that the initial solutions excel the random ones and the population keeps individual diversity, we propose a novel population initial algorithm, based on the Giffler's group initial algorithm. In the clonal selection algorithm model, some mechanisms in the clonal selection, including affinity maturation, high probability mutation and receptor cutups, are used in order to achieve the global optimal solution. In addition, being aimed at the problem about getting into locked into local minima easily in the Menetic algorithm, this thesis designs local research strategy based on Simulated Annealing (SA) and adopts the neighborhood definition of Nowicki and Smutnicki to achieve the decrease of neighborhood's radius as the optimization process goes deeply. Finally, the proposed algorithm is examined using some well-known benchmark problems. Numerical results validate the effectiveness of the proposed algorithm.(2) GTSP can be formulated as follows: There are n cities distributed in m regions, these regions are not overlapped mutually, and a traveling salesman problem is asked to visit all of the m regions and then return to his start. The aim of GTSP is to determine the tour covering all of the m regions, but only once for each region. Many existing GTSP algorithms based on mathematical programming need the transformation from GTSP to CTSP. With this kind of transformation, CTSP algorithms could be used to solve GTSP. However, the transformation would cause the increase of the dimensions of involved problems at some extent. In some cases, the transformed CTSP are even more difficult to solve than the original ones. GCGA is a novel genetic algorithm aimed at solving GTSP and, in the mean time, it could be used to solve CTSP in the same framework. However, authors did not demonstrate the feasibility to solving CTSP in their earlier work. In this thesis, the generalized chromosome characteristics, including chromosome length and coding space, are analyzed, and then the feasibility for solving the CTSP is verified. Numerical experiments show the advantages of the GCGA for solving a large scale CTSP, compared with the common genetic algorithms.(3) An extended ant colony optimization method is proposed for solving the GTSP. The ant optimization algorithm is a novel algorithm originating from the natural phenomenon of ant searching food. As a general random optimizing method, the ant optimization algorithm inspired by the behavior feature of natural ants has been applied successfully to a series of difficult combinatorial optimization questions. However, ant optimization algorithm itself still needs further research on both theory and application sides. In order to avoid being trapped into local minima, a mutation process and a local searching technique are also introduced into the proposed method. Numerical results show that the proposed method could deal with the GTSP problems fairly well and the developed mutation process and local search technique introduced could effectively overcome the drawbacks in solving GTSP with common ant colony optimization methods.(4) In order to enable investors to understand the macroscopic social economy factor that influences the estate market, and enable their investment ideas to tend to scientific and rational, furthermore, to grasp opportunities and directions for investment, it is the important and valuable reference with instruction significance to carry on a generalized achievements analysis for each listed company. For this reason, a PCA-SOM model is proposed in this thesis for assessing the financial performance of listed companies. Firstly, this model utilizes the principal components analysis (PCA) to establish a synthesis appraisal model of the company's finance performance, and then utilizes Self-Organizing Map (SOM) neural network to examine the effectiveness of proposed model. The principal components analysis is a multi-components statistical method that transforms many related variables into a few unrelated variables. And in order to verify the validity of obtained ranking with the principal components analysis, we must select a kind of method for clustering examination that examines the obtained company's synthesis targets with PCA. This thesis utilizes the SOM method to carry on the classified examination for the results of PCA. The most important characteristics of SOM method is to capture the inherent regulars and the essential attributes in samples automatically, changes the network parameter and in self-organize and auto-adapted way. This study has greatly extended application of the neural networks in the pattern recognition. Besides, because most practical applications are non-linear and PCA is not suitable to be used to non-linear problems, this thesis introduces the kernel function into the PCA model, which maps a low-dimension input space into a high-dimension feature space, and transforms the linear nonseparable problems (in the input space) into linear separable ones (in the feature space). Finally, this thesis selects the Gauss kernel function and the multinomial kernel function to carry on the numerical experiments, respectively. Experimental results show that the ability of feature abstraction based on the KPCA surpasses original PCA greatly, and KPCA has the capability to abstract principle components in more effective way. Hence, the KPCA is more suitable to deal with nonlinear problems.