Размещено на http://www.allbest.ru/

Таганрогский государственный радиотехнический университет

Генетический алгоритм плоской укладки

Л.А. Гладков, В.М. Курейчик

347928, Ростовская обл., г. Таганрог, пер. Некрасовский 44,

kur@tsure.ru; kurgla@tsure.ru

Аннотация

искусственный интеллект технология

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

Введение

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

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

1. Постановка задачи

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

1.1 Инструментарий

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

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

1.2 Основные положения

За основу алгоритма принята теорема МакЛейна о том, что граф можно уложить на плоскости без пересечений, если на множестве его циклов можно построить некоторый базис Bp, содержащий p - циклов таких, что каждое ребро графа принадлежит строго двум циклам, где p = m - n + 2 (m - число ребер, а n - число вершин графа). Построение оптимального решения либо множества максимально близких к нему решений является основной задачей алгоритма.

Схема метода предусматривает его разделение на отдельные операции. В качестве исходных данных используются модифицированные списки смежности графа, на основании которых выполняется генерация циклов. Экспериментальные исследования, проведенные ранее, показали, что для однозначного решения задачи достаточно исследовать множество самых коротких циклов графа, например циклов длины 3 - 4, что позволяет сократить время работы алгоритма.

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

1.3 Параметры ГА

Данное множество циклов передается в основной блок алгоритма - блок генетических операторов (БГО), где выполняется исследование и генерация решения.

1.3.1 Методика кодирования и оценка качества

Эффективность работы генетических алгоритмов обратной связи во многом зависит от способа кодирования данных. С учетом специфики решаемой задачи была предложена специальная хромосома, с числом разрядов равным p + 3. Первые p разрядов хромосомы представляют собой номера циклов задействованных в текущем решении. Дополнительные три разряда используются для оценки качества получаемого решения. Разряд № p + 1 содержит информацию о ребрах не задействованных в данном решении, разряд p + 2 - ребра, задействованные один раз и разряд p + 3 - ребра, использованные дважды. Для оценки качества полученного решения вводится функция (m):

(m) = ( 2Nmp+3 + Nmp+2 ) / 2m, (1)

где Nmp+3 - число элементов в p + 3 - разряде хромосомы, Nmp+2 - соответственно число элементов в p + 2 - разряде хромосомы, а m - число ребер в исследуемом графе.

Как видно из формулы, значения которые может принимать функция оценки (m) находятся в интервале [0; 1], причем качество решения тем выше, чем больше число ребер, задействованных в оцениваемом решении (прежде всего встречающихся дважды).

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

Таким образом, целевая функция хромосомы полученного решения (H) является аддитивной функцией двух переменных:

(H) = ((m); L0) (2)

Причем (H) max, когда (m) 2m L0 0.

1.3.2 Методика формирования начальной популяции

В алгоритме предусмотрены два варианта стратегии формирования множества начальных решений.

1. Из множества циклов C выбираем ребра, повторяющиеся дважды. Циклы, которым принадлежат найденные в результате такого поиска ребра образуют комбинацию, представляющую собой начальное решение. Если в ней оказываются «нелегальные ребра» (т.е. повторяющиеся более 2 раз), то из комбинации удаляется минимально возможное число циклов, содержащих «лишние» ребра и комбинация преобразуется в хромосому. Таким образом получается базовое начальное решение.

2. Начальное базовое решение формируется за счет объединения случайно выбранных пар циклов, имеющих как минимум одно общее ребро.

Множество промежуточных решений формируется путем попарного объединения циклов, имеющих одинаковые ребра. Причем номера получаемых таким образом парных ребер обязательно должны совпадать с номерами ребер, записанных в разрядах p + 1 или p + 2 базового начального решении. Кроме того, номера циклов из множества промежуточных решений не должны совпадать с номерами циклов участвующих в базовом решении.

Размер популяции промежуточных решений зависит, таким образом, от числа ребер, содержащихся в разрядах p + 1 и p + 2 хромосомы базового решения.

1.3.2 Методика выбора промежуточных решений

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

1. Минимальное число совпадений номеров ребер в разрядах p + 2 и p + 3 претендента и разряде p + 3 первого родителя.

