1 Introduction

Interactive evolutionary computation (IEC) is a method framework of systemic optimization that uses a real human’s subjective evaluation in its optimization process. There are many tasks whose performances are difficult to measure or almost impossible to be quantified by machine, but can be evaluated by human beings. In some practice problems of real-world systemic optimization, it is difficult to design a fitness function that simulates a real human’s subjective evaluation, therefore, we use a real human to replace the fitness function in order to make the problem converge to subjective evaluation of a real human.

The IEC shown in Fig. 1 can optimize such tasks by involving a human user in an IEC optimization loop. The optimization framework of IEC has three parts, an IEC algorithm (including IEC interface), a real human, and an optimized target system. Research on the three parts of IEC correspondingly gives rise to three directions of IEC studies.

  1. 1.

    IEC algorithm study for reducing user fatigue;

  2. 2.

    human psychological and physiological study using IEC, i.e., IEC for human science research; and

  3. 3.

    real-world optimization application using IEC, i.e., application-oriented research of IEC.

Fig. 1
figure 1

An optimization framework of interactive evolutionary computation (IEC), it includes an IEC algorithm (including interface), a real human, and an optimized target system in general

Full size image

The first study direction of IEC is the research on its algorithm. The main issue of IEC is the user fatigue problem when a real human gives fitness to an IEC algorithm. The objective of IEC algorithm research makes sure that IEC can be applied in real-world applications without serious user fatigue. The user fatigue problem occurs in the process of IEC optimization, when a real human needs to repeatedly give feedback to an IEC algorithm from his/her subjective evaluation. This does not occur in computer evaluation processes. This problem restricts the application of IEC optimization.

The second study direction is the human psychological and physiological research using IEC, i.e., IEC for human science research. The philosophy of this research lies in the subjective evaluation of IEC coming from a real human’s psychological and/or physiological characteristics. When an IEC algorithm converges to the real human’s characteristics in its optimization process, we can use IEC optimization data to analyse these psychological and/or physiological characteristics to obtain new and unknown knowledge or indexes. From this view, IEC can be considered as a data analysis and processing tool for human related research, especially for discovering psychological and/or physiological knowledge about humans.

The third study direction of IEC is regarding its real-world application research in practice. This research includes three aspects. One is the art innovation applications, these include computer graphics, music design, clothing design, and architectural design. Another is engineering applications, these include image and audio processing, robot control, data mining, and software design. The rest are various other IEC-based applications, these include education, games, etc. Reference (Takagi 2001) makes a summary of these IEC research projects.

Fig. 2
figure 2

IEC papers published in each year from 2000 to 2017, the rate of increase of IEC papers is about 1.10 per year. The data is retrieved from SCOPUS database in Apr. 2018

Full size image

From the later part of the 1980s until now, the research fields and application practices of IEC have been enriched and perfected. On conducting an investigation in SCOPUS database to find papers on IEC, we found that the number of IEC papers increase from 2000 to 2017 (see Fig. 2). We use the keywordsFootnote 1 to investigate the number of IEC papers, the total number of which was 1267 during 1980 to 2017. The rate of increase of IEC papers from 2000 to 2017 is about 1.10 per year, which is as the same as that of papers on evolutionary computation (EC), whose rate of increase is about 1.12 (retrieved in Apr. 2018). This indicates that IEC is a perspective study topic in the evolutionary computation research community.

This paper firstly investigates the characteristics of IEC in Sect. 2, and the humans model used in IEC algorithm research and its research issues in Sect. 3. In addition, we briefly introduce the latest research philosophies and methodologies of three research directions and aspects of IEC. Based on these introductions and summaries, we present future research issues and concrete research methods. In IEC algorithm research, improving the convergence of the IEC algorithm is one of the solutions to the user fatigue problem. Besides improving the IEC user interface, allowing the user participation in IEC search, and using machine learning to design a better human model, we emphasize and introduce the three research directions and methods in Sect. 4, Sect. 5, and Sect. 6, respectively. The first of these is the accelerating algorithm convergence of IEC, second is developing a new IEC algorithm and its optimization framework, and the third is multi-objective IEC. This is a perspective research issue and method that uses IEC to investigate psychological and/or physiological characteristics of humans in human science. We present several research works on this topic, and introduce the research philosophy, methodology, and results on IEC for human science in Sect. 7. Finally, we make a conclusion of the whole work in Sect. 8.

2 Characteristics of interactive evolutionary computation

Optimization with human’s subjective evaluation is a primary characteristic of IEC. From the optimization framework viewpoint, any EC algorithm has its IEC version when the fitness function is replaced with a real human’s evaluation. Several EC techniques are used in IEC, such as interactive genetic algorithms (IGA) (Dawkins 1986), interactive genetic programming (Sims 1991), interactive evolution strategy (Herdy 1997), human based genetic algorithm (Kosorukoff 2001), interactive particle swarm optimization (Madar et al. 2005), interactive differential evolution (IDE) (Takagi and Pallez 2009), etc. It is necessary to understand the characteristics of IEC when studying IEC algorithms and/or applying IEC to a certain application, so that the proper IEC algorithm can be correctly applied. Concretely speaking, IEC has the following characteristics.

  1. 1.

    optimization using IEC algorithm needs less individuals and less generations to obtain the optimum;

  2. 2.

    it is hard to obtain the global optimum, and the global optimal solution in IEC is not unique;

  3. 3.

    the fitness of IEC is a relative and discrete value; and

  4. 4.

    the fitness of IEC has noise.

