A Proposal of Interactive Simulated Annealing
Mitsunori M IKI * Tomoyuki H IROYASU * and Toshihiko F USHIMI **
(Received Desember 20, 2002)
Recently, threr is Interactive Evolutional Computation (:IEC) developed as one of the realization methods of Humanized Technology. IEC is a technique of optimizing a problem combining evaluation of man and the optimal technology of a computer. The problem deals with emotio-sensitivity. As the typical techniques of IEC , Interactive Genetic Algorithm (:IGA) is known as a powerful method. As new approach in IEC, this paper proposes Interactive Simulated Annealing (ISA). SA is the same general-purpose optimization technique as GA. In order to confirm the validity of the proposal approach, subjective experiments ware conducted on a proto-type system using student as subjects.
Key words ： Simulated Annealing, Interactive Evolutionary Computing, Sensible Design, Optimun Design, Human Interaction
キーワード ： シミュレーテッドアニーリング，ヒューマンインターフェース，対話型進化計算，感性に基づく 設計，最適設計
対話型シミュレーテッドアニーリングの提案
三 木 光 範 ・ 廣 安 知 之 ・ 伏 見 俊 彦
1. はじめに
これまでの知能科学，特にソフトコンピューティン グと呼ばれる分野においては，1980 年代にニューラ ルネットワーク (Neural Network: NN)，ファジーシ ステムおよび進化計算 (Evolutionary Computation:
EC) などの技術が注目された．その後それぞれの技 術の融合，協調モデルが提案され，1990 年代に実応 用へと広がっていった．そして，今，これらの技術と 感性工学が融合し，Humanized Technology が 1 つの 研究分野として形成されようとしている．Humanized Technology の実現方法の 1 つとして注目されている 研究が，対話型進化計算法 (Interactive Evolutionary
* Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto
Telephone:+81-774-65-6930, Fax:+81-774-65-6780, E-mail:[email protected] , [email protected]
** Graduate Student, Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6716, Fax:+81-774-65-6716, E-mail:[email protected]
Computation: IEC) である．IEC は最適化系にシス テムの操作者そのものを取り込む，つまり人間の主観 的評価と EC 技術の組み合わせにより最適解を導き 出す手法であり，現在ではアート，工学，教育，エン ターテインメントなどの分野に応用されている 1) ． IEC には遺伝的アルゴリズム (Genetic Algorithm:
GA) 2) をはじめ，様々な進化計算法が用いられてい
る．GA を対話型進化計算法に取り入れた対話型遺伝
的アルゴリズム (IGA) は探索範囲が広く，解に多様性
があるという特徴がある．しかし，IGA は多点探索
であるのですべての解候補を人間が評価する必要があ
り，操作者の疲労が大きい．また，探索過程の終盤では
多くの候補の相違が少なくなり，適切な評価が容易で
はない．こうした場合には一対比較が有効だと考えら れる 3) ．このような点から本研究ではシミュレーテッ ドアニーリング (Simulated Annealing: SA) 4) を用い た 対話型シミュレーテッドアニーリング (Interactive Simulated Annealing: ISA) を提案する．
SA では現在の解とそれをわずかに変化させた次の 解とを比較することができ，上で述べた IGA の欠点 を解消できると考えられる．
一対比較に SA を適用した理由は，局所探索をラ ンダムに行いながら解に改良が見られない場合，つま り改悪の場合でも，新しい点に移る可能性を残すこと で大域的最適解を得られるという特徴があるからであ る．そのため，改悪の場合でも，新しい点に移るとい う SA を組み込んだ ISA が感性に対しても有効であ ると考えられる．
本論文では，SA の改悪方向への遷移が人間の感性 に対してどのような影響を与えるかについて検証した．
検証に関しては，改悪方向への遷移を行わず，改善方 向への遷移のみで探索を行う山登り法との比較実験を 行い，ISA の有効性を検証した．対象問題としては人 間の感性を反映できる服装のカラーコーディネートに 関する問題を用いた．
2. 対話型進化計算法 2.1 対話型進化計算法 (IEC) の概要
システムの最適化とは，望ましいシステム出力が得 られるようにシステムパラメータを調整することであ る．多くの場合，望ましいシステム出力は数値的ゴー ルである．工学的にも，自分が聞いたり見たりして最 適になるようにシステムを調整するという要求はいろ いろある．例えば，気に入った画像や音楽を生成した い，あるいは検索したい，という要求はいろいろな場 面で見られる．これらをシンセサイザや CG などの パラメータの最適化と考えれば，数値的最適化手法が 適用できそうである．では，評価はどうであろうか．
従来このような場合，人間の評価系の代替モデルを作 り，これを最適化システムに組み込むことで探索を行 う方法がよく行われてきた 1) ．しかし，個人の主観に 依存する好みなどについて十分正確なモデルを作るこ とは難しく，完全なものができるとは考えにくい 1) ． そこで，人間の評価系をモデル化して組み込むとい う分析的なアプローチに対して，ユーザそのものを最 適化系に組み込んで，ユーザの評価によってコンピュー タに最適化させるというアプローチが考えられる．こ のように人間と機械との交互作用によって主観的評価
に基づく最適化を行う手法が対話型コンピューティン グである．
2.2 対話型遺伝的アルゴリズム (IGA)
2.2.1 対話型遺伝的アルゴリズム (IGA) の概要 これまでに述べてきた IEC の代表的な手法として 対話型遺伝的アルゴリズム（Interactive Genetic Al- gorithm: IGA） 1) がある．IGA は，GA 2) による探 索をベースとしつつも，GA の処理の中の「評価」の 部分を人間が行う．つまり， IGA は，最適化を行う基 準となる評価関数を人間に置き換えた GA である．
2.2.2 IGA の問題点と解決策
IGA における問題点は以下の 2 点がある．
(1) ユーザの疲労
IGA はその仕組み上ユーザの関与は必須であ る．人間が疲れを知らないコンピュータと協調し て，世代ごとに多くの個体を比較評価し，評価値 を入力するには限界がある．たとえ，よい解が得 られるツールを IGA によって作れたとしてもユー ザの疲労を軽減できなければ，一般的なツールと して意味をなさない．
(2) 設計解の早熟収束，収束性の悪化
この問題は，ユーザの疲労という問題から派生 した問題ともいえる．IGA においては，操作者が 全個体に対して評価する必要があるので，提示で きる個体数は 10〜20，評価できる世代数も 10〜
20 世代と限定される．そのため，早熟収束，収 束性の悪化という問題が生じてしまう．
(1) の問題点に対しての解決策としては，5 段階評 価による評価方法の提案，主観的評価実験による評価 世代数の検討，インタフェースの改善などの解決策が 提案されている 5, 6) ．(2) の問題点に対しての解決策 としては，少ない個体数でも早く収束するよう評価値 の予測機能を入れる方法が提案されている．これは，
個体間のユークリッド距離による人間の評価を予測す る目的関数を作成し，GA 内部では 200 個体に対して GA 演算を行い，そのうち上位 10 個体のみをユーザ に提示する方法である 7) ．
IGA には上に述べたような問題点がある．本研究 では，これらの問題の改善アプローチとしても シミュ レーテッドアニーリング (SA) を適用することで改善 できるのではないかと考えた．
(1) ユーザの疲労
ISA が一対比較であるということを考えれば IGA
よりもユーザに対する疲労は軽減される．
(2) 設計解の早熟収束，収束性の悪化
終盤における収束性の悪化に ISA を適用するこ とで収束行うことができる．
3. 対話型シミュレーテッドアニーリングの提案 3.1 対話型シミュレーテッドアニーリングの概要
SA とは GA と同じくヒューリスティック探索法で ある．SA の基本となる考えは Metropolis らが 1953 年に発表した焼きなましと呼ばれる加熱炉内の固体の 冷却過程をシミュレートするアルゴリズムに端を発し，
最適化問題，特に組み合わせ最適化問題を解く汎用近 似解法の１つとして用いられている．
前節で IGA の問題点を述べたが， SA には一点探索 で，改悪をある確率で受理することにより大域的最適 解を求めることができるという特徴がある. したがっ て，IEC に SA を適用することで次のような改善が 期待できると考えた．
• IEC における操作者の疲労の軽減
• 収束した状態における解探索
ここで対話型シミュレーテッドアニーリング (Inter- active Simulated Annealing: ISA）を提案する．ISA は，IGA におけるユーザの疲労の軽減および，最終 候補における解探索を目的としている．IGA は，一 度に多数の解候補を掲示する多点探索であるのに対し て，ISA は，2 つの解候補を掲示する．一対比較を行 い探索を進めていく．したがって，ユーザは多数の解 を評価する必要はなく，現在の解に対して次の解候補 に「良い」， 「悪い」といった評価を与えるだけでよい．
そのため，ユーザにかかる負担は IGA に比べると軽 減される．
また，IGA などにおいて最終候補に残った解はい ずれも操作者の好みを反映している場合が多い．すな わち，最終候補はいずれも操作者の好みに近いもので あるため，評価をし，評価値を決定することが難しく なってくる．そこで，IGA で操作者の好みを反映した 解に ISA を適用することによってより操作者の感性 を反映した解を探索することができると考えた．ISA の概念図を Fig. 1 に示す．
3.2 ISA の基本アルゴリズム
ISA は，SA による探索をベースとしつつ， SA 処理 の中の「評価」の部分を人間が行う．つまり，ISA は 受理判定を人間が行う SA であるといえる．したがっ て， ISA は人間の主観的評価に基づいてシステムを最 適化させる技術であるといえる．以下，ISA の基本動
User System
Output Evaluate Alternative Solutions
Current Next
SA engine
Fig. 1. Interactive Simulated Annealing.
作を述べる．
ISA における基本動作のフローチャートを Fig. 2 に示す．ISA は SA の基本アルゴリズムの評価の部分 にユーザの判断を組み込んだところが通常の SA と異 なる．この仕組みによりユーザの感性を組み込むこと になる．
Set Initial Parameter Generate
Accept Criterion
Transition
Reduce Criterion
End Terminal Criterion
Yes No
Yes No
Yes No
Reduce Evaluation
Human Operation Human Operation
Fig. 2. Flow Chart of ISA.
ISA は SA と同じく，与えられた初期状態から出発 して状態を遷移させ最適な状態に辿り着くことが目的 である．SA との大きな違いは解の評価と終了条件に ある．
1. 初期設定
初期設定では，SA に必要なパラータ，温度，近 傍，クーリング率など各種パラメータをシステム に対して設定する．
2. 初期解生成
SA では初期状態は乱数により発生させられるが，
ISA の場合は初期状態をユーザが生成する．この
理由は ISA では中盤から終盤にかけての解を探
索することに重点をおいているからである．序盤
から中盤にかけての解は IGA で求めることを想 定した上で ISA は効果を発揮すると考えられる．
3. 生成処理
生成処理では，SA と同様に現在の状態を x とし て与えて次に遷移すべき状態 x を作りだす．
4. 評価
新たに生成された状態について評価を行う．この 評価は新たに生成された状態 x と前の状態 x の 優劣をユーザが判定し，評価を行う．評価方法は
「良い」および「悪い」で行う．そのため，IGA の評価値入力に対して 2 者選択方式なので容易に 評価が行える．
5. 受理判定
SA での受理判定は，次の状態 x のエネルギー E と現在の状態 x のエネルギー E との差分 ∆ E (=
E − E )，および温度パラメータ T によって，次 の状態への遷移を受理するか否かの判定をする．
一方， ISA では人間の評価関数を対象として扱う ので，∆ E を数値的に求めることは容易ではない ため，ユーザの評価に応じてシステムが ∆ E を与 える．与えた ∆ E と温度パラメータにより受理 率が変化していくという方法を採用した．また，
受理判定に関しては与えた ∆ E と温度パラメー タを基に式 (1) の Metropolis の基準 8) を用いて いる．ここでシステムより与えられる ∆ E の値 については実験の結果より 160 とした．実験につ いては 5 章で詳しく述べる．
A ( E, E , T ) =
1 if ∆ E < 0 exp
− ∆E T
otherwise (1) 6. クーリング
SA と同様にクーリングスケジュールに基づき温 度をクーリングする．
7. 終了条件
ISA においては操作の終了はユーザが判断する．
求めるものが得られたのであれば ISA は終了し，
得られていないのであれば ISA は再び生成，評 価，受理判定，クーリングという操作を繰り返す．
3.3 ISA の特徴
ISA の特徴は改悪方向へある確率で遷移することで ある．数値計算などに SA を適用した場合，改悪方向 への遷移によって局所解からの脱出が保証されている．
しかし，人間の感性を反映する解を対象とする場合，
改悪方向への遷移がユーザに対してどう影響するかに ついては検証されていない．
本研究では，ISA の特徴である改悪方向への遷移が もたらす影響を検証するためにシステムを構築し，実 験を行った．改悪方向への遷移がない山登り法 (Hill- Climbing Method) と比較することで，ISA の有効性 について検証した．
4. ISA システム
4.1 ISA システムの概要
本研究では，ISA の有効性を検証するために「服装 のカラーコーディネート支援システム」を提案する．
服装の配色コーディネート支援システムとはジャケッ ト，パンツ，マフラーおよびシューズの各色を変更す ることによってデザインを決定するものである．
ユーザに掲示される画面を Fig. 3 に示す．画面上に 現在の状態 (Current) と，次状態の候補 (Next) が掲示 される．ユーザはこれら 2 つの候補を比較し，Next の 方が良いと判断すれば ”Good” ボタンを，逆に Cur- rent の方が良いと判断すれば ”Bad” ボタンを選択す る．つまり，新たに生成された候補と現在の候補を比 較して評価を行なうのである．評価基準は「好み」と しているので，ユーザが自分の好みに応じて評価をし ていく．
4.2 設計変数
本システムでは， SA 処理における設計変数として服 装におけるジャケット，パンツ，マフラーおよびシュー ズの 4 つを用いている．ユーザはこれらの設計変数の トータルバランスを考えた上で掲示されるデザインに 対して評価を行う．
各設計変数におけるカラーパターンは 色相 (HUE)/
色調 (TONE) で表わされる 120 通り (HUE & TONE)
としているので，存在しうるすべてのデザインは約 2
億通りとなる．HUE & TONE とは，無限に広がる色
に対してなるべく単純で理解しやすい有彩色 120 色と
無彩色 10 色に分類・整理したものである 9) ．
HUE & TONE を用いる利点は，人間の感性を考
慮したカラーパターンで構成されており，人間の感性
を表す 180 のイメージ語と関連づけられている．そ
のため，色の意味をイメージで系統だてた仕組みに構
成されているといえる．ISA を用いて人間のイメー
ジを一つの形にしていく上で，人間の感性に基づいて
いるということは非常に重要なことである．HUE &
TONE をシステムに組みこむことによって，人間の感 性を考慮した数値的データを得ることができる． HUE
& TONE における有彩色 120 色を Fig. 4 に示す．
Button for Bad Button for Good
Control Parameters Information (Temperature) maffler jacket pants
shoes
Current Next
Fig. 3. User interface of the proposed system.
TONE
HUE
Fig. 4. HUE & TONE.
4.3 ISA システム 4.3.1 初期解
初期解は，ユーザが自分の好みに合うように配色を 決定する．この初期解を生成する理由は IGA により 大域的探索を行った後に ISA で局所的探索を行うシ ステムを想定し，ある程度ユーザの好みを反映してい る解候補を生成する必要があるからである．初期設定 では，HUE ＆ TONE 上の TONE が 3 および 8 の 列，計 20 色を掲示し，そこから色を選択して初期解 とするものとした（Fig. 5）．これは，3 と 8 の列を用 いることによって大まかな色の組み合わせを設定し，
後はシステムにより詳細な色の組み合わせを行うこと
を目的としているためである．
Fig. 5. A window for selecting colors.
4.3.2 近傍
ISA システムにおいて現在の状態から次状態を生成 するとき，現在の状態からどれぐらいの距離で遷移す るかを決めるのが近傍である．HUE ＆ TONE 上に おいて近傍内で現在の色から次の色がランダムに決定 される．本研究ではこの近傍の大きさを「良い」， 「悪 い」というユーザの評価によって変動するように設定 した．初期設定では近傍を 1 に設定し，それ以降は
「良い」が選択されると近傍を半分にし， 「悪い」が 5 回選択された場合は近傍を 1 つ増加させる．この理由 は「良い」が選択されたということは選択した解候補 の周辺に良い解候補がある可能性が高いと考えられる ため，近くを探索するように近傍を小さくする．逆に，
「悪い」が選択されるということは好みに合わないと 考えられるので，その周りには良い状態がある可能性 は低く，近傍を大きくして探索範囲を広めている．
4.3.3 温度スケジュール
SA における温度というパラメータは改悪方向への 遷移確率を決定するものである．したがって，高温時で は改悪方向への遷移の確率が高くなり，徐々に温度が 下がっていくにつれて改悪方向への遷移確率が下がっ ていく．本研究では最高温度を 100 度とし，最低温度 を 1 度として，100 度から 1 度まで 20 ステップで下 げるようにした．これより逆算してクーリング率を決 定する．これらの値は経験的に求めた．
4.3.4 ∆ E の設定
SA のアルゴリズムの特徴である改悪方向への遷移 の確率を決めているもう 1 つの要素が ∆ E である．
∆ E とは現在の状態と次状態との差を表わすパラメー タである．通常の SA の場合はこの ∆ E は容易に数 値で求められ，式 (1) のメトロポリス基準 8) より改悪 受理確率が決定される．
ISA においては現在の状態と次状態の差を明確な 数値で表わすことは容易ではない．なぜなら，解に人 間の感性が反映されているからである．したがって，
事前に ∆ E の値を決定する必要がある．∆ E の値は 次章の実験結果から最高温度時のおける改悪遷移確率
が 20%のときが最も適切であるという結果を得た．こ
のときの ∆ E は式 (1) より 160 である．実験に関し ては次章で詳細に述べる．
ISA システムで用いたパラメータを Table 1 に示す．
Table 1. Parameters of ISA System.
Parameter Value
Maximun Temperature 100 Minimun Temperature 1 Cooling Ratio 0.794 Markov Length 5 steps
∆ E 160
5. 対話型シミュレーテッドアニーリングにおける 改悪受理率に関する実験と考察
5.1 実験概要
ISA の最大の特徴である改悪方向への状態推移を行 うためには，改悪方向への推移確率をどのような値に するかが問題となる．通常の SA では，現在の状態と 次状態とのエネルギー差 ∆ E (= E − E ) は任意に求 まり，∆ E と温度で受理確率が決定されるが，人間の 感性を扱う ISA の場合は ∆ E は決定できないので，
システムがユーザの評価に応じて与えなければならな い．そこで，本研究では，∆ E の値を決定するための パラメータを求めるために実験をおこなった．
実験方法は，ユーザが「悪い」と判断したときに与 える ∆ E を最高温度時における改悪受理確率が 90%〜
10%となるように算出する．算出方法は式 (1) により
求める．算出された各改悪受理確率の ∆ E を Table 2 に示す．
求めた ∆ E によって探索能力の性能の違いを HUE
& TONE 上で任意にある一点を決め，その決めた一
点から距離が 2 の点へ到達するのに要したステップ数 で比較することで調べた．目的までに到達するステッ プ数が少ないほど探索能力が高いといえる．本実験で はまずジャケットだけに着目し，1 設計変数の場合の 実験を 5 パターン行った．次に，ジャケットとパンツ の 2 設計変数の実験を 2 パターン行なった．比較対象 である 山登り法を用いたシステムについても同様の 実験を行なった．
5.2 実験
以後 HUE & TONE 上のカラーを（TONE , HUE）
で表現する．
1. 1 設計変数の場合
HUE & TONE 上のカラーで Table 3 に示すパ
ターンについて実験を行った．
Table 3. Problem 1 (1 Design Variable).
Design Variable Start Point Goal Point
(a) Jacket (8 , 6) (10 , 8)
(b) Jacket (8 , 6) (10 , 4)
その他 3 パターンについても同様の実験を行な った．
2. 2 設計変数の場合
2 設計変数として，ジャケットとパンツの組み合
わせで Table 4 に示すパターンについて実験を
行った．
Table 4. Problem 2 (2 Design Variables).
Design Variable Start Point Goal Point
(c) Jacket (8,6) (10,8)
Pants (8,6) (10,4)
(d) Jacket (8,6) (8,8)
Pants (8,6) (10,6)
各色がスタートから目的の色に到達するまでに要し たステップ数を調べた．また，スタートから終了まで は最大で 100 ステップとした．
ここに実験で用いたカラーデータを選んだ理由を示 す．(a) のパターンは出発点と目的点に明らかな違い が見られる．(b) のパターンは出発点と目的点が同系 統の色で明らかな違いは見られない．(c) のパターン は (a) と (b) 組み合わせたものである． (d) のパターン は，初期点からジャケットは HUE だけを，パンツは TONE だけを変化させたものである．これら 4 つの パターンについての実験結果を示し，考察を行なう．
5.3 実験結果 (1) 1 設計変数の場合
実験結果を Fig. 6 に示す．また，5 パターンの 平均ステップ数を Fig. 7 に示す．縦軸は探索に 要したステップ数を，横軸は最高温度時の各改悪 受理率を表わしている．
Fig. 6 より，1 設計数の場合は山登り法が最も探
索数が少なくなっている．(a) に関しては改悪受
理率を 10%から 90%まで変化させて実験を行っ
た結果，改悪受理率が少ないほうが探索数も少な
くなった．(b) に関しては改悪受理率が小さくな
るにつれて探索数も小さくなるとう結果にはなら
ず，改悪受理率 30%のときが最も探索数が少ない
Table 2. Accept Ratio of Uphill Transition and ∆ E .
Accept Ratio of Uphill Transition 10% 20% 30% 40% 50% 60% 70% 80% 90%
∆ E 230 160 120 90 70 50 35 22 10
10% 20% 30% 40% 50% 60% 70% 80% 90%
Accept Ratio (at Maximum Temperature)
Annealing Steps
Hill-Cimbing Method
(a) (8,6) → (10,8)
Accept Ratio (at Maximum Temperature)
10% 20% 30% 40% 50% 60% 70% 80% 90%
Annealing Steps
Hill-Climbing Method
㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪊㪇 㪊㪌 㪋㪇 㪋㪌 㪌㪇
(b) (8,6) → (10,4)
10% 20% 30% 40% 50%
Accept Ratio (at Maximum Temperature)
Annealing Steps
Hill-Climbing Method
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇 㪪㫌㪺㪺㪼㫊㫊㩷㪩㪸㫋㫀㫆
Success Ratio
㪇 㪈㪇 㪉㪇 㪊㪇 㪋㪇 㪌㪇 㪍㪇 㪎㪇 㪏㪇 㪐㪇 㪈㪇㪇
㪇 㪇㪅㪉 㪇㪅㪋 㪇㪅㪍 㪇㪅㪏 㪈 㪈㪅㪉
(c) jacket:（8,6） → （8,8） , pants （8,6） → （10,6）
10% 20% 30% 40% 50%
Accept Ratio (at Maximum Temperature)
Annealing Steps
Hill-Climbing Method
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇 㪪㫌㪺㪺㪼㫊㫊㩷㪩㪸㫋㫀㫆
Success Ratio
㪇 㪈㪇 㪉㪇 㪊㪇 㪋㪇 㪌㪇 㪍㪇 㪎㪇 㪏㪇 㪐㪇
㪇 㪇㪅㪈 㪇㪅㪉 㪇㪅㪊 㪇㪅㪋 㪇㪅㪌 㪇㪅㪍 㪇㪅㪎 㪇㪅㪏 㪇㪅㪐 㪈
(d) jacket: （8,6） → （10,8） , pants （8,6） → （10,4）
Fig. 6. Ability of Search on Accept Ratio of Uphill Transition.
という結果になった．
また，改悪受理率 60%以上についてはいずれ も山登り法と比べ探索数が倍以上になっている．
したがって，他のパターンに関しては改悪受理率 50%までの実験を行なった．
Fig. 7 より，1 設計変数の場合は，山登り法が 最も探索数が少なくなり，改悪受理率が大きくな るにしたがって探索数も増加するという傾向がみ られた．
(2) 2 設計変数の場合
実験結果を Fig. 6 に示す．また，2 パターン
の平均を Fig. 8 に示す．縦軸は探索に要したス
テップ数および目標に到達できた確率を示してい る．横軸は各改悪受理率を表わしている．
Accept Ratio (at Maximum Temperature)
10% 20% 30% 40% 50%
Hill-Climbing Method
Annealing Steps
㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪊㪇 㪊㪌
Fig. 7. Average of Problem 1.
Fig. 6 より，(c) および (d) に関して改悪受理率
20%の場合が最も探索数が少なくなっている．し
かし，目標まで 100 ステップでは到達できなかっ
た場合がいずれの場合においても見られた．到達 率だけをみると山登り法が最も到達率が高く，改 悪受理率が大きくなるにつれて到達率は低くなっ ている．
10% 20% 30% 40% 50%
Accept Ratio (at Maximum Temperature)
Annealing Steps
Hill-Climbing Method
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇 㪪㫌㪺㪺㪼㫊㫊㩷㪩㪸㫋㫀㫆
Success Ratio
㪇 㪈㪇 㪉㪇 㪊㪇 㪋㪇 㪌㪇 㪍㪇 㪎㪇 㪏㪇 㪐㪇
㪇 㪇㪅㪈 㪇㪅㪉 㪇㪅㪊 㪇㪅㪋 㪇㪅㪌 㪇㪅㪍 㪇㪅㪎 㪇㪅㪏 㪇㪅㪐 㪈
Fig. 8. Average of Problem 2.
Fig. 8 より，山登り法が最も到達率が高いが，
探索ステップ数が多く， ISA は改悪受理確率 10%
が最も到達率が高いが，探索数が最も少ないのは 改悪受理率 20%のときである．改悪受理率 40%，
50%の場合は到達率が低くなるに加え，探索数も 多くなっている．
5.4 考察
1. 1 設計変数の場合
Fig. 6 の (a),(b) ともに改悪受理率 60%以上で 急激に探索数が増えている．その理由は，改悪受
理率が 60%を超えるとランダムサーチになるた
めと考えられ，改悪受理率 60%以上での探索は意 味がないといえる．
(a) と (b) を比べると両方とも初期点は同じで あるのに (a) の方では改悪受理確率が上がってい くにつれて徐々に探索数が上がっている．それに 対し，(b) は山登り法は改悪受理確率が上がるに つれて探索数も増加するという傾向ではない．そ の理由は， (a) のパターンは比較的初期点と目標点 の違いが明確である．それに対して (b) のパター ンは色相やトーンが類似しており，色の違いが明 確ではないため，目標まで直線的に到達すること が困難であることがいえる．このため少しの改悪 を認める場合が少ない探索数で目標に到達してい ると考えられる．
以上のことより次のことがいえる．
• 60%以上の改悪受理確率には有効性は無い．
• 初期点と目標点の違いが明確であり，目標 への道筋がはっきりしているものについて
は改悪方向への推移は有効でない可能性が 高い．
• 目標への道筋が明確にわからない場合，あ る程度の改悪方向への推移は目標への到達 を早める可能性がある．
2. 2 設計変数の場合
2 設計変数の場合では改悪受理率 20%が最も探 索数が少なくなり，山登り法が目標点への到達率 で最も高くなっている．2 変数になったことによ り 1 変数のときよりも色空間が複雑な構造になっ ていると考えられる．
山登り法は少しずつ変化をして目標に向かって 推移していくので目標に到達する確率は高くなる が，そのためにかかる探索数は多くなってしまう．
一方，改悪を受理する場合はユーザが判断した目 標の方向へ遷移しない場合がある．色空間が複雑 になることで改悪の受理が役立つことがあると考 えられる．
以上の結果より以下のことがいえる．
• 改悪受理確率 20%のときが最も効率が良い．
• 問題が複雑になると山登り法では多くの探 索数を必要とする．
• 複雑な問題においては少しの改悪方向への 推移がある方が効率よく探索を行うことが できる．
この実験より，目標への道筋が明確なものについて は山登り法が最も良い結果になった．しかし，2 変数 以上のような複雑な探索空間の場合ではある程度の改 悪方向への受理が良好な結果をもたらすことがわかる．
これより ISA において最も効率の良い探索は改悪受
理確率が 20%のときであるとする．
6. 主観的評価実験と考察 6.1 主観的評価実験
主観評価実験とは各被験者の主観的判断によってい くつかの事物を評価する実験方法である．主観評価実 験では，各被験者が ISA システムと 山登り法を用い たシステムの 2 つのシステムを操作し，比較評価を行 う．
実験に用いた被験者は 20 人とし，実験を行った．各
被験者は，提示された教示にしたがって 2 つのシステ
ム（ISA システムと 山登り法を用いたシステム）を
操作し，用意された回答用紙に記入する．また，被験 者は 20 歳代前半の男女で，実験の理解には問題ない．
実験の手順を以下に示す．
1. システム A を操作しそのシステムについて評価．
2. システム B を操作しそのシステムについて評価．
3. 2 つのシステムを比較して評価．
まず，ユーザは自分の好みの配色を考え，初期解を 生成する．この初期解をもとにして システム A，B を 使用して，より自分の好みに合うようなデザインを作 成する．システムにより生成される解候補に対する評 価はユーザの「好み」を基準として評価を行なう．現在 の解候補が ”Current” に，次状態の解候補が ”Next”
に掲示され，ユーザは現在の解候補に対して次状態の 解候補の良い&悪いの評価を行う．この操作を 50 回 繰り返した時点で終了とする．
2 つのシステムを用いて好みのデザインを作成した後 2 つのデザインを比較し，回答用紙に記入する．本実 験では，以下の 2 つの項目について検証を行った．
1. ISA システムと 山登り法を用いたシステムで形
成した設計解の比較．
2. ISA システムにおける改悪遷移の設計解への影響．
上記の 2 つの項目について検証を行うための検定項 目について以下に説明する．
6.1.1 符号検定
ISA システムの有意性を検証するために，ISA シ ステムと 山登り法を用いたシステムで形成できる設 計解の比較を行った．この比較には符号検定 10) を利 用した．符号検定 10) とは，少ないサンプル数で異な る 2 つの事象における有意義を検定する方法である．
2 つのシステムを操作後，被験者は以下の質問に回答 する．
• あなたにとって好みに合うデザインを形成できた のはどちらのシステムであるか．
• ISA システムにおいて改悪方向への遷移が設計解 を形成するのに役立ったか．
この質問に対する回答を符号検定によって解析する．
6.1.2 改悪遷移の影響
ISA システムと 山登り法を用いたシステムの最も 大きな違いは改悪方向への遷移を行うか行わないかで ある．この ISA における改悪方向への遷移が設計解 の推移にどのような影響を与えているのかを検証する ために，ISA システムと 山登り法を用いたシステム における設計解の推移の履歴を取り，この履歴をもと に改悪方向への遷移が行われたときに設計解に起こる 変化を検証した．検証方法としては各アニーリングス テップにおける 4 つの設計解の推移を HUE と TONE の 2 つに分けて行なった．
6.2 実験結果 6.2.1 符号検定
符号検定の結果を Table 5 に示す．被験者のうち最初 の 10 人は初めに ISA システムを行い, その後に 山登り 法を用いたシステムを行なった（ISA - Hill-Climbing）．
残りの 10 人は 山登り法を用いたシステムを先に行い，
後に ISA システムを行った（Hill-Climbing - ISA）．
以後 ISA システムを ISA，山登り法を用いたシステ ムを Hill-Climbing と表記する． Table 5 に示すよう Table 5. Results of Sign Tests (about The Bbetter Design Solution).
ISA Hill-Climbing ISA - Hill-Climbing 6 4 Hill-Climbing - ISA 9 1
Total 15 5
に，設計解に関して，良い設計解の形成を行うことが できたシステムはどちらであるかという質問をしたと ころ，回答結果を用いた 20 人中 15 人から ISA シス テムの方が山登り法を用いたシステムより良い設計解 を形成できたという回答を得た．この実験では，符号 検定により危険率 5% での有意差が認められた．
Table 6 に ISA システムおける改悪方向への遷移 が設計解を形成するのに役立ったかという質問にたい して 5 段階評価の回答を求めた結果を示す． Table 6
Table 6. Score and The Number of People.
Score 5 4 3 2 1
The Number of People 2 9 5 3 1 Average of Score 3.777778
より 4 の評価が一番多かった．また，5 の評価を 2 人
から得ることができた．この結果より被験者のうちの
半数以上の被験者から改悪方向への遷移が設計解を形 成するのに役に立った．もしくは，少しは役立ったと いう回答が得られた．評価の平均は 3.8 となり，良好 な結果が得られた．
6.2.2 改悪遷移の影響 1. 各設計解の推移
ISA における改悪方向への遷移が設計解の推移にど のような影響を与えているのかを検証するために，両 システムの ”Current” 状態の設計解の履歴を取った．
設計変数 ”jacket” の結果を以下の Fig. 9 に ISA が 良いと答えた被験者の履歴を， Fig. 10 に 山登り法 が 良いと答えた被験者の設計解の推移を示す．各グラフ は縦軸に TONE および HUE を，横軸に探索ステッ プを示している．なお，”jacket” 以外の設計変数につ いても同様の結果が得られた．
㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇㫊
0 5 10 15 20 25 30 35 40 45 50
㪟㪬㪜
㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇㫊
㪫㪦 㪥 㪜
0 5 10 15 20 25 30 35 40 45 50
Uphill Transition
㪠㪪㪘 㪟㫀㫃㫃㪄㪚㫃㫀㫄㪹㫀㫅㪾
㪠㪪㪘 㪟㫀㫃㫃㪄㪚㫃㫀㫄㪹㫀㫅㪾 Uphill Transition
Fig. 9. History of Solutions (ISA Good).
Fig. 9 および Fig. 10 を見ると，ISA が良いと 答えた被験者は 山登り法 が良いと答えた被験者より ISA，山登り法 の両システムを用いたときでの設計解 に変動があることがわかる．特に改悪方向への遷移が 行なわれたときに設計解が変動していることがわかる．
一方，山登り法 が良いと答えた被験者に関しては，設 計解に変化があまり見られなかった．
2. ステップ数と改悪受理率
アニーリングステップ数と改悪受理率の関係を Fig.
11 に示す．
㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇㫊
㪟㪬㪜
㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼㫇㫊
㪫㪦 㪥 㪜
Uphill Transition
㪠㪪㪘 㪟㫀㫃㫃㪄㪚㫃㫀㫄㪹㫀㫅㪾
0 5 10 15 20 25 30 35 40 45 50
0 5 10 15 20 25 30 35 40 45 50
Uphill Transition
㪠㪪㪘 㪟㫀㫃㫃㪄㪚㫃㫀㫄㪹㫀㫅㪾
Fig. 10. History of Solutions (Hill-Climbing Good).
㪇 㪇㪅㪇㪌 㪇㪅㪈 㪇㪅㪈㪌 㪇㪅㪉
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㪪㫋㪼
㪘㪺㪺㪼㫇㫋㩷㪩㪸㫋㫀㫆
㪬㫇㪿㫀㫃㫃㩷㪫㫉㪸㫅㫊㫀㫋㫀㫆㫅
0 5 10 15 20 25 30 35 40 45 50
Fig. 11. Transition about Accept Ratio of Uphill Transirion.
Fig. 11 より，改悪遷移確率はステップ数の前半が
高くなっており，20 回目以降は改悪受理率は 5%以下 になっており，ほとんど改悪方向への遷移が行なわれ ないとこがわかる．実際に，20 回目までで改悪方向へ の遷移が行なわれており， 20 回目以降では改悪方向へ の遷移は行なわれないという結果になった．
6.3 考察 6.3.1 符号検定
Table 5 から符号検定において ISA システム と 山 登り法を用いたシステム によって形成できる設計解
に危険率 5%の有意差があった．
ISA システムの目的は，ISA の特徴である改悪方
向への遷移がユーザにとってどのような影響を与えて
いるかである．アンケートの結果より，改悪方向への
遷移は少なからずも設計解を形成する際に影響をもた らしているといえる．しかも半数以上のユーザが役に 立ったという結果から有効性が期待できる．
また，Table 5 から 2 つのシステムの比較を行なう 場合，システムの操作順序が回答結果に大きく依存す ると考えられる．実際に Table 5 から，後に操作した システムの方が良好な結果を得ている．この理由とし て後に操作するシステムでは，1 回目のシステムで得 られた設計解のイメージをもとに更に良い設計解を形 成しようとする傾向があると考えられる．そのため，
結果的には 1 回目に形成した設計解に比べて良い設計 解が形成できたような印象を受けるものと考えられる．
6.3.2 改悪遷移の影響 1. 各設計解の推移
Fig. 9，Fig. 10 からわかったことは，山登り法 が 良いと答えた被験者については，初期解で生成した解 が被験者の好みを強く反映しているため，初期解から あまり動かないという点である．一方，ISA が良いと 答えた被験者に関しては，初期解と最終解がまったく 異なることが確認できた．つまり，被験者は探索を進 めながら好みが変化していき，初期解とは異なった好 みを発見できたと考えられる．
Fig. 10 より，改悪受理が行なわれた後は変化して
いるが，最終解では初期解に類似した解に戻っている．
この結果から，山登り法 が良いと答えた被験者，つ まり，初期解が好みに合っているユーザに関しては改 悪受理はあまり有効ではないと考えられる．
Fig. 9 では 3 回の改悪方向への遷移が行なわれて
いる．この改悪受理において，1 回目の改悪受理から 次の改悪受理までの間は改悪受理された設計解と類似 した設計解が選択されている．この結果より改悪方向 への遷移によって好みが変動したことがいえる．ISA が良いと答えた被験者に共通していえることが初期解 と最終解とが大きく異なっていることから改悪方向へ の遷移は有効に働いていると考えられる．
以上の考察から， ISA における改悪方向への遷移は 人の感性に関して有効であると考えることができる．
2. ステップ数と改悪受理率
Fig. 11 より，改悪方向への遷移が行なわれたのは
探索の前半部分であることがいえる．一方，後半部分 では改悪受理が行なわれていない．この結果から， ISA では探索の序盤では比較的改悪遷移が行なわれるが，
探索が進むにしたがって，改悪遷移が行なわれる確率 はかなり低くなることがいえる．
以上の考察から，改悪方向への遷移はユーザに対 して設計解を変動させるきっかけを与える効果がある．
その設計解の変動に対して有効に働くか否かはユーザ によって異なることがわかった．
7. 結論
本研究では，対話型シミュレーテッドアニーリング の提案を行い，その有効性を検証した．有効性を検証 するために「服装カラーコーディネート支援システム」
を構築し，被験者を用いて ISA システムと山登り法 を用いたシステムの比較実験を行った．その結果，得 られた結論を以下に示す．
1. 本実験では，対話型進化計算法 (IEC) における 新たなアプローチである 対話型シミュレーテッ ドアニーリング (ISA) を提案した．
2. ISA システムと 山登り法を用いたシステムによっ
て形成される設計解に関しては，符号検定 10) に より，危険率 5%で ISA システムに有意な差が あった．
3. ISA システムにおける改悪方向への遷移はユーザ
の設計解を変動させるきっかけを与える効果があ ることがわかった．これは設計解を形成するにあ たり有効に働く場合がある．
以上の結論から，本実験で提案した ISA の有効性
を確認することができた．今後の課題としては他の対
象問題へ ISA を適用し，有効性を検証すること．ま
た， ISA は IGA に比べ 多様性に欠ける，このため多
様性が必要な場合には IGA とのバイブリッド化など
の改良が必要である.
同志社大学理工学研究報告 第 44 巻 第 1 号，
pp. 13-24，2003 年 4 月
問い合わせ先：
同志社大学工学部
