Interactive Evolutionary Computation

What is Interactive Evolutionary Computation?

Interactive Evolutionary Computation is a method enabling a system to interact with a user in order to automatically make objects that represent a good fit to user preferences. This method can be applied to various design areas such as clothing design, color coordination, shoe design, fashion coordination, sound and visual effects, and lighting and camera motion in 3D CG space.

Here’s an example of an interactive system for shoe design using IEC.

To begin, the computer automatically creates various shoe designs by combining design components at random. The design components are parts of shoes—for example, base, line and toe—and each component includes different design objects. The computer randomly selects design objects for every component.

Next, a user evaluates the designs generated by the system, based on their feel or preference. The system assigns a value to each design, based on the user’s evaluation.

The system then combines two designs with high evaluation scores to create new designs and presents these to the user.

IEC repeats the process, and finally, the user identifies the best design.


Interactive evolutionary computation

As recent product development attaches great importance to user preference, IEC clearly has potential in this area. However, one general problem with IEC is that the evaluation burden on the user is huge because of the need to repeat the evaluation many times.

We aim to develop new evaluation interfaces for IEC that will reduce this user burden.

Improvement of evaluation interface

A conventional IEC interface shows 10~20 designs to the user in each generation, and the user assigns a value of 1~5 points or 1~10 points to each design. However, this method sometimes makes it difficult for the user to evaluate designs when they are unsure about scoring.


A conventional IEC interface

To overcome this difficulty, we have proposed a simpler evaluation method, in which the user selects only the best option from among the presented designs.

This method cannot be applied to Interactive Genetic Algorithms as generally used because the system discards designs other than the one selected by the user.

To apply the method to IEC, we have proposed two new IEC algorithms: the tournament-style evaluation method and interactive tabu search.

Evaluation in tournament form

In the tournament-style evaluation method, a user repeats their evaluation to compare two presented designs and to select a favorite. This method effectively reduces user burden when evaluating time-series data such as music or animation because only two items are compared in each evaluation.

Tournament-style evaluation employs two different systems. The first of these is the standard tournament method, in which a user simply selects a favorite from two presented designs. For example, a user returns two kinds of evaluation, such as “design 1 is good” or “design 2 is good.” The second tournament method involves a stepwise evaluation, in which a user returns four kinds of evaluation, such as “design 1 is good,” “design 1 is very good,” “design 2 is good” or “design 2 is very good.”


The standard tournament method


The stepwise evaluation method

Just choose one favorite design!

In an interactive tabu search, a user chooses only one favorite design from among the presented designs. In one generation, the system usually shows 8 to 10 designs to the user. This method is unsuitable for evaluations such as music or animation because it compares several designs at a time. However, it reduces the evaluation burden on the user for evaluation of content such as still images.


Interactive tabu search

Evaluation experiment

In a computer simulation, a computer-generated quasi-user evaluated designs in place of a real user. We built design support systems using the tournament-style evaluation method or interactive tabu search and trialled with real users to investigate how easily they could evaluate designs.

Simulation results confirmed that these methods perform well in optimizing solutions, and experimental results with real users show a reduced evaluation burden.

We aim to develop applied systems based on tournament-style evaluation and interactive tabu search. This work includes development of a basic algorithm for interactive parallel tabu search, in which users can select several favorites from presented designs.

References

H.Takenouchi, M.Tokumaru, N.Muranaka, “Interactive Evolutionary Computation Using a Tabu Search Algorithm”, IEICE TRANSACTIONS on Information and Systems, Vol.E96-D, No.3, pp.673-680, 2013-03.

H.Takenouchi, M.Tokumaru, N.Muranaka, “Tournament Evaluation System Considering Multiple People’s Kansei Evaluation”, Journal of Kansei Engineering International, Vol.9, No.2, pp.43-50, 2010-06.

S.Domae, H.Takenouchi, M.Tokumaru, “Parallel Retrieval Interactive Tabu Search”, 14th International Symposium on Advanced Intelligent Systems – ISIS2013, T3f-2, 2013-11 (Daejeon, Korea).

H.Takenouchi, M.Tokumaru, N.Muranaka, “Tournament Evaluation System Applying Win-Lose Result Presumption Considering Kansei Evaluation by Multiple People”, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.16, No.3, pp.453-461, 2012-05.

H.Takenouchi, M.Tokumaru, N.Muranaka, “Performance Evaluation of Interactive Evolutionary Computation with Tournament-Style Evaluation”, WCCI 2012 IEEE World Congress on Computational Intelligence, pp.193-200, 2012-06 (Brisbane, Australia).

H.Takenouchi, T.Hirokata, M.Tokumaru, N.Muranaka, “Running Shoe Design System with Interactive Evolutionary Computation”, International Conference on Kansei Engineering and Emotion Research 2012, pp.925-932, 2012-05 (Penghu, Taiwan).