Как работает инструмент Построить сбалансированные зоны

Инструмент Построить сбалансированные зоны использует генетический алгоритм для построения пространственно непрерывных зон в области изучения, на основании указанного критерия. Вы можете построить зоны, содержащие одинаковое число объектов, совпадающие по набору атрибутивных значений, или и то, и другое. Есть также опции выбора зон приблизительно одинаковой площади, настолько компактных, насколько возможно, с сохранением суммарной статистики (например, среднего или пропорций) остальных переменных.

Примеры сценариев

Этот инструмент можно использовать в следующих типах сценариев:

• Предприятие розничной торговли хочет выделить районы, в которых каждый менеджер отвечает за равный объем продаж и одинаковое количество сотрудников, независимо от количества магазинов в каждом районе.

• Изменение климата способствует увеличению количества лесных пожаров в год во многих районах, что приводит к росту расходов в этих регионах. Местные и национальные органы власти могут использовать этот инструмент для выравнивания как рабочей нагрузки, так и затрат на борьбу с пожарами путем создания административных районов.

• Можно создать дополнительные районы полицейского патрулирования для баланса рабочей нагрузки и распределения вызовов между офицерами. Путем балансировки индекса уровня преступности можно уравновесить избыток или недостаток персонала в округах для обеспечения своевременного и эффективного реагирования.

Определение критериев построения и выбора зон

Чтобы инструмент построил оптимально сбалансированные зоны, необходимо предоставить критерий, определяющий оптимальность зоны. Существует два типа критериев: критерий построения зон и критерий выбора зон. Инструмент балансирует зоны, чередуя построение зон и выбор зон, а критерий, заданный для каждого шага, определяет конечные сбалансированные зоны, рекомендуемые инструментом.

На этапе создания зоны создается множество зон, которые формируются случайным образом до тех пор, пока не будут удовлетворены критерии построения зоны. Критерий построения зоны должен рассматриваться как необходимое условие для формирования зоны, и все зоны будут расти таким образом, чтобы соответствовать этим критериям (более подробно о том, как формируются зоны, см. раздел Нарастание зон с помощью Генетического алгоритма). Далее осуществляется этап выбора зоны, когда каждый набор зон ранжируется и выбираются лучшие зоны на основе их соответствия критериям выбора зоны. В целом, критерии выбора зон должны рассматриваться как предпочтения, а не требования, они используются для выбора зон, которые уже соответствуют критериям построения зон.

Выбор критериев, которые должны использоваться для построения и выбора зон, зависит от ваших задач и условий, и следующие опции параметра Метод создания зон помогут вам правильно определить эти критерии:

• Целевой атрибут – Каждая зона будет иметь примерно одинаковую общую сумму атрибута, и эта общая сумма должна быть указана. Число созданных зон зависит от общей суммы атрибута. Например, этот параметр можно использовать для создания областей обслуживания, содержащих около 1000 клиентов. Если входные объекты включают 5 000 клиентов, будет создано около 5 зон, каждая из которых будет содержать около 1000 клиентов. Для двух миллионов клиентов будет создано около 2000 зон, каждая из которых будет содержать около 1000 клиентов.

• Определенное число зон — Число зон должно соответствовать указанному числу, и каждая зона будет состоять из примерно одного и того же количества объектов. Эта опция полезна, когда вы знаете, сколько зон вам нужно, и вы хотите, чтобы каждая зона содержала одинаковое количество входных объектов.

• Число зон и целевой атрибут – Объединяет две предыдущих опции путем балансирования между суммой атрибута и определенным количеством зон. Например, эту опцию можно использовать для создания ровно 20 областей обслуживания, которые имеют примерно одинаковый объем продаж в каждой зоне. Для этой опции не указывается требуемая сумма атрибутов, поскольку она определяется путем деления общей суммы атрибутов на число зон. Эта опция не выравнивает число объектов в каждой зоне (однако в качестве критерия выбора зоны можно указать предпочтение равному числу объектов, как описано далее в этом разделе).

