автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование генетических алгоритмов компоновки по критериям числа внешних связей и задержки распространения сигналов

Введение.,.'.'

1. Методы решения задачи компоновки.

1.1. Выбор критериев задачи компоновки.

1.2. Анализ алгоритмов и методов поиска решений.

1.3. Учет критериев.

Технические задачи, решаемые на современном этапе развития электронной и вычислительной техники, характеризуются высокими требованиями и множественностью входящих в них параметров. На данном Этапе представляется довольно сложным реализация того или иного метода, охватывающего все необходимые условия проектирования, т.к. в связи с огромным количеством элементов и критериев в решаемой задаче многие алгоритмы не справляются с решением или требуют много процессорного времени для решения, даже в условиях современного развития информационных технологий. В связи с этим появилась необходимость в поиске новых методов и направлений для решения данного класса задач, что привело к появлению множества алгоритмов, разработанных на разных этапах конструкторского ^проектирования. Особые трудности вызвала разработка алгоритмов для решения так называемых ЫР-полных задач, в которых нахождение оптимального значения возможно только полным перебором. К таким относится большинство графовых задач, не имеющих непрерывной целевой функции (компоновка, размещение, покрытие, типизация, разрезание и т.п.). В этих задачах речь идет прежде всего о нахождении достаточного ' минимума (максимума), а не оптимума. Наиболее используемыми на практике для их решения явились алгоритмы, имеющие малую вычислительную сложность (ВСА) порядка О(ап), и

V О высокостабильные алгоритмы, имеющие ВСА до 0(Ьп ) и при этом дающие близкие к оптимальному решению результаты. Первые базируются на применении итерационных методов и используются в графовых задачах малого размера (число вершин п<30), вторые же комбинируют в себе итерационные методы и какие-либо другие (в основном статистические или генетические) методы и работают с графами большого размера. Примером таких алгоритмов может послужить алгоритм Kernighan-Lin (ВСА = 0(ап )), который дает хорошие результаты для задачи графового разбиения, но в то же время для больших (более 300 вершин) графов требует на порядок больше времени, чем разработанные позднее эвристические алгоритмы [8], работающие не с одним , а сразу с несколькими решениями и дающими г положительный результат" в более короткое время. Такие методы, основанные на биологической эволюции, становятся сейчас популярными в мировой практике, т.к. позволяют работать в любых областях задач проектирования, начиная с компоновки и заканчивая трассировкой соединений, в том числе и в тех случаях, когда стандартные методики поиска оказываются безрезультатными и неэффективными.

Актуальность работы. В последнее время в связи с быстрым развитием технологий изготовления электронных схем, в том числе БИС и . • . v

СБИС, повышением степени интеграции и более жесткими требованиями к их быстродействию, возникает необходимость в пересмотре разработанных ранее й существующих на сегодняшний день алгоритмов и методов проектирования. Основная трудность на данном этапе выявляется в таком увеличении количества переменных и параметров проектирования, что существующие алгоритмы оказываются малоэффективными как с точки зрения точности и оптимальности получаемого решения, так и с позиции времени их работы. Указанные трудности особенно отражаются в работе алгоритмов компоновки, трассировки и размещения, где при увеличении количества элементов значительно возрастает вычислительная сложность алгоритма (ВСА). Кроме того, результатом уменьшения размеров компонентов БИС и СБИС и повышения их быстродействия явилась необходимость учета в задачах компоновки и размещения множества критериев, таких, как электромагнитотепловая (ЭМТ) совместимость, элементарная и суммарная задержка сигналов, суммарное число внешних связей и т.д. Все это приводит к необходимости поиска таких методов решения этих задач, которые позволяли бы при незначительных затратах машинного времени получать достаточно точные и приемлемые в современных условиях решения, удовлетворяющие всему множеству V поставленных ограничений по всем критериям задачи. К таким можно отнести методы эволюционного моделирования, которые были разработаны в начале 70-х, но только сейчас приобрели приоритет в отношении других методов, как способные обрабатывать множество решений при учете множества критериев. Такими свойствами обладают генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Основная цель ГА - абстрактно и формально объяснить адацтацию процессов в естественных системах и спроектировать искусственные программные системы, которые содержат основные механизмы естественных систем. Основная тема поиска ГА -поиск балланса между эффективностью и качеством для "выживания" в различных условиях.

