Содержание к диссертации
Введение
1. Задача синтеза топологической структуры при создании сетей беспроводного доступа 15
1.1 Развитие беспроводных сетей передачи информации 15
1.2 Сети 4G 1.2.1 Технология LTE и ее архитектура 18
1.2.2 Технология UMB и ее архитектура 20
1.2.3 Технология WiMAX и ее архитектура
1.2.3.1 Основные принципы архитектуры сети WiMAX 22
1.2.3.2 Варианты применения сетей WiMAX 24
1.2.3.3 Место WiMAX в иерархии структуры сетей NGN 26
1.2.3.4 Достоинства и недостатки 28
1.3 Этапы создания сети беспроводного доступа 30
1.3.1 Программный комплекс планирования сетей связи 32
1.4 Задача размещения базовых станций 34
1.4.1 Постановка модифицированной задачи размещения базовых станций 40
1.5 Выводы 44
2. Способы решения задач размещения 46
2.1 Анализ способов решения задач размещения 46
2.2 Метод полного перебора 51
2.3 Метод ветвей и границ 56
2.3.1 Метод ветвей и отсечений 59
2.4 Алгоритм поиска по соседству
2.4.1 Схема «обмена клиентами» 63
2.4.2 Схема «перемещение устройств обслуживания» 65
2.4.3 Структура алгоритма
2.5 Генетический алгоритм 68
2.6 Выводы з
3. Решение задачи оптимального размещения на основе муравьиных алгоритмов оптимизации 83
3.1 История появления муравьиных алгоритмов оптимизации 83
3.2 Особенности искусственных муравьев 85
3.3 Характеристики муравьиных алгоритмов оптимизации 88
3.4 Обобщенная структура алгоритмов муравьиной оптимизации 89
3.5 Принципы функционирования муравьиных алгоритмов оптимизации 94
3.6 Применение метаэвристики оптимизации муравьиной колонией к задаче оптимального размещения базовых станций 98
3.7 Выводы 114
4. Программная реализация и исследование предложенных алгоритмов 116
4.1 Среда разработки Borland Delphi 116
4.2 Реализация предложенных алгоритмов в среде
Borland Delphi 7.0 117
4.2.1 Интерфейс созданного программного обеспечения 119
4.3 Исследование алгоритмов на основе созданного программного обеспечения 126
4.3.1 Исследование метода полного перебора 126
4.3.2 Исследование генетического алгоритма 128
4.3.3 Исследование муравьиного алгоритма 138
4.4 Выводы 145
Заключение 147
Список используемой литературы
- Технология WiMAX и ее архитектура
- Схема «обмена клиентами»
- Характеристики муравьиных алгоритмов оптимизации
- Исследование алгоритмов на основе созданного программного обеспечения
Введение к работе
Актуальность темы. Стремительное развитие беспроводных телекоммуникационных технологий в последние два десятилетия привело к непрерывной смене стандартов в области беспроводной связи. Характерной особенностью всех стандартов, разработанных в последние годы, является ориентация на обеспечение требуемых показателей качества обслуживания QoS. Не исключением является и стандарт IEEE 802.16-2004, на который ориентировано представленное диссертационное исследование, - стандарт беспроводных сетей для организации фиксированного широкополосного доступа.
Диссертация посвящена одной из множества задач, возникающих при создании сетей IEEE 802.16-2004 - а именно, оптимальному размещению базовых станций и подключению к ним абонентов. Речь идет о минимизации целевой функции суммарной стоимости сети при решении задачи синтеза топологической структуры беспроводной сети фиксированного широкополосного доступа, учитывающей соблюдение параметров качества обслуживания пользователей. Решение подобной задачи приводит к сокращению капитальных затрат оператора связи на создание сети при условии соблюдения параметров качества обслуживания, что в свою очередь влияет на качество предоставляемых услуг, а соответственно и на доходы оператора связи. К тому же, в открытой печати наблюдается недостаток опубликованных исследований, посвященных решению задачи оптимального размещения базовых станций в сетях IEEE 802.16-2004. В связи с этим тема диссертационной работы является актуальной.
Среди публикаций, посвященных изучению методологии создания сетей IEEE 802.16-2004 и решению задач размещения базовых станций, следует отметить исследования Вишневского В.М., Ляхова А.И., Портного С.Л., Шахно-вича И.В., Широкова В. Также существуют исследования, ориентированные на решение общих задач размещения, среди которых можно выделить работы Кочетова Ю.А., Пащенко М.Г., Вереснева В.Л. Среди зарубежных ученых стоит отметить фамилии Murphy S., Amaldi Е., Capone A., Sridharan R., Klincewicz J.G., Barcelo I, Beasley IE.
Цель работы. Исследование существующих и разработка новых методов, позволяющих оптимизировать размещение базовых станций с точки зрения минимизации целевой функции стоимости при обеспечении требуемых характеристик качества обслуживания. Анализ предложенных алгоритмов, оценка влияния параметров настройки алгоритмов на время и качество решения.
Основные задачи исследования.
формулировка критериев задачи оптимизации, учитывающих потери сигналов при распространении;
анализ существующих методов решения NP-трудных задач размещения;
разработка алгоритмов оптимального размещения базовых станций и подключения к ним абонентов;
создание программного обеспечения для решения задач размещения любой размерности и конфигурации;
проведение вычислительных экспериментов на основе созданного программного обеспечения.
Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов комбинаторной оптимизации, теории графов, теории алгоритмов, и объектно-ориентированного программирования.
Научная новизна работы.
предложена модифицированная постановка задачи оптимального размещения базовых станций, учитывающая модель распространения сигналов в радиоканале;
предложен алгоритм размещения базовых станций на основе генетического подхода;
предложен алгоритм размещения базовых станций на основе метода роевого интеллекта;
Основные положения, выносимые на защиту.
модифицированная постановка задачи размещения базовых станций;
эволюционный метод вычислений, представленный генетическим алгоритмом, для решения задач размещения базовых станций;
метод роевого интеллекта, представленный алгоритмом муравьиной колонии, для решения задач размещения базовых станций;
результаты сравнительного анализа предложенных алгоритмов размещения базовых станций.
Практическая ценность и реализация результатов работы.
Применение предложенных в диссертации алгоритмов для оптимального размещения базовых станций, позволяет сократить капитальные затраты телекоммуникационных компаний при развертывании беспроводных сетей фиксированного широкополосного доступа. Решение задачи в формулировке, учитывающей потери сигналов в радиоканале и качество обслуживания абонентов, а также направленной на минимизацию суммарной стоимости комплекса благоприятно скажется как на ценовой политике для конечного пользователя, так и на его лояльности.
Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными организациями и телекоммуникационными компаниями при проектировании и внедрении сетей стандарта WiMAX.
Основные теоретические и практические результаты, полученные в диссертации, использованы в ООО «Саха-Белком» и внедрены в учебный процесс ГОУВПО ПГУТИ, что подтверждено соответствующими актами.
Работа выполнена при поддержке гранта 2007 года для студентов, аспирантов и молодых ученых от Министерства образования и науки Самарской области (шифр гранта 302ТЗ. Ж).
Апробация работы. Основное содержание работы докладывалось и обсуждалось на VIII Международной научно-технической конференции «Про-
блемы техники и технологий телекоммуникаций» (Уфа, 2007г.), на IX - XII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2007 - 2010гг.), IX Международной научно-технической конференции «Кибернетика и высокие технологии» (Воронеж, 2008г.).
Публикации. По теме диссертации опубликовано 16 работ, в том числе 2 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 1 статья в журнале «Telecommunication Sciences» (Украина), 6 тезисов, 6 докладов в трудах международных научных конференций, а также 1 свидетельство о регистрации программы для ЭВМ.
Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Основная часть работы содержит 163 страницы машинописного текста, 39 рисунков, 29 таблиц. Список литературы включает 111 наименований.
Технология WiMAX и ее архитектура
Сети второго поколения были основаны уже на цифровом стандарте мобильной связи GSM, разработанном в ETSI, и появились в начале 1990-х годов. Однако предназначались они, прежде всего, для передачи речи и низкоскоростных данных в виде SMS [6]. Также существуют стандарты D-AMPS, JDC, CDMA [7]. Впрочем, системы 2G, будучи наиболее популярными в 1990-х годах, остаются таковыми и до сегодняшнего дня.
Промежуточным важным шагом эволюции от сетей 2G к сетям 3G стало внедрение технологии пакетной передачи данных GPRS, которая позволяет предоставлять услуги, аналогичные услугам сетей мобильной связи третьего поколения, и использует стандарт GSM как базовый. Технология основана на передаче данных по сети с коммутацией пакетов параллельно с передачей речи в режиме коммутации каналов и обеспечивает передачу данных со скоростью до 115 Кбит/с. Внедрение подсистемы GPRS не требует кардинальной модернизации существующей сетевой инфраструктуры GSM [8]. Технология EDGE, разработанная для повышения скорости передачи данных до 384 Кбит/с в подсистеме GPRS, предусматривает модуляцию с большей спектральной эффективностью и алгоритмы адаптации каналов связи в зависимости от требований абонента и наличия помех. В ней используются существующие протоколы радио интерфейса стандарта GSM, и для ее внедрения не требуется создания новых сетевых элементов (она совместима с GSM/GPRS). Во второй половине 1990-х годов произошел переход от сетей GSM с технологией EDGE к сетям 3G. Вначале МСЭ предполагал разработать единый глобальный стандарт на технологию радио интерфейса системы 3G, этот проект был позднее переименован в IMT-2000. После завершения процесса гармонизации в семейство стандартов радиодоступа вошли пять радио интерфейсов [9, 10]. Система UMTS [11] (европейский стандарт сетей 3G) в ходе своего развития имела несколько релизов, последние из которых содержат разработку спецификаций по управлению качеством услуг для технологии высокоскоростного доступа с коммутацией пакетов в линии «вверх» HSUPA и в линии «вниз» HSDPA. Стоит отметить, что с помощью сетей 3G можно передавать большие объемы информации с высокими скоростями до 2048 Кбит/с.
В настоящее время организациями 3GPP и 3GPP2 разрабатываются и тестируются технологии четвертого поколения мобильных сетей 4G.
Если рассматривать четвёртое поколение мобильных телекоммуникаций, то это будет долгосрочная эволюция систем 3G. Международное телекоммуникационное сообщество признало необходимость перехода к новым сетям 4G, одобрив и приняв к использованию рекомендацию МСЭ ITU-RM. 1457-7 в октябре 2007 г. Предполагается, что системы мобильной связи четвертого поколения будут основываться на следующих технологиях: LTE, WiMAX. Каждая из них обладает своим набором достоинств и недостатков, поэтому наиболее вероятным вариантом развития будет их взаимное сосуществование в зависимости от специфики деятельности операторов связи. Еще одним возможным претендентом на право называться технологий 4G является технология UMB, которая пока не находит широкого распространения. Скорости передачи информации, поддерживаемые сетями 4G, позволят обеспечить внедрение таких услуг, как мобильное телевидение высокой четкости, организация видеоконференций, видео телефония, глобальный роуминг, VoIP, высокоскоростной Интернет и другие мультимедийные услуги. Примечательной особенностью при появлении сетей 4G станет переход от концепции Triple Play к концепции Quadro Play, в которой под четвертым компонентом подразумевается полная мобильность абонента.
Консорциум 3GPP заявил об утверждении спецификаций для наземной сети радиодоступа LTE 17 января 2008 г. и в настоящее время осуществляется контроль над внесением в них изменений. Основной целью является поддержка развития высокопроизводительных сетей мобильной связи следующего поколения, технологий широкополосного доступа, внедрение передовых технологий 3GPP LTE. Первоначально были определены основные характеристики, которым должен отвечать будущий стандарт: улучшение эффективности сети, а также предоставляемых через нее сервисов, повышение скорости обмена информацией, интеграция технологии с другими стандартами связи, уменьшение энергопотребления и стоимости пользовательских терминалов.
Однако скорость - не единственное достоинство LTE. В рамках данного стандарта также удалось добиться существенного уменьшения задержки между отправкой запроса и получением данных. Кроме того, терминал, поддерживающий данную технологию, сможет функционировать в любых частотах, предоставляемых различными операторами (от 450 МГц до 2,6 ГГц).
Можно отметить следующие характеристики LTE [12]: - увеличение максимальной скорости данных до 50 Мбит/с в восходящем и до 100 Мбит/с в нисходящем каналах; - масштабируемость полосы пропускания от 1,4 до 20 МГц, как в восходящем канале, так и в нисходящем каналах; - поддержка многоантенных систем MIMO и технологии OFDM; - зона покрытия одной базовой станцией - до 30 км в штатном режиме; - обеспечивается поддержка соединений для абонентов, движущихся со скоростью до 350 км/ч; - сосуществование с официальными стандартами при переходе всех сетей на передачу IP пакетов. Для технологии LTE консорциум 3GPP предложил новую сетевую инфраструктуру (SAE - System Architecture Evolution). Цель и сущность концепции SAE — эффективная поддержка широкого коммерческого использования любых услуг на базе IP и обеспечение непрерывного обслуживания абонента при его перемещении между сетями беспроводного доступа, которые не обязательно соответствуют стандартам 3GPP (GSM, UMTS, WCDMA) (рис. 1.3, [13]).
Схема «обмена клиентами»
Метод, описанный в [40], несколько отличается от вышеприведенных способов решения. В нем автор разделил подзадачу Лагранжа на п задач «рюкзака», соответственно, по одной задаче для каждого устройства обслуживания, и из этих комбинированных решений получал оценку нижней границы для задачи с множеством задействованных устройств обслуживания. Это множество устройств обслуживания далее используется для постановки транспортной задачи с одним источником, чье оптимальное решение, полученное посредством метода ветвей и границ, обеспечивает допустимое решение и верхнюю границу исходной задачи.
Подобный подход, основанный на отказе от ограничений, отвечающих за подключение клиентов только к одному устройству обслуживания и решении задач «рюкзака», предложен в [41]. В соответствие с исчерпывающим исследованием, проведенным в [42], метод, рассмотренный в [41] обеспечивает наилучшие допустимые решения среди вышеупомянутых подходов.
В указанной работе [42], автор также предложил другую эвристику Лагранжа, основанную на отказе от выполнения ограничений, отвечающих как за назначение клиентов только одному устройству обслуживания, так и ограничений на количество ресурсов данного устройства. Заслуга данного подхода заключается в его робастности, поскольку он обеспечивает решения хорошего качества на широком диапазоне различных задач размещения.
В последние годы для решения задачи SSCFLP были применены такие способы как: табу-поиск, имитация отжига, генетические алгоритмы [43]. Кроме того, некоторые исследователи, благодаря развитию вычислительной техники, а, соответственно, и возможности решать задачи большей размерности, стали использовать метод ветвей и границ в сочетании с различными методами, например, такими как метод отсечений.
Таким образом, на основе анализа работ, посвященных решению задач размещения устройств обслуживания, удалось выявить следующие закономерности:
1. Большинство работ основано на использовании метода Лагранжевых релаксаций. Лагранжевы релаксации получаются путем перехода к двойственной задаче относительно исходного множества дополнительных ограничений. В основном, релаксация применяется по отношению к ограничениям (2.2) и (2.3). Под релаксацией понимается процедура, при которой происходит ослабление требований к первоначальным ограничениям задачи, т.е. осуществляется замена задачи минимизации функции по некоторому множеству решений на задачу минимизации по некоторому более широкому множеству [44]. Получившаяся задача уже легко решается, как правило, на основе методов субградиентной оптимизации, и ее оптимальное решение дает оценку снизу для целевой функции исходной задачи. Эти итеративные процедуры формируют последовательность векторов, которые, начиная с некоторого начального значения, меняются по определенному правилу [45].
Если разрыв целочисленности равен нулю, то такой подход дает возможность найти оптимальное решение задачи и доказать его оптимальность. В противном случае, когда полученная нижняя оценка не является точной, она может быть использована в методе ветвей и границ и/или служить начальным приближением для эвристических методов.
2. Практически все исследователи в своих попытках решить задачи размещения устройств обслуживания используют различные эвристические методы, что является вполне обоснованным. Как было сказано выше, задачи класса CFLP являются NP-трудными. На современном этапе развития методов оптимизации не известны алгоритмы, обеспечивающие точное решение таких задач за полиномиальное время. Равно как и не доказано, что они в принципе не существуют [46]. Способы, используемые для решения задач класса NP можно разбить на две общие категории. К первой категории относятся подходы, в которых делается попытка максимального сокращения объема перебора, хотя при этом и признается неизбежность экспоненциального времени работы. К наиболее широко используемым приемам сокращения перебора относятся методы отсечений, методы ветвей и границ, методы «неявного» перебора [47], метод Лагранжа [48, 49]. Ко второй категории относятся подходы, основанные на приеме, который можно назвать «снижение требований». Он заключается в отказе от поиска оптимального (точного) решения за экспоненциальное время и в нахождении вместо этого субоптимального (близкого к точному) решения за приемлемое время. Алгоритмы, использующие такой прием, обычно называются эвристическими, поскольку они используют различные разумные соображения без строгих обоснований.
На основе вышесказанного было принято следующее решение. Поскольку задача диссертационного исследования обладает явной практической направленностью и ее решение желательно обеспечить в режиме реального времени, то рациональным способом ее решения будет применение эвристических методов оптимизации. Поэтому программное обеспечение, представленное в главе 4, решает поставленную задачу точным методом перебора и двумя эвристическими методами. Эти методы обеспечивают субоптимальные решения в режиме реального времени.
Характеристики муравьиных алгоритмов оптимизации
Среди главных особенностей муравьиных алгоритмов оптимизации (МАО) можно выделить следующие: положительная обратная связь, распределенное вычисление, использование «жадной» эвристики. Положительная обратная связь нужна для быстрого обнаружения хороших решений, распределенное вычисление позволяет избегать пригодными для параллельных преждевременной сходимости, а жадная эвристика помогает находить приемлемые решения на ранних стадиях процесса поиска. Отметим некоторые характеристики, которыми обладают муравьиные алгоритмы: - этот подход обладает гибкостью, поскольку он может быть применен для похожих разновидностей одной и той же задачи; - также обладает свойством робастности, так как может быть применен к совершенно различным задачам комбинаторной оптимизации, естественно при правильной интерпретации входных данных и ограничений; - является подходом, основанным на популяции, как и генетический алгоритм. Этот факт позволяет использовать положительную обратную связь как механизм поиска, и делает муравьиные алгоритмы вычислений в многопроцессорной системе [91].
В муравьином подходе к решению задач поисковая деятельность распределяется через множество так называемых «муравьев», т.е. агентов с очень простыми основными возможностями, которые в некоторой степени имитируют поведение настоящих муравьев.
Для применения муравьиного подхода к решению конкретной задачи комбинаторной оптимизации требуется определить следующие моменты [92]: 1. Подходящее представление задачи в виде графа. 2. Автокаталитический (т.е. положительный) процесс обратной связи. 3. Способ удовлетворения ограничений, присутствующих в задаче. 4. Определить эвристическую функцию.
Для того чтобы применить подход, основанный на оптимизации муравьиной колонией, для решения той или иной задачи, сначала необходимо выбрать подходящее представление в виде адекватной модели [93]. Затем следует определить один из центральных моментов - процедуру обновления феромона. Модель задачи оптимизации определяется в виде P — (S,Q,f) и состоит из: - пространства поиска S, определяемого через конечное множество дискретных переменных; - множества Q ограничений среди переменных; - целевой функции /, для которой необходимо найти максимум или минимум. Пространство поиска S определяется следующим образом. Задано. множество дискретных переменных Xt,i = l,...,n, принимающих значения v/ eD; = V/,...,v . Назначение величины v/ для конкретной переменной Xt обозначается в виде Xi — v/. Решение s eS, представляющее полное назначение всех переменных, является допустимым решением задачи, если каждой переменной решения присвоено определенное значение, и при этом выполняются все ограничения из множества D.. Если множество Q — пустое, то Р называется моделью задачи без наличия ограничений. Решение s є называется глобальным оптимумом в том и только в том случае, когда f(s ) f(s) VseS или f(s ) f(s) VseS в зависимости от специфики решаемой задачи. Множество всех глобально оптимальных решений обозначается S с5. Решение задачи комбинаторной оптимизации требует нахождения, по крайней мере, одного s GS . Модель задачи комбинаторной оптимизации используется затем для описания модели феромонного распределения, которая также применяется в МАО [94]. Сначала определяется переменная X,=v/ (т.е. переменная Xt, которой присвоено значение v/ из области Dt), которая называется компонентом решения и обозначается с». Множество всех возможных компонентов решений обозначается через С. Затем параметр феромонного следа Ту ассоциируется с каждым компонентом Су. Множество всех возможных параметров феромонных следов обозначается через Т. Значение параметра феромонного следа Ту обозначается как Ту, и называется значением феромона или феромонным уровнем. Стоит заметить, что феромонные значения, в общем, являются функцией от шага t на какой либо итерации алгоритма: ті:=тіЛі). Эти феромонные значения затем используются и обновляются во время поиска решения, что позволяет моделировать распределение вероятностей для различных компонентов решения.
Введем понятия итерации и шага алгоритма. Если в искусственной колонии присутствуют а муравьев, то шагом алгоритма называется а передвижений, выполненных всеми муравьями за интервал времени (t,t + l), т.е. за один шаг каждый муравей совершает переход к следующему компоненту решения. Тогда после п шагов (где п - количество компонентов решения), которые называются итерацией алгоритма (или циклом), каждый муравей посещает все компоненты решения. Таким образом, одна итерация алгоритма (один цикл) состоит из посещения компонентов решения всеми муравьями, улучшения полученных решений с помощью локального поиска (в случае его использования), и процедуры феромонного обновления.
В МАО искусственные муравьи строят решение комбинаторной задачи оптимизации, перемещаясь по так называемому конструирующему графу GC(V,E). Граф содержит множество вершин V и множество ребер Е.
Множество компонентов решения С может быть ассоциировано либо с множеством вершин V графа GC(V,E), либо с множеством его ребер Е. Муравьи двигаются от вершины к вершине по ребрам графа, последовательно
Исследование алгоритмов на основе созданного программного обеспечения
Расчет потерь на основе канальной модели SUI при распространении сигналов между базовыми и абонентскими станциями осуществляется в отдельной форме, которая вызывается нажатием кнопки «Калькулятор потерь», расположенной на вкладке «Расчет» (рис. 4.7).
Таким образом, действия пользователя при работе с созданным программным обеспечением состоят в следующем. После открытия исполняемого файла, скомпилированного как Ants.exe, пользователь расставляет на карте с декартовыми координатами места кандидаты и клиенты.
Затем необходимо задать исходные параметры для базовых станций и клиентов, выбрать один из способов решения задачи, задать параметры настройки алгоритмов, рассчитать потери при распространении и нажать на кнопку «Запуск расчета», расположенную на вкладке «Расчет».
Ход выполнения работы алгоритма в процентном отношении отображается в виде компонента Progress Bar. Завершение работы алгоритма соответствует значению 100 %, отображаемому на компоненте. После этого на экране монитора появляется окно, содержащее результаты расчетов (рис. 4.8). В этом окне представлено: количество клиентов и количество мест кандидатов, присутствующих в начале работы алгоритма; строка, содержащая число установленных в итоге базовых станций после работы алгоритма. Также отображается выбранный пользователем способ решения задачи и время, затраченное выбранным алгоритмом на поиск решения. Другой важнейшей составляющей результатов работы является «Матрица размещения клиентов» и «Матрица размещения базовых станций» присутствующие на форме
«Результаты расчета» в виде таблиц. В первой отображаются сведения о том к какой базовой станции, размещенной на определенном месте кандидате, подключен конкретный клиент, также указано расстояние от базовой станции до конкретного подключенного клиента и стоимость его подключения. В случае невозможности подключения клиента по причине его непопадания в зону действия ни одной из станций, или из-за превышения значения производительности базовой станции, в матрице размещения клиентов отображается соответствующая информация. В матрице размещения базовых станций отображается информация о том на каких местах кандидатах установлены базовые станции, а на каких не установлены. Суммарная стоимость комплекса представлена отдельной строкой.
Для тестирования разработанного программного обеспечения при решении задач размещения базовых станций и подключения к ним клиентов были проведены компьютерные эксперименты. Все испытания проводились на персональном компьютере с двух ядерным процессором Intel Core 2 Duo 2,66 ГГц, оперативной памятью 3,25 Гб и операционной системой Windows ХР SP2. Для тестирования разработанных алгоритмов были сгенерированы случайным образом задачи трех типов: малой, средней и большой размерности.
Для проведения экспериментов на основе метода полного перебора была сгенерирована задача малой размерности га = 6, к = 5, в которой клиенты и места кандидаты были размещены случайным образом. Первый эксперимент состоял в определении зависимости времени работы при увеличении числа клиентов, при этом количество мест кандидатов оставалось постоянным т = 6. Результаты представлены в табл. 4.1. Соответствующий график приведен на рис. 4.9.
Второй эксперимент заключался в определении зависимости времени работы при увеличении числа мест кандидатов, при этом количество клиентов оставалось постоянным к = 5, Результаты представлены в табл. 4.2. Соответствующий график приведен на рис. 4.10.
Зависимость времени работы полного перебора от числа клиентов Таблица 4.2. Результаты времени работы решения задач размещения методом полного перебора при постоянном числе клиентов
Для проведения исследования на основе предложенного генетического алгоритма была выполнена серия экспериментов. Прежде всего необходимо было определить, способен ли разработанный генетический алгоритм решать задачу размещения базовых станций и каково качество получаемых решений. Для ответа на эти вопросы было использовано множество задач, что и при исследовании полного перебора. Сначала изменялось количество клиентов при постоянном числе мест кандидатов, а затем изменялось число мест кандидатов при постоянном количестве клиентов. Значения целевых функций приведены соответственно в табл. 4.3 и 4.4. В представленных задачах малой размерности генетический алгоритм выдавал наилучшее значение при каждом испытании. Количество проведенных испытаний составило 100 запусков алгоритма.
Представленные данные свидетельствуют о том, что на задачах малой размерности генетический алгоритм обеспечивает получение точных значений целевой функции, как и метод полного перебора, обеспечивающий точное решение при каждом запуске алгоритма. При этом теория генетических алгоритмов дает основание полагать, что при повышении размерности решаемых задач генетический алгоритм будет обеспечивать получение
130 субоптимальных решений, отличающихся от точных. Однако проверить данный факт посредством экспериментов не представляется возможным по причине экспоненциальной зависимости времени работы полного перебора от количества входных данных.
Согласно [64] качество генетического алгоритма оценивается расстоянием D = \f\ — fylf\, где fx - глобальный оптимум, полученный экспериментально (методом полного перебора), f2 - лучшее значение, найденное генетическим алгоритмом. Из таблиц 4.3 и 4.4 видно, что в представленных экспериментах расстояние D равно нулю, что свидетельствует о 100 % точности генетического алгоритма.
