(57)【要約】【課題】本発明では、一次元BPPのより汎用的なモデルとして、複数の母材長を扱うプレカット材料の取り合わせ問題を対象にGAの適用を検討し、組み合わせパターンを２つの文字列の遺伝子で表すことにより組み合わせパターンを探索する過程を省き、単純GAに近いモデルとし、さらに交差制御パラメータを設けて取り合わせ計算の結果を反映し、高い歩留をもつ母材と製品の取り合わせ処理方法を提供するものである。【解決手段】複数の定尺母材群(以下、母材種と略記）から所定長さの製品群を切り出す際のプレカット材料の取り合わせ問題について、割付ける製品の並びで染色体を表現し(Order based representation)、製品を割付ける母材種を指定する遺伝子Ｂと同じ母材種に割付けられた製品群の中での割付け順を指定するソートキーとなる遺伝子Ｐの2重遺伝子構造の染色体とし、複数のステップを経て歩留を判定していく方法を提供する。【選択図】図３
2008310689.tif 000002
【特許請求の範囲】
【請求項１】
複数種の定尺母材群(以下、母材種と略記）から所定長さの製品群を切り出す際のプレカット材料の取り合わせ問題について、割付ける製品の並びで染色体を表現し(Order based representation)、製品を割付ける母材種を指定する遺伝子（以下、遺伝子Bと略記、数式ではＧｅｎｅＢと表す）と同じ母材種に割付けられた製品群の中での割付け順を指定するソートキーとなる遺伝子（以下、遺伝子Ｐと略記、数式ではＧｅｎｅＰと表す）の2重遺伝子構造の染色体とし、次のステップ（数式では、Stepと表す）で計算するものとし、
【数１】
2008310689.tif 000038
さらに次の制御工程を備える、
制御1： 歩留の高い母材−製品グループに属する製品の割付け順を早くして、先行す            る割付けによってグループが破壊されないようにする
制御2： 歩留の高い母材−製品グループに属する製品の遺伝子は、交差操作を経ても            できるだけ維持されるようにする
という制御をすることを特徴とするプレカット材料取合せ最適化処理方法。
【請求項２】
請求項１において、製品の集合をｌ=｛ｉ｜ｉ＝１，２．．．，ｎ｝製品ｉの長さをｌi、この製品を割付ける母材の母材種をｔiとし、一方、母材種ｔ（ｔ＝１，２，．．，ｍ）の母材の集合をＢtとし、Ｂtに属する母材をｋ(t)（＝１，２，．．）長さをｂtとして製品ｉの遺伝子座の各遺伝子を下記のように定義し、
【数２】
2008310689.tif 000039
【数３】
2008310689.tif 000040
【数４】
2008310689.tif 000041
と計算することを特徴とする、請求項１記載のプレカット材料取合せ最適化処理方法。
【請求項３】
請求項１において、
母材ｋ(t)から製品を切り取った後の残材に対して、残材率ｒk(t)（０≦ｒk(t)≦１）を次式で定義し、
【数５】
2008310689.tif 000042
なお、（５）式の最後の項は、母材ｋ(t)の歩留を示し、
ここで前記制御1を実現するため、（３）の遺伝子Ｐ（GeneP）を十分小さい数αを導入して下記のように定義し、
【数６】
2008310689.tif 000043
遺伝子Ｐ（GeneP）は取り合わせ計算毎に（５）式により再計算される母材−製品グループの残材率と母材番号から成り同じ母材-製品グループでは同じ値であり、高い歩留のときは小さな値を持つことになり、
さらに制御2を実現するため、交差制御パラメータ(Crossover Control Parameter: CCP)ｐiを導入し、交差時の遺伝子交差確率とし、
【数７】
2008310689.tif 000044
CCPの関数Ｆpは残材率ｒk(t)に対する増加関数とすることを特徴とする請求項１記載のプレカット材料取合せ最適化処理方法。
【請求項４】
母材に割付けられた製品の組み合わせ結果により（５）式から残材率を算出し、遺伝子Ｐ（GeneP）を（６）式の定義に従って更新することを特徴とする請求項３記載のプレカット材料取合せ最適化処理方法。
【請求項５】
請求項１〜３の何れか１つに記載の方法をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項６】
請求項５に記載のプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の定尺長さの原材料から所定長さの製品部材を所定の本数だけ切り出すために、歩留りの良い前記原材料の各定尺長さのものの本数とそれぞれの原材料からどの製品部材を切り出すかを決定するプレカット材料取合せ処理方法に関し、典型的な組み合わせ問題であるビンパッキング問題(Bin Packing Problem: BPP)の応用として取り組み、これに遺伝的アルゴリズム(Genetic Algorithm: GA)を適用した、最適化処理方法に関するものである。
【背景技術】
【０００２】
プレカット材料取り合わせとは、いくつかの種類の長さの木材母材から、住宅建築で要求される長さの部材製品を切り出す問題(Cutting Stock Problem)で、一次元のビンパッキング問題(Bin Packing Problem: BPP)として考えることができる。但し、通常BPPではビンの容量は一定とされるが、プレカットの場合は数種類の長さの母材を対象とする。
【０００３】
プレカット材料の一例としては、住宅構造材のプレカットの場合、断面形状や樹種，等級といった仕様毎に数種類の長さ(3.5m〜6m)の母材が用意され、そこから決められた長さの部材(製品)を切り出す。一般的な大きさの住宅の場合、梁、桁、土台など横架材とよばれるものでは、約20種類の仕様毎に数種類の長さの母材から平均10本、合計約200本の製品が切り出される。
【０００４】
図１は、プレカット材料取り合わせの模式的な一例を示す。取り合わせ計算の目標は、製品の仕様毎に用意された数種類の長さの母材群１０１の各長さにより、製品群１０２の長さに合わせて、取り合わせ結果１０３から、要求製品をいかに少ない母材(歩留最大)で切り出すかということにある。また、母材の長さによって調達コストや在庫コストが異なる場合は、必要な母材コストの最小化が目標となる。通常、母材コストは材積単価で決まるため材積歩留の最大を狙うのが一般的である。なお、現在多くのプレカット工場での一次歩留は、概ね85%から90%といわれている。例えば、特許文献１（特許第３５６５２６２号）には、コンピュータを用いたロジックによる割り付け方法を示している。
【０００５】
また、組合せ最適化問題処理方法として、遺伝子アルゴリズムを用いたものに、特許文献２（特開平１０−１１１８６１号）、特許文献３（特開平１０−１５７２７号）及び鋳片切断制御方法として特許文献４（特開平９−９４６４６号）がある。
【０００６】
また、ビンに入れるアイテムの組み合わせの集合を遺伝子として特殊な交差方法を提案した例として、非特許文献１（八川 徹也, 飯間 等, 三宮 信夫: ビンパッキング問題に対する遺伝的アルゴリズムの提案, 計測自動制御学会論文集, Vol.41, No.3, 274-282 (2005))が見られる。
更に、非特許文献２（山地 秀美, 辻村 泰寛, 山本 久志: NVPシステム設計に対する遺伝的アルゴリズム適用の有効性と評価, 日本経営工学会論文誌, Vol.57, No.2, 113-119 (2006)）において、ソフトウェアシステムのフォールトレラント設計にGAを適用する際に、乱数で表現した遺伝子を用いてタスクを組み合わせる順序を指定する提案をしている。これは遺伝子をキーとして遺伝子座をソートし、ソート順に遺伝子座のタスクを割り当てていく方式である。
【特許文献１】特許第３５６５２６２号公報
【特許文献２】特開平１０−１１１８６１号公報
【特許文献３】特開平１０−１５７２７号公報
【特許文献４】特開平９−９４６４６号公報
【非特許文献１】八川 徹也, 飯間 等, 三宮 信夫: ビンパッキング問題に対する遺伝的アルゴリズムの提案, 計測自動制御学会論文集, Vol.41, No.3, 274-282 (2005)
【非特許文献２】山地 秀美, 辻村 泰寛, 山本 久志: NVPシステム設計に対する遺伝的アルゴリズム適用の有効性と評価, 日本経営工学会論文誌, Vol.57, No.2, 113-119 (2006)
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明では、一次元BPPのより汎用的なモデルとして、複数の母材長を扱うプレカット材料の取り合わせ問題を対象にGAの適用を検討し、組み合わせパターンを２つの文字列の遺伝子で表すことにより、組み合わせパターンを探索する過程を省き、単純GAに近いモデルとし、さらに交差制御パラメータを設けて取り合わせ計算の結果を反映し、「高い歩留をもつ母材と製品のグループが次世代に引き継がれる傾向」という新たなエリート選択（拡張エリート選択）機能を持たせることで収束性の良いモデルを提供するものである。
【課題を解決するための手段】
【０００８】
本発明の第１の解決手段（請求項１）は、複数の定尺母材群（以下、母材種と略記）から所定長さの製品群を切り出す際のプレカット材料の取り合わせ問題について、割付ける製品の並びで染色体を表現し(Order based representation)、製品を割付ける母材種を指定する遺伝子（以下、遺伝子Ｂと略記、式中ではGeneBと表す）と同じ母材種に割付けられた製品群の中での割付け順を指定するソートキーとなる遺伝子（以下、遺伝子Ｐと略記し、式中ではGenePと表す）の2重遺伝子構造の染色体とし、次のステップ（数式ではStepと表す）で計算するものとし、
【０００９】
【数１】
2008310689.tif 000003
さらに次の制御工程を備え、
制御1： 歩留の高い母材−製品グループに属する製品の割付け順を早くして、先行する割付けによってグループが破壊されないようにする
制御2： 歩留の高い母材−製品グループに属する製品の遺伝子は、交差操作を経てもできるだけ維持されるようにする
という制御をすることを特徴とするプレカット材料取合せ最適化処理方法を提供する。
【００１０】
更に、本発明の第２の解決手段は、請求項１において、製品の集合を  ｌ  =｛ｉ｜ｉ＝１，２．．．，ｎ｝製品ｉ  の長さをｌi、この製品を割付ける母材の母材種をｔiとし、一方、母材種ｔ（ｔ＝１，２，．．，ｍ）の母材の集合をＢiとし、Ｂiに属する母材をＫ(t)（＝１，２，．．．，ｍ）長さをｂtとして製品  ｉ  の遺伝子座の各遺伝子を下記のように定義し、
【００１１】
【数２】
2008310689.tif 000004
【数３】
2008310689.tif 000005
【数４】
2008310689.tif 000006
と計算することを特徴とする、請求項１記載のプレカット材料取合せ最適化処理方法を提供する。
【００１２】
更に、請求項１において、
母材Ｋ(t)から製品を切り取った後の残材に対して、残材率ｒk(t)（０≦ｒk(t)≦１）を次式で定義し
【００１３】
【数５】
2008310689.tif 000007
なお、（５）式の最後の項は、母材Ｋ(t)の歩留を示し、
ここで前記制御1を実現するため、（３）のGenePを十分小さい(例えば0.0001)数αを導入して下記のように定義し、
【００１４】
【数６】
2008310689.tif 000008
GenePは取り合わせ計算毎に（５）式により再計算される母材−製品グループの残材率と母材番号から成り同じ母材-製品グループでは同じ値であり、高い歩留のときは小さな値を持つことになり、
さらに制御2を実現するため、交差制御パラメータ(Crossover Control Parameter: CCP) ｐiを導入し、交差時の遺伝子交差確率とし、
【００１５】
【数７】
2008310689.tif 000009
CCPの関数Ｆpは残材率ｒk(t)に対する増加関数とすることを特徴とする請求項１記載のプレカット材料取合せ最適化処理方法を提供する。
【００１６】
更にまた、母材に割付けられた製品の組み合わせ結果により（５）式から残材率を算出し、GenePを（６）式の定義に従って更新することを特徴とする請求項３記載のプレカット材料取合せ最適化処理方法である。
更にまた、これらをコンピュータプログラムとするとともに、持ち運びに便利なコンピュータ読み取り可能な記録媒体とすることもできる。
【発明の効果】
【００１７】
本発明は、一次元BPPの例としてプレカット材料の取り合わせの問題を対象にGAの適用を検討し、プレカットの場合は一般の一次元BPPとは違い母材長が複数であるため２重構造の文字列による遺伝子構造とし、かつ交差制御パラメータを設け遺伝子と協同で個体の中の優位な構成グループ(エリートグループ)を保護する、一種のエリート選択を行うことで収束性のよいモデルを確立し、歩留まりの良いプレカット材料取合せ処理を実施するものである。
また、本発明は、プレカット材料取り合わせに限らず、例えば運ぶべき貨物に対して積載可能量の違うトラックが複数台ある場合、効率的な貨物の積み合わせを探査する場合にも適用することができる。
【発明を実施するための最良の形態】
【００１８】
以上、プレカット材料取り合わせは材料切り出し問題(Cutting Stock Problem)であり、１次元のBPPとしてモデル化できるが、通常BPPは１種類の容量のビンを扱うが今回のプレカットの場合は先に述べたように母材長が数種類あり、複数容量のビンを想定する意味でより汎用的である。以下に複数種のビンを扱う一次元マルチBPPを定義する。
ｍ種類の容積ｂt（ｔ＝１，．．，ｍ）ビンが十分にあり、これに容積ｌi（ｉ＝１，．．．，ｎ）のアイテムをすべて入れるとき、容積ｂtのビン種別ｔのビンの使用コストをｃｔ、ビンｋ（ｋ＝１，２，．．．）のビン種別をｔkとすると、一次元マルチBPPは、
【００１９】
【数８】
2008310689.tif 000010
【数９】
2008310689.tif 000011
【数１０】
2008310689.tif 000012
【数１１】
2008310689.tif 000013
【数１２】
2008310689.tif 000014
と表せる。（９）式はビンに入れるアイテムの容積合計がビンの容量以下であること、(１０)式はすべてのアイテムをどれかのビンに入れること、(１１)式は１つのアイテムが同時に複数のビンには入らないことを示している。
上記に対して、ビンをプレカット母材に、容量別のビンの集合を長さ別の母材（以下、母材種と表記）の集合に、ビンに入れるアイテムを切り出す製品に置き換え、容積を長さに読み替えればプレカット材料取り合わせ問題となる。通常プレカットでは歩留最大を狙うのが一般的である。歩留ｙは次式で表され、
【００２０】
【数１３】
2008310689.tif 000015
ここで分子の製品長累計は所与であるので、(1)式で使用コストｃtを母材長ｂtに置き換えて
【数１４】
2008310689.tif 000016
とすればよい。なお、プレカットでは、母材の両端を整える「鼻切」（母材の両端の形状を整えるための両端切り落としのこと）および製品を切り出す際の「鋸代」（切断時に鋸の厚さ分が切り屑となって損失すること）を考慮する必要があるが、本質的な問題ではない。
【００２１】
BPPにGAを適用する場合、ビンへの割付けパターンを何らかの方法でリストアップしてそれぞれのパターンを遺伝子とし、ビンに入れるすべてのアイテムを含むようにパターン遺伝子を並べて染色体とする方法がとられる。たとえば八川ほか(２００５)は一つのビンに入るアイテムの集合を一つの遺伝子とし、各ビンに対応した遺伝子を並べて個体としている。しかしこの方法は、ビンに入るアイテムの組み合わせを探査し評価する必要があり、本発明のように複数種類のビンを扱う場合には、簡単に当てはめることができない。
【００２２】
図２は、ＦＦ（ファーストフィット）法における母材数を事前に設定する、取り合わせ問題の０−１文字列表現の模式的例である。このように、単純GAで使われる0-1文字列を遺伝子とするアイデアとして以下のモデルが考えられる。各長さの母材に対してあらかじめ全製品をたとえばFF(ファーストフィット)法などで仮割付けし、用意すべき母材の十分な数を算出する。製品はその製品長以上の長さを持つ母材のどれかに割り当てられる。これを0-1文字列で表現し遺伝子コードとする。
【００２３】
しかしこの場合、母材種ごとの母材数を仮に製品数の半分にできたとしても、製品数ｎ、母材種数ｍとすると染色体の0-1文字列は最大で  ｎ×ｍ／２×ｎ  ビット長となり、先に述べた一般住宅の横架材の例では1,000〜3,000ビットの膨大な探査空間を扱うこととなり探査効率や収束性の問題が懸念される。そこで本発明では次のようなモデルを検討した。
【００２４】
本発明では割付ける製品の並びで染色体を表現し(Order based representation)、製品を割付ける母材種を指定する遺伝子Ｂと同じ母材種に割付けられた製品群の中での割付け順を指定するソートキーとなる遺伝子Ｐの2重遺伝子構造の染色体を考える。
製品の集合を  ｌ  =｛ｉ｜ｉ＝１，２．．．，ｎ｝、製品ｉの長さをｌi、この製品を割付ける母材の母材種をｔiとする。一方、母材種ｔ（ｔ＝１，２，．．．，ｍ）の母材の集合をＢtとし、Ｂtに属する母材をｋ(t)（１，２，．．）、長さをｂtとして製品の遺伝子座の各遺伝子を下記のように定義する(表1遺伝子構造参照）。
【００２５】
【数１５】
2008310689.tif 000017
【数１６】
2008310689.tif 000018
【数１７】
2008310689.tif 000019
【００２６】
【表１】
2008310689.tif 000020
この２つの遺伝子を使って、取り合わせ計算を以下のようなルールで行う。なお、「鼻切」と「鋸代」は母材長や製品長の調整で容易に組み込むことができるので、ここでは表現の単純化のため無視した。
＜取り合わせ計算ルール＞
【数１８】
2008310689.tif 000021
【００２７】
しかし上記の遺伝子構造による取り合わせルールでは、同一母材種内の母材と製品の組み合わせがソートキーであるGenePの相対的な大小関係で決まるため、組み合わせがGenePの変化に敏感に反応するためスキーマの概念が成立せず、安定的な最適解への進化が期待できないことが想定される。そこでこれを回避するためには、「高い歩留をもつ母材−製品グループは次世代に引き継がれる傾向」を持たせることを考える。具体的には、
制御1： 歩留の高い母材−製品グループに属する製品の割付け順を早くして、先行する割付けによってグループが破壊されないようにする。
制御2： 歩留の高い母材−製品グループに属する製品の遺伝子は、交差操作を経てもできるだけ維持されるようにする。
という制御をする。通常のエリート選択が個体単位の適応率による選択であることに対し、この制御は個体を構成する母材と製品のグループ単位に適応率(歩留)の高いグループを保存するという広義のエリート選択であり、これを拡張エリート選択と呼ぶこととする。
母材ｋ(t)から製品を切り取った後の残材に対して、残材率ｒk(t)（０≦ｒk(t)≦１）を次式で定義する。
【００２８】
【数１９】
2008310689.tif 000022
なお、式の最後の項は、母材ｋ(t)の歩留である。
ここで先に述べた制御1を実現するため、（３）のGenePを十分小さい(例えば0.0001)数αを導入して下記のように定義する。
【００２９】
【数２０】
2008310689.tif 000023
GenePは取り合わせ計算毎に（５）式により再計算される母材−製品グループの残材率と母材番号から成り同じ母材-製品グループでは同じ値であり、高い歩留のときは小さな値を持つことになる。
さらに制御2を実現するため、交差制御パラメータ(Crossover Control Parameter: CCP)ｐiを導入し、交差時の遺伝子交差確率とする。
【００３０】
【数２１】
2008310689.tif 000024
CCPの関数Ｆpは残材率ｒk(t)に対する増加関数とする。なお、CCPおよびその関数については次のセクションの交差の検討の中で詳細する。
【００３１】
本発明のアルゴリズム全体の流れ（フローチャート）を図3に示す。
A.  初期設定（Ｓ３０１）
各個体に対して、遺伝子座（製品：ｉ＝１，２，．．．，ｎ）のGeneBｔiには１≦ｔi≦ｍとなる乱数、GenePｓiには０≦ｓi≦１の乱数をセットする。但し、あらかじめ（６）式を満たすように設定し致死遺伝子を避ける。
以上により決められた初期個体数だけ個体を発生させる。
B.   取り合わせ計算（Ｓ３０２）
前節の取り合わせ計算ルールに従って割付けを行い、その結果を使って次の処理をする。
B-1. 適応率の計算
適応率ａは(5)式の個体の歩留ｙ（０≦ｙ≦１）を関数Ｆaでスケーリングする。
【００３２】
【数２２】
2008310689.tif 000025
歩留は、予備実験で平均は70%〜90%、最小値は50%〜60%であることがわかっており、また目標は90%以上としたい。これを踏まえると適応率ａはｙ<0.5ではほぼ0となり、ｙが0.6から1.0の間で大きく変化するように関数Ｆa（ｙ）を設定すべきである。
B-2. 母材残材率の計算とGenePの更新
母材に割付けられた製品の組み合わせ結果により（５）式から残材率を算出し、GenePを（６）式の定義に従って更新する。
【００３３】
C.  選択（Ｓ３０３）
選択は通常のエリート選択とルーレット選択を組み合わせる。計算された適応率に従って、指定された選択率で決められた数まで、まず個体適応率の降順に指定された数だけエリート選択し、残りを適応率に比例するルーレット選択によって選択することで個体を淘汰する。
D.  交差（Ｓ３０４）
選択によって淘汰された個体を、この交差によって初期個体数まで増殖させる。
通常、交差は2つの親個体の遺伝子から1点交差や一様交差のルールに従い２つの子個体を生成する。しかし本発明では、それぞれの親の遺伝子を交差確率CCPにしたがって遺伝子交換することで2つの子を生成する、拡張エリート選択方式をとる。個体Aのｉ番目の遺伝子座（ｉ＝１，２，．．．，ｎ）のGeneBをｔi（Ａ），GenePをｓi（Ａ），CCPをｐi（Ａ）として、次のようなルールで子の遺伝子を生成する。
【００３４】
【数２３】
2008310689.tif 000026
【数２４】
2008310689.tif 000027
但し、Ｒｎｄは(0,1)の乱数
ｐiは（５）式で定義される母材の残材率により（７）式で与えられる。予備実験では歩留が90%以上になった個体は、構成する母材の残材率もほとんどが0.1%以上であることがわかっており、歩留の目標を90%以上とするならば残材率は0.05%以下を目指す必要がある。従って、ｐiを与える（７）式の関数Ｆpは、母材の残材率ｒに対して原点付近では0に近く、ｒ＝０．０５近傍で大きく変化し、ｒ＞０．１ではある程度の確率で遺伝子交換が行われるように、設定するのが効果的と推定できる。
【００３５】
E.  突然変異（Ｓ３０５）
本発明モデルでは2種類の遺伝子を扱っているので、遺伝子毎に変異確率を設定しそれぞれの設定した確率で対象の個体を選んで変異操作を行う。突然変異対象となった個体に対して、ランダムに選んだ遺伝子座の遺伝子を初期設定の要領で乱数により再設定する。なお変異する遺伝子座の数はあらかじめ指定しておく。
GeneBの変異の場合は同時にGenePも再設定することとし、致死遺伝子の発生を避けるため（４）(9)式の条件を適用する。GenePが変異する場合はGeneBは変化させない。
【００３６】
Ｆ．目標の達成判定（Ｓ３０６）
あらかじめ決められた目標歩留が達成されるか、世代を重ねて設定した最大世代数に達しているかを判定する。
達していないときには、Ｓ３０１の後流に帰り、同じ手順に従って判定を繰り返す。
Ｇ．ＳＴＯＰ(  処理の終了)
あらかじめ決められた目標歩留が達成されるか、世代を重ねて設定した最大世代数に達したら処理を終了する。
【実施例１】
【００３７】
図８の横架材プレカット一覧に示す付表１にあるように、本発明モデルのGAを、ある住宅メーカーが受注した標準的な一戸建て住宅の、横架材199本を対象に適用した。これらの横架材は、断面サイズや樹種、等級など同じ母材から切り出すことができる18のロットにグループに分けることができ、それぞれのロット毎に切り出す製品数や使用する母材群も異なる(表2：母材群と製品群及び実行結果を参照)。例えばロットNo.8やロットNo.9は対象製品が1本、ロットNo.6は2本、ロットNo.12及び16は3本であり、これらは世代を重ねるまでも無く簡単に最適解が得られると予想できる。したがって母材種と製品の組み合わせの数に応じて生成する個体数や最大世代数を適宜設定した。そのほかのパラメータは、予備実験の結果を踏まえて以下のとおりに設定した。なお鼻切は0mm、鋸代は5mmとする。
【００３８】
【数２５】
2008310689.tif 000028
【００３９】
【表２】
2008310689.tif 000029
また各関数については、(１５)式の適応率関数Ｆaは一次関数、(７)式のCCP関数Ｆpはシグモイド関数に近い形とした(図4適応率関数(左)およびCCP関数(右)を参照)。
【００４０】
【数２６】
2008310689.tif 000030
【数２７】
2008310689.tif 000031
【００４１】
適応率関数とCCP関数の組み合わせ実行結果を表3に示す。なお使用したパソコンの仕様は図５のとおりである。表2の結果は、ロット毎に同じパラメータで50回実行し得られた歩留の最大値、平均値、最小値と標準偏差を示している(実行結果例は図９の付表2と図１０の付表3に示す）。概ね製品数が5本以下のロットについては、50回実行の結果すべて同じ値となり最適値と推定される。また標準偏差はほぼ0.5％以内に収まった。例外はロットNo.12とNo.14であるが、ロットNo.12では50回の試行のうち80%台が2回発生し残りは96.22%であった。
この結果、各50回の試行の最大歩留の取り合わせを採用すると、この住宅1棟の必要な横架材199本を全体の材積歩留が95.21%でプレカット割付けができたことになる。
【００４２】
【表３】
2008310689.tif 000032
【００４３】
表3で、製品数が多く標準偏差も比較的大きなロットNo.1について、適応率関数FaとCCP関数Fpについて評価する。表3は比較した適応率関数とCCP関数のケース別組み合わせある。Case7を除きその他のパラメータは変更しないこととする。図６に各関数のグラフを示した。
Case1と2は適応率関数のみ変えた場合、Case3〜5はCCP関数のみ変えた場合、Case6と7はCCPによる交差制御をしない場合である。
表4はＣａｓｅ別の50回の実行結果（ロットＮｏ．１の場合）である。
【００４４】
【表４】
2008310689.tif 000033
【００４５】
Case1と2は適応率関数のみ変えた場合であり、OriginalとCase1およびCase2を比較すると適応率関数は収束性にあまり影響のないことがわかる。一方、Case3〜5はCCP関数のみ変えた場合であり、CCP関数は収束性に影響し適切な関数形を与えれば良い収束性を得ることができる。つまりCCPによる交差時の遺伝子交差制御が収束性に大きく関係しており、拡張エリート選択が適応率による通常の選択よりも淘汰に影響を与えていると推測される。
【００４６】
これをさらに確認するため、CCPによる交差制御の有無の違いを歩留の世代推移状況で比較した。図7は世代別個体歩留の推移（左：Case6  右：Original）を示し、元のモデル(Original: CCPによる交差制御)とCase6(一様交差方式)のそれぞれ最大歩留を得た時の、世代別個体歩留の最大値，平均値，最小値の推移を示した。これを見るとCCPを交差に反映させない場合は収束性が不安定であることがわかる。すなわち先に述べた、「スキーマの概念が成立せず安定的な最適解への進化が期待できない」という推測が確認できる。この場合エリート選択を加えること(Case7)で若干の歩留向上が見られるが(表４)、元のモデルに比べ著しく収束性が悪く、CCPによる拡張エリート選択の有効性が実証された。
【００４７】
【表５】
2008310689.tif 000034
【００４８】
本発明のGAを他のアルゴリズムと比較するに当たって、プレカット材料取り合わせへのGＡの適用例が見当たらないため、特許されているプレカット材料取り合わせのヒューリスリックアルゴリズム特許文献１との比較と、ビンパッキング問題で一般的なＦＦＤ（First Fit Descending ）法をこのモデルに適用できるように改良し、その結果との比較を行った。
【００４９】
この特許文献１のアルゴリズムは、すべての製品の長さ合計に対してその合計長以上になる複数母材長の母材の組み合わせをリストアップし、リストアップした母材の組み合わせで母材長合計の昇順にすべての製品が割付けられるかを判断するステップと、割付け可能な最小母材長合計の組み合わせに対して、さらに母材長合計が小さくなる母材の組み合わせを探査するステップからなる方法である。
【００５０】
ＦＦＤ（First Fit Descending） 法はビンパッキング問題では一般的な解法である。しかし、本モデルでは母材の長さ(ビンの容量)は複数種類あるためそのままでは使えない。そこで、FFD法を次のように改良して、プレカットの取り合わせ問題に適用した。
製品長の降順にソートした製品の並びをｉ＝１，２，．．，ｎとし、以下のルールで製品を母材に割付ける。
【００５１】
【数２８】
2008310689.tif 000035
【数２９】
2008310689.tif 000036
【数３０】
2008310689.tif 000037
となる母材ｋ(t)への割付け結果を採用し、割付けた製品の集合ｌk(t)を確定          する。
Step.5：すべての製品ｉ（ｉ＝１，．．，ｎ）に対して割付けが終われば完了。未          割付けの製品があれば、Step.1へ。
このマルチFFD法は、各母材種の母材1本単位にFFDルールで製品長の降順に製品を割付け、最も高い歩留が得られた母材種の母材とその割付け結果を採用していく作業を、すべての製品が割付済みになるまで実行する方法である。
【００５２】
表５に本発明GAでの数値(表3)と特許文献１方法およびマルチFFDを適用した結果（詳細例は付表3）を比較した。この結果、本論文のモデルは特許方法に対して0.6%、FFDモデルに対して1.7%の歩留優位となった。特に組み合わせパターンの多いロットNo.1やロットNo.7での優位性が確認できる。一般にプレカット工場での歩留は90%以下であることを考慮すれば、本発明のGAモデルはきわめて有用であると言える。これは、CCPの交差制御による拡張エリート選択が効果的かつ安定的に最適解への進化を促した結果である。
【産業上の利用可能性】
【００５３】
本発明では、プレカット業界のプレカット材料取り合わせに限らず、一般に積み合わせ問題といわれている分野で、例えば運送業界では運ぶべき貨物に対して積載可能量の違うトラックが複数台ある場合、効率的な貨物の積み合わせを探査する場合にも適用することができる。これは、鉄道輸送の場合の大きさの違う鉄道コンテナに対する積み合わせや、船積みにも適用できる。
【００５４】
Cutting Stock Problem (CPS)として研究されている分野でも、母材を製造しそこから製品を切り出す工程において、例えば鉄鋼業におけるＨ型鋼の圧延とソーイングスケジュールやパイプ鋼の切断スケジュールなどにも応用できる。製紙業の紙ロールのカッティングもその例である。
【図面の簡単な説明】
【００５５】
【図１】プレカット材料取り合わせの模式的な一例を示す。
【図２】ＦＦ法における母材数を事前に設定する、取り合わせ問題の０−１文字列表現の模式的例である。
【図３】本発明のアルゴリズム全体の流れ（フローチャート）図である。
【図４】本発明における適応率関数(左)およびCCP関数(右)のグラフである。
【図５】本発明の実施に用いたパソコンの仕様（プログラムの環境）である。
【図６】本発明実施例による適応率関数(左)とＣＣＰ関数(右)である。
【図７】本発明実施例による世代別個体の推移(左：Ｃａｓｅ６，右：Ｏｒｉｇｉｎａｌ)図である。
【図８】横架材プレカット一覧表（付表１）である。
【図９】本発明１実施例に用いたものの繰返し実行結果表（付表２）である。
【図１０】本発明におけるＧＡとＦＦＤの実行結果（付表３）である。
【符号の説明】
【００５６】
１０１      母材群
１０２      製品群
１０３      取り合わせ結果
Ｓ３０１    初期設定
Ｓ３０２    取り合わせ計算
Ｓ３０３    選択
Ｓ３０４    交差
Ｓ３０５    突然変異
Ｓ３０６    目標歩留判定
Ｓ３０７    ＳＴＯＰ
【図１】
2008310689.tif 000045
【図２】
2008310689.tif 000046
【図３】
2008310689.tif 000047
【図４】
2008310689.tif 000048
【図５】
2008310689.tif 000049
【図６】
2008310689.tif 000050
【図７】
2008310689.tif 000051
【図８】
2008310689.tif 000052
【図９】
2008310689.tif 000053
【図１０】
2008310689.tif 000054