格点划分策略研究

观察该算法输出的地区组成通常都是断开的，这将很快通过蒙特卡罗研究进行量化。B、 弗里德曼和霍尔顿包装法的影响在检查模仿弗里德曼和霍尔顿方法建造的地区是否相互关联之前，我们首先要通过与无党派的分区模式进行比较，来量化这种选区划分程序给支持者带来了多大程度的优势。为了评估选区划分的影响，我们在a21×21网格区域上构建了一个选民模型，其中人口分布如第一节B所示为准高斯分布，源点遵循表1的基准，总人口固定为PS≈4700（高达0.5%的波动）。由于walker函数在近似高斯的总体分布中引入了随机波动，每次运行都会返回不同的重新划分。因此，我们可以使用多次运行的算法，通过蒙特卡罗方法评估给定源点集的不规则划分的影响。美国国会选区的典型人口为70万；如果需要，我们的结果可以相应地重新缩放。格点法研究13弗里德曼·霍尔顿包装的样本执行情况图5：具有高斯总体分布和平衡投票的表1的基准模型#1（顶部）和#4（底部）的分配结果示例。gerrymander\'sSparty是红色的，在这两种情况下都赢得了五个地区中三个地区的普选。图6：我们实施弗里德曼-霍尔顿方法的流程图。14预印图7。

：21×21晶格的公平对称性分布。具体而言，我们在30个不同的21×21格子种群模型上生成了一组不同的重新划分计划，这些模型具有平衡投票数NS≈ 对于四个基准源点位置中的每一个，取0（如图3和图4所示），并将该地区划分为五个区（即取n=5）。Dk各区1≤ k≤ 5，我们计算了平均地区投票数和人口PDk，以及平均地区获胜人数。在表2中，我们显示了通过FH包装和平均30次运行重新划分后的每个地区的平均投票数：PD1PD2PD2PD3PD4PD4PD5ND5#win#1902 43.7 970 5.8 978 1.5 946-34.6 910-16.3 3 3#2 898 60.6 903 16.0 955 9.5 950-27.2 1001 58.8 3#3 897 82.1 899 37.2 906 29.4 950-21.6 1059-127.1 3#4 901 83.6 898 15.4939 9.8 945 69.6 1022 39.8表2：通过FH方法重新划分后每个地区的平均净投票数。将这些结果与一些“公平”的人口划分进行比较是很有见地的。由于人口近似于二维高斯分布，任何不考虑选民分布的人口球对称分区都可以视为无党派分区。我们将通过将中心单元分配给1区，然后对称划分未分配给1区的一组领土单位，创建2-5区，从而构建一个无党派n=5区。我们选择划分2-5区，只需沿水平和垂直中轴线绘制区域线，并沿顺时针方向将边界上的领土单位分配给相邻的区域。

1区的大小是固定的，因此5个地区的人口大致相等，因此它是由高斯方差和人口阈值t确定的。由此产生的地区如图7所示。为了评估选区划分的影响，我们将选区划分严重的预测结果（由我们对FH布局策略的算法实施确定）与对上述对称选区的投票结果进行比较，以获得平衡区域。在S上生成30个人口分布，我们计算每个地区的平均净投票数和支持者获胜的地区平均获胜数，如表3所示。格点选区划分策略研究15模型ND1ND2ND3ND4ND5#win#1 0.1 35.1 31.5-31.5-35.1 2.44#2-0.1 153.6 124.0-124.1-153.5 2.56#3-0.1-311.1 49.3-49.0 310.8 2.46#4 0.0-45.2 44.8 44.6-44.9 2.42表3：IDED每个地区的平均净投票数将无党派对称选区化。通过表2和表3的比较，可以清楚地看出，FH包装对选举结果有显著影响，从而使预测的地区获胜人数向支持党倾斜。然而，正如我们接下来所展示的，通过FH包装建造的区域通常是断开连接的，因此通常是法律禁止的。C、 Friedman和Holden地区的连通性Friedman-Holden方法不包括任何空间数据，可能会出现断开的地区。在下面的内容中，我们将量化FH包装方法无法产生相关（因而合法）区域的失败。

