Research On User-system Cooperative Evolutionary Algorithm

In the present word, there are a lot of application problems which can be resolved as optimization problems. Evolution computing is always one of the effective meth-ods of solving the optimization problems. For the optimization problems with explicit objectives, evolutionary algorithms show great advantages on resolving these problem-s, because they have no requests for the continuity, differentiability and convexity of objective function. However, for the optimization problems with implicit objectives, traditional evolutionary algorithms seem to be unable to solve them. In fact, many practical problems can be recognized as optimization problems with implicit objectives, such as art design, CAD design, image retrieval and so on. The optimization objec-tives of all these problems depend on the user's subjective factors, such as knowledge of art, preference, experience, intuition etc. These indices cannot be easily quantified and are nearly impossible to be expressed as mathematical functions which can be used as optimization objectives. Interactive Evolutionary Algorithm (IEA) is the main way of solving the optimization problems with implicit objectives, so it attracts increasing attentions from domestic and foreign scholars. However, for the narrow definition of IEA, users only play the role of fitness function, the potential of user intervention can-not be effectively released. But for the IEA with broad definition, which means users play more roles in the process of EAs, it gets more attention recently. How to integrate more user's interventions into IEA, to improve the algorithm's efficiency and to reduce user fatigue greatly is a meaningful research topic.The dissertation defines the broad IEA and relevant technology as "User-system Cooperative Evolutionary Computation (USCEC)". USCEC framework is created based on Differential Evolution Algorithm (DEA), user's intervention can be manifested on three levels:population, individual and genes. USCEC discards the interactive way of providing fitness value. It uses the interactive ways based on the pairwise comparison selection and gene editing, meanwhile it uses many working modes which can switch freely, so that it can take maximum advantage of the algorithm and human. The main work of this dissertation is as follows:(1) Two methods which can be used to reduce the number of editable features are proposed in this dissertation. They are based on interval entropy and recognizable factors respectively. As to the method based on interval entropy, the distribution of features in satisfactory solutions are mainly analyzed, but as to the method based on recognizable factors, both satisfactory solutions and dis-satisfactory solutions need to be analyzed at the same time. The results of experiment show that the method based on recognizable factors have better effects than the method based on interval entropy under the high dimensional feature vector. It can improve the efficiency of algorithm as well as reduce the number of the editable features, that can reduce the user fatigue.(2) The dissertation proposed a local search method based on SVM to get the decision hyperplane which can classify the satisfactory solution and the dis-satisfactory solution. The position of hyperplane can be adjusted constantly based on the evaluation of the accumulated samples. Individuals which are farthest from the hyperplane in satisfactory candidate solutions can be chosen as elites to replace the bad solutions. The results of experiment show that the method can reduce the number of gene editing. In other words, the evaluation of solutions is used to replace the edition of solutions, which can alleviate the user fatigue during the editing behavior.(3) The dissertation proposed an opposite-learning method based on lens imaging principle. An opposite solution window is added to the interaction interface of evalu-ation, which can provide a chance for each individual to be close to the best solution. This method introduced two parameters-search radius and scale factor, which realizes the balance between search breadth and search depth, it can be considered as a contest between current population and opposite population with the help of user. The experi-ment shows that the method can accelerate the convergence of the algorithms and find the satisfactory solution in fewer iteration times.(4) In order to alleviate user fatigue, the dissertation proposed a surrogate model which can replace the evaluation from user. Because of the pair-compared evaluation in USCEC, the model can be designed as a comparator. A directed graph was used to show the preference information from user evaluation and a classifier was built based on Extreme Learning Machine (ELM), and an improved Particle Swarm Optimization (PSO) was used to optimize the parameters in ELM. The results of experiment show that relative to the surrogate model based on BPNN, the method in this dissertation can get better accuracy, and gain more samples for training models in fewer iteration times through the combination with opposite-based learning strategy.The above researches are successfully applied in cartoon face design systems and content-based image retrieval and the results show that it provides a new interactive way for IEC, enlarging the application of human intervention in the fields of IEC, improving the efficiency of IEA, meanwhile alleviating the user fatigue, which provides guarantees for applying the algorithms to more complicated problems.