Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Evolutionary interactive Web-based applications are applications that are supported by interactive evolutionary computation (IEC). IEC is a branch of evolutionary computing where users are part of the evolutionary process by replacing the fitness function. In these applications the users typically evaluate individuals in a population by using their personal preferences [1]. This evaluation is subjective because the user uses his own perception of the environment, using his senses, interests, etc., in order to evaluate. Usually in these applications users lose interest in using them. This may be due to different causes. For example having a very specialized user interface, evaluating large amounts of individuals, where these individuals do not attract the attention of users. This takes the user to the point of boredom, which is known as the fatigue problem [1] in interactive evolutionary computation and consequently the users lose interest in participating. One way to attract the user’s interest is presenting individuals that cause an impact in relation to their senses, likes, interests, etc. The question is how to produce such individuals in the population? We know that the user participates in the evolutionary process by replacing the fitness function. Then we could design a fitness function expression that takes all the elements that the user performs in order to evaluate individuals. Thus the evolutionary interactive algorithm will produce individuals that attract the user interest in some degree.

There are some works that use the strategy of designing fitness expressions. For example Ohsaki et al. [2] in 1998, developed a method using discrete fitness value in order to reduce the psychological stress that is generated in the process of evaluating individuals.

Yuan and Gong [3] suggest an interactive evolutionary algorithm that divides the population into several clusters. The way they assigns the fitness to the individuals is by the evaluation the user performs only for central individual in each cluster, the others are estimated based on this evaluation.

Gong and Yuan [4] and Gong et al. [5] also propose to adopt a fuzzy number to express the fitness function of the individual to reflect the user cognition and use a stochastic variable with a normal distribution to represent the stochastic behavior in the fitness based on the error theory.

Our approach is focuses on using a fuzzy system [6] based on rules to infer a value that is obtained based on the preference rate that the user has on an individual as well as the level of experience that a user acquires when is using the application. Ones we have the defuzzified value from the fuzzy system, we proceed to assign to our fitness expression, which we will explain in detail in Sect. 3. The application we use to test the our fitness function expression, is developed on the EvoSpace_I framework [7]. This application is inspired on digital art which creates animations from squares, circles, lines, colors, overlaps, backgrounds, etc. The animations represent individuals in the population. This paper is organized as follows: In Sect. 2 we present the related work, in Sect. 3 we present our strategy of fitness function expression using fuzzy logic, in Sect. 4 we present our experimental results, and finally in Sect. 5 we present our conclusions.

2 Related Work

In this section we presented the work related to different approaches to evaluate fitness function and the Evospace-interactive framework.

2.1 Approaches to Evaluate Fitness Function

In 1998, a new input method for human operators of an interactive genetic algorithm to reduce the psychological weight is proposed. This method uses a discrete fitness values to reduce the psychological stress involved in the input procedure. They perform simulations to investigate the influence of the resulting quantization noise from the use of discrete values of fitness in convergence. Showing that the quantization noise does not significantly worsen the convergence. In this method they evaluated using two subjective tests involving the task of drawing faces. The subjective test results shows that this method significantly reduce the level of psychological stress of human interactive genetic algorithms operators [2]. Another approach, proposed to use novel method evaluation, where the user only evaluates a satisfactory or unsatisfactory individual. These approaches consider the level of sensibility of the different users to their perception of the beautiful and the ugly, and fitness is automatically calculated based on user evaluations and time. They also propose effective strategies for comparing different individuals of the same generation in uncertain fitness conditions of an individual. Where they obtains the probability of an individual dominance by use of the probability of the interval domain, and translate to a fuzzy number in a range based on α-cut set [4]. They determine the dominant individual in tournament selection with size being two on base given by the probability of a particular domain. This approach was applied to an interactive evolutionary system for fashion design. In Fig. 1 we can see different user interfaces they used. Based on this approach, another work was derived. Where the approach adopt a fuzzy number described with a Gaussian membership function to express an individual’s fitness. In order to compare the different individuals, they generated a fitness interval based on a cut set, and obtain the probability of interactive genetic algorithms with individual’s fuzzy fitness. The contributions in this approach can improve the performance of existing income generating activities in alleviating user fatigue and finding optimal solutions to an optimization problem, so it is beneficial for solving complicated problems with implicit or fuzzy indices [5].

Fig. 1
figure 1

Different user interfaces interactive evolutionary system for fashion design [5]

Full size image

2.2 EvoSpace-I

EvoSpace-Interactive is an open source framework focused on Web environments for collaborative interactive evolutionary applications. This framework defines three main components for each application, which are:

  • Individual.

  • Processing Script.

  • Worker Script.

The individual is represented internally as a data dictionary stored in Redis [6]; the individual contains three main attributes: id, chromosome, mom, dad, and views. This attributes represents the key information of the individual as the individual offspring, the number of times that the individual has been selected, etcetera, as we can see in Fig. 2.

Fig. 2
figure 2

Individual representation [7]

Full size image

As we can observe on Fig. 3, this work uses database management systems to implement collaborative interactive evolutionary applications. One of the reasons that this framework is using Redis [6] is because it provides a hash-based implementation of sets and queues, which are natural data structures for the EvoSpace model [8]. On the other hand this framework uses a relational database to save basic information about the user extracted from the social platform (Facebook) through open graph API and OAuth2 authentication.