为此，我们将以表2所示的地区为例，输出地区单位的分配，并确定每个地区中连接组件的数量。为了表明通过FH填料构建的区域高度不连通，我们在之前生成的S上取30次FH填料的输出，并计算每个区域（标记为D1至D5）的连接组件平均数和4个基准源点模型的所有区域平均数。结果显示在表4中，图5显示了算法为每个基准模型输出的（30个）地区组成中的一个，从中可以看出，这些地区是高度断开的。D1 D2 D3 D4 D5型平均值#1 2.4 4.9 8.7 1.1 1.4 3.7#2 2.0 8.7 9.0 9.1 1 1.0 6.0#3 4.0 18.2 14.4 12.5 1.0 10.2#4 4.0 16.6 24.1 26.1 6.9 15.5表4：通过我们的FH打包策略算法实施创建的区域的连接组件数。在上述设置下，我们发现Friedman&Holden（2008）的策略通常是将地区划分为O（10）个部分。重要的是，法律禁止断开连接的地区。因此，虽然弗里德曼-霍尔顿方法简单且易于实施，但它过于简单，无法给出一个现实的重新划分模型，并且清楚地表明，算法方法考虑选民的空间分布是至关重要的。我们还注意到，Puppe和Tasnadi【2009年】提出了补充论点，反对从公理化的角度对空间数据进行区分，同时对其进行划分。16预印。带空间限制的布局我们在本节中专门介绍两种新算法，它们以一种非常有利于倡导者的方式在晶格上进行gerrymander-VoterDistribution，并给出最相关的区域：“空间限制的Friedman-Holden”（SRFH）布局和“饱和”布局。

