WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 58 |

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

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

покрытия осуществляется коллективом Целью является поиск оптимальной кластеров муравьев.

комбинации компонент.

В работах [6,7] построение минимального дерева Штейнера (МДШ) Основные модификации ACO осуществляется группой муравьев.

В литературе было предложено Коллектив решает задачу, которая не может несколько метаэвристических моделей быть решена одним агентом. Впервые Материалы XVI Международной конференции по нейрокибернетике используется двухканальная система деревом “гильотинного разреза”. Дерево непрямого обмена информации. Каждый разрезов формируется из двух типов муравей имеет свой цвет. При своём вершин (рис.2).

движении муравей метит путь и феромоном Множество вершин первого типа и своим цветом, и эта информация M={mi| i=1,2,…,nm}, являющихся листьями используется другими муравьями для дерева D, соответствуют модулям.

выбора пути. Множество вершин второго типа C={ci | i=1,2,…,nc}, соответствуют разрезам (H Новая парадигма комбинаторной или V). Для бинарного дерева разрезов оптимизации trees ant colony optimization всегда выполняется равенство nm = nc+1.

(T-ACO) V Основной особенностью алгоритмов генетического программирования (ГП), H H которые направлены на решение задач 4 5 автоматического синтеза программ на V V H V основе входных обучающих данных путем индуктивного вывода, являются древовидные структуры данных, H используемые для представления генотипа.

m1 m2 m3 m4 m5 m6 mДеревья в ГП составлены из узлов двух типов, узлов функций и узлов терминалов.

Терминалы – листья дерева, соответствуют m8 mлибо переменной данной области задачи, Рис.2. Дерево разрезов либо постоянной. Например, выражение xПредлагается новая парадигма + z может быть представлено деревом комбинаторной оптимизации trees ant (рис.1).

colony optimization (T-ACO), основанная на + идеях муравьиной колонии и в первую очередь на идее непрямого обмена - стигмержи (stigniergy), позволяющая осуществлять синтез дерева. Такой подход * Z является эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую X X интерпретацию в виде деревьев.

Рис.1. Представление выражения деревом Представление оптимизационной задачи в виде парадигмы T-ACO опирается на два Типичной задачей ГП является задача ключевых момента: формирование графа символического регресса. Символический поиска решений (ГПР) и построения регресс заключается в построении допустимых альтернативных решений математического выражения F, задаваемого (деревьев) на графе поиска решений.

примерами пар (x1, y1), (x2, y2),…, (xn, yn), Граф поиска решений G=(MC,U), где xi,и yi – входные и выходные записи.

строится следующим способом. Пусть nc=4, Обозначим как yi* значение выходной а nm=5. В начале, на вершинах множества С записи, получаемой с помощью выражения формируется полный граф (рис.3). Ребра F. Для оценки математического выражения неориентированные.

F используется критерий Вводится стартовая вершина S, которая D=|yi - yi *|.

дугами связывается с каждой вершиной Примером использования древовидных множества С (рис.4).

структур является формирование плана чипа путем рекурсивного разрезания прямоугольников на две части задаваемого 4-Й МЕЖДУНАРОДНЫЙ СИМПОЗИУМ «НЕЙРОИНФОРМАТИКА И НЕЙРОКОМПЬЮТЕРЫ» бинарное дерево Dk. Бинарное дерево Каждая вершина ciС связывается формируется на базе ГПР последовательно дугами со всеми nm вершинами множества от корня до листьев M (рис.5).

Пошаговый процесс построения дерева на базе ГПР начинается со стартовой вершины S. В результате осуществляется выбор корневой вершины с0C. На каждом шаге выбирается одна из еще не связанных c1 cc2 c вершин, которая связывается ребром с Рис.3. Первый этап построения ГПР одной из уже ранее выбранных и связанных вершин. На вершины ГПР накладываются S следующие ограничения. Вершины множества M могут быть в строящемся дереве только дочерними (листьями), в каждую вершину mjM входит только одно ребро ГПР. Вершины множества C должны быть связаны с двумя дочерними c1 c2 c3 c4 cвершинами из множества CM и сами в Рис.4. Второй этап построения ГПР свою очередь являются дочерними для некоторых вершин множества C.

