后者考虑到确保各地区人口大致相等，以使各地区具有法律效力。我们构建的能力函数取决于这两个质量，如果算法对支持者有利，它允许算法倾斜人口。设W为支持者可赢得的地区数量，由ND>W的地区数量加上一半的竞争地区（ND<W的地区）（12）W给出=∑i“Θ（NDk-w）+∑iΘ（NDk）-∑iΘ（NDk-w） ！#，其中，Θ是HeavisideΘ函数。我们还确定了以下人口指标（13）g：=PS最大值1≤我≤n（PDk）- 最小1≤我≤n（PDk）.数量W和量度g表征了给定地区规划的显著属性，以划分选区，并利用这些特征，我们定义了以下划分选区指数，由获胜地区的比率减去人口分布：（14）g：=Wn-g，指数g取区间[0，1]中的值，对于能力指数最高的地区组，老年人最理想的结果出现。我们考虑的指数G非常简单，仅由两个参数定义，其中一个当然可以构建更复杂的指数，但这种简单的形式足以探索在给定领土上划分选区的前景。然而，确定用于划分选区的高效指标将是未来工作中一个有趣的问题。22预印本B。

我们的突变程序在amanner的每次迭代中在相邻区域之间交换某些单元，从而保持每个区域的连通性，并有利于平衡种群。定义13：对于D区的领土单位T，如果存在T，则D区（D 6=D）被称为T的相邻区∈ D是T的相邻单位。为了描述在突变过程中领土单位切换到不同相邻地区的倾向，我们定义了以下定义14：不稳定的Li，jof a Territory unit Ti，jin district D为零ifD-Ti、jis未连接。否则，Li，j：=最大值（PD-PD）在所有地区，Dadjacentto Ti，j。根据上述定义，如果给定的领土单位Ti，j与其相邻的每个领土单位位于同一地区，则Li，j=0和Li，j6=0仅适用于地区之间边界上的领土单位。为了实现突变过程，我们首先确定每个Ti，j的不稳定性Li，j∈ S和我们定义M：=所有Ti，j上的最大值【Li，j】∈ S、 23所有Ti，j的格点划分策略研究∈S当Li，j>0时，T上的突变以概率Li，j/M进行，从旧区中移除Ti，j，并将Ti，jt添加到与Ti，j相邻的最低人口区。这种领土单位的转移将始终使地区人口更加平衡，因此投票区很快变得更加公平。总之，一组N个种子区域形成了第1代，然后我们的算法对第1代执行以下迭代过程：它确定√N个案例（适当四舍五入）的G指数最高√N种情况下，应用置换程序√N次。由于突变的概率性质，这产生了N个不同的后代，包括i+1代。

随着每次迭代，区域集朝着G的局部最大值发展。在预设的一组迭代次数后，算法输出具有最终生成的最佳G指数的区域集。通常，在O（10）次迭代之后，算法收敛到G’1的集合。我们在图14中提供了该算法的流程图说明。D、 遗传GerryManderingf的样本执行对于我们的示例运行，我们为第一代构建N=100个

然而，在我们的遗传选区划分算法中开发的遗传启发式和变异程序是独特的和原始的，有趣的是，至少在我们简化的晶格模型中，公平区可以很容易地根据我们下面规定的简单直观的标准来构建。虽然公平是一个主观概念，但我们可以通过一个启发式公式构建一个合理的能力指数，该公式考虑到：i）地区人口平衡；ii）州在国会代表的准确性；iii）每个地区的表示准确性。24遗传GerrymanderingFigure 13的印前样本执行：表1的基准模型#1（顶部）和模型#4（底部）采用了遗传性选区划分，类似于图5、9和11，这两个地区都是红胜3区。图14：第四节遗传选区划分算法流程图。选区划分策略的格点研究25我们通过功能函数fP、fS、fD：（16）fP：=1分别量化这三个特征-g、 fS：=1-1+NSPS-西尼罗河,fD：=nn∑i=1QDkPDk，式（12）和（13）中定义了W和g，我们用QDa度量给定地区的人口比例D=∪（i，j）∈ITi，j（针对指数集I）whosevote PREFESSION vi，jaligns（地区净投票数ND），定义人：（17）QD：=∑（i，j）∈IPi，j·（1+符号[vi，j]·符号[ND]）。还要注意的是，虽然g衡量的是人口分布，但这里FP描述的是人口平衡。使用部分能力函数，我们将整体“公平”能力F定义为（18）F：=fP+fS+fD-,其值位于区间[0,1]内。被视为“最公平”的地区应拥有最高的能力指数。通常在我们的试验中，我们发现最后一组集市区的能力指数值往往超过F>0.9。图15：。