• Пользовательские начальные местоположения — каждая зона будет формироваться из фиксированного набора начальных местоположений, определяемого параметрами Точки начальных местоположений и Входные объекты. Общее количество создаваемых зон определяется количеством начальных местоположений. Количество начальных местоположений определяется на основе точек начальных местоположений и входных объектов следующим образом:

  • Если входными объектами являются полигоны, то в качестве начальных местоположений будут выбраны полигоны, пересекающиеся с точками начальных местоположений. Зоны будут расти из этих начальных местоположений за счет агрегирования соседних объектов.

  • Если входные объекты – это точки, то начальными будут выбраны точки, ближайшие к каждой точке начального местоположения.

  Вы можете указать дополнительные переменные и их веса с помощью параметра Критерии построения зон.

  Выберите эту опцию, если у вас есть фиксированные местоположения, вокруг которых должны строиться зоны. Например, можно создать противопожарную защитную зону вокруг существующих пожарных съездов.

Критерии построения зон

Для каждой опции параметра Метод создания зон существуют различные критерии построения зон, и все зоны формируются до тех пор, пока они не будут удовлетворять этим критериям.

• Целевой атрибут – Вы должны указать атрибут, который хотите сбалансировать, и указать сумму в параметре Критерий построения зон с целевым атрибутом. При необходимости можно задать несколько атрибутов с различными суммами и назначить каждому из них вес, чтобы некоторые атрибуты имели более высокий приоритет при выборе местоположений с наименьшими оценками жизнеспособности.

• Заданное число зон — Вы должны указать число зон с помощью параметра Целевое число зон.

• Число зон и целевой атрибут – Вы должны указать число зон в параметре Число зон и атрибут для балансировки в параметре Критерий построения зон. Вы можете снова указать несколько атрибутов и веса для расстановки приоритетов.

• Пользовательские начальные местоположения — необходимо указать начальные местоположения, от которых будут строиться зоны, в параметре Точки начальных местоположений. Количество зон будет определяться как количеством точек начальных местоположений, так и входными объектами. Вы можете указать дополнительные переменные и их веса с помощью параметра Критерии построения зон.

Критерии выбора зон

Критерии выбора зон - это дополнительные опции, которые позволяют указать предпочтения между зонами, созданными на этапе построения зон. Эти критерии используются вместе с критериями построения зон для определения зон, которые в конечном итоге будут предложены инструментом. Большинство критериев выбора зон применимы ко всем опциям параметра Метод создания зон. В следующих разделах описываются все опции выбора зон и их применение.

Критерии характеристики зон

Опции параметра Характеристики зон в основном относятся к размеру и форме зон. Вы можете использовать любую или все из следующих опций:

• Равная площадь - Предпочтение отдается близким по площади зонам. Эта опция применяется только в том случае, если входные объекты являются полигонами.

• Компактность - Предпочтение отдается зонам, близким по форме к окружностям. Эта опция применима всегда.

• Равное число объектов - Предпочтение отдается зонам, состоящим примерно из одинакового количества объектов. Эта опция не применяется при использовании опции Определенное число зон, так как этот метод создания зон уже обеспечивает равное число объектов в качестве критерия построения зон.

Критерии согласования атрибутов

Параметр Атрибуты для согласования позволяет указать, какие атрибуты, не используемые в качестве критериев построения зон, нужно дополнительно принимать во внимание. Это позволяет включать зоны, имеющие одинаковую сумму, среднее значение, дисперсию или медиану атрибута. Можно задать несколько атрибутов, например, включить зоны с одинаковой общей численностью населения (суммой) и приблизительно одинаковым средним показателем доходов (медианой).

Этот критерий выбора применяется ко всем методам создания зон. Атрибуты, используемые в данном параметре, должны быть непрерывными, а не категориальными.

Сохранение пропорций категорийных переменных