На практике более 60 процентов от общих временных потерь приходится на задержки в межсоединениях. Эти задержки вызваны тем, что удельный размер межсоединений значительно превышает размеры самих элементов, которые постоянно миниатюризируются ввиду развития технологии проектирования. Увеличение же длины межсоединений опережает рост размеров области для размещения элементов, что приводят к понижению быстродействия схемы вцелом. Кроме того, из-за постоянного повышения требований к проектируемым изделиям в отношении выполняемых функций увеличивается размерность задач проектирования. Указанные трудности указывают на необходимость развития новых методик поиска с учетом:

- топологических характеристик проектируемых изделий на этапе размещения элементов;

- характеристик длины соединений и топологии прокладки на этапе трассировки; ' ;

- характеристик общей длины межсоединений и задержек сигналов на этапе компоновки блоков;

- характеристик ЭМТ совместимости на этапе компоновки БИС и СБИС.

В связи с этим становится актуальным вопрос о разработке нового алгоритма компоновки, использующего методы генетического поиска (МГП) в комбинации с другими итерационными методами, что позволит уменьшить время поиска решений в задачах большой размерности, и в то же время повысить качество этих решений за счет использования итерационных методов поиска оптимума.

Цель и задачи работы. Целью данной диссертационной работы является исследование новых методов и алгоритмов компоновки, использующих в своей основе принципы генетического программирования и эволюционного моделирования. Основная задача состоит в компоновке электронной схемы с учетом суммарного числа внешних связей и элементарных задержек в распространении сигналов, а также в оценке качества применяемых генетических алгоритмов и получаемых в результате V их работы решений.

Научная новизна. В результате исследования нескольких различных алгоритмов разрезания графов, на базе ПГА (простого генетического алгоритма) была разработана новая структурная схема генетического алгоритма компоновки, при этом:

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

2. Разработана модернизированная структура генетических операторов, позволяющая оптимизировать процесс генетического поиска при поставленных условиях задачи.

3. Описана новая эвристика улучшения решений, основанная на комбинации итерационного „и статистического методов.

Методы исследования. Примененные методы исследования базируются на использований теории графов, теории множеств и теории алгоритмов и включают в себя элементы эволюционного моделирования и исследования ГА. Приведенные в работе положения подтверждаются V экспериментальными результатами. Изучение и сравнение характеристик ГА производится на базе. существующих систем генетического поиска, линейного и нелинейного программирования. Практический анализ осуществлен при помощи имеющихся вычислительных средств и реализован на IBM-совместимых компьютерах в среде Windows 95.

Практическая ценность. Разработанный в результате анализа существующих методов поиска решений алгоритм компоновки позволяет использовать новые возможности в процессе проектирования:

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

2; Методика поиска позволяет учитывать как математическую, так и статистическую закономерность при распределении элементов, что позволяет улучшить практические результаты по сходимости алгоритма.

3. Разработанная структурная схема алгоритма и методика решения использует методы генетического поиска, что позволяет решать NP-полную задачу компоновки сокращенным перебором, используя знания о решаемой задаче. •

4. Программное обеспечение разработано под наиболее популярную систему Windows фирмы Microsoft Corporation, и создано на языке программирования Borland С++.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе "Разработка интеллектуальных систем проектирования на основе эволюционной адаптации" (№ ГР 01.9.60004346), а также научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований "Генетические алгоритмы в интеллектуальных САПР".

Материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при проведении практических занятий и в цикле лабораторных работ по курсу "Методы оптимизации" и "Методы генетического поиска".

Апробация. Апробация научных и практических результатов работы проводилась на научных семинарах (1997-1999, ТРТУ), Всероссийских научно-технических конференциях студентов и аспирантов (в г. Таганроге за период с 1996 по 1999г.), Международной научно-технической конференции "Интеллектуальные САПР" в 1999 г.

Публикации. По теме диссертации опубликовано 7 печатных работ.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, списка литературы и приложений. Работа содержит 140 страниц, включая 38 рисунков, 14 таблиц, список литературы из 102 наименований, 5 страниц приложений.

