Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей

Рисунок 2.13 – Присоединение компонента  к выходу компонента

Если после вышеперечисленных действий муравья у компонента  не осталось "висящих" входов и выходов, то муравей "переползает" из компонента  по входу  назад через выход  в компонент . Если у компонента  еще остались "висящие" входы и выходы, то муравей случайным образом размещается на любом из них. Иначе – покидает компонент  по тому пути, по которому он на него попал.

Если же у компонента  остались "висящие" входы и выходы, то муравей случайным образом размещается на любом из них.

2.3.5 Пример перемещений муравья

Пусть контекстная диаграмма системы имеет два входа (a и b) и два выхода (c и d), а муравей находится в конце входа b (рис. 2.14).

Рисунок 2.14 – Контекстная диаграмма с двумя входами и двумя выходами

Пусть в библиотеке компонентов находятся (рис. 2.15):

–  компонент С1 с входами b, e и выходом d;

–  компонент С2 с входом a и выходами e, f;

–  компонент С3 с входом f и выходом c.

Рисунок 2.15 – Пример библиотеки компонентов

Первое перемещение муравей делает следующим образом.

Вначале он выбирает из библиотеки компонент С1, у которого есть вход b, который можно присоединить к входу b контекстной диаграммы.

После присоединения входа b компонента С1 к входу b контекстной диаграммы, муравей "переползает" по входу b на компонент С1 и присоединяет "висящий" выход d компонента С1 к еще свободному выходу d контекстной диаграммы системы.

У компонента С1 остался "висящий" вход e, в начале которого и размещается муравей (рис. 2.16).

Рисунок 2.16 – Первый ход муравья

Второе перемещение муравей делает следующим образом.

Вначале он выбирает из библиотеки компонент С2, у которого есть выход e, который можно присоединить к входу e компонента С1.

После присоединения выхода e компонента С2 к входу e компонента С1, муравей "переползает" по входу e на компонент С2 и присоединяет "висящий" вход a компонента С2 к еще свободному входу a контекстной диаграммы системы.

У компонента С2 остался "висящий" выход f, в конце которого и размещается муравей (рис. 2.17).

Рисунок 2.17 – Второй ход муравья

Третье перемещение муравей делает следующим образом.

Вначале он выбирает из библиотеки компонент С3, у которого есть вход f, который можно присоединить к выходу f компонента С2. После присоединения входа f компонента С3 к выходу f компонента С2, муравей "переползает" по выходу f на компонент С3 и присоединяет "висящий" выход c компонента С3 к еще свободному выходу c контекстной диаграммы системы (рис. 2.18).

Рисунок 2.18 – Третий ход муравья

У компонента С3 не осталось "висящих" входов и выходов. Поэтому муравей "переползает" обратно по связи f на компонент С2. У компонента С2 тоже не осталось "висящих" входов и выходов. Поэтому муравей "переползает" обратно по связи e на компонент С1. У компонента С1 тоже не осталось "висящих" входов и выходов. Поэтому муравей "переползает" обратно по связи b на вход b контекстной диаграммы системы.

Муравей вернулся в начальное положение, поэтому его перемещения на этом прекращаются.

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

Наконец, из библиотеки компонентов муравью, вероятно, следует выбирать для присоединения тот компонент, у которого в результате окажется меньше "висящих" входов и выходов. Хотя такая локальная оптимальность вовсе не гарантирует того, что процесс построения системы из заданных компонентов закончится быстрее.

2.4 Перемещение нескольких муравьев

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

Рисунок 2.19 – Конфликт двух муравьев

2.4.1 Разрешение конфликтов

Можно предложить несколько способов разрешения конфликтов муравьев при доступе к одним ресурсам.

Например, можно назначить муравьям приоритеты – целые числа от 1 до V, где V – количество муравьев. Чем меньше число, тем выше приоритет. Таким образом, самый высокий приоритет имеет муравей, которому сопоставлено число 1, а самый низкий – муравей, которому сопоставлено число V. Если два муравья конфликтуют, то предпочтение отдается тому, у которого выше приоритет. Например, если у муравьев, изображенных выше на рис. 2.19, приоритеты назначены так, что муравей, находящийся на выходе c компонента C1, имеет приоритет 7, а муравей, находящийся на выходе c компонента C2, имеет приоритет 9, то их конфликт за выход c контекстной диаграммы системы разрешиться в пользу муравья, находящегося на выходе c компонента C1, который имеет более высокий приоритет по сравнению с муравьем, находящимся на выходе c компонента C2. Результат разрешения конфликта этих двух муравьев показан на рис. 2.20.

Рисунок 2.20 – Разрешение конфликта двух муравьев

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

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

2.4.2 Пример перемещений нескольких муравьев

Пусть контекстная диаграмма системы имеет два входа (a и b) и два выхода (c и d), а муравей 1 находится в конце входа b, и муравей 2 – в начале выхода c, рис. 2.21).

Рисунок 2.21 – Размещение муравьев на контекстной диаграмме

Пусть в библиотеке компонентов находятся (рис. 2.22):

–  компонент С1 с входами b, e и выходом g;

–  компонент С2 с входом a и выходами e, f;

–  компонент С3 с входами f, h и выходом c;

–  компонент С4 с входом g и выходами h, d.

Рисунок 2.22 – Библиотека из четырех компонентов

Первое перемещение муравей 1 делает следующим образом.

Вначале он выбирает из библиотеки компонент С1, у которого есть вход b, который можно присоединить к входу b контекстной диаграммы.

После присоединения входа b компонента С1 к входу b контекстной диаграммы, муравей "переползает" по входу b на компонент С1. У компонента С1 остался "висящий" вход e и "висящий" выход g, в конце которого и размещается муравей 1 (рис. 2.23).

Рисунок 2.23 – Первый ход муравья 1

Первое перемещение муравей 2 делает следующим образом. Вначале он выбирает из библиотеки компонент С3, у которого есть выход c, который можно присоединить к выходу c контекстной диаграммы. После присоединения выхода c компонента С3 к выходу c контекстной диаграммы, муравей "переползает" по выходу c на компонент С3. У компонента С3 остались "висящие" входы h и f, в начале которого и размещается муравей 2 (рис. 2.24).

Рисунок 2.24 – Первый ход муравья 2

Второе перемещение муравей 1 делает следующим образом.

Вначале он выбирает из библиотеки компонент С4, у которого есть вход g, который можно присоединить к выходу g компонента С1.

После присоединения входа g компонента С4 к выходу g компонента С1, муравей "переползает" по входу g на компонент С4, выход h которого он соединяет с входом h компонента С3, а выход d – c выходом d контекстной диаграммы системы (рис. 2.25).

Рисунок 2.25 – Второй ход муравья 1

Второе перемещение муравей 2 делает следующим образом. Вначале он выбирает из библиотеки компонент С2, у которого есть выход f, который можно присоединить к входу f компонента С3. После присоединения выхода f компонента С2 к входу f компонента С3, муравей "переползает" по входу f на компонент С2, выход e которого он соединяет с входом e компонента С1, а вход a – c входом a контекстной диаграммы системы (рис. 2.26).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9