株式会社　インテグラル サイトマップ　
ホームお問合せ資料請求このサイトについて
会社案内
社長挨拶
会社概要
つくば発の取り組み
案内地図
つくば公園通りマップ
採用情報
インターンシップ
プレスリリース
業務内容・実績
プロジェクトの遂行
建築ソリューション
システムソリューション
Linuxソリューション
ホームページ制作
技術・製品紹介
住宅性能診断士ホームズ君シリーズ
省エネ診断システム
筋かいセンサー
常時微動センサー
最適化技術紹介
生産最適化システム　CIMシリーズ
国際学会論文投稿システム

ホームズ君.com
ホームズ君 耐震フォーラム
つくばPiazza
スポルティーバつくば





最適化技術紹介

インテグラルが研究・実用化している最適化技術を紹介します。

  インテグラルの最適化技術は、建材加工の歩留まり向上など解決困難な実社会の諸問題を、 数学的・情報科学的に解決する為の一連の技術・研究です。
インテグラルは、ここで紹介する最適化技術の研究・実績を基盤に、 建材加工最適化エンジン「CIM-Nest」 を開発・実用化しました。

数学や情報科学の分野 「組み合わせ最適化」 「離散数学」「人工知能」などを中心に、 最適化技術の基礎研究から応用研究、実用化を推進しています。
以下では、「組み合わせ最適化」にまつわる問題と、 インテグラルが採用している解決方法を中心に、 詳しく紹介します。
最高の歩留まりを割り出すのに2.96×10の141乗年かかる？
■組み合わせ的爆発

※下記「例題：巡回セールスマン問題」とあわせてご覧ください。

建材の生産・加工において、最も重要なポイントの一つは、 「素材から部品を切り取る際の歩留まりの向上」です。

「歩留まり向上」のためには、 素材と部品の「組み合わせ」を考えなければなりません。 具体的には次のような点です。

  1. 「素材と部品の組み合わせは？」
  2. 「全ての部品を加工するのに、必要最低限の素材の量は？」
  3. 「部品を素材のどの位置から切り取るか？」
  4. 「加工を短時間で確実に行えるか？」
  5. 「1〜4をどうやりくりすれば、歩留まりが向上するか？」
素材と部品の組み合わせは何通りもあります。
「歩留まり向上」を実現する最もシンプルな手法は、 完全列挙法です。

完全列挙法とは、 「全ての組み合わせを列挙し、その中から最適な組み合わせを求める手法」です。 しかしこの完全列挙法には、致命的な問題があります。

部品の種類や数が増えると、組み合わせの数は爆発的に増加し、天文学的な数になります。 このような現象は一般に「組み合わせ的爆発」と呼ばれます。

「組み合わせ的爆発」が起きた場合、限られた時間の中で全ての組み合わせを列挙することは、事実上不可能です。 人間ではもちろん、スーパーコンピュータでも途方もない時間がかかってしまうのです。
■例題：巡回セールスマン問題
とある会社のセールスマンが、つくば市内のいくつもあるお得意先に、新開発された世界最新鋭のコンピュータの紹介のために、一件一件挨拶回りすることになりました。

彼は、なるべく早くすべてのお得意先様の訪問を終えて、上司に報告したいと考えました。どのような順番で訪問すれば最も短い距離で訪問できるでしょうか？

このセールスマンは「全ての巡回経路から最短の巡回経路を求めるプログラム」 （すなわち完全列挙法を行うプログラム）を作り、自社製品の実力を試してみることにしました。このコンピュータは１秒間に１０億通りの計算ができます。

サンプルとして、本社周辺の１０件のお得意先の場所を入力した結果、0.00036288秒で答えを出しました。さすが、世界最新鋭のコンピュータです。セールスマンは自信を持って、お客様に紹介できると確信しました。

新製品のコンピュータのおかげで、意外と早く訪問することができるとわかったので、お得意先様を２０件回ることに決めて、再び、コンピュータに２０件のお得意先の場所のデータを入力してみると….

どういうわけか計算結果がなかなか出てきません。調べてみると、計算が完了するまでに77年近くかかるとなっています。どうしたのでしょうか？

結局、このセールスマンはコンピュータの性能が悪いと判断し、営業をやめてしまいました。

原因を追究しないで、営業をやめてしまうセールスマンにも問題はありますが、こういった現象は一般に「組み合わせ的爆発」と呼ばれます。
訪問先が10→20に増加すると、その巡回経路のパターン数は、次の通りです。

10! = 362880
から
20! = 2432902008176640000 (243京2902兆81億7664万)
に増加！

巡回経路のパターン数は、天文学的になってしまいました。
約77年もの間、コンピュータが計算し続けることは、現実では、あり得ません。
巡回する個所と巡回経路のパターン数、計算時間の関係、次の通りです。

巡回する個所 巡回経路のパターン数 計算に必要な時間
(1秒間に10億通りの計算を行うコンピュータの場合)
10 　10! [通り]
＝362880 [通り]
 　10! [通り] ÷ 10億[通り/秒]
＝362880 [通り] ÷ 10億[通り/秒]
＝0.00036288 [秒]
20 　20! [通り]
＝2.433×10の18乗 [通り]
 　20! [通り] ÷ 10億 [通り/秒]
