Study On Generalized Chromosome Genetic Algorithm And Iterative Least Squares Support Vector Machine Regression

In this dissertation two kinds of classical algorithms in computational intelligence andmachine learning-genetic algorithm (GA) and support vector machine (SVM), and severalapplication problems are studied. The main contents and conclusions in this paper can besummarized as follows:(1) Propose the novel generalized chromosome-based genetic algorithm (GCGA), unifythe algorithm models of generalized traveling salesman problem (GTSP) and conventionaltraveling salesman problem (CTSP). GTSP can be formulated as follows: There are n citiesdistributed in m regions, these regions are not overlapped mutually, and a traveling salesmanproblem is asked to visit all of the m regions and then return to his start. The aim of GTSP isto determine the tour covering all of the m regions, but only once for each one. GTSP is akind of combinatorial optimization problems with more application fields than CTSP, whichcould provide ideal models for modern material flow design, post-box collection,stochastical vehicle routing, region delivery and municipal programming. Compared withCTSP, GTSP is more flexible and could model well the problems with hierarchical traits.Moreover, according to the generalization in this dissertation, GTSP could include thevertices grouped (the ones in a certain region) and vertices isolated (the ones not sharing anyregion with others). Hence, GTSP could include CTSP. However, the algorithm studies forGTSP is far under-studied, especially, the algorithms based on GA. This dissertationproposes a novel structure of chromosome, called generalized chromosome (GC), at first.Different from conventional chromosome, GC have two parts: head part and body part. GCstores the numbers of cities in the corresponding regions in head part, and stores thenumbers of groups in body part. The body part of GC is similar with the conventionalchromosome, which determines the visit sequence for the traveling salesman. In theencoding stage, the collaboration of the body and head parts in a GC will give thedetermined sequence information of each region and the city numbers which specifies thevisited city in its region. Because of the special structure of GC, conventional GA cannot rundirectly. Hence, this dissertation presents the full GA scheme, called generalizedchromosome-based genetic algorithm (GCGA), which mainly includes the following geneticoperators: population initialization operator P , generalized crossover operator C ,generalized mutation operator M , generalized inversion operator R and the generalizedfitness function. The proposed GCGA doesn't involve the transformation from GTSP toCTSP which is included in most current GTSP algorithms, and therefore, avoids thedimensional expansion. Theoretical analysis shows that the length of GC is not larger thanthe city number n while is used to solve standard GTSP. Benchmark problems and numericalsimulations demonstrate that the proposed GCGA could solve well the test instances and hasadvantages in optimization results and implementation speed. In addition, the proposedGCGA presents the uniform framework for GTSP and CTSP. And according to ourgeneralization, GTSP could include the hybrid of grouped vertices (called supper vertices)and isolated vertices (scattered vertices). The proposed GCGA not only could solve GTSPand CTSP, but also could solve the hybrid of GTSP and CTSP.(2) Summarize three kinds of constrained TSPs, and propose the correspondingalgorithms based on GA. The standard TSP is a kind of classical combinatorial optimizationproblems. Although it could represent a large class of real application problems, there aremany concrete applications which standard TSP appears weak to deal with because it is adeep abstract of some combinatorial optimization problems. For example, drilling is oftenneeded on large scale integrated circuit board in electronical industry, which is only requiredto finish all drilling in working time, but not required to return the drill to its start.Sometimes this problem may be constrained on the start and/or the end points of the drillroute. In these cases the aim is to determine the Hamilton path instead of Hamilton tour.Another example is the problem of material delivery, when there are most likely some citieswithout direct connecting roads, especially, just after natural disasters some roads may bedestroyed. In this case it is required to determine a shortest Hamilton tour in a non-completegraph. However, we notice that the standard TSP cann't be used to deal with the importantproblems with real application background. To attempt to overcome the difficulties, thisdissertation summarizes three kinds of constrained TSPs, including: 1) free-end TSP wherethe aim is to determine a shortest Hamilton path and the ends is not constrained, 2) fixed-endTSP where the aim is also to determine the shortest Hamilton path, but the start and/or endpoints are designated before hand, 3) non-complete graph TSP where the aim is to determinethe shortest Hamilton tour in a non-complete graph. Corresponding to these constrainedTSPs, this dissertation presents the specific algorithms for them: 1) free-end geneticalgorithm, 2) fixed-end genetic algorithm, and 3) non-complete graph genetic algorithm.These specific algorithms share the common traits that they are easy to be operated,designed under the principle to try to keep more characters of standard GA and make full useof the evolutionary rule-"The fittest, the survival". The algorithms are not integrated forcemeasures to keep the individuals feasible, but make them to be eliminated naturally in theprocess of evolution. Benefiting from these designing rules, the proposed algorithms avoidthe time consumption in regulating the infeasible individuals. Experiment resultsdemonstrate that the proposed algorithms fulfill the expected designing goal.(3) Propose two iterative learning algorithms based on least squares support vectormachine (LS-SVM), which reserve well the sparseness of support vectors and speedsdrastically up the learning process. Support vector machine (SVM) was proposed in 1995based on the statistical learning theory. Superior to most of the exsiting machine learningmodels, SVM has stronger theoretical foundation, and theoretically could resist well theoverfitting suffered by other machine learning models. SVM has been paid intensiveattentions since it was born and obtained quick development on both theory and applicationfields. However, the conventional SVM needs to solve a inequality-constrained quadraticprogramming (QP), and the exsiting QP technologies and hardware conditions could notsupport the learning of large sample problems due to the huge memory requirement or theintolerable consumption of time. Especially, the conventional SVM is not fit for real timecontrol problems. Suykens et al in 1999 converted the inequality constraints into equalityones and made the training of the SVM equivalent to solving a group of equalities. Theresulted SVM from Suykens' approach is called least squares support vector machine(LS-SVM). LS-SVM simplifies the training of SVM in a great extent and lowers thedoor-sill of SVM applications, expands the application fields. However, there is still adrawback that LS-SVM loses the sparseness of support vector which is one of the importantadvantages of conventional SVM. This deficiency deteriorates its expected implementationefficiency. This dissertation proposes two iterative learning algorithms of least squaressupport vector machine regression, including: scale-fixed iterative least squares supportvector regression (FILSSVR) and adaptive iterative least squares support vector regression(AILSSVR). Both the proposed algorithms reduce the sizes of working sets, reserve thesaparesness of support vectors in LS-SVM, and avoid the low efficiency resulted from alltraning samples' entering into working sets. FILSSVR needs a predetermined parameter N asthe size of woring set at first, and then it starts from the smallest working set with only twosamples. After its working set reaches a size of N, FILSSVR performs iterative learning withthis size-fixed working set. When a new sample comes into FILSSVR's working set, theremust be a sample (i.e., old support vector) in current working set being removed out.AILSSVR also starts from the smallest working set, but it has a mechanism to check theimportance of support vectors (samples in working set). When a new sample enters into theworking set, AILSSVR will check whether the size of working set needs to be reducedbassed on the importance of all samples in working set to realize the goal to controladaptively the size of working set. Generally, the size of working set is related to regressionprecision. The higher precision is required, the larger size of working set is reached. For allof the concerned benchmark problems, the proposed adaptive iterative algorithm determinesa quite small working set, only 0.08%~9.8% samples of the training set, yet obtains similar(even higher) regression accuracies. Moreover, it only requires 0.003%~1.485% runningtime of that consumpt by LS-SVM. Experiment results show that the proposed iterative leastsquares support vector regression algorithm could reserve well the sparseness of supportvectors, improve drastically the learning speed, determine reasonably the support vectornumber according to the gloable complexity of the learning problems and the support vectordesity according to the local characters. Furthermore, due to the ability to determineadaptively the support vector number and to learn iteratively, the proposed AILSSVR couldbe easily generalized into online learning algorithms, and after then the generalizedalgorithms would be benefit for real time control fields.(4) Discuss the equivalence between classification and regression from multipleview-points, and verify the equivalence by using experiments. Pattern classification andfunction regression are two main learning problems in machine learning fields, but there isfew literatures discussing the equivalence between them. The exsiting algorithms forclassification and regression are mainly designed, respectively, from the distinct charactersbetween them, and in lack of universality. We notice that according to statistical learningtheory (SLT) classification and regression share a common learning model. This observationinspires us that there is some kind of equivalence between classification and regression. Thisdissertation discusses the equivalence from four view-points, including: the uniformity oflearning model in SLT, the similarity of individual learning algorithms under the frameworkof LS-SVM, the feasibility of algorithm convertion from each other, and the verification ofnumerical simulations. In addition, the author presents the convertion from minimaloptimization problems of classification to that of regression, and the scheme of setting classlabels for multi-classification problems. Based on the above discussions, the author pointsout that classification and regression have common root in SLT, the differences in LS-SVMlearning algorithms results from the artificial factors, but not the inherent natures. At last theauthor points out that the application of regression algorithms to multi-classificaitonproblems could avoid the ensamble of multiple classifiers, and hence could improve theimplementation efficiency. The experiments using individual learning algorithms to solve theopponent problems support well our conclusions of equivalence between classification andregression.The results of the dissertation will contribute to the theory and application studies ongenetic algorithms and support vector machines. We believe that as two hot researchdirections, genetic algorithms and support vector machines must obtain more extensivelystudies by the virtue of their potential in machine learning fields.