Результаты работы ПО partingGO по тестированию ГО на указанных примерах сведены в таблице В. В таблицах 9 и 10 показаны результаты по работе ПО partingEV и partingAB (соответственно по эвристикам улучшения и блоку адаптации).

Используемые в таблицах сокращения представляют собой следующие характеристики : t(CPU) - время работы алгоритма на процессоре (CPU) в секундах.

1. Курейчик В. М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990.

2. Вычислительные системы. Сборник трудов, выпуск 54, Новосибирск, 1973.

3. Под редакцией Морозова К. К. Методы разбиения схем РЭА на конструктивно законченные части. Москва, Советское радио, 1978.

4. Букатова И. Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981.. v , '

5. Савельев А. Я. , Овчинников В. А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.

6. Корячко В. П., Курейчик В. М., Норенков И. П. Теоретические основы САПР. Москва, Энергоатомиздат, 1987.

7. V. М. Kureichik, Е. D. Goodman, W. F. Punch. An approach to partitioning based on simulated evolution. Известия ТРТУ, выпуск 3, Таганрог, 1996.

8. Youssef G. Saab, Vasant B. Rao. "Fast Effective Heuristics for the Graph Bisectioning Problem" , IEEE, vol.9 N1, January 1990, Transaction on computer-aided design. •

9. Батищев Д.И. Генетические Алгоритмы решения экстремальных задач. Нижний Новгород, Нижегородский государственный университет имени Н.И.Лобачевского, 1995.

10. Y.C.Wei, C.K.Cherig. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.f28

11. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Desighn Automation Conference, paper 25/1, pp.421-425., 1991.

12. B.Kernighan, S.Lin. "An efficient heuristic procedure for partitioning graphs" , Bell Syst. Tech.J., vol 49, pp. 291-307, Feb, 1970.

13. C.Fiduccia, R.Mattheyses. "A linear time heuristics for improving network partitions", in 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

14. C.J.Alpert, A.B.Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th АСМЯЕЕЕ Design automation conference, 1993, pp. 743-748.

15. D.Schweikert, B.Kernighan, "A proper model for partitioning of electrical circuits", in 19th Desighn automation workshop, 1972, pp. 57-62.

16. Emanuel Falkenauer, "Setting New Limits in Bin Packing with a Grouping GA Using Reduction", Tech.report ROl 08, March 1994.

17. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided desighn of integrated circuits and systems, vol.17, No,3, March 1998, pp. 193-204.V

18. Под редакцией Норенкова И. П. Системы автоматизированного проектирования в радиоэлектронике. Справочник. Москва, Радио и связь, 1986.

19. Курейчик В. М. Генетические алгоритмы. Монография. Таганрог, ТРТУ, 1998.

20. Автоматизация проектирования электронной аппаратуры. Междуведомственный тематический научный сборник, выпуск 3. Таганрог, ТРТИ им. В. Д. Калмыкова, 1984.

21. Рябец Н. Н., Рябец М. Н. Исследование алгоритма упорядочения каналов трассировки СБЙС, Известия ТРТУ №3, 1997. Материалы Всероссийской конференций "Интеллектуальные САПР-96", стр.195.

22. Рябец М. Н. Оптимальное планирование кристалла СБИС при решении задачи размещения. Всероссийская научная конференция студентов и аспирантов. Тезисы докладов. Радиоэлектроника, микроэлектроника, системы связи и управления. 1997. стр.90.

23. Рябец М. Н. Генетический алгоритм компоновки на основе обобщенного критерия. Известия ТРТУ №2, 1998. Материалы Всероссийской конференции "Интеллектуальные САПР-97", стр.49.V

24. Норенков И. П., Маничев В. Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. Москва, Высшая Школа, 1983.

25. Рябец М. Н. Последовательный генетический алгоритм компоновки. IV Всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления", 8-9 октября 1998 г., стр.80.

26. Рябец М. Н. Применение генетических алгоритмов в задаче К-кусочного разбиения. Известия ТРТУ №3, 1999. Материалы международной научно-технической конференции "Интеллектуальные САПР", стр.116.

27. Смирнов Н. В., Дунин-барковский И. В. Курс теории вероятностей и математической статистики. Москва, Наука, Главная редакция физико-математической литературы, 1969.

