】……＝‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖‖＝‖＝‖＝‖‖‖‖‖‖‖‖‖刑Ill……l……l……l…llll……ll…………ll……l……l…llll…lllll…ll…lllll…lll…lll…lllll…llll…ll……………l…llll………l……lll…………【ll……1……l…l……lll…l……ll…

経験知識を最適化問題へ利用する際の諸問題について−システムの構築体験から考える−
岩谷 敬治，小西 正窮
Illl……l……l‖＝＝‖Wll……l…lllll‖‖‖‖‖＝＝‖‖‖＝＝‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖＝‖‖＝‖‖＝‖‖‖‖‖‖＝‖‖‖＝＝‖‖‖‖‖＝‖‖‖＝州Il……tllll…‖‖‖＝‖‖‖‖州Illl‖＝‖‖＝‖‖‖州Illl……l…l………l…川………llll…llll…l………ll………lる（図1）．コイル状に巻き取られた冷延鋼板（以下1．緒言コイル）は人側から引き出され，ロールに導かれて熱本事例報告では，1990年代前半におこなったスケ処理炉を通過した後，出側で再びコイル状に巻き取らジューリングシステム構築の体験を基に，最適化問題れる．なお，処理中のコイルの後端と次コイルの先端に対し経験知識を利用する際の問題点を議論する．まを人側の溶接機で接続し，通板を連続的におこなうこず2章で問題対象とした連続焼鈍設備（以下，とが，CALの操業上重要である．

CAL：ContinuousAnnealingLine）のスケジュー1）

上位の生産管理システムからCALに対し，翌日にング問題と数理計画法の適用限界を述べ，次に3章で処理すべきコイル約100本の情報が，投入指令としては熟練者の問題解決方法とそれを用いてシステム化し発行される．投入指令および後述する他の情報から，た際の問題点を示し，4章では実用化に至ったスケジ

焼鈍順序を決定する問題を投入順問題と呼ぶ．各コイ

ューリングシステムの枠組を示す．そして，5章では，

ルは幅，厚み，鋼種等に違いがあり，処理順は生産性，計画の対象が日々変化する実際の最適化問題には，知品質等に影響を与える．

識工学手法は本質的に対応が難しい事を示す．最後に

2．2 投入順問題の制約条件とプール材，ダミー材

6章では，実用性の観点から，知識工学手法や数理計連続して焼鈍する2本のコイルは，設備上の限界に画法の今後の展開に対する期待を述べる．2〜5章で用いたアルゴリズムの詳細や適用結果は，過去の文献［1］を参照して頂きたい．

より次の条件を満足する必要がある．
1佑月（紺わfz，ゐど）≦細目≦‰（肋，fゎぁど）
ここに，なお，本論では 最適化問題 という言葉を評価関数の値を重視する計画問題という意味で使用している

紺わ′言，ゐf：才番目のコイルの幅，厚み，焼鈍温度
帆β，仲㍍：グ番目のコイルに接続可能なコイル幅の点を最初にお断りしておく．

下限と上限．

なお，厚み，焼鈍温度にも同形式の制約が存在する．

2．対象とする問題の概要

これらの条件を満たす2本のコイルを接続可能と呼ぶ．

2．1CAL［2］とその投入順問題の概要

投入指令に対して，あるコイル（あるいは，複数のコCALは冷延鋼板の熱処理を連続的に行う設備であイルからなるコイル集■合）が他のコイルのいずれにも接続できないと，連続通板が必要なCALにとって重大な問題となる．その対応方法は2種類存在する．一熱処理設備

つは接続不可能なコイルの焼鈍処理の延期である．処理を延期されたコイルをプール材と呼ぶ．今一つは，ダミー材と呼ぶ接続専用コイルを用いる方法である．
図2に示すように，コイルAとBは接続できないが，ダミー

図1CAL（連続焼鈍設備）概要

コイルⅩをその間に挟むことで，（1）式を満足するようにするのである．

このように，投入指令，ダミー材，及び蓄積していいわたに〒65ト2271神戸市西区高塚台1−5−5
こにし まさみ 岡山大学工学部〒700−8530岡山市津島中3−1−1
610（24）るプール材の情報から焼鈍順序を決定する事が，CALの投入順問題となる（図3）．
なお，1日に焼鈍できるコイル数には下限凡と上© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ（1）∬古から∬z＋1に接続した時に一定倍以上幅が増鋼板進行方向加する場合・は1．それ以外は0．
接続不可能 †長：後処理変更の有無
加≠動＋1ならば1．それ以外は0．