：通过修改后的GG建设7个公平区，用于公平重新划分，适用于21×21的地区，具有平衡投票和两个来源点（位置如表1的模型#1所示）。演示类似于图5.26预印本。我们将配备指数F（而非G）的遗传选区划分（GG）算法称为“用于公平重新划分的修改GG”。按照第IV.D节的相同方法，我们使用N=100个种子配置执行示例运行，并进行30次迭代。图15显示了七个地区的该示例运行结果。特别是，根据设计，修改后的GG为公平重新划分而产生的公平地区配置支持50%-平衡选区（balancedterritories）50%的选票分成两半，准确地代表了整个地区的选民偏好。此外，大多数地区避免包括对立的两极分化选民，确保每个当选的地区代表反映其选民的价值观。五、 结果通过这里开发的算法，我们将量化一些关于动名词划分的一般陈述。为此，我们考虑将一个21×21格划分为n=5个区域，人口为PS≈ 4700和选民分布如表1所示。在所有情况下，人口和投票阈值固定为t=0.05×PS/n和w=5。由于人口分布固有的随机性，我们可以使用第三节和第四节中开发的具有空间限制的重新划分算法输出的区域，通过蒙特卡罗方法研究选区划分的各个方面。

具体而言，我们为五个地区的情况生成了一大组无政府区，并进行了统计分析，以量化无政府区给提案方带来的优势以及无政府区的其他特征。虽然之前已经使用蒙特卡罗方法来检测选区划分，例如【Herschlag，2018；Herschlag et al.，2017】，以及构建公平区，例如【Fifield et al.，2015】，但据我们所知，这是首次应用蒙特卡罗方法来量化选区划分的一般特征。A、 不同选区划分策略的量化影响。gerrymanderer的主要目的是最大限度地增加选举期间预计的选区数量。第二个目标是与ND建设支持者区 0和以ND排列对手地区≈ 0，这样所构建的地区就不会受到投票偏好的潜在波动的影响，并且可以利用有利于他们的波动来挑选更多的地区。为了评估选区划分的影响，我们将上文开发的每个选区划分算法的预测选举结果与第二节中概述的无党派对称划分模型进行比较。如图7所示。对称分配模型的预测选择结果如表3所示。

首先采用SRFH打包算法，并遵循与第二节类似的方法。B我们在S上生成30个人口分布，并计算每个地区的平均净投票数和支持者的平均地区获胜数（#win）：格点研究选区划分策略27模型ND1ND2ND3ND4ND5#win#1 13.8 5.9 3-6.3-16.6 3#2 15.8 7.2 5.7-14.8-14.2 3#3 12.6 13.2 9.7-2.4-31.6 3.2#4 9 26.0 5.9-0.2-45.7 2.8表6：SRFH后的平均地区投票第III.A.SRFH节的包装——当对立极端选民彼此非常接近时，包装最有效。这种方法处理模式#4的选民分布的效果明显较差（从#win<3这一事实可以看出），而且尽管有利于支持者党，但反对者在30%的试验中占据了大多数选区。在通过饱和填充进行选区划分的情况下，我们发现，虽然不明显，但它可以非常有效地确保地区的投票平衡：ND1ND2ND3ND4ND5型#win#1-187 136 32 11 8 4#2-338 219 45 25 48 4#3-438 65 207 63 102 4#4-222 11 128 15 68 4表7-：第III.B节饱和填充后的平均地区投票，我们考虑了遗传选区划分算法的应用，每次选举后，我们按照净投票数的顺序（在计算地区平均数之前）对地区进行标记：模型ND1ND2ND3ND4ND5#win#1 36.9 12.3 0.8-12.1-37.5 2.7#2 117 57 16-54-137 2.7#3 232 116-4 113 232 2.5#4 130 53 5-59-119 2.5#表8：第四节遗传选区划分算法后的地区平均投票数。因为在上述每种情况下，地区投票接近平衡的NS≈ 0，在公平选举中，支持者选区的预期平均获胜人数为#win≈ 2.5. 对于对称源的对称分区，表3中的情况就是这样。