28. Ашманов С. А. Линейное программирование. Москва, Наука, Главная редакция физико-математической литературы, 1981.

29. Куник Е. Г., Храмцов В. Н. Решение оптимизационных задач на графовых структурах в системах автоматизации проектирования.

30. Междуведомственный тематический научный сборник "Автоматизация проектирования электронной аппаратуры", Выпуск 6. Таганрог, 1989.

31. Мелихов А. Н., Берштейн Л. С. Конечные четкие и расплывчатые множества. Таганрог, ТРТИ, 1980.

32. Морозов К. К., Одиноков В. Г., Курейчик В. М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. Москва, Радио и связь, 1983.

33. Курейчик В. М. Оптимизация в САПР: Учебное пособие.Таганрог, ТРТУ, 1998.

34. J. Holland. Adaptation in Natural and Artifical Systems. Ann Arbor, MI: Univ. of Michigan Press, ;1975.

35. Курейчик В. M. Генетические алгоритмы: состояние, проблемы, перспективы. "Системы управления РАН", Москва, №5, 1998.

36. Курейчик В. М. Генетические алгоритмы. Известия ТРТУ, №2, Таганрог, 1998,

37. Курейчик В. В/Перспективные архитектуры генетического поиска. Известия ТРТУ, №2, Таганрог, 1998.

38. Курейчик В. В. Эволюционные вычисления в САПР. Известия ТРТУ, №2, Таганрог, 1998. '

39. Мухлаева И. В., Мухлаев А. В. Повышение направленности генетического поиска с применением знаний о задаче. Известия ТРТУ, №2, Таганрог, 1998.

40. Щеглов С. Н., Кулинский В. А. Разработка и исследование операторов генетического поиска для задачи разнесения соединения по слоям. I Всероссийская конференция молодых ученых и аспирантов, Таганрог, Изд-во ТРТУ, 1998.

41. Рябец М. Н. Использование аддитивного критерия в генетических алгоритмах. I Всероссийская конференция молодых ученых и аспирантов, Таганрог, Изд-во ТРТУ, 1998.

42. Курейчик В. М. Генетические алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3, 1998.

43. Курейчик В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы. Известия Академии наук. Теория и системы управления, №1, 1999.

44. Курейчик В. М., Курейчик В. В. Генетический алгоритмVразбиения графа. Известия Академии Наук. Теория и системы управления, №4, 1999.

45. Лебедев В. Б. Планирование СБИС методом генетического поиска. "Известия ТРТУ", №3,1999;

46. Курейчик В. М., Курейчик В. В. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта. "Известия ТРТУ", №3, 1999.f32

47. Мухлаева И. В. Кроссинговер для решения задачи двумерной упаковки и размещения прямоугольных элементов на плоскости. "Известия ТРТУ", №3, 1999.

48. Лисяк В. В., Лисяк Н. К. Стохастические методы размещения и компоновки БИС в параллельных ЭВМ с перестраиваемой архитектурой. "Известия ТРТУ", №3, 1999.

49. Матузков О. В. Решение задачи коммивояжера с использованием генетического алгоритма. "Известия ТРТУ", №3, 1999.

50. Гладков Л. А., .Гулевич А. И. Программа оболочка для исследования графовых задач. "Известия ТРТУ", №3, 1999.

51. Лебедев Б. К. Разбиение на основе коллективной адаптации. "Известия ТРТУ", №3, 1999.53; V.V.Miagkikh, A.P.Topchy, S.A.Chertkov. Genetic algorithms: some new features for premature convergence avoidance. Известия ТРТУ, выпуск 3, Таганрог, 1996.

52. Файзуллин А. 3. Определение функции пригодности индивида популяции в генетическом алгоритме упаковки. Всероссийская научная конференция студентов и аспирантов, 26-27 октября, Таганрог, 1995.

53. Мягких В. В., Савельев О. В. Метод "социальных катастроф" для избежания преждевременной сходимости в генетических алгоритмах. Всероссийская научная конференция студентов и аспирантов, 26-27 октября, Таганрог, 1995.