Параметр Категорийная переменная для сохранения пропорций позволяет указать категорийную переменную, которая будет использоваться для балансировки пропорций категорий в зонах. Необходимо также выбрать Метод пропорций, чтобы указать, как пропорции должны быть сбалансированы. Предусмотрены следующие методы пропорции:

• Сохранение внутренней пропорции - Предпочтение отдается зонам, которые имеют одинаковые относительные пропорции категорий в пределах каждой отдельной зоны. Например, если категорийная переменная, которую вы используете для сохранения пропорций, представляет двоичную классификацию лесного и не лесного земельного покрова, и 60 процентов объектов имеют тип лесного земельного покрова, а 40 процентов - не лесного, то эта опция предпочтет зоны, где каждая отдельная зона состоит на 60 процентов из лесного земельного покрова и на 40 процентов из не лесного.

• Сохранение общей пропорции - Зоны будут созданы таким образом, чтобы пропорции доминирования категорий соответствовали общим пропорциям категорий. Например, если категорийная переменная указывает, находится ли объект на суше или на воде, и 60 процентов объектов находятся на суше, эта опция предпочтет зоны, где около 60 процентов зон находятся преимущественно на суше и 40 процентов зон находятся преимущественно на воде.

Этот критерий выбора применяется ко всем методам создания зон. Атрибуты, используемые в данном параметре, должны быть категорийными, а не непрерывными.

Критерии, основанные на расстоянии

Параметр Расстояние согласования позволяет выбрать зоны, близкие к другому набору объектов (или нескольким наборам объектов). Например, если вы строите административные районы здравоохранения, вы можете предпочесть зоны, близкие к существующим больницам. Расстояние между зоной и пространственным объектом определяется медианным расстоянием от всех пространственных объектов в зоне до ближайшего объекта, указанного в качестве расстояния согласования.

Сценарии для критериев выбора зон

Существует множество доступных опций для критериев построения и выбора зон, и может быть не сразу понятно, какие параметры использовать, чтобы учесть ваши требования и предпочтения для формирования зон. Ниже приведены несколько сценариев и параметры, которые следует в них использовать.

Сценарий 1: Распределение объектов недвижимости по риэлторам

Вы аналитик в агентстве недвижимости. У вас есть класс объектов со всеми доступными объектами недвижимости и их стоимостью. В вашем агентстве 12 риэлторов, и вы хотите распределить объекты недвижимости так, чтобы каждый риэлтор получил равное количество объектов, а общая стоимость недвижимости в каждой зоне была примерно одинакова. Вы также хотите, чтобы зоны были близки к существующим филиалам агентства недвижимости.

Для этого можно использовать опцию Число зон и целевой атрибут в параметре Метод создания зон. Укажите 12 для параметра Целевое число зон (по одному для каждого риэлтора) и выберите поле, представляющее стоимость каждого объекта, в параметре Критерии построения зон. Выберите опцию Равное число объектов в параметре Характеристики зон, чтобы отдать предпочтение зонам, где каждому риэлтору назначено приблизительно равное количество объектов. Чтобы учесть расстояние до ближайшего филиала агентства недвижимости, укажите в параметре Расстояние согласования класс объектов, представляющий местоположения филиалов.

Сценарий 2: Создание новых границ районов

Создание новых границ районов, которые имели бы сбалансированную численность населения внутри каждого района, является сложной и трудной задачей, часто возникающей почти на всех уровнях власти. Используя демографические данные, собранные в небольших районах, вы хотите создать районы, в каждом из которых проживает около 10 000 человек. Кроме того, по демографическим данным примерно 75 процентов населения проживает в городах и 25 процентов в сельской местности. Вы хотите, чтобы около 75 процентов зон были преимущественно городскими, а около 25 процентов - преимущественно сельскими, чтобы правильно представлять каждую группу.