Fig. 3
figure 3

EvoSpace-I framework [7]

Full size image

3 Fitness Estimation Strategies for Web Based Interactive Evolutionary Applications Considering User Preferences and Activities Using Fuzzy Logic

This section explains the proposed strategy to calculate the fitness of the individual in a web-based interactive evolutionary computation applications using fuzzy logic. Before showing our strategy, it is necessary to explain how the individual evaluation is made in the shapes animation application. The Fig. 4 shows the user interface where the user interacts with the application. The main goal of this interaction is the individuals evaluation, the first action of the user, in order to evaluate, is to login through a Facebook [9] account in order to have different futures as a collection creation, store individual in a collection, etc. The evaluation takes place through a five-star rate selection by the user; this rate represents the degree of user preference for an individual. The application keeps the record of every user activity using the activities stream standard [10]. In these particular case the activities represents the user experience.

Fig. 4
figure 4

Shapes animation application user interface

Full size image

In this paper we propose the using of fuzzy logic [6] in order to obtain a defuzzify value to be used to calculate the individual fitness trough a fitness function expression. It is used by modeling a fuzzy Mamdani type inference system [11, 12] as we can see in Fig. 5. This model was designed empirically. The model consists of two input variables, which are the preference and the experience of the user as well as an output that we called fuzzy rate. The first one has 3 linguistic variables, which are low, medium and high, representing the preference with triangular membership functions over a range of 1–5. The second one also has three linguistic variables, which are low, medium and high representing the experience with triangular membership functions over a range of 1–100. Finally we have the output consisting of three linguistic variables bad, normal and good representing the fuzzy rate with triangular membership functions in a range of 1–100.

Fig. 5
figure 5

Fuzzy system of Mamdani type [2, 11, 12]

Full size image

Below we show the rules IF-THEN of the fuzzy system:

  1. 1.

    If preference is low and experience is low then fuzzy-rate is bad

  2. 2.

    If preference is low and experience is mid then fuzzy-rate is bad

  3. 3.

    If preference is low and experience is high then fuzzy-rate is normal

  4. 4.

    If preference is mid and experience is low then fuzzy-rate is normal

  5. 5.

    If preference is mid and experience is mid then fuzzy-rate is normal

  6. 6.

    If preference is mid and experience is high then fuzzy-rate is good

  7. 7.

    If preference is high and experience is low then fuzzy-rate is normal

  8. 8.

    If preference is high and experience is mid then fuzzy-rate is good

  9. 9.

    If preference is high and experience is high then fuzzy-rate is good

These rules will give us a fuzzy rate value result, this is the value need it to be defuzzify by the centroid method in order to be used in our fitness expression, given by Eq. 1. This expression is responsible to represent the individual fitness.

$$ F = \frac{{\mathop \sum \nolimits_{i = 0}^{n} x_{i} y_{i} }}{{\mathop \sum \nolimits_{i = 0}^{n} y_{i} }} $$
(1)

where n represents the number of users that have given an evaluation of the individual, x is the rate of preference for the individual given by the user, y is a function that calls the fuzzy system in order to have the fuzzy rate. This function needs x and the user experience level. The user experience level is given by the total activities that user have at the moment. In each activity we assign the score, for example if the user log in (join) to the application we assign 5 points, if the user evaluates (likes) an individual we give 3 points, etc.; in Fig. 6 we can show the flow for assigning fitness to the individual.

Fig. 6
figure 6

Assign fitness flow

Full size image

4 Results

To view the results given by the application, we need to know how different individuals were produced by interactive evolutionary algorithm. One way to know how different a set is, we use the information entropy measure, which is defined in Eq. 2. This measure allows us to understand how different the resulting individuals are from each other. If all individuals were the same then the entropy tends to be 0. The more diversity we have in the resulting individuals, then the information entropy tends to be higher.

$$ H\left( X \right) = \mathop \sum \limits_{i = 1}^{n} p\left( {x_{i} } \right)log_{2} \left(\frac{1}{{p(x_{i} )}}\right) = - \mathop \sum \limits_{i = 1}^{n} p\left( {x_{i} } \right)log_{2} p(x_{i} ) $$
(2)

The experiment consisted of 10 users used the application to evaluate individuals for a period of 3 min. We initialize the population with 80 individuals.

Table 1 shows the results of this experiment using the accumulated entropy and compares with historical data that had been produced using the same individuals chromosome structure with a precise fitness assignment strategy. Figure 7 shows this structure.

Table 1 Experiment results
Full size table
Fig. 7
figure 7

Individual chromosome structure

Full size image

This structure is represented by real numbers, which is a data array of 15 positions. Each index of the array represents a behavior of the individual in the animation. For example the index 0 represents the number of figures that were used in the animation, the index 1 represents the size of the figures in the animation, the index 2 represents whether or not a triangle, etc.

In Fig. 8 shows the best individuals that occurred during the experiment.

Fig. 8
figure 8

Best individuals at the time

Full size image

Table 2 shows the identifier of the individual as well as the number of evaluations received from users, including their current fitness.

Table 2 Experiment results
Full size table

5 Conclusions

The results show that the proposed fitness expression is working as we expect. However the number of users that was used in the experiment was very small. It is necessary to expand the number of users in order to know whether or not this fitness expression is working properly, in other words if it is attracting the interest of users.