(57)【要約】【課題】複数の施設の各々をある地理的範囲においてどこに配置すれば有効であるかを実用的な時間内に求める。【解決手段】配置立案装置は、所要の施設の数に基づいた配列を持ち施設の配置の複数の候補をそれぞれ示す複数の遺伝コードに対して、評価、選択、交叉、突然変異を含む遺伝的アルゴリズムを適用する。遺伝コード評価部３は、遺伝コードの各々が示す施設の配置から、施設による全サービスカバー面積に対応する指標を求め、この指標を遺伝的アルゴリズムの評価値として使用する。【選択図】        図１
2004272455.tif 000002
【特許請求の範囲】
【請求項１】
ある地理的範囲において複数の施設の配置を立案する配置立案装置において、
所要の施設の数に基づいた配列を持ち遺伝的操作の母集団となり上記施設の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、
入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、
上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、
上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、
上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、
遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記施設の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、
上記評価部は、遺伝コードの各々が示す施設の配置から上記施設による全サービスカバー面積に対応する指標を上記評価値として算出することを特徴とする配置立案装置。
【請求項２】
ある地理的範囲において複数の施設の配置を立案する配置立案装置において、
所要の施設の数に基づいた配列を持ち遺伝的操作の母集団となり上記施設の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、
入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、
上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、
上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、
上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、
遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記施設の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、
上記評価部は、各遺伝コードが示す個々の施設の位置と既知の複数の地点との間の距離を算出し、各遺伝コードについてのこれらの距離の総和に対応する指標を上記評価値として算出することを特徴とする配置立案装置。
【請求項３】
選択部は遺伝コードの評価値そのものをしきい値と比較し、比較結果に応じて遺伝コードを選択することを特徴とする請求項１または請求項２記載の配置立案装置。
【請求項４】
評価部または選択部は遺伝コードの評価値に応じて予め割り振られた確率を評価値に乗算し、選択部はこの計算結果をしきい値と比較し、比較結果に応じて遺伝コードを選択することを特徴とする請求項１または請求項２記載の配置立案装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ある地理的範囲において複数の施設の配置を立案する配置立案装置に関する。
【０００２】
【従来の技術】
遺伝的アルゴリズムは、生物が環境に適応して進化してゆく遺伝過程を工学的に模倣した学習アルゴリズムであり、現実の事象に適応した最適解または準最適解を短時間で求めるために利用されている。例えば、集積回路内の素子間の接続関係等の制約条件の下、素子の実装面積がより小さくなるように集積回路に素子を配置する目的で遺伝的アルゴリズムを使用する素子配置方法が提案されている（例えば特許文献１）。
【０００３】
【特許文献１】
特開平７−８６４１１号公報
【０００４】
【発明が解決しようとする課題】
しかし、例えば店舗、軍事施設、携帯電話基地局等の複数の施設をある地理的範囲において有効に配置するための遺伝的アルゴリズムは開発されていない。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、複数の施設の各々をある地理的範囲においてどこに配置すれば有効であるかを実用的な時間内に求める配置立案装置を得ることを目的とする。
【０００６】
【課題を解決するための手段】
この発明に係る配置立案装置は、ある地理的範囲において複数の施設の配置を立案する配置立案装置において、所要の施設の数に基づいた配列を持ち遺伝的操作の母集団となり上記施設の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記施設の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、上記評価部は、遺伝コードの各々が示す施設の配置から上記施設による全サービスカバー面積に対応する指標を上記評価値として算出するものである。
【０００７】
この発明に係る配置立案装置において、上記評価部は、各遺伝コードが示す個々の施設の位置と既知の複数の地点との間の距離を算出し、各遺伝コードについてのこれらの距離の総和に対応する指標を上記評価値として算出するものでもよい。
【０００８】
【発明の実施の形態】
以下、この発明に係る様々な実施の形態を説明する。
実施の形態１．
図１は、この発明に係る配置立案装置の構成を示すブロック図である。図示のように、この配置立案装置は、入力部１、初期コード化部２、遺伝コード評価部（終了判定部）３、遺伝的操作部（選択部、交叉処理部、突然変異処理部）４および出力部５を備える。初期コード化部２、遺伝コード評価部３および遺伝的操作部４は、プログラムに従ってコンピュータの中央演算処理装置が行う動作のモジュールを表しており、実際には一体として中央演算処理装置を構成する。
【０００９】
入力部１には、所要の施設の数、および施設を配置する対象となる地理的範囲の総面積を操作者が入力する。所要の施設の数は、中央演算処理装置の初期コード化部２に通知され、総面積は遺伝コード評価部３に供給される。地理的範囲の形状が一定の場合（例えば円や矩形）には、面積を算出するために必要な情報（例えば半径や辺の長さ）を面積に代えて入力部１に入力し、中央演算処理装置に面積を算出させてもよい。
【００１０】
初期コード化部２は、入力部１から所要の施設の数を通知されると、遺伝的操作の母集団を構成する第一世代の遺伝コードである複数の初期の遺伝コードをランダムに生成する。これらの初期の遺伝コードの各々は、次に図２および図３を参照しながら説明するように、所要の施設の数に基づいた配列を持ち、所要の施設の配置の候補を示す。
【００１１】
図２は、初期コード化部２で生成された初期の遺伝コードの一例を示す模式図である。遺伝コードは様々な法則に基づいて配列されてよく、具体的な配列の法則は配置立案装置の設計に依存するが、図示の簡略な例では遺伝コードは三つの所要の施設の配置を６桁の配列で表す。第１桁および第２桁（０，０）が第１の施設のＸ座標およびＹ座標をそれぞれ示し、第３桁および第４桁（１，１）が第２の施設のＸ座標およびＹ座標をそれぞれ示し、第５桁および第６桁（２，２）が第３の施設のＸ座標およびＹ座標をそれぞれ示す。
【００１２】
図２の遺伝コードに対応する施設の配置候補を平面上に示すのが図３である。図３に示すように、この配置候補では、黒丸で表された第１の施設は位置（０，０）に配置され、黒三角で表された第２の施設は位置（１，１）に配置され、黒四角で表された第３の施設は位置（２，２）に配置されている。
【００１３】
初期コード化部２は、配置立案装置の設計に依存する数の初期の遺伝コードを例えば乱数を用いてランダムに作成する。これらの初期の遺伝コードはそれぞれ異なる配置候補を示すが、配置立案装置の設計に依存する同じ法則に基づく配列を持つ。また、初期の遺伝コードを後述の遺伝的操作で改変した後の世代の遺伝コードも同様の法則で所要の施設の配置の候補を表すので、生成された遺伝コードから同様の法則で配置計画案を解釈することができる。
【００１４】
遺伝コード評価部３は、初期コード化部２または遺伝的操作部４から入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る。遺伝的操作部４には、遺伝コード評価部３から遺伝コードと評価値が入力され、各々の遺伝コードに遺伝的操作を施す。
【００１５】
図４は、遺伝的操作部４の動作を示すフローチャートである。遺伝コードと評価値が入力されると、ステップＳＴ１で遺伝的操作部４は選択部として機能し、評価値の各々に基づいて適切な遺伝コードを選択する。次にステップＳＴ２で遺伝的操作部４は交叉処理部として機能し、選択された遺伝コードの各々に交叉処理を施す。さらにステップＳＴ３で遺伝的操作部４は突然変異処理部として機能し、交叉が施された遺伝コードの一部に突然変異処理を施して、突然変異処理後の遺伝コードの各々を遺伝コード評価部３に供給する。
【００１６】
遺伝コード評価部３は、終了判定部としても機能し、遺伝的操作が終了条件を満たした場合に、突然変異処理後の遺伝コードの少なくとも一つを施設の配置候補の最適解または準最適解である最終遺伝コードとして出力部５に出力し、遺伝的操作が終了条件を満たさない場合に、突然変異処理後の遺伝コードの各々を選択部としての遺伝的操作部４に供給する。従って、遺伝的操作が終了条件に達するまで、評価、選択、交叉処理および突然変異処理から構成されるサイクルが繰り返される。
【００１７】
図５はこの配置立案装置の処理を視覚で理解できるように描写した模式図である。まず、初期コード化部２では、初期の四つの遺伝コード（１，１，１，２，２，２）、（１，１，１，１，２，２）、（１，２，２，２，３，３）、（２，２，２，２，３，３）を生成する。
【００１８】
遺伝コード評価部３は、施設を配置する対象となる地理的範囲の総面積と全サービスカバー面積との比率を評価値として算出する。すなわち、評価値Ｅは評価関数としての式（１）に従って算出される。
Ｅ＝ＡＣ／ＡＴ                            ・・・（１）
ここでＡＣは全施設による全サービスカバー面積であり、ＡＴは施設を配置する対象となる地理的範囲の総面積である。総面積ＡＴは、入力部１を介して遺伝コード評価部３に与えられてもよいし、対象地理的範囲の形状が一定の場合には総面積ＡＴを算出するために必要な情報（例えば半径や辺の長さ）が入力部１から遺伝コード評価部３に与えられて遺伝コード評価部３で算出してもよい。
【００１９】
また、全施設による全サービスカバー面積ＡＣは、初期コード化部２から入力された初期の遺伝コードの各々が示す施設の配置から遺伝コード評価部３によって算出することができる。具体的には、各施設のサービス領域の面積および形状が既知であれば、遺伝コードが示す施設の配置から重なり部分の面積を推定し、全施設の面積の合計から重なり部分面積を減算することで、全サービスカバー面積ＡＣを得ることができる。例えば施設が店舗、軍事施設、携帯電話基地局である場合には、各施設のサービス領域の面積および形状は既知である。すなわち店舗については消費者が一定時間以内に歩いて店舗に到着する範囲、軍事施設についてはレーダの電波が有効に届く範囲、携帯電話基地局については基地局から電波が届く範囲が各施設のサービス領域である。従って、各施設のサービス領域は、同一の半径を持つ円とみなすことができるので、サービス領域の面積および形状は既知であり、施設の配置から重なり部分の面積を推定すれば全サービスカバー面積ＡＣを得ることができる。
【００２０】
上記のようにして、遺伝コード評価部３は評価関数を適用して、図５に示すように入力された遺伝コードの各々の評価値を得る。例えば、遺伝コード（１，１，１，２，２，２）は、第１の施設が位置（１，１）に配置され、第２の施設が位置（１，２）に配置され、第３の施設が位置（２，２）に配置されることを表しており、この評価値Ｅは０．３４３である。
【００２１】
遺伝的操作部４での選択工程では、これらの遺伝コードの評価値Ｅのうち二以上の最も高い評価値を選択し、これらの最も高い評価値に対応する遺伝コードを交叉処理工程に供する。図６はこの選択工程の具体的手法を示す。この選択工程で選択すべき評価値の個数はしきい値として中央演算処理装置に予め記憶されている。例えば、このしきい値は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００２２】
図６に例示する選択工程では、まず遺伝コード評価部３で算出された評価値群を順位付けする（ステップＳＴ１０）。ステップＳＴ１０では、高い評価値ほど、高い順位すなわち若い順位序数を持つように、各評価値に順位序数が割り振られる。例えば最高の評価値には１位、次点の評価値には２位というようにである。
【００２３】
次に、これらの評価値群のうち一つの評価値を取り出し（ステップＳＴ１１）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ１２）。このループカウンタＩの初期値はゼロである。
【００２４】
さらに、取り出した評価値Ｅ（Ｉ）の順位序数を、上位何番まで選択するかを示すしきい値と比較する（ステップＳＴ１３）。そして、しきい値より大きい順位序数の場合にはこの評価値Ｅ（Ｉ）を選択しないが、しきい値以下の順位序数を持つ場合にはこの評価値Ｅ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ１４）。
【００２５】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ１５）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ１１に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、しきい値分の個数の高い評価値を選択する。以上のように、しきい値までの順位序数を持つ二以上の評価値ひいては評価値に対応する遺伝コードを選択することにより、より良い遺伝コードが着実に生成される。
【００２６】
遺伝的操作部４での交叉処理工程では、図５に示すような一様交叉を行ってもよい。すなわち、選択工程で選択された遺伝コード中の数値を部分的にランダムに交換することにより、交叉が施された所定の数の遺伝コードを得てもよい。
【００２７】
あるいは、遺伝的操作部４での交叉処理工程では、図７に示すような一点交叉を行ってもよい。すなわち、選択工程で選択された遺伝コード中の交叉点（ある桁）以下の数値を互いに交換することにより、交叉が施された遺伝コードを得てもよい。このように一点交叉を行うことにより、評価値の高い遺伝コードの一部分を引き継いだ、より評価値の高い遺伝コードの生成を迅速に可能にすることができる。
【００２８】
遺伝的操作部４での突然変異処理工程では、交叉処理後の遺伝コードから突然変異処理を実行する確率に従って一部の遺伝コードをランダムに取り出し、取り出された遺伝コード中の一部を図５および図８に示すように任意に変更する。突然変異処理を実行する確率は、中央演算処理装置に予め記憶されている。例えば、この確率は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。一つの遺伝コード中の突然変異処理で変更する部分はランダムであり、どの数に変更するかもランダムである。このように、突然変異を行うことで局所解から回避するという効果がある。
【００２９】
突然変異処理工程では、突然変異処理を実行する確率に従って一部の遺伝コードに突然変異処理を施す。従って、図５に示すように、突然変異処理後の遺伝コードには、交叉処理工程後の遺伝コードと同じものと、実際に変異させられたものが混在する。
【００３０】
このようにして遺伝的操作部４により、選択、交叉および突然変異を施された次の世代の遺伝コードが生成される。次の世代の遺伝コードの各々は、終了判定部としての遺伝コード評価部３に供給され、遺伝的操作が終了条件に達するまで、評価、選択、交叉処理および突然変異処理から構成されるサイクルが繰り返される。すなわち、遺伝コード評価部３は、遺伝的操作後（突然変異処理後）の遺伝コードの各々に上記と同様に式（１）の評価関数を適用して遺伝コードの各々の評価値を得て、遺伝的操作が終了条件を満たさない場合に、遺伝的操作後の遺伝コードの各々を選択部としての遺伝的操作部４に供給する。遺伝的操作部４は高い評価値を持つ二以上の遺伝コードを選択して、選択された遺伝コードの各々に交叉処理を施し、交叉が施された遺伝コードの一部に突然変異処理を施して、突然変異処理後の遺伝コードの各々を遺伝コード評価部３に供給する。
【００３１】
この実施の形態において、遺伝的操作の終了条件は、遺伝コード評価部３が算出した評価値の一つまたは全てがあるしきい値を上回ったこととしてもよい。あるいは、遺伝的操作の終了条件は、上記の評価、選択、交叉処理および突然変異処理から構成されるサイクルが規定の回数まで達したこと、すなわち規定の世代の遺伝コードが生成されたこととしてもよいし、初期の遺伝コードの生成からカウントを開始した経過時間が規定の許容時間を上回ったこととしてもよい。この終了条件が満たされると、遺伝コード評価部３は、突然変異処理後の遺伝コードのうち、少なくとも一つの最も評価値が高いものを施設の配置候補の最適解または準最適解である最終遺伝コードとして出力部５に出力する。出力部５は、ディスプレイに最終遺伝コードを表示させる表示制御部でもよいし、プリンタに最終遺伝コードを印刷させる印刷制御部でもよい。
【００３２】
以上のようにこの実施の形態１によれば、遺伝的アルゴリズムを適用し、施設が配置される地理的範囲の総面積と、遺伝コードの各々が示す施設の配置から求められる施設による全サービスカバー面積との比率を遺伝的アルゴリズムの評価値として使用することによって、複数の施設の各々をある地理的範囲においてどこに配置すれば有効であるか（すなわち全サービスカバー面積を広く確保できるか）を実用的な時間内に求めることが可能である。
【００３３】
上記の実施の形態１では、所要の各施設のサービス領域の面積および形状が既知であるが、この発明はこのような形態に限定されず、各施設のサービス領域の面積および形状が不定である場合に最適解または準最適解を求めるような形態もこの発明の範囲にある。例えば、所要の施設の各サービス領域の面積および形状の少なくとも一方が不定である場合には、操作者は、各サービス領域の面積および形状を入力部１に入力してもよい。また、操作者は各サービス領域の面積に代えて面積を算出するのに必要な情報を入力部１に入力し、中央演算処理装置に各サービス領域の面積を算出させてもよい。これによりサービス領域の面積と形状が中央演算処理装置に既知となり、サービス領域の面積と形状および遺伝コードが示す施設の配置から重なり部分の面積を推定すれば全サービスカバー面積ＡＣを得ることができる。
【００３４】
また、上記の実施の形態１では、評価値Ｅは式（１）に従って算出される。ただし、評価値Ｅの逆数を評価値として使用してもよい。すなわち、施設を配置する対象となる地理的範囲の総面積を全施設による全サービスカバー面積で除算した商（１／Ｅ）を評価値として算出してもよい。このような場合には、選択工程では、最も低い二以上の評価値に対応する遺伝コードが選択される。また、このような場合には、終了条件としては、評価値の一つまたは全てがあるしきい値を下回ったこととしてもよい。
【００３５】
また、評価値Ｅは以下の式（２）に従って算出してもよい。
Ｅ＝ＡＣ                                  ・・・（２）
すなわち、全施設による全サービスカバー面積ＡＣを、施設を配置する対象となる地理的範囲の総面積ＡＴで除算せずに、そのまま評価値Ｅとしてもよい。総面積ＡＴは一定なので、式（２）でも良好な結果を得ることができる。
【００３６】
実施の形態２．
次に上記の遺伝的操作部４で行う選択工程の変形例をこの発明の実施の形態２に係る選択工程として説明する。実施の形態２で、配置立案装置の構成要素および選択工程以外の工程は、実施の形態１と同じでよい。
【００３７】
図９は、実施の形態２に係る選択工程の具体的手法を示す。この選択工程では、あるしきい値以上の評価値およびこのような評価値を持つ遺伝コードを選択する。このしきい値は中央演算処理装置に予め記憶されている。例えば、このしきい値は予めパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００３８】
図９に示す選択工程では、まず遺伝コード評価部３で算出された評価値群のうち一つの評価値を取り出し（ステップＳＴ２０）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ２１）。このループカウンタＩの初期値はゼロである。
【００３９】
さらに、取り出した評価値Ｅ（Ｉ）そのものを上記のしきい値と比較する（ステップＳＴ２２）。そして、しきい値より小さい場合にはこの評価値Ｅ（Ｉ）を選択しないが、しきい値以上の場合にはこの評価値Ｅ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ２３）。
【００４０】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ２４）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ２０に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、しきい値以上の評価値を選択する。以上のように、しきい値以上の評価値ひいては評価値に対応する遺伝コードを選択することにより、より良い遺伝コードが着実に生成される。
【００４１】
なお、評価値Ｅの逆数（１／Ｅ）を評価値として使用する場合には、選択工程では、しきい値以下の評価値に対応する遺伝コードが選択される。
【００４２】
実施の形態３．
次に上記の遺伝的操作部４で行う選択工程の他の変形例をこの発明の実施の形態３に係る選択工程として説明する。実施の形態３で、配置立案装置の構成要素および選択工程以外の工程は、実施の形態１と同じでよい。
【００４３】
図１０は、実施の形態３に係る選択工程の具体的手法を示す。この選択工程では、評価値に応じて予め割り振られた確率を評価値に乗算して得られた副次的評価値があるしきい値以上であれば、その評価値およびこれに対応する遺伝コードを選択する。確率およびしきい値は中央演算処理装置にあらかじめ記憶されている。例えば、確率およびしきい値はあらかじめパラメータファイルに設定しておき、システム起動時に遺伝的操作部４がこれを参照するようにしてもよい。
【００４４】
図１０に示す選択工程では、まず遺伝コード評価部３で算出された評価値群のうち一つの評価値を取り出し（ステップＳＴ３０）、ループカウンタＩをＩ＋１に設定する（ステップＳＴ３１）。このループカウンタＩの初期値はゼロである。
【００４５】
さらに、取り出した評価値Ｅ（Ｉ）に基づいてパラメータファイルから確率Ｏ（Ｉ）を読み出し（ステップＳＴ３２）、評価値Ｅ（Ｉ）に確率Ｏ（Ｉ）を乗算することにより副次的評価値Ａ（Ｉ）を算出する（ステップＳＴ３３）。確率Ｏ（Ｉ）は、評価値の大きさに応じて予め割り振られている。例えば、評価値が０以上０．１未満であれば確率は０．１、評価値が０．１以上０．２未満であれば確率は０．２というように、評価値Ｅが高いほど高い確率を予め割り振ってある。
【００４６】
次に副次的評価値Ａ（Ｉ）を上記のしきい値と比較する（ステップＳＴ３４）。そして、副次的評価値Ａ（Ｉ）がしきい値より小さい場合にはこの評価値Ｅ（Ｉ）を選択しないが、副次的評価値Ａ（Ｉ）がしきい値以上の場合にはこの評価値Ｅ（Ｉ）ひいてはこれに対応する遺伝コードを選択する（ステップＳＴ３５）。
【００４７】
この後、ループカウンタＩを全評価値の数Ｍと比較する（ステップＳＴ３６）。ここでＩ＝Ｍであれば選択処理を終了し、Ｉ＜Ｍであれば、別の評価値を選択すべきか否か判断するために処理はステップＳＴ３０に戻る。このようにして全評価値について選択すべきか否かの判断の試行を行い、副次的評価値Ａ（Ｉ）がしきい値以上の評価値Ｅ（Ｉ）を選択する。
【００４８】
生物の遺伝過程において個体の環境への適合度が高い場合には、自然淘汰される確率が低くなる（換言すれば生き残る確率が高くなる）と考えられる。従って、個体の環境への適合度に相当する遺伝コードの評価値Ｅ（Ｉ）に、個体が生き残る確率に相当する確率Ｏ（Ｉ）を乗算することにより得られた副次的評価値Ａ（Ｉ）は、元の評価値Ｅ（Ｉ）よりもさらに、選択されるべき適合度を示す指標として的確であると考えられる。遺伝コードの評価値Ｅ（Ｉ）の相違は、確率Ｏ（Ｉ）を乗じることにより、副次的評価値Ａ（Ｉ）の相違として拡大される。以上のように、遺伝コードの評価値Ｅ（Ｉ）に応じて予め割り振られた確率Ｏ（Ｉ）を乗算して副次的評価値Ａ（Ｉ）を得ることで、上述した他の実施の形態による配置立案装置よりも、さらにより良い遺伝コードが着実に生成されるという効果がある。
【００４９】
なお、副次的評価値Ａ（Ｉ）の算出は、中央演算処理装置が行う動作のモジュールのうち、遺伝コード評価部３に相当するモジュールが行ってもよいし、選択部としての遺伝的操作部４に相当するモジュールが行ってもよい。
【００５０】
また、評価値Ｅの逆数（１／Ｅ）を評価値として使用する場合には、評価値１／Ｅが低いほど、低い確率を予め割り振っておき、選択工程では、しきい値以下の副次的評価値Ａ（Ｉ）に対応する遺伝コードが選択される。
【００５１】
実施の形態４．
次に上記の遺伝コード評価部３で行う評価工程の変形例をこの発明の実施の形態４に係る評価工程として説明する。実施の形態４で、配置立案装置の構成要素および評価工程以外の工程は、実施の形態１と同じか実質的に同じでよい。
【００５２】
この実施の形態４では、遺伝コード評価部３は、上記の式（１）に代えて、評価関数としての式（３）に従って評価値Ｅ２を算出する。
【数１】
2004272455.tif 000003
【００５３】
ここで添え字ｉは個々の施設に与えられる通し番号であり、添え字ｊは個々の既知の地点に与えられる通し番号であり、ｄｉｊは、各遺伝コードが示す個々の施設ｉの位置と既知の複数の地点ｊとの間の距離である。数ｍは所要の施設の数であり、従って、０＜ｉ≦ｍである。数ｎは既知の地点の数であり、従って、０＜ｊ≦ｎである。既知の地点の位置は中央演算処理装置にあらかじめ記憶されている。例えば、既知の地点の位置はあらかじめパラメータファイルに設定しておき、システム起動時に遺伝コード評価部３がこれらを参照するようにしてもよい
。
【００５４】
このように、式（３）の評価関数は、各遺伝コードが示す個々の施設の位置と既知の複数の地点との間の距離ｄｉｊを算出し、各遺伝コードについてのこれらの距離ｄｉｊの総和を算出することを表す。そして、評価値Ｅ２は、既知の地点と施設の距離を示す指標となる。すなわち評価値Ｅ２が大きいほど既知の地点と施設の距離が長くて不合理であり、評価値Ｅ２が小さいほど既知の地点と施設の距離が短くて好ましいことを示す。
【００５５】
例えば、店舗の配置計画では、多くの消費者の家から一定距離範囲内にいずれかの施設すなわち店舗があるようにしたい。これらの消費者の個々の家を既知の地点として式（３）に従って評価値Ｅ２を算出することにより、消費者の家と施設の距離を示す指標が得られる。すなわち評価値Ｅ２が小さいほど好ましい。
【００５６】
選択工程では、遺伝コードの評価値Ｅ２のうち二以上の最も低い評価値Ｅ２または評価値Ｅ２の逆数（１／Ｅ２）のうち最も高いものを選択し、これらの評価値に対応する遺伝コードを交叉処理工程に供してもよい。また、評価値Ｅ２またはその逆数（１／Ｅ２）をしきい値と比較し、比較結果に応じて遺伝コードを選択してもよい。さらには、評価値Ｅ２に応じて予め割り振られた確率Ｏを評価値Ｅ２またはその逆数（１／Ｅ２）に乗算して得た副次的評価値Ａ（Ｉ）をしきい値と比較し、比較結果に応じて遺伝コードを選択してもよい。つまり、この実施の形態４での選択工程は、実施の形態１から実施の形態３のいずれかの選択工程を変形することにより達成されうる。これらの選択工程によれば、可能な限り多くの消費者もしくは使用者の家から一定距離範囲内にいずれかの施設があるように施設を配置することができる。
【００５７】
以上のようにこの実施の形態４によれば、遺伝的アルゴリズムを適用し、各遺伝コードが示す個々の施設の位置と既知の複数の地点との間の距離を算出し、各遺伝コードについてのこれらの距離の総和を評価値として使用することによって、可能な限り多くの消費者もしくは使用者の家から一定距離範囲内にいずれかの施設があるように施設を配置することができる。換言すれば、複数の施設の各々をある地理的範囲においてどこに配置すれば有効であるかを実用的な時間内に求めることが可能である。
【００５８】
なお、実施の形態１に関連して上述した式（１）または式（２）による評価値Ｅと実施の形態４に関連して上述した式（３）による評価値Ｅ２の両方を一つの配置立案装置で使用してもよい。すなわち、個々の遺伝コードに対して、二つの評価値Ｅ，Ｅ２を算出し、これらの評価値Ｅ，Ｅ２の両方に基づいて選択処理を実行してもよい。
【００５９】
【発明の効果】
以上のように、この発明によれば、ある地理的範囲において複数の施設の配置を立案する配置立案装置において、所要の施設の数に基づいた配列を持ち遺伝的操作の母集団となり上記施設の配置の複数の候補をそれぞれ示す複数の初期の遺伝コードをランダムに生成する初期コード化部と、入力された遺伝コードの各々に評価関数を適用して遺伝コードの各々の評価値を得る評価部と、上記評価値の各々に基づいて適切な遺伝コードを選択する選択部と、上記選択部で選択された遺伝コードの各々に交叉処理を施す交叉処理部と、上記交叉が施された遺伝コードの一部に突然変異処理を施して、上記突然変異処理後の遺伝コードの各々を上記評価部に供給する突然変異処理部と、遺伝的操作が終了条件を満たした場合に、上記突然変異処理後の遺伝コードの少なくとも一つを上記施設の配置候補の最適解または準最適解である最終遺伝コードとして出力し、上記遺伝的操作が終了条件を満たさない場合に、上記突然変異処理後の遺伝コードの各々を上記選択部に供給する終了判定部とを備え、上記評価部は、遺伝コードの各々が示す施設の配置から上記施設による全サービスカバー面積に対応する指標を上記評価値として算出するので、複数の施設の各々をある地理的範囲においてどこに配置すれば全サービスカバー面積を広く確保できるかを実用的な時間内に求めることが可能であるという効果がある。
【００６０】
この発明によれば、評価部は、各遺伝コードが示す個々の施設の位置と既知の複数の地点との間の距離を算出し、各遺伝コードについてのこれらの距離の総和に対応する指標を上記評価値として算出するものでもよく、この場合には、可能な限り多くの消費者もしくは使用者の家から一定距離範囲内にいずれかの施設があるように施設を配置することができるという効果がある。
【図面の簡単な説明】
【図１】この発明に係る配置立案装置の構成を示すブロック図である。
【図２】この発明に係る配置立案装置の初期コード化部で生成された初期の遺伝コードの一例を示す模式図である。
【図３】図２の遺伝コードに対応する施設の配置候補を平面上に示す模式図である。
【図４】この発明に係る配置立案装置の遺伝的操作部の動作を示すフローチャートである。
【図５】この発明に係る配置立案装置の処理を視覚で理解できるように描写した模式図である。
【図６】この発明の実施の形態１による配置立案装置の選択工程の具体的手法を示すフローチャートである。
【図７】この発明に係る配置立案装置の交叉処理工程の具体的手法を示す模式図である。
【図８】この発明に係る配置立案装置の突然変異処理工程の具体的手法を示す模式図である。
【図９】この発明の実施の形態２による配置立案装置の選択工程の具体的手法を示すフローチャートである。
【図１０】この発明の実施の形態３による配置立案装置の選択工程の具体的手法を示すフローチャートである。
【符号の説明】
１  入力部、２  初期コード化部、３  遺伝コード評価部（終了判定部）、４遺伝的操作部（選択部、交叉処理部、突然変異処理部）、５  出力部。
【図１】
2004272455.tif 000004
【図２】
2004272455.tif 000005
【図３】
2004272455.tif 000006
【図４】
2004272455.tif 000007
【図５】
2004272455.tif 000008
【図６】
2004272455.tif 000009
【図７】
2004272455.tif 000010
【図８】
2004272455.tif 000011
【図９】
2004272455.tif 000012
【図１０】
2004272455.tif 000013