S Изначально каждая вершина сiC обладает двумя вакансиями для связи с двумя дочерними вершинами. В процессе построения дерева вакансии вершин сiC ccпоследовательно заполняются. Процесс c1 cзавершается после заполнения всех вакансий.

Состояние процесса построения дерева на шаге t описывается следующими параметрами.

m1 m2 m3 m4 mПодмножества C1(t) C и M1(t) M Рис.5.Третий этап построения ГПР включают вершины уже вошедшие в состав строящегося дерева на t-1 предыдущих После построения ГПР на всех его шагах. Подмножества C2(t) C и M2(t) M ребрах откладывается начальное включают вершины, которые еще не вошли количество феромона Q/v, где v=|U|. В в состав строящегося дерева. C1(t)C2(t)= общем случае поиск решения задачи C, M1(t) M2(t)=M. Причем, если осуществляется коллективом муравьев Z={ C2(t)M2(t), то вершины множества C1(t) zk|k=1,2,…,nk}. Вначале муравьи должны обладать, хотя бы одной размещаются в стартовой вершине S.

вакансией.

Процесс поиска решений итерационный.

Процедура включения на шаге t На каждой итерации муравьиного вершины в состав строящегося дерева алгоритма каждый муравей zk строит свое производится с соблюдением условия конкретное решение задачи. Решением достаточности вакансий, суть которого является бинарное дерево в графе заключается в том, что если число вершин G=(MC,U). Каждая итерация l включает еще не вошедших в состав строящегося три этапа. На первом этапе муравей дерева больше единицы (т.е. |C2(t)M2(t)| находит решение, на втором этапе >1), то после включения одной из таких откладывает феромон, на третьем этапе вершин в множество C1(t)M1(t) вновь осуществляется испарение феромона. На образованное множество C1(t+1) должно первом этапе каждой итерации каждый k-й обладать хотя бы одной вакансией.

муравей формирует свое собственное Материалы XVI Международной конференции по нейрокибернетике Для каждой вершины осуществляется переход на следующую итерацию.

xjX2(t)=C2(t)M2(t), определяется набор ребер Ujk(t), связывающих xj с вершинами Заключение множества X1(t)=C1(t)M1(t), каждое из которых с соблюдением перечисленных Предлагается новая парадигма выше ограничений и условия комбинаторной оптимизации trees ant достаточности, может войти в состав colony optimization (T-ACO), основанная строящегося бинарного дерева. Для на идеях муравьиной колонии и в первую каждого ребра ui ( Ujk(t)) определяется очередь на идее непрямого обмена - параметр fik - суммарный уровень феромона стигмержи (stigniergy), позволяющая на этом ребре.

осуществлять синтез дерева. Такой подход Вероятность Pik включения ребра ui в является эффективным способом поиска формируемое дерево Dk(t) определяется рациональных решений для задач следующим соотношением оптимизации, допускающих графовую Pik=fik/ fik интерпретацию в виде деревьев.

i На втором этапе итерации, каждый Список литературы муравей откладывает феромон на рёбрах построенного маршрута.

1.M. Dorigo and T. Sttzle. Ant Colony Количество феромона k(l), Optimization. MIT Press, Cambridge, MA, 2004.

откладываемое муравьем zk на каждом 2.M. Dorigo, M. Birattari, T. Sttzle, Ant Colony ребре построенного дерева Dk, Optimization-- Artificial Ants as a Computational Intelligence Technique, IEEE Computational определяется следующим образом Intelligence Magazine, 2006.

k(l)= Q / Fk(l), 3. Курейчик В.М., Кажаров А.А., О некоторых где l-номер итерации, Qi– общее модификациях муравьиного алгоритма. //Известия количество феромона, откладываемое ЮФУ. Изд-во ТТИ ЮФУ, 2008, №4(81). С. 5-11.

муравьем на ребрах маршрута Dk, Fk(l)– 4.Курейчик В.М., Лебедев Б.К., Лебедев О.Б.

Разбиение на основе моделирования адаптивного целевая функция для решения, полученного поведения биологических систем.

муравьем zk на l-ой итерации. Чем меньше Нейрокомпьютеры: разработка, применение. 2010.

Fk(l), тем больше феромона откладывается №2. С. 28-34.

на ребрах построенного дерева и, 5.Лебедев О.Б. Покрытие методом муравьиной колонии /Двенадцатая национальная конференция следовательно, тем больше вероятность по искусственному интеллекту с международным выбора этих ребер при построении участием КИИ-2010. Труды конференции. Т. 2. М.:

