Interactive Evolutionary Algorithms For Optimization Problems With Implicit Objectives

Optimization problems with implicit objectives refer to problems whose optimization objectives cannot be specified by explicit mathematical functions. Many practical problems can be recognized as this kind of optimization problems, such as fashion design, music composition, image processing , and so on. Optimization objectives of these problems are generally to meet some requirements of human. They are difficult to be quantified because they are usually related to human's preference, intuition, experience, values and belief. The interactive evolutionary algorithm (IEA) is an optimization method that adopts evolutionary computation (EC) among system optimization based on subjective human evaluation. As the main method for solving optimization problems with implicit objectives, it attracts more and more attentions from researchers all over the world. As a result of the participation of human, to reduce user fatigue and improve the algorithm's efficiency is a very imperative and significant topic.The research about IEA is carried out from three aspects in this dissertation, including the interaction methods in IEA, multi-user IEAs, and interactive PBIL algorithms. The main work of this dissertation includes the following aspects.(1) A novel evaluation manner based on tournament selection is proposed to reduce user fatigue. This evaluation manner can reduce user's mental burden compared with the traditional grading method, and has fewer number of evaluations than the paired comparison method. The proposed evaluation manner is performed as follows: At first, the population is divided into several sub-populations. Then the user selects relatively good individuals from each sub-population. The selected individuals are referred as winners. All winners will participate in the tournaments of the next round. The tournament will be finished when the last winner is found, and the fitness value of each individual is assigned as its height in the tournament tree. Interactive genetic algorithm based on tournament selection (TS-IGA) is applied in a dress color optimization system to study how the population size and sub-population size influence the performance of the algorithm. At last, comparison experiments are conducted using TS-IGA and IGA based on paired comparison (PC-IGA). Experimental results show that TS-IGA with proper sub-population size can effectively decrease the number of users'evaluations and the algorithm's convergence time and therefore realize user fatigue reduction.(2) We propose an active intervention operator: a sub-chromosome fixing operator. This operator can prevent the good gene segments from being destroyed by crossover and mutation operators, and can reduce the search space remarkably. Traditional crossover and mutation operators may become ineffective as a result of the proposed operator, so we improve the crossover and mutation operators to make them effective even if the proposed operator is performed. At last, two interactive genetic algorithms, one with the proposed operator and the other without, are applied to a fashion design system, respectively. Experimental results demonstrate that the sub-chromosome fixing operator can accelerate the convergence of IEC and improve the quality of solutions.(3) We propose a multi-user interactive genetic algorithm (MUIGA) that can meet the requirements of multi-people. Single user evaluation is replaced by group evaluation in MUIGA. That is to say, the individuals'fitness values lie on the decision of a group instead of a single user. The detail design of the three key modules—population initialization module, single-population module and multi-population module is given. At last, the proposed algorithm and the general single-user interactive genetic algorithm are applied to a fashion design system, respectively. Experimental results show that MUIGA can meet the requirements of multi-people better than single-user IGA.(4) An interactive population-based incremental learning (IPBIL) algorithm has been proposed to optimize problems with implicit objectives, which are traditionally solved by using interactive evolutionary computation (IEC). That is expected to reduce user fatigue, which is a key limitation of IEC, because users only need to select some good individuals rather than evaluate all individuals when using IPBIL. To compare the performance of IEC and IPBIL, they are applied to a fashion design system. Experimental results indicate that although IPBIL needs more generations to find a satisfactory design, it needs less time consumption and much fewer mouse clicks than IEC. Accordingly, compared with IEC, IPBIL can significantly reduce user fatigue.(5) To solve multimodal optimization problems with implicit objectives, we propose an algorithm—IPBIL with multiple probability vectors (IPBIL-MPV). The key idea is to utilize multiple probability vectors to catch different search directions and thus find more than one solutions. We perform a subjective experiment in which IPBIL-MPV is applied to a fashion design problem. The experimental results show that IPBIL-MPV can find several distinct solutions in a run. Thus it is an effective method to solve multimodal optimization problems with implicit objectives.