＝2.433×10の18乗 [通り] ÷ 10億 [通り/秒]
＝約 2432902008 [秒]
＝約 77 [年]
100 　100! [通り]
＝約 9.332×10の157乗 [通り]
 　100! [通り] ÷ 10億 [通り/秒]
＝約 9.332×10の157乗 [通り] ÷ 10億[通り/秒]
＝約 9.332×10の148乗 [秒]
＝約 2.96×10の141乗 [年]

以上の問題は、一般に「巡回セールスマン問題」と呼ばれ、 現在も世界中で、様々な研究が行われています。
■組み合わせの最適化
建材の生産・加工における「歩留まり向上」の問題は、 前述の通り「組み合わせ的爆発」が起きる問題です。

このような問題を解決するには、 「全ての組み合わせを列挙せずに、 限られた時間内に『最適に近い組み合わせ』を求める」必要があります。

この解決手法を、一般に「組み合わせ最適化」と呼び、 数学・情報科学などにおいて世界中で研究が行われています。

インテグラルは「組み合わせ最適化」に関する独自の研究・ノウハウを基盤に、 建材加工最適化エンジン「CIM-Nest」を開発・実用化しました。 短い計算時間(数分程度)で高い歩留まりを実現します。
建材の生産・加工の現場で、歩留まり向上だけでなく、 さまざまな問題の解決に貢献させて頂いております。　

★インテグラルの「組み合わせの最適化」の手法
インテグラルの建材加工最適化エンジン「CIM-Nest」は、 次に挙げる手法を臨機応変に適用して、最適化の計算を行います。

●完全列挙法
全ての組み合わせを列挙し、その中から最適な組み合わせを求める手法です。
最もシンプルな手法の一つですが、組み合わせる部品の数が多いと、 「組み合わせ的爆発」が起き、列挙・解決が不可能になります。 部品がｎ個の場合、それぞれの部品に番号1からnを付けて、 「部品を素材に順番に割り当てていき、 素材に収まらなくなったら次の素材に割り当てる」ことによって、 １通りの割り当て結果を得ることができます。 割り当て結果の数、すなわち部品の組み合わせの数は、 部品n個の順列ですから、nの階乗通りあります。

部品の数 部品の組み合わせの数 計算(列挙)に必要な時間
(1秒間に10億通りの計算を行うコンピュータの場合)
5 　5! [通り]
＝120 [通り]
 　5! [通り] ÷ 10億[通り/秒]
＝120 [通り] ÷ 10億[通り/秒]
＝0.00000012 [秒]
10 　10! [通り]
＝362880 [通り]
 　10! [通り] ÷ 10億[通り/秒]
＝362880 [通り] ÷ 10億[通り/秒]
＝0.00036288 [秒]
20 　20! [通り]
＝2.433×10の18乗 [通り]
 　20! [通り] ÷ 10億 [通り/秒]
＝2.433×10の18乗 [通り] ÷ 10億 [通り/秒]
＝約 2432902008 [秒]
＝約 77 [年]
25 　25! [通り]
＝約 1.551 × 10の25乗 [通り]
 　25! [通り] ÷ 10億 [通り/秒]
＝約 1.551 × 10の25乗 [通り] ÷ 10億 [通り/秒]
＝1.551×10の16乗 [秒]
＝約 49185724 [年]
30 　30! [通り]
＝約 2.652×10の32乗 [通り]
 　30! [通り] ÷ 10億 [通り/秒]
＝約 2.652×10の32乗 [通り] ÷ 10億 [通り/秒]
＝約 2.652×10の23乗 [秒]
＝約 8000兆 [年]
100 　100! [通り]
＝約 9.332×10の157乗 [通り]
 　100! [通り] ÷ 10億 [通り/秒]
＝約 9.332×10の157乗 [通り] ÷ 10億[通り/秒]
＝約 9.332×10の148乗 [秒]
＝約 2.96×10の141乗 [年]

●準完全列挙法
計算方法は完全列挙法と同等ながら、 いくつかの部品を計算前にグループ化することにより、 部品の数が多くても完全列挙を可能にする手法です。
完全列挙法の説明で述べた通り、 部品の数が増えると、部品の組み合わせを全て列挙することは困難になります。 しかし、部品をサイズや形状の特長でグループ化すると、 グループの組み合わせが減少し、結果として、列挙・解決が可能になる場合があります。 特に、複数の部品を合体させて一つの部品として扱うと、 部品の数が減り、 組み合わせの数も、計算時間も、激減します。

●降順ソート法
部品を、サイズの大きいものから、順番に素材に割り当てた結果を、最適な組み合わせとする手法です。
最もシンプルな手法の一つです。
パッキング問題等として知られている状況に対して、 発見的方法による解の１つとして考えられる手法です。 考え方としては単純ですが、 得られる歩留まりは悪くありません。 計算時間も、割り当てが１度ですから、ほとんどかかりません。

●人工知能法
人の脳神経細胞のように計算する『ニューラルネット』や、
生物進化のように組み合わせの淘汰を行う『遺伝的アルゴリズム』などの技術により、 最適な組み合わせを求める手法です。
上記の手法をいくつも連動させる場合もあります。
高度で複雑な計算を行う為、 比較的高い歩留まりを得られますが、 比較的長い計算時間が必要になります。

[ 紹介 / 最適化エンジン「CIM-Nest」/ CIMシリーズ ]
Copyright (C) INTEGRAL