[バランス調整されたゾーンの構築 (Build Balanced Zones)] ツールは、遺伝アルゴリズムを使用し、指定された条件に基づいて空間的に隣接するゾーンを分析範囲に作成します。同数のフィーチャを含むゾーン、属性値のセットに基づく類似のゾーン、またはそれら両方を作成できます。また、できるだけコンパクトにしてほぼ等しい面積を持つようにゾーンを選択するオプション、また、他の変数の要約統計量 (平均、比率など) を一定に維持するようにゾーンを選択するオプションもあります。
シナリオ例
このツールは次のようなシナリオで使用できます。
- ある小売会社は、各地区の店舗数とは関係なく、各マネージャーが同じ売上額と従業員数を担当するように地区を形成しようと考えています。
- 気候変動が原因で、数多くの地域で年間の山火事の発生件数が増加しており、それらの地区での経費が上昇することが見込まれています。地方自治体も中央政府も、このツールを使用して、行政地区を作成して消防活動にかかるワークロードとコストを平坦化することができます。
- 警察では、警官の出動負荷と通報数のバランスを調整して、パトロール地区を作成できます。各ブロック グループの犯罪発生指標のバランスを調整することにより、一部の地区における人員過剰または人員不足が緩和され、迅速で効果的な警察活動が確保されます。
ゾーン構築とゾーン選択基準の定義
ツールで適切にバランス調整されたゾーンを構築するには、ゾーンが最適となる条件を定める必要があります。指定できる条件には、ゾーン構築条件とゾーン選択基準の 2 つのタイプがあります。ツールは、ゾーン構築とゾーン選択を交互に行いながらゾーンを調整します。各ステップで指定した条件によって、ツールが推奨する最終的なバランス調整されたゾーンが決まります。
ゾーン作成ステップでは、ゾーン構築条件が満たされるまでランダムに成長する多数のゾーンを構築します。ゾーン構築の条件は、ゾーンの要件として考慮する必要があります。また、すべてのゾーンは、これらの条件を満たしながら成長します (ゾーンの成長について詳しくは「遺伝的アルゴリズムによるゾーンの成長」セクションをご参照ください)。ゾーン選択ステップでは、各ゾーンのセットにランク付けをして、ゾーン選択基準を満たしている度合いに応じて最適なゾーンを選択します。一般的に、ゾーン選択基準は要件ではなく好みとして考慮する必要があり、ゾーン構築条件をすでに満たしているゾーンから選択するために使用されます。
ゾーン構築とゾーン選択に使用される基準は、それぞれの状況によって異なります。基準を正しく定義できるよう、[ゾーンの作成手法] パラメーターには次のオプションが用意されています。
- [属性ターゲット] - 各ゾーンの属性の合計はほぼ同じであり、この合計を指定する必要があります。作成されるゾーンの数は、属性の総数に左右されます。たとえば、このオプションを使用して、すべてに約 1,000 人の顧客が含まれる到達圏を作成できます。入力フィーチャ全体で合計 5,000 人の顧客がいる場合は約 5 つのゾーンが作成され、そのそれぞれに約 1,000 人の顧客が割り振られます。合計顧客数が 200 万人であれば、約 2,000 個のゾーンが作成され、そのそれぞれに約 1,000 人の顧客が含まれます。
- [指定されたゾーン数] - ゾーンの数は指定された数に一致し、各ゾーンはほぼ同数のフィーチャで構成される必要があります。このオプションは、必要なゾーン数がわかっており、各ゾーンに同数の入力フィーチャを含める必要がある場合に便利です。
- [ゾーン数と属性ターゲット] - 前述の 2 つのオプションを組み合わせ、特定のゾーン数の間で属性の合計を調整します。このオプションは、たとえば、各ゾーンでほぼ同じ売上高を持つ 20 個ちょうどの到達圏を作成する場合に便利です。このオプションでは、属性に対して希望する合計数は指定しません。その合計数は、属性の総数をゾーン数で除算することで求められるからです。また、このオプションではゾーンごとのフィーチャ数を平坦化しません (ただし、フィーチャを同数に設定する場合は、ゾーン選択基準として指定できます。それについては本トピックで後述します)。
ゾーンの構築条件
[ゾーンの作成手法] パラメーター オプションごとに、それぞれに異なる必須のゾーン構築条件があり、すべてのゾーンはこれらの条件を満たすまで成長します。
- [属性ターゲット] - バランス調整する属性を指定し、[ゾーンの構築条件とターゲット] パラメーターで合計を指定する必要があります。あるいは、異なる合計を持つ複数の属性を指定してから、各属性に対してウェイトを指定し、一部の属性を他の属性よりも優先させることもできます。
- [指定されたゾーン数] - [ゾーンのターゲット数] パラメーターを使用し、ゾーン数を指定する必要があります。
- [ゾーン数と属性ターゲット] - ゾーン数を [ゾーン数] パラメーターで指定し、[ゾーンの構築条件] パラメーターではバランス調整する属性を指定する必要があります。ここでも複数の属性を指定し、ウェイトを指定して優先させることもできます。
ゾーン選択基準
ゾーン選択基準とは、ゾーン構築手順で作成したゾーンに対して優先事項を指定するためのオプションです。これらの基準をゾーン構築条件と併用することで、ツールが最終的に推奨するゾーンが決定されます。ほとんどのゾーン選択基準は、[ゾーンの作成方法] パラメーターのすべてのオプションに適用されます。次のセクションでは、各ゾーン選択オプションと、それらのオプションが適用されるタイミングについて説明します。
ゾーンの特性基準
[ゾーンの特性] パラメーター オプションは、一般的に、ゾーンのサイズと形状に関連するものです。次のオプションのいずれか、またはすべてで使用できます。
- [等面積] - 面積がほぼ等しいゾーンが優先されます。このオプションは、入力がポリゴンの場合にのみ適用されます。
- [圧縮率] - 形状が円形に近いゾーンが優先されます。このオプションは常に適用されます。
- [同数のフィーチャ] - ほぼ同数のフィーチャで構成されるゾーンが優先されます。このオプションは、[指定されたゾーン数] オプションが使用されている場合には適用されません。そのゾーン作成手法では、ゾーン構築条件において同数のフィーチャがすでに確保されているからです。
属性の考慮条件
[考慮する属性] パラメーターでは、ゾーン構築条件としては使用されなかったが、考慮するべき追加の属性を指定できます。これにより、属性の合計値、平均値、偏差、または中央値の一貫性を保つゾーンを含められるようになります。また、複数の属性を指定することも可能なので、たとえば総人口 (合計値) と、年収の中央値 (中央値) がほぼ同じゾーンを含めることができます。
この選択基準は、すべてのゾーン作成手法に適用されます。このパラメーターで使用する属性は、カテゴリではなく連続値である必要があります。
カテゴリ変数の割合の維持
[割合を維持するカテゴリ変数] パラメーターでは、ゾーン内のカテゴリの割合をバランス調整するために使用されるカテゴリ変数を指定できます。また、[按分方法] を選択し、割合をバランス調整する方法を指定する必要があります。次の按分方法が用意されています。
- [内部の割合を維持] - 個々のゾーン内でカテゴリの相対的な割合を維持するゾーンが優先されます。たとえば、割合を維持するために使用するカテゴリ変数が、森林と非森林の 2 項で成る土地被膜分類を表しており、フィーチャの 60 パーセントが森林の土地被膜タイプ、40 パーセントが非森林の土地被膜タイプである場合、個々のゾーンが 60 パーセント森林、40 パーセント非森林で構成されるゾーンが優先されます。
- [全体の割合を維持] - カテゴリ優位性の全体的な割合が、カテゴリ全体の割合と一致するようにゾーンが作成されます。たとえば、カテゴリ変数が陸地のフィーチャか水上のフィーチャかを表しており、フィーチャの 60 パーセントが陸上にある場合は、ゾーンの約 60 パーセントが主に陸上にあり、ゾーンの約 40 パーセントが主に水上にあるゾーンが優先されます。
この選択基準は、すべてのゾーン作成手法に適用されます。このパラメーターで使用する変数は、連続値ではなくカテゴリである必要があります。
距離ベースの基準
[考慮する距離] パラメーターは、異なるフィーチャ セット (または複数のフィーチャ セット) に近いゾーンを優先します。たとえば、健康管理地区を構築している場合は、既存の病院に近いゾーンを優先させます。ゾーンとフィーチャ間の距離は、ゾーン内のすべてのフィーチャから最寄りのフィーチャまでの距離の中央値を、考慮する距離として指定して定義します。
ゾーン基準の選択のシナリオ
ゾーン構築条件とゾーン選択基準にはさまざまなオプションが用意されており、ゾーンの要件や優先順位によってどのパラメーターを使用するかは一目ではわからないことがあります。次に、いくつかのシナリオと、各シナリオにおいて使用するパラメーターを示します。
シナリオ 1: 不動産仲介人への物件情報の割り当て
あなたは不動産会社のアナリストです。地域内の空き物件情報とその価格を含むフィーチャクラスがあります。会社には 12 人の不動産仲介人が所属しており、各仲介人の物件情報とその総額が各ゾーンにおいてほぼ均等になるよう割り振りたいと考えています。また、ゾーンが既存の支店の近隣になるようにします。
そのために、[ゾーンの作成方法] パラメーターの [ゾーン数と属性ターゲット] オプションを使用します。[ゾーンのターゲット数] パラメーターには「12 」(仲介人ごとに 1 つ) を設定し、[ゾーンの構築条件] パラメーターには各物件の価格を表すフィールドを選択します。[ゾーンの特性] パラメーターでは [同数のフィーチャ] を選択します。そうすると、各仲介人にほぼ同数の物件が割り当てられたゾーンが優先されます。最寄りの支店までの距離を考慮するには、支店の場所を表すフィーチャクラスを [考慮する距離] パラメーターで指定します。
シナリオ 2: 新しい地区境界線の作成
各地区の人口がバランスよく調整されるよう新しい地区境界線を作成するタスクは複雑かつ困難ですが、あらゆる自治体で頻繁に実施する必要がある作業です。小規模な地区で収集された人口統計データを使用して、1 つの地区の人口が約 10,000 人になるようにしたいと考えています。さらに、人口の約 75 パーセントが都市部に在住し、25 パーセントが農村部に在住するようにします。各グループを適切に表せるよう、ゾーンのおよそ 75 パーセントの大半を都市部、25 パーセントの大半を農村部とします。
そのために、[ゾーンの作成方法] パラメーターで [属性ターゲット] を使用します。各地区の人口を表すフィールドを選択し、[ゾーンの構築条件とターゲット] パラメーターの列に「10,000」を指定します。[割合を維持するカテゴリ変数] パラメーターに、地区が都市部であるか農村部であるかを表すフィールドを指定し、[按分方法] パラメーターの [全体の割合を維持] オプションを選択します。
シナリオ 3: 保護観察官へのワークロードの割り振り
あなたは法執行機関の GIS アナリストであり、25 人の保護観察官の担当件数のバランスを調整する任務を担っています。市内のすべての犯罪者の所在地と、各犯罪者のリスク評価の数値があります。それをすべての保護観察官に均等に割り振ります。このとき、犯罪者の合計リスクはほぼ同じになるようにします。ただし、リスクのバランス調整よりも、各保護観察官が担当する犯罪者数を同じにすることを重視します。さらに、保護観察官の移動コストを抑えるために、ゾーンをできる限りコンパクトにします。
そのためには、[ゾーンの作成方法] パラメーターで [指定されたゾーン数] オプションを使用し、[ゾーンのターゲット数] パラメーターで「12」を指定します。[考慮する属性] パラメーターで各犯罪者のリスクを表すフィールドを指定し、[ゾーンの特性] パラメーターで [圧縮率] オプションを選択して、コンパクトなゾーンを作成します。
遺伝的アルゴリズムによるゾーンの成長
[バランス調整されたゾーンの構築 (Build Balanced Zones)] ツールは、ゾーン構築およびゾーン選択で定義した基準を使用し、入力フィーチャの空間的な制限を考慮しながら遺伝的アルゴリズム (GA) を使用して最適なゾーンを成長させます。
GA は、自然選択と遺伝学に関して Charles Darwin が初めて述べた革新的な理論に基づきます。Darwin の適者生存の原理に従うと、個体群の中で適応性が最も高い個体は、生存して子孫を残す傾向が高くなります。
一般的に考えられる解の数が非常に多いため、GA はランダムな探索から始めて、より見込みの高い方向に探索を進めることにより、最適解を探索します。GA の最適化は、考えられるそれぞれの解 (この例では、考えられるそれぞれのゾーン配置) が個体群内における個体に類似しているという自然の生物学的進化を抽象化したものです。世代が進むにつれて、適応性が最も高い個体のみが生き残り続け、また効果の高い探索のみが続行されます。
このアルゴリズムは、それぞれの個体が考えられる解であり、それらの個体を含むランダムな個体群を作成するところから開始します。それぞれの解について適応性スコアを計算し、既存の個体群内でそのスコアが最も低い個体 (最適解) が次世代に渡され、残りの適さない解は除去されます。適応性が最も高い個体は親となり、交差や変異などの遺伝子操作によって、子孫を対で作成できるようになります。それぞれの新世代は、前世代における適応性が最も高い個体の組み合わせであり、それらの子孫です。アルゴリズムが検出しようとする、考えられる解の範囲を広げる目的で、ときどき、個体 (親でも子孫でもない、「外来種」と呼ばれる) が次世代にランダムに導入されます。新世代ごとに、すべての個体について適応性スコアが計算され、指定された世代の数だけプロセスが繰り返されます (デフォルトは 50 世代)。最終世代における適応性が最も高い個体が、ツールから返されるバランス調整されたゾーンに対応します。
初期個体群の選択
アルゴリズムで使用される初期個体群の選択は、分析範囲でフィーチャをランダムに選択することにより行われます。デフォルトの個体群は 100 体の個体で構成されますが、[個体群のサイズ] パラメーターを使用して変更できます。ランダムに選択されたフィーチャは開始位置 (「シード」と呼ばれる) であり、そこから近くのフィーチャに集約されてゾーンが成長します。ゾーンは、合計値がゾーン構築条件の閾値に達するまで集約と成長を続けます。たとえば、ゾーン構築条件として人口 100,000 人と 50,000 世帯を指定した場合、100,000 が人口、50,000 が世帯数の閾値であり、すべての閾値に達するとゾーンは成長を停止します。次のゾーンについて、最初のゾーンの外部から新しいシードが選択され、ランダムに成長します。すべてのフィーチャがゾーンに割り当てられるまで、このプロセスが続行されます。
生物学において、個体の遺伝物質は染色体に保持されます。染色体は、遺伝的な生命単位である遺伝子で構成されます。このツールでは、考えられる解が染色体に相当し、シードが遺伝子に相当します。これらの遺伝子は、親からその子孫に転送される遺伝単位であるため、その後の世代の作成に使用されます。次の図に、考えられる解の例と、解の各ゾーンのシードの Object ID 値を示します。
適応性スコアの計算
それぞれの考えられる解の適応性スコアは、ツールに指定された各種のゾーン構築条件およびゾーン選択基準に結果のゾーンがどれだけ厳密に従っているかを示す尺度です。適応性スコアが小さいほど基準により適合していることを示します。したがって、最終目標は適応性スコアの低い解を求めることです (理想的には、考えられる解の最小適応性スコア (大域最小値) を持つ解)。考えられる解の適応性スコアは、次の式を使用して計算されます。
- n - 解のゾーンの総数。
- c - ゾーンの構築と解の選択に使用する条件の総数。
- Vj - j 番目の条件の閾値。
- Vij - i 番目のゾーンの j 番目の条件。
適応性スコアの式は、解の各ゾーンについて、理論上の完璧な値と各条件の値との差を累計したものと考える必要があります。完璧な解 (これは一般的に不可能) では、すべてのゾーンのすべての条件値が理論上の値に等しくなり、適応性スコアはゼロになります。閾値 (Vj) で除算することで、適応性スコアは無次元数になります。無次元数であることは重要で、たとえば面積の測定値に平方メートルと平方フィートのいずれを選択しても適応性スコアに影響しません。
[出力収束テーブル] パラメーターは、各世代の最適解の適応性スコアの合計と、各個体の条件のスコアを示します。収束チャートは出力テーブルを使用して作成され、これらの適応性スコアが世代にわたってどのように変化するかを示します。このアルゴリズムはすでに得られた解よりも適する解を求めようとするため、通常、世代が進むにつれてチャートの適合性の合計を示す線は低下し、最後には平坦になります。この平坦な線は、適応性スコアが局所最小値 (大域最小値ではない可能性がある) に達したことを示し、それ以降の世代を続行しても、より適する解が得られない可能性があります。
交差による新世代の作成
アルゴリズムが初期の個体群を生成すると、個体の半数は次世代に関与して、新しい考えられる解の子孫を作成することができます。これらの個体はその適応性に基づいて選択され (最小の適応性スコアにより決定される)、ランダムにペアとして組み合わされて、交差と呼ばれるプロセスを使用して子孫が生成されます。交差 (「組み換え」と呼ばれることもある) は、2 体の親からの情報を組み合わせて子孫を生成する遺伝操作です。次の図に、交差して 2 体の子孫を作成する 2 体の親のシードの例を示します。
その結果、新世代の個体の半数は前世代の親であり、半数はそれらの子孫です。この新世代について適応性スコアが計算され、上位の半数が次世代に進み、優れた解に向けた探索が進行します。
変異および外来種による考えられる解の拡張
個体群の進化において多様性は非常に重要であり、多様性を維持する方法の 1 つは変異によるものです。変異とは、一連の遺伝子に導入されるわずかな変化または改変であり、異なる遺伝コードを使用して個体を作成することです。このツールでは、変異が発生する個体のシードはランダムに並べ替えられ (順列され) ます。次に、変異が発生してシードが並べ替えられる、解の 1 つを示します。
子孫に変異が発生する可能性は [変異係数] パラメーターにより制御することができ、そのデフォルト値は 0.1 です。変異を導入することにより、考えられる解が拡張され、多くの場合にアルゴリズムが迅速に局所最適解に収束します。ただし、変異係数を非常に高くすると、多くの変化が導入されるため、アルゴリズムの効率が低くなり、収束に時間がかかります (またはまったく収束しない)。
考えられる解を拡張する別の方法は、以前の世代またはそれらの子孫のいずれにも含まれない、まったく新しい個体 (「外来種」と呼ばれる) を個体群に導入することです。外来種の個体を導入すると、高い収束速度を維持しつつ、大域最小値 (局所最小値ではない) を得られる確率が上昇します。突然変異ファクターは、各世代において、ランダムに生成されたシードで構成される外来種に置換される子孫の割合を制御します。
切断されたグループ
空間的制限により、切断されたグループが作成されることがあります。切断されたグループでは、グループ内のフィーチャは大きい分析範囲のどのフィーチャにも隣接しません。これは、[入力フィーチャ] が連続しないポリゴン (島など) の場合に見られます。ゾーンは、ゾーン内の既存フィーチャの空間近傍を集約することによってのみ成長します。これを解決するには、切断されたグループとグループ外の最寄りのフィーチャとの間にリンクを生成し、近傍を確立するとともに、ゾーンの成長を継続させます。[出力フィーチャ] の属性テーブルに [切断されたグループ ID] フィールドを追加します。これによって、分析範囲で切断されたフィーチャまたはフィーチャ グループを視覚化できるようになります。
参考資料
- Coley, D. A. (1999). An introduction to genetic algorithms for scientists and engineersで使用できる解析ツール用のコード片を参照し、追加することができます。World Scientific Publishing Company.
- Lorena, L. A. N., & Furtado, J. C. (2001). Constructive genetic algorithm for clustering problemsで使用できる解析ツール用のコード片を参照し、追加することができます。Evolutionary Computation, 9(3), 309-327.
- Patel, N., & Padhiyar, N. (2010, October). Alien Genetic Algorithm for Exploration of Search Spaceで使用できる解析ツール用のコード片を参照し、追加することができます。AIP Conference Proceedings (Vol. 1298, No. 1, pp. 325-330). AIP.