Because IEC optimization uses a real human’s subjective evaluation, user fatigue will increase along with increasing individual number and evaluation generation times. It is necessary to design an IEC algorithm with less individuals and less generations. It is a promising research direction and solution to establish a human model using machine learning techniques, and use the relations of search variables and their fitness to replace a real human’s evaluation.

If a real human cannot distinguish the difference between two individuals, the individuals are considered the same or almost same when we conduct an IEC evaluation. This is the reason that it is hard to obtain the global optimal solution in IEC optimization, and the global optimum is not unique.

The fitness of IEC optimization is a relative value because the fitness comes from the comparisons of individuals. If the fitness in IEC optimization is an absolute and continuous value, the fitness of an individual will have a worse value in the earlier generations, and will have a better value in the later generations. Absolute and continuous fitness value of IEC reduces the selective pressure of the IEC algorithm so as to influence convergence of the IEC algorithm.

The fitness value of IEC optimization is discrete, i.e., there are five or seven discrete values as input of IEC fitness value. This evaluation method ignores the real difference of solutions, so the fitness of IEC optimization has noise. Because IEC evaluation cannot avoid noise, the IEC algorithm, which is sensitive to noise, will lead to poor evaluation performance and result. Therefore, the IEC algorithm that is sensitive to the noise should have a noise filter processing to improve its optimization capability.

3 Human model used in algorithm research of interactive evolutionary computation

3.1 Design philosophy of human model

It is very important to simulate IEC optimization in IEC algorithm research. Although the final stage of IEC research is its application to a specific, concrete problem, it is not suitable to use a real human to evaluate IEC algorithm in its research and investigation stage. When we need to multiply running results of IEC evaluation to obtain a statistical conclusion of the IEC algorithm, the real human’s evaluation is not reliable and repeatable. The human model of IEC algorithm can replace the real human to obtain reliable and repeatable evaluations. With regard to statistical tests in IEC algorithm evaluations, the Wilcoxon signed-rank test (Wilcoxon 1945) is usually used in two IEC algorithms’ comparison, and the Friedman test (Friedman 1937) and the Bonferroni-Dunn procedure (Dunn 1958) are involved in multiple IEC algorithms’ ranking and comparison.

The IEC algorithm research needs the simulation of human evaluation. These simulations are implemented by designing a human model. When we design a human model for IEC algorithm research, we need to consider the characteristics of IEC optimization, e.g., fitness being a relative and discrete value, etc. In a common EC algorithm, if we change the fitness function to that with the discrete value, it is a method for designing a human model to simulate IEC optimization. Concretely speaking, in the process of IEC optimization, we divide a continuous search range of fitness into n levels averagely to implement the relative and discrete fitness value. If IEC optimization requires an elite strategy, we can choose one of individuals, whose fitness is in the first level of fitness range.

Designing a human model for IEC algorithm research, it demands some special considerations, such as in recurrent IEC research, where the Gaussian mixture model (GMM) has been used as a human model (Pei and Takagi 2013a). The design philosophy of GMM depends on the following.

  1. 1.

    model’s fitness landscape should be simple;

  2. 2.

    model should be multi-modal;

  3. 3.

    model has a big valley structure in the whole scale; and

  4. 4.

    complexity and shape of the model should be controlled by tuning some parameters.

Fig. 3
figure 3

A three dimensional view of a Gaussian mixture model

Full size image

In a certain range of evaluation for a human user, he/she cannot distinguish the better or worse of the solutions, so the human model should be relatively simple. The user of IEC optimization will give the same evaluation to the solutions, such as image, audio, and other evaluation objects, although the design parameters (search variables) are different. Therefore, the human model should be designed as a multi-modal function. The user of IEC optimization can obtain a satisfactory solution after a few generation evaluations, so the human model should be a big valley structure in the whole range view (see Fig. 3). For different applications, the fitness landscape needs to be tuned to be adaptive to a variety of such applications, so the complexity and shape of human model should be controlled by tuning some parameters. Fig. 3 gives an example of GMM, its parameter design is in Eq. (1). Fig. 3 presents a three dimensional GMM landscape. In the common condition, the designed parameters should be controlled less than ten, the parameter search variable range (x) of this GMM is \([-5.12,5.12]\).

$$\begin{aligned} GMM(\mathbf{x})=\sum _{i=0}^k {a_i\exp ({ -\sum _{j=0}^n{\frac{(x_{ij}-\mu _{ij})^2}{2\sigma _{ij}^2}}})}. \end{aligned}$$
(1)

where

$$\begin{aligned} \mathbf {\sigma _{ij}} = \left( \begin{array}{cccccccccc} 1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5 &{}1.5\\ 2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 \\ 1 &{}1 &{}1 &{}1 &{}1 &{}1 &{}1 &{}1 &{}1 &{}1 \\ 2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 &{}2 \end{array}\right) . \end{aligned}$$
$$\begin{aligned} \mathbf {\mu _{ij}} = \left( \begin{array}{cccccccccc} -1 &{}1.5 &{}-2 &{}2.5 &{} -1 &{}1.5 &{}-2 &{}2.5 &{}-1 &{}1.5\\ 0 &{}-2 &{}3 &{}1 &{}0 &{}-2 &{}3 &{}1 &{}0 &{}-2\\ -2.5 &{} -2&{} 1.5&{} 3.5&{}-2.5 &{} -2&{} 1.5&{} 3.5&{}-2.5 &{} -2\\ -2 &{}1 &{}-1 &{}3 &{}-2 &{}1 &{}-1 &{}3 &{} -2 &{}1 \end{array}\right) . \end{aligned}$$
$$\begin{aligned} {a_i} = \left\{ \begin{array}{cccc} 3.1,&3.4,&4.1,&3.0 \end{array} \right\} . \end{aligned}$$

