対話型遺伝的アルゴリズムを用いた室内レイアウトシステムの開発 コンピュータサイエンス専攻1年 趙　冬青 「対話型遺伝的アルゴリズムを用いた室内レイアウトシステムの開発」と題しまして、コンピュータサイエンス専攻1年 趙　冬青が発表します。

発表の手順 研究の背景と目的 従来システム 提案システム インタフェース部の開発 発表の手順と致しましては、まず初めに、［研究の背景と目的」について述べます。次に、［従来システム、提案システム」について説明し、最後に「インタフェース部の開発」という流れで発表します

研究の背景と目的 まずは研究の背景と目的について説明します。

室内レイアウト問題とは レイアウト問題とは家具を部屋内に制約条件を満たすように配置する問題である。 その配置にはドアや窓の位置、家具の配置順番、家具の向きなどを考える必要がある｡ 室内レイアウト問題とは 　　レイアウト問題とは家具を部屋中に制約条件を満たすように配置する問題です。その配置にはドアや窓の位置、家具の配置順番、家具の向きなどを考える必要があります｡ 　　その図に示すように、緑色の枠（わく）は部屋を示します。それぞれの部屋にソファー、テーブルなど家具を配置します。 テーブル ソファー

従来研究 清水,「遺伝的アルゴリズムを用いた室内レイアウトシステム｣(2001): 通常のGAに基づき突然変異の後にヒューリス 　　ティック演算を導入した。 徐,｢遺伝的アルゴリズムを用いた室内レイアウトシステムの開発｣(2004): 　　対話型室内レイアウトシステムを提案した。探　 　　索能力が高く、対話型インターフェースを介して　 　　修正が可能である。 次に従来研究について説明します。 清水さんの遺伝的アルゴリズムを用いた室内レイアウトシステムという論文では通常のGAに基づき突然変異の後にヒューリスティック演算を導入（どうにゅう）することを提案しました。 徐さんの遺伝的アルゴリズムを用いた室内レイアウトシステムの開発という論文では対話型室内レイアウトシステムを提案しました。探索能力が高く、対話型インターフェースを介して修正が可能であるという特徴があります。

従来システム 次に従来システムとして徐さんのシステムについて説明します。

配置図 部屋の平面図： 家具： 右 左 下 上 小さい正方形で区切り、 家具はブロックを基準に配置 作業 スペース 　まず、配置図について説明します。　 　家具を配置する部屋の平面図を配置図と呼びます。 　配置図は、平面を小さな正方形で区切り（クリック）、この正方形を｢ブロック｣と呼び、家具はこのブロックを基準に配置します。 　家具は、作業スペースを含め、上、下、左、右4方向の向きをとることができます。この図において、メーシュ部分は作業スペースを表しています。 小さい正方形で区切り、 家具はブロックを基準に配置

解のコード化 A,B:部屋 １～７:家具 1↓ 1↓ 5→ 3← 6↑ 6↑ 5→ 配置順 1 2 3 4 5 6 7 8 9 　　配置順 1 2 3 4 5 6 7 8 9 部屋･家具番号 A B 家具の向き ― ↓ ↑ → ← 6↑ 1↓ 6↑ 5→ 3← 1↓ 次に解のコード化について説明します。 遺伝子は、部屋番号または家具番号ならびに家具の向きとします。 この図は部屋Aに家具1,6,5,3を、部屋Bに家具2,7,9の順に配置することを意味します。 配置図上には図の左上から右下に向けて部屋内に収まるように家具の配置順に従って配置します。 家具がはみ出した場合は下に配置します。 部屋Bについても同様の手順で行います。 5→ A,B:部屋 １～７:家具

交叉・突然変異 交叉 突然変異 交換 交叉は一点交叉で、交叉ポイントまでは親１の遺伝子をそのまま用いる。 子１ 交叉 親１ 親2 突然変異 交叉ポイント後の遺伝子は、親２の交叉ポイント後の遺伝子で重複せず同じ場所配置できるものはそのまま配置する。 次に、配置できなかったところは、親２の遺伝子で使われていないものを左から順番にうめて行く。 次に交叉、突然変異を説明します。 交叉は一点交叉で、交叉ポイントまでは親１の遺伝子をそのままもちいます。 交叉ポイント後の遺伝子は、親２の交叉ポイント後の遺伝子で重複せず同じ場所配置できるものはそのまま配置します。 次に、配置できなかったところは、親２の遺伝子で使われていないものを左から順番にうめていきます。 突然変異は、このように2つ遺伝子ランダムに選び、交換します。 交換

アルゴリズム 初期集団の生成； for(世代数の上限まで){ 全個体の適応度を計算する； 選択； 交叉； 突然変異； } ユーザによる修正； アルゴリズムについては、まず初期集団を生成します。次は全個体の適応度の計算、交叉、突然変異を世代数の上限までに実行します。 このアルゴリズムでは、ユーザによる修正は、探索が終わってから行います。

