対話型進化計算法を用いたオフィスレイアウト支援システム

情報処理学会第68回全国大会
1L-7
対話型進化計算法を用いたオフィスレイアウト支援システム
細野克之 † 屋中 麻衣子 † 長名優子 ‡
†
1
東京工科大学 工学部情報工学科，‡ 東京工科大学 コンピュータサイエンス学部
はじめに
部屋情報の入力
・部屋のサイズ
オフィスなどの限られた空間に机，椅子，棚などを
どのように配置するかを考える際に，様々な条件を考
慮しながら実用的なレイアウト案を考えるのは決して
・柱のサイズ、位置
・使用用途
・入口のサイズ、位置
・印刷機の有無
・窓のサイズ、位置
・会議用スペース
として用いるか
・電源の位置
ユーザによる評価
グループ情報の入力
・使用人数
グループ内の配置案の作成
配置案の表示
・机のグループごとの
配置案の作成
2D表示
簡単なことではない．ユーザが入力した条件にあうよ
ユーザによる評価
うなレイアウトを自動的に生成し，提示してくれるよ
・会議用スペースの配置案
GAによる
レイアウト案の生成
・グループ間の距離
うなシステムとしては，遺伝的アルゴリズムを用いた
・選択
etc...
・交叉
レイアウト案の表示
オフィスレイアウト支援システム [1] が提案されてい
・突然変異
・適応度計算
評価するレイアウト案
の選択
る．このシステムでは，ユーザが机や棚などの什器の
種類や数をすべて指定してレイアウト案を生成するよ
・表示した配置案を評価
3D表示
・選択したレイアウトの
OpenGLによる3D表示
うなものになっている．このようなシステムはすでに
レイアウト案の分析
ユーザの評価の反映
オフィスにある什器を利用して，オフィスのレイアウト
対話型 G A
を変更することを考えるような場合には利用しやすい
ものである．しかし，新規に什器を購入することも含
めてレイアウト案をゼロから考えたい場合には，ユー
ザが配置する什器のサイズをすべて指定するのではな
図 1: システムのイメージ
く，グループごとの人数や使用用途などのおおまかな
価に反映することで，ユーザの望むようなレイアウト
条件から，配置する什器も含めてレイアウト案を提示
案を作成していく．提案システムの全体の流れを図 1
してくれるようなシステムが望まれると考えられる．
に示す．
本研究では，遺伝的アルゴリズムの評価の一部を
提案システムでは机などの什器をグループ (部署) 単
ユーザが行う対話型進化計算法を用い，グループごと
位でまとめて扱い，グループごとの配置案の組み合わ
の人数や使用用途などのおおまかな条件からレイアウ
せでレイアウトを表現する．グループごとの配置案は
ト案の生成が行えるようなシステムを提案する．
矩形で表現されるため，グループごとの配置案間の位
2
置関係をシーケンスペアで表現する．
オフィスレイアウト支援システム
提案システムでは，レイアウト案を図 2 のように
提案するオフィスレイアウト支援システムでは，遺
遺伝子の形で表現する．N 個のグループから構成さ
伝子の形でレイアウト案を表現し，選択，交叉，突然
れるレイアウト案を考える場合には，遺伝子の長さは
変異などの遺伝的操作を繰り返すことでレイアウト案
4N + 2 となる．遺伝子は，図 2 に示すように (1) グ
を作成する．提案システムでは，ユーザにより部屋と
ループ間の位置関係，(2) グループごとの配置案の番
グループの使用人数，使用用途の情報が入力されると，
号，(3) グループごとの配置案の向き，(4) 棚の配置
その条件に合うような複数のレイアウト案が遺伝的ア
案の番号を表す 4 つの部分から構成されている．グ
ルゴリズムを用いて生成される．このシステムは対話
ループ間の位置関係は，シーケンスペアで表現するが，
型進化計算法を用いたものであり，レイアウト案を生
シーケンスペアをそのまま遺伝子として表現すると交
成する際に，遺伝子で表現されたレイアウト案の評価
叉や突然変異により致死遺伝子が発生してしまうため，
の一部をユーザが行い，その結果を次の世代以降の評
シーケンスペアを順序表現 [6] に変換したものを遺伝
Office Layout Support System using Evolutionary Computation
Katsuyuki Hosono, Maiko Yanaka and Yuko Osana
(Tokyo University of Technology, [email protected])
子として用いる．また，印刷機を 1 つのグループに 2
2-155
つ以上配置しないように印刷機を配置するグループの
番号も順序表現を用いて表現する．
情報処理学会第68回全国大会
対応するレイアウト案
グループごとの
配置案の番号
グループごとの配置案の位置関係
グループごとの
配置 案の向き
棚の配置
案の番号
1 2 1 3 1 1 1 2 1 1 1 2 1 1
1 : そのまま
2 : 90度回転
グループ２
グループ１
グループ３
印
棚の配置案
グループ３
グループ１
窓
1
窓
窓
1
2
窓
窓
窓
1
2
窓
窓
2
ドア
ドア
グループ２
窓
1
印
3
窓
窓
4
窓
窓
印
2
3
窓
窓
ドア
窓
ドア
図 2: レイアウト案の遺伝子による表現
遺伝的アルゴリズムでは，より良い遺伝子を次世代
に残すために適応度を計算し，その値に応じて選択を
行う．提案システムでは，(1) グループの配置案への
ユーザの評価，(2) 印刷機の配置，(3) 会議用スペース
の位置，(4) 電源とグループの位置 ，(5) 遺伝子の表
現するレイアウト案 のコンパクトさを評価の基準と
して用いる．また，ユーザによる評価の結果を (1) 棚
の配置案や (2) 机のグループの位置関係に関して考慮
し，評価に反映させる．
3
計算機実験
図 3: 生成されたレイアウト案の例
提案システムの動作を確認し，有効性を示すために
計算機実験を行った．提案システムを用いて，様々な
条件下でレイアウト案を生成した．図 3 にその例を
示す．
4
おわりに
対話型進化計算法を用いたオフィスレイアウト支援
システムを提案し，使用人数や使用用途などのおおま
かな条件から，レイアウト案の生成の行えることを確
認した．
[3] 藤吉邦洋, 大村智一, 井尻堅大：“Simulated Annealing 法探索に適した Sequence-Pair によるパッ
キング解空間,” 電子情報通信学会技術研究報告,
VLD99-118, Vol.99, No.659, pp.9-16, 2000.
[4] 大村智一, 藤吉邦洋：“Sequence-Pair を用いたパッ
キングにおける矩形回転による面積最小化 – 局面
的なスライス構造の利用 –,” 電子情報通信学会技
術研究報告, VLD99-119, Vol.99, No.659, pp.1724, 2000.
[5] 藤吉邦洋, 村田洋：“L 型モジュールを含んだ矩形パ
ッキング問題に対する Sequence-Pair を用いたア
ルゴリズム,” 電子情報通信学会論文誌 A, Vol.J83-
A, No.5, pp499-510, 2000.
参考文献
[1] S. Hashimoto, K. Haruyama, T. Nakamura, T.
Nakajima and Y. Osana : ”Office layout support
system using island model genetic algorithm,”
Proceedings of IEEE Congress on Evolutionary
Computation, Edingburgh, 2005.
[6] J.J. Grefenstette, R. Gooal, B. Rosmaita, and
D. Van Gucht, : Genetic Algorithm for the
Traveling Salesman Problem, Proc. 1st. ICGA,
1985.
[7] 土谷裕一，善如寺香, 長名優子 : “遺伝的アルゴリ
ズムを用いたオフィスレイアウト支援システム,”
情報処理学会第 66 回全国大会講演論文集, 2004.
[2] 北野宏明: 遺伝的アルゴリズム, 産業図書, 1993.
2-156