Статья

Название статьи РАСПРЕДЕЛЕНИЕ КОМПЛЕКСА ПРОГРАММ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ МЕТОДА КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Автор Б.К. Лебедев, В.Б. Лебедев
Рубрика РАЗДЕЛ VI. ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ НОВОГО ПОКОЛЕНИЯ И НЕЙРОКОМПЬЮТЕРЫ
Месяц, год 06, 2015
Индекс УДК 621.3.049.771.14
DOI
Аннотация Рассматривается однородная распределительная задача. Приведена постановка задачи. Рассмотрены достоинства и недостатки основных групп алгоритмов – точных и приближенных. На основе анализа разработанных алгоритмов (последовательных, итерационных, селективно-перестановочных и т.д.) сделан вывод о необходимости создания эффективного алгоритма, отвечающего современным требованиям на базе новых технологий и подходов. В работе на основе графического представления решения ОРЗ в виде двудольного графа предлагается новая парадигма комбинаторной оптимизации, базирующаяся на методе кристаллизации россыпи льтернатив. В методе кристаллизации россыпи альтернатив (Crystallization of alternatives field (CAF)) каждое решение формируется (представляется) множеством агентов. Каждому агенту соответствует множество альтернативных состояний. Каждый агент может находиться в одном из альтернативных состояний. Решение определяется совокупностью альтернативных состояний множества агентов. Предложены новые механизмы решения задач ОРЗ. Такие методы являются итеративными, эвристическими методами случайного поиска. Разработка новых алгоритмов проводилась на основе использования метаэвристик, заложенных в природных механизмах принятия решений. Наряду с метаэвристиками, на которых построены роевые алгоритмы, используется метаэвристика, с тенденцией к использованию альтернатив (вариантов компонентов) из наилучших найденных решений. В процессе эволюционной коллективной адаптации методами дискриминантного анализа формируются оценки приспособленности альтернатив. Приспособленность альтернатив рассматривается как вероятность ее использования в формируемом решении. Совокупность данных об альтернативах и их оценках составляет россыпь альтернатив. В процессе эволюционной коллективной адаптации производится вычленение из множества вариантов наиболее приспособленных альтернатив. Экспериментальные исследования проводились на ЭВМ типа IBM PC/AT. Временная сложность алгоритма имеет оценку О(n2), где n – число вершин двудольного графа. Для проведения объективных экспериментов были использованы тестовые задачи, представленные в литературе и Интернет. По сравнению с существующими алгоритмами достигнуто улучшение результатов от 2 до 6%.

Скачать в PDF

Ключевые слова Однородная распределительная задача; двудольный граф; оптимизация; роевой интеллект; адаптивное поведение; метод кристаллизации россыпи альтернатив.
Библиографический список 1. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. – М.: МГУ им. М.В. Ломоносова, 2011. – 222 c.
2. Ларионов А.М., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. – СПб.: Энергоатомиздат, 1987. – 256 с.
3. Романовский И.В. Алгоритмы решения экстремальных задач. – М.: Наука, 1977. – 352 c.
4. Нейдорф Р.А., Жикулин А.А. Быстродействующая модификация алгоритма оптимизации решения // Труды конгресса по интеллектуальным системам и информационным технологиям «AIS-IT’14». Научное издание в 4-х томах. Т. 1. – М.: Физматлит, 2010. – C. 15-22.
5. Кобак В.Г., Будиловский Д.М. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов // Вестник ДГТУ. – 2006. – № 4. – С. 327-334.
6. Нейдорф Р.А., Филиппов А.В., Ягубов З.Х. Перестановочный алгоритм биэкстремального решения однородной распределительной задачи // Вестник ДГТУ. – 2011. – Т. 11, № 5 (56).
7. Нейдорф Р.А., Жикулин А.А. Исследование вариантов модификации приближенных алгоритмов решения однородных распределительных задач, повышающих их эффективность // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Труды X Междунар. науч.-техн. форума. – Ростов-на-Дону: ИЦ ДГТУ, 2012. – С. 370-375.
8. Нейдорф Р.А., Жикулин А.А. Селективно-перестановочный метод приближенного решения однородной распределительной задачи. Комбинационные перестановки // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 167-172.
9. Плотников В.Н., Зверев В.Ю. Методы быстрого распределения алгоритмов в вычислительных системах // Техническая кибернетика. – 1974. – № 3.
10. Будиловский Д.М. Генетический подход к решению минимаксной задачи в однородных системах обработки информации // Математические методы в технике и технологиях. – 2006. – Т. 2, № 19.
11. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
12. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования: Монография. – Таганрог: Изд-во ЮФУ, 2013.
13. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 41-47.
14. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-35.
15. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адаптивного поведения биологических систем // Нейрокомпьютеры: разработка, применение. – 2010. – № 2. – С. 28-34.
16. Raidl G.R. A Unified View on Hybrid Metaheuristics. In: Lecture Notes in Computer Science. Springer-Verlag. – 2006. – P. 1-12.
17. Лебедев Б.К., Лебедев В.Б. Оптимизация методом кристаллизации россыпи альтернатив // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 11-17.
18. Лебедев Б.К., Лебедев В.Б. Метод кристаллизации россыпи альтернатив // Сборник научных трудов VII Международной научно-практической конференции “Интегрированные модели и мягкие вычисления в искусственном интеллекте”. Т. 2. – М.: Физматлит, 2013. – C. 903-912.
19. Лебедев Б.К., Лебедев В.Б. Глобальная трассировка методом кристаллизации россыпи альтернатив // Известия ЮФУ. Технические науки. – 2014. – № 7 (156). – С. 42-51.
20. Лебедев Б.К., Лебедев В.Б. Построение кратчайших связывающих соединений методом кристаллизации россыпи альтернатив // МЭС-2014. VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем – 2014». Сборник трудов / Под общ. pед. Академика РАН А.Л. Стемпковского. – М.: ИППМ РАН, 2014. Ч. I. – С. 177-183.

Comments are closed.