1. (ReceivedJanuary17,2011) NorikoO MitsunoriM TomoyukiH andMasatoY InteractiveGeneticAlgorithmusingInitialIndividualsGeneratedfromHumanSensitivity

Interactive Genetic Algorithm using Initial Individuals Generated from Human Sensitivity

Noriko O_KADA^* Mitsunori M_IKI^** Tomoyuki H_IROYASU^*** and Masato Y_OSHIMI^**

(Received January 17, 2011)

In this paper, we propose new methods to generate initial individuals which reflects human’s sensitivity in Interactive Genetic Algorithm (IGA). Specifically, we propose the initial individuals generation method based on color harmony theories. IGA is an optimization method based on Genetic Algorithms (GA) which simulates the evolution of living things, where the evaluation part of the GA is handled subjectively by a user. Color harmony theory are the principles used to create harmonious color combinations. In the proposed methods, by including user’s favorite individuals in an initial population, we aim at to increase efficiency of searching solution and reducing user’s loads. We constructed a system which designs a color combination of individual workspace and experimented to verify the validity of the proposal methods. The experiment showed that a design with a user’s high level of satisfaction is generable in the system using the proposal methods. In addition, we figured out that the proposed methods are effective, and found out that it was useful in reducing the psychological fatigue of the users.

Key words optimization, interactive evoluationary method, Interactive Genetic Algorithm, color combination

1.

1) 2)

* Graduate Student, Department of Intelligent Information Engineering and Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6924, E-mail:[email protected]

** Department of Intelligent Information Engineering and Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6930, Fax:+81-774-65-6796, E-mail:{mmiki, myoshimi}@mail.doshisha.ac.jp

*** Department of Biomedical Information, Doshisha University, Kyoto

Telephone:+81-774-65-6932, Fax:+81-774-65-6019, E-mail:[email protected]

(Interactive Genetic Algorithm:IGA)³⁾

IGA Genetic Algorithm:

GA ⁴⁾

IGA

IGA

IGA

IGA

IGA

2.

2.1 IGA

GA

5) GA

IGA

6, 7,8)

IGA IGA

Fig. 1 IGA

Fig. 2

User System

GA

Display Evaluation

Fig. 1. IGA system.

Initialization

Evaluation

Selection

Crossover

Mutation Start

Yes End No Display

Human operation

Terminal criterion

Fig. 2. Flow chart of IGA.

2.2

IGA

IGA

IGA

IGA

10 20

3.

3.1 3.1.1

2

9)

PCCS(Practical Color Co-ordinate System) ¹⁰⁾

PCCS

3.1.2 PCCS PCCS

1964

10)

PCCS HSB

3

(tone) 2

PCCS Fig.

3

PCCS

PCCS 4

4 12

24

PCCS Fig. 4

p Pale

ltg Light Grayish

g Grayish

v Vivid b

Bright

s Strong

dp Deep lt

Light

sf Soft

dk Dark d Dull

dkg Dark Grayish W

White

ltGy Light Gray

mGy Medium Gray

dkGy Dark Gray

Bk Black

Saturation High

Low

Brightness

Low High

Fig. 3. Tone of PCCS.

3.2

IGA

20 20

1

2:R 3:yR

4:rO 5:O

6:yO 7:rY 8:Y

9:gY 10:YG

11:yG

13:bG

14:BG 12:G

15:BG

16:gB

17:B

21:bP 24:RP

23:rP 22:P

20:V 19:pB 18:B 1:pR

yellowish red reddish orange

red

yellowish green green

bluish purple reddish purple purplish red

yellow green

red purple

purplish blue

blue green

blue bluish green

purple

violet

greenish blue

Fig. 4. Hue circle of PCCS.

3

8 ¹⁰⁾

3 1

4

Fig.

5

•

• 3

4

•

Fundamental color

Faux-Camaieu Tone on Tone

Gradation Natural harmony

Fig. 5. Example of color combination.

3.3 3.2

4

1

4 3

3

Fig. 6. Method of generating initial individuals based on color the harmony theory.

4.

4.1

•

3 3

•

HSB ¹⁰⁾

HSB

(Hue) (Saturation) (Brightness) 3

5

0 360

0 100

•

1 1

HSB

HSB

0.0 1.0 4.2

1.

3.3

3

1

9 2.

1 1

1 5 5

5 9

3.

4.

GA

(BLX-α)¹¹⁾