ダミーコイルX

ム：必要なダミー材数∬古から∬汗1に接続する場合に（1）式等の制約を満足するために必要なダミー材数．
ム：速度変更の有無

図2 ダミーコイルの概念∬どから∬g＋1に接続する場■合通板速度が一定倍以上変化する場合1．それ以外0．
αざ：各項目に対する重み．
である．
2．4 投入順問題への分枝限定法適用
昨日の投入順
結果からCAL投入順問題は（1），（2）式を制約条件，（3）式を評

明日の投入順問題へ価関数とする組合せ最適化問題となり，分枝限定法の

図3 投入順問題の入出力適用が考えられる［3］．分枝限定法の求解効率は，有効な下界値導出法の有無等に依存する．たとえば，巡限凡があるので，投入順に含まれるコイル数Ⅳは回セールスマン問題［4］（以下，TSP）には種々の手以下の制約を満たす必要がある．

法［5］が提案されており，相当規模の問題も高速に解

凡≦Ⅳ≦凡

（2）

ける．投入順問題はTSPに類似するが，（2）式のため2．3 投入順の評価関数

巡回都市数の上下限しか与えられていないTSPとい（1）品質への影響（幅アップ回数最小化）える．その結果，巡回都市の選択問題も含むために，（1）式を満足しても，連続するコイル間で幅が広がる

複雑性は高くなる．また，評価関数ムやムが示す通と品質に影響を与える可能性がある．そのため，一定

り，コイルCl→C2→C3と接続した場合の評価値値以上の幅アップとなる接続は少ない程よい．

がコイルCl→C3と接続した場合・より小さくなる可能性がある点でも通常のTSPとは異なる．

（2）操業者の負荷（後処理変更回数最小化）

これらの理由のため，TSPで有効な探索手法が利焼鈍後のコイルに施すべき後処理はコイルによって異なり，その変更は操業者の負担となる．したがって，用できない．そのため，当時のワークステーションで後処理の変更回数は少ない程よい．

1時間以内に最適化できる投入順問題の規模は十教本程度であった．

（3）生産性（ダミー材数最小化，速度変更最小化）
生産性の悪化要因は2種類ある．ひとつはダミー材

3．熟練者の問題解決方法とシステム化のの数であり，その理由は明白である．いまひとつは連問題点続する2コイル間での炉内通過速度の変化である．通過速度が異なるコイルが連続する場合，接続点近辺で3．1熟練者の問題解決方法は速度を低速側に合一わせる必要があり，生産性を阻害

投入順問題に対し，熟練者は1−2時間で高レベルな解を導出している．そこで，彼らの作業プロセスをする．これらを定式化すると以下のようになる．
Ⅳ−1（3a）ダ（∬）＝∑／（∬ゎ∬汗1）

z＝1

ステップ1．プール材の決定′（∬ど，∬z＋1）＝α1ム（∬ゎJ汀1）＋α2ム（∬z，∬机）＋α3ノも（∬ゎ∬g＋1）＋α。ム（∬ゎ∬汗1）（3b）
ここに，作業の対象とするコイルを固定する．
ステップ1で当日の焼鈍を決定したコイルを数種類か：オ番目のコイルにおける後処理の内容．

1999年11月号

まず，熟練者は最初にプール材を決定し，順序作成
ステップ2．コイルの大グループへの分割

Jど：投入順におけるグ番目のコイル．
力：幅アップの有無分析した．のグループ（以下大グループ）に分割する．
ステップ3．幅アップ部分の作成© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）『‖

各大グループで最も幅の狭いコイルと広いコイルを

3．2 経験知識によるシステム化の問題点選択し，その間をなるべく少数のコイルで接続する．

前節で示したプロセスをモデル化してシステムを構

このようにして作成した数本のコイルは，各大グルー築したが，導出できる解は熟練者のレベルに遠く及ばプの先豆引こ持ってくる（以後，この部分を幅アップ部なかった．その理由を以下に示す．

分と呼ぶ）．これにより，残りの大部分のコイルで幅計画問題では，計画対象内容によって経験知識の有アップが生じなくなる（以後，幅ダウン部分と呼ぶ）．

効性が左右される．計画対象内容とは，投入順作成の投入順序によるコイル幅の変化と大グループの意味を対象となる投入指令，ダミー材，プール材の構成内容

図4（a）に示す．

である．たとえば，ステップ5には，次のような経験

