# Interactive Tabu Search vs. Interactive Genetic Algorithm

Tatsuya Hirokata, Masataka Tokumaru, Noriaki Muranaka

► To cite this version:

Tatsuya Hirokata, Masataka Tokumaru, Noriaki Muranaka. Interactive Tabu Search vs. Interactive Genetic Algorithm. 9th International Conference on Entertainment Computing (ICEC), Sep 2010, Seoul, South Korea. pp.505-507, 10.1007/978-3-642-15399-0_74. hal-01055586

HAL Id: hal-01055586

https://inria.hal.science/hal-01055586

Submitted on 13 Aug 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Interactive Tabu Search vs. Interactive Genetic
Algorithm

Tatsuya Hirokata¹, Masataka Tokumaru², Noriaki Muranaka²,

¹Graduate School of Kansai University.3-3-35,Yamatre-cho,Suita-shi,Osaka,Japan.

² Kansai University.3-3-35,Yamatre-cho,Suita-shi,Osaka,Japan.

{k875239, toku, muranaka}@kansai-u.ac.jp

**Abstract.** We propose an interactive tabu search (ITS) to be used for the development support of a product that fits a human’s feeling. Interactive evolutionary computation (IEC) is one of the technologies used in the development support of products that fit a human’s feeling using a computer and person undergoing a communication. The interactive generic algorithm (IGA) is generally used in the IEC. A major problem with the use of the IEC is the increased burden on the IEC user to evaluate multiple solution candidates. Using the ITS instead of the IGA may reduce this burden, because the ITS user chooses only his most favorite solution candidate among multiple solution candidates. We performed a comparison of the search performance using simulations with the ITS and IGA. As a result of this simulation, the search performance of the ITS exceeded that of the IGA by a range from 2% to 10%.

**Keywords:** Tabu search, Interactive evolutionary computation,

# 1 Introduction

Interactive evolutionary computation (IEC) is a technique used in the development support of a product that fits a human’s feeling using a computer.

A major problem with the use of the IEC is the increased evaluation burden of the IEC user. One of the methods that can be used to reduce the evaluation burden of the IEC user is an improvement to the evaluation interface [1]. A general evaluation interface of IEC is an *n*-stage evaluation method of all of the individuals that the IEC system shows. However, if many individuals are shown immediately, the result is a large evaluation burden for the IEC user.

The burden of the IEC user is caused as follows. First, the user should evaluate the same individual repeatedly during a single search. Second, the user must give each individual a gradual evaluation point. To solve these problems, an algorithm that can maintain evolution performance by a simple evaluation interface is desirable. However, this is difficult to achieve when using a generic algorithm (GA).

Therefore, we use a tabu search (TS) instead of a GA. The ITS aims to reduce the evaluation burden of the IEC user.
## 2 Interactive Tabu Search

The ITS is a tabu search that evaluates the solution candidates using human intuitive evaluation instead of a quantitative evaluation function. The evaluation interface of the ITS is a method to choose the individual that the user prefers the most. We anticipate that the simplicity of this solution evaluation greatly reduces the burden of the user.

Following are the steps of the ITS process:

(1) Generation of the initial individuals.

The initial individuals are generated by the bit strings at random.

(2) Presentation and evaluation by the users.

All of the individuals are shown to the user, who chooses the individual that he prefers the most.

(3) Update of the tabu list.

The information of the individual that the user has chosen is added to the tabu list.

(4) Generation of neighboring individuals.

The neighboring individuals are generated by flipping the single bit individual that the user chose. Multiple neighboring individuals are generated. Steps (2) to (4) are repeated until the final generation.

(5) Generation of the initial individuals from the tabu list.

The TS searches while repeating improvement and the change for the worse of the solution. Therefore, the evaluation of an individual chosen before several generations may be higher than the evaluation of the current individual. The tabu list records the chosen individuals from several generations. The individuals in the tabu list are shown to the user.

## 3 Simulation and Result

We evaluate the utility of the ITS with the use of a simulation, which compares the search performance of the ITS with the IGA. The utility of the ITS can be proven if the search performance of the ITS is better than that of the IGA.

The target individual to mean human's feeling is generated, and evaluates the individual in Hamming distance with it. Figure 1 shows the evaluation of the individuals according to the target individual.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Evaluation of the individual by the target individual.</figcaption></figure>
The evaluation value is the number of bits that a number accords with it. If the length of the bit string is longer than 10 bits, the evaluation value is converted so that the maximum length becomes 10.

Figure 2 shows a result of the simulation. As a result of this simulation, the search performance of the ITS exceeded the performance of the IGA by approximately 2% with the 20th generation of 10 bits. In addition, the search performance of the ITS exceeded that of the IGA by approximately 10% with the 20th generation of 50 bits. The ITS achieves the same evaluation value with half the generation number of the IGA. The ITS can be figured to be algorithm that can maintain search performance by a simple evaluation interface. So we consider that the ITS be expected to reduce the evaluation burden of the IEC user.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Search performance of ITS and IGA</figcaption></figure>

# 5 Summary

We propose the use of an ITS to reduce the burden of users. The utility of the ITS was proved by simulation. In the future, we will inspect the evaluation burden of the user who is used as a subject.

# References

1. Hideyuki Takagi: Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation. Proceedings of the IEEE. vol.8, no.9, pp.1275-1296(2001).