WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 55 | 56 || 58 | 59 |   ...   | 82 |

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

Без ограничения общности представим (2) как задачу нахождения min L.

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

Основным понятием ЕА является генеральная совокупность - все множество возможных решений. В нашем случае определим генеральную совокупность как множество векторов X = (x0,x1,x2,...,xk,xn), где x0 - место дислокации пожарного подразделения, xn - номер перекрестка, ближайшего к месту пожара.

Таким образом, значениями элементов вектора X является последовательность номеров перекрестков, которые необходимо проехать для того, чтобы прибыть в xn. Заметим, что количество перекрестков, в общем случае, является переменным. Минимальное значение k определяется номером квазиокружности (см. рис. 1), на котором лежит перекресток xn, максимальное значение может быть достаточно большим.

Все xi, i = 0,k являются разными и ни одно из них не совпадает с xn. На первый взгляд, оптимальнее будут те варианты, у которых xi < xj для всех i < j, но выполнение такого условия не является обязательным.

Модель целевой функции Адекватное применение ЕА связано с превращениями числовых значений из двоичной системы исчисления в десятичную и наоборот. При этом возникает информационная избыточность, поскольку не все двоичные представления имеют свои аналоги в десятичной системе. В общем случае, это приводит к необходимости привлечения дополнительных вычислительных ресурсов и увеличения времени решения задачи [Кисляков 2000, 2001].

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

Важной процедурой является определение выборочной последовательности, которая должна иметь свойство репрезентативности [Goldberg, 1989; Werbos, 1974; Исаев, 2000; Jensen, 2001]. Векторы выборочной последовательности могут иметь разное количество элементов, что связано с количеством перекрестков на пути проезда. Их генерация происходит с учетом содержания матрицы S. Первый и последний элементы векторов одинаковы (перекресток, где находится пожарное депо и ближайший перекресток к месту пожара). Другие элементы определяются случайным образом, но с учетом XII-th International Conference "Knowledge - Dialogue - Solution" выполнения условия, что из места дислокации пожарного подраздела можно попасть на один из 4-х перекрестков, а из каждого из них - уже на один из трех. Обозначим P - количество элементов в выборочной совокупности.

Для формирования целевой функции (fitness-function) можно применить два подхода. В первом случае необходимо иметь достаточное множество статистических данных, сгруппированных в табл. 2, и осуществить идентификацию зависимости Таблица Структура исходных данных для идентификации fitness-function Длина пути, L Количество № временного Качество дорожного Время проезда, T перекрестков, K интервала, g покрытия, q T = F(L,K,g,q), (4) где T - время следования пожарного расчета к месту пожара, K - количество перекрестков, которые он проехал, g- номер временного интервала, q- показатель качества дорожного покрытия, который интегрирует в себе и погодные условия. При правильной формализации задачи осуществить идентификацию (4) несложно. Достаточно предварительно выполнить нормализацию данных и применить метод наименьших квадратов для построения уравнения линейной регрессии [Наконечный, 1997], метод Брандона – для нелинейной регрессии [Чавкин, 2001], методы самоорганизации моделей – для полиномиальных зависимостей (метод группового учета аргументов [Ивахненко, 1975] или метод последовательных упрощений [Васильев, 2001]).

Во втором случае формирования целевой функции происходит эмпирически с использованием взвешивающих и поправочных коэффициентов. При этом используются данные матрицы T. Среднее время проезда из x0 в xn определяется по формуле (по одному из маршрутов):

n Tср. = (sij 0), (5) t ij i=0 ji где (*) - функция-индикатор. Ввиду того, что, в среднем, время прохождения пожарного расчета увеличивается с увеличением количества перекрестков, уточним (5):

T = w1 kn2 Tср, (6) где w1 - весовой коэффициент, который определяет значимость параметра количества перекрестков. С учетом качества дорожного покрытия целевая функция (5)-(6) является такой:

n T = w1 w2 kn2 qij (sij 0), (7) t ij i=0 ji где w2 - весовой коэффициент, указывающий на важность параметра качества дорожного покрытия.

Поскольку в разное время суток длительность прохождения пожарного расчета к месту пожара будет разной, то модель (7) необходимо уточнить:

w i n (8) i=Tv = kn2 (v = gt1) qij (sij 0), t ij gti=0 ji где w3 - весовой коэффициент важности временных интервалов, v - номер временного интервала.

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

248 Mathematical Foundations of AI Эволюционный метод определения оптимального пути следования пожарного расчета Учитывая то, что каждая вершина (перекресток) инцидентна только четырем другим вершинам, а их общее количество является достаточно большим (используется при построении матриц S и T), применять традиционное бинарное представление элементов вектора совокупности (хромосомы) в классическом ЭА нерационально. Пусть X1,X2,...,Xp - векторы выборочной совокупности (содержат множество перекрестков-маршрутов), упорядоченные по количеству элементов, т.е. Xi Xj, i < j. Для каждого из них, рассчитав значение функции (4), получим T1,T2,...,Tp.

Используя принцип последовательного преодоления неопределенности, кроссовер будем проводить по принципу последовательного отбора [Витковски, 2003; Алгулиев, 2004], в соответствии с которым большую вероятность участия в рекомбинациях имеют векторы с меньшим значением fitness-function.

Предположим, что необходимо определить оптимальный маршрут к перекрестку № 39 (см. рис. 1).

