Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
ПОНОМАРЕВ Андрей Васильевич
МОДЕЛИ И МЕТОДЫ ГРУППИРОВКИ ОБЪЕКТОВ ДЛЯ ГЕОЛОГО-ЭКОНОМИЧЕСКОГО РАЙОНИРОВАНИЯ
Специальность 05.13.01 - Системный анализ, управление и обработка информации (технические системы)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Санкт-Петербург 2012
Работа выполнена в Федеральном государственном бюджетном учреждении науки Санктн Петербургском институте информатики и автоматизации Российской академии наук (СПИИРАН).
Научный консультант:
кандидат технических наук, доцент Мустафин Николай Габдрахманович
Официальные оппоненты:
доктор технических наук, профессор, зав. лабораторией СПИИРАН Александров Виктор Васильевич кандидат технических наук, доцент, Балтийский государственный технический университет ВОЕНМЕХ им. Д.Ф.Устинова Королев Сергей Николаевич
Ведущая организация: Санкт-Петербургский государственный университет водных коммуникаций
Защита состоится л 2012 г. в часов на заседании диссертан ционного совета Д.002.199.01 при Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской акаден мии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.
С диссертацией можно ознакомиться в библиотеке Федерального государственного бюдн жетного учреждения науки Санкт-Петербургского института информатики и автоматизан ции Российской академии наук.
Автореферат разослан л 2012 г.
Ученый секретарь диссертационного совета Д.002.199.кандидат технических наук Ф.Г. Нестерук
Общая характеристика работы
Актуальность темы диссертации.
Задача геолого-экономического районирования приобрела актуальность в связи с расн смотрением на государственном уровне перспектив развития политики в области недрон пользования, суть которых заключается в переходе от лицензирования отдельных обън ектов недропользования на лицензирование промышленно-сырьевых узлов и геолого-экон номических районов, включающих месторождения разных полезных ископаемых. Целью этого перехода является повышение рентабельности освоения минерально-сырьевых рен сурсов и полноты их вовлечения в хозяйственный оборот.
В общем случае, задача геолого-экономического районирования является комплексн ной системной задачей, решаемой экспертами в области экономики недропользования с учетом знаний о разведанных запасах минерально-сырьевых ресурсов, истории и перспекн тивах развития минерально-сырьевого комплекса, данных об инфраструктуре и трудовых ресурсах исследуемого региона. Однако при решении этой задачи эксперту приходится обрабатывать значительные объемы фактической информации, что делает актуальной задачу компьютерной поддержки этого процесса. Создание программных инструментов важно еще и потому, что способно повысить качество принимаемых экспертом решений, например, за счет обеспечения возможности быстрого анализа альтернативных вариантов районирования.
В то же время, значительное количество задач, возникающих в научной и практин ческой деятельности человека, включая задачи геолого-экономического районирования, имеют в своей основе общую идею: образование групп из заданных объектов при опрен деленных условиях. Многие из этих задач успешно решаются с применением различных методов и моделей - теории графов, кластерного анализа, математического программирон вания. Вместе с тем, почти нет работ, в которых бы предпринимались попытки осознать и описать внутреннее родство таких задач, выделить общие идеи, подходы и методы, которые можно было бы применять последовательно, при решении различных задач групн пировки объектов.
Цель диссертационной работы и задачи исследования. Цель диссертационной работы состоит в разработке моделей и методов группировки объектов для повышения качества геолого-экономического районирования и снижения затрат на его проведение.
Для достижения поставленных целей были решены следующие задачи:
1) проведен обзор классических оптимизационных задач, связанных с группировкой объектов;
2) исследованы существующие подходы к формированию промышленно-сырьевых узн лов, предложена базовая модель формирования промышленно-сырьевых узлов, оснон ванная на принципе максимизации интегрального дохода, и набор ее конкретизаций для различных условий применения;
3) проведена классификация видов задачи группировки и для распространенных подн классов задачи группировки сформулированы эквивалентные задачи математическон го программирования;
4) для ряда разновидностей задачи группировки объектов разработаны новые или адапн тированы существующие алгоритмы решения и произведена оценка эффективности разработанных алгоритмов на синтетических наборах данных;
5) показана связь некоторых видов абстрактных задач группировки с предложенными моделями формирования промышленно-сырьевых узлов;
6) разработанные методы и алгоритмы группировки применены к практической задаче геолого-экономического районирования.
Методы исследования. В работе используются методы теории графов, дискретной оптимизации, теории множеств. Для обработки результатов экспериментальных исследон ваний стохастических алгоритмов используются методы математической статистики.
Основные положения, выносимые на защиту:
1. Совокупность математических моделей для решения задачи формирования промышн ленно-сырьевых узлов, основанных на принципе оптимизации интегрального дохода, получаемого в процессе освоения недр.
2. Методы решения вариантов задачи группировки объектов, возникающих при испольн зовании предлагаемых моделей формирования промышленно-сырьевых узлов.
3. Приближенные алгоритмы решения задачи формирования промышленно-сырьевых узлов.
Научная новизна работы состоит в следующем:
1. Разработан набор оригинальных математических моделей для решения задачи форн мирования промышленно-сырьевых узлов на основе принципа оптимизации интен грального дохода, учитывающий различные варианты освоенности исследуемой терн ритории и перечня доступных данных, а также позволяющий свести задачу формин рования промышленно-сырьевых узлов к задаче целочисленного линейного програмн мирования.
2. Предложена модель абстрактной задачи централизованной группировки, обобщаюн щая задачу формирования промышленно-сырьевых узлов и позволяющая испольн зовать разработанные методы и алгоритмы при решении задач централизованной группировки объектов.
3. Разработан набор приближенных алгоритмов, основанных на применении схемы лон кального поиска, для решения задачи формирования промышленно-сырьевых узлов с учетом мощности действующих горно-обогатительных предприятий. Применение разработанных алгоритмов позволяет существенно ускорить решение задачи форн мирования промышленно-сырьевых узлов по сравнению с классическими точными методами решения задач целочисленного программирования.
4. Предложен метод решения задачи формирования промышленно-сырьевых узлов, осн нованный на сведении данной задачи к задаче поиска базы матроида максимального веса, позволяющий эффективно решать задачу формирования промышленно-сырьен вых узлов и дающий лицу, принимающему решения, возможность интерактивного анализа чувствительности.
5. Предложен метод учета в задаче формирования промышленно-сырьевых узлов огран ничения на разброс значений скалярной характеристики объектов одной группы в виде логических функций, позволяющий сохранить структуру задачи как задачи целочисленного линейного программирования.
Практическая значимость данной диссертационной работы состоит в повышении качества решения задачи геолого-экономического районирования за счет предоставления лицу, принимающему решения, возможности оперативно оценивать варианты районирон вания, отличающиеся различными модельными допущениями и доступными исходными данными.
Модели и алгоритмы, изложенные в диссертации, могут быть использованы для рен шения широкого круга задач централизованной группировки объектов произвольной прин роды.
Реализация результатов работы. Исследования, отраженные в диссертации, подн держаны грантом РФФИ №09-07-00436-а Онтолого-ориентированное управление гибкин ми сетевыми организациями и проектом Президиума РАН №2.13 Разработка теоретичен ских основ и интеллектуальных моделей для поддержки принятия решений при управлен нии гибкими сетевыми организациями, 2009Ц2011.
Апробация полученных в диссертации результатов подтверждена актами об испольн зовании результатов диссертационной работы в процессе обучения студентов в Санктн Петербургском государственном электротехническом университете ЛЭТИ и в научнон исследовательской работе по государственному контракту №АЛ-04-06/9 Разработка прон граммно-технологического комплекса, обеспечивающего построение, мониторинг и функн ционирование ГИС-ориентированной системы для составления геолого-экономических карт федеральных округов России совместно с Всероссийским научно-исследовательским геон логическим институтом (ВСЕГЕИ) им. А.П. Карпинского.
Апробация результатов работы. Основные положения и результаты диссертации представлялись на следующих конференциях: Информационные технологии в экономин ке, образовании и бизнесе (Саратов, 2011), Наука и техника XXI века (Новосибирск, 2011), Наука и современность Ч 2011 (Новосибирск, 2011), Проблемы подготовки кадн ров в сфере инфокоммуникационных технологий (Санкт-Петербург, 2011), а также на городском семинаре Информатика и компьютерные технологии (СПИИРАН, Санктн Петербург, 2012).
Публикации. Материалы диссертации опубликованы в 8 печатных работах, в том числе в 3 рецензируемых изданиях из списка ВАК.
Структура и объем работы. Диссертация объемом 123 страницу содержит ввен дение, четыре главы, заключение, список литературы (81 наименование), 22 рисунка, таблиц.
Содержание работы Во введении обоснована актуальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, показана практическая значин мость полученных результатов, представлены выносимые на защиту научные положения.
В первой главе, с одной стороны, произведен обзор классических задач, связанн ных с группировкой объектов, а с другой стороны, описана одна из практических задач группировки Ч задача геолого-экономического районирования.
Рассмотрены следующие задачи, так или иначе связанные с группировкой объекн тов: кластерный анализ, задачи разбиения и покрытия множества, задачи о назначениях (классическая и обобщенная), дискретные задачи размещения (в особенности, простейшая задача размещения).
В приведенном перечне естественным образом выделяются однородные задачи, то есть такие, исходными данными для которых является одно множество равноправных объектов, и неоднородные, где присутствует несколько (обычно два) неравноправных исн ходных множеств и группы формируются с учетом определенных ограничений. К первому виду относится кластерный анализ, ко второму Ч обобщенная задача о назначениях и дисн кретные задачи размещения. Задача разбиения множества, хотя формально относится к первому виду, сочетает в себе черты обоих. В диссертации, в первую очередь, рассматн риваются неоднородные группировки, а именно, группировки с двумя неравноправными исходными множествами.
Одной из практических задач группировки является задача формирования промышн ленно-сырьевых узлов, возникающая при геолого-экономическом районировании и создан нии геолого-экономических карт.
Основой для геолого-экономического районирования является территориальная блин зость участков недр и центров переработки сырья, существование цепочек поставок, родн ство технологий добычи и обогащения, совместное использование инфраструктуры. В рен зультате такого районирования создаются агрегированные сущности (объекты геолого-экон номического районирования). В дальнейшем, стратегия развития горно-промышленного комплекса региона складывается именно из решений, принимаемых относительно этих агрегированных объектов.
Выделяется несколько уровней агрегации и, соответственно, несколько видов агрегин рованных объектов. Первым уровнем являются промышленно-сырьевые узлы.
Под промышленно-сырьевым узлом (ПСУ) понимается пространственно обособленн ная группа сближенных минерально-сырьевых объектов, обладающих одинаковым набон ром полезных ископаемых, локализация которых связана с месторождениями определенн ного геолого-промышленного типа и, как следствие этого, с единой технологией получения первого товарного продукта на существующих или проектируемых горно-обогатительных предприятиях (ГОП).
Рассмотрены описанные в литературе методы автоматизированного формирования промышленно-сырьевых узлов и показано, что они обладают рядом недостатков, что обун словливает необходимость разработки новых, улучшенных методов.
Для постановки задачи оптимального формирования ПСУ на исследуемой территон рии ключевым является вопрос о том, каким образом, по каким критериям такие варин анты могут сравниваться, на основании каких критериев можно судить о превосходстве того или иного набора ПСУ.
На этом этапе возможны различные установки, так или иначе учитывающие цели и стратегию недропользования в регионе. Данная работа основывается на экономической интерпретации задачи формирования ПСУ, изложенной в работах Куклиной Е.А., где ван рианты формирования ПСУ оцениваются по рентабельности (или интегральному доходу), получаемой при реализации соответствующего варианта. Дополнительно может ставитьн ся задача полного распределения всех объектов минерально-сырьевой базы по ПСУ для вовлечения их в активное хозяйствование.
Прибыль от функционирования ПСУ определенного состава вычисляется как разнин ца между суммарной потенциальной стоимостью запасов и ресурсов (СП) по всем минен рально-сырьевым объектам, входящим в состав данного узла, и затратной частью (ЗО), формируемой на основе цепочки преобразований, которым подвергается добываемое минен ральное сырье: добыча транспорт обогащение. Затраты, возникающие на каждом из этапов, делятся на капитальные и эксплуатационные. Таким образом, в затратной части оказывается 6 показателей, сведенных в таблицу 1.
Таблица 1. Основные затратные показатели Добыча Обогащение Транспорт Капитальные КД КП КТ Эксплуатационные СД СП СТ Суммарные затраты на формирование ПСУ символически можно записать следуюн щим образом:
ЗО = (КП + СП) + (КД + СД + КТ + СТ). (1) МСО Это выражение является ядром предлагаемой базовой модели формирования ПСУ. Мон дель названа базовой, поскольку она задает общую идею поиска, но она не может быть применена непосредственно без уточнения того, как именно вычисляются параметры, в нее входящие Ч для некоторых параметров могут применяться существенно различные стратегии.
Следует заметить, что данное выражение представляет собой упрощенную символин ческую запись, на практике КП и СП, обычно, зависят от точки размещения горно-обон гатительного предприятия (ГОП) и состава узла, КД и СД зависят от параметров местон рождения (в первую очередь, объема запасов), КТ и СТ Ч от взаимного расположения месторождения и горно-обогатительного предприятия и объема запасов месторождения.
Знак суммирования по МСО следует понимать как суммирование по всем месторожден ниям (минерально-сырьевым объектам), входящим в состав узла.
Конкретизация модели обеспечивается выбором способа оценки затрат каждого вин да. В частности, затрат на обогащение КП и СП. При использовании метода корреляцин онных зависимостей1, приняв за kкп и kсп коэффициенты, устанавливающие связь между СП и КП и СП соответственно, выражение для суммарных затрат можно переписать слен дующим образом:
ЗО = kкп СП + kсп СП + (КД + СД + КТ + СТ) = МСО МСО МСО = (kкпСП + kспСП + КД + СД + КТ + СТ). (2) МСО В таком виде выражение все еще не может быть использовано, поскольку в нем не раскрыт способ вычисления КД, СД, КТ и СТ. Для вычисления первых двух величин в работе такн же используется метод корреляционных зависимостей, последняя же пара, обозначающая полные затраты на транспортировку руды от места добычи к месту обогащения, может оцениваться различными способами, в зависимости от имеющейся информации, и задан ет одну из стратегий расширения базовой модели. В работе рассматриваются следующие реализации этой стратегии:
на основе данных о сети дорог;
обанов Н. Я. Экономика природопользования при разведке, добыче и обогащении полезных ископаемых. Экономическая оценка минеральных ресурсов. СПб.: Изд-во СПбГГИ, 2009, 99 с.
на основе эмпирических показателей развития транспортной инфраструктуры;
комбинированная (при наличии неполных данных о сети дорог).
Другим особым случаем является создание ПСУ на базе эксплуатируемого горнон обогатительного предприятия. Такое предприятие должно быть учтено при расчете капин тальных затрат на создание ПСУ (КП). В работе предлагается несколько стратегий для его учета:
не учитывать;
линейное уменьшение КП узла;
уменьшение КП узла без псевдоприбыли.
Структура базовой модели формирования ПСУ с различными стратегиями отобран жена на рисунке 1.
Рис. 1. Структура базовой модели формирования ПСУ Выбор той или иной стратегии предлагается осуществлять в зависимости от харакн теристик исследуемой территории и доступных данных. Например, для неосвоенных райн онов наилучшим выбором будет стратегия, не учитывающая существующие ГОП (и ее применение будет оправдано, поскольку там их нет), применение которой позволит полун чить более эффективные с вычислительной точки зрения математические постановки, не жертвуя важной информацией.
Выбор же стратегии оценки транспортных затрат, в основном, определяется наличин ем информации о транспортных сетях в электронной форме, доступной для обработки, пон скольку это позволяет получать более точные оценки. При отсутствии такой информации можно воспользоваться эмпирическими показателями, но вопрос точности получаемых оценок, в этом случае, нужно исследовать отдельно в связи с источником получения этих эмпирических показателей. Подобные исследования выходят за рамки настоящей работы.
Во второй главе вводятся формальные определения группы и группировки, а также ряд вспомогательных терминов и идей, используемых в диссертации. Выделяетн ся структура постановки конкретной задачи группировки и, на основе варьирования знан чений компонент постановки, строится классификация задач группировки. Предлагается вариант записи некоторых видов задачи группировки как задач математического програмн мирования с булевыми переменными. Показывается, каким образом различные варианты модели задачи формирования ПСУ соотносятся с выделенными вариантами абстрактной задачи группировки.
Предлагаемая модель абстрактной задачи группировки базируется на следующих определениях и положениях.
Исходными данными для группировки является семейство исходных множеств O = (O(1), O(2),..., O(k)). Здесь k Ч количество типов исходных объектов; например, в задаче формирования промышленно-сырьевых узлов k равно 2 и семейство O образовано двумя множествами: горно-обогатительных предприятий и месторождений.
В работе вводится понятие базовой группы. Базовой группой G, заданной на семейн стве исходных множеств O называется набор множеств (1) (2) (k) G = (OG, OG,..., OG ) таких, что (i) OG O(i), i {1,..., k}.
(i) OG называются компонентами группы.
Группировку G на семействе исходных множеств O определим как множество попарно не пересекающихся базовых групп на этом семействе. То есть, G = {G}, (3) (G1, G2)|G1, G2 G G1 G2 = (4) Группировка G называется полной по O(i) тогда и только тогда, когда O(i)(G) = O(i).
Группировка G называется полной тогда и только тогда, когда она полная по кажн дому из множеств O.
Группировка G называется частично полной тогда и только тогда, когда она не является полной, но в O существует хотя бы одно множество O(i), по которому данная группировка является полной.
Группировка, не являющаяся ни полной, ни частично полной, называется неполной.
Ограниченной группой (ОГ) или группой с ограничениями называется базовая групн па, на состав которой наложены дополнительные ограничения.
На практике обычно ставится задача нахождения хороших (в ряде случаев, оптимальн ных) группировок на различных классах ОГ. Для точной постановки этой задачи нужно определить способ сравнения группировок. В предлагаемой модели абстрактной задачи группировки предлагается поставить каждому варианту группировки в соответствие чисн ло и решать задачу поиска такой группировки на исходном семействе множеств, которой соответствует максимальное (или минимальное) число. Способ оценки группировки будем называть системой показателей (СП).
Таким образом, для определения задачи группировки в терминах предлагаемой мон дели абстрактной задачи группировки необходимо задать:
семейство исходных множеств;
класс ограниченной группы Ч набор ограничений на структурные отношения объекн тов разных типов внутри группы;
тип группировки по отношению к покрытию исходных множеств: полная, частично полная, неполная;
систему показателей.
В зависимости от конкретных структуры исходных множеств объектов, ограничений и системы показателей образуются частные постановки общей задачи группировки.
Важным критерием классификации задач группировки является структура внутрин групповых отношений. По этому критерию можно выделить:
одноранговую группировку;
централизованную группировку;
Задача группировки будет являться одноранговой в том случае, когда выделяемые группы являются однородными и состоят из объектов, одинаковых по своей роли в групн пе. Для этого вида группировок характерно наличие одного исходного множества (семейн ство O представлено только одним множеством O(1), класс ОГ либо эквивалентен классу базовых групп, либо содержит простейшие ограничения на размер группы, а система пон казателей базируется на попарных отношениях между объектами. К этой разновидности относятся большинство вариантов задачи кластеризации.
Централизованная группировка предполагает, что семейство исходных множеств O состоит из двух множеств: множества первичных объектов O(1) и множества потенциальн ных центров групп O(2), относительно которых происходит объединение первичных обън ектов. При рассмотрении этого вида группировок будем пользоваться альтернативным обозначением этих множеств S и C соответственно.
Класс ОГ в задачах данной категории может содержать разнообразные ограничения, но обязательно присутствует требование того, чтобы группа включала только один объект из множества C. В сочетании с общим для любых группировок требованием того, чтобы объект относился не более, чем к одной группе, в данной категории группировок речь идет об однозначном соответствии между группами и потенциальными центрами.
В рамках данной работы производится анализ, в первую очередь, именно централин зованной группировки, причем рассматриваются три системы показателей; это связано с тем, что именно к таким задачам группировки сводятся задачи формирования промышн ленно-сырьевых узлов при предлагаемых стратегиях учета ГОП. Во всех рассматриваен мых системах показателей оценка группировки задается как сумма оценок групп, а оценки групп, в свою очередь, формируются следующим образом (здесь C(G) Ч центр группы G, а S(G) Ч множество сателлитов этой группы):
Простейшая система показателей. Предполагается, что задано одно отображение D : S C R. Оценка группы вычисляется по формуле:
val(G) = d(s, C(G)).
sS(G) Система показателей со стоимостью активации. Здесь, помимо D, задано отобран жение P : C R. Оценка группы вычисляется по формуле:
val(G) = -p(C(G)) + d(s, C(G)).
sS(G) Система показателей с линейной стоимостью и бесплатным порогом. Помимо D, заданы отображения R: S R, L: C R и A: C R, а оценка группы вычисляетн ся так:
val(G) = d(s, C(G)) + a(C(G)) min(0, l(C(G)) - r(s)). (5) sG(S) sS(G) Смысл параметров определяется прикладной задачей, сводимой к данной задаче группировки.
Задача группировки может быть представлена как задача математического програмн мирования с булевыми переменными. При этом тип группировки по отношению к исходн ным множествам и класс ОГ преобразуются в ограничения задачи, а система показатен лей Ч в целевую функцию. Базовая постановка задачи математического программирован ния для централизованных группировок с простейшей системой показателей записывается следующим образом:
n m Максимизировать z = xijd(si, cj) (6) i=1 j=при ограничениях m xij 1 i {1,..., n} (7-а) j=xij yj i {1,..., n}, j {1,..., m} (7-б) xij, yj {0, 1} i {1,..., n}, j {1,..., m}.
Здесь переменные вида xij Ч признак вхождения объекта si в группу с центром в cj, а yj Ч признак образования группы с центром в cj. Если не указано иное, то n здесь и далее обозначает |S|, а m обозначает |C|.
Ограничения вида 7-б назовем ограничениями целостности, поскольку они выран жают требование внутренней согласованности и непротиворечивости значений переменн ных xij и yj.
Ограничения вида 7-а выражают отношение объектов множества S к группировке, поэтому назовем их ограничениями покрытия. От вида знака в этом ограничени будет зависеть требование полноты по S искомой группировки.
В работе описано каким образом различные варианты задачи группировки модифин цируют приведенную здесь базовую постановку. Проанализированны следующие разнон видности:
1) полные, частично полные и неполные задачи группировки;
2) группировки со стоимостью активации потенциальных центров;
3) группировки с некоторыми видами ресурсных ограничений;
4) группировки с ограничением на одновременное вхождение;
5) группировки с ограничением на структуру группы.
Показано сведение каждой из рассматриваемых моделей формирования ПСУ к ван риантам задачи группировки. Например, вариант модели формирования ПСУ, в котон ром в качестве стратегии учета существующих предприятий выбран вариант линейного уменьшения КП, сводится к задаче группировки с системой показателей со стоимостью активации, причем смысл отображений D и P, являющихся параметрами этой системы показателей, задается следующим образом:
dij = СП(si) - (kкпСП(si) + kспСП(si) + КД(si) + СД(si) + КТ(si, cj) + СТ(si, cj)), pj = VГОП, под VГОП здесь понимается балансовая стоимость действующего горно-обогатительного предприятия. Для вычисления КД и СД может применяться метод корреляционных зан висимостей, а способ вычисления транспортных затрат КТ и СТ определяется доступной информацией (о сетях транспорта).
В практических задачах объекты зачастую описываются некоторым множеством разн нородных собственных характеристик, сочетание значений которых может влиять на допун стимость того или иного варианта группировки. Показано, каким образом предлагаемые модели могут быть использованы для группировки объектов при наличии ограничений на значения характеристик объектов. В частности, рассмотрен ряд специфических огран ничений: группировка с ограничением на разброс значений скалярной характеристики объектов группы и с ограничением на соотношение разнотипных объектов в группе.
Предлагаемый метод учета ограничения на разброс значений скалярной характерин стики объектов группы заключается в следующем. Пусть, q(si) Ч какая-то скалярная характеристика объекта si. Тогда требование того, что разброс значений этой характерин стики в группе не должен превышать q записывается так:
G G : max q(s) - min q(s) q.
sG sG Ограничения подобного вида предлагается представлять в виде дополнительных огранин чений к рассмотренной выше базовой постановке задачи группировки как задачи матен матического программирования, сведя их к логическим функциям, задающим запрет на одновременное вхождение объектов в группу. Введем на множестве S S логическую q функцию R, определяемую следующим образом:
1, если |q(x) - q(y)| > q;
q R (x, y) = 0, в противном случае.
Тогда для учета ограничения на разброс параметра к списку ограничений базовой постан новки задачи группировки как задачи математического программирования необходимо добавить ограничения вида:
q xi,j + xi,j 1 j {1,..., m}, i1, i2 {1,..., n}, R (si, si ) = 1.
1 2 1 В третьей главе производится анализ трех разновидностей задачи централизованн ной группировки: с простейшей системой показателей, с системой показателей со стоимон стью активации и с линейной стоимостью и бесплатным порогом. Предлагаются методы решения этих задач и ставится вычислительный эксперимент, позволяющий оценить эфн фективность работы предложенных методов на синтетических наборах данных.
Рассматриваются все возможные варианты группировки с простейшей системой пон казателей относительно покрытия исходных множеств: полная, полная по C, полная по S и неполная. Следует заметить, что все методы разрабатывались таким образом, что, в найденном решении обязательно выполняется заданное требование полноты и, возможно, более строгие. То есть, при поиске неполной группировки решение, являющееся полной группировкой, считается допустимым, но не наоборот.
Метод решения задачи полной централизованной группировки с простейшей систен мой показателей основывается на том, что в графовой интерпретации эта задача известна как m n задача о назначениях и может быть сведена к поиску потока минимальной стоимости2 в специальным образом построенной сети M(V, E, a, f). Принцип построения inf inf s t inf m-n inf q Рис. 2. Вид сети для представления задачи полной группировки как задачи о потоке минимальной стоимости сети M(V, E, a, f) следующий. Пусть множество вершин V = C S {s} {t} {q}. То есть, в множестве вершин графа есть по одной вершине для каждого из элементов множен ства C S, вершинаЦисточник s, вершинаЦсток t и дополнительная фиктивная вершина q. Обозначение множества вершин V мы будем употреблять также и в функциональном контексте в качестве обозначения отображения между множествами исходных объектов и множеством вершин графа. При этом запись V (si) следует интерпретировать как вершин на графа, соответствующая объекту si. Множество дуг E, вместе с отображениями a и f, задающими пропускные способности дуг и стоимости использования единицы пропускной способности, является объединением следующих множеств:
множество дуг вида V (cj), V (si), где si S, cj C. Для таких дуг принимается a(V (cj), V (si)) = , f(V (cj), V (si)) = -d(si, cj);
множество дуг вида s, V (cj), где cj C. Для таких дуг принимается a(s, V (cj)) = 1, f(s, V (cj)) = 0;
множество дуг вида V (si), t, где si S. Для таких дуг принимается a(V (si), t) = 1, f(V (si), t) = 0;
дуга s, q, для которой принимается a(s, q) = |S| - |C|, f(s, q) = 0;
множество дуг вида s, V (cj), где cj C. Для таких дуг принимается a(s, V (cj)) = , f(s, V (cj)) = 0.
Таким образом, предлагаемым методом решения задачи полной централизованной группировки является применение алгоритма нахождения максимального потока минин мальной стоимости к сети M.
Для решения задачи нахождения потока минимальной стоимости существует множен ство алгоритмов, как псевдополиномиальных, так и строго полиномиальных. Лучший из известных автору алгоритмов принадлежит J.B. Orlin и имеет сложность O((m log n)(m + n log n)), где n и m Ч количества вершин и дуг сети соответственно.
Полная по C централизованная группировка с простейшей системой показателей мон жет быть решена с помощью обобщения предыдущей задачи. Сеть для решения строится аналогичным образом, но иначе задается пропускная способность дуги (s, q) - в случае Bertsekas D. Linear Network Optimization: Algorithms and Codes. The MIT Press, 19задачи полной группировки пропускная способность этой дуги была m - n, здесь же предн лагается рассмотреть сети с любой целочисленной пропускной способностью соответствун ющей дуги, попадающей в определенный интервал 3. Фактически, речь идет о семействе сетей M, элементами которого являются сети M[x], построенные по изложенным выше правилам и имеющие пропускную способность дуги c(s, q) = x.
inf inf s t inf X inf q Рис. 3. Вид сети M[x] В работе доказывается, что решение задачи централизованной группировки с прон стейшей системой показателей является максимальным потоком минимальной стоимости в одной из сетей семейства M[x]|0 x m-n.
Таким образом, предлагаемый метод полной по C централизованной группировки с простейшей системой показателей заключается в последовательном рассмотрении сетей M[0], M[1],..., M[m - n] и нахождении в них максимальных потоков минимальной стоин мости. Результат группировки получается выбором одного из решений m-n+1 подзадач, обладающего наименьшим значением стоимости.
Предлагаемый метод решения полных по S и неполных задач централизованной групн пировки с простейшей системой показателей основан на доказанном в работе утвержден нии, что графовая интерпретация группировки такого вида является матроидом, а поиск оптимальной группировки эквивалентен поиску базы максимального веса для этого матрон ида. Следовательно, оптимальные группировки могут эффективно находиться вариантом жадного алгоритма РадоЧЭдмондса.
Суть алгоритма заключается в том, что все пары si, cj упорядочиваются по убыван нию значения отображения d(si, cj) и далее анализируются последовательно. Если si из пары si, cj, рассматриваемой на очередном шаге, еще не входит в группу, то он включан ется в группу с центром в cj.
Особенность алгоритма для неполных задач централизованной группировки в том, что алгоритм заканчивает работу при обнаружении на очередном шаге пары с отрицан тельным значением d(si, cj).
Сложность этих алгоритмов оценивается как O(mn log(mn)).
В системе показателей со стоимостью активации определена стоимость образования группы на основе заданного объекта из C; эта стоимость задается отображением P : C R.
В работе рассмотрены четыре варианта централизованной группировки с такой син стемой показателей.
Постановки полной и полной по C задачи группировки со стоимостью активации сводятся к аналогичным задачам группировки без стоимости активации. Действительно, в полной и полной по C задачах все потенциальные центры (объекты из C) должны войти в группировку, а значит, целевая функция всегда будет содержать все слагаемые p(cj).
Полная по S и неполная разновидности этой задачи не сводимы к потоку, но предн ставляют собой хорошо изученную задачу дискретной оптимизации, известную под нан званием простейшая задача размещения (uncapacitated factory location problem). Эта задача является NP-трудной и для ее решения можно воспользоваться классическими мен тодами точного решения задач ЦЛП или приближенными методами; в данной работе для решения практических задач формирования промышленно-сырьевых узлов, сводимых к данному виду задачи группировки, используется три способа: применение универсального решателя SCIP для получения точных решений и генетический алгоритм и разновидность метода локального поиска для получения приближенных.
При реализации генетического алгоритма и процедуры локального поиска не было сделано существенных усовершенствований по отношению к современным алгоритмам рен шения простейшей задачи размещения, поэтому позволю себе не помещать в автореферат подробности их работы.
Особенность системы показателей с линейной стоимостью и бесплатным порогом состоит в том, что в рамках нее каждый сателлит характеризуется некоторым количеством ресурса (R: S R), а для каждого центра указан порог (L: C R), до превышения которого штраф за образование группы с соответствующим центром отсутствует, а после превышения этот штраф растет пропорционально величине превышения с коэффициентом A: C R.
Постановка данной разновидности задачи группировки как задачи математического программирования записывается следующим образом:
m n m Максимизировать z = a(cj)qj + xijd(si, cj) (8) j=1 i=1 j=при ограничениях qj 0 j {1,..., m} n qj yjl(cj) - xijr(si). j {1,..., m} i=m xij 1 i {1,..., n} j=xij yj i {1,..., n}, j {1,..., m} xij, yj {0, 1} i {1,..., n}, j {1,..., m}.
Переменная q здесь введена как способ избавиться от min в целевой функции (см. формулу 5).
В работе рассматриваются способы решения некоторой разновидности этой задачи.
А именно, принимаются следующие допущения:
a(cj) полагается равным 1 для всех j;
l(cj) считается неотрицательным для всех j;
r(si) считается неотрицательным для всех i;
речь идет только о неполной группировке.
Такой набор допущений связан с тем, что именно такая формальная постановка соответствует практической задаче формирования ПСУ, в том случае, если применяется стратегия учета существующих горно-обогатительных предприятий без псевдоприбыли.
Данная задача относится к задачам частично-целочисленного программирования.
Для оценки применимости классических точных методов решения такого рода задач к задаче группировки с линейным порогом и бесплатной стоимостью в работе использован один из самых быстрых на данный момент3 коммерческих решателей задач линейного, целочисленного и квадратичного программирования Ч IBM ILOG CPLEX 12.4.
Исследование базируется на гипотезе, что производительность и точность методов решения зависят от исходных данных, задаваемых набором отображений A, L, R, D, и более того, от некоторых обобщенных характеристик, отражающих взаимосвязь этих исн ходных отображений.
Выделены следующие характеристики:
плотность набора, выражающая соотношение между бесплатными границами и суммарным объемом ресурса всех сателлитов. Плотность вычисляется по формуле l(c)/ r(s);
cC sS доля центров, у которых бесплатный порог больше 0;
фаворитизм Ч неравномерность распределения значений в отображении D; эта хан рактеристика применима, в основном, к синтетическим наборам, и может либо прин нимать значение лотсутствует, если для каждого сателлита значения отображения D формируются случайно в достаточно широких пределах или быть числом от 0 до 1, и тогда это число выражает для любого сателлита долю тех центров, значения отображения D для пары с которыми больше нуля, значения для остальных пар равны нулю;
rЦd отношение, вычисляемое как r(s)/ d(s, c).
sS sS cC В рамках эксперимента для каждого из выделенных параметров задавалось нескольн ко уровней и тестовые наборы создавались для каждого сочетания уровней. Конкретные значения отображений получались с использованием генератора случайных чисел, таким образом, чтобы с определенной степенью точности выдерживались требуемые обобщенные характеристики.
Применение CPLEX к 840 наборам разных классов показало, что, с одной стороны, большинство наборов данных вплоть до достаточно больших размерностей (400Ц500) эфн фективно решаются этим инструментом, с другой стороны, выделен набор таких классов, решение которых представляет значительные трудности. Такими трудными классами оказались наборы исходных данных, обладающих плотностью 80Ц100%% и небольшой дон лей центров с бесплатным порогом (10Ц40%%). На таких наборах значительно медленнее происходит и поиск приближенных решений. В связи с этим, для быстрого получения прин ближенных решений, было разработано несколько вариантов алгоритмов решения задачи группировки с линейной стоимостью и бесплатным порогом, основанных на локальном поиске. А именно:
локальный поиск со случайным стартом;
метод Лидер группы4;
вариант схемы GRASP (Greedy Randomized Adaptive Search Ч вероятностный жадн ный алгоритм поиска).
начало 2012 года Кочетов Ю. А. Методы локального поиска для дискретных задач размещения. Дисс. на соискание степени доктора ф.-м. наук, Новосибирск, 20 Время, с 160 1 1 1 Плотность, % Отношение, % 1Рис. 4. Время работы CPLEX при поиске точного решения При реализации поиска со случайным стартом и схемы GRASP применялась ускон ренная реализация локального поиска, использующая структуры данных типа куча для быстрого выбора лучшего соседнего решения.
Для разработанных алгоритмов была экспериментально проведена оценка средней погрешности. В оценке участвовало 720 наборов разных классов, для которых были изн вестны оптимальные решения. Каждый стохастический приближенный метод запускался на одном наборе по 5 раз, результаты усреднялись.
Для всех методов средняя погрешность оказалась в пределах 5%, лучшие результан ты получены применением локального поиска со случайным стартом и методом Лидер группы (см. таблицу 2 и таблицу 3).
Время решения задачи приближенными методами оказалось сравнимо с временем решения задачи с помощью CPLEX на наборах, быстро решаемых CPLEX, и существенно ниже на наборах, представляющих для универсального решателя сложность.
Таблица 2. Оценки средней погрешности для локального поиска Вариант алгоритма Количество итераций Средняя погрешность Старт с пустой 1 4, 5% группировки Старт со случайной 100 2, 9% группировки 200 2, 8% 300 2, 7% 400 2, 6% 500 2, 6% Таблица 3. Оценки средней погрешности для метода Лидер группы Количество Вероятность выбора (p) итераций 0, 25 0, 5 0, 100 2, 8% 3, 2% 3, 6% В четвертой главе описан набор программных модулей, предназначенных для рен шения различных видов задачи группировки, и осуществляется решение задачи геологон экономического районирования месторождений Дальневосточного федерального округа (ДВФО) с помощью разработанных модулей. Источником данных о месторождениях явн ляется Государственный кадастр месторождений и проявлений полезных ископаемых.
В рамках диссертационной работы создана библиотека модулей группировки, кажн дый модуль которой предназначен для решения некоторого вида задач группировки опрен деленным алгоритмом. Некоторые модули реализуют алгоритмы, разработанные в ходе данного исследования, другие же содержат лишь постановку задачи на языке какогон либо универсального решателя и процедуры согласования форматов исходных и выходных данных.
Все модули библиотеки обладают единым форматом представления входных и вын ходных данных. Это означает, что пользователь библиотеки, проведя классификацию той задачи группировки, с которой он столкнулся, может выбрать любой из модулей, решаюн щий задачу этого класса. В дальнейшем, может быть реализована процедура (или экспертн ная система) автоматического выбора модуля в зависимости от отношений группируемых объектов и/или эмпирических данных о том, как проявляют себя разные алгоритмы групн пировки на наборах данных, обладающих определенными характеристиками.
По отношению к применяемым методам, разработанные модули можно разбить на три группы:
модули, использующие какой-либо универсальный решатель (SCIP или CPLEX);
модули, реализующие специальные алгоритмы (жадный алгоритм, вариант поиска потока максимальной стоимости, локальный поиск и т.д.);
модули, реализующие генетический алгоритм решения (на основе библиотеки GAlib).
Для решения практической задачи группировки Ч поиска моносырьевых промышн ленно-сырьевых узлов Ч в первую очередь, необходимо зафиксировать определенный геон лого-промышленный тип месторождений, к которому будут принадлежать все элементы выделяемых узлов. Геолого-промышленный тип Ч это комплексная характеристика местон рождения, которая определяет технологии добычи и обогащения сырья и влияет на стоин мостные оценки.
Было осуществлено несколько экспериментов с месторождениями различных геон лого-промышленных типов.
Два исходных множества задачи группировки определялись следующим образом:
множество S Ч сателлитов Ч являлось множеством месторождений, множество C Ч потенн циальных центров групп Ч также являлось множеством месторождений (точнее, точек, совпадающих в пространстве с месторождениями) исходя из того, что создание горнон обогатительного предприятия (ГОП), расположенного вблизи источника сырья, является широко распространенной практикой в геолого-экономическом хозяйствовании.
Для оценки затрат на создание узла использовалась стратегия линейного уменьшен ния КП узла, в которой учитывается тот факт, что капитальные затраты на переработку в существующем ГОП должны быть меньше на величину, связанную с текущим состоянием этого ГОП. В частности, одним из способов оценки является балансовая стоимость ГОП.
В этой модели затраты на формирование узла вычисляются по формуле:
ЗО = -VГОП + (kкпСП + kспСП + КД + СД + КТ + СТ), МСО где VГОП Ч балансовая стоимость ГОП.
Такая модель вычисления затрат на формирования ПСУ соответствует системе пон казателей со стоимостью активации. А именно, отображение D задается выражением:
dij = СП(si) - (kкпСП(si) + kспСП(si) + КД(si) + СД(si) + КТ(si, cj) + СТ(si, cj)), а отображение P :
pj = VГОП.
Относительно этих исходных данных ставилась задача оптимальной централизованной группировки с системой показателей со стоимостью активации.
Рис. 5. Моносырьевые группы ГПТ Оловянные на фрагменте карты ДВФО Результаты, полученные с применением разработанных алгоритмов к сформулирон ванной задаче группировки, показали хорошее соответствие (95Ц98%) с результатами геон лого-экономического районирования ДВФО, выполненного экспертами в области недрон пользования. На рисунке 5 показан фрагмент карты ДВФО с выделенными моносырьевын ми узлами геолого-промышленного типа Оловянные.
ОСНОВНЫЕ НАУЧНЫЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ В настоящей диссертационной работе решена важная актуальная задача обеспечения модельно-алгоритмической поддержки геолого-экономического районирования, имеющая большое значение для осуществления эффективной государственной политики в области экономики природопользования. В ходе решения данной задачи были получены следуюн щие результаты:
1. Предложена базовая модель для решения задачи формирования промышленно-сырьен вых узлов, основанная на принципе оптимизации интегрального дохода, получаемон го в процессе освоения недр. Совокупность конкретизаций базовой модели позволяет учитывать различные свойства исследуемой территории и осуществлять решение зан дачи при различных требованиях к полноте и составу исходных данных.
2. Предложено обобщение задачи формирования промышленно-сырьевых узлов в виде абстрактной задачи группировки, сформулирована формальная модель задачи групн пировки. Модель позволяет использовать предложенные алгоритмы при решении задач централизованной группировки.
3. Разработан набор приближенных алгоритмов, основанных на схеме локального поисн ка и позволяющих решать задачу формирования промышленно-сырьевых узлов при разных стратегиях учета действующих горно-обогатительных предприятий. Разрабон танные алгоритмы позволяют существенно ускорить решение задачи формирования промышленно-сырьевых узлов для некоторых классов наборов исходных данных по сравнению с классическими точными методами.
4. Предложен метод решения задачи оптимального формирования промышленно-сырьен вых узлов, основанный на сведении данной задачи к задаче поиска базы матроида максимального веса. Это обеспечивает быстрое решение задачи формирования прон мышленно-сырьевых узлов и дает лицу, принимающему решения, возможность опен ративной оценки вариантов районирования и интерактивного анализа их чувствин тельности.
5. Предложен метод учета в задаче формирования промышленно-сырьевых узлов огран ничения на разброс значений заданной скалярной характеристики объектов в группе, позволяющий учитывать специфические требования, возникающие при решении зан дачи формирования промышленно-сырьевых узлов, с помощью введения логических функций.
6. Разработаны программные модули для решения различных вариантов задачи групн пировки, вошедшие в ГИС-ориентированную систему Геолого-экономическая карта региона (ВСЕГЕИ им. А.П. Карпинского). Некоторые модули реализуют авторские алгоритмы, другие являются лоболочками к пакетам решения задач целочисленнон го и частично целочисленного программирования SCIP и CPLEX.
7. Разработанные модели и программные модули использованы при решении задачи формирования промышленно-сырьевых узлов на месторождениях твердых полезных ископаемых Дальневосточного федерального округа. Результат на 95Ц98% совпал с результатом работы независимой экспертной группы.
Полученные результаты соответствуют п.4 Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки инн формации и п.9 Разработка проблемноЦориентированных систем управления, принятия решений и оптимизации технических систем паспорта специальности 05.13.01 Ч Системн ный анализ, управление и обработка информации.
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Опубликовано в рецензируемых изданиях из списка ВАК:
1. Пономарев А. В. Метод оптимальной группировки векторных объектов относин тельно центров / Мустафин Н. Г., Пономарев А. В., Савосин С. В. // Труды СПИИРАН.
СПб: Наука, 2012. Вып. 1(20). С. 208Ц22. Пономарев А. В. Методы и алгоритмы группировки геологических объектов / Мустафин Н. Г., Пономарев А. В., Савосин С. В. // Информационно-измерительные и управляющие системы. 2009. Т. 4. С. 71Ч74.
3. Пономарев А. В. Программно-технологический комплекс Единой информационнон аналитической системы Минерально-сырьевые ресурсы России / Дубенецкий В. А., Кран соткин С. И., Мустафин Н. Г. и др. // Программные продукты и системы. 2005. Т. 1. С.
9Ч13.
Опубликовано в других изданиях:
4. Пономарев А. В. Алгоритмическая поддержка задачи геолого-экономического райн онирования // Информационные технологии в экономике, образовании и бизнесе: материан лы международной научно-практической конференции / Под ред. А. Зарайский. Саратов:
Издательство ЦПМ Академия Бизнеса, 2011. С. 150Ч153.
5. Пономарев А. В. Модель группировки объектов, основанная на бинарных отношен ниях // Наука и техника XXI века: материалы международной заочной научно-практин ческой конференции. Новосибирск: Изд. Априори, 2011. С. 90Ч93.
6. Пономарев А. В. Применение генетических алгоритмов для группировки объектов // Наука и современность - 2011: сборник материалов XIII Международной научно-пракн тической конференции. Часть 2 / Под ред. С. Чернов. Новосибирск: Издательство НГТУ, 2011. С. 238Ч242.
7. Пономарев А. В. Использование метода локального поиска для решения задачи группировки объектов // Проблемы подготовки кадров в сфере инфокоммуникационных технологий. СПб научноЦпрактическая конференция. СПб: Сборник трудов конференции / СПОИСУ, 2011. С. 62Ц67.
8. Пономарев А. В. Модель данных для решения аналитических задач в ГИС-орин ентированной системе Геолого-экономическая карта региона / Водяхо А. И., Мустафин Н. Г., Первицкий А. Ю. и др. // Труды СПИИРАН. СПб: Наука, 2007. Т. 4. С. 345Ц356.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям