(57)【特許請求の範囲】
【請求項１】
部材を切り出す鋼板にマーキン線を描画するマーカの移動経路を最適化する方法であって、
前記マーキン線の描画データを取得し、該取得した描画データから、前記マーキン線を構成する線分の始点及び終点を前記移動経路上の地点として定義する地点定義ステップと、
前記最適化処理の条件パラメータを設定するパラメータ設定ステップと、
以下の（ア）及び（イ）の各ステップ、即ち、
（ア）前記地点のうち任意の２地点間を結ぶ各経路にそれぞれ設定されたフェロモン値に対する感度が互いに異なる複数種類のエージェントを用いて、全ての前記地点を巡回する巡回路をアントコロニー法により構築する経路探索を、予め定められた収束条件又は終了条件の成立まで反復する経路探索ステップと、
（イ）前記経路探索の各反復で前記巡回路の解が得られる毎に、得られた解に基づいて前記フェロモン値を更新するフェロモン値更新ステップと、
を、前記条件パラメータにしたがい実行するアントコロニー最適化処理ステップと、
前記経路探索の各反復で前記巡回路の解が得られる毎に、該得られた解のうち最短経路長の解を、過去の反復で得られた前記巡回路の解のうち最短経路長の解と比較し、経路長が短い方の解を記憶保存する最短解保存ステップと、
前記経路探索の各反復で前記巡回路の解が得られる毎に、該得られた解が局所最適解であるか否かを判定する判定ステップと、
前記判定ステップで局所最適解であると判定された場合に、前記条件パラメータの設定内容を、各反復で得られる前記巡回路の最短経路長の解の収束度が変化するように変更するパラメータ変更ステップと、
前記収束条件又は終了条件の成立時に、前記最短解保存ステップで記憶保存した解を、最適化した前記移動経路として出力する出力ステップと、
を含むことを特徴とするマーカの移動経路最適化方法。
【請求項２】
前記収束条件又は終了条件の成立時に、前記条件パラメータの設定内容を、前記取得した描画データ中の前記鋼板に描画する前記マーキン線の型式を示す型式識別データと関連付けて記憶保存するパラメータ保存ステップと、
前記描画データの取得時に、該取得した描画データ中の型式識別データを、前記パラメータ保存ステップで記憶保存した型式識別データと照合する型式照合ステップと、
をさらに含み、
前記パラメータ設定ステップは、前記型式照合ステップの照合において前記取得した描画データ中の型式識別データと一致する型式識別データが前記パラメータ保存ステップで記憶保存されている場合に、該型式識別データと関連付けて記憶保存されている設定内容に前記条件パラメータを設定する、
ことを特徴とする請求項１記載のマーカの移動経路最適化方法。
【請求項３】
前記地点定義ステップは、
前記取得した描画データから、一の前記線分と、該一の線分の終点から所定のしきい値以下の距離に始点が存在する他の前記線分とを一の線分グループに属させ、該一の線分グループにおける描画順が最初の前記線分の始点と描画順が最後の前記線分の終点とを、前記移動経路上の地点としてそれぞれ定義する、
ことを特徴とする請求項１又は２記載のマーカの移動経路最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鋼板から切り出す部材の現図の際に鋼板のマーキン面にマーキン線を描画するマーカの移動経路の最適化方法に関するものである。
【背景技術】
【０００２】
例えば造船の分野では、ネスティングを行って鋼板から歩留まりよく船殻部材を切り出せるレイアウトを決定し、決定したレイアウトで鋼板のマーキン面にマーキンを行うことで、船殻部材を鋼板上に現図するようにしている。
【０００３】
鋼板に対するマーキンにはマーキン機が用いられる。マーキン機は、通常、鋼板のマーキン面に沿ってマーカを移動させるＸ−Ｙステージを有している。造船に用いる鋼板はその寸法が長大であることから、マーキンの際にマーカを効率よく移動させることが、マーキン作業の短時間化に大きく貢献する。
【０００４】
マーキン作業におけるマーカの移動パターンは、現状、ソートプログラムによって決定している。ソートプログラムでは、計算機の性能の良し悪しに拘わらず同じ解が求められる。ソートの考え方の基本は、まず、横方向に長いロンジ取り付け線等を原点側から反原点側に向けて鋼板にマーキンする。続いて、反原点側から原点側に向けて横方向に長い線をマーキンしながらマーカを戻させる。これを繰り返した後、上下に延びる幅方向の線を、原点側と反原点側との間でマーカを往復させながらしてマーキンしていく。
【０００５】
このようにソートプログラムを用いてマーカの移動パターンを決定する手法は、人間が機械を見たときに次の動作予測を立てやすいことから、長く間利用されている。ところが、ソートの考え方は、必ずしも全ての鋼板にマッチするとは限らない。例えば、長さ方向（横方向）と幅方向の線のバランスが良くないケース等では、ソートプログラムで決定した移動パターンにより、マーカが無駄な動きをしてしまう場合が多かった。
【０００６】
マーカの無駄な動きをなくし、マーキン線からマーキン線に移る時や、テキストからテキストに移る時の空走距離を短くして、マーカの移動距離を少なくするには、鋼板毎に個別の最適なソートプログラムを作成することが理想的である。しかし、そうすることは非現実的であるため、結果として、最適解ではなく平均的な解しか得られない汎用的なアルゴリズムのソートプログラムで良しとしているのが現状である。
【０００７】
とは言え、上述したような平均的な解を得るソートプログラムを用いる現状の手法にも限界があり、解にムラが生じてしまうことも多々あるので、考え方を改めて、マーカの全移動パターンの中から一番良い移動パターンを見つけ、これを近似解として採用する最適化の考え方を導入することにした。
【０００８】
近年、最適化の手法の一つとして、アントコロニー最適化手法（ＡＣＯ）が提唱されている。アントコロニー最適化手法は、蟻のコロニーの求餌行動にヒントを得たものである。
【０００９】
例えば、巡回セールスマン問題（ＴＳＰ）にアントコロニー最適化手法を適用して路長の短い巡回路を求める場合には、各路に付加したフェロモンに感度を有する複数の蟻の行動から、複数の巡回路を構築する。そして、複数の蟻による巡回路構築を終了条件が成立するまで反復し、反復して構築した巡回路の中から路長の短い最適解を求める。ここで、フェロモンとは時間の経過と共に減少又は消滅するパラメータであり、現実の蟻の行動により発生する揮発性物質を模したものである。このフェロモンの値は、解を構成する各路の評価値として用いられる。このようにして巡回路の最適解を求める方法は、Ａｎｔ  Ｓｙｓｔｅｍ（ＡＳ）と呼ばれる。各路のフェロモン値は、複数の蟻による巡回路の構築を反復する度に、構築した複数の巡回路を用いて更新される。
【００１０】
ところで、ＡＳについては、大規模な問題に対する求解能力の低さが指摘されている。そこで、この点を改良した方法がいくつか提案されている。Ｒａｎｋ−Ｂａｓｅｄ  Ａｎｔ  Ｓｙｓｔｅｍ（ＡＳ−Ｒａｎｋ）や、Ｍａｘ−Ｍｉｎ  Ａｎｔ  Ｓｙｓｔｅｍ（ＭＭＡＳ）もその一つである。
【００１１】
ＡＳ−Ｒａｎｋでは、終了条件が成立するまでの間、複数の蟻が複数の巡回路を構築する度に、構築した複数の巡回路と、それまで反復して構築された巡回路とを、路長が短い巡回路から順にソートしたリストを作成する。そして、今回構築された各巡回路の、作成したリスト上のランクに対応する重み付けをした上で、各巡回路を用いて各路のフェロモン値を更新する。
【００１２】
ＭＭＡＳでは、局所最適解へのトラップを避けるために、フェロモン値の更新に、更新の際に構築された複数の巡回路における最良解、又は、更新までの反復において構築された全ての巡回路における最良解を用いる。また、ＭＭＡＳでは、フェロモン値に対して上限値と下限値が設定され、更新で得られたフェロモン値が上限値又は下限値を超える場合は、更新後のフェロモン値が上限値又は下限値に置き換えられる。なお、フェロモン値の初期値は上限値に設定される。また、局所最適解にトラップされた場合には、フェロモン値が上限値に更新される。
【００１３】
上述したＭＭＡＳでは、フェロモン値の上下限制限や、スタート時及び局所最適解へのトラップ後の再スタート時におけるフェロモン値の上限値使用によって、各路のフェロモン値の差が小さくなりやすくなる。そのため、初期反復時において一部の路のフェロモン値が高くなり、望ましくない局所最適解へのトラップが回避されやすくなる。但し、各反復時に構築された複数の巡回路の多様性を有効に利用しづらくなることから、複数の蟻を用いるＡＣＯの群知能モデルとしての特徴を十分に生かし切れないという側面がある。
【００１４】
そこで、局所最適解へのトラップを回避し、かつ、各反復時に構築された複数の巡回路の多様性を有効利用するための、ＡＳ−Ｒａｎｋをベースとした新しい方法が提案された。この提案では、フェロモン値に対する感度が異なる３種類の蟻を使用する。まず、標準的な感度を有する蟻は、フェロモン値の高い路を優先的に選択して巡回路を構築する。逆感度を有する蟻は、フェロモン値の低い路を優先的に選択して巡回路を構築する。ランダム選択の蟻は、フェロモン値の高低を全く無視しランダムに路を選択して巡回路を構築する。この３種類の蟻をＤｉｆｆｅｒｅｎｔ  Ｓｅｎｓｉｔｉｖｅ  Ａｎｔｓ（ＤＳＡ）と呼ぶ。
【００１５】
また、この提案では、フェロモン値の更新に際して作成するリストに、今回の反復で構築した複数の巡回路のうち所定数の解を追加する。具体的には、所定数のうち所定割合（Ｐｒａｔｅ，０＜Ｐｒａｔｅ＜１）については、今回の反復で構築した解を、巡回路長が短い順からリストに追加する。また、所定数のうち所定割合を差し引いた残りについては、残る巡回路長の比較的短い解を、同じ反復で構築した最良解との巡回路長の距離差が大きい順からリストに追加する。
【００１６】
そして、各反復で構築した最良解の巡回路長が、それ以前に行った全反復を通じた最良解の巡回路長を、連続して所定回数下回らなかった場合は、上述した所定割合（Ｐｒａｔｅ）の値を減少させる。この手法をＰａｒｅｔｏ  Ｒａｎｋｉｎｇ  Ｓｅｌｅｃｔｉｏｎ（ＰＲＳ）と呼ぶ。
【００１７】
以上のＡＳ、ＡＳ−Ｒａｎｋ、ＭＭＡＳ、ＤＳＡとＰＲＳとを併用したＡＳ−Ｒａｎｋの改良法の各方法については、非特許文献１に詳細に解説されている。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】巽啓司; 谷野哲三、″解の多様性を維持するアントコロニー最適化手法(モデリングと最適化の理論)″、数理解析研究所講究録第１５２６巻  Ｐ．２４１−２４９、［online］、２００６年１２月、京都大学数理解析研究所、［２０１０年８月１３日検索］、インターネット〈URL：http://hdl.handle.net/2433/58855〉
【発明の概要】
【発明が解決しようとする課題】
【００１９】
上述したＤＳＡとＰＲＳとを併用したＡＳ−Ｒａｎｋの改良法によるアントコロニー最適化手法を、マーキン経路の最適化に用いることは、鋼板毎に最適なマーキン経路を求めることができるので、非常に有用である。
【００２０】
但し、アントコロニー最適化手法には、解が局所最適解に陥りやすいという難点がある。その場合、他により短い経路が存在していても、周りの経路よりも相対的に短い経路に収束してしまうことがある。アントコロニー最適化手法では、フェロモン値が最も高い経路に収束した結果を最短経路長の解としているので、解が局所最適解に陥ると、実はフェロモン値が一番高い経路より低くても、フェロモン値が一番高い経路よりも経路長が短い経路が存在するケースが発生する。
【００２１】
本発明は前記事情に鑑みなされたもので、本発明の目的は、アントコロニー最適化手法を用いて鋼板毎に適切な最短経路長のマーカの移動経路を求めることができるマーカの移動経路最適化方法を提供することにある。
【課題を解決するための手段】
【００２２】
上記目的を達成するため、請求項１に記載した本発明のマーカの移動経路最適化方法は、
部材を切り出す鋼板にマーキン線を描画するマーカの移動経路を最適化する方法であって、
前記マーキン線の描画データを取得し、該取得した描画データから、前記マーキン線を構成する線分の始点及び終点を前記移動経路上の地点として定義する地点定義ステップと、
前記最適化処理の条件パラメータを設定するパラメータ設定ステップと、
以下の（ア）及び（イ）の各ステップ、即ち、
（ア）前記地点のうち任意の２地点間を結ぶ各経路にそれぞれ設定されたフェロモン値に対する感度が互いに異なる複数種類のエージェントを用いて、全ての前記地点を巡回する巡回路をアントコロニー法により構築する経路探索を、予め定められた収束条件又は終了条件の成立まで反復する経路探索ステップと、
（イ）前記経路探索の各反復で前記巡回路の解が得られる毎に、得られた解に基づいて前記フェロモン値を更新するフェロモン値更新ステップと、
を、前記条件パラメータにしたがい実行するアントコロニー最適化処理ステップと、
前記経路探索の各反復で前記巡回路の解が得られる毎に、該得られた解のうち最短経路長の解を、過去の反復で得られた前記巡回路の解のうち最短経路長の解と比較し、経路長が短い方の解を記憶保存する最短解保存ステップと、
前記経路探索の各反復で前記巡回路の解が得られる毎に、該得られた解が局所最適解であるか否かを判定する判定ステップと、
前記判定ステップで局所最適解であると判定された場合に、前記条件パラメータの設定内容を、各反復で得られる前記巡回路の最短経路長の解の収束度が変化するように変更するパラメータ変更ステップと、
前記収束条件又は終了条件の成立時に、前記最短解保存ステップで記憶保存した解を、最適化した前記移動経路として出力する出力ステップと、
を含むことを特徴とする。
【００２３】
請求項１に記載した本発明のマーカの移動経路最適化方法によれば、アントコロニー最適化処理により反復して得られるマーキン線描画用のマーカの巡回路の解が局所最適解に陥ると、巡回路の最短経路長の解の収束度が変化するように最適化処理の条件パラメータを変更して、以後の最適化処理が反復される。
【００２４】
そして、収束条件又は終了条件が成立するまでの、アントコロニー最適化処理の反復中に得られた巡回路の解のうち、最短経路長の解が、最適化したマーカの移動経路として出力される。
【００２５】
このため、アントコロニー最適化処理の解が局所最適解に陥り、フェロモン値の一番高い経路が最短経路長でないにも拘わらず最適化した移動経路として出力されるのを防止して、アントコロニー最適化手法を用いて鋼板毎に適切な最短経路長のマーカの移動経路を求めることができる。
【００２６】
また、請求項２に記載した本発明のマーカの移動経路最適化方法は、請求項１に記載した本発明のマーカの移動経路最適化方法において、
前記収束条件又は終了条件の成立時に、前記条件パラメータの設定内容を、前記取得した描画データ中の前記鋼板に描画する前記マーキン線の型式を示す型式識別データと関連付けて記憶保存するパラメータ保存ステップと、
前記描画データの取得時に、該取得した描画データ中の型式識別データを、前記パラメータ保存ステップで記憶保存した型式識別データと照合する型式照合ステップと、
をさらに含み、
前記パラメータ設定ステップが、前記型式照合ステップの照合において前記取得した描画データ中の型式識別データと一致する型式識別データが前記パラメータ保存ステップで記憶保存されている場合に、該型式識別データと関連付けて記憶保存されている設定内容に前記条件パラメータを設定する、
ことを特徴とする。
【００２７】
請求項２に記載した本発明のマーカの移動経路最適化方法によれば、請求項１に記載した本発明のマーカの移動経路最適化方法において、アントコロニー最適化処理の反復によって得られるマーカの巡回路の解が局所最適解となると、条件パラメータの設定内容が変更される。したがって、収束条件又は終了条件の成立時における条件パラメータは、アントコロニー最適化処理の反復によって得られるマーカの巡回路の解が局所最適解とならない内容であることになる。
【００２８】
よって、収束条件又は終了条件の成立時に記憶保存される条件パラメータの設定内容は、その条件パラメータによるアントコロニー最適化処理の反復でマーカの最短経路長の解を得たマーキン線にとって、最短経路長の解を効率よく得るのに適した内容であることになる。
【００２９】
このため、最適化処理の条件パラメータを記憶保存したマーキン線の描画データと型式識別データが同じマーキン線の描画データを取得した場合に、アントコロニー最適化処理を記憶保存した条件パラメータによって行うことで、そのマーキン線について、適切な最短経路長のマーカの移動経路を効率よく求めることができる。
【００３０】
さらに、請求項３に記載した本発明のマーカの移動経路最適化方法は、請求項１又は２に記載した本発明のマーカの移動経路最適化方法において、
前記地点定義ステップが、
前記取得した描画データから、一の前記線分と、該一の線分の終点から所定のしきい値以下の距離に始点が存在する他の前記線分とを一の線分グループに属させ、該一の線分グループにおける描画順が最初の前記線分の始点と描画順が最後の前記線分の終点とを、前記移動経路上の地点としてそれぞれ定義する、
ことを特徴とする。
【００３１】
請求項３に記載した本発明のマーカの移動経路最適化方法によれば、請求項１又は２に記載した本発明のマーカの移動経路最適化方法において、互いの終点と始点とが所定のしきい値以下の距離にある二つの線分が属する同一の線分グループに対してマーカの移動経路上の２つの地点が定義されることになる。
【００３２】
したがって、各線分の始点及び終点にそれぞれマーカの移動経路上の２つの地点が定義されるよりも、アントコロニー最適化処理によって全地点の巡回路の解を得る際の処理の規模が小さくなる。
【００３３】
このため、アントコロニー最適化処理による巡回路の解を求める処理の全体量を抑制し、処理時間の短縮化を図ることができる。
【発明の効果】
【００３４】
本発明のマーカの移動経路最適化方法によれば、アントコロニー最適化手法を用いて鋼板毎に適切な最短経路長のマーカの移動経路を求めることができる。
【図面の簡単な説明】
【００３５】
【図１】本発明が適用されるマーキン装置の概略構成を示す斜視図である。
【図２】本発明に係るマーカの移動経路最適化方法に利用できるＡＳ−Ｒａｎｋの改良法によるアントコロニー最適化処理におけるランキングリスト作成方法の概念を示すグラフである。
【図３】本発明の一実施形態に係るマーカの移動経路最適化方法の手順を示すフローチャートである。
【図４】本発明の一実施形態に係るマーカの移動経路最適化方法の手順を示すフローチャートである。
【図５】図１のマーキン装置で鋼板に描画するマーキン線の描画データの一例を示す説明図である。
【図６】図３の手順において複数のマーキン線をグループ化する際の具体例を示す説明図である。
【図７】図３の手順において複数のマーキン線をグループ化する際の具体例を示す説明図である。
【図８】図３の手順において複数のマーキン線をグループ化する際の具体例を示す説明図である。
【図９】図３及び図４の手順で最適化処理を行った場合に得られる最適化されたマーカの移動経路の解を示す説明図である。
【図１０】マーキン線の描画パターンに依存しない汎用的な最適化手法によって最適化処理を行った場合に得られる最適化されたマーカの移動経路の解の一例を示す説明図である。
【発明を実施するための形態】
【００３６】
以下、本発明の実施形態について図面を参照しながら説明する。
【００３７】
図１は本発明が適用されるマーキン装置の概略構成を示す斜視図である。本実施形態のマーカの移動経路最適化方法は、図１に示すＮＣ印刷装置１のマーカ３で鋼板５のマーキン面５ａにマーキン線７を描画する際の、マーカ３の移動経路を最適化する際に用いられる。マーキン線７は、鋼板５から切り出す部材９ａ，９ｂ，９ｃを現図するために、マーキン面５ａに描画するものである。
【００３８】
なお、図１のＮＣ印刷装置１には、マーカ３をカッタ（図示せず）に取り替えることによって、ＮＣ切断装置としても使用できるものを用いてもよく、印刷専用機を用いてもよい。
【００３９】
本実施形態では、マーカ３の移動経路の最適化に、背景技術の欄で説明したＤＳＡ（Ｄｉｆｆｅｒｅｎｔ  Ｓｅｎｓｉｔｉｖｅ  Ａｎｔｓ）とＰＲＳ（Ｐａｒｅｔｏ  Ｒａｎｋｉｎｇ  Ｓｅｌｅｃｔｉｏｎ）とを併用した、ＡＳ−Ｒａｎｋの改良法によるアントコロニー最適化処理を用いる。そこで、このアントコロニー最適化処理の全体的な手順を以下に説明する。
【００４０】
まず、このアントコロニー最適化処理は、都市Ｎと都市間の経路Ｐに対して、最小距離を持つ巡回路Ｘを求める処理である。巡回路Ｘとは、ある都市Ｎから出発し全ての都市Ｎを一度ずつ訪問して最初の都市Ｎに戻ってくる路のことである。ここで、都市ｉ，ｊ∈Ｎを結ぶ経路（ｉ，ｊ）∈Ｐの長さをｄｉｊとすると、最小距離を持つ巡回路Ｘを求める問題は、以下の（１）式によって定型化できる。
【数１】
0005520763.tif 000002
【００４１】
この問題を解くため、ＤＳＡを併用する本実施形態のＡＳ−Ｒａｎｋの改良法によるアントコロニー最適化処理では、複数の蟻（エージェント）ｋ∈Ａを各都市にランダムに配置する。そして、各ステップｔにおいて、都市ｉにいる蟻ｋが次の都市をそれぞれ選択し、ステップｔ＝ｎで、各蟻ｋがそれぞれ巡回路Ｘｋ  を構築する。なお、本実施形態では、以下のように、後述するフェロモン値に対して３種類の感度をもつ蟻ｋを使用する。
【００４２】
まず、標準的な蟻ＡＮＳは、各ステップｔにおいて都市ｉにいるときの、次の都市ｊを選択する確率ｐｋｉｊ  が、以下の（２）式によって定義される。
【数２】
0005520763.tif 000003
【００４３】
ここで、τｉｊは、経路（ｉ，ｊ）に付加されたフェロモン値を表す。また、ηｉｊは、ヒューリスティック情報と呼ばれ、問題に合わせ各経路にアプリオリに与えられる定数である。巡回路を求める巡回セールスマン問題（ＴＳＰ）に対しては、（１／ｄｉｊ）がよく用いられる。さらに、αとβは正の整数であり、それぞれτｉｊとηｉｊの相対的な影響度を決定する定数である。Ｎｋ  （ｔ）は、ステップｔにおいて蟻ｋが未訪問の都市集合を表す。
【００４４】
次に、逆感度をもつ蟻ＡＩＳは、各ステップｔにおいて都市ｉにいるときの、次の都市ｊを選択する確率ｐｋｉｊ  が、以下の（３）式によって定義される。
【数３】
0005520763.tif 000004
【００４５】
つまり、経路（ｉ，ｊ）に付加されたフェロモン値τｉｊが小さく、ヒューリスティック情報ηｉｊが大きい場合（ヒューリスティック情報ηｉｊに（１／ｄｉｊ）を用いた場合は、経路の長さｄｉｊが短い場合）、高い確率でその経路（ｉ，ｊ）を選択する。
【００４６】
次に、ランダム選択の蟻ＡＲＳは、フェロモン値τｉｊの高低を全く無視しランダムに経路を選択する（ランダムに次の都市を選ぶ）。
【００４７】
ステップｔ＝ｎで、各々の蟻ｋは、それぞれ巡回路Ｘｋ  を構築する。その後、それぞれの経路のフェロモン値τｉｊは、得られた解（各蟻ｋが構築した巡回路Ｘｋ  ) を用いて、以下の（４），（５）式によって更新される。
【数４】
0005520763.tif 000005
【００４８】
ここで、ρ（０＜ρ＜１）は、フェロモンの蒸発率を表す。この巡回路構築を、収束条件又は終了条件が成立するまで何度も反復していく。
【００４９】
なお、ＡＳ−Ｒａｎｋでは、フェロモン値τｉｊの更新の際、その反復で得られた解（巡回路）Ｘｋ  を、巡回路長が短い解から順にソートしたリストＬ⊂Ａを作成し、そのランクに対応した重みｗｋ  を用いて、各経路のフェロモン値を更新する。したがって、この重みｗｋ  を（４）式に適用した以下の（６）式によって、フェロモン値τｉｊを更新する。ちなみに、フェロモン値τｉｊの下限値は、τｍｉｎ  に設定する。
【数５】
0005520763.tif 000006
【００５０】
そして、本実施形態のＡＳ−Ｒａｎｋの改良法では、フェロモンに対する感度が異なる３種類の蟻Ａ（エージェント）を使用して解の多様性を図っていることから、フェロモン値τｉｊの更新にも解の多様性が維持されるように、上述したリストＬの作成方法を次のように変更している。
【００５１】
本実施形態のＡＳ−Ｒａｎｋの改良法では、巡回路長だけではなく, 反復ｉにおいて得られた各々の解Ｘｋ  （ｉ），ｋ∈Ａとその反復ｉでの最良解Ｘｂｓ（ｉ）との距離も考慮に入れて解を選択する。その距離としては、δｋ  （ｉ）：＝｜Ｘｋ  （ｉ）−Ｘｂｓ（ｉ）｜を用いるものとする。この値は、Ｘｋ  （ｉ）とＸｂｓ（ｉ）との交差集合の基数である。このように巡回路長が短く、最良解Ｘｂｓ（ｉ）からの距離δｋ  （ｉ）が大きい解、つまり、近似的なパレート解を求めるために以下の手法を用いる。
【００５２】
まず、最初に、得られたすべての解Ｘｋ  （ｉ）を巡回路長の短い順にソートし、その順に｜Ｌ｜Ｐｒａｔｅ個の解をリストに加える。つまり、Ｐｒａｔｅは、１回の反復ｉで得られたすべての解Ｘｋ  （ｉ）のうち、巡回路長の短い方から順にフェロモンを塗布する解Ｘｋ  （ｉ）の割合を表す値であり、いわば、フェロモンの塗布による経路保持率を表す数値と言うことができる。ここでＰｒａｔｅは、０＜Ｐｒａｔｅ＜１を満たす正の定数数とする。
【００５３】
次に、リストに加えなかった残りの解のうち巡回周長が短い順に｜Ａ｜／２個の解の中から距離δｋ  （ｉ）の大きい解を順に｜Ｌ｜（１−Ｐｒａｔｅ）個選び、リストＬに加える。このランキングリスト作成方法の概念を、図２のグラフに示す。その後、リストＬを用いて、（６）式に基づきフェロモン値τｉｊを更新する。
【００５４】
また、今までの各反復によって得られた解Ｘｋ  の中の最良解Ｘ＾（「Ｘの上に＾」の符号。以下同じ。）とその最良解Ｘ＾の巡回路長ｆ＾（「ｆの上に＾」の符号。以下同じ。）を保持し、各反復ｉにおいて、もしその反復ｉで得られた最良解ｆ（Ｘｂｓ（ｉ））が最良解Ｘ＾の巡回路長ｆ＾よりも小さければ、巡回路長ｆ＾の値 を最良解ｆ（Ｘｂｓ（ｉ））の値に置き換える。そうでなく、もしＩｍａｘ  回連続して巡回路長ｆ＾が更新されていない場合は、下式、
Ｐｒａｔｅ＝ｍａｘ｛Ｐｒａｔｅ−（Ｐｄ，Ｐｍｉｎ）｝
を用いてＰｒａｔｅを減少させる。但し、（Ｐｄ，Ｐｍｉｎ）［０＜（Ｐｄ，Ｐｍｉｎ）＜１］とＩｍａｘは、正の定数を表す。
【００５５】
以上に説明した、パレート解を求めるための手法が、背景技術の欄において説明したＰＲＳ（Ｐａｒｅｔｏ  Ｒａｎｋｉｎｇ  Ｓｅｌｅｃｔｉｏｎ）である。
【００５６】
続いて、図３及び図４のフローチャートを参照して、本発明の一実施形態に係るマーカの移動経路最適化方法の手順を説明する。なお、以下に説明する各手順は、例えば、汎用のパーソナルコンピュータによって実行することができる。
【００５７】
本実施形態に係るマーカの移動経路最適化方法は、先に説明したように、ＤＳＡとＰＲＳとを併用したＡＳ−Ｒａｎｋの改良法によるアントコロニー最適化処理である。しかし、単にそれだけでなく、ステップの枠を太線で示した図３のステップＳ３、ステップＳ５、ステップＳ７、ステップＳ１３、及び、ステップＳ１５と、図４のステップＳ４７、ステップＳ４９、及び、ステップＳ５３に、本実施形態独自の特徴的な手順を追加している。
【００５８】
まず、図３に示すように、マーキン線７の描画データをＮＣ印刷装置１からダウンロードさせて取り込む（ステップＳ１）。図５の説明図に示すように、ここで取り込む描画データＤは、鋼板５のマーキン面５ａに描画するマーキン線７を示すＣＡＤデータである。このＣＡＤデータの形式は任意であるが、本実施形態ではＪＷＣ形式のＣＡＤデータを取り込むようにしている。描画データには、マーキン線７を構成する線分やテキストの座標や要素情報が含まれている。
【００５９】
なお、図５中の破線で示すマーキン線７は、鋼板５から切り取る部材９ａ，９ｂ，９ｃ，…の輪郭線であり、実線で示すマーキン線７は、切り取った部材９ａ，９ｂ，９ｃ，…に他の部材を溶接する位置や、各部材９ａ，９ｂ，９ｃ，…の部材名情報を示すテキスト等の描画線である。
【００６０】
次に、ステップＳ１で取り込んだ描画データＤのマーキン線７が流用番船のものであるか否かを確認する（ステップＳ３）。
【００６１】
ここで、型式識別データとは、マーキン線７の描画データＤが何番船に関するものであるかを示す識別データであり、描画データＤ中に含まれている。また、条件パラメータデータベースは、例えば、汎用パーソナルコンピュータのハードディスクドライブ等に設けられる。この条件パラメータデータベースには、条件パラメータの設定内容と型式識別データとが関連付けて記憶保存されている。
【００６２】
条件パラメータは、後述するアントコロニー最適化処理を行う際の条件を定義するパラメータである。条件パラメータの設定内容と関連付ける型式識別データは、その条件パラメータでマーカ３の移動経路のアントコロニー最適化処理を行ったマーキン線７の描画データＤ中に含まれた型式識別データである。
【００６３】
そして、後述するようにアントコロニー最適化処理の収束条件又は終了条件が成立し、最適化したマーカ３の移動経路の解を最適化処理の結果として出力する時点で、条件パラメータとして設定されていた内容が、型式識別データと関連付けて条件パラメータデータベースに記憶保存される（図４のステップＳ５３を参照）。
【００６４】
したがって、ステップＳ１で取り込んだ描画データＤ中の型式識別データと一致する型式識別データが条件パラメータデータベースに記憶保存されている場合は、その描画データＤのマーキン線７と同じマーキン線７の描画データＤを用いて、マーカ３の移動経路の最適化処理を過去に行っていることになる。
【００６５】
このため、過去にマーカ３の移動経路の最適化処理を行っているマーキン線７と同じマーキン線７の描画データＤを用いて、マーカ３の移動経路の最適化処理を行う場合には、過去に最適化処理を行った際と同じ内容の条件パラメータを用いて最適化処理を行うのが合理的である。
【００６６】
そこで、ステップＳ３の、ステップＳ１で取り込んだ描画データＤのマーキン線７が流用番船のものであるか否かの確認においては、ステップＳ１で取り込んだ描画データＤのマーキン線７が、過去にマーカ３の移動経路の最適化処理を行ったマーキン線７と同じであるか否かを確認する。そのために、ステップＳ３では、ステップＳ１で取り込んだ描画データＤ中の型式識別データと、条件パラメータデータベースに記憶保存されている型式識別データとを照合し、一致する型式識別データが記憶保存されているか否かを確認する。
【００６７】
そして、ステップＳ１で取り込んだ描画データのマーキン線７が、流用番船のものである（取り込んだ描画データＤ中の型式識別データと一致する型式識別データが条件パラメータデータベースに記憶保存されている）場合は（ステップＳ３でＹＥＳ）、過去に同じマーキン線７を描画する際のマーカ３の移動経路について最適化処理を行った際の条件パラメータの設定内容を取得する（ステップＳ５）。
【００６８】
詳しくは、ステップＳ１で取り込んだ描画データ中の型式識別データと一致する型式識別データと関連付けて条件パラメータデータベースに記憶保存されている条件パラメータの設定内容を取得する。
【００６９】
一方、ステップＳ１で取り込んだ描画データＤのマーキン線７が、流用番船のものでない（取り込んだ描画データＤ中の型式識別データと一致する型式識別データが条件パラメータデータベースに記憶保存されていない）場合は（ステップＳ３でＮＯ）、例えばハードディスクに記憶されている標準の条件パラメータの設定内容を取得する（ステップＳ７）。標準の条件パラメータの設定内容は、予め実験等によって適切な内容を決めておくことができる。
【００７０】
なお、条件パラメータは、以下の各項目から１又は複数を選択することができる。まず、アントコロニー最適化処理の収束条件に関する項目としては、巡回路探索の最大試行回数（最大反復回数）の上限値（回）、収束値（％）、及び、最大計算時間（分）がある。
【００７１】
最大試行回数の上限値とは、その回数まで巡回路探索を試行（請求項中の反復に相当）すると、解が収束していない場合でもアントコロニー最適化処理を終了する値である。収束値とは、１回の試行で構築した各巡回路の長さが、予め指定された割合の範囲内に全て収まっている場合に、解が収束したものとしてアントコロニー最適化処理を終了する値である。最大計算時間とは、その時間に累計試行時間が達すると、解が収束していない場合でもアントコロニー最適化処理を終了する値である。
【００７２】
次に、アントコロニー最適化処理において行う各種の計算条件に関する項目としては、フェロモンの蒸発率ρ、経路保持率Ｐｒａｔｅ、フェロモンの重さα、距離の重さβ、ランダム蟻ＡＲＳの率、及び、逆感度蟻ＡＩＳの率がある。
【００７３】
フェロモンの蒸発率ρは、フェロモン値τｉｊの更新の際に反映される、更新前のフェロモン値τｉｊが更新後のフェロモン値に及ぼす重み付けの係数である。フェロモン値τｉｊは、蟻の通過によりフェロモンが塗布された経路については増加し、それ以外の経路については減少する。
【００７４】
フェロモンの蒸発率ρの値を上げた場合は、更新に伴うフェロモンの蒸発が多くなるため、更新によってフェロモン値τｉｊが相対的に減少しやすくなる。これにより、蟻があまり通過しない経路のフェロモンが更新によって消えやすくなるが、巡回路の解が局所最適解に陥りやすくなる。一方、フェロモンの蒸発率ρの値を下げた場合は、更新に伴うフェロモンの蒸発が少なくなるため、更新によってフェロモン値τｉｊが相対的に減少しにくくなる。これにより、蟻があまり通過しない経路でもフェロモンが消えにくくなるが、巡回路の解が最適化されにくくなる。
【００７５】
経路保持率Ｐｒａｔｅは、１回の反復ｉで得られたすべての解Ｘｋ  （ｉ）のうち、巡回路長の短い方から順にフェロモンを塗布する解Ｘｋ  （ｉ）の割合を表す値である。
【００７６】
経路保持率Ｐｒａｔｅの値を上げた場合は、フェロモンを塗布する経路が相対的に増えるため、少し遠回りの経度であってもフェロモンが塗布される。これにより、局所最適解には陥りにくくなるが、巡回路の解が最適化されにくくなる。一方、経路保持率Ｐｒａｔｅの値を下げた場合は、フェロモンを塗布する経路が減るため、より短い経路に限ってフェロモンが塗布される。これにより、蟻がフェロモン値τｉｊの高い経路を選択しやすくなり、過去の経路情報が重視されやすくなるので、巡回路の解が収束しやすくなるが、局所最適解に陥りやすくなる。
【００７７】
フェロモンの重さαは、蟻が経路を選択する際に、次の都市までのフェロモン値τｉｊをどの程度重要視するかを決定する係数で、上述した（２）式の係数αがこれに相当する。
【００７８】
フェロモンの重さαの値を上げた場合は、フェロモン値τｉｊを重要視し、次の都市まで距離が離れていても、フェロモン値τｉｊが高ければその経路を選択しやすくなる。これにより、過去の経路情報を重視するので、巡回路の解が収束しやすくなるが、局所最適解に陥りやすくなる。一方、フェロモンの重さαの値を下げた場合は、フェロモン値τｉｊよりも距離を重視しやすくなり、フェロモン値τｉｊが高くても距離が離れていると、その経路を選択しにくくなる。これにより、フェロモン値τｉｊが多少低くても距離が短い経路を選択しやすくなるので、局所最適解には陥りにくくなるが、巡回路の解が最適化されにくくなる。
【００７９】
距離の重さβは、蟻が経路を選択する際に、次の都市までの距離をどの程度重要視するかを決定する係数で、上述した（２）式の係数βがこれに相当する。
【００８０】
距離の重さβの値を上げた場合は、次の都市までの距離が短い経路を重要視し、フェロモン値τｉｊが少なくても、次の都市までの距離が短ければその経路を選択しやすくなる。これにより、局所最適解には陥りにくくなるが、巡回路の解が最適化されにくくなる。一方、距離の重さβの値を下げた場合は、次の都市までの距離よりもフェロモン値τｉｊを重視しやすくなり、距離が近くてもフェロモン値τｉｊが低いと、その経路を選択しにくくなる。これにより、距離が多少遠くてもフェロモン値τｉｊが高い経路を選択しやすくなり、過去の経路情報を重視するので、巡回路の解が収束しやすくなるが、局所最適解に陥りやすくなる。
【００８１】
ランダム蟻ＡＲＳの率は、３種類の蟻に占めるランダム蟻ＡＲＳの割合を表す値である。ランダム蟻ＡＲＳの率を上げた場合は、経路をランダムに選択する蟻が増えるため、新しい経路を選択しやすくなる。これにより、局所最適解には陥りにくくなるが、巡回路の解が収束しにくくなる。一方、ランダム蟻ＡＲＳの率を下げた場合は、経路をランダムに選択する蟻が減るため、過去の経路情報を重視するようになる。これにより、巡回路の解が収束しやすくなるが、局所最適解に陥りやすくなる。
【００８２】
逆感度蟻ＡＩＳの率は、３種類の蟻に占める逆感度蟻ＡＩＳの割合を表す値である。逆感度蟻ＡＩＳの率を上げた場合は、フェロモン値τｉｊが少ない経路を選択する蟻が増えるため、新しい経路を選択しやすくなる。これにより、局所最適解には陥りにくくなるが、巡回路の解が収束しにくくなる。一方、逆感度蟻ＡＩＳの率を下げた場合は、フェロモン値τｉｊが少ない経路を選択する蟻が減るため、過去の経路情報を重視するようになる。これにより、巡回路の解が収束しやすくなるが、局所最適解に陥りやすくなる。
【００８３】
上述したように、いずれの項目を条件パラメータとしても、その内容を変更することは、巡回路の解の収束度、つまり、最短巡回路長（最短経路長）の解の収束度が変化するように変更することになる。
【００８４】
以上の項目から選択される条件パラメータをステップＳ５又はステップＳ７で取得したならば、取得した条件パラメータの設定内容を、デフォルトの条件パラメータとしてセットし（ステップＳ９）、次に、ステップＳ１で取り込んだ描画データＤから、マーキン線７を構成する線分の総数のデータを取得する（ステップＳ１１）。
【００８５】
続いて、取得した全線分のデータを解析して、一の線分の終点と他の線分の始点とが所定のしきい値以下の距離にある線分どうしを一の線分グループに属させて、一つのグループとして配列にまとめるグループ化処理を行う（ステップＳ１３）。
【００８６】
例えば、図６の説明図に示す例では、描画方向が互いに異なり終点と始点とが一致する各線分（Ａ１〜Ａ４、Ｂ１〜Ｂ４）がある場合に、ステップＳ１３において、それらをそれぞれ同一のグループに属させるようにする。
【００８７】
また、図７の説明図に示す例のように、タブシルやスプラインのように直線の連続で形成する曲線を描画する場合には、隣り合う一の直線の終点と他の直線の始点とが、所定のしきい値以下の至近距離に配置されることになる。したがって、ステップＳ１３においては、タブシルやスプラインのような曲線を構成する複数の直線を、全て一つのグループに属させるようにする。図７の例の場合には、タブシルの枠でそれぞれ囲まれた部分によりグループ１，２の２つのグループを構成する場合を示している。なお、タブシル枠内のグループ１，２の各表記はマーキン線７ではない。
【００８８】
さらに、図８の説明図に示す例のように、各部材９ａ，９ｂ，９ｃの部材名情報を示すテキストを描画する場合には、それぞれの部材９ａ，９ｂ，９ｃの部材名情報を示すテキストが、互いの終点と始点とが所定のしきい値以下の距離に接近するように配列されることになる。したがって、ステップＳ１３においては、例えば、間隔を詰めて配置される一群のテキストを構成する複数の線分を、全て一つのグループに属させるようにする。図８の例の場合には、太枠でそれぞれ囲った部分によりグループ１〜５の５つのグループを構成する場合を示している。なお、太枠そのものと太枠脇のグループ１〜５の表記とは、いずれもマーキン線７ではない。
【００８９】
そして、ステップＳ１３で配列にまとめたグループの総数と、グループ番号をそれぞれ付与した各グループの配列内容とを取得する（ステップＳ１５）。次に、各グループの始点と終点とを別々の都市（請求項中の地点に相当）として、それらの始点及び終点を都市の配列に取得する。また、ステップＳ１３でグループ化の対象とならなかった他の線分についても、始点と終点とを別々の都市（請求項中の地点に相当）として、それらの始点及び終点を都市の配列に取得する（ステップＳ１７）。なお、同じグループ又は同じ線分の始点と終点は、後述するステップＳ２３で都市番号を取得する際に、ペアとしての関係が分かる都市番号がセットされるように配列する。
【００９０】
続いて、ステップＳ１５で都市番号をセットした各都市間の距離を全て計算し、計算した値を各都市間の距離の配列に保持する（ステップＳ１９）。
【００９１】
次に、アントコロニー最適化処理を行うに当たっての初期化処理を行う（ステップＳ２１）。この初期化処理としては、例えば、各都市間を結ぶ経路に対するフェロモン値τｉｊの初期化や、反復回数のカウンタｉ及び最良解Ｘ＾の巡回路長ｆ＾の連続非更新回数のカウンタＩｃのゼロリセット（ｉ：＝０，Ｉｃ：＝０）、巡回路長ｆ＾の初期化等がある。
【００９２】
フェロモン値τｉｊの初期値は、例えば、下限値τｍｉｎ  とすることができる。あるいは、後述するステップＳ２５で取得する蟻（請求項中のエージェントに相当）の総数ｍを、Ｇｒｅｅｄｙ法によって生成された巡回路の平均巡回路長で除した値を、フェロモン値τｉｊの初期値とすることもできる。巡回路長ｆ＾の初期値は、十分大きな値に設定する。
【００９３】
続いて、各都市の都市番号をランダムに取得し（ステップＳ２３）、都市数から「１」を差し引いた数を蟻（エージェント）の総数として取得する（ステップＳ２５）。そして、取得した数の蟻を、同じ都市に複数重複して配置されないようにランダムに配置する（ステップＳ２７）。なお、ここでは１巡目の反復に用いる標準的な蟻ＡＮＳのみを各都市Ｎに配置するものとする。
【００９４】
次に、上述した（２）式によって定義される、次の都市ｊを選択する確率ｐｋｉｊ  にしたがって、各都市に配置した標準的な蟻ＡＮＳに他の都市を巡回させ、選択した経路にそれぞれフェロモンを塗布（追加）させていく（ステップＳ２９）。そして、全ての蟻ＡＮＳに全ての都市を巡回させた後（ステップＳ３１）、ステップＳ２９で塗布したフェロモンを加えた値にフェロモン値τｉｊを更新する（ステップＳ３３）。このフェロモン値τｉｊの更新は、上述した（５），（６）式にしたがって行う。
【００９５】
続いて、ステップＳ５又はステップＳ７で取得した条件パラメータと、都市数とにしたがって、標準蟻ＡＮＳ、逆感度蟻ＡＩＳ、及び、ランダム蟻ＡＲＳの数をそれぞれ決定する（ステップＳ３５）。
【００９６】
次に、２巡目以降の反復ｉに移り、図４に示すように、上述した（２），（３）式によって定義される、次の都市ｊを選択する確率ｐｋｉｊ  にしたがって、各都市に配置した標準蟻ＡＮＳ及び逆感度蟻ＡＩＳに、次の都市への経路を選択させ、選択した経路にそれぞれフェロモンを塗布（追加）させていく（ステップＳ３７、ステップＳ４１）。同様に、ランダム蟻ＡＲＳにも次の都市への経路をランダムに選択させ、選択した経路にそれぞれフェロモンを塗布（追加）させていく（ステップＳ３９）。そして、ステップＳ３７〜ステップＳ４１で塗布したフェロモンを加えた値にフェロモン値τｉｊを更新する（ステップＳ４３）。このフェロモン値τｉｊの更新は、上述したＰＲＳの定義によるランキングリスト作成方法で作成したリストＬに基づいて、（５），（６）式にしたがって行う。
【００９７】
次に、ステップＳ３７〜４１による標準蟻ＡＮＳ、逆感度蟻ＡＩＳ、及び、ランダム蟻ＡＲＳの経路選択の結果である巡回路の解をそれぞれ求め、その中の巡回路長が一番短い巡回路の解Ｘｋ  を、今回の反復ｉにおける最良解ｆ（Ｘｂｓ（ｉ））として、今までの各反復によって得られた解Ｘｋ  の中の最良解Ｘ＾と比較する。そして、巡回路長の短い方の解（最良解ｆ（Ｘｂｓ（ｉ））又は最良解Ｘ＾）を、その解の巡回路長と共に、例えばハードディスクドライブに記憶保持する（ステップＳ４５）。
【００９８】
次に、ステップＳ４５で記憶保持した最良解Ｘ＾が局所最適解に陥っているか否かを確認する（ステップＳ４７）。この確認は、例えば、ステップＳ４５の手順において記憶保持した最良解Ｘ＾が、今回の反復ｉにおける最良解ｆ（Ｘｂｓ（ｉ））にＩｍａｘ  回連続して更新されなかったか否かによって行うことができる。そして、局所最適解に陥っている場合は（ステップＳ４７でＹＥＳ）、ステップＳ９でセットした条件パラメータの値を変更する（ステップＳ４９）。
【００９９】
続いて、アントコロニー最適化処理の収束条件又は終了条件を満たしているか（条件が成立しているか）否かを確認する（ステップＳ５１）。満たしていない（成立していない）場合は（ステップＳ５１でＮＯ）、ステップＳ３７にリターンして次順の反復に移行し、満たしている（成立している）場合は（ステップＳ５１でＹＥＳ）、ステップＳ１で取り込んだ描画データＤ中の型式識別データと関連付けて、現在の条件パラメータの値を条件パラメータデータベース（ＤＢ）に記憶保存する（ステップＳ５３）。
【０１００】
次に、ステップＳ４５で記憶保持した最良解Ｘ＾の巡回路（巡回経路）を、原点からスタートするようにソートし（ステップＳ５５）、巡回経路にしたがって、マーカ３の移動経路（マーキン経路）を作成する（ステップＳ５７）。そして、作成したマーカ３の移動経路を含むマーキン線７の印字データを（例えば、マーカ３を不図示のカッタに取り替えたＮＣ切断装置に）出力した後（ステップＳ５９）、一連の手順を終了する。
【０１０１】
以上の説明からも明らかなように、本実施形態では、図３のフローチャートにおけるステップＳ３が、請求項中の型式照合ステップに対応する手順となっている。また、本実施形態では、図３中のステップＳ５乃至ステップＳ９が、請求項中のパラメータ設定ステップに対応する手順となっている。さらに、本実施形態では、図３中のステップＳ１７が、請求項中の地点定義ステップに対応する手順となっている。
【０１０２】
また、本実施形態では、図４のフローチャートにおけるステップＳ３７乃至ステップＳ４１が、請求項中の経路探索ステップに対応する手順となっている。さらに、本実施形態では、図４中のステップＳ４３が、請求項中のフェロモン値更新ステップに対応する手順となっている。そして、本実施形態では、ステップＳ３７乃至ステップＳ４３が、請求項中のアントコロニー最適化処理ステップに対応する手順となっている。
【０１０３】
さらに、本実施形態では、図４中のステップＳ４５が、請求項中の最短解保存ステップに対応する手順となっている。また、本実施形態では、図４中のステップＳ４９が、請求項中のパラメータ変更ステップに対応する手順となっている。さらに、本実施形態では、図４中のステップＳ５３が、請求項中のパラメータ保存ステップに対応する手順となっている。また、本実施形態では、図４中のステップＳ５９が、請求項中の出力ステップに対応する手順となっている。
【０１０４】
以上に説明した手順でアントコロニー最適化処理によるマーカ３の移動経路の最適化を行う本実施形態によれば、最良解Ｘ＾が局所最適解に陥っている場合に、アントコロニー最適化処理を行う際の条件を定義する条件パラメータを、最短巡回路長の解の収束度が変化するように変更するようにした。
【０１０５】
このため、局所最適解に陥った状態を条件パラメータの変更により解消して、局所最適解よりも巡回路長が短い最良解Ｘ＾があればその最良解Ｘ＾がアントコロニー最適化処理によって得られやすくすることができる。これにより、アントコロニー最適化手法を用いて鋼板５毎に適切な最短経路長のマーカ３の移動経路を求めることができる。
【０１０６】
これにより、図９の説明図に示すように、マーキン線７を描画する際の最短巡回路長となるマーカ３の移動経路１１を適切に求めることができる。即ち、図１０の説明図に示すように、従来の汎用的なソートプログラムによってマーカ３の移動経路１１ａを求める場合に比べて、移動距離が短く効率的な移動経路１１（図９参照）を求めることができる。
【０１０７】
なお、本実施形態では、ＮＣ印刷装置１から取り込んだ描画データＤのマーキン線７が流用番船のものである場合に、同じ番船のマーキン線７について過去にマーカ３の移動経路の最適化処理を行った際の条件パラメータでアントコロニー最適化処理を行うようにした。そのための構成は省略しても良いが、本実施形態のように、そのための構成を設ければ、以下のような利点がある。
【０１０８】
即ち、過去にマーカ３の移動経路の最適化処理を行ったのと同じ番船のマーキン線７について、マーカ３の移動経路の最適化処理を行う場合は、過去のマーキン線７に関するマーカ３の移動経路の最適化処理が収束又は終了したときの条件パラメータ、つまり、反復により得られる解が局所最適解に陥っていないときの条件パラメータで、今回のマーキン線７に関するマーカ３の移動経路の最適化処理を行えるようになる。
【０１０９】
これにより、流用番船のマーキン線７に関するマーカ３の移動経路の最適化処理を行う際に、最短巡回路長の解を効率よく得るのに適した内容に条件パラメータを設定して、マーカ３の移動経路の最適化処理を効率よく行うことができる。
【０１１０】
また、本実施形態では、一の線分の終点と他の線分の始点とが所定のしきい値以下の距離にある線分どうしを一の線分グループに属させ、都市Ｎの数を減らすことでアントコロニー最適化処理の規模を小さくすることで、処理時間の短縮化を図れるようにした。
【０１１１】
そのようにするための構成は省略しても良いが、本実施形態のように、そのための構成を設ければ、最短巡回路長の解を求めるための都市Ｎ（経路）の座標数を減らし、分散コンピューティング等を利用して処理能力を高めなくても、汎用コンピュータレベルですむ少ない処理で最適化処理を行うことができる。
【符号の説明】
【０１１２】
１  ＮＣ印刷装置
３  マーカ
５  鋼板
５ａ  マーキン面
７  マーキン線
９ａ，９ｂ，９ｃ  部材
１１  移動経路
１１ａ  移動経路
【図１】
0005520763.tif 000007
【図２】
0005520763.tif 000008
【図３】
0005520763.tif 000009
【図４】
0005520763.tif 000010
【図５】
0005520763.tif 000011
【図６】
0005520763.tif 000012
【図７】
0005520763.tif 000013
【図８】
0005520763.tif 000014
【図９】
0005520763.tif 000015
【図１０】
0005520763.tif 000016