ステップ4．小グループヘの分割知識が存在した．

各大グループの幅ダウン部分を更に数グループ（以IF下小グループ）に分割する（図4（b））．

最後端のコイルが鋼種Vl，幅月imm，厚みれmm

THEN 次に接続するコイルは鋼種VlまたはV2，

ステップ5．小グループの順列作成

かつ幅が昂−ゐ1mm以下，かつ厚みは右各小グループ内の順列を経験知識を利用しながら試±flmmの範囲内とする．

行錯誤的に作成する．

単純な問題は，計画対象内容によってはTHEN部

ステップ6．調整
ステップ1〜5で全体の投入順は完成する．しかし，分を満足するコイルがないことである．より複雑な問改善が必要と判断した箇所を入れ替え等で修正する場

題としては，このルールを適用してあるコイルを使っ合がある．また，途中の各ステップでも，低レベルなたために，その後の投入順で本来ならば不要なダミー解しか導出できないと判断し，それ以前のステップに材が必要になることが考えられる．このような場′合に戻る場ノ合もある．

は，このルールは有効ではなかったことになる．
熟練者の知識は，多くの場合の計画対象内容において有効であり，9割以上の確度があったと考えている．
しかし，1問題の解決に発火する知識は十数個にのぼる．そのため，9割程度の確度では実用に耐えうる投入順は作成できない．

4．構築したスケジューリングシステム
本章では最終的に実用化に至ったスケジューリング

a）大グループとその幅アップ部分．幅ダウン部分

システムの概要を示す．

大グループ1
小グループ1小グループ2小グループ3小グルー
皆Cミ†∩

4．1アルゴリズムの概要構築したシステムは3モジュールからなる（図5）．
モジュール1では，熟練者の経験知識をそのまま利用して作業ステップ1，2，3を実行する．それにより，幅アップ部分

焼鈍順序

幅ダウン部分

（机大グループ内の小グループ

各大グループの幅ダウン部分の順序決定問題が複数個残る．モジュール2では，それらを（3）式の評価関数

図4 焼鈍順序と幅の関係を変形することでTSPに変換し，分枝限定法を用い投入順問題

解

図5 スケジューリングアルゴリズムの3モジュール
612（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ（4）他l通常の推論機能

図7 熟練者の作業方法と通常の推論機能

図6 近傍探索アルゴリズムによる解の改善が必要になったとすれば，熟練者は小グループ内で投て解く．その結果一応完成した投入順を，モジュール入順序を組み直したり，小グループへの分割方法を変3で近傍探索アルゴリズムを利用して改善する．モジ更したりする．熟練者が短時間でレベルの高い投入順

ュール3のフローを図6に示す． 問題箇所設定 でを作成できるのは，作業をやり直すステップの決定がは，評価関数の′（∬ゎ∬机）の値が大きい上位研箇所的確なためと考えられる．つまり，得られた解（あるを選択し，近傍作成では 他コイルの挿入いは，得られるであろう解）を評価した上で，適切に， 入換バックトラックをおこなう能力が熟練者が熟練者たるえ 等をおこない，解を漸次改善した．
4．2 実機適用

本当の理由である．それゆえ熟練者は100％正しい知上記アルゴリズムの適用により，熟練者レベルの解識を持つ必要がない．（4）式に示したルールのIF条件の導出が可能となってきた．そのため，実用システム部やTHEN実行部を複雑にすれば計画対象内容に依を構築し，システムと熟練者の解の比較に基づくシス存しないルールとなるかもしれない．しかし，完全性テム改良作業を継続した．熟練者レベルの解を常時導を必要としない熟練者からの知識獲得では，難しい作出するシステムとするには多くの改良が必要であった業と考える．

が，経験知識，分枝限定法，近傍探索という枠組みに5．2 不完全な知識ベース下での推論手法の検討変更はなかった．本システムは1993年に実機化され，熟練者の知識と作業方法の関係を図7（a）に示す．熟練者から抽出した不完全な知識ベースでも，図7（a）に1999年現在でも利用されている．

示す評価機能，バックトラック機能があれば熟練者並

5．考察

みの解は導出可能となる．不完全な知識べ岬スを用い投入順問題に対し，試行錯誤の末に，数理計画法とる推論手法としては，確信度推論やファジィ推論［6］知識工学手法を結合する形で実用化システムの枠組みも提案されている．しかし，その動作は通常の推論シを構築した．その体験に基づき，最適化問題に対するステム同様，図7（b）のように開ループ的である．推論