BLX-α 2 di α

BLX-α

BLX-

7 8

Parent2 Parent1

Child1 d Child2

Fig. 7. Crossover for hue.

0.0 1.0

Parent1 Parent2

d

Child1 Child2

Fig. 8. Crossover for saturation and brightness.

5.

NV 1

6.

5.

5.1

IGA

2

20 20

2 2

Table 1

•

1

3 9

•

IGA

9

Table 1. Parameter.

Number of individuals 9

Number of design variables 9 Number of search generations Arbitrary Crossover rate ^NP_N^−NE

P

Mutation rate _N¹

V

NP:Number of individuals NE:Number of elite individuals NV:Number of design variables

1

2

3

1

5 2

5 3

5

IGA

5.2

1 3 Fig. 9

Fig. 11 1

2

3

5% Table

2

Satisfactory Satisfactory so-so Can't really say

Dissatisfied Rather dissatisfied

Random system 30%

6 people

Color harmony system 65%

13 people

15%

3 people

80%

16 people 5%

1 people 5%

1 people

Fig. 9. Result of satisfactory level for the proposed system.

Yes Somewhat yes Can't really say

No Somewhat no

Random system Color harmony system

15%

3 15%

3 people

40%

8 people 15%

3 people 30%

6 people

10%

2 people

15%

3 people 30%

6 people

35%

7 people

Fig. 10. Result on the indicated of many preferred individuals in the initial generation.

Fig. 9 1

95% 19

Delightful Delightful so-so Can't really say

Dreary Rather dreary

Random system Color harmony system

20%

4 people

60%

12 people 15%

3 people 1 people5%

35%

7 people

25%

5 people 10%

2 people 25%

5 people 1 people5%

Fig. 11. Result on the pleasantness of the design process in the proposed system.

Table 2. Result of sign test.

Evaluation item Significance probability Item 1 Color harmony system 1.90×10⁻⁵ Random system 9.53×10⁻⁷ Item 2 Color harmony system 9.44×10⁻² Item 3 Color harmony system 1.84×10⁻³ Random system 7.08×10⁻²

Fig. 10 2

Fig. 11 3

80% 16 60% 12

Fig. 12

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

User

2 3 5 6 7 8 9

1 4 1011121314151617 181920

Number of generations

Fig. 12. Number of search generations.

9.15 12.1

4.46 5.63

IGA

6.

IGA

IGA

1) HCD

( 2006) p.22-56.

2)

Vol.64 No.10 p.1419-1422 (1998).

3)

Vol.13 No.5 p.692-703 (1998).

4) D.E.Goldberg Genetic Algorithms in Search Optimization and Machine Learnig (1989).

5)

4 ( 2000) p.325-361.

6) Hideyuki Takagi Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation Proceedings of IEEE (2001).

7) GA 3 CG

Vol.J81-D-2 No.7 p.1601-1608 (1998).

8)

Vol.10 No.2 p.243-251 (2008).

9) (

1997) p.227-244.

10)

( 2004).

11) Eshleman,L.J and Schaffer,J.D Real-Coded Genetic Algorithms and Interval-Schemata Foundations of Genetic Algorithms Vol.2 p.187-202 (1993).

p Pale

ltg Light Grayish

g Grayish

v Vivid b

Bright

s Strong

dp Deep lt

Light

sf Soft

dk Dark

d Dull

dkg Dark Grayish W

White

ltGy Light Gray

mGy Medium Gray

dkGy Dark Gray

Bk Black

Saturation High

Low

Brightness

Low High

2:R 3:yR

4:rO 5:O

6:yO 7:rY 8:Y

9:gY 10:YG

11:yG

13:bG

14:BG 12:G

15:BG

16:gB

17:B

21:bP 24:RP

23:rP 22:P

20:V 19:pB 18:B 1:pR

yellowish red reddish orange

red

yellow ish gr

een green

bluish purple reddish purple purplish red

yellow green

red purple

pu rplish lu b

e

blue green

blue bluish green

purple

violet

greenish blue

Parent2 Parent1

Child1 d Child2 Fundamental color

Faux-Camaieu Tone on Tone

Gradation Natural harmony

Fig. 3. Tone of PCCS. Fig. 4. Hue circle of PCCS.

Fig. 5. Example of color combination.

Fig. 6. Method of generating initial individuals based on color the harmony theory.

Fig. 7. Crossover for hue.