日本財団 図書館


4. 障害物に対する評価値を優先的に改善する修正オペレータ
 GAの配管問題への適用において、パイプ本数の増加につれて、実行可能な解の生成が急激に困難になることは3.3節で述べたが、それと同時に、障害物に対する評価値がなかなか改善されない可能性がある。そこで、障害物との交わりを考慮することで障害物に対する評価値を改善する修正オペレータ(Modification Operator on Obstacle; MOO)を提案する。
 
4.1 MOOのアルゴリズムの概要
 障害物と交わっているパイプを優先的に修正し、全てのパイプができるだけ障害物を避けるように解を修正する修正オペレータのアルゴリズムの概要を以下に示す。
1. MOCを適用する。
a. すべてのパイプが障害物と交わっていなければ終了。
b. そうでなければ、ステップ2へ。
2. 障害物と交わっているパイプを全て再生成する。
a. すべてのパイプが障害物と交わっていなければステツプ3へ。
b. そうでなければ、このステップを繰り返す。このステップがβ回繰り返された場合、ステップ3へ。
3. このステップがγ回繰り返された場合、MOCを適用して終了。そうでなければ、ステップ1へ。
β:回避回数(avoidance number)
γ:修正回数(modification number)
 
4.2 有効性の確認
 MOOの有効性を確認するために、3.5節の配管問題に修正オペレータMOOを適用し、比較実験を行った。実験では、アルゴリズムは同じものとし、予備実験によりパラメータは初期集団の生成回数を20、交叉回数を20とする以外は同じものとした。MOOのβを100、γを100としている。Fig. 13、Fig. 14に示すように、MOOの効果により初期集団で障害物を避けた解を発見できている。評価時間はMOOを適用した場合の第100世代までの時間とMOOを適用した場合の第1000世代までの時間が大体同じであった。しかし、この時の評価値を比較すると、MOCを適用した場合のほうが良好な解を得ている。これは、探索のアルゴリズムの観点から考えると、障害物と交わっている解も有効な情報を保持している可能性があり、評価値を与えて実行可能解にすることで、探索の効率が上がる可能性を示している。また、MOOを適用した場合において第1000世代のパレート解が第100世代のパレート解と同じであり解の改善が見られなかった。交叉方法に関しては、XTG、一様交叉共に差はなかった。これは、交叉により生成された解候補に対してMOOを適用すると再生成されるパイプの数が増加し、MOCに比べ交叉により引き継いだ性質を破壊してしまうからであると考えられる。
 
Fig. 13 First pareto solutions with the MOO.
 
Fig. 14  Pareto solutions in the 100th generation with the MOO.
 
4.3 パラメータの扱い
 修正オペレータにパラメータを導入しており、任意に定める必要がある。そこで、それらに対する知見を述べる。
[脱却回数:α]
 パイプ同士の接触に関するのでパイプの本数に関係している。親の遺伝子をできるだけ引き継いだままでいるためには、できるだけ大きい値であるほうが好ましいが、大きすぎるとなかなか実行可能解を生成できない可能性がある。
[回避回数:β]
 1つのパイプと障害物との接触に関するのでパイプの本数に関係なく、定めることができ、障害物の大きさ、配置に依存する。
[修正回数:γ]
 全てのパイプがお互いに接触することなく、障害物を避けて配管するためのパラメータで、パイプの本数に大きく依存している。パイプの本数が増えるにつれ、大きい値となるほうがよいが、探索に時間がかかる。
 いずれのパラメータにしても、パイプの本数だけでなく径の大きさ・配置にも関係があり、問題設定に大きく依存し、実験的経験的に求められるものと考えられる。
 
5. 結言
 本論文では、パイプが密集し、障害物が存在する空間における配管設計問題を定式化した。本問題は大規模な組み合わせ最適化、数値最適化の複合問題かつ多目的最適化問題になっており、一般的な最適化手法を適用するのは困難であった。そこで、コード化/交叉方法、致死解を実行可能解に修正する修正オペレータを提案し、本問題に適した多目的GAを設計した次に、パイプが密に存在し、比較的大きな障害物が存在する配管設計問題を設定し、提案手法の有効性を示した。また、障害物を優先的に避けるように解を修正する修正オペレータを提案し、効果を得られることを示した。
 障害物に対する評価値とパイプの長さを評価値として多目的最適化を行ったが、実際の設計では、取り付け作業の効率、パイプの径、平行配管など他に考慮すべき項目が多数存在する。いかにそれらを評価し、アルゴリズムに取り組むかが今後の課題である。本研究では、機器の配置から始点・終点が与えられた場合に経路を自動設計する手法を提案したが、機器の配置も含めた最適化を行うことで、配管する空間の最小化も期待できる。また、探索時間を短縮するアルゴリズム、パラメータの設定に関してさらなる知見、改良が必要である。本論文で示した知見は、実際の現場に適用する予定である。実際の現場における本提案手法の有効性の検証は今後の課題である。
 
参考文献
1) Coello, C. A. C., An Updated Survey of Evolutionary Multiobjective Optimization Techniques, State of the Art and Future Trends, Proc. Congress on Evolutionary Computation 1999, pp.3-13.
2) Come, D.W., Knowles, J.D. and Oates, M.J.:The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization , Parallel Problem Solving from Nature 6 (PPSN2000), pp.839-848.
3)小野 功:形質遺伝を重視した遺伝的アルゴリズムによる最適化, 東京工業大学, 博士論文(1997)
4)柳浦睦憲, 茨木俊秀:組合せ最適化―メタ戦略を中心として―, pp.79-85, 朝倉書店(2001)
5)小野 功, 佐藤 浩, 小林重信:単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化, 人工知能学会誌, Vol.14, No.6, pp.l146-l155(1998)
6)小林重信, 吉田幸司, 山村雅幸:GAによるパレート最適な決定木集合の生成, 人工知能学会誌Vol.ll, No5, pp.778-785(1996)


前ページ 目次へ 次ページ





日本財団図書館は、日本財団が運営しています。

  • 日本財団 THE NIPPON FOUNDATION