It is the fundamental difference between common EC and IEC that the fitness of IEC has relative and discrete characteristics. The human model of IEC can support a relative fitness value rather than an absolute value. Its implementation lies in the separation of the fitness values into n level discrete values, e.g., from one to five levels. Compared with the common EC algorithm, it needs an accurate and continuous fitness value.

3.2 Training of human model

From the systemic viewpoint of the evaluation in IEC optimization, user input is the optimized parameters (in parameter space), and the output is subjective evaluations. We can establish this input-output relation with a mathematical model so as to analyse the human model to obtain the knowledge of a certain IEC user. At the same time, we can use such human model to help the IEC algorithm search to accelerate its search convergence. There are three primary modeling methods to establish a human model for IEC algorithm research. They are the case reasoning-based human model (Machwe and Parmee 2009), neural network-based (NN) human model (Ohsaki and Takagi 1998), and fuzzy system-based human model (Kamalian et al. 2006).

3.2.1 Case Reasoning-based Human Model

In the case reasoning-based human model, it is easy to calculate the distance between designed variables in parameter space so as to obtain the differences of a new solution and searched solutions (Machwe and Parmee 2009). However, in a specific IEC-based optimization application, the influences of designed parameters are not equal. Because the relation of fitness and designed parameters is not linear, the influences of designed parameters are also different. From these designed parameter sensitive and unsensitive applications, we should distinguish these conditions. These conventional distance-based human model cannot obtain a good evaluation result. A human model, which can distinguish parameter sensitive and parameter unsensitive cases, should be considered in such applications.

3.2.2 Neuron Networks-based Human Model

Because the neural network is a universal approximator (Hornik et al. 1989), an NN-based human model can establish any relation of designed parameter and fitness using the non-linear modeling characteristic of NN (Ohsaki and Takagi 1998). The primary issue of NN-based human model lies in the training of the model. Because the IEC has the characteristics of less population size and less evaluation generations, it can only support a small number of input-output data. The trained NN by using such a small amount of data will lead to less accuracy of the human model, so that it restricts the application of the NN-based human model in IEC optimization. Therefore, only this NN-based model, which can be trained with less data sets and obtains high model accuracy, can be used in modeling the IEC human model.

3.2.3 Fuzzy System-based Human Model

Fuzzy system-based models have been widely studied since fuzzy sets, fuzzy logic and fuzzy system were found (Zadeh 1965), and it was proven as a universal approximator as well (Wang and Mendel 1992). The advantage of the fuzzy system-based human model lies in its training (Kamalian et al. 2006). Because of the off-line training characteristic of the fuzzy system-based human model, it can be trained from the first generation of IEC optimization, rather than the NN-based model, which needs more training data to a certain level of accuracy to be used in IEC optimization. Further, the NN-based human model cannot be used from the first generation of IEC optimization. These are two differences of fuzzy system-based human model and NN-based human model.

3.2.4 Training Issues of Human Model

In order to obtain enough training data for the human model, it is necessary to collect evaluation data from the IEC user in the initial generations. After obtaining such a well trained human model, we can use it in the later generations of IEC optimization to replace the real human so that the IEC with large population size and more generations can enhance the IEC search capability to a fast convergence. This is a promising research topic for further investigation. We can also establish several human models in the IEC optimization, and find the best configured model in the specific application to replace the real human for accelerating the IEC search. This is another research subject regarding the IEC human model. In addition, how to find the difference of an IEC user and established human model, and how to reduce this difference are important research issues and topics in IEC human model study.

Fig. 4
figure 4

IEC optimization with a user model

Full size image
Fig. 5
figure 5

IEC optimization with models of other persons and the user himself/herself

Full size image

3.3 Use of multiple models of past IEC users

The human model of IEC evaluation is a promising research topic both to accelerate IEC search and to relieve IEC user fatigue. However, before using an IEC human model, the model must be made using inputs/outputs data to/from the user during the IEC optimization process in some early generations. An IEC human model can help its real human user after a trained model is obtained (see Fig. 4). In the worst case, the IEC optimization may end before a human model is made.

Preparing multiple models of past IEC users in advance and using the one most similar to the current IEC user among them until his/her model is actually trained out is one of the solutions for this problem (Henmi et al. 2006). We collect several past IEC user models before we start IEC optimization. When inputs are given to an IEC user, the same input data are given to these models and their model outputs are calculated. Next, actual IEC user evaluation responses are compared to these model outputs, and one model whose outputs are the most similar to the actual user responses. This selected model is used as a temporal human model and is used to estimate user evaluation values for many individuals and the top best n individuals are given as offspring candidates in the next generation. During this temporal model’s use, the inputs/outputs to/from the actual IEC user are used to train his/her actual human model. This process is continued until the generation when his/her human model is made, and the trained human model is used to estimate his/her evaluation values since then (see Fig. 5).

4 Acceleration of search in interactive evolutionary computation

4.1 Function approximation of a fitness landscape

One of the EC acceleration methods is towards approximating a fitness landscape with a simpler shape and quickly reach towards the global area (Jin 2005). Unlike the original complex fitness landscapes, it is possible to reach to the global optimum of the approximated simple function quickly without converging to a local optimum. This approach is based on an assumption that the global optimum of the approximated function is located near that of the original fitness landscape.