在SRFH包装中，gerrymander旨在确保在大多数地区获胜，但会失去后来建造的（中等）地区，而饱和策略依赖于建造带有明显对手偏见的地区。在第四节中，我们介绍了一种基于遗传算法的新策略。在线提供了我们每个算法的Pythoncodes。A、 空间受限的Friedman-Holden打包我们将在这里介绍空间受限的Friedman-Holden（SRFH）打包算法，它是对FH打包方法的修改，允许包含空间数据。SRFH分区算法首先形成每个分区，包括最强大的对手和支持者未分配的单位，以及它们之间的领土单位路径（必然包括中等选民）。然后，该算法依次添加与形成选区相邻的双方的高度极化单位，直到其满足人口需求，且净投票有利于支持者，即直到选区满足等式（9）和等式（10）。我们首先讨论了地区的总体建设，但最后一个地区除外。假设有x个未分配的领土单位，则与FH算法类似，第一步是通过快速排序，按照减少净投票数vi，jand的顺序对未分配的单位进行排序，并重新标记有序集{T，T···································。如图8所示，为了形成一个新的地区，该算法包括未分配的单位和地区之间的最短路径，避免了所有已分配的地区单位。在确定最短路径时，我们使用标准的Grass-fire算法BIN【1964】删除指定的单元。

如果^和^txe之间的给定路径超过目标总体PD±，则可以选择下一条最短路径，但这通常不是问题。当PDk<PD-该算法将重复向该地区添加未分配且与其相邻的最极端的单位。如果根据投票阈值参数W确定，选区的净投票数不足以支持支持者，则算法将依次向选区添加支持者单位。一旦网络投票有利于支持者，算法会添加对手单位以平衡投票。将每个单元添加到给定地区后，该算法计算当前地区人口PD，并在PD>PD时确定该地区-. 然后检查PD<PD+，如果该检查失败，则添加的最新领土单元将替换为替代相邻单元，直到满足上述条件。在连接集验证为一个地区后，该算法将在剩余的领土单元排序列表上递归以创建另一个地区。该算法通常会按照减少NDk的顺序产生选区，支持者的投票比反对者的投票强。n施工后剩余的未分配单元-1区被分配给最终区，因此最后一个区通常是断开连接的。图10提供了说明该算法步骤的流程图。我们将在第III.C节中量化连接组件的典型数量。格点划分策略研究17图8：左：最极端的支持者和对手单位的一个例子。中心：极端端点之间通过未分配区域的最短路径。右图：考虑添加到该地区的领土单位集（橙色）。B

饱和打包算法下面我们将介绍另一种打包算法，我们称之为饱和打包算法，它实现了将极端选民简单打包到单个紧凑区域的经典策略。饱和打包算法建立在SRFH打包方法的建立算法框架上，但在建设任何地区之前，每个领土单元都会根据其净投票数和与支持者源点的平均距离分配一个优先级值。定义12：对于具有α支持者源点E的领土S，。。。，Eα，我们定义了优先权zi，jof a Territory unit Ti，jto be（11）zi，j：=-vi，j·αα∑i=1d（Ei，Ti，j）。一旦分配了所有优先权，将按照优先权递减的顺序对领土单位列表进行排序，并将排序列表开头具有最大负优先权的领土单位添加到集合D中，最终形成第一个地区。然后，算法搜索与DAD相邻的所有领土单位，并将第二个负优先级单位添加到D。最后一个过程重复，直到PD>PD-. 在通过饱和填充算法构建区域1后，所有后续区域将使用上一节中概述的SRFH填充算法创建。该算法的流程图如图12所示。C、 饱和填充和弗里德曼·霍尔顿填充的示例在第五节中，我们将使用本节中开发的两种算法来进行选区划分方面的蒙特卡罗研究。

然而，首先，考虑一些单独的例子是很有见地的，尤其是查看每个算法为给定选民分布生成的典型地区，类似于图5。图9和图11分别显示了SRFH包装和饱和包装策略的输出示例，其中我们将21×21晶格划分为五个区域，用于表1.18中基准选民模型#1和#4的空间受限Friedman Holden包装的预印样本执行图9：空间受限的Friedman Holden Packing算法应用于表1的Benchmark选民模型#1（顶部）和模型#4（底部），类似于图5，在两个red wins 3区。图10：第III.A节空间受限Friedman-Holden填料的流程图。格里曼德拉策略的格点研究19饱和填料的样本执行图11：在红胜4区，对表1的基准选民模型#1（顶部）和模型#4（底部）应用饱和包装，类似于图5和图9。图12：第III.B.20节中详述的饱和填料流程图注意到，根据设计，除第5区外，创建的区域是连接的，这是对Friedman&Holden[2008]的原始策略的显著改进，该策略通常为每个区域产生平均O（10）组分。

按照与表4类似的方法，采用30条试验，在表5中，我们量化了饱和填料和SRFH填料最终区域中连接组件的数量（“D5”），并说明了所有区域连接组件的平均数量（“平均”），以便与表4进行比较。SRFH型号：D5#SRFH：平均饱和度：D5#饱和度：平均值#1 3.6 1.5 2.8 1.4#2 4.4 1.7 4 1.6#3 5.7 1.9 6.0 2.0#4 8.2 2 2.4 3.9 1.6平均值5 1.9 4.2 1.7表5：5区的平均连接组件数，以及5个区的平均连接组件数和SRFH算法。如第二节所示。C使用基本FH包装方法（不考虑投票者的空间分布），连接组件的平均数量为isO（10）组件（参见表4），而对于具有空间限制的算法，平均值为O（1）。由于组件太少，只需少量的交换就可以在后期处理中实现连接性。此外，在现实环境中，还可以利用地理特征或利用领土外部的空白区域来安排最终区域的连接。关于这些不同分区策略的有效性的研究将在第五节第四节遗传选区划分算法中介绍。在第三节中，我们在Friedman&Holden【2008】的基本策略基础上提出，通过我们称之为饱和和SRFH打包算法的方法，包括空间限制。然而，这些方法都依赖于在不参考全球分配的情况下，为满足当地要求的曼内地区分配领土单位，并且通常最终地区是断开的。虽然可以在算法完成后“固定”最终区域，但这有点不令人满意。

为了解决最终区域仍然不连通的问题，基于遗传算法方法的一般思想，我们在此引入一类新的选区划分算法，我们称之为遗传选区划分（GG）。这种遗传算法不是通过选择特定的地区单元来构建地区，而是通过一系列迭代来实现某个目标。该算法从一些任意的初始“种子”区域集生成许多微小改变的变体（突变），然后为每个区域集计算能力指数，并保留索引值最高的区域集，然后再重复该过程。经过多次迭代，系统会收敛到特定的结果。格点法研究21这种程序的一个显著好处是，由于最初的种子是一组连接的区域，如果在随后的突变中连接得到尊重，那么最终的格点区也将连接起来。据我们所知，遗传算法还没有被应用到如何优化选区划分以提供高度党派性结果的问题上。然而，在利用遗传算法实现公平分配方面已经做了大量的工作，例如【Forman&Yue，2003；Bacao et al.，2005；Chou et al.，2007；Altman&McDonald，2011；Vanneschi et al.，2017】。A、 选区划分指数为了划分选区，需要构建一个支持支持者的能力指数。虽然没有独特的方法来构建这一指数，但任何关于选区划分的良好指数都应该考虑到选区划分党可以赢得的选区数量和人口分布。