РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОМПОНОВКИ БЛОКОВ ЭВА БИОИНСПИРИРОВАННЫМИ МЕТОДАМИ

Для построения формальной математической модели задач компоновки применяют теорию графов. Схема представляет собой граф, в котором каждый блок соответствует вершине графа, а связи схемы – его рёбрам [1].

Поэтому задача компоновки определяется далее: Дан граф . Задача компоновки представляет собой задачу разбиения или "разрезания" данного графа на блоки   так, чтобы количество рёбер, которые соединяют эти блоки, было минимальным, т.е. нужно минимизировать величину , где - множество ребер, которые соединяют блоки   и  .

Совокупность частей  по формуле (1) является разбиением графа :

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

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

Оптимизация целевой функции: .

Алгоритм колонии пчел в первый раз предложен турецким ученым в 2005 г. Суть данного алгоритма - поведение пчел в живой природе.

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

Источник нектара оценивается значимостью, которая определяется разными параметрами.

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

Работа алгоритма колонии пчел зависит от последующих параметров:

• Общее количество участков.
• Количество элитных участков.
• Количество пчел-исследователей.
• Количество пчел-разведчиков.
• Количество пчел на других участках.
• Начальный размер пространства для поиска – размер участков с их окрестностями.
• Размер окрестности.
• Максимальное количество итераций.

Основой алгоритма колонии пчел является то, что каждая пчела на каждом шаге будет определять как элитные участки для исследования, так и участки в окрестности элитных. Это даст возможность разнообразить популяцию решений на следующих итерациях, повысить вероятность нахождения близких к оптимальным решениям. Биоинспирированный алгоритм [3] решения задачи компоновки представлен на рисунке 1:

Рисунок 1 .  Биоинспирированный алгоритм решения задачи компоновки

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

Рисунок 2 .  Программная реализация

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

Таблица 1.

Экспериментальные данные

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

Рисунок 3.  Графики зависимости целевых функций от времени для МА и ПА

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

Список литературы:

1. Курейчик В.В., Запорожец Д.Ю. Роевый алгоритм в задачах оптимизации. - Таганрог: Изд-во ТРТУ, 2010. – С. 28-32.
2. Курейчик В.М., Кажаров А.А. Использование пчелиных алгоритмов для решения комбинаторных задач. -Таганрог: Изд-во ТРТУ, 2010. – С.583-589.
3. Курейчик В.В., Курейчик В.М., Сорокалетов П.В. Биоинспирированные методы в оптимизации. – М.: Физматлит, 2009. – 380 с. 41.