4.1.1 Fitness Landscape Approximation in Original Search Space

Our first proposal was to approximate a fitness landscape with a uni-modal (single peak) function and replace the worst individual with the peak point of the approximated function as an elite individual (Ingu and Takagi 1999) (see Fig. 6). The roughest approximation of any fitness landscape would be a uni-modal function, and we can obtain its peak location analytically, i.e., without EC search, when we use a certain kind of uni-modal function. We approximated an n-dimensional (n-D) fitness landscape with an n-D quadratic function and obtained an elite individual by solving n pluralistic simultaneous equations in our experiments.

Fig. 6
figure 6

Function approximation of n-D parameter space with a uni-modal function. The apex is used for search as an elite. We can use the elite to accelerate IEC search by replacing it with the worst individual. It is a low risk and high return method

Full size image

4.1.2 Fitness Landscape Approximation in Dimensionality Reduction Search Space

Our second proposal was to simplify our first proposal and reduce its computational cost for solving simultaneous equations (Pei and Takagi 2011). Its idea is to project an n-D fitness landscape onto each parameter axis, approximate each projected one-dimensional (1-D) fitness landscape with a 1-D uni-modal function, and estimate the elite by synthesizing the peaks of n 1-D uni-modal functions instead of approximating an n-D fitness landscape with one n-D uni-modal function directly (see Fig. 7). Experimental results showed the computational cost of the second method became 1/3 - 1/2 of that of the first method while their acceleration performance are almost the same (Pei and Takagi 2013a).

Fig. 7
figure 7

1-D function approximation and its obtained elite location in an projected 1-D parameter space. We estimate the elite by synthesizing the peaks of n 1-D uni-modal functions to accelerate IEC search

Full size image

4.2 Complexity analysis of fitness landscape using Fourier transform

The novelty of the Fourier transform approach is to accelerate EC search using frequency information of a fitness landscape (Pei and Takagi 2012b). We obtain fitness values of multiple search points at even intervals in a parameter space, apply fast Fourier transform (Heideman et al. 1985) to them, and obtain the frequency with the biggest amplitude, denoting this frequency as a principal frequency. Our idea is to approximate a fitness landscape with a sine or cosine curve obtained by the principal frequency and its phase information and use the peak point of the approximated sine or cosine curve as the elite with the same method as described above (see Fig. 8). Experimental results with eight benchmark functions showed that this method is efficient in accelerating most of them (Pei and Takagi 2012a).

We also proposed a Fourier Niche method by modifying the method mentioned to discover better multiple local optima. While the Fourier approach mentioned in the above uses only one major frequency, the Fourier Niche method uses not only it but also the second, third, and other major frequency components and approximates a fitness landscape to estimate the second, third, ... local optima. Experimental results with six one dimensional and two dimensional benchmark functions showed that this method was efficient in finding local optima and accelerating most of them.

Fig. 8
figure 8

Obtaining frequency information by applying fast Fourier analysis and using an elite from a trigonometric function (\(\sin (x)\) or \(\cos (x)\)) to accelerate IEC search

Full size image

4.3 Interactive differential evolution with (gravity + moving) vector

IEC user fatigue is a serious issue for practice of IEC applications as we described. However, many accelerating methods for differential evolution (DE) proposed so far are not always applicable to interactive differential evolution (IDE) (Takagi and Pallez 2009). Since IEC users cannot continue to evaluate IEC tasks for a long time, only methods which have acceleration effects that appear in early search generations with smaller population size without increasing additional human evaluations can be used for IEC. Our development of IEC acceleration methods must satisfy these restrictions.

IEC can reach towards the global optimum area even when searching with a small population size in a few generations. This means that fitness landscapes of IEC tasks are simple. As the DE/best approach works better than the DE/rand approach for a simple fitness landscape in general (Storn and Price 1997), we want to use the IDE/best to make IDE converge quickly. However, an IDE user must compare all individuals to find the best individual when he/she uses IDE/best, and it loses the good feature of DE, a paired comparison nature, and increases IDE user fatigue.

We proposed the DE/gravity approach that uses the center of population gravity as a base vector (Funaki and Takagi 2011). It does not increase the number of user evaluations, but its performance is close to the DE/best approach. We also proposed to use moving vector information from parent individuals to their offspring. The good news is that these two methods work complementary. When the global optimum locates around a center point in a parameter space, the DE/best works well but moving vectors cancel each other and their average moving vector works ineffectively. On the other hand, when the global optimum locates around the edge of a search space, the average moving vector works well, while DE/gravity does not work well. Simulation results showed that the convergence speed of the (IDE/gravity + moving vector) is faster than the IDE/rand and close to the IDE/best thanks to their complementary effect without increasing the numbers of human evaluations.

4.4 Triple or quadruple comparisons-based interactive differential evolution

We proposed a triple or quadruple comparisons-based mechanism to enhance differential evolution (DE), especially IDE, without increasing IDE user’s fatigue to a large extent (Pei and Takagi 2013b). Not only a target vector and a trial vector of canonical DE but also their opposite vector(s) generated by opposition-based learning (Tizhoosh 2005) are compared, and the best vector among them becomes an offspring in the next generation.

