Font Size: a A A

Coevolutionary Algorithms And Their Applications

Posted on:2005-06-29Degree:DoctorType:Dissertation
Country:ChinaCandidate:J LiuFull Text:PDF
GTID:1118360152471375Subject:Circuits and Systems
Abstract/Summary:PDF Full Text Request
Although evolutionary computation has been widely used in many fields, there still exist some open problems in the theories and the applications. This thesis is focused on coevolutionary computation, one important field of evolutionary computation. Systematic researches have been made along five challenging problems, classification in data mining, satisfiability problem, numerical optimization with or without constraints, multiobjective optimization, and floorplanning in VLSI. Many new algorithms and strategies are proposed for different problems, and can be summarized as follows:(1) A new algorithm, organizational coevolutionary algorithm for classification, is proposed for classification task in data mining. It is different from the available EA-based techniques mainly in that it uses a bottom-up search mechanism. The approach makes groups of examples evolved, and then rules are extracted from these groups of examples at the end of evolution. This method can avoid generating meaningless rules during the evolution process. In the experiments, first of all, its predictive accuracy is validated by 12 UCI benchmark datasets. Secondly, its scalability is tested by increasing the training data from 100 000 to 10 000 000. At last, the method is applied to two practical cases, radar target recognition and remote sensing target recognition, with satisfactory results.(2) Based on the concept of organization, a novel algorithm, organizational evolutionary algorithm for SAT problem, is proposed to deal with the satisfiability problem. It first divides a SAT problem into several sub-problems, and forms an organization by each sub-problem. When the sub-problems are solved, the method adjusts the variables in different sub-problems so that the origin problem can be solved. In the experiments, 3700 benchmark SAT problems in SATLIB are used to test the performance. All experimental results show that the method has a higher success ratio and a lower computational cost.(3) A novel algorithm is proposed to deal with both unconstrained and constrained numerical optimization problems. Its mechanism is completely different from the traditional genetic algorithm, evolutionary programming and evolution strategy. A population consists of organizations, and an organization consists of individuals.Evolutionary operations do not exert on individuals directly, but on organizations. We prove theoretically that it converges to the global optimum. In the experiments, 15 unconstrained and 13 constrained benchmark functions are used to validate its performance. In addition, its parameters are analyzed systematically.(4) A new representation for general nonslicing floorplan in VLSI, moving modal sequences, is proposed. Its correctness and complexity are analyzed theoretically. It can represent many kinds of blocks, including rectangle blocks and rectilinear blocks, and is suitable for evolutionary algorithms to solve floorplan.(5) Based on the moving modal sequences, an organizational evolutionary algorithm is proposed for floorplanning. It can solve various kinds of problems. In the experiments, high quality solutions are found for the problems with 300 hard blocks, the problems with 100 soft blocks, and the problems with 100 soft blocks and rectilinear blocks. This proves that the method is suitable for large-scale problems, and is worth for practical problems.(6) A coevolutionary algorithm is proposed for multiobjective optimization. Based on this modal, a coevolutionary multiobjective algorithm based on moving modal sequences is proposed for floorplanning. It can provide various kinds of solutions in a run, so is convenient for the users to make decisions.
Keywords/Search Tags:Evolutionary algorithm, Coevolutionary algorithm, Organization, Data mining, Classification, Radar target recognition, Remote sensing target recognition, Satisfiability problem, Numerical optimization, Unconstrained optimizatioin
PDF Full Text Request
Related items