然而，正如预期的那样，对于我们的算法生成的不规则选区，一个观察到的清晰偏向于支持者。具体而言，SFRH包装（表6）使支持者始终赢得60%的地区，饱和包装（表7）使支持者赢得了令人印象深刻的80%的地区。遗传性选区划分（表8）的效果较差，但仍然可以为只有两个来源点的选民模型提供支持者优势。28预印本B。紧凑性测试——划分选区最明显的特征之一是，它通常会导致高度非凸或非紧凑的区域。受这一共同特征的激励，研究人员【Roeck，1961；Schwartzberg，1966；Oxtoby，1977；Young，1988；Niemi et al.，1990；Polsby&Popper，1991；Chambers&Miller，2010；Hodge et al.，2010】提出了几何测量方法，可以潜在地用于识别不公正划分。应该注意的是，简单的几何测试虽然直观，但确实有某些缺点。例如，theyoften不考虑自然或法定边界（如海岸线或国家边界）导致的地区边界变化，也不包含人口分布或人口统计信息。无论如何，计算我们工作中出现的划分选区的几何测量值是很有意思的，以确定哪些指数值可能表示有侵略性的划分选区。我们将研究最直观的无量纲动植物区划量度：等周商指数【Polsby&Popper，1991】，定义为（19）ID：=4πAP，适用于面积a和周长P的D区。该指数被标准化为圆，而区域与圆的偏差给出ID<1。

在表9中，我们给出了通过遗传性别划分产生的每个地区的平均IDforeach district（在每次跑步后以上升的NDA标记地区）以及所有地区平均超过30次跑步的平均IDforeach district。模型ID1ID2ID3ID4ID5Iaverage#1 0.5 0.46 0.35 0.40 0.42 0.43#2 0.41 0.37 0.37 0.40 0.48 0.41#3 0.45 0.39 0.37 0.39 0.39 0.5 0.42#4 0.37 0.40 0.40 0.46。为了证明遗传Gerrymanderingalgorithm生成的区域可能被等轴测商测试检测和约束，我们将表9中的Id值与第二节理想化无党派对称区域计算的等轴测商进行比较。B、 这些在表10中给出。ID1ID2ID3ID4ID5Iaverage#1-#4 0.40 0.71 0.71 0.71 0.65表10-：理想化无党派对称地区的等周商指数无党派划分策略研究29因为理想化无党派对称地区遵循简单的几何构造规则，而不参考选民分布，在模型1到4中发现了相同的ID值（在人口分布中的变化可以忽略不计）。从上述分析中，我们发现，我们的划分选区方法总是导致平均碘缺乏症，比对称的“公平”地区低得多（约33%）。此外，一些按性别划分的地区的ID值非常低，例如模型1中3区的平均值为I（#1）D3≈ 0.35，小于ID为的典型对称区域的等周商的一半≈0.71.

我们的结论是，通过我们的遗传选区划分算法构建的选区划分通常是高度非紧凑的选区，以实现选民的真实分布。我们的研究结果表明，如果重新划分选区受到紧凑性约束的限制，那么人们对选举的影响程度将大大降低，许多激进的选区划分方法（尤其是我们自己的方法）可能会被证明无效。因此，这进一步支持了民主ZF对重新划分方案提出某种形式的紧凑性要求的需要，并补充了ine中提出的类似论点和发现。g、 【Schwartzberg，1966年；Polsby&Popper，1991年；Altman，1998年；Hodge et al.，2010年；Humphreys，2011年；Chou et al.，2014年；Bowen，2014年；Chen&Rodden，2015年】六、总结与结论向选民分配权力是代议制民主的根本力量。政治上的不公正划分选区，如果不加以制止，可能会破坏民主制度。由于划分选区的问题可以像表述良好的数学问题一样表述出来，人们可以开发工具和测试来识别和禁止这种做法。我们提出了许多研究选区划分的工具，并用这些工具来检验选区划分的核心问题。发展了一个人口分布的格模型，我们提出了几种算法来将格区域划分为无规则、等人口、连通（或大部分连通）的区域。我们使用我们的晶格模型来论证Friedman&Holden[2008]的方法是不现实的，因为它通常会导致断开的区域。然而，包装和破解技术仍然是划分选区的核心工具，我们在构建自己的算法方法时也采用了这些思想。