The biggest feature of the paired comparison-based IDE is “less user fatigue”, and the triple or quadruple comparisons-based IDE weaken this feature. However, there are many IEC tasks that are shown to an IEC user time-sequentially but we can memorize/recall three or four task outputs easily (Miller 1956). These kinds of tasks do not increase IDE user fatigue seriously unlike interactive genetic algorithms (IGA) (Dawkins 1986). If the increased number of human comparisons in each generation results in the acceleration of IDE convergence and decreases the total number of user evaluations, it may be better than canonical IDE.

We evaluated the proposed method by comparing it with canonical IDE and conventional opposition-based IDE using a Gaussian mixture model for simulating IDE. We also compare them using 24 benchmark functions for evaluating DE. The experiments showed that our proposed methods could enhance IDE and DE search efficiently from several evaluation indexes including the converged fitness values at the same generation numbers and the same number of fitness calculations, fitness calculation cost, success rates of convergence, and acceleration rates (Pei and Takagi 2013b).

4.5 Triple comparisons-based interactive differential evolution with memetic search

Another implementation of multiple comparison-based IDE algorithm uses memetic search to construct its optimization framework (Pei and Takagi 2017). In conventional IDE, the comparison of target vector and trial vector supports a local fitness landscape where is the promising search area in parameter space. If the fitness of target vector is better than that of the trial vector, we can apply a memetic search around the target to obtain a third vector, and vice versa. We compare the target vector, trial vector, and the third vector to implement another form of triple comparison-based IDE. The evaluation results presented a better optimization capability comparing with conventional IDE.

4.6 Prediction of an estimated convergence point

IEC is a stochastic optimization algorithm. From the fundamental point of view, it can be explained by the probability theory. If we embed a deterministic search method in IEC or EC algorithms, its optimization should be enhanced. A moving vector from the last generation to current generation supports fitness landscape information where the global optimum is located. If we use such information to estimate the convergence point, IEC and EC searches should be enhanced.

$$\begin{aligned} \hat{\mathbf{x }}= & {} \left( \sum _{i=1}^{n}H_{i}\right) ^{-1} \left( \sum _{i=1}^{n}H_{i}{} \mathbf a _{i}\right) . \nonumber \\= & {} \left\{ \sum _{i=1}^{n}\left( I_{d}-\mathbf b _{0i}{} \mathbf b _{0i}^\mathbf{T }\right) \right\} ^{-1} \left\{ \sum _{i=1}^{n}\left( I_{d} -\mathbf b _{0i}{} \mathbf b _{0i}^\mathbf{T }\right) \mathbf a _{i} \right\} . \end{aligned}$$
(2)

We introduce a method to estimate a convergence point analytically to accelerate an IEC or EC search (Murata et al. 2015). When we search a d-dimensional parameter space using one of the IEC or EC algorithms with n individuals, let the i-th parent individual, its offspring individual, and moving vector be \(\mathbf a _{i}\), \(\mathbf c _{i}\), \(\mathbf b _{i} = \mathbf c _{i} - \mathbf a _{i}\), respectively; \(\{(\mathbf a _{i},\mathbf c _{i}),\;i=1,2,...,n;\; \mathbf a _{i},\mathbf c _{i}\in \mathbf R ^{d}\}\) (see Fig. 9). The unit directional vector of \(\mathbf b _{i}\) is also defined as \(\mathbf b _{0i}=\mathbf b _{i}/\Vert \mathbf b _{i}\Vert \quad (\mathbf b _{0i}^{\mathrm {T}}{} \mathbf b _{0i} = 1)\). In Fig. 9, when we refer to a vector we mean a column vector. Given n vectors, \(\mathbf b _{i}\), that extend from n vectors, \(\mathbf a _{i}\), let \(\mathbf x \in \mathbf R ^{d}\) be the point that is nearest to the lines made by extending the line segments \(\mathbf b _{i}\) (\(\mathbf x\) is indicated by the \(\star\) mark in Fig. 9.). Eq. (2) shows how to estimate \(\mathbf x\), where \(\mathrm {I}_{d}\) is an identity matrix, and \(H_{i}= \mathbf {b}_{0i}\mathbf {b}_{0i}^{\mathrm {T}}-\mathrm {I}_{d}\). We can use this elite point to accelerate EC and IEC search (Yu et al. 2016), and perspectively it can be extended into multi-modal (Yu and Takagi 2015) and multi-objective optimization tasks.

Fig. 9
figure 9

The convergence point (\(\star\)) estimated by the moving vectors between individuals (\(\mathbf a _{i}\), \(i=1,2,...,n\)) in the d-dimensional parameter space in the k-th generation and those (\(\mathbf c _{i}\), \(i=1,2,...,n\)) in the (\(k+1\))-th generation. We can use this estimated point as an elite individual to accelerate EC or IEC search. This method also can be extended into multi-modal and multi-objective optimization tasks

Full size image

5 New algorithm framework of interactive evolutionary computation

5.1 Paired comparison-based interactive differential evolution

It is hard for an IGA user to evaluate tasks displayed time-sequentially, such as sounds or movies, because he or she cannot compare them at once and must compare them in his/her memory, which increase human fatigues. IGA is not suitable for tasks for which individuals cannot be given to an IGA user at once.

Tournament GA is one of its solutions, and a tournament IGA user chooses a better individual or gives fitness to paired individuals (Miller et al. 1995). Although pair-based comparisons can reduce IGA user’s fatigue, the tournament method does not compare whole individuals, and therefore fitness values must include noise, which reduces their search capability.