経験知識の利用方法について考察する．

結果を論理処理とは別の角度から 評価 して，不適5．1最適化問題に対する知識獲得の限界

切ならば推論をやり直す推論制御の仕組みがない点で，計画対象内容によっては熟練者から抽出した知識は熟練者の作業方法と根本的に異なる．

不適切になるのに，なぜ熟練者自身は高レベルの投入視点を変えると，図7（a）に示した熟練者の作業手順順を作成できるのであろうか？ それは，ステップ5，は，実用に耐えうる解を求めるために，計画対象内容6で示したように，試行錯誤的に作業をおこなうからによっては真でない知識を含む知識ベースの中から，である．（4）式で示すルールを用いた後，ダミーコイル用いるべき知識の部分集合を試行錯誤的に決定するプ

1999年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）613ロセスと考えることができる．それに一番近い推論方

複数の数理計画モジュールと知識処理モジュールが相法は仮説推論［7］であろう．仮説推論で利用する知識互に呼び出しあう方法などが提案されている．

ベースも真でないものを含む事を特徴とする．その上

しかし，そのような複雑なシステムを実用化した場で，与えられた命題を導出できるように，知識ベース合・，計画対象内容の変化によって低レベルな解しか得の部分集合を試行錯誤的に求めるプロセスが仮説推論られなくなった時にシステムのチューニングは可能なといえる．つまり仮説推論において， 証明を求めらのだろうか．問題なのは経験知識か，数理計画法か，れる命題 を 評価関数最適化

それらの融合方法か，単なるプログラムのバグなのかに置き換えた推論機構が，熟練者の作業プロセスとなるが，実現は難しい判断は難しい．ESに対する保守性の問題点の指摘のではないだろうか．

［9］は多いが，融合した場合は更に問題となる可能性

一般に，推論という技術パラダイムが，正しい知識がある．

を抽出し正しい論理処理を実行すれば正しい結論が得

その点，本間題に用いた図5に示す構造は，各モジられるという，開ループ的な発想に基づいているのな

ュールの役割分担が明確で相互の影響が少ないので，らば，計画対象内容に応じて試行錯誤が必要な最適化保守が可能であったと考えている．実際，本システム問題解決の中核にはなれないであろう．本問題で利用が利用され続けているのは生産現場スタッフと熟練者したような，少量の知識を用いた前処理的な役割が限の多大な努力の賜物であるが，この単純な構造も多少界ではないだろうか．

は寄与していると考えている．

5．3 数理計画法を生かす経験知識

6．2 数理計画法とその周辺技術

多数にのぼる全経験知識から不完全性を除去するの5．3節では数理計画法を活用する観点からの経験知は困難であるが，問題解決に必要不可欠な知識に絞れ識の取捨選択が重要であることを主張した．苦から数ば可能かもしれない．必要不可欠な知識とは，原問題

理計画法を用いたシステム構築には，陰に陽に経験知を数理計画法で解ける問題に変更する知識である．そ識が利用されていたと考えるが，その利用方法論は存のような知識は何通りでも考えられるが，選択基準と在しなかった．ESの流行で初めて知識獲得方法が議して次に示す分類を考える．

論されるようになったが，そこには数理計画法から見知識1：効率的なアルゴリズムの通用が可能なようた知識の有用性という視点が欠けている．
この議論を一般化すると，数理計画法の多くの周辺に問題構造を改善し，解の導出速度を向上

技術を数理計画法の立場から整理する必要を感じる．

する知識

知識2：探索範囲を限定し，解の導出速度を向上す

たとえば，エーザインタフエース構築技術も計画システムには重要である．手動での組み直し機能が充実しる知識

知識1を適用した場合，導出される解のレベルは変ていればシステムの導出解のレベルは多少悪くてもよ化しない．しかし，知識2の場合には，解の探索範囲いという議論さえある．しかし，自由度が高いインタを人間が解けるまで限定するためその保証はない．

フェースと整／合性をとるために，アルゴリズムの追加

熟練者の知識をこのように厳密に区別することは難に苦労するという本末転倒な問題も，筆者には経験がしい．しかし，敢えて分類すればプール材の決定知識ある．また，計算機環境の変化もインタフェース部分

は知識1の意味合・いが強く，本間題のシステム化に必に問題を発生させる場ノ合が多い．2000年間題でOS須といえる．また，大グループヘの分割知識，幅アッのバージョンアップが必要になり，その結果，インタプ部分の作成知識は知識2の意味合いが強いが，ルーフェース部分だけが動作しなくなるケースも考えられル数が少なかったためチューニングが可能だったと考る．

