Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей
Рисунок 2.4 – Соединение входа с входом
Выход Out (m) контекстной диаграммы системы может быть присоединен к
выходу 
компонента 
, если тип Out (m) совпадает с типом 
.
Это условие можно записать в виде равенства 
(рис.
2.5).
Рисунок 2.5 – Соединение выхода с выходом
Выход 
компонента 
может быть присоединен к
входу 
компонента 
, если тип 
совпадает с типом
. Это условие можно
записать в виде равенства 
(рис.
2.6).
Рисунок 2.6 – Соединение выхода с входом
Пусть контекстная диаграмма системы имеет вход a и выход b (рис. 2.7).
Рисунок 2.7 – Пример контекстной диаграммы системы
Пусть в библиотеку компонентов входит компонент С1 с входом a и выходом c и компонент С2 с входом c и выходом b (рис. 2.8).
Рисунок 2.8 – Примеры контекстных диаграмм компонентов
Тогда вход a и выход b системы могут быть соединены с помощью компонентов С1 и С2 так, как показано на рис. 2.9.
Рисунок 2.9 – Примеры соединений компонентов
2.3 Элементарное перемещение муравья
2.3.1 Перемещение из входа контекстной диаграммы
Пусть изначально муравей
находится в конце входной стрелки In (n). Он может случайным образом выбрать
из библиотеки компонентов любой компонент 
,
у которого есть вход 
, который можно
присоединить к входу In (n). После присоединения входа 
компонента 
к входу In (n) контекстной диаграммы, муравей "переползает" по
входу 
на компонент 
и пытается присоединять "висящие"
входы компонента 
либо к еще
свободным входам контекстной диаграммы системы, либо к еще свободным выходам
других компонентов. Аналогично муравей пытается присоединять "висящие"
выходы компонента 
либо к еще
свободным выходам контекстной диаграммы системы, либо к еще свободным входам
других компонентов (рис. 2.10).
Рисунок 2.10 – Присоединение компонента к входу системы
Если после
вышеперечисленных действий муравья у компонента 
не
осталось "висящих" входов и выходов, то муравей "выползает"
из компонента 
по входу 
, через который он попал в
этот компонент. На этом перемещения муравья прекращаются.
Если же у компонента 
остались "висящие"
входы и выходы, то муравей случайным образом размещается на любом из них. Если
муравей оказался в конце "висящего" входа компонента 
, то далее он должен
действовать так, как описано ниже в пункте 2.3.3. Если муравей оказался в
начале "висящего" выхода компонента 
,
то далее он должен действовать так, как описано ниже в пункте 2.3.4.
2.3.2 Перемещение из выхода контекстной диаграммы
Пусть изначально муравей
находится в начале выходной стрелки Out (m). Он может случайным образом выбрать
из библиотеки компонентов любой компонент 
,
у которого есть выход 
, который можно
присоединить к выходу Out (m). После присоединения выхода 
компонента 
к выходу Out (m) контекстной диаграммы, муравей "переползает" по
выходу 
на компонент 
и пытается присоединять "висящие"
входы компонента 
либо к еще
свободным входам контекстной диаграммы системы, либо к еще свободным выходам
других компонентов. Аналогично муравей пытается присоединять "висящие"
выходы компонента 
либо к еще
свободным выходам контекстной диаграммы системы, либо к еще свободным входам
других компонентов (рис. 2.11).
Рисунок 2.11 – Присоединение компонента к выходу системы
Если после
вышеперечисленных действий муравья у компонента 
не
осталось "висящих" входов и выходов, то муравей "выползает"
из компонента 
по выходу 
, через который он попал в
этот компонент. На этом перемещения муравья прекращаются.
Если же у компонента 
остались "висящие"
входы и выходы, то муравей случайным образом размещается на любом из них. Если
муравей оказался в конце "висящего" входа компонента 
, то далее он должен
действовать так, как описано ниже в пункте 2.3.3. Если муравей оказался в
начале "висящего" выхода компонента 
,
то далее он должен действовать так, как описано ниже в пункте 2.3.4.
2.3.3 Перемещение из входа UFO-компонента
Пусть изначально муравей
находится в начале входной стрелки 
компонента
. Он может случайным
образом выбрать из библиотеки компонентов любой компонент 
, у которого есть выход 
, который можно
присоединить к входу 
. После
присоединения выхода 
компонента 
к входу 
компонента 
, муравей "переползает"
по выходу 
на компонент 
и пытается присоединять "висящие"
входы компонента 
либо к еще
свободным входам контекстной диаграммы системы, либо к еще свободным выходам
других компонентов. Аналогично муравей пытается присоединять "висящие"
выходы компонента 
либо к еще
свободным выходам контекстной диаграммы системы, либо к еще свободным входам
других компонентов (рис. 2.12).
Рисунок 2.12 –
Присоединение компонента 
к входу
компонента 
Если после
вышеперечисленных действий муравья у компонента 
не
осталось "висящих" входов и выходов, то муравей "переползает"
из компонента 
по выходу 
назад через вход 
в компонент 
. Если у компонента 
еще остались "висящие"
входы и выходы, то муравей случайным образом размещается на любом из них. Иначе
– покидает компонент 
по тому пути, по
которому он на него попал.
Если же у компонента 
остались "висящие"
входы и выходы, то муравей случайным образом размещается на любом из них.
2.3.4 Перемещение из выхода UFO-компонента
Пусть изначально муравей
находится в конце выходной стрелки 
компонента
. Он может случайным
образом выбрать из библиотеки компонентов любой компонент 
, у которого есть вход 
, который можно
присоединить к выходу 
. После
присоединения входа 
компонента 
к выходу 
компонента 
, муравей "переползает"
по входу 
на компонент 
и пытается присоединять "висящие"
входы компонента 
либо к еще
свободным входам контекстной диаграммы системы, либо к еще свободным выходам
других компонентов. Аналогично муравей пытается присоединять "висящие"
выходы компонента 
либо к еще
свободным выходам контекстной диаграммы системы, либо к еще свободным входам
других компонентов (рис. 2.13).
Рисунок 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).
