TOP > 国内特許検索 > 製品割り付け決定装置、製品割り付け決定方法、製品割り付けプログラム > 明細書

明細書 :製品割り付け決定装置、製品割り付け決定方法、製品割り付けプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5302080号 (P5302080)
公開番号 特開2010-009585 (P2010-009585A)
登録日 平成25年6月28日(2013.6.28)
発行日 平成25年10月2日(2013.10.2)
公開日 平成22年1月14日(2010.1.14)
発明の名称または考案の名称 製品割り付け決定装置、製品割り付け決定方法、製品割り付けプログラム
国際特許分類 G05B  19/418       (2006.01)
FI G05B 19/418 Z
請求項の数または発明の数 10
全頁数 23
出願番号 特願2009-103052 (P2009-103052)
出願日 平成21年4月21日(2009.4.21)
優先権出願番号 2008138123
優先日 平成20年5月27日(2008.5.27)
優先権主張国 日本国(JP)
審査請求日 平成24年4月19日(2012.4.19)
特許権者または実用新案権者 【識別番号】505127721
【氏名又は名称】公立大学法人大阪府立大学
【識別番号】000183428
【氏名又は名称】住友林業株式会社
発明者または考案者 【氏名】竹安 数博
【氏名】豊田 丈輔
個別代理人の代理人 【識別番号】100065248、【弁理士】、【氏名又は名称】野河 信太郎
審査官 【審査官】後藤 健志
参考文献・文献 特開平09-150311(JP,A)
特許第3565262(JP,B2)
特開2008-310689(JP,A)
特開2010-152584(JP,A)
Johsuke Toyoda, Kazuhiro Takeyasu,Extended Elitism Method for Cutting Stock Problem of Timber Precutting,International Journal of Information Systems for Logistics and Management,2007年,vol.3,No.1,p47-59
豊田丈輔,材料取り合わせ問題のための対戦交叉法を用いた遺伝的アルゴリズムの提案,大阪府立大学経済研究,日本,2008年 9月25日,54(2),p165-184
豊田丈輔,材料取り合わせ問題のための対戦交叉法GAの改善,大阪府立大学経済研究,日本,2008年12月26日,54(3),p135-146
調査した分野 G05B 19/418
特許請求の範囲 【請求項1】
長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置であって、
(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、
(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付け部と、
(3)前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、
(4)前記個体適応率に基づいて個体の選択を行う個体選択部と、
(5)前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、
(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、
(7)終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、
前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする製品割り付け決定装置。
【請求項2】
前記母体は、長さが互いに異なる複数種類の母材であるか,又は容積が互いに異なる複数種類の容器である請求項1に記載の装置。
【請求項3】
前記初期集団生成部は、所定の規則に従った方法による個体の生成と、乱数を用いた方法による個体の生成とを組み合わせることによって初期の集団を生成する請求項1又は2に記載の装置。
【請求項4】
所定の規則に従った方法によって生成された個体の割合は、10~90%である請求項3に記載の装置。
【請求項5】
前記個体適応率は、(全製品の長さ又は容積の合計)/(使用した全母体の長さ又は容積の合計)で定義される個体歩留が1に近づくにつれて値の上昇度が大きくなる関数に基づいて算出される請求項1~4の何れか1つに記載の装置。
【請求項6】
製品iについての前記遺伝子適応率は、製品iが母体kに割り付けられるとき(母体kに割り付けられる全製品の長さ又は容積の合計)/(母体kの長さ又は容積)で定義される材料歩留に基づいて算出される請求項1~5の何れか1つに記載の装置。
【請求項7】
遺伝子Pは、製品iが母体kに割り付けられるとき(母体kに割り付けられる全製品の長さ又は容積の合計)/(母体kの長さ又は容積)で定義される材料歩留に基づいて算出され、
前記算出部は、前記製品割り付け部による割り付けの結果に基づいて前記遺伝子Pを更新する請求項1~6の何れか1つに記載の装置。
【請求項8】
前記個体選択部は、前記個体適応率が高い所定数の個体を選択するエリート選択と、前記個体適応率に比例するように所定数の個体を選択するルーレット選択を組み合わせた方法によって個体の選択を行う請求項1~7の何れか1つに記載の装置。
【請求項9】
長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定方法であって、
(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成ステップと、
(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付けステップと、
(3)前記製品割り付けステップによる割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出ステップと、
(4)前記個体適応率に基づいて個体の選択を行う個体選択ステップと、
(5)前記個体選択ステップによって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉ステップと、
(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理ステップと、
(7)終了基準が満たされるまで前記製品割り付けステップ、前記算出ステップ,前記個体選択ステップ、前記交叉ステップ及び前記多様化処理ステップによる処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断ステップとを備え、
前記交叉ステップは、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする製品割り付け決定方法。
【請求項10】
コンピュータを長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置として機能させる製品割り付けプログラムであって、
コンピュータを
(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、
(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付け部と、
(3)前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、(4)前記個体適応率に基づいて個体の選択を行う個体選択部と、
(5)前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、
(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、
(7)終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部として機能させ、
前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする製品割り付けプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置及び製品割り付けプログラムに関する。
【背景技術】
【0002】
住宅構造材のプレカット等では、一般に、図4に示すように、長さが互いに異なる複数種類の材料から複数種類の製品を切り出す。それぞれの長さの材料の使用本数には制限が設けられず、ある長さの材料を複数本使用することも可能である。このような条件下では、材料への製品の割り付けは、図5(a)や図5(b)に例示するように様々な方法で行うことができる。一般に、残材の合計長さが短いほど割り付け方法が適切であるが、残材の合計長さを最小化するように製品の割り付けを行うことは容易ではない。
【0003】
本発明者らは、以前に、製品の並びを遺伝子配列として一種のOrdered-basedモデル(製品の切り出し順に注目するモデル)に対して遺伝子レベルの交叉制御を行う拡張エリート選択法(Extended Elitism Method:EEM)を提案して、一般のプレカット向上では90%以下と言われている歩留まりを95%前後にまで向上させた(非特許文献1を参照。)
【先行技術文献】
【0004】

【特許文献1】特許第3565262号
【0005】

【非特許文献1】Toyoda J., Takeyasu K.: Extended Elitism Method for Cutting Stock Problem of Timber Precutting: International Journal of Information Systems for Logistics and Management. 3-1 (2007) 47-59.
【0006】

【非特許文献2】Toyoda J. and Takeyasu K.: A Revised First Fit Algorithm for Timber Precutting. International Journal of Computational Science 2-1, (2008), pp.92-107.
【0007】

【非特許文献3】八川 徹也, 飯間 等, 三宮 信夫: ビンパッキング問題に対する遺伝的アルゴリズムの提案, 計測自動制御学会論文集, Vol.41, No.3, (2005), pp.274-282.
【0008】

【非特許文献4】Fleszar, K., Hindi, K. S.: New heuristics for one dimensional bi n-packing, Computer & Operations Research 29 (2002) pp.821-839.
【0009】

【非特許文献5】Scholl A., Klein R. and Jurgens C.: BISON: the fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 24-7, (1997),pp.625-645
【0010】

【非特許文献6】Schwerin P. and Wascher G.: The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. International Transactions in Operational Research 4 (1997), pp. 377-389.
【発明の開示】
【発明が解決しようとする課題】
【0011】
非特許文献1に記載の方法は非常に優れた方法ではあるが、収束性が良くない場合もある。従って、収束性がさらに優れた割り付け方法が望まれている。
また、ここまで述べてきた材料への製品の割り付けの問題は、容積が互いに異なる複数種類の容器に複数種類の製品を充填する場合の問題と等価である。
【0012】
本発明はこのような事情に鑑みてなされたものであり、長さ又は容積が互いに異なる複数種類の母体(材料,容器)に対して複数種類の製品の割り付けを効率的に行うことができる製品割り付け決定装置を提供するものである。
【課題を解決するための手段および発明の効果】
【0013】
本発明の製品割り付け決定装置(以下、単に製品割り付け装置とも呼ぶ)は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置であって、(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付け部と、(3)前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、(4)前記個体適応率に基づいて個体の選択を行う個体選択部と、(5)前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、(7)終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする。
【0014】
非特許文献1に記載のEEMでは、遺伝子毎にその製品が割り付けられた材料の残材率(=1-材料歩留)の関数である交叉制御パラメータ(Crossover Control Parameter :CCP)を定義し、CCPを遺伝子が引き継がれる確率として、次のルールで親1と親2から子1と子2を生成した(子2は親1と親2の関係を入れ替える)。
CCPi(親1)≧Rndならば、子1のi番目の遺伝子=親1のi番目の遺伝子
CCPi(親1)<Rndならば、子1のi番目の遺伝子=親2のi番目の遺伝子
但し、CCPi(親1)は親1のi番目の遺伝子のCCP、Rndは[0,1)の乱数
【0015】
EEMも遺伝子単位に残材率の低い「良い遺伝子」が引き継がれる傾向が得られるようにCCP関数を定義することで、総体としての個体の収束性を確保しているが、この方式では子は“良い遺伝子”を片親からのみ引き継ぐことになる。一方、本発明の方式では、それぞれの親から歩留の高い「良い遺伝子」を引き継ぐことができるため、さらに良い収束性が期待できる。
従って、本発明によれば、長さ又は容積が互いに異なる複数種類の母体(材料,容器)に対して複数種類の製品の割り付けを効率的に行うことができる。
以下、本発明の種々の実施形態を例示する。
【0016】
前記母体は、長さが互いに異なる複数種類の母材であるか,又は容積が互いに異なる複数種類の容器であってもよい。
前記初期集団生成部は、所定の規則に従った方法による個体の生成と、乱数を用いた方法による個体の生成とを組み合わせることによって初期の集団を生成してもよい。所定の規則に従って生成された個体の割合は、10~90%であってもよい。
【0017】
前記個体適応率は、(全製品の長さ又は容積の合計)/(使用した全母体の長さ又は容積の合計)で定義される個体歩留が1に近づくにつれて値の上昇度が大きくなる関数に基づいて算出してもよい。
【0018】
製品iについての前記遺伝子適応率は、製品iが母体kに割り付けられるとき(母体kに割り付けられる全製品の長さ又は容積の合計)/(母体kの長さ又は容積)で定義される材料歩留に基づいて算出してもよい。
遺伝子Pは、製品iが母体kに割り付けられるとき(母体kに割り付けられる全製品の長さ又は容積の合計)/(母体kの長さ又は容積)で定義される材料歩留に基づいて算出され、前記算出部は、前記製品割り付け部による割り付けの結果に基づいて前記遺伝子Pを更新してもよい。
前記個体選択部は、前記個体適応率が高い所定数の個体を選択するエリート選択と、前記個体適応率に比例するように所定数の個体を選択するルーレット選択を組み合わせた方法によって個体の選択を行ってもよい。
【0019】
また、本発明は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置であって、
(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成ステップと、
(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付けステップと、
(3)前記製品割り付けステップによる割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出ステップと、
(4)前記個体適応率に基づいて個体の選択を行う個体選択ステップと、
(5)前記個体選択ステップによって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉ステップと、
(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理ステップと、
(7)終了基準が満たされるまで前記製品割り付けステップ、前記算出ステップ,前記個体選択ステップ、前記交叉ステップ及び前記多様化処理ステップによる処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断ステップとを備え、
前記交叉ステップは、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする製品割り付け決定装置を提供するものである。
【0020】
また、本発明は、コンピュータを長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置として機能させる製品割り付けプログラムであって、コンピュータを(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付け部と、(3)前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、(4)前記個体適応率に基づいて個体の選択を行う個体選択部と、(5)前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、(7)終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部として機能させ、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成することを特徴とする製品割り付けプログラムも提供する。
ここで例示した種々の実施形態は、互いに組み合わせることができる。
【図面の簡単な説明】
【0021】
【図1】本発明の一実施形態の製品割り付け装置の構成を示すブロック図である。
【図2】本発明の一実施形態の製品割り付け装置による製品割り付けの流れを示すフローチャートである。
【図3】本発明の一実施形態の製品割り付け装置による交叉操作の概念図である。
【図4】本発明の製品割り付け装置が対象とする材料と製品の一例を示す。
【図5】図5(a)、(b)は、それぞれ、材料への製品の割り付けの例を示す。
【発明を実施するための形態】
【0022】
以下,本発明の一実施形態を図面を用いて説明する。図面や以下の記述中で示す内容は,例示であって,本発明の範囲は,図面や以下の記述中で示すものに限定されない。

【0023】
本発明の一実施形態の製品割り付け装置は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置であって、(1)製品を割り付ける母体の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、(2)各個体の染色体B及び染色体Pに基づいて製品を母体に割り付ける製品割り付け部と、(3)前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、(4)前記個体適応率に基づいて個体の選択を行う個体選択部と、(5)前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、(6)選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、(7)終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成する。

【0024】
以下、長さが互いに異なる複数種類の材料に対して複数種類の製品の割り付けを行う方法と、この方法を実行することができる製品割り付け装置を例に挙げて説明を進める。
上記のように、母体は、母材または容器を意味するが、以下の説明では、一つの実施例として、母体を、母材あるいは材料と表記する。
また、以下の説明は、容積が互いに異なる複数種類の容器に対して複数種類の製品の割り付けを行う方法と、この方法を実行することができる製品割り付け装置についても当てはまる。

【0025】
以下の説明では、表1に示す記号を用いた。なお、材料の長さ種別を「材長種」と表現した。材料kは、上記した母体kに相当する。

【0026】
【表1】
JP0005302080B2_000002t.gif

【0027】
1.製品割り付け装置が対象とする問題
本実施形態の製品割り付け装置が対象とする問題について説明する。
今、m種類の長さbt(t=1,・・・,m)の材料が十分にあり、これから長さli(i=1,・・・,n)の製品n本を切り出すとき、材長種tの材料の使用コストをctとすると、CSP(Cutting Stock Problems)は、
【数1】
JP0005302080B2_000003t.gif
と表せる。(2)式は材料に割り付けられた製品の長さ合計が材料の長さ以下であること、(3)式はすべての製品はどれかの材料に割り付けられること、(4)式は1つの製品が同時に複数の材料に割り付けられないことを示している。

【0028】
CSPでは歩留最大を狙うのが一般的である。歩留yは次式で表され、
【数2】
JP0005302080B2_000004t.gif
ここで分子の製品長累計は所与であるので、(1)式で使用コストctを材長btに置き換えて
【数3】
JP0005302080B2_000005t.gif
とすればよい。なお、実際のCSPでは材料の両端を整える「鼻切」および製品を切り出す際の「鋸代」を考慮する必要があるが、本質的な問題ではない。
以上の内容において、m=1とすれば通常の一次元ビンパッキング問題(Bin Packing Problem: BPP)となることは言うまでも無い。

【0029】
2.製品割り付け装置の構成
図1のブロック図を用いて製品割り付け装置1の構成について説明する。
製品割り付け装置1は、コンピュータを用いて構成され、演算を行うCPU(演算部)11と、演算に伴って発生する一時的な情報を記憶するRAM(記憶部)12と、CD-ROMドライブ等の外部記憶装置13と、ハードディスク等の内部記憶装置14とを備える。CPU11は、CD-ROM等の本発明の記録媒体2からコンピュータプログラムを外部記憶装置13にて読み取り、読み取ったコンピュータプログラムを内部記憶装置14に記憶し、RAM12にコンピュータプログラムをロードし、ロードしたコンピュータプログラムに基づいて製品割り付けに必要な処理を実行する。すなわち、このコンピュータプログラムが、コンピュータを初期集団生成部、製品割り付け部、算出部、個体選択部、交叉部、多様化処理部、終了判断部として機能させる。
入力部15は、材料や製品の仕様や種々の実行条件等の入力を受け付ける。また、出力部16は、製品割り付けの結果を画面やプリンタ等に出力する。

【0030】
3.製品割り付け決定方法
次に、製品割り付け装置1を用いて製品割り付けを行う方法について図2のフローチャートに沿って説明する。この方法は、主として、図2に示すような7つのステップからなる。

【0031】
3-1.初期集団生成部(初期集団生成ステップ)
まず、初期集団生成部が、製品を割り付ける材料の種類を指定する遺伝子Bを製品毎に有する染色体Bと、製品を割り付ける順序を指定する遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成する。

【0032】
(1)遺伝子Bと遺伝子Pについて
製品割り付け装置1では、割り付ける製品の並びを染色体で表現し、製品を割り付ける材長種を指定する遺伝子(以下、「遺伝子B」,「GeneB」と称する。)と同じ材長種に割り付けられた製品群の中での割り付ける順序を指定するソートキーとなる遺伝子(以下「遺伝子P」,「GeneP」と称する。)の2重遺伝子構造の染色体を有する個体を用いる。

【0033】
遺伝子Bと遺伝子Pの表現方法は、特に限定されないが、一例では、以下に示す方法で表現することができる。
まず、製品iをi番目の遺伝子座に対応させ、割り付ける材長種をti、割り付け順をsiとし、製品iの長さをli、材長種tの材料の集合をBt、長さをbt、Btに属する材料をk(t)(=1,2,・・・)としてこれに割り付けられた製品の集合をIk(t)とする
。このとき材料k(t)の歩留yk(t)は次式で定義される。この歩留は、(5)式の全体歩留に対して材料単位の歩留であり、以下、(5)式を「個体歩留」、(7)式を「材料歩留」と呼ぶ。

【0034】
【数4】
JP0005302080B2_000006t.gif

【0035】
この材料歩留を用いて製品iの遺伝子座の各遺伝子は、下記のように表現することができる。
【数5】
JP0005302080B2_000007t.gif

【0036】
ここでεは同じ材料に割り付けられた製品グループが確実に同じ値となるための定数で、材料歩留に対して十分に小さな値とする。表2に遺伝子Bと遺伝子Pの構造を示す。

【0037】
【表2】
JP0005302080B2_000008t.gif

【0038】
(9)式のように遺伝子Pを定義すると、より高い材料歩留の材料に割り付けられた製品の遺伝子Pは小さな値になり、優先的に割り付けが行われる。このため、材料歩留の高い材料-製品グループが材料歩留の低い製品によって破壊されることが抑制され、収束性が向上する。なお、遺伝子Pの初期値は、乱数を用いて決定することができる。

【0039】
(2)初期集団生成方法について
次に、初期集団生成部が初期の集団を生成する方法について説明する。
初期集団生成部は、遺伝子Bを製品毎に有する染色体Bと、遺伝子Pを製品毎に有する染色体Pとを有する個体を複数生成することによって初期の集団を生成することができる。

【0040】
各個体を生成する方法は、特に限定されず、所定の規則に従った方法によって個体を生成してもよく、乱数を用いた方法によって個体を生成してもよい。所定の規則に従った方法とは、予め定めてあるルールに従って製品を材料に割り当て、その結果に基づいて遺伝子B及び遺伝子Pを設定する方法である。この方法の例としては、本発明者らによる非特許文献2に記載されたRevised First Fit Descending (RFFD)法や特に製品の並びに条件をつけないで同じアルゴリズムを適用するRevised First Fit (RFF)法が挙げられるが、これらに限定されない。

【0041】
一般に所定の規則に従った方法によって個体を生成した場合、個体が最初から比較的優秀であるので迅速に収束する反面、局所解への落ち込みが起こり易いという特徴がある。一方、乱数を用いた方法によって個体を生成した場合、局所解への落ち込みが起こり難い反面、収束までに時間がかかるという特徴がある。そこで、所定の規則に従った方法によって一部の個体を生成し、乱数を用いた方法によって残りの個体を生成することによって初期の集団を生成することによって局所解への落ち込みを抑制しつつ収束を早めることができる。所定の規則に従った方法によって生成する個体の割合は、例えば10~90%である。この割合は、具体的には10,20,30,40,50,60,70,80,90%である。この割合は、ここで例示した数値の何れか2つの間の範囲内であってもよい。材料種と製品の組み合わせによって所定の規則に従った方法のみ又は乱数を用いた方法のみによって個体を生成した方がいい結果が得られる可能性はあるが、両者を組み合わせた方がいい結果が得られる可能性が高いと考えられる。

【0042】
以下、初期の集団の生成方法の一例を示す。
この例では、1個体にはRFFDを適用し、残りの個体には必要回数製品をランダムに並び替えてRFFを適用し生成する。但し、初期個体の多様性を確保するために、すべてをRFFDおよびRFFで生成するのではなく、あらかじめ決められたRFF生成比率αに相当する個体数とし、残りは乱数によって生成する。具体的な遺伝子の初期設定方法は以下のように行う。

【0043】
【数6】
JP0005302080B2_000009t.gif

【0044】
ここでβは(9)式で得られる遺伝子Pの値の範囲から突出しないためのパラメータで、先行実験によって残材率の分布をみておよそ下限値になるようを設定する。

【0045】
3-2.製品割り付け部(製品割り付けステップ)
次に、製品割り付け部が、各個体の染色体B及び染色体Pに基づいて製品を材料に割り付ける。
製品割り付けの方法は、特に限定されないが、一例では、以下の製品割り付けルールに従って行うことができる。なお、「鼻切」と「鋸代」は材料長や製品長の調整で組み込むことができるので、ここでは単純化のため無視する。

【0046】
【数7】
JP0005302080B2_000010t.gif

【0047】
3-3.算出部(算出ステップ)
次に、算出部が、前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する。また、遺伝子Pが材料歩留に基づいて算出される場合、算出部は、製品割り付け部による割り付けの結果に基づいて遺伝子Pの更新を行うことが好ましい。

【0048】
(1)個体適応率
個体適応率は、各個体の優劣を示す指標となるものであればその表現方法は特に限定されない。一例では、個体適応率は、(5)式で示される個体歩留が1に近づくにつれて値の上昇度が大きくなる関数に基づいて算出される。このように設定することによって、個体歩留が大きい個体が個体選択部によって選択される可能性が高まり収束性が向上する。
個体適応率aは、一例では、(5)式の個体歩留y(0≦y≦1)を関数Fでスケーリングしたものであり、(16)式のように表現することができる。

【0049】
【数8】
JP0005302080B2_000011t.gif

【0050】
この適応率は「選択」フェーズでの個体の選択基準となるため、個体の生存分布はこの関数に依存し、その結果収束性に影響を与える。最適値への収束性のためには個体の多様性と優秀性のバランスが重要である。そのため個体適応率は個体歩留yが平均歩留より小さい範囲では小さく、平均値から最大値にかけて大きく変化する関数によってスケーリングするのが合理的である。このような関数の一例は、F(y)=y10である。

【0051】
(2)遺伝子適応率
遺伝子適応率は、各個体における各製品の割り付けの優劣を示す指標となるものであればその表現方法は特に限定されない。一例では、遺伝子適応率GFR(Gene Fitness Ratio)
は、(11)式のように、材料歩留まりを用いて表現することができる。(11)式によれば、材料歩留まりが高い材料に割り付けられている製品に対応する遺伝子の遺伝子適応率が高くなり、このような遺伝子が交叉操作で生成される次世代の個体に引き継がれやすい。

【0052】
【数9】
JP0005302080B2_000012t.gif

【0053】
3-4.個体選択部(個体選択ステップ)
次に、個体選択部が、前記個体適応率に基づいて個体の選択を行う。選択の方法は、個体適応率が利用されるものであれば特に限定されない。

【0054】
選択の方法としては、例えば、個体適応率が高い所定数の個体を選択するエリート選択による方法や、個体適応率に比例するように所定数の個体を選択するルーレット選択による方法や、これらを組み合わせた方法が挙げられる。エリート選択のみだと多様性が失われて局所解に落ち込みやすくなり、ルーレット選択のみだと収束性が良くないので、エリート選択とルーレット選択を組み合わせることが好ましい。

【0055】
個体選択部が選択する個体の割合は、特に限定されないが、例えば、10~90%である。この割合は、具体的には例えば10,20,30,40,50,60,70,80,90%である。この割合は、ここで例示した数値の何れか2つの間の範囲内であってもよい。また、エリート選択とルーレット選択を組み合わせる場合、選択する個体のうち例えば3~30%をエリート選択によって選択する。この割合は、具体的には例えば3,5,10,15,20,25,30%である。この割合は、ここで例示した数値の何れか2つの間の範囲内であってもよい。

【0056】
3-5.交叉部(交叉ステップ)
次に、交叉部が、前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する。また、交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Bと遺伝子Pを選択するという操作を製品毎に行うことによって生成された染色体B及び染色体Pを有する個体を生成する。
つまり、この交叉方法では、次のような交叉操作であらたな子を生成する。

【0057】
【数10】
JP0005302080B2_000013t.gif
ここで、個体Aのi番目の遺伝子座の遺伝子Bをti(A),遺伝子Pをsi(A),遺伝子適応率GFRをgi(A)と表現した。図3に例を示す。図3ではわかりやすくするため遺伝子ではなく割り付けられた材料とGFRのみ記した。この例ではB,E,Hの材長種と製品グループ(シャドウ部分)が子に引き継がれる。
このような交叉方法を以下、対戦交叉法(Tournament Crossover Operation Method: TCOM)」と呼ぶ。

【0058】
非特許文献1に記載のEEMでは、TCOMモデルと同じ遺伝子構造を持ち、遺伝子毎にその製品が割り付けられた材料の残材率(=1-材料歩留)の関数である交叉制御パラメータ(Crossover Control Parameter :CCP)を定義し、CCPを遺伝子が引き継がれる確率として、次のルールで親1と親2から子1と子2を生成した(子2は親1と親2の関係を入れ替える)。

【0059】
【数11】
JP0005302080B2_000014t.gif

【0060】
EEMも遺伝子単位に残材率の低い“良い遺伝子”が引き継がれる傾向が得られるようにCCP関数を定義することで、総体としての個体の収束性を確保しているが、この方式では子は“良い遺伝子”を片親からのみ引き継ぐことになる。一方、TCOMモデルでは、それぞれの親から歩留の高い“良い遺伝子”を引き継ぐことができるため、さらに良い収束性が期待できる。

【0061】
3-7.多様化処理部(多様化処理ステップ)
次に、多様化処理部が、選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理を行う。この処理によって局所解への落ち込みを抑制することができる。

【0062】
多様化処理は、一例では、交叉処理の後に行われるが、多様化処理を行うタイミングは、特に限定されず、交叉処理の前や個体選択の前に行ってもよい。
多様化処理を行う個体の選択は、ランダムな方法によって行ってもよいが、例えば個体適応率が低い個体を優先的に選択する等、完全にランダムな方法以外の方法で行ってもよい。

【0063】
多様化処理の対象となる個体の割合は、特に限定されないが、例えば5~40%程度である。この割合は、具体的には例えば5,10,20,30,40%である。この割合は、ここで例示した数値の何れか2つの間の範囲内であってもよい。

【0064】
突然変異では、選択された個体中の選択された遺伝子を変異させる。遺伝子の選択は、ランダムな方法によって行ってもよいが、例えば遺伝子適応率が低い遺伝子を優先的に選択する等、完全にランダムな方法以外の方法で選択を行ってもよい。遺伝子を変異させる方法は特に限定されないが、一例では、(15)式の遺伝子Bおよび遺伝子P設定ルールに従って遺伝子を再設定することによって変異させることができる。変異させる遺伝子座の割合は、特に限定されないが、例えば3~30%である。この割合は、具体的には例えば3,5,10,20,30%である。この割合は、ここで例示した数値の何れか2つの間の範囲内であってもよい。突然変異は、遺伝子Bと遺伝子Pの何れか一方のみ起こるようにしてもよく、両方に起こるようにしてもよい。遺伝子Bが突然変異した場合、変異後の内容に基づいて遺伝子Pを更新することが合理的であり好ましい。一方、遺伝子Pの場合は単独で変化させることが好ましい。

【0065】
個体の入れ替えは、選択された個体を削除し、同じ数の個体を「3-1.初期集団生成」の項で説明した方法で生成するによって行うことができる。この場合、所定の規則に従った方法によって生成する個体の割合は、初期集団生成の場合と同じであっても異なっていてもよい。

【0066】
3-8.終了判断部(終了判断ステップ)
次に、終了判断部が、終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する。
終了基準は、特に限定されないが、例えば、(1)集団に属する個体のうち個体適応率が最大のものの個体適応率が目標値を超える、(2)集団の世代数が基準値を超える等が挙げられる。(2)のみを終了基準としてもよいが、目標の個体適応率を超えた後に処理を続けるのは効率的でない場合があるので(1)と(2)の基準を併用して(1)又は(2)の条件が満たされたときに終了基準が満たされたと判断することが好ましい。

【0067】
終了後は、集団に属する個体のうち個体適応率が最大のもの染色体Bと染色体Pを用いて上述した製品割り付けルールに従って製品を材料に割り付けることによって高い歩留まりで製品割り付けを行うことができる。

【0068】
以上の実施形態で示した種々の特徴は,互いに組み合わせることができる。1つの実施形態中に複数の特徴が含まれている場合,そのうちの1又は複数個の特徴を適宜抜き出して,単独で又は組み合わせて,本発明に採用することができる。

【0069】
4.製品割り付けの具体例
以下、上記実施形態の製品割り付け装置を用いた製品割り付けの具体例について説明する。以下の説明では、本発明の製品割り付け装置で採用したモデルを「TCOMモデル」と称する。

【0070】
4-1.BPPベンチマーク問題による比較評価
本TCOMモデルは材料の種類m=1とすればBPPに適用できる。BPPについてはベンチマークのための問題がインターネット上に公開されている(http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm)。そこで我々もTCOMモデルをm=1としてこのベンチマーク問題に適用し、本TCOMモデルとEEMモデルおよび一様交叉モデルとの比較を行うこととする。表3に我々の実行環境を示した。プログラム言語はMicrosoft Excelとインタープリター言語であるVBA(Visual Basic for Application)を使っており、C言語やPascalなどのコンパイル言語に比べて処理効率は低い。

【0071】
【表3】
JP0005302080B2_000015t.gif

【0072】
4-1-1.ベンチマーク問題
ベンチマーク問題はB1,B2,B3の3種類あり、B1はビン容量に対してアイテム容積をまんべんなく設定した780例の問題群であり、B2はビンに入るアイテムの数がおよそ3,5,7,9となるように設定されている480例の問題群である。B3はビン容量が100000に対してアイテムサイズは(20000,35000)の範囲で一様分布し、ビンには3から5つのアイテムが入るように設定される「Very Hard」とされる10例の問題である。我々のモデルは本来はCSPへの適用を目的としており、後出のセクション4-2ではプレカットのCSPに適用している。そこでこれらの問題群のうち比較的プレカットの条件に近いB3のデータを取り上げて比較することとする。なお、ベンチマークの各問題には、現在知られている最小使用ビン数が示されている。我々のモデルは目的関数を個体歩留としているが、材料の種類m=1の場合は個体歩留と使用材料数は目的関数として同値である。

【0073】
4-1-2.パラメータ、関数形の設定
個体数と世代数はそれぞれ100個体、1000世代とし、10回繰返し試行し最も良い結果を採用する。計算時間は最小解(最小解が得られない場合は準最小解)が得られた時点までとする。適応率関数と各種のパラメータは、予備実験の結果を踏まえ(17)式のように設定した。なお、鼻切および鋸代は考えない。

【0074】
【数12】
JP0005302080B2_000016t.gif

【0075】
EEMモデルの収束に大きな影響を与えることがわかっている交叉制御パラメータCCPの関数形は、プレカットのCSPに適用した際に最も良い結果を出した下記の関数形を採用する。

【0076】
【数13】
JP0005302080B2_000017t.gif

【0077】
さらにRFFによる初期個体生成が結果に及ぼす影響を評価するため、RFFによる初期個体の生成率αをそれぞれ1(All RFF),0.5(50%RFF),0(All RN:乱数)とした場合を比較評価する。なお、一様交叉とEEMではα=0.5とした。また前節の比較でのTCOMはα=0.5を採用している。

【0078】
4-1-3.収束性の評価
この結果を表4に示す。一様交叉ではまったく最小解を得られなかった。絶対偏差も平均3となっており、Falkenauerが指摘したように製品の並びを遺伝子表現するモデルでは、従来型の交叉方法では収束性が極めて悪いことがわかる。またEEMでは得られた最小解は1つであった。このモデルは優秀な遺伝子を片方の親からしか引き継げないため、両方から引き継ぐ本TCOMモデルに比べて収束性が悪いものと推定される。

【0079】
一方、初期個体の生成については、α=0.5が最も良い結果となった。RFFによって生成された個体はある程度の高い適応度(個体歩留)を持つことがわかっているが、すべてをRFFで生成するとかえって結果が悪くなるのは、初期個体群が多様性を欠いた結果、局所解に陥ったと推定できる。また、すべてを乱数で発生させた場合はα=0.5の場合と同じ数の最小解を得たが、初期個体の歩留水準が低いため最小解までに多くの世代経過を必要し時間が長くかかっている。

【0080】
【表4】
JP0005302080B2_000018t.gif

【0081】
4-2.住宅プレカット材料取り合わせ問題への適用
本TCOMモデルはCSPを対象とするGAモデルである。そこで典型的なCSPである住宅のプレカット材のCSPに適用する。

【0082】
4-2-1.住宅プレカットデータ
住宅プレカットCSPとは、いくつかの種類の長さを持つ木材母材から、住宅建築で要求される長さの部材(製品)を切り出す問題である。ここでは標準的な2つの一戸建て住宅の横架材を対象にした(表5,表6)。これらの横架材は、断面形状(Shape)や樹種(Spec.)、等級(Grade)など同じ母材から切り出すことができる16および18のロットにグループに分けることができ、それぞれのロット毎に切り出す製品数(Num.)や使用する母材群(Kinds of Material)も異なる。ロット毎の歩留は(5)式の長さ歩留で計算できるが、邸全体の歩留はロット毎に断面形状が異なるため体積による材積歩留で比較する。すなわち、邸の材積歩留=全製品体積/全使用材料体積とする。

【0083】
【表5】
JP0005302080B2_000019t.gif

【0084】
【表6】
JP0005302080B2_000020t.gif

【0085】
4-2-2.比較する手法
提案のTCOMモデルを評価するに当たって、プレカット材料への適用事例の文献がないため、我々が既にプレカットCSPに適用して報告しているEEMモデルおよび特許されているプレカットCSPのヒューリスリックアルゴリズム(特許文献1)との比較を行うことにする。

【0086】
今回比較対象とした特許文献1のアルゴリズムは、すべての製品の長さ合計に対してその合計長以上になる複数母材長の母材の組み合わせをリストアップし、リストアップした母材の組み合わせで母材長合計の昇順にすべての製品が割り付けられるかを判断するステップと、割り付け可能な最小母材長合計の組み合わせに対して、さらに母材長合計が小さくなる母材の組み合わせを探査するステップからなる方法であり、既に実際に使われているものである。

【0087】
4-2-3.実行結果の比較
TCOMモデルはBPPへの適用時と同じく個体数を100として1000世代までの実行を10回繰返した最良値を採用し、処理時間は最良値が得られる時間までとする。そのほかのパラメータも同じ(17)式、(18)式とした。実行結果を表7に示す。EEMと特許文献1の結果は前回の報告値とした。なお、鼻切は0mm、鋸代は5mmとした。この結果、2つのGAモデルはまったく同等の結果となり、特許アルゴリズムより優位な結果が得られた。邸1のEEMの数字は最適値であることがわかっており、邸2についても最適解かあるいはそれに近い値と推定できる。したがってTCOMとEEMの優劣はつかなかったものと考えられる。

【0088】
【表7】
JP0005302080B2_000021t.gif

【0089】
4-2-4.実用に向けての検討
GAを実用手法として使う場合、実行結果が確率的に変化するため、実行結果の評価と処理時間をどのようにバランスされるかが課題となる。BPPベンチマークデータのように最適値がわかっている場合は、あらかじめ設定した世代数が経過するか最適値が達成したら終了すればよいが、一般には最適値はわからない。そこで最適解であることがわかっている邸1について最適値が得られるまでの世代推移を分析し、10回の繰返しで最適値が少なくとも1回出現するような世代数を設定することで処理時間の短縮を図る。RFFで初期個体を生成すると、確率的に最初から最適解となる場合があるので、(17)式でRFF生成比率α=0として、最大歩留(最適値)が得られるまでの状況の詳細を表8に示した。この表で「Num. of Prd.」は製品数、「Num. of Mtr.」は材長種の数、「Max. Rate」は最大歩留、「Max. Num.」は10回の実行で最大歩留が得られた回数、「Generation」の欄は最大歩留までの経過世代数の最大値、最小値、平均値および標準偏差、「Time」は1000世代までの実行時間(秒)である。1000世代まで実行すると、この邸の取り合わせ計算には162秒×10回=約27分かかることになる。

【0090】
【表8】
JP0005302080B2_000022t.gif

【0091】
この結果、No.1とNo.7のロットを除いて10回の実行のすべてが最適値となっており、最も少ないロットNo.1でも最適値が5回出現している。最適値に至るまでの世代数は製品数と材長種数の組み合わせに対して正の相関を持ち、製品数×材長種数が100を超えると世代数に大きな影響を与えているように見える。そこで仮に以下のように実行世代数を定め、RFF生成比率α=0.5に戻して実行し時間短縮を図る。

【0092】
【数14】
JP0005302080B2_000023t.gif

【0093】
表9に(19)式の設定で実行した結果を示した。ここで「Max Gen.」が実行世代数である。全体の処理時間は3分(18秒×10回)となったが、すべてのロットで最大歩留を得た。同じ(19)式のルールで実行した邸2の結果も表9に併記しているが、1000世代の場合と同じ結果を4分以内(22秒×10回)で出すことができた。

【0094】
【表9】
JP0005302080B2_000024t.gif

【0095】
以上の結果から、本TCOMモデルを一般の木造住宅プレカットCSPに実際に適用する場合、たとえば実行世代数として(19)式のルールを適用すれば、数分程度の処理時間で極めて高い歩留を得られることがわかる。

【0096】
4-3.まとめ
複数材長の一次元CSPを対象にGAモデルを検討した。敢えて従来から非効率性を指摘されていたアイテム単位の遺伝子構造を持つモデルとして、遺伝子毎の適応率(GFR)を導入してその比較によって交叉を制御することで、安定的に高い歩留を得る対戦交叉操作モデル(TCOM)を提案した。これをBPPのベンチマークデータに適用し、TCOMの有効性と拡張エリート選択(EEM)モデルと比べた優位性を確認するとともに、プレカットCSPデータにも適用し、一般のプレカット工場では通常90%以下といわれている歩留を、数分の処理時間で95%前後まで向上させることができた。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4