(57)【要約】【課題】長さ又は容積が互いに異なる複数種類の母体（材料，容器）に対して複数種類の製品の割り付けを効率的に行うことができる製品割り付け装置を提供する。【解決手段】親の個体の染色体データを、製品を割り付ける母体と割り付け順を示す遺伝子を配列したものに定義して、世代交代により歩留まりの良い割り付けに進化させる。世代交代のための交叉制御では、一対の親個体の同一の製品の遺伝子適応率を比較して、遺伝子適応率の良いほうの遺伝子を子に引き継がせることを基本ルールとする。その一方で、一対の親の個体歩留を比較して、個体歩留が高い方の親の遺伝子については、前記基本ルールに従わずに、引き継がれる確率を高める。これにより、局所解に陥るのを防止できる。【選択図】図４
2010152584.tif 000002
【特許請求の範囲】
【請求項１】
長さ又は容積が互いに異なる複数種類の母体の中から任意の母体を任意の数だけ取り出して、これらの母体に、複数種類の所定数の全ての製品を割り付けて、割り付けの歩留まりを計算する製品割り付け装置であって、
各製品を割り付ける母体の種類を指定する遺伝子Ｂとその母体に製品を割り付ける順序を指定する遺伝子Ｐとを前記全ての製品について表示する構造の染色体を、一個体毎に持たせて、該当する構造の染色体データを持つ個体データを所定数集合させた初期個体集団を生成して記憶装置に記憶させる初期設定手段と、
前記記憶装置に記憶された各個体データの前記染色体データを読み出して、所定の取り合わせ計算ルールに従って、前記個体データ毎に、前記遺伝子Ｐで指定された母体に前記遺伝子Ｂで指定された割り付け順で前記全ての製品を割り付ける、割り付け処理を実行する製品割り付け手段と、
前記個体データ毎の使用された母体全体の割り付け歩留まりを個体歩留とし、母体毎の割り付け歩留まりを材料歩留まりと呼ぶとき、前記割り付け処理の結果を取得して、前記個体データ毎に、割り付け結果データと、前記個体歩留の関数から導かれた個体適応率データと、前記材料歩留の関数から導かれた遺伝子適応率データとを取得して、前記記憶装置に記憶させる適応率計算手段と、
前記記憶装置に記憶された前記各個体データの個体適応率データを比較して、適応率の良い複数の個体を選択して新たな個体集団を前記記憶装置に記憶させる個体選択手段と、
前記新たな個体集団に含まれたいずれかの個体データを一対読み出して、当該一対の染色体データに含まれる同一の製品の遺伝子を比較し、いずれか一方の遺伝子を該当する製品の遺伝子として子に引き継ぐという処理を全ての製品について実行して、子の個体データを生成する処理を、所定数の個体が生成されるまで繰り返す交叉制御手段と、
前記所定数の子の個体データに対して、任意の方法で生成した新たな個体データを追加して、新たな親となる個体集団を生成して記憶装置に記憶させる多様化処理手段と、
前記交叉制御手段による世代交代処理回数が予め設定した上限値に達するまで、あるいは、前記製品割り付け手段による各個体データの割り付け処理の結果が予め設定した目標値に達するまで、前記製品割り付け手段による割り付け処理と、前記適応率計算手段による適応率の取得処理と、前記個体選択手段による新たな個体集団の選択処理と、前記交叉制御手段による子の個体データ生成処理と、前記多様化処理手段による新たな個体集団の生成処理とを繰り返し実行するように制御する繰り返し制御手段とを備え、
前記交叉制御手段は、前記一対の親の、同一の製品の遺伝子適応率を比較して、遺伝子適応率の良いほうの遺伝子を子の当該製品の遺伝子とすることを基本ルールとする一方、一対の親の個体歩留を比較して、個体歩留が高い方の親の遺伝子については、前記基本ルールに従わずに、子の遺伝子として引き継がれる確率を高める基準を設けたことを特徴とする製品割り付け装置。
【請求項２】
請求項１に記載の製品割り付け装置において、
前記取り合わせ計算ルールは、製品と遺伝子Ｂと遺伝子Ｐとを一組のデータとし、遺伝子Ｂを第１キーとし遺伝子Ｐを第２キーとして、製品を昇順にソートし、ソートした順に前記製品を取り出して、取り出した製品を遺伝子Ｂで表示された母体に割り付け、次に取り出した製品の遺伝子Ｂが別の母体を表示しているときは、その別の母体に当該製品を割り付け、次に取り出した製品の遺伝子Ｂが同じ母体を表示しているときは、現在割り付け中の母体に当該製品の割り付けが可能かどうかを判断し、割り付け可能であれば現在割り付け中の母体に当該製品を割り付け、割り付け不可能であれば、新たな同じ母体に当該製品を割り付けるというものであることを特徴とする製品割り付け装置。
【請求項３】
請求項２に記載の製品割り付け装置において、
前記母体に製品を割り付ける順序を指定する遺伝子Ｐは前記材料歩留まりの関数であって、同じ母体に割り付けられた製品の遺伝子Ｐはいずれも同じ値になるように設定されることを特徴とする製品割り付け装置。
【請求項４】
請求項１乃至３のいずれかに記載の製品割り付け装置において、
前記個体適応率を、前記個体歩留まりが、前記個体集団に含まれた個体の個体歩留まりの平均値より小さい範囲で小さく、かつ、当該平均値から最大値の範囲で大きく変化する関数を演算して求めたものにすることを特徴とする製品割り付け装置。
【請求項５】
請求項１乃至４のいずれかに記載の製品割り付け装置において、
親個体の温度を、個体歩留が大きいほど低い値を示す関数で表し、各個体の各製品の遺伝子が子個体に引き継がれる確率を、一対の親個体のうちの一方の温度が他方の温度よりも低くて、一方の遺伝子適応率が他方の遺伝子適応率よりも大きいときは、一方の遺伝子が子の個体に引き継がれ、一対の親個体のうちの一方の温度が他方の温度よりも高くて、一方の遺伝子適応率が他方の遺伝子適応率よりも小さいときは、他方の遺伝子が子の個体に引き継がれ、それ以外の場合には、温度差と遺伝子適応率の関数によりいずれかの遺伝子が引き継がれる確率が決められることを特徴とする製品割り付け装置。
【請求項６】
製品割り付け装置のコンピュータを、請求項１に記載の各手段として機能させる製品割り付けプログラム。
【請求項７】
製品割り付け装置のコンピュータを、請求項１に記載の各手段として機能させる製品割り付けプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項８】
請求項１に記載の製品割り付け装置を使用して、前記各手段が該当する処理を実行するステップを含む製品割り付け方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、長さ又は容積が互いに異なる複数種類の母体に対して複数種類の製品の割り付けを行う場合に、最適な割り付けを達成するための製品割り付け装置と製品割り付けプログラムと記録媒体と製品割り付け方法に関する。
【背景技術】
【０００２】
住宅構造材のプレカット等では、長さが互いに異なる複数種類の材料から複数種類の製品を切り出す。それぞれの材料の使用本数には制限が設けられない。同じ長さの材料を複数本使用することもできる。ひとつの材料に可能な限りの製品を割り付ける。このとき、割り付け結果の歩留まりの最適化を図るために、例えば一次元ビンパッキング問題の手法が採用される。例えばＦｉｓｒｔ  Ｆｉｔ  Ｄｅｃｒｅａｓｉｎｇ法では、始めに一番長い製品に対して、一番長い材料から順に、割り付けられるだけの製品を割り付ける。一杯になったら次の材料に次の製品を割り付ける。材料長を変更したり割り付け順を変更したりして、複数の割り付け結果の歩留まりを比較評価する。そのような試行の末に、最適な割り付け結果が得られる。（非特許文献2参照）
【０００３】
この他に、こうした材料取り合わせ問題を処理するために、遺伝子工学を利用する方法がある。遺伝子工学を利用するときは、始めに各種の割り付け結果を示す染色体をもつ多数の個体を用意して、世代交代により製品の割り付け結果を進化させる。歩留まりの良い割り付け結果を示す染色体を持つ個体を選んで、良い遺伝子が子に引き継がれるようにして世代交代を繰り返させる。これにより、最適な割り付け結果を示す染色体を持つ個体が得られる。
【０００４】
本発明者らは、以前に、拡張エリート選択法（Extended Elitism Method:EEM）を提案した。この方法では、製品の割り付け順を遺伝子情報に含めた、一種のOrdered-basedモデルを採用した。このモデルで遺伝子レベルの交叉制御を行うことにより、一般の建材のプレカット工場では９０％以下と言われている歩留まりを、９５％前後にまで向上させることができた（非特許文献１を参照。）
【特許文献１】特許第３５６５２６２号
【非特許文献１】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 bin-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 W?scher 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)の乱数
【００３０】
このように、残材率の低い「良い遺伝子」が引き継がれるようにＣＣＰ関数を定義すれば、世代交代の結果、より優れた染色体を持つ個体が生まれ、収束性を確保できる。しかしながら、このＥＥＭでは、子は“良い遺伝子”を片親からのみ引き継ぐことになる。これに対して、本発明では、それぞれの親から歩留の高い「良い遺伝子」を引き継ぐことができるため、さらに良い収束性が期待できる。しかも、交叉ルールに焼きなまし法による確率関数を使って、局所解に陥る危険を回避した。従って、本発明の製品割り付け装置によれば、遺伝子工学的手法により、長さ又は容積が互いに異なる複数種類の母体（材料，容器）に対して複数種類の製品の割り付けを効率的に行うための割り付け結果を取得できる。
【実施例２】
【００３１】
（使用される記号の説明）
次に、上記の処理をより具体的な実施例で説明する。以下の説明では、表１に示す記号を用いる。なお、材料の長さ種別を「材長種」と表現した。
【００３２】
【表１】
2010152584.tif 000003
【００３３】
（歩留まりの目標値）
この実施例では、プレカット製品を材料から切り出すときの最適な割り付け方法の算出を紹介する。最適な割り付けかどうかは、下記のように、材料の歩留まりが最大かどうかで判断する。
今、ｍ種類の長さｂｔ（ｔ＝１，・・・，ｍ）の材料が十分にあり、これから長さｌｉ（ｉ＝１，・・・，ｎ）の製品全てを切り出すとき、材長種ｔの材料の使用コストをｃｔとすると、ＣＳＰ（Cutting Stock Problemｓ）は、下の（１）式で表せる。
【数１】
2010152584.tif 000004
ただし、（２）式は、材料に割り付けられた製品の長さの合計が、材料の長さ以下であることを示す。（３）式はすべての製品はどれかの材料に割り付けられることを示す。（４）式は１つの製品が同時に複数の材料に割り付けられないことを示す。
【００３４】
ＣＳＰでは歩留最大を狙うのが一般的である。歩留ｙは次の（５）式で表される。
【数２】
2010152584.tif 000005
ここで分子の製品長累計は所与であるので、(1)式で使用コストｃｔを材長ｂｔに置き換えて（６）式のようにすればよい。
【数３】
2010152584.tif 000006
なお、実際のＣＳＰでは材料の両端を整える「鼻切」および製品を切り出す際の「鋸代」を考慮する必要があるが、本質的な問題ではない。
以上の内容において、ｍ＝１とすれば通常の一次元ビンパッキング問題（Bin Packing Problem: BPP）となることは言うまでも無い。
既存の計算方法を使用して、予め最良と思われる個体歩留を計算しておき、図１に示す最良個体歩留４０を記憶しておくとよい。他の計算方法よりも良い歩留まりが得られたらそれを採用するというように、本発明の装置を利用するとよい。
【００３５】
（初期個体集団と世代交代）
本発明では、収束性のよい染色体を持つ個体構造を定義する。各個体の染色体は、それぞれいずれかの材料に全ての製品を割り付けた、割り付け結果を示す情報を持つ。初期個体集団には、割り付け結果が良いものも悪いものも混在させる。こうした所定数の個体を生成して、目的を達成するまで、良い遺伝子を引き継ぐように世代交代をさせる。この世代交代のつど、後で説明する（取り合わせ計算ルール）を適用して各個体の歩留まりを評価する。
【００３６】
（個体構造の定義）
使用される個体の染色体は、表２のように遺伝子Ｂと遺伝子Ｐとを有する。遺伝子座は、割り付けられる製品の数だけあり、割り付けられる製品と１対１で対応している。遺伝子Ｂ（表２中で「GeneB」と表示している）は、製品を割り付ける材長種を指定する。遺伝子Ｐ（表２中で「GeneP」と表示している）は、同じ材長種に割り付けられる製品群の中での割り付け順を指定する。
【００３７】
【表２】
2010152584.tif 000007
【００３８】
（取り合わせ計算ルール）
上記のように個体構造を定義することにより、個体の世代交代による進化を制御できる。取り合わせ計算ルールは、個体の歩留まりの評価と、世代交代を制御するパラメータのせ計算に使用される。各個体は、各遺伝子座に遺伝子Ｂと遺伝子Ｐを持つ２重遺伝子構造の染色体を有する。この染色体について、取り合わせ計算を以下のようなルールで行う。なお、「鼻切」と「鋸代」は材料長や製品長の調整で組み込むことができるので、ここでは単純化のため無視した。
始めに、製品を，GeneBを第1キー，GenePを第2キーとして昇順にソートし，ソートした順に製品を取り出して、以下のステップ（Step1と Step2）をすべての製品が割付けられるまで繰り返す。
Step1. GeneBが変化したら，新しい材長種の新たな材料に割付ける
Step2. GeneBが変化しないときは，現在割付け中の材料にその製品が割付け可能であれば割付け，不可能であれば同じ材長種の新たな材料に割付ける。
【００３９】
（収束性確保のための遺伝子構造）
上記の取り合わせルールでは、割付け順がGenePの相対的な大小関係で決まる。その結果、GenePの微小な変化で材料−製品グループが過敏に変化してしまうため、通常の一様交叉のような方法では安定的な最適解への進化が期待できない。そこでこれを回避するために、「高い材料歩留をもつ材料−製品グループが次世代に引き継がれる傾向」を持たせる。具体的には次の2つの制御を行う。この制御が可能な遺伝子構造の設計が必要である。
制御1： 材料歩留の高い材料−製品グループに属する製品は優先的に割付け順を早くして、先行する材料の取り合わせでグループが破壊されないようにする。
制御2： 材料歩留の高い材料−製品グループに属する製品の遺伝子が、交叉操作で次世代にできるだけ引き継がれるようにする。
【００４０】
（制御１）
制御１のために、「個体歩留」と「材料歩留」をパラメータにする。さらに遺伝子Ｐを下記のように定義する。製品ｉをｉ番目の遺伝子座に対応させ、割り付ける材長種をｔi、割り付け順をｓiとし、製品ｉの長さをｌiとする。材長種ｔの材料の集合をＢｔ、長さをｂｔ、Ｂｔに属する材料をｋ（ｔ）（＝１，２，・・・）として、この材料に割り付けられた製品の集合をＩｋ（ｔ）とする。このとき材料ｋ（ｔ）の歩留ｙｋ（ｔ）は次の（７）式で定義される。この歩留は、（５）式の個体全体の歩留に対して材料単位の歩留である。（５）式が「個体歩留」、（７）式が「材料歩留」である。
【００４１】
【数４】
2010152584.tif 000008
【００４２】
（制御２）
この材料歩留を用いて製品ｉの遺伝子座の遺伝子Ｂと遺伝子Ｐを、下記のように表現する。
【数５】
2010152584.tif 000009
【００４３】
ここで、遺伝子Ｂは１からｍまでのいずれかの材料を指定する値を表示する。遺伝子Ｐは、０と１の間の数値で、ソートキーになる。εは、同一の材料に割り付けられた製品グループの遺伝子Ｐが確実に同じ値となるために調整をする定数で、材料歩留に対して十分に小さな値とする。（９）式のように遺伝子Ｐを定義すると、より高い材料歩留の材料に割り付けられた製品の遺伝子Ｐは小さな値になり、ソートしたとき先頭側に並び、取り合わせ計算の順番が早くなる。従って優先的に割り付けが行われる。このため、材料歩留の高い材料−製品グループが材料歩留の低い製品によって破壊されることが抑制され、収束性が向上する。なお、遺伝子Ｐの初期値は、乱数を用いて決定することができる。
【００４４】
初期個体を生成する方法は、特に限定されず、所定の規則に従った方法によって生成してもよい。乱数を用いた方法によって個体を生成してもよい。所定の規則に従った方法とは、予め定めてあるルールに従って製品を材料に割り当て、その結果に基づいて遺伝子Ｂ及び遺伝子Ｐを設定する方法である。この方法の例としては、本発明者らによる非特許文献２に記載されたRevised First Fit Descending (RFFD)法や特に製品の並びに条件をつけないで同じアルゴリズムを適用するRevised First Fit (RFF)法が挙げられるが、これらに限定されない。
【００４５】
一般に所定の規則に従った方法によって初期個体を生成した場合、個体が最初から比較的優秀であるので迅速に収束する反面、局所解への落ち込みが起こり易いという特徴がある。一方、乱数を用いた方法によって初期個体を生成した場合、局所解への落ち込みが起こり難い反面、収束までに時間がかかるという特徴がある。そこで、所定の規則に従った方法によって一部の個体を生成し、乱数を用いた方法によって残りの個体を生成することによって初期の集団を生成する。これによって局所解への落ち込みを抑制しつつ収束を早めることができる。所定の規則に従った方法によって生成する個体の割合は、例えば１０〜９０％である。材料種と製品の組み合わせによって結果が異なる。所定の規則に従った方法のみで個体を生成するといい結果が得られることある。また、乱数を用いた方法のみによって個体を生成といい結果が得られることある。しかし、両者を組み合わせた方がいい結果が得られる可能性が高いと考えられる。
【００４６】
（初期個体集団の生成）
初期設定手段２１は、上記のように定義した個体を複数生成することによって初期個体集団３１を生成する。以下、初期個体集団３１の生成方法の一例を示す。
この例では、１個体にはＲＦＦＤを適用し、残りの個体には必要回数製品をランダムに並び替えてＲＦＦを適用して生成する。但し、初期個体の多様性を確保するために、すべてをＲＦＦＤおよびＲＦＦで生成するのではなく、あらかじめ決められたＲＦＦ生成比率αに相当する個体数とし、残りは乱数によって生成する。具体的には以下のように行う。
【００４７】
【数６】
2010152584.tif 000010
【００４８】
ここでβは（９）式で得られる遺伝子Ｐの値の範囲から突出しないためのパラメータで、先行実験によって残材率の分布をみておよそ下限値になるように値を設定する。
【００４９】
（適応率の算出）
図４を用いて説明したように、初期設定手段２１が初期個体集団３１を生成した後に、製品割り付け手段２２が材料取り合わせ計算を行い、その後、適応率計算手段２３が個体適応率と遺伝子適応率を計算する。また、遺伝子Ｐが材料歩留に基づいて算出される場合、（９）式を使用して遺伝子Ｐの更新を行う。
【００５０】
（１）遺伝子適応率
遺伝子適応率は、各個体における各製品の割り付けの優劣を示す指標となるものである。その表現方法は特に限定されない。一例では、遺伝子適応率GFR(Gene Fitness Ratio)は、下の（１３）式のように、材料歩留まりを用いて表現することができる。（１３）式によれば、材料歩留まりが高い材料に割り付けられている製品に対応する遺伝子の遺伝子適応率が高くなり、このような遺伝子が交叉操作で生成される次世代の個体に引き継がれやすい。
【００５１】
【数７】
2010152584.tif 000011
【００５２】
（２）個体適応率
個体適応率は、各個体の優劣を示す指標となるものであればその表現方法は特に限定されない。一例では、個体適応率は、（５）式で示される個体歩留が１に近づくにつれて値の上昇度が大きくなる関数に基づいて算出される。このように設定することによって、個体歩留が大きい個体が個体選択手段２４によって選択されて親の個体になる可能性が高まり収束性が向上する。
個体適応率ａは、一例では、（５）式の個体歩留ｙ（０≦ｙ≦１）を関数Ｆでスケーリングしたものであり、（１４）式のように表現することができる。
【００５３】
【数８】
2010152584.tif 000012
【００５４】
この個体適応率は親の個体を選択するための選択基準となるため、個体の生存分布はこの関数に依存し、その結果収束性に影響を与える。最適値への収束性のためには個体の多様性と優秀性のバランスが重要である。そのため、全ての個体の個体歩留の平均値を求めておき、個体適応率は、個体歩留ｙが平均値より小さい範囲では小さく、平均値から最大値にかけて大きく変化する関数によってスケーリングするのが合理的である。このような関数の一例は、Ｆ（ｙ）＝ｙ１０である。
【００５５】
（個体選択）
個体選択手段２３は、与えられた個体集団の中から、世代交代をさせる場合の親となる個体を選択する。例えば、個体集団の３分の１を選択して残し、他は破棄する。選択する割合はケースによって様々で、例えば１０〜９０％のうちの任意の割合を採用するとよい。これで、良い遺伝子を持つ親を優先的に残すようにするとともに、次のような調整も行なう。例えば、まず、全ての個体を個体適応率の順番にソートし、個体適応率が高い所定数の個体を選択する。これがエリート選択法である。次に、残りの個体から所定数の個体をルーレット選択法により選択する。各個体の選択確率は個体適応率に比例させるとよい。この他に、個体適応率を利用した各種の選択法を組み合わせても良い。
【００５６】
エリート選択法のみでは多様性が失われて局所解に落ち込みやすい。ルーレット選択法のみでは収束性が良くない。従って、エリート選択法とルーレット選択法等を組み合わせることが好ましい。例えば、選択する個体のうちの５％をエリート選択法で選択する。残りをルーレット選択法やその他の選択法により選択する。ルーレット選択法のほかにエリート選択法やその他の選択法を使用する割合は３％〜３０％程度が適する。ケース毎に適するものを採用するとよい。
【００５７】
（交叉処理）
図５は交叉制御手段の動作説明図である。
交叉制御手段２５は、選択後の親の個体集団３７に含まれる個体データを一対ずつ親個体として取り出し、交叉制御により子の個体データを生成する。これらが次世代の子の個体集団になる。交叉制御では、取り出した一対の親個体の、同じ遺伝子座にある各遺伝子の遺伝子適応率を、個別に比較する。図では、一対の親を親１、親２と表示した。また、交叉制御をかりやすくするため、各遺伝子座には、製品が割り付けられた材長種（Ａ、Ｂ、Ｃ、Ｄ・・）とＧＦＲのみを記した。
【００５８】
原則として、遺伝子適応率を比較し、遺伝子適応率が高いほうの親個体の遺伝子を子に引き継ぐ。引き継がれる遺伝子は、それぞれGeneＢとGeneＰである。
【００５９】
【数９】
2010152584.tif 000013
このような交叉方法を以下、対戦交叉法（Tournament Crossover Operation Method: TCOM）」と呼ぶ。
【００６０】
このTCOMは上記の2つの制御によって、製品の並びを染色体とする遺伝子構造にもかかわらず、材料に割付けられる製品のグループを尊重し、無駄な冗長性によって探査空間を広げることなく、遺伝子毎にGFRを比較して高い適応率の遺伝子を次世代に引き継ぐことで、遺伝子の総体である個体の適応率を高めていくことに特徴がある。
【００６１】
しかし、この方法は(1５)式のルールで引き継ぐ遺伝子が決まるため、例えば極めて高い材料歩留をもつ材料に割付けられた製品の遺伝子は“常に”次世代に引き継がれることになる。ところが、一部の材料歩留が高くても材料歩留の総和としての個体歩留が高いとは限らない。なかにはある材料の歩留を低くすることで、他の材料の歩留が改善され、全体の歩留を高くする場合もありうるが、(1５)式のルールによる交叉方法を固定的に扱うと、たとえば限りなく1に近い材料歩留の遺伝子の組は、必ず次世代に引き継がれ材料歩留が低くなる可能性はほとんど無い。この場合、袋小路に入ってしまい、局所解に陥る危険がある。
【００６２】
特にRFFで生成される個体は、FF法の特徴である良い組み合わせの先取りにより、高い歩留の組み合わせのある一方で、最後に割付けられた材料の歩留が低くなり、全体歩留が高くならない場合がある。実際、後で述べるように前回のTCOMの提案(豊田, 2008)では、BPPのベンチマークによる評価の中で、RFFによる初期個体生成率をα＝１とした場合、α＝０．５とした場合より悪くなることがわかっている。
【００６３】
これを解決するために、本発明では、(1５)式の交叉ルールに確率的な要素を組み込む。そこで焼きなまし法(Simulated Annealing)の考え方を取り入れることにする。焼きなまし法は、内部温度がゆっくり冷えるにつれて原子が初期の高エネルギー状態からエネルギー極小の状態に移る現象に倣って、内部温度を定義し、この温度が高いときは解を大きく変化させることで探査範囲を広げ、温度の低下とともに徐々に探査範囲を収束させていく手法である。この考え方を次のように交叉ルールに取り入れる。
【００６４】
（交叉ルール）
親個体P(P=1,2)の“温度”T(p)を親の個体歩留の関数として以下のように定義する。これにより、個体歩留が高いほど温度が低いという性質を持たせる。
T(p)=(1- y(p))×γ  P=1,2        (1６)
ここでy(p)は親個体Pの個体歩留、γは調整パラメータで本論ではγ＝０．１とした。子のｉ番目の遺伝子が親１から引き継がれる確率をPr(1)として、これを両親のGFRと温度の関数として以下のように定義する。
【数１０】
2010152584.tif 000014
【００６５】
図６は、（１７）式の確率関数をグラフ化した説明図である。
親１から遺伝子が引き継がれる確率はPr(1)である。親２から遺伝子が引き継がれる確率はPr(2)=1 −Pr(1)である。(1７)式の確率関数を使って、(1５)式の交叉ルールを次式のように変更する。図６には、親１の遺伝子を引き継ぐ確率曲線(T =0.01の場合)を示した。
【数１１】
2010152584.tif 000015
【００６６】
このルールは、個体歩留の低い個体は高い内部エネルギーを持つため、この個体のある遺伝子が高い遺伝子適応率を持っていても、相対的に内部エネルギーの低い個体の遺伝子との生存競争に敗れる場合があることを意味している。従って極めて高い材料歩留をもつ材料に割付けられた製品の遺伝子であっても、その個体の歩留が相手の個体歩留より低い場合には、子に引き継がれない可能性がでてくることになる。これにより、局所解に陥る危険を緩和することができると期待される。
【００６７】
即ち、親個体の温度を、個体歩留が大きいほど低い値を示す任意の関数で表す。そして、各個体の各製品の遺伝子が子個体に引き継がれる確率をこの温度に依存させる。一対の親個体のうちの一方の温度が他方の温度よりも低くて、一方の遺伝子適応率が他方の遺伝子適応率よりも大きいときは、一方の遺伝子が子の個体に引き継がれる。一対の親個体のうちの一方の温度が他方の温度よりも高くて、一方の遺伝子適応率が他方の遺伝子適応率よりも小さいときは、他方の遺伝子が子の個体に引き継がれる。それ以外の場合には、温度差と遺伝子適応率の関数によりいずれかの遺伝子が引き継がれる確率が決められる。図６のグラフのｅｘｐカーブはその確率が単調増加あるいは単調減少関数で求められることを示す。たとえ遺伝子適応率が大きくても個体全体としての歩留まりが悪い場合や、遺伝子適応率が低くても個体全体としての歩留まりが良い場合には、確率的にいずれか一方の遺伝子を子に引き継がせるようにして、局所解へ陥るのを防止した。
【００６８】
（多様化処理）
多様化処理手段２７は、次世代の処理の前に、個体集団の一部を新たに生成した個体と入れ替えたり、一部に突然変異を生じさせたりする。この処理によって局所解への落ち込みを抑制することができる。多様化処理を行う個体の選択は、ランダムな方法によって行ってもよいし、ランダムな方法以外の方法で行ってもよい。例えば個体適応率が低い個体を優先的に選択して入れ替えるようにしてもよい。この実施例では、多様化処理は交叉処理の後に行われる。多様化処理の対象となる個体の割合は、特に限定されないが、例えば５〜４０％程度である。この多様化処理を行うタイミングは特に限定されない。交叉処理の前や個体選択の前に行ってもよい。
【００６９】
突然変異では、選択された個体中の選択された遺伝子を変異させる。遺伝子の選択は、ランダムな方法によって行ってもよいが、例えば遺伝子適応率が低い遺伝子を優先的に選択する等、完全にランダムな方法以外の方法で選択を行ってもよい。遺伝子を変異させる方法は特に限定されないが、一例では、（１２）式の遺伝子Ｂおよび遺伝子Ｐの設定ルールに従って遺伝子を再設定することによって変異させることができる。変異遺伝子座数は、特に限定されないが、全体の座数の例えば３〜３０％である。突然変異は、遺伝子Ｂと遺伝子Ｐの何れか一方のみ起こるようにしてもよく、両方に起こるようにしてもよい。遺伝子Ｂが突然変異した場合、変異後の内容に基づいて遺伝子Ｐを更新することが合理的であり好ましい。一方、遺伝子Ｐの場合は単独で変化させることが好ましい。
【００７０】
（繰り返し制御）
繰り返し制御手段２７は、終了基準が満たされるまで上記の世代交代を繰り返すように制御する。終了基準は、特に限定されないが、例えば、（１）集団に属する個体のうち個体適応率が最大のものの個体適応率が目標値を超える、（２）集団の世代数が基準値を超える等が挙げられる。（２）のみを終了基準としてもよい。目標の個体適応率を超えた後に処理を続けるのは効率的でない場合がある。そこで、（１）と（２）の基準を併用して（１）又は（２）の条件が満たされたときに終了基準が満たされたと判断することが好ましい。
【００７１】
終了後は、集団に属する個体のうち個体歩留が最大のものを取り出す。そして、染色体Ｂと染色体Ｐを用いて上述した製品割り付けルールに従って製品を材料に割り付け、その割り付け結果を出力させることができる。
【００７２】
（装置の概略動作）
図７と図８は上記の装置の動作フローチャートである。
上記の装置のコンピュータプログラムは、例えば、次のような手順で動作する。はじめに、ステップＳ１１で、初期設定手段２１が初期個体集団を生成する。即ち、所定の構造の染色体を持つ個体を、十分な数だけ生成する。それらの染色体構造データを含む個体データを記憶装置に記憶させる。製品割り付け手段２２は、こうして得られた初期個体集団３１から、個体データを一つずつ記憶装置から読み出して、全ての個体について、ステップＳ１２からステップＳ２０までの処理を実行する。
【００７３】
まず、ステップＳ１２で、対象となる個体データを選択する。ステップＳ１３でGeneBとGenePを使用してソート処理をする。その後、ステップＳ１４で、取り合わせ計算（「取り合わせ計算ルール」の項で説明）を実行する。ステップＳ１５では、その個体データの個体歩留まりを計算する。さらに、ステップＳ１６で使用される各材料の材料歩留まりを計算する。ステップＳ１７では、ソートキーとなるGenePを（９）式を用いて計算し、書き替えをする。ステップＳ１８では、ＧＦＲ（遺伝子適応率）を計算する。さらにステップＳ１９で個体適応率を計算する。
【００７４】
ステップＳ２０で全ての個体について計算が終了したかどうかという判断をする。この判断の結果がノーのときはステップＳ１２の処理に戻る。イエスのときは処理を終了して図８の処理に進む。図８のフローチャートにおいて、ステップＳ３１〜３３は繰り返し制御手段２７の処理である。ステップＳ３４は個体選択手段２４の処理である。ステップＳ３５〜３７は交叉制御手段２５の処理である。ステップＳ３８は多様化処理手段２６の処理である。
【００７５】
ステップＳ２１では、対象となる個体データの中から、個体歩留が最大値のものを読み出す。例えば、ステップＳ１５で、個体歩留の計算と同時に、個体歩留の高いものを選別する処理をしておけばよい。ステップＳ２２では、そのうちの最大歩留まりは目標値かどうかという判断をする。目標値であれば、処理を終了する。ステップＳ２３では、最大世代数まで世代交代を実行したかどうかという判断をする。この判断の結果がイエスのときは処理を終了する。
【００７６】
ステップＳ３２とステップＳ３３の判断の結果がいずれもノーのときはステップＳ３４以下の処理に移行する。即ち、次の世代交代を実行する。ステップＳ２４では、上記のソートの結果を利用して、個体適応率の良い個体を例えば、全体の２分の１だけ選択する。これが親の個体集団３７になる。ステップＳ２５では、その個体集団の中から一対の親を選択する。そして、既に説明したようにして、ステップＳ２６で交叉制御をする。ステップＳ２７では、子の個体データが必要数生成されたかどうかという判断をする。この判断の結果がイエスのときはステップＳ３８の処理に移行し、ノーのときはステップＳ３５の処理に戻る。ステップＳ２８では、多様化処理をする。そして、再び、図７のステップＳ１２以下の材料取り合わせ処理を繰り返す。
【００７７】
（BBPベンチマーク問題による評価）
材料取り合わせ計算は、様々な計算方法による計算結果を比較して、そのうちのもっとも良い割り付け結果を採用するとよい。材料と製品の組み合わせにより、それぞれ最適な計算方法が異なることが多いからである。従って、コンピュータによる演算処理時間が長いものは、作業効率を妨げる。そこで、次のようなベンチマークテストをして、本発明の装置の実用性の高さを実証する。
【００７８】
上記のTCOMモデルでは、材料の長さ種類ｍ＝１としてBPPベンチマーク問題によって：拡張エリート選択(Extended Elitism Method: EEM)GAモデル(Toyoda, et al., 2007)との比較や、TCOMモデルのRFF初期個体生成率αを1、0.5および0とした場合の比較を行った。使用したベンチマークデータはData Set 3に分類されるもので、ビン容量が100000に対してアイテムサイズは(20000,35000)の範囲で一様分布している。ビンには3から5つのアイテムが入るように設定されるVery Hardとされる10例の問題である。これに、現在知られている最少使用ビン数が示されている。
【００７９】
その結果、EEMに対する優位性を確認すると同時に、RFFによる初期個体生成の比率による違いは次のような結果となった。初期個体比率α＝０．５とした場合は10問中8問でビンの最少解が得られ、α＝０では収束速度は遅いものの得られた解はα＝０．５の場合と同等であった。しかし、α＝１として全ての初期個体をRFFとRFFDで生成した場合は、10問のうち最少解を得たのは５問のみであり、TCOMは初期固体の構成によって局所解に陥る危険があることを確認した。
【００８０】
そこで、本発明による、交叉に確率的要素を取り入れた新しいTCOMモデルを、同じベンチマーク問題に適用し、その効果を確認することにする。上記の前モデルで多様性維持のために行った突然変異における新規個体投入を、本発明では敢えて多様性より計算時間短縮を優先して行わないことにする。その他の条件は前モデルと同様に、個体数は100、最大世代数は1000世代とし、各種パラメータは(18)式として、10回の試行で最も良い結果を採用する。ベンチマーク問題は、前回と同じData Set 3のVery Hardとされる10例の問題を使い、実行環境も表3のとおり前回と同じである。
【数１２】
2010152584.tif 000016
【００８１】
【表３】
2010152584.tif 000017
【００８２】
実行結果を表4に示した。NewTCOMが今回の改善後の新モデルである。"All RFF"はα＝１００％、"50%RFF"はα＝５０％、"All RN"はα＝０％ですべてを乱数によって生成したことを示している。"Hits"は10の問題のうち最適値が得られた問題の数であり、"Av.Rel."は各問題の相対偏差平均、"Max.Rel."は最大相対偏差、"Av.Abs."は絶対偏差平均、"Max.Abs."は最大絶対偏差である。なお相対偏差は、100×(実行値−最少解)／最少解で、絶対偏差は(実行値−最少解)で計算される。"Av.Time"は平均計算時間で単位は秒である。表4からわかるように、今回の改善後のモデルでは、α＝１００％の場合でも8問が最少解となり、また平均計算時間も優秀な初期個体の効果により最も早い3秒台となった。
【００８３】
【表４】
2010152584.tif 000018
【００８４】
（住宅プレカット材料データによる評価）
前回のモデルに適用したものと同じ住宅プレカットデータで、改善モデルを評価する。住宅プレカットCSPとは、いくつかの種類の長さを持つ木材母材から、住宅建築で要求される長さの部材(製品)を切り出す問題である。ここでは標準的な２つの一戸建て住宅の横架材に適用した(表6，付表1)。これらの横架材は、断面形状(Shape)や樹種(Spec.)、等級(Grade)など同じ母材から切り出すことができる16および18のロットにグループに分かれ、それぞれのロット毎に切り出す製品数(Num.)や使用する母材群(Kinds of Material)も異なる。なお邸全体の歩留は、ロット毎に断面形状が異なるため体積による材積歩留で比較する。
パラメータは前回と同じように(18)式でλ＝０．２とし、個体数は100とする。最大世代数は前回の報告で実用を考えた場合の設定ルールである(19)式で設定する。また、試行回数も前回と同じ10回である。その結果を邸１については表5に、邸２については表6に示す。
【数１３】
2010152584.tif 000019
【００８５】
【表５】
2010152584.tif 000020
【００８６】
【表６】
2010152584.tif 000021
【００８７】
表5および表6で、"Num. of Prd."および"Num. of Mtr."はそれぞれ各ロットの製品数と材長種の数である。"Max. Gen."は(19)式のルールに基づく最大世代数である。新旧のTCOM欄の"Yield Rate"は10回の試行で得た最大歩留、"Num."は10回の試行のうち最大歩留を得た回数、"Time"は計算時間を秒で表した。ここで、旧TCOMのデータは前回報告のものである。なおTimeは、前回は有効数字1桁であったため若干小さ目に出ており、実質的には今回と前回は変わらない。以上の結果、プレカットデータによる評価では、前回のモデルとほぼ同等の結果となった。これは、いずれの邸も歩留はほぼ最適値と想定され、また製品数が最大でも40以下であり、歩留と時間のいずれも顕著な差がでなかったと推定できる。
【００８８】
（まとめ）
複数材長を扱う一次元のMultiple Stock Length CSPを対象に、前回報告したTCOMを使ったGAモデルについて、TCOMによる交叉では引き継ぐ遺伝子を確定的に決定するため、局所解に陥る危険があることを指摘した。そしてこの打開策として、親個体の（１−歩留）を「温度」とみなして、遺伝子交換の決定過程に焼きなまし法の考え方を取り入れることで、確率の要素を取り入れる新しいTCOMを提案した。これを前回と同じBPPベンチマークデータとプレカットデータに適用し、新旧のTCOMを比較評価した。その結果、ベンチマークデータではRFFによる初期個体性成立を100%にしたとき、旧モデルでは10問中5問の最少解であったのに対し、新TCOMでは8問の最少解をより短時間に得ることができた。また、プレカットデータに対しては同等の性能であることを確認した。
【図面の簡単な説明】
【００８９】
【図１】本発明の製品割り付け装置の実施例を示す機能ブロック図である。
【図２】上記の製品割り付け装置の本体制御部の内部ブロック図である。
【図３】本発明の製品割り付け装置で使用するデータ構造の説明図である。
【図４】本発明の製品割り付け装置の概略動作を示す説明図である。
【図５】交叉制御の動作例を示す説明図である。
【図６】焼き鈍し法による確率曲線の説明図である。
【図７】本発明の装置の動作フローチャート（前半）である。
【図８】本発明の装置の動作フローチャート（後半）である。
【符号の説明】
【００９０】
１０  製品割り付け装置
１１  プリンタ
２０  演算処理装置
２１  初期設定手段
２２  製品割り付け手段
２３  適応率計算手段
２４  個体選択手段
２５  交叉制御手段
２６  多様化処理手段
２７  繰り返し制御手段
３０  記憶装置
３１  初期個体集団
３２  材料データ
３３  製品データ
３４  取り合わせ計算ルール
３５  世代交代上限値
３６  歩留まり目標値
３７  親の個体集団
３８  子の個体集団
３９  最良割り付け
４０  最良個体歩留
【図１】
2010152584.tif 000022
【図２】
2010152584.tif 000023
【図３】
2010152584.tif 000024
【図４】
2010152584.tif 000025
【図５】
2010152584.tif 000026
【図６】
2010152584.tif 000027
【図７】
2010152584.tif 000028
【図８】
2010152584.tif 000029