54. Kelly D. Crawford. Solving the n-Queens problem using genetic algorithms. ACM (Association of Computing Machinery), 0-89791-502-X/92/0002/1039, 1992, pp.1039-1045

55. Кодачигов В. И., Карелин В. П., Пашкевич А. П., Курейчик В. М. О разрезании произвольного конечного графа на подграфы. в кн.:

56. Цифровые модели и интегрирующие структуры. Под.ред. А. В. Каляева. Таганрог, Радиотехнический институт, 1970.

57. Горинштейн Л. Л. О разрезании графа. Известия АН СССР, Техническая кибернетика, 1969, №1.

58. Мелихов А. Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. "Наука", Главная редакция физико-математической литературы, 1974.

59. Naveed Sherwani (Intel Corporation). Algorithms for VLSI Physical Design Automation. Second edition, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

60. Y. Saab. "A new effective and efficient multi-level partitioning algorithm", in Design, Automation and Test in Europe Conference 2000. Paris, France, 27-30 March 2000, pp.112-116.

61. C. Alpert. The ISPD98 circuit benchmarks suite. Physical Design Workshop, 1998, pp.80-85. .

62. Y. Gao, D. Wong. ."Wire-sizing for delay minimization and rinding control using transmission line model", in Design, Automation and Test in Europe Conference 2000. Paris, France, 27-30 March 2000, pp.512-516.

63. N. Fröhlich, V. Glockel, J. Fleischmann. "A new partitioning method for parallel simulation of VLSI circuits on transistor level", in Design, Automation and Test in Europe Conference 2000. Paris, France, 27-30 March 2000, pp.679-685.

64. H. M. Djidjev. On the problem of partitioning planar graphs. SIAM Journal on Algebraic and Discrete Methods. 3(2): 229-240, 1982.

65. S. Even. Graph algorithms. Computer Science Press, 1979.

66. Берштейн Л. С. Применение ориентированных гиперграфов дляVкомпоновки комбинированных схем в ячейки. Межвузовский тематическийнаучно-технический сборник "Методы построения алгоритмических моделей сложных систем", вып.5. Таганрог, ТРТИ, 1980.

67. М. К. Goldberg, М. Burstein. Heuristic improvement technique for bisection of VLSI networks. Proceedings of IEEE International Conference on Computer Design, pp. 122-125, 1983.

68. R. B. Hitchcock. Partitioning of logic graphs: A theoretical analysis of pin reduction. Proceedings of Design Automation Conference, pp.54-63, 1970.

69. B. Krishnamurthy. An improved mincut algorithm for partitioning vlsi networks. IEEE Transactions on Computers, pp.438-446, 1984.

70. Y. Wei, C. Cheng. Towards efficient hierarchical designs by ratiocut partitioning. Proceedings if IEEE International Conference on Computer-Aided Design, pp.298-301, 1989.

71. Бьярн Страу струп. Язык программирования С++. Киев, "ДиаСофт", 1993.

72. Чарльз Калверт. Программирование в Windows. Под. ред. Д. Зарецкого. Москва, Бином, 1995.

73. Pentium Processor with ММХ™ Technology Performance Brief. Intel, Order Number: 243286-001, January 1997.

74. Мухлаев А. В. Адаптация в САПР. Междуведомственный тематический научный сборник "Автоматизация проектирования электронной аппаратуры", выпуск 6, Под.ред. Курейчика В. М. Таганрог, 1989.

75. Курейчик В. М. Генетические алгоритмы и их применение в САПР. Междуведомственный тематический научный сборник "Интеллектуальные САПР", Выпуск 5. Таганрог, 1995.

76. Файзуллин А. 3.\ Генетический алгоритм упаковки элементов произвольной формы на Плоскости. Междуведомственный тематический научный сборник "Интеллектуальные САПР", Выпуск 5. Таганрог, 1995.155V

77. Чернышев Ю. О., Буракова А. В. Исследование генетических методов решения задачи коммивояжера. Междуведомственный тематический научный сборник "Интеллектуальные САПР", Выпуск 5. Таганрог, 1995.

78. С. Б. Михалев, А. Н. Зажарский, В. В. Кондратьев. Средства вычислительной техники для применения в САПР. Минск, "Беларусь", 1989.