Для этого вы можете использовать опцию Целевой атрибут в параметре Метод создания зон. Выберите поле, отражающее количество людей в каждом небольшом районе, и укажите 10 000 в параметре Критерий построения зон с целевым атрибутом. Выберите поле, указывающее, является ли район городским или сельским, в параметре Категорийная переменная для сохранения пропорций и выберите опцию Сохранение общей пропорции в параметре Метод пропорций.

Сценарий 3: Распределение рабочей нагрузки между инспекторами по надзору за условно-досрочно освобожденными

Вы являетесь аналитиком ГИС для отдела правоохранительных органов, и вам было поручено сбалансировать нагрузку 25 инспекторов по надзору за условно-досрочно освобожденными. У вас есть местоположения всех правонарушителей в городе вместе с численной оценкой риска каждого правонарушителя, и вы хотите разделить их поровну между каждым из инспекторов по надзору за условно-досрочно освобожденными, сохраняя общий риск правонарушителей примерно одинаковым. Однако баланс риска не столь важен, как одинаковое количество правонарушителей, закрепленных за каждым инспектором по надзору за условно-досрочно освобожденными. Кроме того, вы хотите создать максимально компактные зоны, чтобы сократить время, затрачиваемое инспекторами по надзору за условно-досрочно освобожденными на дорогу.

Для этого можно использовать опцию Определенное число зон в параметре Метод создания зон и указать 12 для параметра Целевое число зон. Укажите поле, отражающее уровень опасности каждого нарушителя, в параметре Атрибуты для согласования и выберите опцию Компактность в параметре Характеристики зон, чтобы создать компактные зоны.

Сценарий 4: Создание сбалансированных зон экстренного реагирования на основе существующих пожарных станций

Вы работаете ГИС-аналитиком в городском департаменте по чрезвычайным ситуациям, и вам необходимо определить зоны обслуживания для пожарных и бригад скорой помощи. В городе уже есть пожарные части, и каждая из них должна использоваться как фиксированное начальное местоположение для зоны реагирования.

У вас есть данные о кварталах переписи населения и потребности в реагировании на происшествия, и вы хотите распределить эти территории между пожарными станциями так, чтобы на каждую станцию приходилась примерно одинаковая общая нагрузка, например численность населения и исторический объем вызовов. Хотя балансировка нагрузки имеет большое значение, также крайне важно, чтобы до каждой зоны можно было добраться от назначенной пожарной станции за приемлемое время реагирования. Поэтому зоны должны быть географически компактными, чтобы сократить расстояние перемещения и повысить эффективность реагирования.

Для этого можно использовать опцию Пользовательские начальные местоположения параметра Метод создания зон и указать местоположения пожарных станций в качестве точек начальных местоположений. Укажите поля, представляющие численность населения и общий объем вызовов, в параметре Критерии построения зон, а в параметре Характеристики зон задайте приоритет компактности. Это обеспечивает расширение зон от каждой пожарной станции, сохранение их пространственной целостности и максимально равномерное распределение нагрузки с учетом фиксированных местоположений пожарных станций.

Нарастание зон с помощью Генетического алгоритма

Используя критерии, заданные для построения и выбора зон, инструмент Построить сбалансированные зоны создает оптимальные зоны с помощью Генетического алгоритма (ГА), учитывая пространственные ограничения входных объектов.

ГА основан на эволюционной теории естественного отбора и генетики, впервые описанной Чарльзом Дарвином. Согласно Дарвиновскому принципу выживания наиболее приспособленных, такие организмы в популяции имеют тенденцию к выживанию и производству потомства.

Так как число возможных решений обычно очень велико, ГА подбирает оптимальное решение, начиная с поиска случайного решения, и постепенно продвигаясь к более перспективным направлениям. Оптимизация методом ГА является абстрактным воплощением биологической эволюции в живой природе, то есть, каждое возможное решение (в нашем случае, каждая возможная комбинация зон) аналогично отдельному организму в популяции. По мере роста поколений выживают только самые приспособленные особи – и, аналогично, продолжаются только наиболее результативные направления поиска.