制約条件の例 分類 制約 違反点数 C01 家具は室内に配置 50 C02 窓をふさぐ配置を行わない 10 C03 壁際に配置すべき家具は壁際に配置 C04 類似・関連する家具は近くに配置 C05 出入り口に家具を配置してはいけない この表は、制約条件の例をしめしています。 家具が室内に配置という制約に違反すると違反点数50点が加算されます。 窓をふさぐ配置を行わないという制約に違反すると違反点数10点が加算されます。 また、壁に配置すべき家具は壁に配置しなければ違反点数10点が加点されます。

適応度の計算方法 ある家具の配置が制約に違反しているときに適応度を次の式で計算する。 Fitness=違反点数の合計； この違反点数の合計を最少化することが本システムの目的である｡ 次に適応度の評価方法について説明します。ある家具の配置が制約に違反しているときを次のように行います。違反している制約の違反点数の合計を適応度とします。この違反点数を最少化することが本システムの目的です。

従来研究の問題点と対策 探索が終了したあとでユーザによる修正を行っている ユーザの好みを十分に反映できない 対話型進化計算を用いて探索の途中でユーザの好みを反映する方法を提案する。 次に従来研究の問題点と対策について説明します。従来研究では、探索が終了したあとでユーザによる修正を行っています。このため、得られたレイアウトにユーザの好みを十分反映できないという問題点があります。そこで、本研究では対話型進化計算を用いて探索の途中でユーザの好みを反映する方法を提案します。

提案システム 次に提案システムについて説明します。

⓶各レイアウト案をユーザに提示、評価を受け取る 全体の流れ ⓵初期集団の生成 ⓶各レイアウト案をユーザに提示、評価を受け取る 提示 ⓷評価を探索に反映 評価 まず全体の流れについて説明します。 対話型システムは、まず初期集団を生成します。次にレイアウト案をユーザに提示して、ユーザから評価値を受け取ります。その評価に基づいて改良を行って次のレイアウト案集団を作ります。ユーザが満足するまで２番から４番の操作を繰り返します。 ⓸次のレイアウト案集団を作る

島モデルGA ユーザの評価負担を低減し、なおかつ、ユーザの好みに合ったデザインを得るため、島モデルを用いる。 集団を複数に分けることで、部分集団ごとに計算機を割り当てることによる並列化が容易となる。

島モデルGA 初期個体集団 島 移住 独立に進化する 個体の交換で行う 次に簡単に島モデルについて説明します。 (click)島モデルでは、初期個体集団を、 (click)複数の独立した島に分割します。以後、GAによる進化はそれぞれの島ごとに独立に行われます。これにより、集団全体での多様性が維持されやすくなります。各島は独自に進化をするのですが、島間で遺伝情報を交換する必要があります。各島間における遺伝情報の交換方法としては、 (click)従来、個体そのものを移動させる移住操作により行われてきました。

コピー 提案アルゴリズム 突然変異率大きく 選択 ユーザが気に入ったレイアウトを含む島を選択する 次に提案アルゴリズムについて説明します。インタフェースによってまず4個初期集団を生成します。次に100世代ごとに。そのレイアウトをコピーして後は各島が別の進化をたどるように突然変異率は大きく設定しておきます。 ユーザが気に入ったレイアウトを含む島を選択する

インタフェース部の開発 最後にインタフェース部の開発について説明します。

家具の追加 メイン画面 進化計算 評価 システムを起動するとまずこのようなメイン画面が表示されます。この部分には、現在のレイアウトが表示されます。一番目のボタンは、家具の追加のために使用します。次のボタンは進化計算を始めるために使用します。最後のボタンは、レイアウトの評価のために使用します。

家具の追加画面 この図は、「家具の追加画面｣を示しています。

家具の属性の選択画面 次に、配置したい家具のサイズを入力し、家具の種類、配置したい部屋を選べます。

他の家具の追加画面 ここを押すと追加用のウインドが開きます。。。。。。。。。

完成画面 追加完了の場合は進化計算ボタンを押すことで探索を始めます

結言 まとめ 従来手法を調査した 対話型システムを提案した インタフェース部を開発した 今後の予定 島モデルGAのプログラムの開発 　従来手法を調査した 　対話型システムを提案した 　インタフェース部を開発した 今後の予定 　島モデルGAのプログラムの開発 　インタフェースの改良 　評価実験　 以上をまとめますと、いままでに従来手法を調査しました、対話型システムを提案しました、インタフェース部を開発しました。 今後は島モデルGAのプログラムの開発、インタフェースの改良、評価実験を行う予定です。