(57)【要約】【課題】長さ又は容積が互いに異なる複数種類の母体（材料，容器）に対して複数種類の製品の割り付けを効率的に行うことができる製品割り付け決定装置を提供する。【解決手段】本発明の製品割り付け装置は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置であって、交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする。【選択図】図２
2010009585.tif 000002
【特許請求の範囲】
【請求項１】
長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置であって、
（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、
（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付け部と、
（３）前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、
（４）前記個体適応率に基づいて個体の選択を行う個体選択部と、
（５）前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、
（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、
（７）終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、
前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする製品割り付け決定装置。
【請求項２】
前記母体は、長さが互いに異なる複数種類の母材であるか,又は容積が互いに異なる複数種類の容器である請求項１に記載の装置。
【請求項３】
前記初期集団生成部は、所定の規則に従った方法による個体の生成と、乱数を用いた方法による個体の生成とを組み合わせることによって初期の集団を生成する請求項１又は２に記載の装置。
【請求項４】
所定の規則に従った方法によって生成された個体の割合は、１０〜９０％である請求項３に記載の装置。
【請求項５】
前記個体適応率は、（全製品の長さ又は容積の合計）/（使用した全母体の長さ又は容積の合計）で定義される個体歩留が１に近づくにつれて値の上昇度が大きくなる関数に基づいて算出される請求項１〜４の何れか１つに記載の装置。
【請求項６】
製品ｉについての前記遺伝子適応率は、製品ｉが母体ｋに割り付けられるとき（母体ｋに割り付けられる全製品の長さ又は容積の合計）/（母体ｋの長さ又は容積）で定義される材料歩留に基づいて算出される請求項１〜５の何れか１つに記載の装置。
【請求項７】
遺伝子Ｐは、製品ｉが母体ｋに割り付けられるとき（母体ｋに割り付けられる全製品の長さ又は容積の合計）/（母体ｋの長さ又は容積）で定義される材料歩留に基づいて算出され、
前記算出部は、前記製品割り付け部による割り付けの結果に基づいて前記遺伝子Ｐを更新する請求項１〜６の何れか１つに記載の装置。
【請求項８】
前記個体選択部は、前記個体適応率が高い所定数の個体を選択するエリート選択と、前記個体適応率に比例するように所定数の個体を選択するルーレット選択を組み合わせた方法によって個体の選択を行う請求項１〜７の何れか１つに記載の装置。
【請求項９】
長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定方法であって、
（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成ステップと、
（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付けステップと、
（３）前記製品割り付けステップによる割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出ステップと、
（４）前記個体適応率に基づいて個体の選択を行う個体選択ステップと、
（５）前記個体選択ステップによって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉ステップと、
（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理ステップと、
（７）終了基準が満たされるまで前記製品割り付けステップ、前記算出ステップ,前記個体選択ステップ、前記交叉ステップ及び前記多様化処理ステップによる処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断ステップとを備え、
前記交叉ステップは、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする製品割り付け決定方法。
【請求項１０】
コンピュータを長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置として機能させる製品割り付けプログラムであって、
コンピュータを
（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、
（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付け部と、
（３）前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、（４）前記個体適応率に基づいて個体の選択を行う個体選択部と、
（５）前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、
（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、
（７）終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部として機能させ、
前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする製品割り付けプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置及び製品割り付けプログラムに関する。
【背景技術】
【０００２】
住宅構造材のプレカット等では、一般に、図４に示すように、長さが互いに異なる複数種類の材料から複数種類の製品を切り出す。それぞれの長さの材料の使用本数には制限が設けられず、ある長さの材料を複数本使用することも可能である。このような条件下では、材料への製品の割り付けは、図５（ａ）や図５（ｂ）に例示するように様々な方法で行うことができる。一般に、残材の合計長さが短いほど割り付け方法が適切であるが、残材の合計長さを最小化するように製品の割り付けを行うことは容易ではない。
【０００３】
本発明者らは、以前に、製品の並びを遺伝子配列として一種のOrdered-basedモデル（製品の切り出し順に注目するモデル）に対して遺伝子レベルの交叉制御を行う拡張エリート選択法（Extended Elitism Method:EEM）を提案して、一般のプレカット向上では９０％以下と言われている歩留まりを９５％前後にまで向上させた（非特許文献１を参照。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３５６５２６２号
【非特許文献】
【０００５】
【非特許文献１】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.
【０００６】
【非特許文献２】Toyoda J. and Takeyasu K.: A Revised First Fit Algorithm for Timber Precutting. International Journal of Computational Science 2-1, (2008), pp.92-107.
【０００７】
【非特許文献３】八川 徹也, 飯間 等, 三宮 信夫: ビンパッキング問題に対する遺伝的アルゴリズムの提案, 計測自動制御学会論文集, Vol.41, No.3, (2005), pp.274-282.
【０００８】
【非特許文献４】Fleszar, K., Hindi, K. S.: New heuristics for one dimensional bi  n-packing, Computer & Operations Research 29 (2002) pp.821-839.
【０００９】
【非特許文献５】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
【００１０】
【非特許文献６】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.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
非特許文献１に記載の方法は非常に優れた方法ではあるが、収束性が良くない場合もある。従って、収束性がさらに優れた割り付け方法が望まれている。
また、ここまで述べてきた材料への製品の割り付けの問題は、容積が互いに異なる複数種類の容器に複数種類の製品を充填する場合の問題と等価である。
【００１２】
本発明はこのような事情に鑑みてなされたものであり、長さ又は容積が互いに異なる複数種類の母体（材料，容器）に対して複数種類の製品の割り付けを効率的に行うことができる製品割り付け決定装置を提供するものである。
【課題を解決するための手段および発明の効果】
【００１３】
本発明の製品割り付け決定装置（以下、単に製品割り付け装置とも呼ぶ）は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け決定装置であって、（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付け部と、（３）前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、（４）前記個体適応率に基づいて個体の選択を行う個体選択部と、（５）前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、（７）終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする。
【００１４】
非特許文献１に記載のＥＥＭでは、遺伝子毎にその製品が割り付けられた材料の残材率(＝１−材料歩留)の関数である交叉制御パラメータ(Crossover Control Parameter :CCP)を定義し、ＣＣＰを遺伝子が引き継がれる確率として、次のルールで親１と親２から子１と子２を生成した（子２は親１と親２の関係を入れ替える）。
CCPi(親1)≧Rndならば、子１のｉ番目の遺伝子=親１のｉ番目の遺伝子
CCPi(親1)＜Rndならば、子１のｉ番目の遺伝子=親２のｉ番目の遺伝子
但し、CCPi(親1)は親1のｉ番目の遺伝子のCCP、Rndは[0,1)の乱数
【００１５】
ＥＥＭも遺伝子単位に残材率の低い「良い遺伝子」が引き継がれる傾向が得られるようにＣＣＰ関数を定義することで、総体としての個体の収束性を確保しているが、この方式では子は“良い遺伝子”を片親からのみ引き継ぐことになる。一方、本発明の方式では、それぞれの親から歩留の高い「良い遺伝子」を引き継ぐことができるため、さらに良い収束性が期待できる。
従って、本発明によれば、長さ又は容積が互いに異なる複数種類の母体（材料，容器）に対して複数種類の製品の割り付けを効率的に行うことができる。
以下、本発明の種々の実施形態を例示する。
【００１６】
前記母体は、長さが互いに異なる複数種類の母材であるか,又は容積が互いに異なる複数種類の容器であってもよい。
前記初期集団生成部は、所定の規則に従った方法による個体の生成と、乱数を用いた方法による個体の生成とを組み合わせることによって初期の集団を生成してもよい。所定の規則に従って生成された個体の割合は、１０〜９０％であってもよい。
【００１７】
前記個体適応率は、（全製品の長さ又は容積の合計）/（使用した全母体の長さ又は容積の合計）で定義される個体歩留が１に近づくにつれて値の上昇度が大きくなる関数に基づいて算出してもよい。
【００１８】
製品ｉについての前記遺伝子適応率は、製品ｉが母体ｋに割り付けられるとき（母体ｋに割り付けられる全製品の長さ又は容積の合計）/（母体ｋの長さ又は容積）で定義される材料歩留に基づいて算出してもよい。
遺伝子Ｐは、製品ｉが母体ｋに割り付けられるとき（母体ｋに割り付けられる全製品の長さ又は容積の合計）/（母体ｋの長さ又は容積）で定義される材料歩留に基づいて算出され、前記算出部は、前記製品割り付け部による割り付けの結果に基づいて前記遺伝子Ｐを更新してもよい。
前記個体選択部は、前記個体適応率が高い所定数の個体を選択するエリート選択と、前記個体適応率に比例するように所定数の個体を選択するルーレット選択を組み合わせた方法によって個体の選択を行ってもよい。
【００１９】
また、本発明は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置であって、
（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成ステップと、
（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付けステップと、
（３）前記製品割り付けステップによる割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出ステップと、
（４）前記個体適応率に基づいて個体の選択を行う個体選択ステップと、
（５）前記個体選択ステップによって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉ステップと、
（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理ステップと、
（７）終了基準が満たされるまで前記製品割り付けステップ、前記算出ステップ,前記個体選択ステップ、前記交叉ステップ及び前記多様化処理ステップによる処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断ステップとを備え、
前記交叉ステップは、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする製品割り付け決定装置を提供するものである。
【００２０】
また、本発明は、コンピュータを長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置として機能させる製品割り付けプログラムであって、コンピュータを（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付け部と、（３）前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、（４）前記個体適応率に基づいて個体の選択を行う個体選択部と、（５）前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、（７）終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部として機能させ、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成することを特徴とする製品割り付けプログラムも提供する。
ここで例示した種々の実施形態は、互いに組み合わせることができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態の製品割り付け装置の構成を示すブロック図である。
【図２】本発明の一実施形態の製品割り付け装置による製品割り付けの流れを示すフローチャートである。
【図３】本発明の一実施形態の製品割り付け装置による交叉操作の概念図である。
【図４】本発明の製品割り付け装置が対象とする材料と製品の一例を示す。
【図５】図５（ａ）、（ｂ）は、それぞれ、材料への製品の割り付けの例を示す。
【発明を実施するための形態】
【００２２】
以下，本発明の一実施形態を図面を用いて説明する。図面や以下の記述中で示す内容は，例示であって，本発明の範囲は，図面や以下の記述中で示すものに限定されない。
【００２３】
本発明の一実施形態の製品割り付け装置は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う製品割り付け装置であって、（１）製品を割り付ける母体の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する初期集団生成部と、（２）各個体の染色体Ｂ及び染色体Ｐに基づいて製品を母体に割り付ける製品割り付け部と、（３）前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する算出部と、（４）前記個体適応率に基づいて個体の選択を行う個体選択部と、（５）前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する交叉部と、（６）選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理部と、（７）終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する終了判断部とを備え、前記交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成する。
【００２４】
以下、長さが互いに異なる複数種類の材料に対して複数種類の製品の割り付けを行う方法と、この方法を実行することができる製品割り付け装置を例に挙げて説明を進める。
上記のように、母体は、母材または容器を意味するが、以下の説明では、一つの実施例として、母体を、母材あるいは材料と表記する。
また、以下の説明は、容積が互いに異なる複数種類の容器に対して複数種類の製品の割り付けを行う方法と、この方法を実行することができる製品割り付け装置についても当てはまる。
【００２５】
以下の説明では、表１に示す記号を用いた。なお、材料の長さ種別を「材長種」と表現した。材料ｋは、上記した母体ｋに相当する。
【００２６】
【表１】
2010009585.tif 000003
【００２７】
１．製品割り付け装置が対象とする問題
本実施形態の製品割り付け装置が対象とする問題について説明する。
今、ｍ種類の長さｂt（ｔ＝１，・・・，ｍ）の材料が十分にあり、これから長さｌi（ｉ＝１，・・・，ｎ）の製品ｎ本を切り出すとき、材長種ｔの材料の使用コストをｃtとすると、ＣＳＰ（Cutting Stock Problemｓ）は、
【数１】
2010009585.tif 000004
と表せる。（２）式は材料に割り付けられた製品の長さ合計が材料の長さ以下であること、（３）式はすべての製品はどれかの材料に割り付けられること、（４）式は１つの製品が同時に複数の材料に割り付けられないことを示している。
【００２８】
ＣＳＰでは歩留最大を狙うのが一般的である。歩留ｙは次式で表され、
【数２】
2010009585.tif 000005
ここで分子の製品長累計は所与であるので、(1)式で使用コストｃtを材長ｂtに置き換えて
【数３】
2010009585.tif 000006
とすればよい。なお、実際のＣＳＰでは材料の両端を整える「鼻切」および製品を切り出す際の「鋸代」を考慮する必要があるが、本質的な問題ではない。
以上の内容において、ｍ＝１とすれば通常の一次元ビンパッキング問題（Bin Packing Problem: BPP）となることは言うまでも無い。
【００２９】
２．製品割り付け装置の構成
図１のブロック図を用いて製品割り付け装置１の構成について説明する。
製品割り付け装置１は、コンピュータを用いて構成され、演算を行うＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報を記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備える。ＣＰＵ１１は、ＣＤ−ＲＯＭ等の本発明の記録媒体２からコンピュータプログラムを外部記憶装置１３にて読み取り、読み取ったコンピュータプログラムを内部記憶装置１４に記憶し、ＲＡＭ１２にコンピュータプログラムをロードし、ロードしたコンピュータプログラムに基づいて製品割り付けに必要な処理を実行する。すなわち、このコンピュータプログラムが、コンピュータを初期集団生成部、製品割り付け部、算出部、個体選択部、交叉部、多様化処理部、終了判断部として機能させる。
入力部１５は、材料や製品の仕様や種々の実行条件等の入力を受け付ける。また、出力部１６は、製品割り付けの結果を画面やプリンタ等に出力する。
【００３０】
３．製品割り付け決定方法
次に、製品割り付け装置１を用いて製品割り付けを行う方法について図２のフローチャートに沿って説明する。この方法は、主として、図２に示すような７つのステップからなる。
【００３１】
３−１．初期集団生成部（初期集団生成ステップ）
まず、初期集団生成部が、製品を割り付ける材料の種類を指定する遺伝子Ｂを製品毎に有する染色体Ｂと、製品を割り付ける順序を指定する遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成する。
【００３２】
（１）遺伝子Ｂと遺伝子Ｐについて
製品割り付け装置１では、割り付ける製品の並びを染色体で表現し、製品を割り付ける材長種を指定する遺伝子（以下、「遺伝子Ｂ」,「GeneB」と称する。）と同じ材長種に割り付けられた製品群の中での割り付ける順序を指定するソートキーとなる遺伝子（以下「遺伝子Ｐ」,「GeneP」と称する。）の２重遺伝子構造の染色体を有する個体を用いる。
【００３３】
遺伝子Ｂと遺伝子Ｐの表現方法は、特に限定されないが、一例では、以下に示す方法で表現することができる。
まず、製品ｉをｉ番目の遺伝子座に対応させ、割り付ける材長種をｔi、割り付け順をｓiとし、製品ｉの長さをｌi、材長種ｔの材料の集合をＢt、長さをｂt、Ｂtに属する材料をｋ(t)（＝１，２，・・・）としてこれに割り付けられた製品の集合をＩk(t)とする
。このとき材料ｋ(t)の歩留ｙk(t)は次式で定義される。この歩留は、（５）式の全体歩留に対して材料単位の歩留であり、以下、（５）式を「個体歩留」、（７）式を「材料歩留」と呼ぶ。
【００３４】
【数４】
2010009585.tif 000007
【００３５】
この材料歩留を用いて製品ｉの遺伝子座の各遺伝子は、下記のように表現することができる。
【数５】
2010009585.tif 000008
【００３６】
ここでεは同じ材料に割り付けられた製品グループが確実に同じ値となるための定数で、材料歩留に対して十分に小さな値とする。表２に遺伝子Ｂと遺伝子Ｐの構造を示す。
【００３７】
【表２】
2010009585.tif 000009
【００３８】
（９）式のように遺伝子Ｐを定義すると、より高い材料歩留の材料に割り付けられた製品の遺伝子Ｐは小さな値になり、優先的に割り付けが行われる。このため、材料歩留の高い材料−製品グループが材料歩留の低い製品によって破壊されることが抑制され、収束性が向上する。なお、遺伝子Ｐの初期値は、乱数を用いて決定することができる。
【００３９】
（２）初期集団生成方法について
次に、初期集団生成部が初期の集団を生成する方法について説明する。
初期集団生成部は、遺伝子Ｂを製品毎に有する染色体Ｂと、遺伝子Ｐを製品毎に有する染色体Ｐとを有する個体を複数生成することによって初期の集団を生成することができる。
【００４０】
各個体を生成する方法は、特に限定されず、所定の規則に従った方法によって個体を生成してもよく、乱数を用いた方法によって個体を生成してもよい。所定の規則に従った方法とは、予め定めてあるルールに従って製品を材料に割り当て、その結果に基づいて遺伝子Ｂ及び遺伝子Ｐを設定する方法である。この方法の例としては、本発明者らによる非特許文献２に記載されたRevised First Fit Descending (RFFD)法や特に製品の並びに条件をつけないで同じアルゴリズムを適用するRevised First Fit (RFF)法が挙げられるが、これらに限定されない。
【００４１】
一般に所定の規則に従った方法によって個体を生成した場合、個体が最初から比較的優秀であるので迅速に収束する反面、局所解への落ち込みが起こり易いという特徴がある。一方、乱数を用いた方法によって個体を生成した場合、局所解への落ち込みが起こり難い反面、収束までに時間がかかるという特徴がある。そこで、所定の規則に従った方法によって一部の個体を生成し、乱数を用いた方法によって残りの個体を生成することによって初期の集団を生成することによって局所解への落ち込みを抑制しつつ収束を早めることができる。所定の規則に従った方法によって生成する個体の割合は、例えば１０〜９０％である。この割合は、具体的には１０，２０，３０，４０，５０，６０，７０，８０，９０％である。この割合は、ここで例示した数値の何れか２つの間の範囲内であってもよい。材料種と製品の組み合わせによって所定の規則に従った方法のみ又は乱数を用いた方法のみによって個体を生成した方がいい結果が得られる可能性はあるが、両者を組み合わせた方がいい結果が得られる可能性が高いと考えられる。
【００４２】
以下、初期の集団の生成方法の一例を示す。
この例では、１個体にはＲＦＦＤを適用し、残りの個体には必要回数製品をランダムに並び替えてＲＦＦを適用し生成する。但し、初期個体の多様性を確保するために、すべてをＲＦＦＤおよびＲＦＦで生成するのではなく、あらかじめ決められたＲＦＦ生成比率αに相当する個体数とし、残りは乱数によって生成する。具体的な遺伝子の初期設定方法は以下のように行う。
【００４３】
【数６】
2010009585.tif 000010
【００４４】
ここでβは（９）式で得られる遺伝子Ｐの値の範囲から突出しないためのパラメータで、先行実験によって残材率の分布をみておよそ下限値になるようを設定する。
【００４５】
３−２．製品割り付け部（製品割り付けステップ）
次に、製品割り付け部が、各個体の染色体Ｂ及び染色体Ｐに基づいて製品を材料に割り付ける。
製品割り付けの方法は、特に限定されないが、一例では、以下の製品割り付けルールに従って行うことができる。なお、「鼻切」と「鋸代」は材料長や製品長の調整で組み込むことができるので、ここでは単純化のため無視する。
【００４６】
【数７】
2010009585.tif 000011
【００４７】
３−３．算出部（算出ステップ）
次に、算出部が、前記製品割り付け部による割り付けの結果に基づいて各個体の優劣を示す個体適応率と、各個体における各製品の割り付けの優劣を示す遺伝子適応率を算出する。また、遺伝子Ｐが材料歩留に基づいて算出される場合、算出部は、製品割り付け部による割り付けの結果に基づいて遺伝子Ｐの更新を行うことが好ましい。
【００４８】
（１）個体適応率
個体適応率は、各個体の優劣を示す指標となるものであればその表現方法は特に限定されない。一例では、個体適応率は、（５）式で示される個体歩留が１に近づくにつれて値の上昇度が大きくなる関数に基づいて算出される。このように設定することによって、個体歩留が大きい個体が個体選択部によって選択される可能性が高まり収束性が向上する。
個体適応率ａは、一例では、（５）式の個体歩留ｙ（０≦ｙ≦１）を関数Ｆでスケーリングしたものであり、（１６）式のように表現することができる。
【００４９】
【数８】
2010009585.tif 000012
【００５０】
この適応率は「選択」フェーズでの個体の選択基準となるため、個体の生存分布はこの関数に依存し、その結果収束性に影響を与える。最適値への収束性のためには個体の多様性と優秀性のバランスが重要である。そのため個体適応率は個体歩留ｙが平均歩留より小さい範囲では小さく、平均値から最大値にかけて大きく変化する関数によってスケーリングするのが合理的である。このような関数の一例は、Ｆ（ｙ）＝ｙ10である。
【００５１】
（２）遺伝子適応率
遺伝子適応率は、各個体における各製品の割り付けの優劣を示す指標となるものであればその表現方法は特に限定されない。一例では、遺伝子適応率GFR(Gene Fitness Ratio)
は、（１１）式のように、材料歩留まりを用いて表現することができる。（１１）式によれば、材料歩留まりが高い材料に割り付けられている製品に対応する遺伝子の遺伝子適応率が高くなり、このような遺伝子が交叉操作で生成される次世代の個体に引き継がれやすい。
【００５２】
【数９】
2010009585.tif 000013
【００５３】
３−４．個体選択部（個体選択ステップ）
次に、個体選択部が、前記個体適応率に基づいて個体の選択を行う。選択の方法は、個体適応率が利用されるものであれば特に限定されない。
【００５４】
選択の方法としては、例えば、個体適応率が高い所定数の個体を選択するエリート選択による方法や、個体適応率に比例するように所定数の個体を選択するルーレット選択による方法や、これらを組み合わせた方法が挙げられる。エリート選択のみだと多様性が失われて局所解に落ち込みやすくなり、ルーレット選択のみだと収束性が良くないので、エリート選択とルーレット選択を組み合わせることが好ましい。
【００５５】
個体選択部が選択する個体の割合は、特に限定されないが、例えば、１０〜９０％である。この割合は、具体的には例えば１０，２０，３０，４０，５０，６０，７０，８０，９０％である。この割合は、ここで例示した数値の何れか２つの間の範囲内であってもよい。また、エリート選択とルーレット選択を組み合わせる場合、選択する個体のうち例えば３〜３０％をエリート選択によって選択する。この割合は、具体的には例えば３，５，１０，１５，２０，２５，３０％である。この割合は、ここで例示した数値の何れか２つの間の範囲内であってもよい。
【００５６】
３−５．交叉部（交叉ステップ）
次に、交叉部が、前記個体選択部によって選択された個体の中から一対の個体を親個体として選択してこれら親個体の対を交叉させることによって新たな個体を生成する操作を規定の個体数になるまで繰り返して新世代の集団を生成する。また、交叉部は、前記親個体の対のそれぞれの遺伝子適応率を比較し遺伝子適応率が高い親個体の遺伝子Ｂと遺伝子Ｐを選択するという操作を製品毎に行うことによって生成された染色体Ｂ及び染色体Ｐを有する個体を生成する。
つまり、この交叉方法では、次のような交叉操作であらたな子を生成する。
【００５７】
【数１０】
2010009585.tif 000014
ここで、個体Ａのｉ番目の遺伝子座の遺伝子Ｂをｔi（Ａ），遺伝子Ｐをｓi（Ａ），遺伝子適応率ＧＦＲをｇi（Ａ）と表現した。図３に例を示す。図３ではわかりやすくするため遺伝子ではなく割り付けられた材料とＧＦＲのみ記した。この例ではＢ，Ｅ，Ｈの材長種と製品グループ（シャドウ部分）が子に引き継がれる。
このような交叉方法を以下、対戦交叉法（Tournament Crossover Operation Method: TCOM）」と呼ぶ。
【００５８】
非特許文献１に記載のＥＥＭでは、ＴＣＯＭモデルと同じ遺伝子構造を持ち、遺伝子毎にその製品が割り付けられた材料の残材率（＝１−材料歩留）の関数である交叉制御パラメータ（Crossover Control Parameter :CCP）を定義し、ＣＣＰを遺伝子が引き継がれる確率として、次のルールで親１と親２から子１と子２を生成した（子２は親１と親２の関係を入れ替える）。
【００５９】
【数１１】
2010009585.tif 000015
【００６０】
ＥＥＭも遺伝子単位に残材率の低い“良い遺伝子”が引き継がれる傾向が得られるようにＣＣＰ関数を定義することで、総体としての個体の収束性を確保しているが、この方式では子は“良い遺伝子”を片親からのみ引き継ぐことになる。一方、ＴＣＯＭモデルでは、それぞれの親から歩留の高い“良い遺伝子”を引き継ぐことができるため、さらに良い収束性が期待できる。
【００６１】
３−７．多様化処理部（多様化処理ステップ）
次に、多様化処理部が、選択された個体に対して突然変異を生じさせるか又はこの個体を新たに生成した個体と入れ替える多様化処理を行う。この処理によって局所解への落ち込みを抑制することができる。
【００６２】
多様化処理は、一例では、交叉処理の後に行われるが、多様化処理を行うタイミングは、特に限定されず、交叉処理の前や個体選択の前に行ってもよい。
多様化処理を行う個体の選択は、ランダムな方法によって行ってもよいが、例えば個体適応率が低い個体を優先的に選択する等、完全にランダムな方法以外の方法で行ってもよい。
【００６３】
多様化処理の対象となる個体の割合は、特に限定されないが、例えば５〜４０％程度である。この割合は、具体的には例えば５，１０，２０，３０，４０％である。この割合は、ここで例示した数値の何れか２つの間の範囲内であってもよい。
【００６４】
突然変異では、選択された個体中の選択された遺伝子を変異させる。遺伝子の選択は、ランダムな方法によって行ってもよいが、例えば遺伝子適応率が低い遺伝子を優先的に選択する等、完全にランダムな方法以外の方法で選択を行ってもよい。遺伝子を変異させる方法は特に限定されないが、一例では、（１５）式の遺伝子Ｂおよび遺伝子Ｐ設定ルールに従って遺伝子を再設定することによって変異させることができる。変異させる遺伝子座の割合は、特に限定されないが、例えば３〜３０％である。この割合は、具体的には例えば３，５，１０，２０，３０％である。この割合は、ここで例示した数値の何れか２つの間の範囲内であってもよい。突然変異は、遺伝子Ｂと遺伝子Ｐの何れか一方のみ起こるようにしてもよく、両方に起こるようにしてもよい。遺伝子Ｂが突然変異した場合、変異後の内容に基づいて遺伝子Ｐを更新することが合理的であり好ましい。一方、遺伝子Ｐの場合は単独で変化させることが好ましい。
【００６５】
個体の入れ替えは、選択された個体を削除し、同じ数の個体を「３−１．初期集団生成」の項で説明した方法で生成するによって行うことができる。この場合、所定の規則に従った方法によって生成する個体の割合は、初期集団生成の場合と同じであっても異なっていてもよい。
【００６６】
３−８．終了判断部（終了判断ステップ）
次に、終了判断部が、終了基準が満たされるまで前記製品割り付け部、前記算出部,前記個体選択部、前記交叉部及び前記多様化処理部による処理を繰り返し、前記終了基準が満たされた場合に繰り返しを終了する。
終了基準は、特に限定されないが、例えば、（１）集団に属する個体のうち個体適応率が最大のものの個体適応率が目標値を超える、（２）集団の世代数が基準値を超える等が挙げられる。（２）のみを終了基準としてもよいが、目標の個体適応率を超えた後に処理を続けるのは効率的でない場合があるので（１）と（２）の基準を併用して（１）又は（２）の条件が満たされたときに終了基準が満たされたと判断することが好ましい。
【００６７】
終了後は、集団に属する個体のうち個体適応率が最大のもの染色体Ｂと染色体Ｐを用いて上述した製品割り付けルールに従って製品を材料に割り付けることによって高い歩留まりで製品割り付けを行うことができる。
【００６８】
以上の実施形態で示した種々の特徴は，互いに組み合わせることができる。１つの実施形態中に複数の特徴が含まれている場合，そのうちの１又は複数個の特徴を適宜抜き出して，単独で又は組み合わせて，本発明に採用することができる。
【００６９】
４．製品割り付けの具体例
以下、上記実施形態の製品割り付け装置を用いた製品割り付けの具体例について説明する。以下の説明では、本発明の製品割り付け装置で採用したモデルを「ＴＣＯＭモデル」と称する。
【００７０】
４−１．ＢＰＰベンチマーク問題による比較評価
本ＴＣＯＭモデルは材料の種類ｍ＝１とすればＢＰＰに適用できる。ＢＰＰについてはベンチマークのための問題がインターネット上に公開されている（http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm）。そこで我々もＴＣＯＭモデルをｍ＝１としてこのベンチマーク問題に適用し、本ＴＣＯＭモデルとＥＥＭモデルおよび一様交叉モデルとの比較を行うこととする。表3に我々の実行環境を示した。プログラム言語はMicrosoft Excelとインタープリター言語であるＶＢＡ（Visual Basic for Application）を使っており、Ｃ言語やＰａｓｃａｌなどのコンパイル言語に比べて処理効率は低い。
【００７１】
【表３】
2010009585.tif 000016
【００７２】
４−１−１．ベンチマーク問題
ベンチマーク問題はＢ１，Ｂ２，Ｂ３の３種類あり、Ｂ１はビン容量に対してアイテム容積をまんべんなく設定した７８０例の問題群であり、Ｂ２はビンに入るアイテムの数がおよそ３，５，７，９となるように設定されている４８０例の問題群である。Ｂ３はビン容量が１０００００に対してアイテムサイズは（２００００，３５０００）の範囲で一様分布し、ビンには３から５つのアイテムが入るように設定される「Very Hard」とされる１０例の問題である。我々のモデルは本来はＣＳＰへの適用を目的としており、後出のセクション４−２ではプレカットのＣＳＰに適用している。そこでこれらの問題群のうち比較的プレカットの条件に近いＢ３のデータを取り上げて比較することとする。なお、ベンチマークの各問題には、現在知られている最小使用ビン数が示されている。我々のモデルは目的関数を個体歩留としているが、材料の種類ｍ＝１の場合は個体歩留と使用材料数は目的関数として同値である。
【００７３】
４−１−２．パラメータ、関数形の設定
個体数と世代数はそれぞれ１００個体、１０００世代とし、１０回繰返し試行し最も良い結果を採用する。計算時間は最小解（最小解が得られない場合は準最小解）が得られた時点までとする。適応率関数と各種のパラメータは、予備実験の結果を踏まえ（１７）式のように設定した。なお、鼻切および鋸代は考えない。
【００７４】
【数１２】
2010009585.tif 000017
【００７５】
ＥＥＭモデルの収束に大きな影響を与えることがわかっている交叉制御パラメータＣＣＰの関数形は、プレカットのＣＳＰに適用した際に最も良い結果を出した下記の関数形を採用する。
【００７６】
【数１３】
2010009585.tif 000018
【００７７】
さらにＲＦＦによる初期個体生成が結果に及ぼす影響を評価するため、ＲＦＦによる初期個体の生成率αをそれぞれ１（Ａｌｌ  ＲＦＦ），０．５（５０％ＲＦＦ），０（Ａｌｌ  ＲＮ：乱数）とした場合を比較評価する。なお、一様交叉とＥＥＭではα＝０．５とした。また前節の比較でのＴＣＯＭはα＝０．５を採用している。
【００７８】
４−１−３．収束性の評価
この結果を表４に示す。一様交叉ではまったく最小解を得られなかった。絶対偏差も平均３となっており、Ｆａｌｋｅｎａｕｅｒが指摘したように製品の並びを遺伝子表現するモデルでは、従来型の交叉方法では収束性が極めて悪いことがわかる。またＥＥＭでは得られた最小解は１つであった。このモデルは優秀な遺伝子を片方の親からしか引き継げないため、両方から引き継ぐ本ＴＣＯＭモデルに比べて収束性が悪いものと推定される。
【００７９】
一方、初期個体の生成については、α＝０．５が最も良い結果となった。ＲＦＦによって生成された個体はある程度の高い適応度（個体歩留）を持つことがわかっているが、すべてをＲＦＦで生成するとかえって結果が悪くなるのは、初期個体群が多様性を欠いた結果、局所解に陥ったと推定できる。また、すべてを乱数で発生させた場合はα＝０．５の場合と同じ数の最小解を得たが、初期個体の歩留水準が低いため最小解までに多くの世代経過を必要し時間が長くかかっている。
【００８０】
【表４】
2010009585.tif 000019
【００８１】
４−２．住宅プレカット材料取り合わせ問題への適用
本ＴＣＯＭモデルはＣＳＰを対象とするＧＡモデルである。そこで典型的なＣＳＰである住宅のプレカット材のＣＳＰに適用する。
【００８２】
４−２−１．住宅プレカットデータ
住宅プレカットＣＳＰとは、いくつかの種類の長さを持つ木材母材から、住宅建築で要求される長さの部材（製品）を切り出す問題である。ここでは標準的な２つの一戸建て住宅の横架材を対象にした（表５，表６）。これらの横架材は、断面形状（Ｓｈａｐｅ）や樹種（Ｓｐｅｃ．）、等級（Ｇｒａｄｅ）など同じ母材から切り出すことができる１６および１８のロットにグループに分けることができ、それぞれのロット毎に切り出す製品数（Ｎｕｍ．）や使用する母材群（Kinds of Material）も異なる。ロット毎の歩留は（５）式の長さ歩留で計算できるが、邸全体の歩留はロット毎に断面形状が異なるため体積による材積歩留で比較する。すなわち、邸の材積歩留＝全製品体積／全使用材料体積とする。
【００８３】
【表５】
2010009585.tif 000020
【００８４】
【表６】
2010009585.tif 000021
【００８５】
４−２−２．比較する手法
提案のＴＣＯＭモデルを評価するに当たって、プレカット材料への適用事例の文献がないため、我々が既にプレカットＣＳＰに適用して報告しているＥＥＭモデルおよび特許されているプレカットＣＳＰのヒューリスリックアルゴリズム（特許文献１）との比較を行うことにする。
【００８６】
今回比較対象とした特許文献１のアルゴリズムは、すべての製品の長さ合計に対してその合計長以上になる複数母材長の母材の組み合わせをリストアップし、リストアップした母材の組み合わせで母材長合計の昇順にすべての製品が割り付けられるかを判断するステップと、割り付け可能な最小母材長合計の組み合わせに対して、さらに母材長合計が小さくなる母材の組み合わせを探査するステップからなる方法であり、既に実際に使われているものである。
【００８７】
４−２−３．実行結果の比較
ＴＣＯＭモデルはＢＰＰへの適用時と同じく個体数を１００として１０００世代までの実行を１０回繰返した最良値を採用し、処理時間は最良値が得られる時間までとする。そのほかのパラメータも同じ（１７）式、（１８）式とした。実行結果を表７に示す。ＥＥＭと特許文献１の結果は前回の報告値とした。なお、鼻切は０ｍｍ、鋸代は５ｍｍとした。この結果、２つのＧＡモデルはまったく同等の結果となり、特許アルゴリズムより優位な結果が得られた。邸１のＥＥＭの数字は最適値であることがわかっており、邸２についても最適解かあるいはそれに近い値と推定できる。したがってＴＣＯＭとＥＥＭの優劣はつかなかったものと考えられる。
【００８８】
【表７】
2010009585.tif 000022
【００８９】
４−２−４．実用に向けての検討
ＧＡを実用手法として使う場合、実行結果が確率的に変化するため、実行結果の評価と処理時間をどのようにバランスされるかが課題となる。ＢＰＰベンチマークデータのように最適値がわかっている場合は、あらかじめ設定した世代数が経過するか最適値が達成したら終了すればよいが、一般には最適値はわからない。そこで最適解であることがわかっている邸１について最適値が得られるまでの世代推移を分析し、１０回の繰返しで最適値が少なくとも１回出現するような世代数を設定することで処理時間の短縮を図る。ＲＦＦで初期個体を生成すると、確率的に最初から最適解となる場合があるので、（１７）式でＲＦＦ生成比率α＝０として、最大歩留（最適値）が得られるまでの状況の詳細を表８に示した。この表で「Num. of Prd.」は製品数、「Num. of Mtr.」は材長種の数、「Max. Rate」は最大歩留、「Max. Num.」は１０回の実行で最大歩留が得られた回数、「Generation」の欄は最大歩留までの経過世代数の最大値、最小値、平均値および標準偏差、「Ｔｉｍｅ」は１０００世代までの実行時間（秒）である。１０００世代まで実行すると、この邸の取り合わせ計算には１６２秒×１０回＝約２７分かかることになる。
【００９０】
【表８】
2010009585.tif 000023
【００９１】
この結果、Ｎｏ．１とＮｏ．７のロットを除いて１０回の実行のすべてが最適値となっており、最も少ないロットＮｏ．１でも最適値が５回出現している。最適値に至るまでの世代数は製品数と材長種数の組み合わせに対して正の相関を持ち、製品数×材長種数が１００を超えると世代数に大きな影響を与えているように見える。そこで仮に以下のように実行世代数を定め、ＲＦＦ生成比率α＝０．５に戻して実行し時間短縮を図る。
【００９２】
【数１４】
2010009585.tif 000024
【００９３】
表９に（１９）式の設定で実行した結果を示した。ここで「Max Gen.」が実行世代数である。全体の処理時間は３分（１８秒×１０回）となったが、すべてのロットで最大歩留を得た。同じ（１９）式のルールで実行した邸２の結果も表９に併記しているが、１０００世代の場合と同じ結果を４分以内（２２秒×１０回）で出すことができた。
【００９４】
【表９】
2010009585.tif 000025
【００９５】
以上の結果から、本ＴＣＯＭモデルを一般の木造住宅プレカットＣＳＰに実際に適用する場合、たとえば実行世代数として（１９）式のルールを適用すれば、数分程度の処理時間で極めて高い歩留を得られることがわかる。
【００９６】
４−３．まとめ
複数材長の一次元ＣＳＰを対象にＧＡモデルを検討した。敢えて従来から非効率性を指摘されていたアイテム単位の遺伝子構造を持つモデルとして、遺伝子毎の適応率（ＧＦＲ）を導入してその比較によって交叉を制御することで、安定的に高い歩留を得る対戦交叉操作モデル（ＴＣＯＭ）を提案した。これをＢＰＰのベンチマークデータに適用し、ＴＣＯＭの有効性と拡張エリート選択（ＥＥＭ）モデルと比べた優位性を確認するとともに、プレカットＣＳＰデータにも適用し、一般のプレカット工場では通常９０％以下といわれている歩留を、数分の処理時間で９５％前後まで向上させることができた。
【図１】
2010009585.tif 000026
【図２】
2010009585.tif 000027
【図３】
2010009585.tif 000028
【図４】
2010009585.tif 000029
【図５】
2010009585.tif 000030