We pointed out that DE includes paired comparison in its algorithm and is suitable for IEC, and we proposed the paired comparison-based IDE (Takagi and Pallez 2009). The final stage of DE operation is the comparison of the target vector and a trial vector, and the better one becomes an offspring individual in the next generation. The IDE user compares pairs of sounds, movies, and other tasks without any modification of the DE algorithm unlike the tournament IGA.

Fig. 10
figure 10

Graphical user interfaces of a IGA and b IDE. The IGA user compares all individuals simultaneously and gives a relative evaluation value to each of them. The IDE user compares a pair of individuals and chooses the better one

Full size image

Graphical user interfaces of IGA and IDE are shown in Fig. 10. The IGA user compares all individuals and gives a relative evaluation value to each of them. When the tasks are sounds or movies, it is hard for IGA user to memorize them and evaluate them. The IDE user compares a pair of individuals and chooses the better one. It is not hard to compare two individuals even if they are sounds or movies. We confirmed that the IDE converges faster than IGA through simulation experiments (Takagi and Pallez 2009) and are evaluating user fatigue through human subjective test.

5.2 Interactive particle swarm optimization

Particle swarm optimization (PSO) is a meta-heuristic population-based algorithm inspired from the particle behaviour of animals (Eberhart and Kennedy 1995). The primary mechanism of it optimization follows the principle of evolution using the search positions of the particle itself, the best local particle, and the best global particle.

From the current comparison study of PSO, the optimization performance of PSO is better than that of genetic algorithm (GA) for these problems with the simple fitness landscape, and on the contrary, GA is better than PSO for these problems with complex fitness landscape. Interactive PSO can converge due to simple landscape of human evaluation space, when the interactive PSO algorithm has less generations and less population size. So the framework of PSO can be used in interactive application. However, when the interactive problem has evaluation noise, the interactive PSO is worse than IGA (Nakano and Takagi 2009). How to reduce noise from the human subjective evaluation, it is a promising research subject for further investigation in interactive PSO.

5.3 Interactive fireworks algorithm

The fireworks algorithm is an optimization algorithm that simulates the fireworks explosion phenomenon in parameter search space (Tan and Zhu 2010). In its algorithm framework, the search range and the number of generated offspring are decided dynamically by considering global exploration and local exploitation. We have studied approximation sampling issues of firework algorithms, and found it only needs a few of individuals in its optimization process (Pei et al. 2012). Because there are smaller population sizes (usually less than ten individuals) in the fireworks algorithm, it should be a great search algorithm in the IEC framework. The development of interactive fireworks algorithm and application of this algorithm is also a potential research subject for further study.

5.4 Interactive chaotic evolution

Determinism, probability, and chaos are three fundamental philosophies and methodologies in scientific research (Pei 2015). In the optimization field, determinative and stochastic optimization algorithms are well studied with theoretical supports from determinism and probability. However, there is little research that mentions chaotic optimization supported by chaos theory. Chaotic evolution is a new type of evolutionary computation algorithm that fuses the ergodicity of chaos and the iteration of evaluation (Pei 2014). It should be one of implementations of the chaotic optimization method.

The primary operation of chaotic evolution simulates chaotic motion in a parameter space when chaos occurs in the system. Because there is a paired-comparison mechanism in its optimization framework, and its convergent speed is better than DE, interactive chaotic evolution should be better than IDE, however, it also needs experimental evaluation to verify this hypothesis. Developing the interactive chaotic evolution algorithm, multi-modal chaotic evolution algorithm, and multi-objective chaotic evolution algorithm (Pei and Hao 2017) are three promising research subjects in chaotic evolution.

6 Multi-objective interactive evolutionary computation

The new framework of IEC research is the combination of IEC with evolutionary multi-objective optimization (EMO). Since EMO algorithms handle solutions in an objective space, the coordinates of the solutions must be specified by numerical objective values. However, there are multi-objective tasks with objects that are not clearly specified numerically. For example, let’s consider apartment search. EMO is applicable to finding less expensive and wider apartments located near a train station as these three objects have numerical values. However, it does not work for finding apartments with object(s) that have to be evaluated subjectively, e.g., “greater view from a room window”. The framework of IEC+EMO is developed for EMO tasks with objects that are evaluated not only objectively but also subjectively.

6.1 Micro-electro-mechanical system design

Micro-Electro-Mechanical Systems (MEMS) have been designed manually by using a computer-aided design system. To automate this design, EMO was applied together with an MEMS simulation tool calculating fitness values (Zhou et al. 2002). However, it is not easy to automate the design completely. One of the reasons is that we cannot describe all design knowledge into the system, and optimization parameters in MEMS design do not cover all design aspects influencing MEMS performance.

IEC can overcome this problem and increase the performance of MEMS design by cooperating with designers’ subjective evaluations. MEMS design experts can evaluate how designed MEMSs are good by just glancing at whole designs based on their experience and knowledge.

We compared the EMO+IEC-based approach and EMO-only approach by applying it to designing an MEMS resonator. The objectives of EMO are MEMS area size, a resonant frequency, and stiffness, and IEC users evaluated designed MEMS circuits visually. Sign test result showed that the evaluations of the EMO+IEC-based approach was significantly higher than that of the EMO-only approach (Kamalian et al. 2004).

6.2 Architectural room floor planning

