バランス調整されたゾーンの構築の仕組み
バランス調整されたゾーンの構築 ツールは、指定した基準に基づいて、遺伝的アルゴリズムを使用して調査エリア内に空間的に連続したゾーンを作成します。 同数のフィーチャを含むゾーン、属性値のセットに基づく類似のゾーン、またはそれら両方を作成できます。 また、ほぼ同じ面積のゾーン、できる限りコンパクトなゾーン、および他の変数の一定な統計サマリー (平均や比率など) を維持するゾーンを選択することもできます。
シナリオの例
このツールは次のようなシナリオで使用できます。
小売企業が、各地区の店舗数にかかわらず、各マネージャーが同等の売上高と従業員数を担当する地区を作成したいと考えています。
気候変動は多くの地域で年間の山火事発生件数の増加につながっており、それによってこれらの地域のコストが増加しています。 地方自治体や国の政府は、このツールを使用して行政地区を作成することで、消火活動の作業負荷とコストの両方を均等化できます。
警察のパトロール地区を作成して、警察官間の作業負荷と通報件数のバランスを取ることができます。 特定のエリアで人員過剰または人員不足が発生している場合は、各ブロック グループの犯罪指数のバランスを取り、警察の対応の迅速性と有効性を確保することで緩和できます。
ゾーンの構築および選択の条件の定義
ツールで最適にバランスの取れたゾーンを構築するには、ゾーンが最適であるとはどういうことかを定義する条件を指定する必要があります。 指定できる条件には、ゾーンの構築条件およびゾーンの選択条件の 2 種類があります。 このツールは、ゾーンの構築とゾーンの選択を交互に行うことでゾーンのバランスを取り、各ステップで指定した条件によって、ツールが推奨する最終的なバランス ゾーンが決定されます。
ゾーンの作成ステップでは、ゾーンの構築条件が満たされるまでランダムに成長する多数のゾーンを構築します。 ゾーンの構築条件はゾーンの要件と見なす必要があり、すべてのゾーンはこれらの条件を満たすように成長します。ゾーンがどのように成長するかについての詳細は、「遺伝的アルゴリズムによるゾーンの成長」セクションで説明します。 次に、ゾーンの選択ステップでは、各ゾーン セットをランク付けし、ゾーンの選択条件をどの程度満たしているかに基づいて最適なゾーンを選択します。 一般に、ゾーンの選択条件は要件ではなく優先条件と見なす必要があり、ゾーンの構築条件をすでに満たしているゾーンの中から選択するために使用されます。
ゾーンの構築およびゾーンの選択に使用する条件の選択は、それぞれの状況によって異なります。条件を正しく定義するために、ゾーンの作成方法 パラメーターには次のオプションが用意されています:
属性ターゲット - 各ゾーンは、属性の合計値がほぼ同じになるように作成されます。この合計値を指定する必要があります。 作成されるゾーン数は、属性の全体の合計値によって決まります。 たとえば、このオプションを使用して、それぞれ約 1,000 人の顧客を含むサービス エリアを作成できます。 すべての入力フィーチャに合計 5,000 人の顧客がいる場合、それぞれ約 1,000 人の顧客を含むゾーンが約 5 つ作成されます。 顧客が合計 200 万人いる場合は、それぞれ約 1,000 人の顧客を含むゾーンが約 2,000 作成されます。
定義されたゾーン数 - ゾーン数は指定した数と等しくなければならず、各ゾーンはほぼ同じ数のフィーチャで構成されます。 このオプションは、必要なゾーン数がわかっていて、各ゾーンに同じ数の入力フィーチャを含める必要がある場合に便利です。
ゾーン数と属性ターゲット - 指定したゾーン数の間で属性の合計値のバランスを取ることで、前の 2 つのオプションを組み合わせます。 たとえば、このオプションを使用して、各ゾーン内の売上高がほぼ同じであるサービス エリアを正確に 20 個作成できます。 このオプションでは、属性の合計値は属性の総合計をゾーン数で割ることによって決まるため、目的の属性合計値を指定しません。 このオプションでは、各ゾーン内のフィーチャ数は均等化されません (ただし、このトピックの後半で説明するように、フィーチャ数を均等にする優先条件をゾーンの選択条件として指定できます)。
カスタム シード ロケーション - 各ゾーンは、シード ロケーション ポイント と 入力フィーチャ パラメーターに基づいて固定されたシード ロケーション セットから成長します。 作成されるゾーンの総数はシード ロケーションの数によって決まります。 シード ロケーションの数は、シード ポイントと入力フィーチャに基づいて次のように決まります:
入力フィーチャがポリゴンの場合、シード ロケーション ポイントと交差するポリゴンが開始位置として選択されます。 ゾーンは、これらのシード ロケーションから近隣フィーチャを集約することで成長します。
入力フィーチャがポイントの場合、各シード ロケーション ポイントに最も近いポイントがシードとして選択されます。
ゾーンの構築条件 パラメーターを使用して、追加の変数とその重みを指定できます。
ゾーンを成長させる固定位置がある場合は、このオプションを選択します。 たとえば、既存の消防用スロープの周囲に防火帯を作成できます。
ゾーンの構築条件
ゾーンの作成方法 パラメーターの各オプションには、それぞれ異なるゾーンの構築条件が必要であり、すべてのゾーンはこれらの条件を満たすまで成長します。
属性ターゲット - バランスを取りたい属性を提供し、ゾーンの構築条件とターゲット パラメーターで合計値を指定する必要があります。 必要に応じて、異なる合計値を持つ複数の属性を指定したり、各属性に重みを指定したりできます。これにより、適合度スコアが最も低い位置を選択する際に、一部の属性を他の属性より優先できます。
定義されたゾーン数 - ターゲットのゾーン数 パラメーターを使用してゾーン数を指定する必要があります。
ゾーン数と属性ターゲット - ゾーン数 パラメーターでゾーン数を指定し、ゾーンの構築条件 パラメーターでバランスを取る属性を指定する必要があります。 この場合も、複数の属性を指定し、それらを優先するための重みを指定できます。
カスタム シード ロケーション - ゾーンが成長するシード ロケーションを シード ロケーション ポイント パラメーターで指定する必要があります。 ゾーン数は、シード ロケーション ポイントの数と入力フィーチャの両方によって決まります。 ゾーンの構築条件 パラメーターを使用して、追加の変数とその重みを指定できます。
ゾーンの選択条件
ゾーンの選択条件は、ゾーンの構築ステップで作成したゾーンの中から優先条件を指定できる追加オプションです。 これらの条件は、ゾーンの構築条件とともに使用され、最終的にツールによって推奨されるゾーンを決定します。 ゾーンの選択条件のほとんどは、ゾーンの作成方法 パラメーターのすべてのオプションに適用できます。 以下のセクションでは、各ゾーンの選択オプションと、それらが適用される場合について説明します。
ゾーンの特性条件
ゾーンの特性 パラメーターのオプションは、一般にゾーンのサイズと形状に関連しています。 次のいずれか、またはすべてのオプションを使用できます:
等面積 - 面積がほぼ等しいゾーンが優先されます。 このオプションは、入力フィーチャがポリゴンの場合にのみ適用されます。
コンパクト性 - 円形に近いゾーンが優先されます。 このオプションは常に適用できます。
同数のフィーチャ - ほぼ同じ数のフィーチャで構成されるゾーンが優先されます。 このオプションは 定義されたゾーン数 オプションを使用する場合には適用されません。このゾーンの作成方法では、ゾーンの構築条件によってフィーチャ数が均等になることがすでに保証されているためです。
属性考慮条件
考慮する属性 パラメーターでは、ゾーンの構築条件として使用されなかった追加属性を考慮対象として指定できます。 これにより、属性の合計、平均、分散、または中央値の一貫性を維持するゾーンを含めることができます。 複数の属性を指定することもできます。たとえば、総人口 (合計) が同じで、所得の中央値 (中央値) がほぼ同じであるゾーンを含めることができます。
この選択条件は、すべてのゾーンの作成方法に適用されます。 このパラメーターで使用する属性は、カテゴリー属性ではなく連続属性である必要があります。
カテゴリー変数の割合の維持
割合を維持するカテゴリー変数 パラメーターでは、ゾーン内のカテゴリーの割合のバランスを取るために使用するカテゴリー変数を指定できます。 また、割合のバランスを取る方法を指定するために、按分方法 を選択する必要があります。 次の按分方法が用意されています:
内部の割合を維持 - 各ゾーン内のカテゴリーの相対比率が同じになるゾーンが優先されます。 たとえば、比率を維持するために使用するカテゴリー変数が森林と非森林の 2 値の土地被覆分類を表しており、フィーチャの 60% が土地被覆タイプの森林、40% が非森林の土地被覆タイプである場合、このオプションは各ゾーンが森林 60%、非森林 40% で構成されるゾーンを優先します。
全体の割合を維持 - ゾーンは、カテゴリー優位性の全体的な割合が全体のカテゴリーの割合と一致するように作成されます。 たとえば、カテゴリー変数がフィーチャが陸上にあるか水上にあるかを表しており、フィーチャの 60% が陸上にある場合、このオプションでは、ゾーンの約 60% が主に陸上、40% が主に水上となるゾーンが優先されます。
この選択条件は、すべてのゾーンの作成方法に適用されます。 このパラメーターで使用する変数は、連続変数ではなくカテゴリー変数である必要があります。
距離ベースの条件
考慮する距離 パラメーターでは、別のフィーチャ セット、または複数のフィーチャ セットに近いゾーンを優先できます。 たとえば、医療行政地区を構築している場合は、既存の病院に近いゾーンを優先できます。 ゾーンとフィーチャの距離は、ゾーン内のすべてのフィーチャから、距離の考慮対象として指定された最も近いフィーチャまでの距離の中央値として定義されます。
ゾーン条件を選択するシナリオ
ゾーンの構築条件およびゾーンの選択条件には多数のオプションがあり、ゾーンに関する要件や優先条件に基づいてどのパラメーターを使用すべきかがすぐにはわからない場合があります。 以下に、いくつかのシナリオと、それらのシナリオで使用すべきパラメーターを示します。
シナリオ 1: 物件リストを不動産業者に割り当てる
不動産会社のアナリストであるとします。 利用可能なすべての物件リストと、そのエリア内の各物件価格を含むフィーチャクラスがあります。 会社内には 12 の不動産業者がおり、各不動産業者に物件リストを割り当てて、すべての不動産業者が同じ数のリストを受け取り、各ゾーン内の物件の総価格がほぼ同じになるようにしたいと考えています。 また、ゾーンは既存の不動産支店の近くにしたいと考えています。
これを実現するには、ゾーンの作成方法 パラメーターで ゾーン数と属性ターゲット オプションを使用できます。 ターゲットのゾーン数 パラメーターに 12 (各不動産業者ごとに 1 つ) を指定し、ゾーンの構築条件 パラメーターで各物件の価格を表すフィールドを選択します。 ゾーンの特性 パラメーターで 同数のフィーチャ オプションを選択し、各不動産業者にほぼ同じ数の物件が割り当てられるゾーンを優先します。 最も近い不動産支店までの距離を考慮するには、支店の位置を表すフィーチャクラスを 考慮する距離 パラメーターに指定します。
シナリオ 2: 新しい地区境界の作成
各地区内の人口のバランスを取る新しい地区境界を作成することは、政府のほぼすべてのレベルで頻繁に実行する必要がある、複雑で困難な作業です。 小さな地区で収集された人口および人口統計データを使用して、それぞれ約 10,000 人を含む地区を作成したいとします。 さらに、人口の約 75% は都市部に居住し、25% は農村部に居住しています。 各グループを適切に代表するために、ゾーンの約 75% を都市部が多数を占めるゾーン、25% を農村部が多数を占めるゾーンにしたいと考えています。
これを実現するには、ゾーンの作成方法 パラメーターで 属性ターゲット オプションを使用できます。 各地区の人口を表すフィールドを選択し、ゾーンの構築条件とターゲット パラメーター の列に 10,000 を指定します。 割合を維持するカテゴリー変数 パラメーターで、その地区が都市部か農村部かを表すフィールドを指定し、按分方法 パラメーターで 全体の割合を維持 オプションを選択します。
シナリオ 3: 仮釈放担当官への作業負荷の割り当て
法執行部門の GIS アナリストであり、25 人の仮釈放担当官の担当件数のバランスを取る任務を与えられているとします。 市内のすべての犯罪者の位置と各犯罪者の数値リスク評価があり、それらを各仮釈放担当官に均等に分配しながら、犯罪者の総リスクがほぼ同じになるようにしたいと考えています。 ただし、リスクのバランスは、各仮釈放担当官に割り当てられる犯罪者数を同じにすることほど重要ではありません。 さらに、仮釈放担当官の移動コストを削減するために、ゾーンをできるだけコンパクトにしたいと考えています。
これを実現するには、ゾーンの作成方法 パラメーターで 定義されたゾーン数 オプションを使用し、ターゲットのゾーン数 パラメーターに 12 を指定します。 考慮する属性 パラメーターで各犯罪者のリスクを表すフィールドを指定し、ゾーンの特性 パラメーターで コンパクト性 オプションを選択してコンパクトなゾーンを作成します。
シナリオ 4: 既存の消防署を基点としたバランスの取れた緊急対応ゾーンの作成
市の緊急管理部門の GIS アナリストであり、消防および救急対応のためのサービス カバレッジ ゾーンを定義する必要があるとします。 市には既存の消防署があり、各消防署は対応ゾーンの固定シード ロケーションとして機能する必要があります。
国勢調査ブロックとインシデント需要を表すデータがあり、これらのエリアを消防署に割り当てて、各消防署が人口や過去の通報量などの同程度の総作業負荷を担当するようにしたいと考えています。 作業負荷のバランスを取ることは重要ですが、各ゾーンが、割り当てられた消防署から許容可能な対応時間内に到達可能であることも極めて重要です。 そのため、移動距離を短縮し、対応効率を向上させるために、ゾーンを地理的にコンパクトにしたいと考えています。
これを実現するには、ゾーンの作成方法 パラメーターで カスタム シード ロケーション オプションを使用し、消防署の位置をシード ロケーション ポイントとして指定します。 ゾーンの構築条件 パラメーターで人口と総通報需要を表すフィールドを指定し、ゾーンの特性 パラメーターでコンパクト性を優先します。 これにより、固定された消防署のロケーションを尊重しながら、ゾーンが各消防署から外側に向かって成長し、空間的なまとまりを維持し、作業負荷を可能な限り均等に配分できます。
遺伝的アルゴリズムによるゾーンの成長
ゾーンの構築とゾーンの選択で定義した条件を使用して、バランス調整されたゾーンの構築 ツールは、入力フィーチャの空間的制限を前提として、遺伝的アルゴリズム (GA) を使用して最適なゾーンを成長させます。
GA は、チャールズ ダーウィンが初めて説明した自然選択と遺伝学に関する進化論に基づいています。 ダーウィンの適者生存の原理によれば、個体群内でより適合度の高い生物は生存し、より多くの子孫を残す傾向があります。
可能解の数は通常非常に多いため、GA はランダム探索から開始し、探索をより有望な方向へ進めることで、最適化された解を探索します。 GA 最適化は自然界の生物進化を抽象化したものであり、各可能解 (この場合はゾーンの各配置) が、個体群内の 1 つの生物個体に相当します。 世代が進むにつれて、最も適合度の高い個体のみが生き残り、最も有望な探索のみが継続されます。
このアルゴリズムは、個体群内の各個体が可能解であるランダムな個体群を作成することから始まります。 各解について適合度スコアが計算され、既存の個体群内で適合度スコアが最も低い個体 (最良の解) が次の世代に引き継がれ、残りの適合度の低い解は除外されます。 最も適合度の高い個体は親として指定され、交叉や突然変異などの遺伝的演算子を使用してペアで子孫を作ることができます。 各新世代は、前の世代の最も適合度の高い個体とその子孫の組み合わせです。 場合によっては、個体 (親でも子孫でもない、エイリアンと呼ばれる) が次世代にランダムに導入され、アルゴリズムによって発見される可能解の範囲が広げられます。 各新世代のすべての個体について適合度スコアが計算され、このプロセスは指定された世代数、デフォルトでは 50 世代にわたって繰り返されます。 最終世代で最も適応度の高い個体が、ツールによって返されるバランス ゾーンに対応します。
初期個体群の選択
アルゴリズムの初期個体群は、調査エリア内のフィーチャをランダムに選択するか、カスタム シード ロケーションを使用して選択されます。 デフォルトでは、個体群は 100 個体で構成されますが、この数は 個体数 パラメーターで変更できます。 ランダムに選択された各フィーチャは開始位置 (シード) となり、そこから近隣フィーチャを集約することでゾーンが成長します。 ゾーンは、合計値がゾーンの構築条件の閾値に達するまで集約と成長を続けます。 たとえば、ゾーンの構築条件として人口 100,000 と世帯数 50,000 を指定した場合、100,000 と 50,000 はそれぞれ人口と世帯数の閾値であり、すべての閾値に達するとゾーンの成長は停止します。 次のゾーンでは、最初のゾーンの外側から新しいシードが選択され、ランダムに成長します。 このプロセスは、すべてのフィーチャがゾーンに割り当てられるまで続きます。
生物学では、個体の遺伝物質は染色体に含まれています。 染色体は、生命の遺伝単位である遺伝子で構成されています。 このツールでは、可能解が染色体に相当し、シードが遺伝子に相当します。 これらの遺伝子は、親から子孫に受け継がれる遺伝単位であり、将来の世代を作成するために使用されます。 次の図は、可能解の例と、その解の各ゾーンのシードの Object ID 値を示しています:
適応度スコアの計算
各可能解の適合度スコアは、生成されたゾーンが、ツールで指定されたさまざまなゾーンの構築条件およびゾーン選択条件をどの程度満たしているかを示す指標です。適合度スコアが低いほど、条件への適合度が高いことを示します。 したがって、最終的な目標は、適合度スコアが低い解 (理想的には、可能な限り最も低い適合度スコアを持つ解、つまり大域的最小値を与える解) を見つけることです。 可能解の適合度スコアは、次の式を使用して計算されます:
\(n\) - 解内のゾーンの総数。
\(c\) - ゾーンの構築や解の選択に使用される条件の総数。
\(V_j\) - j 番目の条件の閾値。
\(V_{ij}\) - i 番目のゾーンの j 番目の条件の合計。
適合度スコアの式は、解内の各ゾーンについて、各条件の値が理想的に完全な値からどの程度異なるかを合計するものとして理解できます。 完全解 (通常不可能) では、すべてのゾーンの条件値が理想値と等しくなり、適合度スコアはゼロになります。 閾値 (Vj) で割ると、適合度スコアは単位を持ちません。 単位を持たないことは重要です。たとえば、面積の計測に平方メートルを使用しても平方フィートを使用しても、適合度スコアには影響しません。
出力収束テーブル パラメーターでは、各世代における最良解の総合適合度スコアと、各個別条件のスコアが提供されます。 出力テーブルとともに収束チャートが作成され、これらの適合度スコアが世代を通じてどのように変化するかが示されます。 アルゴリズムは既存の解よりも優れた解を見つけようとするため、チャート内の総合適合度の線は通常、世代が進むにつれて低下し、最終的に横ばいになります。 この横ばいは、適合度スコアが局所的最小値に達したことを示します。ただし、それは大域的最小値ではない可能性が高く、さらに世代を進めても解が改善される可能性は低いことを示しています。
出力収束テーブルに加えて、ジオプロセシング メッセージも、ゾーンがどの程度適切に生成されたかを理解するのに役立ちます。 ゾーンの構築条件とゾーン選択条件ごとに、二乗平均平方根誤差 が提供されます。 値が低いほど、ゾーンが条件をよく満たしていることを示します。
交叉による新世代の作成
アルゴリズムによって初期個体群が生成されると、個体の半数が次の世代に参加し、新しい可能解の子孫を作成できます。 これらの個体は適合度 (最も低い適合度スコア) に基づいて選択され、交叉と呼ばれるプロセスを使用して子孫を生成するためにランダムにペアにされます。 交叉は、組換えと呼ばれることもある遺伝的演算子で、2 つの親からの情報を組み合わせて子孫を生成します。 次の図は、2 つの親のシードが交叉され、2 つの新しい子孫が作成される例を示しています:
その結果、新しい世代の個体の半数は前の世代の親であり、残りの半数はその子孫になります。 この新しい世代についても再び適合度スコアが計算され、上位半数が次の世代に進み、探索はより優れた解へと向かいます。
突然変異とエイリアン種による可能解の拡張
進化する個体群では多様性が非常に重要であり、多様性を維持する方法の 1 つが突然変異です。 突然変異とは、遺伝子配列に導入される小さな変更または変化であり、異なる遺伝コードを持つ個体を作成します。 このツールでは、突然変異を受けた個体のシードはランダムに並べ替え (順序を入れ替え) られます。 次の図は、1 つの可能解が突然変異を受け、シードが並べ替えられる例を示しています:
子孫が突然変異を受ける確率は 突然変異ファクター パラメーターで制御でき、デフォルト値は 0.1 です。 突然変異を導入すると、可能解が拡張され、多くの場合、アルゴリズムは局所的な最適解にすばやく収束できます。 ただし、突然変異係数が非常に高いと、多数の変更が導入されるため、アルゴリズムの効率が低下し、収束が遅くなる、またはまったく収束しなくなる可能性があります。
可能解を拡張するもう 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.