Этот алгоритм начинается с создания случайной популяции, где каждая особь является возможным решением. Для каждого решения вычисляется оценка жизнеспособности, и особи с меньшим значением оценки (наилучшие решения) в существующей популяции переходят в следующее поколение, а оставшиеся решения удаляются. Наиболее приспособленные особи назначаются родителями и могут создавать потомство в парах с помощью таких генетических операторов, как кроссовер (скрещивание) и мутация. Каждое новое поколение представляет собой сочетание наиболее приспособленных особей предыдущего поколения и их потомства. Иногда особи, не являющиеся ни родителями, ни потомством (называемые пришельцами) случайным образом вводятся в следующее поколение, чтобы расширить диапазон возможных решений, обнаруженных алгоритмом. Оценка жизнеспособности вычисляется для всех особей в каждом новом поколении, и процесс повторяется в соответствии с заданным числом поколений (по умолчанию, 50 поколений). Наиболее приспособленная особь последнего поколения соответствует сбалансированным зонам, которые возвращает инструмент.

Выбор исходной популяции

Исходная популяция для алгоритма формируется путем случайного выбора объектов в исследуемой области или с использованием пользовательских начальных местоположений. По умолчанию популяция считается состоящей из 100 особей, но число можно изменить в параметре Размер популяции. Каждый случайно выбранный объект является стартовым местоположением (называемым источник), с которого начинается распространение зоны на соседние объекты. Зона продолжает агрегировать соседние объекты и расти, до тех пор, пока общее значение не приблизится к пороговому значению критерия построения зон. Например, если вы указали размер популяции - 100 000 и число домохозяйств - 50 000, в качестве критерия построения зон, значения 100 000 и 50 000 являются пороговыми значениями для размера популяции и числа домохозяйств, соответственно, и рост зон остановится по достижении этих значений. Для следующей зоны выбирается источник за пределами первой зоны, и с него начинается рост следующей зоны. Процесс продолжается, пока всем объектам не будет назначена та или иная зона.

В биологии генетический материал особей зашифрован в хромосомах. Хромосомы состоят из генов, которые хранят наследуемый материал. Для этого инструмента возможное решение - аналог хромосомы, а источники - аналогичны отдельным генам. Эти гены передают наследуемую информацию от родителей к потомству, а оно, в свою очередь, последующим поколениям. На рисунке ниже показан пример возможного решения вместе со значениями Object ID источников каждой зоны в решении:

Вычисление оценки жизнеспособности

Оценка жизнеспособности каждого возможного решения – измерение, насколько точно результирующие зоны соответствуют различным критериям построения и выбора зон, указанным в инструменте, и чем ниже значение оценки, тем лучше решение соответствует критерию. То есть, наша цель – найти решение с низким показателем жизнеспособности (в идеале — с минимально возможным показателем жизнеспособности, который называется глобальным минимумом). Оценка жизнеспособности возможного решения вычисляется с использованием следующей формулы:

\[ \text{Fitness Score of a possible solution} = \sum_{i=1}^{n} \sum_{j=1}^{c} \left( \frac{v_i - v_{ij}}{v_j} \right)^2 \]

• \(n\) – общее число зон в решении.

• \(c\) – общее число критериев, используемое для построения зон.

• \(V_j\) – пороговое значение j^го критерия.

• \(V_{ij}\) – сумма значений j^го критерия для i^й зоны.

Эту формулу оценки жизнеспособности можно толковать как сложение величин расхождений между значениями каждого критерия и идеальными значениями для каждой зоны в решении. В идеальном решении (которое обычно недостижимо), значения критериев для всех зон равны идеальным значениям и, соответственно, оценка жизнеспособности равна нулю. Деление на пороговое значение (V_j) гарантирует, что оценка жизнеспособности является безразмерной. Безразмерность важна, потому что, например, использование квадратных метров или квадратных футов для измерения площади не повлияет на оценку жизнеспособности.