Room floor planning includes multi-restrictions and multi-objectives such as room sizes, room shapes, moving line to any room without passing through other private rooms, and window sizes requested by architectural laws. Architects design floor layouts taking account of these points. If there is an automated room floor planning support system, architects can save their design time, and house owners can enjoy designing their houses before asking professional architects. This support system should be based on EMO to find solutions taking account of the above objectives. However, this task has further object; this is the satisfaction of architects or house owners with regard to the design plans. The EMO algorithm cannot handle qualitative objectives, and EMO+IEC is necessary for the support system. We developed an algorithm for generating room floor layouts (Inoue and Takagi 2008), combined it with EMO and IEC, and evaluated the designed layouts (Inoue and Takagi 2009). A professional architect used the system and discovered a new type of room layout that he usually does not consider in his manual designing. His evaluation was that the system is useful as an inspiration-assist system.

7 Psychological and physiological research using interactive evolutionary computation

7.1 Measuring perceived emotional expression

We applied IEC to measure a happy–sad range in the human mind and compared the ranges of schizophrenics and mentally healthy people. Some therapists feel that the emotional impressions shown on the faces of schizophrenic patients are fewer than those of mentally healthy people based on their experience. However, there was no way to measure this range. We asked three schizophrenics and five mentally healthy students to design 3-D computer graphics lighting of the happy impression and the sad impression using our IEC-based 3-D computer graphic lighting design support system (Aoki and Takagi 1997), and asked 33 human subjects to evaluate 28 pairs (=\(_{(3+5)}\mathrm{C}_2\)) of designed lighting images.

Fig. 11 is the psychological scale of happy constructed using the Scheffé’s method of paired comparison. The happy–sad ranges obtained from the experimental results imply that it is hard for schizophrenic patients to identify especially a happy impression in lighting, and it is expected that this IEC approach may provide new data that are helpful for psychiatric diagnostics (Takagi et al. 2004).

Fig. 11
figure 11

Psychological scale constructed using the Scheffé’s method of paired comparison and impression levels of the eight best lightings designed by three schizophrenics (PK, PT, and PM) and five mental healthy students (NH, NY, NK, NN, and ND). The bigger measure values, the higher evaluation of happy

Full size image

7.2 Hearing-aid fitting and discovering unknown knowledge

IEC is the best way to carry out hearing-aid fitting because sound qualities for a certain hearing-aid users cannot be measured. Another advantage is that it allows us to fit a hearing aid using any daily-life sounds, while the conventional fitting method has to use only pure tones and narrow band noise. Thanks to this feature, we could find several unknown facts (Takagi and Ohsaki 2007). They are:

  1. 1.

    the characteristics of hearing aids optimized using speech sounds that were different from those optimized using pure tones or band pass noise;

  2. 2.

    those optimized using speech sounds of speaker i with/without noise were almost similar (\(i=1, 2, ...\)); and

  3. 3.

    those optimized using speech sounds were different from those optimized using music.

Nobody had recognized the fact that the best characteristics of hearing aids depend on the kinds of sounds used for fitting. This implies that an audible range in human sense level is not the final cue for the best hearing. We could make these observations thanks to the IEC technique.

7.3 Cochlea implant fitting and discovering unknown knowledge

Cochlea-implant fitting is a similar task to a hearing-aid fitting and has been conducted based on two hypotheses for better fitting: (1) the more electric channels of a cochlea-implant, the better and (2) the wider dynamic range of each channel, the better. As frequency resolution increase according to the number of electric channels, the hypothesis (1) means that higher frequency resolution helps to distinguish the difference of frequency characteristics of phonemes; this hypothesis sounds natural. The hypothesis (2) means that enabling a user to hear sounds from the minimum level to the maximum comfortable level is helpful to distinguish sounds; this hypothesis also sounds natural.

IGA was used to tune the fitting parameters of cochlea implants (Legrand et al. 2007). Their experimental result was that the dynamic ranges of all 15 channels were almost 0 except for three or four channels, and the dynamic ranges of the exceptional three or four channels are narrower than the maximum ranges (see Fig. 12). Nevertheless, its recognition rate with IGA fitting was higher than that of manual fitting. This result did not match the two hypotheses mentioned. This implies that there must be unknown audio-psychophysiological facts. It is a valuable subject to discover these unknown facts using IEC techniques. We will continue researching this subject in the future.

Fig. 12
figure 12

Fitting characteristics of conventional cochlear implant fitting and that using IEC. Horizontal axis means electric channels and a vertical axis means electric voltage of each channel. This figure was remade based on an image in (Legrand et al. 2007)

Full size image

7.4 Interactive evolutionary computation framework using physiological measurement

The fitness of a conventional IEC algorithm comes from the subjective evaluation of humans, and these evaluations are representations of human’s physiological space. IEC framework using physiological measurement is an extension of conventional IEC. There are further potential research directions for IEC framework using physiological measurement. The first direction uses physiological measurement as the IEC fitness function to tune the human’s physiological condition to a certain level. We can use this framework to influence and study human’s physiological condition. The fitness of IEC framework using physiological measurement can use blood pressure, frequency of heart beat, frequency of respiration, etc as the physiological measurement. Reference (Takagi et al. 2005) proposed an extension framework of IEC using physiological measurement, and conducted the experimental study using a simulated physiological signal. Fig. 13 presents an extension IEC framework.

Fig. 13
figure 13

Framework of extended IEC. IEC optimizes physical features of movies or music using a fitness value that is the difference between the target physiological responses and real one of an IEC user

Full size image

