ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ ВИДЕОКАМЕР НА ИНТЕРАКТИВНОЙ КАРТЕ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Введение

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

В данной статьи предлагается метод автоматического размещения видеокамер на интерактивной карте, основанный на генетическом алгоритме.

Описание генетического алгоритма

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

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

Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Основные принципы работы ГА заключены в следующей схеме (см. рис. 1):

1. Инициализируем начальную популяцию из n хромосом.

2. Вычисляем приспособленность начальной популяции.

3. Выбираем с помощью селекции хромосомы-родителей из текущей популяции.

4. Сгенерировать потомков с вероятностью pc.

5. Вычисляем приспособленность потомков с вероятностью pm.

6. Проводим селекцию потомков и формируем следующие поколение популяции, содержащее n хромосом.

7. Повторяем шаги 3–6, пока не будет выполнен заданный критерий останова.

Рисунок 1. Схема работы генетического алгоритма

Условием окончания процесса может служить заданное количество поколений или схождение популяции.

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

Для реализации функции оптимального размещения видеокамер на интерактивной карте, разработана блок – схема алгоритмов работы системы. На рисунке 2 представлена блок-схема генетического алгоритма работы программы. На рисунке 3 представлен макет интерфейса программы с размещенными видеокамерами на карте. Проект карты создавался в приложении QGIS.

Рисунок 2. Блок-схема работы генетического алгоритма

Рисунок 3. Интерфейс интерактивной карты

Список литературы:

1. Веб-сайт [электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki/Генетический_алгоритм
2. Веб-сайт [электронный ресурс]   Режим доступа:  https://www.webkursovik.ru/kartgotrab.asp?id=-86507
3. Веб-сайт [электронный ресурс]   Режим доступа:  http://e-lib.gasu.ru/eposobia/gis/3.html Геоинформационное образование в России: проблемы, направления и возможности развития, Симонов А.В.
4. Панченко, Т. В. Генетические алгоритмы [Текст] : учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань : Издательский дом «Астраханский университет», 2007. — 87 [3] с.
5. Копейкин, И. Современные технологии разработки ГИС приложений / И. Копейник // Информационный бюллетень ГИС-Ассоциации. – 1999. – №3 (20). – с. 50 52