Параметр Выходная таблица конвергенции выдает общую оценку жизнеспособности наилучшего решения в каждом поколении вместе с оценками для каждого отдельного критерия. Вместе с выходной таблицей создается диаграмма конвергенции, для визуализации того, как оценка жизнеспособности меняется по поколениям. Алгоритм пробует найти решение лучше существующего, таким образом линия жизнеспособности на диаграмме должна снижаться по мере роста поколений, пока не выйдет на плато. Выравнивание линии говорит о том, что оценка жизнеспособности достигла локального минимума (что, скорее всего, не является глобальным минимумом), и дальнейшее увеличение числа поколений не улучшит решение.

В дополнение к выходной таблице сходимости, сообщения геообработки также помогут понять, насколько качественно были созданы зоны. Для каждого критерия построения и выбора зон приводится среднеквадратическая ошибка. Чем ниже значение, тем лучше зоны соответствуют критериям.

Создание новых поколений с кроссовером

После того, как начальная популяция была сгенерирована алгоритмом, половина особей может принять участие в генерации следующего поколения и произвести потомство в виде новых возможных решений. Особи подбираются на основании оценки жизнеспособности (которая должна быть минимально-возможной), а затем произвольно спариваются для производства потомства с помощью процесса, называемого кроссовер. Кроссовер (иногда называемый рекомбинацией) – генетический оператор, который комбинирует информацию двух родителей в процессе производства потомства. На следующем рисунке показан пример скрещивания потомков двух родителей, которые, в свою очередь, создают новое потомство:

В результате половина особей нового поколения были родителями в предыдущем поколении, а половина – их потомками. Для этого нового поколения снова рассчитывается оценка жизнеспособности, и лучшая половина переходит в следующее поколение, приближаясь к наилучшему решению.

Расширение поиска возможных решений с помощью мутаций и чужеродных особей (пришельцев)

Генетическое разнообразие крайне важно для эволюционного процесса в популяции, в частности, генетическое разнообразие может поддерживаться через мутации. Мутации – небольшие изменения, или модификации, вводимые в последовательность генов для создания особей с отличающимися генетическими кодами. В этом инструменте любая особь, подвергающаяся мутации, будет иметь свои источники, перестроенные случайным образом (пермутированные). На следующих изображениях показано одно возможное решение, проходящее через мутацию и имеющее свои перестроенные источники:

Вероятность того, что потомство подвергнется мутации, можно контролировать параметром Коэффициент мутаций, его значение по умолчанию – 0.1. Введение мутаций расширяет диапазон возможных решений и часто приводит к тому, что алгоритм быстро конвергирует в сторону локального оптимального решения. Но очень высокие коэффициенты мутаций привнесут слишком много изменений, что приведет к снижению эффективности алгоритма и низкой конвергенции (или полному ее отсутствию).

Другой способ расширения диапазона возможных решений – введение в популяцию новых особей (называемых пришельцами), которые не являются ни частью предыдущего поколения, ни частью потомства. Введение чужеродных особей увеличивает вероятность получения глобального минимума (вместо локального минимума) с сохранением высокой степени конвергенции. Коэффициент мутаций управляет долей потомства каждого поколения, которое будет заменено пришельцем, состоящим из случайно сгенерированных источников.

Отключенные группы

Благодаря пространственным ограничениям, вы можете отключить группы, в которых объекты не являются соседями каких-либо объектов в большей области исследования. Это наиболее распространено, когда Входные объекты представляют собой полигоны, не являющиеся смежными, например, острова. Зоны могут расти только путем агрегирования соседей существующих объектов в зоне. Чтобы решить эту проблему, инструмент создает связь между каждой отключенной группой и ближайшим объектом вне группы, чтобы установить окрестности и позволить зоне продолжать расти. Поле Disconnected Group 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.