Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XLVI Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 07 июня 2018 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Трехсвояков Е.В., Фонова А.Э. РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОМПОНОВКИ БЛОКОВ ЭВА БИОИНСПИРИРОВАННЫМИ МЕТОДАМИ // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XLVI междунар. студ. науч.-практ. конф. № 11(46). URL: https://sibac.info/archive/meghdis/11(46).pdf (дата обращения: 26.02.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 38 голосов
Дипломы участников
У данной статьи нет
дипломов

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

Трехсвояков Евгений Викторович

студент, кафедра САПР ЮФУ,

РФ, г. Таганрог

Фонова Анна Эдуардовна

студент, кафедра САПР ЮФУ,

РФ, г. Таганрог

Щеглов Сергей Николаевич

научный руководитель,

кандидат технических наук, доцент кафедры систем автоматизированного проектирования ЮФУ,

РФ, г. Таганрог

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

 

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

 

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

Таблица 1.

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

Число вершин

Число подграфов

Результат МА

Результат ПА

50

5

165

167

100

10

820

835

500

5

19782

19502

2000

2

-

9983

2000

20

17001

19238

 

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

 

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

 

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

 

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

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

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.