为此，我们开发了三种新的格格划分算法，SRFH填充、饱和填充和遗传格格划分，这些策略的执行示例如图9、11和13所示。我们的选民模型固有的概率人口波动允许我们采用蒙特卡罗方法来研究我们的选区划分算法的有效性。我们发现，将反对派选民塞进少数选区的直率策略“饱和填充”，是确保选区均衡投票的最有效方式。此外，与SRFH填料相比，我们的饱和填料算法导致的最终断裂区域更少，成分减少约25%。遗传性选区划分被认为是我们最完整的算法，因为它输出的是与平衡人口相连的地区，这通常是法律上有效的要求，然而，所有地区保证连通性的代价是显著降低选区划分者的30预印优势。事实上，遗传选区划分算法并不总能确保平衡投票的选举胜利，但它可以使领土倾向于支持简单选民分配的支持者。这些较弱的结果可能是由于遗传算法过早收敛到局部最优解，在未来的工作中，我们将面对这个问题，构建更具攻击性的遗传不规则划分算法。我们的算法还有其他一些值得探索的扩展，例如加入第三方候选人和无投票权选民。此外，我们当前的算法假设完全了解人口分布和选民偏好，但实际上，gerrymanderer对这些分布的信息不精确，这导致选民偏好分布的不确定性。

通过允许每个vi、JT具有一些概率函数，可以实现VoterUnderacity。正如弗里德曼和霍尔顿（Friedman&Holden）[2008]所讨论的那样，在重新划分完成后，也可以实施“选民冲击”，以模拟民众投票的波动（10%）。这两种延期都会直接影响所需的投票阈值w，因为如果重新划分期间的w不够大，支持者可能会输掉选举。此外，有兴趣将这里开始的工作扩展到更系统地研究不同的人口分布和党派偏见的传播，以确定可能更容易出现选区划分的选民分布。我们使用我们的选区划分算法的结果，从经验上证明选区划分为选区划分者的政党提供了明显的优势，并且我们的算法输出的党派关联地区通常无法通过等周商测试。值得注意的是，虽然连通性是法定的，但紧凑性却不是。因此，这项工作进一步支持实施一些法定的契约要求，以重新划分选区，抑制政治上的选区划分。ReferencesAltman，M.（1998）模拟了强制性地区紧凑性对党派成员的影响。政治地理学17.8（1998）：989-1012。Altman，M.和McDonald，M.（2011），《巴德：更好的自动重新划分》，统计软件杂志，第42（2011）4条。Apollonioa，N.et al.（2009）《双色图划分，或：最差的不规则划分》，离散应用数学，第157卷，第17期，第28期（2009），3601。Bacao，F.、Lobo，V.和Painho，M.（2005）将遗传算法应用于区域设计。软计算9.5（2005）：341-348。Benisek v.Lamone，《美国判例汇编》第585卷第17-333页（2018年）。铌，H。

（1964）麻省理工学院出版社（1964）关于提取形状新描述的转换，语音和视觉形式感知的研讨会模型。Bowen，D.C.（2014）《边界、重新划分标准和美国众议院的代表权》。《美国政治研究》42.5（2014）：856-895。《格点格研究中的选区划分策略》（LATTICE STUDIES OF GERRYMANDERING STRATEGIES）31Castellano，C.、Santo F.和Vittorio L.（2009）《社会动力学统计物理学》。《现代物理学评论》81.2（2009）：591。钱伯斯，C.P.和米勒A.D.（2010）《奇异的衡量》，政治学季刊5（1）（2010），27-44。Chen，J.和Rodden J.（2015）《穿过灌木丛：重新划分模拟和党派不平等者的检测》。《选举法杂志》14.4（2015）：331。周，中情局局长和李。S、 -P.（2006）《驯服gerrymander：政治区划问题的统计物理学方法》。Physica A 369.2（2006）：799-808。周，中情局局长，朱。Y、 ，和李。S、 -P.（2007）《基于遗传算法的政治区划问题进化策略》。计算科学国际会议。施普林格，柏林，海德堡，2007年。Chou，C.，et al.（2014）关于选举限制紧凑性度量的实证验证及其对社会科学模型应用的意义。《社会科学计算机评论》32.4（2014）：534-543。Duchin，M.（2018）《选区划分指标：如何衡量？基线是多少？arXiv:1801.02064。Fifield，B.，et al.（2015）使用马尔可夫链蒙特卡罗的新自动重新划分模拟器，工作。Pap。，普林斯顿大学，普林斯顿，新泽西（2015）。Friedman，J.N.和Holden，R.T.（2008）《最佳选区划分：有时拥挤，但从不破裂》，《美国经济评论》（2008），98:1113-144。Forman、S.L.和Yue。Y、 （2003）使用基于TSP的遗传算法进行国会分区。遗传和进化计算会议。