2. Максимальное число одинаковых ребер в разряде p + 1 претендента и разряде p + 3 первого родителя.

3. Максимальное число совпадений ребер из p + 2 претендента с ребрами из разряда p + 2 хромосомы первого родителя.

На основе данных правил был разработан специальный комплексный параметр - функция пригодности промежуточных решений относительно базового решения '(H). Данный параметр является аддитивной функцией двух переменных '(H) = ('m; N'c), где 'm - относительное увеличение числа ребер; N'c - относительное увеличение числа циклов. Количественное значение функции пригодности рассчитывается так:

а) Подсчитывается число совпадений Nd1 ребер из разряда p + 3 оцениваемого промежуточного решения с ребрами из разряда p + 3 первого родителя. Затем подсчитывается число совпадений Nd2 в разрядах p + 3 промежуточного решения и p + 2 первого родителя, а также число совпадений Nd3 в разрядах p + 2 промежуточного решения и p + 3 родителя. Сумма их величин характеризует возможное число ребер, которые необходимо будет удалить из базового решения после выполнения ОК. Т.е., в оптимальных промежуточных решениях значение суммы будет стремиться к нулю;

б) Подсчитывается число совпадений Ns1 ребер из разряда p + 3 оцениваемого промежуточного решения с ребрами из разряда p + 1 первого родителя. Затем подсчитывается число совпадений Ns2 в разрядах p + 2 промежуточного решения и p + 1 первого родителя, и наконец, подсчитывается число совпадений Ns3 в разрядах p + 2 промежуточного решения и p + 2 родителя. Здесь определяется число ребер, добавляющихся в базовое решение после ОК, т.о. качество промежуточного решения тем выше, чем больше значение этой суммы;

в) Подсчитывается значение 'm по формуле:

'm = 1 - [(2Nd1 + Nd2 + Nd3) / (2Ns1 + Ns2 + Ns3)] (3)

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

г) Сравниваются номера ребер в разрядах p +2 и p + 3 промежуточного решения с номерами ребер в разряде p + 3 базового решения и, при наличии совпадений, определяется минимальное число циклов Nc-, которые необходимо удалить из базовой хромосомы после выполнения ОК для устранения нелегальных решений, т.е. значение Nc в оптимальном промежуточном решении будет стремиться к нулю;

д) Подсчитывается значение N'c по формуле:

N'c = 1 - (Nc- / Nc+) (4)

е) Подсчитывается значение функции пригодности хромосомы относительно текущего базового решения '(H).

1.3.3 Методика улучшения базового решения

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

1. В 1-м родителе 1-я точка скрещивания t1 всегда находится за последним значащим (ненулевым) элементом хромосомы hi, 2-я точка t2 выбирается после элемента hi+k, где k - число значащих элементов во 2-й родительской хромосоме.

2. Во 2-м родителе 1-я точка всегда находится перед 1-м элементом хромосомы, а 2-я точка определяется также как в случае с 1-м родителем.

В результате выполнения ОК происходит объединение значащих частей родительских хромосом. Если функция пригодности второго родителя 'm(H) 1, то из хромосомы потомка удаляются ребро (или ребра), повторяющиеся в данной комбинации более двух раз. Параллельно с удалением ребер удаляются Nc- - циклов, которым принадлежит данное ребро. Однако вновь появившиеся в хромосоме циклы не могут быть удалены.

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

При получении решения, не дающего улучшения на протяжении значительного числа поколений к нему применяются операции мутации и инверсии. Для этого случайным образом выбираются два разряда (значащий и незначащий). После обмена значащий элемент обнуляется, а все принадлежащие данному циклу ребра удаляются из генов p + 2 и p + 3.

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

1.4 Результаты

Разработаны и экспериментально апробированы новые архитектуры поиска путем установления баланса в системе, построения порядка из хаоса, иерархии встроенных систем. Программная реализация алгоритма имеет линейную характеристику временной сложности. Так, например, для исследования графовой математической модели размерностью порядка 150 вершин на ЭВМ типа IBM PC с процессором Pentium II в среде Windows 98, требуется примерно 7 минут и порядка 800 килобайт свободной оперативной памяти.

Заключение

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

Размещено на Allbest.ru