Для кроссовера выбраны векторы (0, 1, 5, 24, 12, 23, 39) и (0, 1, 12, 4, 11, 23, 39). Определяем, имеются ли одинаковые элементы в этих векторах, кроме первых двух и последнего элемента. Такой элемент - 12, он и является точкой рекомбинации. Осуществив кроссовер, получим два вектора-потомка: (0, 1, 12, 23, 39) и (0, 1, 5, 24, 12, 4, 11, 23, 39). Если одинаковых элементов нет, то один из векторов (с минимальным значением fitness-function) оставляем и случайным образом (с использованием принципа пропорциональности) выбираем другой вектор из выборочной совокупности. Результатом кроссовера будет ноль, один или два вектора. Ноль, если xi, xj : xi = xj, i j в каждом из векторов; один - если в одном; два, если указанные условия не выполнены ни для одного из векторов-потомков.

Получив P потомков, среди них и среди P родителей выбираем P наилучших векторов. Такой отбор называется элитным. Кроме него, существуют и другие методы отбора: селективный, панмиксия, отбор с вытеснением [Исаев, 2000]. Практическое моделирование засвидетельствовало преимущество именно элитного отбора, поскольку при нем не теряются оптимальные векторы-решения. Из всех видов отбора только для элитного теоретически доказано [Harti, 1990], что итерационный процесс поиска оптимального решения сходится.

Для предотвращения попадания fitness-function в локальный оптимум предусмотрена процедура мутации.

Происходит она с вероятностью 0,01 по такой схеме. Разыгрываем случайное равномерно распределенное на множестве {1,2,...,P} число. Если = k, то мутации подлежит k-й вектор выборочной совокупности. Если количество элементов в нем равняется d, то разыгрывается случайное число на множестве { 2,3,...,d -1 }. Мутации осуществляются у = L элементов, для чего осуществляется случайный выбор из двух вариантов (L +1) -го элемента. Критерием окончания процесса поиска оптимального решения является выполнение одного из следующих условий:

- достижение необходимого значения fitness-function;

- выборочная популяция состоит из одинаковых элементов;

- для любого значения > 0: Ti - Tj <, i, j, i j.

Если выполняются первое или третье условие, то решением задачи будет вектор, значение fitness-function которого является наименьшим.

Такой метод имеет свои преимущества перед классическим ЭА и недостатки, связанные с особенностями задачи. Преимуществом является значительное сокращение количества операций, что объясняется неприменением процедуры преобразования чисел в ЭА из десятичной системы счисления в двоичную и наоборот. Десятичное представление оптимизирует процедуру кроссовера за счет уменьшения времени формирования векторов-потомков. В пользу предложенного метода свидетельствует также то, что он не “привязан” к прямоугольной структуре улиц. Если на некоторых из них выполняется ремонт, то в матрицах XII-th International Conference "Knowledge - Dialogue - Solution" S и T достаточно на соответствующих местах поставить нули. К недостаткам отнесем проблему формирования выборочной совокупности, что связано с разным количеством элементов у векторовпредставителей. Кроме того, процедура определения каждого следующего элемента вектора требует пересмотра строки матрицы расстояний или времени, что при большом количестве перекрестков значительно увеличивает время работы алгоритма.

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

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

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

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

Для решения указанных проблем предлагается такая процедура. В соответствие с рис. 1 и матрицей 4 m расстояний строим матрицу N = (nij)i,j=1 (таблицу направлений, в которой показаны перекрестки, смежные 4 m фиксированному) и матрицу L = (lij)i,j=1 (таблица расстояний от фиксированного перекрестка к смежным) (табл. 3).

Таблица Таблица направлений Перекресток 0 1 2 3 4 5 6 7 8 9 10 11 Налево 2 6 7 8 0 14 15 * 17 18 3 4 Прямо 1 5 0 12 * 14 15 2 3 4 23 Направо 4 12 0 10 11 24 1 6 3 20 21 * Назад 3 0 8 9 10 1 2 17 18 * 20 21 Таблица расстояний между перекрестками Перекресток 0 1 2 3 4 5 6 7 8 9 10 11 Налево 1 3 3 5 6 3 2 * 3 2 4 4 Прямо 9 1 1 3 7 * 2 3 1 2 2 3 Направо 6 2 1 4 4 2 3 3 5 1 2 * Назад 3 9 1 2 2 1 1 2 1 * 2 3 Очевидно, что до фиксированного перекрестка существует большое количество путей, каждый из которых проходит через разное количество промежуточных перекрестков. Минимальное количество таких 250 Mathematical Foundations of AI перекрестков определяется номером квазиконцентрической окружности, проходящей через финальный перекресток. Максимальное количество перекрестков определяется экспертным путем и, чаще всего, не превышает тройного количества минимальных перекрестков в критических случаях, и двойного - в штатных ситуациях.

Определим в качестве конечного перекресток № 39 (см. рис. 1). Он принадлежит четвертой окружности, поэтому наименьшая длина хромосомы равняется четырем и она будет такой:

x(1) x(2) x(3) x(4) В хромосоме x(1) = 0 стартовая точка (депо), x(4) = 39 - конечная точка. Максимальную длину хромосомы положим равной восьми. Параллельно с выполнением традиционных операций ЭА, в предложенной процедуре необходимо придерживаться таких шагов. При инициализации выборочной популяции обеспечить равномерное представительство хромосом разной длины. Для этого разыгрываем случайное равномерно распределенное целое число из множества {4, 5, 6, 7, 8}, которое отвечает длине хромосомы. Если это число 4, то первый и последний ее фрагмент уже известны. Вспомогательная хромосома состоит из четырех генов. Первые два гена кодируют направление движения из x(1) (соответственно: 00 - налево, 01 - прямо, 10 - направо, 11 - назад), другие два – из x(4). На допустимость решения указывает выполнение ограничения, которое определяет то, что перекрестки x(2) и x(3) являются соседними. Для хромосом с большей длиной такая процедура выполняется рекурсивно.

Pages:     | 1 |   ...   | 55 | 56 || 58 | 59 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.