経験知識やインタフェースは計画対象内容や計算機える．

環境への依存性が高く，それに比べて数理計画法は普6．実用性から見た諸技術遍性が高いことを考えると，計画システムの中心は明6．1数理計画法と知識工学手法の融合手法らかである．しかし，周辺技術が不可欠であることも数理計画法と知識工学手法の融合方法については議確かであり，またそれらは計画システムユーザの興味論［8］も多く，複雑な融合方法も提案されている．たを引きやすい．周辺技術を中心技術の視点から整理し，とえば，知識処理の途中で数理計画法を起動する方法，利用してはいけない知識，作ってはいけないインタフェ

614（28）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ースを明確にしておかないと妙な逆転現象が発生する

焼鈍設備のスケジューリング；システム制御情報学会論のではないだろうか．

文誌，Vol．6，No．9，pp．387−395（1993）．
［2］伴，大蔵，宮原，大西，藤村，寺本：連続焼鈍設備と製品

6．3 メタヒューリスティックス
近年，筆者が所属する部署では計画問題に対するSA［10］（シミュレーテイッド・アニーリング）法，GA［11］（遺伝的アルゴリズム）法の利用例［12］［13］が多い．もし，今投入順問題を担当すればSA法を用いるであろう．その一番の理由は，一定レベルの解を出せるようになる確率の高さである．ある程度の解が出るようになると，関係者がより協力的になりその後の開発作業は加速する．の品質特性；神戸製鋼技報，Vol．33，No．4，pp．62−65（1983）．
［3］茨木：組合せ最適化；産業図書，pp．34−74（1983）．

［4］M．BellmoreandG．L．Nemhauser：TheTraveling
SalesmanProblem：ASurvey；OperationsResearch，

Vol．16，No．3，pp．538−558（1968）．
［5］山本，久保：巡回セールスマン問題への招待；朝倉書店（1997）．

［6］D．DuboisandH．Prade：Fuzzysetsinapproximate

計画問題に対して実用システム構築する場合の，こreasoning，Partl：Inferencewithpossibilitydistribuqのような実戦的要素の整理も数理計画法の普及には大tions；Fuzzy Sets and Systems，Vol．40，pP．143−202

事なのではないだろうか．

（1991）．
［7］石塚：不完全な知識の操作による次世代知識ベース・

7．緒言システムへのアプローチ；人工知能学会誌，Vol．3，No．

連続焼鈍設備のスケジューリングシステムを構築した経験から，最適化問題に経験知識を利用する際の問題点を議論した．本論の出発点は，実際の計画問題では計画対象内容がかなり変化するという事実である．
ここから熟練者の知識の完全性に疑問を持ち，更には知識獲得方法論，推論諸手法に対する不満につながった．また，論文などでは知識工学，数理計画双方から様々な手法が提案されるが，長期利用の視点から評価

5，pp．552−562（1988）．
［8］奈良：エキスパートシステムと数理計画法の融合による最適化；人工知能学会誌，Vol．8，No．3，pp．265−271（1993）．

［9］大力：エンジニアリングへの応用の実際；人工知能学

会誌，Vol．14，No．3，pp．389−392（1999）．
［10］S．Kirkpatricket al．：OptimizationbysimulatedAnnealing；Science，Vol．220，No．4598，pp，671−680（1983）．

がされない点も不満であった．そのため，本論が実用［11］Goldberg，D．E．：Genetic Algotithmsin search

性，保守性を重視し，学術性を軽視した議論となって

Optimization and Machine Learning；Addison Wes−

しまった点をご容赦頂きたい．

leyPublishing（1989）．

オペレーションズ・リサーチ学会に投稿させて噴く
上で一番心配し，半ば期待している点は，（1）〜（3）式で示した投入順問題に対する簡潔で有効なアルゴリズムの指摘である．本論の論旨には影響を与えないと思うが，読者諸賢のご意見を期待している．

［12］梅田，他：半導体製造工程におけるロット処理順序の計画方法；システム制御情報学会論文誌，Vol．9，No．12，pp．573−581（1996）．
［13］松田，他：SA法を用いた製品受注枠最適化システ

ム；第4回インテリジェントFAシンポジウム講演論文集，pp．19ト192（1993）．

参考文献［1］岩谷，他：経験知識と最適化手法を組み合わせた連続

1999年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）6柑