The second new type of IEC research is adapting physiological data. Usually, IEC optimizes a target system based on an IEC user’s subjective evaluation, i.e., psychological evaluation. We may extend the evaluation from a psychological one to a physiological one. When the outputs of an IEC target system are given to an IEC user, such as listening to music, watching movies, or enjoying vibrations, some physical stimuli influence his/her physiology. Then, we may be able to drive his/her physiology by controlling the physical stimuli. Suppose that physiologists advise us on the ideal physiological conditions for relaxation, excitement, or other target mental conditions. IEC framework may be able to direct the human physiological conditions to the ideal by minimizing the error between measured physiological data and this ideal. Trials have been held in applying the extended IEC to control eight parameters of a vibration chair using physiological data of an extended IEC user on the chair and to direct emotions of video movie viewers (Takagi 2007) though they have not been completed. Another trial using physiological data is to guess IEC fitness by using the eye-tracking of an IEC user (Pallez et al. 2007). Other physiological data such as electroencephalogram can be used to guess IEC user’s evaluation for the selection of better individuals.

7.5 Aesthetic selection analysis using subjective evaluation from interactive evolutionary computation

The machine learning algorithm attempts to find knowledge from data, and most machine learning research uses deterministic data analysis techniques to achieve this objective. There is some research that tries to apply human related computing techniques for assisting machine learning algorithms to discover the aesthetic selection of humans.

Reference (Pei 2017) presents a work that uses IEC to select principal components of compressed images and tries to find human visual perception knowledge from human’s subjective evaluation. The work compresses an image using principal component analysis (Pearson 1901), and in the process of resorting the image, pared comparison-based IDE algorithm is applied to display to the IEC user two restored images for judging which one is the clearer one. The selection results indicate that:

  1. 1.

    Human’s subjective selection can obtain more detailed information from the visual perception;

  2. 2.

    Humans can perceive more detailed visual information that is presented by the principal components with the small eigenvalues;

  3. 3.

    Subjects’ aesthetic characteristics can be obtained by analyzing the data of principal components; and

  4. 4.

    Human visual perception is sensitive to the shape and frame information from images’ comparisons.

This work is an attempt to apply IEC techniques in machine learning algorithms to find the aesthetic characteristics of humans. Although some of the conclusions and analysis results need to be seriously verified by psychological and physiological fundamentals of human, hopefully, there will be an opportunity to apply IEC in such human related knowledge discovery.

7.6 Awareness computing using interactive evolutionary computation

IEC can be used as a tool to analyse human’s psychological and physiological characteristics. In awareness computing, IEC can also be used to analyse human’s awareness mechanism (Takagi 2012). Much research has different definitions on awareness computing from a variety of viewpoints. Although there are many studies on awareness computing, there is a need to further deepen the research on the human awareness mechanism, and establish the fundamentals of awareness computing.

Reference (Takagi 2012) defines awareness computing as follows. Awareness computing is a process that helps us to understand unknown or potential facts and concepts. This can use IEC to achieve such an objective. For example, when we evaluate a student with a mathematic credit, literature credit, and physics credit, and with his/her height, and weight, we can determine academic capability and physical condition, these two concepts, from this data. The process of obtaining these two concepts is a process of awareness computing, and these two concepts are the definitions of awareness of this process.

Fig. 14
figure 14

Finding out latent variables inside the human model in awareness computing. Variables (x, z, y) present input, output, and potential concepts, respectively. We can establish an evaluation model \(z=f(x)\), and awareness computing separates f(x) into \(y_1=g_1(x), y_1=g_1(x), ...\) to find \(y_i, i=1, 2, ...\) that presents the potential concepts

Full size image

The model of awareness uses human’s input as the model’s input, and output after a human recognizes it as the model’s output. The model helps us to find relations between this input and output. We can use input and output of IEC optimization to establish a model using machine learning methods, and then, separate this model into two parts to find the potential factors and concepts. It is a method to establish awareness model and implement awareness computing. For example, variables (x, z, y) present input, output, and potential concepts, respectively. We can establish an evaluation model \(z=f(x)\), and awareness computing separates f(x) into \(y_1=g_1(x), y_1=g_1(x), ...\) to find \(y_i, i=1, 2, ...\) that presents the potential concepts (see Fig. 14). The primary issues of this process try to find effective methods to separate the model. Principal component analysis (Pearson 1901), factor analysis (Spearman 1904), and non-negative matrix factorization (Lee and Seung 1999), these feature selection methods, can be applied in model separation for implementing awareness computing. This is a promising research issue and topic in awareness computing with IEC.

8 Conclusion

IEC was born when Richard Dawkins showed that complex figures could be generated based on visual evaluation, and showed evolved 2-D line figures (biomorph) as is seen in examples in his book (Dawkins 1986). Since the 1990’s, IEC application areas have spread from computer graphic applications to engineering, entertainment, and many other areas. We did not mention this major IEC research in this paper but explained our research on accelerating IEC and developing new IEC frameworks on the second research direction. Almost all IEC research works are categorized into either of these research directions.

As a new feature, we introduced our research, IEC for human science, as the third direction of IEC research. Artificial intelligence (AI) has become a hot keyword not only in computer science, but also in common scientific research. IEC can act as an interface for the design of a system that is more friendly between human and human, human and computer, human and machine, human and robot pet, etc. It also can be an effective AI tool in human-centered computing, such as home-assisted robot design and pet robot design, to contribute to an aging society in some countries. The analysis and understanding of human characteristics is an important issue to implement these designs, and IEC is also a great tool to contribute to this field. We hope that many people realize that the capability of IEC is not only optimization from these efforts and IEC can make a much wider contribution.