施普林格，柏林，海德堡，2003年。Giansiracusa，N.和Ricciardi C.（2017），《法庭几何》，预印本arXiv:1709.05662Gill v.Whitford，《美国判例汇编》第585卷第16-1161页（2018年）。Glassner，A.S.（2013）《图形宝石》。爱思唯尔。Herschlag，G.，Ravier R.，Mattingly J.C.，评估威斯康星州的党派划分选区，预印本arXiv:1709.01596（2017）。Herschlag，G.等人，《量化北卡罗来纳州的选区划分》，印前十四期：1801.03783（2018）。Hoare，C.A.R.（1961）算法64：快速排序，Comm.ACM。4 (7): 321 (1961).Hodge，J.、Marshall，E.和Patterson，G.（2010）《格里曼德现象和凸性》，《大学数学杂志》第41卷，第4期（2010），第312-32432页预印本Humphreys，M.（2011）紧凑性能约束格里曼德现象吗？。爱尔兰政治研究26.4（2011）：513-520。Niemi，R.G.、Groffman，B.、Calucci C.和Hofeller，T.（1990）测量紧凑性和紧凑性标准在党派和种族划分选区测试中的作用，《政治杂志》52:1155。Macal，C.M.和North M.J.（2005）基于代理的建模和仿真教程。模拟会议，2005年冬季会议录。IEEE，2005年。Miller v.Johnson，《美国判例汇编》第515卷第900页（1995年）。Oxtoby，J.（1977）《弧的直径与选区划分问题》，《美国数学月刊》，第84卷，第3期（1977），第155-162页Polsby，D.和Popper，R.（1991）《第三个标准：紧凑性作为防止党派选区划分的程序保障》，《耶鲁法律与政策评论》，第9301页。Puppe，C.和Tasnadi，A.（2009）《地理约束下的最优重新划分：为什么“打包和破解”不起作用》，《经济学快报》105.1（2009）：93。Roeck，Jr.，E.C.（1961），《将紧凑性作为立法分配的要求进行衡量》，《中西部政治学杂志》，5（1961），70-74。Shaw v.Reno，《美国判例汇编》第509卷第630页（1993年）。施瓦茨伯格，J.E。

（1966）《重新分配、选区划分和紧凑性的概念》，明尼苏达州法律评论，50（1966），443-452。Sherstyuk，K.（1998）《如何划分选区：正式分析》，公共选择95，27。Shiffman，D.（2012）《代码的性质：通过处理模拟自然系统》（2012），ISBN-13:978-0985930806。Smith，A.R.（1979）。Tint Fill，SIGGRAPH’79会议记录，279？283.Vanneschi，L.、Henriques，R.和Castelli，M.（2017）《多目标遗传算法与可变邻域搜索，用于选举重新划分问题》。Swarmand进化计算36（2017）：37-51。Wall，J.F.（2008）《考虑复杂网络中的意见动态和社区结构：模拟选举和选区划分的观点》。(2008).Wang，S.S-H.（2016）党派划分选区实践评估的三项测试。斯坦。五十、 修订版。68 (2016): 1263.Warrington，G.S.（2018）《选区划分指标的比较》，印前十四期：1805.12572。Young，H.P.（1988）《衡量立法区的紧凑性》，《立法研究季刊》第13卷第1期（1988），第105-115页