The Research Of Optimization Hardness Based On The Optimal Contraction Theorem And Its Application

Many sorts of optimization problem are existed in the research fields of engineering development, scientific computation, macro-economy, automatic control, artificial intelligence and so on. However, according to the no free launch(NFL) theorem, the omnipotent algorithm that can perfectly solve all kinds of optimization problem does not exist. Consequently, studying the correspondence between the optimization problem and heuristics is the only way to enhance the performance of the heuristic pertinently. Besides, the family of heuristics is also growing fast, the novel strategies and algorithms are emerging endlessly, especially the heuristics with flatted structure such as meme-tic algorithm. For the framework of meme-tic algorithm can use various heuristics as local optimizer, the idea of choosing the right heuristic for the given optimization problem might be achieved. In order to achieve this best match between the heuristics and the optimization problems, an innovative knowledge system should be designed by fully understanding of the problem features. The main concern of the optimization hardness researches is the effects of the problem features to the optimizing process of the heuristics, this makes optimization hardness one of the theoretical foundations of the innovative knowledge system. Accordingly, the works in this dissertation has unique significance to the further development of the heuristics and to the optimization problems in all research fields. To the heuristics without flatted structure, such as ant colony optimization, particle swarm optimization and so on, the study of optimization hardness could be a part of their self-adapt or self-design ability. This dissertation studies optimization hardness from two aspects.First and foremost, this dissertation studies optimization hardness by analyzing the features of optimization problem. The research on the features of optimization problem is based on the optimal contraction theorem, which is a theory for describing the optimization process of heuristics and uses optimal feature factors(OFFs) as an indicator of the problem features. However, the optimal contraction theorem did not offer the method of measuring optimal feature factors. Therefore, this dissertation proposes a method of estimating OFFs, which uses a sampling sequence for estimating two indicators of OFFs. This dissertation also builds the connections between frequency features and optimization hardness of real-parameter optimization problems, and proposes effective high-frequency ratio(EHFR) on the basis of analyzing problem features. Nonetheless, although the OFFs cover the essential part of problem features, there are still some other problem features that the OFFs cannot indicate. The influence of these features to the optimization hardness is measured by using the concept of Gradient Dependency Set(GDS).Furthermore, this dissertation also studies the influence of optimization hardness to the selection of the strategies and parameters of heuristics. Therefore, it inevitably puts the heuristics with different mechanisms into the same theoretical system, the balance theory of exploration and exploitation should be one of the most suitable theoretical systems. Under the background of exploration and exploitation, this dissertation analyzes the best balance point of exploration and exploitation on both the static and dynamic optimization problems by doing orthogonal experiment, and studies the influence of problem features to the selection for the parameter of heuristics by using the theoretical optimum combination of the factors, which is a part of test results of orthogonal experiments. The dissertation also designs the optimization hardness based memetic algorithm(OHBMA) on the basis of the theoretical optimum combination of the factors, and the OHBMA is applied into multi-level image segmentation problem. Meanwhile, the EHFRs of the test images are also calculated to be the point of reference for comparative analysis.Finally, This dissertation draws conclusions on four main aspects based on the works mentioned above.(1) The EHFR is the unique optimization hardness indicator working on the frequency domain, which also presents impressive performance on precision, stability and the capacity to distinguish.(2) For the features that cannot be described by the OFFs, the deception is deeply correlated with the way of utilizing information, yet, the ruggedness does not show strong relationship with the way of utilizing information.(3) The test results of the orthogonal experiments show strong influence of the problem features to the balance point of exploration and exploitation, this influence means the one-to-one correspondence between various problems and different combinations of the intensity and time for implanting exploration in heuristics. Apparently, these combinations correspond to the strategies and parameters of the heuristics.(4) According to the test results of the OHBMA, the using of the optimization hardness related knowledge can enhance the performance of the heuristics.