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

О.Б. Лебедев; Б.К.  Лебедев; А.Е.  Лебединский

О.Б. Лебедев Южный федеральный университет
Б.К. Лебедев Южный Федеральный Университет
А.Е. Лебединский Южный Федеральный Университет

Ключевые слова: СБИС, размещение стандартных ячеек, одномерная упаковка, генетический поиск, рой частиц, аффинное пространство поиска, гибридизация, оптимизация

Аннотация

Предлагается гибридный алгоритм размещения базовых стандартных библиотечных элементов при проектировании топологии полузаказной СБИС методом одномерной упаковки, основанный на интеграции роевого и генетического алгоритмов. В работе в качестве интерпретации решения – структуры данных, несущей информацию об упаковке (размещении), используется последовательность элементов (приоритетный список), задающая порядок их упаковки. В качестве декодера используется стандартная процедура упаковки (СПУ). Интерпретацией решения задачи размещения, формируемого роевым и генетическим алгоритмами, является упорядоченный список, включающий все ячейки, с разбиением его на части. Каждая часть включает вершины, соответствующие элементам, помещаемым в линейку (блок). Число частей служит оценкой решения. Интерпретацией решения, формируемого алгоритмами, является хромосома, структура которой идентична структуре списка. Разбиение списка на части производится в результате декодирования. Описываются поисковые процедуры в пространстве решений, механизмы поведения модернизированного роя частиц и генетического поиска. В отличие от канонической парадигмы роевого алгоритма предлагается подход к построению модифицированной парадигмы роя частиц, обеспечивающей возможность одновременного использования хромосом с дискретными целочисленными значениями параметров в генетическом алгоритме и в алгоритме на основе роя частиц. В качестве аналога скорости при перемещении выступает оператор направленной мутации (ОНМ), суть которого заключается в изменения целочисленных значений генов в хромосоме. В отличие от канонической парадигмы роевого алгоритма предлагается подход к построению модифицированной парадигмы роя частиц, обеспечивающей возможность одновременного использования хромосом с дискретными целочисленными значениями параметров в генетическом алгоритме и в алгоритме на основе роя частиц. В качестве аналога скорости при перемещении частиц выступает оператор направленной мутации (ОНМ), суть которого заключается в изменения целочисленных значений генов в хромосоме. Это позволило снизить комбинаторную сложность задачи. Это позволило снизить комбинаторную сложность задачи. Для проведения экспериментов были использованы известные тестовые задачи, представленные в библиотеке OR-объектов – (OR-Library Beasley). Временная сложность алгоритма, полученная экспериментальным путем, совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет О(n²)-О(n³). Разработанный алгоритм позволил получить оптимальные решения для всех задач набора.

Литература

1. Месягутов М.А., Мухачева Э.А., Белов Г.Н., Шайтхауэр Г. Упаковка одномерных контейнеров с продолженным выбором идентичных предметов: точный метод поиска оптимального решения. – М.: Наука. Автоматика и телемеханика, – № 1, – 2011. – С. 154-173.
2. Потарусов Р.В., Курейчик В.М. Проблема одномерной упаковки элементов // Известия ТРТУ. Изд-во ТРТУ, – №8, – 2006. – C. 88 – 93.
3. Ross P., Marin-Blazquez J.G., Schulenburg, S., and Hart E. Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heurstics // Proceeding of the Genetic and Evolutionary Computation Conference, GECCO 2003, Chicargo, Illinois, USA, – 2003. – рр. 1295-1306.
4. Gupta J.N. and Ho J.C. A New Heuristic Algorithm for the One-dimensional Bin-packing Problem, Production Planning & Control, – №10, – 1999. – рр. 598-603.
5. Levine J. and Ducatelle F. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, – 2003. – рр. 389-401.
6. Fleszar, K. and Hindi, K.S. New Heuristics for One-dimensional Bin-packing, Computers & Operations Research. – № 29, – 2002. – рр. 821-839.
7. Alvim Adriana C.F., Glover Fred S., Ribeiro Celso C. and Aloise Dario J. Local search for the bin packing problem // Journal of Heuristics. – № 10, – 2004. – рр. 205–229.
8. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. – М.: Физматлит, – 2006. – 288 с.
9. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, – 2005. – 235 р.
10. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: Учебное пособие – М: Издательство МГТУ им. Н.Э. Баумана, –2014. – 448 с.
11. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи размещения на основе эволюционного моделирования. // Известия РАН. Теория и системы управления. – №4, – 2007. – С. 78-90.
12. M. Clerc. Particle Swarm Optimization. ISTE, London, UK, – 2006. – 248 р.
13. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. - Таганрог: Изд-во ЮФУ, 2013. – 199 с.
14. Lebedev B.K., Lebedev O.B., Lebedeva E.O. One-Dimensional swarm algorithm packaging // International Conference Information Technologies in Business and Industry 2018. Journal of Physics: Conference Series, Volume 1015, Enterprise Information systems. 2018.
15. Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Гибридизация роевого интеллекта и генетической эволюции на примере размещения. ЭЛЕКТРОННЫЙ НАУЧНЫЙ ЖУРНАЛ: ПРОГРАММНЫЕ ПРОДУКТЫ, СИСТЕМЫ И АЛГОРИТМЫ. DOI: 10.15827/2311-6749.25.280. http://swsys-web.ru/hybridization-of-swarm-intelligence-and-genetic-evolution.html.
16. Valerio de Carvalho J.M. Exact Solution of Bin-packing Problems Using Column Generation and Branch-and-bound //Annals of Operations Research. – № 86, – 1999. – рр. 629-659.