79. Б. С. Федоров, Н. Б* Гуляев. Проектирование программного обеспечения САПР. Серия "Разработка САПР", книга 3. Москва, "Высшая школа", 1990. ■

80. В. И. Кузовлев, П. Н. Шкатов. Математические методы анализа производительности и надежности САПР. Серия "Разработка САПР", книга 8. Москва, "Высшая школа", 1990.

81. Под. ред. А. В. Петрова. Лабораторный практикум на базе учебно-исследовательской САПР. Серия "Разработка САПР", книга 10. Москва, "Высшая школа", 1991.

82. J. Cong, М. Smith. "A parallel bottom-up clustering algorithm with applications to circuit partitibning in vlsi circuit design", in 30th ACM/IEEE Design Automation Conference, 1993, pp.755-760.

83. Y. Saab, V. Rao. "Stochastic evolution: A fast effective heuristic for some genetic layout problems", in 27th ACM/IEEE Design Automation Conf., 1990, pp.26-31.

84. G. Laszewski. "Intelligent structural operators for the k-way graph partitioning problem", in 4th Iht.Conf. Genetic Algorithms, 1991, pp.45-52.

85. J. P. Cohoon, W. N. Martin, D. S. Richards. A multi-population genetic algorithm for solving the k-partition problem on hyper cubes", in 4th Int. Conf. Genetic Algorithms, 1991, pp.244-248.

86. T. N. Bui, B. R. Moon. "Genetic algorithm and graph partitioning", IEEE Trans. Comput., vol.45, pp. 841-855, 1996.

87. D. Levine. "A genetic algorithm for the set partitioning problem", in 5th Int. Conf. Genetic Algorithms, 1993, pp.481-487.

88. C. Palmer, A. Kershenbaum. "Representing trees in genetic algorithms", IEEE Conf. Evolutionary Computation, 1994, pp.379-384.

89. D. Goldberg, Genetic algorithms in search, optimiszation, and machine learning. MA, Addison-Wesley, 1989.

90. T. N. Bui, B. R. Moon, "Analyzing hyperplane synthesis in geneticValgorithms using clustered schemata", in Int. Conf. Evolutionary Computation, 1994, Lecture Notés in Computer Science, 866, Springer-Verlag, pp.108-118.

91. K. Dejong. "An analysis of the behavior of a class of genetic adaptive systems", Univers. Michigan, Ann Arbor, 1975.

92. T. S. Moh, T. S. Chang, S. L. Hakimi. "Globally Optimal Floorplanning for a Layout Problem", in IEEE Transactions on Circuits and Systems, vol.43, №9, Sept. 1996, pp.713-720.

93. J. Cohoon, W. Paris. "Genetic placement", in Proc. IEEE Int. Conf.

94. Computer-Aided-Design, 1986, pp.422-425.v

95. C. K. Cheng, T. C; Hu. The optimal partitioning of networks. Tech. report CS89-146, UC San Diego, March 1989.

96. C. K. Cheng, Y. C. Wei. "An improved two-way partitioning algorithm with stable performence", IEEE Trans. on CAD, 10(12), Dec. 1991, pp. 15021511.

97. S. W. Hadley, B. L. Mark, A. Vanelli. "An efficient eigenvector approach for finding netlist partitions", IEEE Trans, on CAD, CAD-11 (7), July 1992, pp. 885-892.

98. J. Y. Zien. "Spectral k-way ratio cut partitioning". Master's thesis, UC Santa Cruz, March 1993. i1. V /37

99. R. K. Belew, L. B. Booker. Proceedings of the fourth International Conference on Genetic Algorithms, Univ. of California, San Diego, July 1991. Morgan Kaufmann Publishers; Inc., San Mateo, CA.

100. H. Ding, A. A. El-Keib, R. E. Smith. Optimal Clastering of Power Networks Using Genetic Algorithms, TCGA Report №92001, March 1992, Univ. of Alabama, Tuscaloosa, AL.

101. D. R. Jones, M. A. Beltramo. "Solving Partitioning Problem with Genetic Algorithms". Proceed, of 4th Int. Conf. on Genetic Algorithms, San Diego, July 1991.

102. D. Smith. "Bin Packing with Adaptive Search", proced. of 1st Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, July 1985.