Research On Evolutionary Computation Based Approaches For Automatic Behavioral Refinement And Learning To Rank

Evolutionary Computation (EC) is a kind of intelligent computing approach which is based on the evolutionary principles and strategies in the nature. It can be used to cope with the complex problems involving optimization, forecast and so on in the engineering, technology and other fields, which cannot be managed effectively by traditional theory and approaches. Nowadays, a lot of new EC approaches have been proposed, and the original technologies leap forward with renewed energy.In recent years, classical approaches encountered great difficulties in some research issues, e.g., the automatic refinement problem in software engineering field; for some problem, classical approaches cannot gain ideal results, e.g., learning to rank in information retrieval area. These phenomenons drive us to try to think of these problems from the point of view of natural evolution.Based on the application backgrounds and requirements mentioned above, this thesis tries to employ EC principles to resolve these problems which are difficult for the classical approaches. A series of prototype tools are also developed to validate the research results. The main research contents and innovations of this thesis are listed as follows:1 The theories of modeling and refinement for behaviors in software systems are studied.According to the requirements of the automatic refinement technologies, we introduce a series of formal symbol systems to express the behavior models. In addition, based on these symbols, we propose an approach of formal modeling and a refinement theory for behaviors. We believe that our research will definitely promote the theory and application of the modeling theory integrating formal methods into UML.In Model Driven Development, behavior modeling and refinement are critical issues which take into account a series of action sematics. The problem of behavior modeling essentially involves many issues, such as (1) when should a behavior be performed? (2) How will the states of a system be transferred step by step due to the behavior? (3) What will the final state be like?Since UML has a loosely defined semantics, according to the principles of integrating formal methods into UML, we have to employ formal methods to express behaviors accurately. These formal methods are usually based on set theory and predicate logic, and can be used to provide an unambiguous and precise supplement to natural language descriptions. In addition, formal models can be stepwise refined, thus codes can be generated finally.In recent decades, a great variety of refinement theories and tools were proposed. In general, they take into consideration the definition and verification issues for whole software systems. However, as the modeling theory integrating formal methods into UML has been proposed and rapidly developed, nowadays formal models turn their attention to behavior details in software systems. Unfortunately, there has not been any refienment theories focus on behaviors yet, and traditional refinement theory seems too complicated to match this situation. Therefore, it is really an urgent matter to propose a behavior refinement theory.Guided by other refinement theories, we introduce a collection of formal symbols for expressing behavior models. We also provide an approach of formal modeling and a refinement theory for behaviors using these symbols. According to the behavior refinement theory, a refinement process can be thought of as a problem of figuring out a special state satisfying certain formulae, thus a rational refinement result can be constructed. Thus firstly we should estimate the number of the states in the state space, so as to calculate the complexity of the behavior refinement problem. The result shows that an exhaustive algorithm is impractical, thus some effective strategies should be introduced.2 An automatic approach for behavior refinement based on genetic programming is proposed.Software development tends to be modelized and automatical. Actually, lack of automatic refinement mechanisms is one of the largest barriers to use the formal methods into industries. Thus in this dissertation we propose an automatic behavior refinement approach based on Linear Genetic Programming (LGP).However, LGP has its own weakness. The prominent issue is that it cannot evolve explict loop structures and choice structures. In order to resolve these problems, we introduce a linear genetic programming algorithm based on predicate logic. In the beginning, the abstract models are refined by the bottom-up reduction refinement method according to the forms of their post-condition predicates. After the reduction stage, explict loop structures can be generated, together with a few simpler abstract models. These abstract models generated in the reduction process are refined continuously by the search refinement method based on LGP. In this phase behavior refinement can be regarded as a problem of finding out and a series of proper basic operations and coordinating them in reasonable forms. Furthermore, we provide an optimizing method for the refinement results by reducing redundant operations. Finally, we offer the Combinatorial Termination Criterion (CTC) in LGP algorithm. Based on CTC, choice structures can be evolved. As a classical example, the bubble sort algorithm is evolved successfully by our approach.Our approach provides a novel way to aotumatically refine the formal abstract models. Meanwhile, it can be recognized as a tool to support the modeling theory integrating formal methods into UML. In addition, this approach has strong universality and is suitable for evolving any complex operation composed of some basic ones.3 The ranking function discovery based on evolutionary computation is studied.The performance of a search engine is mainly evaluated by the accuracy of its ranking results. As a matter of fact, ranking problem is a central issue in the Information Retrieval (IR) field. There are mainly three types of page ranking solutions: hyperlink base approaches, content based approaches and hybrid approaches. Besides, machine learning techniques, that is, learning to rank, are becoming more widely used for the ranking problem of IR. This task has emerged as an active and growing area of researches both in information retrieval and machine learning. However, none of current approaches is ideal.Recently some Genetic Programming (GP) based ranking function discovery technologies are proposed. Meanwhile, some more excellent EC algorithms have been provided, such as swarm intelligent algorithms, immune algorithms, etc, which are regarded as some effective tools for resolving the learning to rank problem. Since there are quite substantial similarities in these EC algorithms, in this dissertation we provide a series of generic definitions, together with a common algorithm framework, for EC based learning to rank. In this way, any EC algorithm can be integrated into this framework. We believe that this work will be beneficial to the use of EC in the IR field, especially for the learning to rank problem.Furthermore, RankIP, an approach based on Immune Programming (IP) for the discovery of the effective page ranking function, is proposed. To validate RankIP, we perform experiments on LETOR 2.0 data collections provided by Microsoft Research Asia (MSRA). Results indicate that the use of RankIP leads to effective ranking functions that significantly outperform the baselines, including Ranking SVM, RankBoost, etc. we also theoretically study the dissimilarities between IP and GP. In order to validate these arguments, we carry out some experiments. The results show that under the same conditions IP gains the advantage of GP.