деревьев на следующей итерации.

Физматлит, 2010. С. 423-431.

После того, как каждый агент сформировал 6.Лебедев Б.К., Лебедев О.Б. Построение решение и отложил феромон, на третьем кратчайших связывающих сетей на основе метода муравьиной колонии //Нечеткие системы и мягкие этапе происходит общее испарение вычисления: сб.ст. Третьей Всероссийской научной феромона на ребрах графа G в соответствии конференции: В 2т. Т.II / Волгоградский гос. техн.

с формулой Университет. – Волгоград, 2009. С. 42- fik = fik(1- ), 7.Лебедев О.Б. Трассировка в канале методом где –коэффициент обновления. После муравьиной колонии // Известия ЮФУ. Изд-во ТТИ выполнения всех действий на итерации ЮФУ, 2009, №4. С. 46-52.

находится агент с лучшим решением, которое запоминается. Далее 4-Й МЕЖДУНАРОДНЫЙ СИМПОЗИУМ «НЕЙРОИНФОРМАТИКА И НЕЙРОКОМПЬЮТЕРЫ» РЕШЕНИЕ КОМБИНАТОРНЫХ ЗАДАЧ НА ГРАФАХ НА ОСНОВЕ МЕТОДА ПЧЕЛИНОЙ КОЛОНИИ В.Б. Лебедев Технологический институт Южного федерального университета lbk@tsure.ru In work the modified paradigm of a beer colony for the алгоритмы [2], алгоритмы роевого decision of combinatory problems on graphs is интеллекта [7,8]. Одна из последних considered. On the basis of the analysis of behavioural разработок в области роевого интеллекта - model of self-organizing of a colony of bees, methods алгоритм пчел довольно успешно and mechanisms of formation of corresponding representations of decisions of considered combinatory используется для нахождения глобальных problems on graphs are developed. In comparison with экстремумов сложных многомерных existing algorithms improvement of results is reached.

функций [3,4,8].

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

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

В этой связи разрабатывают различные Паросочетанием графа G=(X,U) эвристики для построения алгоритмов с называет подмножество таких рёбер U*U, полиномиальной временной сложностью.

что любые два ребра uk,ul U* не имеют Существуют алгоритмы решения таких общих вершин, т.е. не смежны.

задач, основанные на использовании Паросочетание максимальной мощности потоков в сетях и имитационного определяется как паросочетание, моделирования [1], генетического поиска включающее максимальное число рёбер, [2] и других эвристиках, которые |U|*=max. [1] обеспечивают приемлемые результаты при Построим двойственный для графа G решении задач малой и средней сложности.

граф Gd=(U,V). Вершины графа Gd Часто эти процедуры используются в соответствуют рёбрам графа G. Пара итерационных структурах. Это предъявляет вершин (ui, uj) в графе Gd связаны ребром повышенные требования к качеству и vk в том и только в том случае, если в графе времени решения рассматриваемых задач.

G соответствующая пара рёбер (ui, uj) Побудительным мотивом исследований и смежны, т.е. инциденты одной вершине.

разработок новых эффективных алгоритмов Множество X0X вершин графа являются возникшие потребности в G=(X,U) называется внутренне решении задач большой и очень большой устойчивым, если любые две вершины xi размерности. Анализ литературы X0 и xjX0 не являются смежными.

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

[3,4]. К таким методам можно отнести, Таким образом, паросочетанию в графе прежде всего, метод эволюционного G соответствует внутренне – устойчивое моделирования [5,6], генетические подмножество двойственного графа Gd.

Материалы XVI Международной конференции по нейрокибернетике Максимальному по мощности функции в этой точке. Решение паросочетанию в графе G соответствует представляет комбинацию уникальных предельное внутренне – устойчивое компонент (вершин и ребер графа поиска подмножество (содержащее наибольшее решений), выбираемых, как правило, из число вершин) двойственного графа Gd. конечного набора конкурирующих между Раскраской графа называется такое собой компонент. Значения целевой приписывание цветов его вершинам, что функции F определяется комбинациями, никакие две смежные вершины не выбранными агентами. Целью является получают одинакового цвета. Если в графе поиск оптимальной комбинации G выделить s непересекающихся друг с компонент.

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

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 58 |



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

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