対話型遺伝的アルゴリズムを用いた
室内レイアウトシステムの開発
コンピュータサイエンス専攻1年
趙 冬青
1
研究の背景と目的
 従来システム
 提案システム
 インタフェース部の開発

2
3
レイアウト問題とは家具を部屋内に制約
条件を満たすように配置する問題である。
 その配置にはドアや窓の位置、家具の配
置順番、家具の向きなどを考える必要が
ある。

テーブル
ソファー
4


清水,「遺伝的アルゴリズムを用いた室内レ
イアウトシステム」(2001):
通常のGAに基づき突然変異の後にヒューリス
ティック演算を導入した。
徐,「遺伝的アルゴリズムを用いた室内レイア
ウトシステムの開発」(2004):
対話型室内レイアウトシステムを提案した。探
索能力が高く、対話型インターフェースを介して
修正が可能である。
5
6
作業
スペース
部屋の平面図:
家具:
右
下
上
小さい正方形で区切り、
家具はブロックを基準に配置
7
1
2
3
4
5
6
7
8
9
部屋・家具番号
A
1
6
5
3
B
2
7
4
家具の向き
―
↓
↑
→
←
―
←
↑
↑
配置順
1↓
6↑
5→
5→
3
←
1↓
6↑
A,B:部屋
1~7:家具
8
交叉
親1
親2
子1
交叉は一点交叉で、交叉
ポイントまでは親1の遺
突然変異
伝子をそのまま用いる。
交叉ポイント後の遺伝子
は、親2の交叉ポイント
後の遺伝子で重複せず同
じ場所配置できるものは
そのまま配置する。
次に、配置できなかっ
たところは、親2の遺
伝子で使われていない
ものを左から順番にう
交換
めて行く。
9
初期集団の生成;
for(世代数の上限まで){
全個体の適応度を計算する;
選択;
交叉;
突然変異;
}
ユーザによる修正;
10
分類
制約
違反点数
C01
家具は室内に配置
50
C02
窓をふさぐ配置を行わない
10
C03
壁際に配置すべき家具は壁際に配置
10
C04
類似・関連する家具は近くに配置
10
C05
出入り口に家具を配置してはいけない 10
11



ある家具の配置が制約に違反していると
きに適応度を次の式で計算する。
Fitness=違反点数の合計;
この違反点数の合計を最少化することが
本システムの目的である。
12
探索が終了したあとでユーザによる修正
を行っている
 ユーザの好みを十分に反映できない


対話型進化計算を用いて探索の途中で
ユーザの好みを反映する方法を提案する。
13
14
⓵初期集団の生成
⓶各レイアウト案をユーザに提示、評価を受け取る
⓷評価を探索に反映
評価
⓸次のレイアウト案集団を作る
15
ユーザの評価負担を低減し、なおかつ、
ユーザの好みに合ったデザインを得るた
め、島モデルを用いる。
 集団を複数に分けることで、部分集団ご
とに計算機を割り当てることによる並列
化が容易となる。

16
初期個体集団
島
独立に進化する
移住
個体の交換で行う
17
突然変異
率大きく
ユーザが気に入ったレイアウトを含む島を選択する
18
19
家具の追
加
進化計算
評価
20
21
22
23
24
まとめ
従来手法を調査した
対話型システムを提案した
インタフェース部を開発した
 今後の予定
島モデルGAのプログラムの開発
インタフェースの改良
評価実験

25
ダウンロード

プレゼンテーション