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

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

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

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

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

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

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

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

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

• Целевой атрибут - Каждая зона будет иметь примерно одинаковую общую сумму атрибута, и эта общая сумма должна быть указана. Число созданных зон зависит от общей суммы атрибута. Например, этот параметр можно использовать для создания областей обслуживания, содержащих около 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 для параметра Целевое число зон. Укажите поле, отражающее уровень опасности каждого нарушителя, в параметре Атрибуты для согласования и выберите опцию Компактность в параметре Характеристики зон, чтобы создать компактные зоны.

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

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

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

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

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

Выбор исходного поколения

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

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

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

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

• 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. ,(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.