Генетические методы структурного синтеза проектных решений тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Арутюнян, Нарек Микаелович

• Арутюнян, Нарек Микаелович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Арутюнян, Нарек Микаелович

ВВЕДЕНИЕ.

ГЛАВА 1. СОСТОЯНИЕ ПРОБЛЕМЫ СТРУКТУРНОГО СИНТЕЗА В

ПРОЕКТИРОВАНИИ И ЛОГИСТИКЕ.

1.1. Задачи структурного синтеза проектных решений.

1.1.1. Задачи пространственного синтеза.

1.1.2. Задачи пространственно-временного синтеза.

1.2. Подходы к решению задач структурного синтеза проектных решений

1.2.1. Интеллектуальные системы и методы структурного синтеза.

1.2.2. Методы дискретного математического программирования.

1.3. Эволюционные методы.

1.3.1. Базовый генетический алгоритм.

1.3.2. Метод «поведения толпы».

1.3.3. Метод «колонии муравьев».

1.4. Тестовые задачи.

Выводы.

ГЛАВА 2. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ.

2.1. Разновидности генетических операторов.

2.2. Многоточечный и однородный кроссовер.

2.3. Параллельные и гибридные генетические методы.

2.4. Метод комбинирования эвристик.

Выводы.

ГЛАВА 3. НОВЫЕ ГЕНЕТИЧЕСКИЕ МЕТОДЫ.

3.1. Смешанный эволюционный метод.

3.1.1. Обоснование предпочтительности многоточечного кроссовера.

3.1.2. Варианты смешанного эволюционного метода.

3.2. Метагенетический метод.

3.3. Циклический генетический метод.

Выводы.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ

НОВЫХ ГЕНЕТИЧЕСКИХ МЕТОДОВ.

Программное обеспечение генетического поиска.

4.2. Многоточечность и полигамность.

4.2.1. Оценка эффективности смешанного эволюционного метода.

4.2.2. Оценка эффективности метода комбинирования эвристик.

4.3. Адаптивность.

4.4. Предотвращение преждевременной стагнации.

Выводы.

Введение диссертации (часть автореферата) на тему «Генетические методы структурного синтеза проектных решений»

В настоящее время весьма актуальными являются проблемы создания и разработки новых высокоточных и быстрых методов для синтеза проектных решений[18,23]. Маршруты проектирования сложных изделий в САПР машиностроения и радиоэлектроники состоят из чередующихся процедур синтеза и анализа проектных решений. В современных САПР преимущественно развиты математическое и программное обеспечения процедур анализа. Принятие проектных решений охватывает широкий круг задач, однако эти задачи трудно формализуемы. Но и в случае формализации их практическая реализация не всегда очевидна. Для многих формализуемых задач структурного синтеза применение известных математических методов не представляется возможным вследствие проблем NP-полноты и большого размера задач. Именно по этой причине структурный синтез обычно выполняется в интерактивном режиме при определяющей роли человека. В первую очередь, это относится к структурному синтезу, при котором выбираются принципиальные конструктивные и схемные решения. Однако по мере усложнения проектируемых изделий возможности человека в решении задач сужаются, растут затраты времени на проектирование, зачастую принимаются решения, далекие от оптимальных. Поэтому поиск новых эффективных методов структурного синтеза проектных решений относится к актуальным проблемам развития математического обеспечения САПР.

Методы локальной оптимизации (Hill Climbing), моделирование отжига (Simulated Annealing) [55,56], генетические алгоритмы (Genetic Algorithms), [35,51,54], нейронные сети (Neural Network) [57,63,66] и поиск с запретами (Tabu Search)[47,48,49,50] - только часть стохастических алгоритмов, которые применяются при решении задач проектирования. Все эти методы, за исключением генетических алгоритмов (ГА), в каждый момент поиска рассматривают только одно решение, и оно неоднократно улучшается во время работы алгоритма.

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

Генетические алгоритмы были предложены в 1975 г. профессором Джоном Холландом [54] в Мичиганском университете. Они получили широкое распространение благодаря профессору университета штата Иллинойс Дэйвиду Гольдбергу [51] и его студентам [35]. В дальнейшем генетические алгоритмы получили развитие в трудах: Э.Гудмана, Л.Дэйвиса, Д.Фогелья и многих других. Значительный вклад в развитие теории эволюционного моделирования и стохастической оптимизации внесли Курейчик В.В.[9,10,59], Курейчик В.М.[5,10,11,12], Батищев Д.И.[2], Мухачева А.С. [16], Де Янг[35,36], Букатова ИЛ.[3], Растригин Л.А.[27], НоренковИ.П. [17,18,19,20,23].

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

Основные преимущества ГА следующие адаптируются и «обучаются» в течение своего исполнения; имеют параллельность внутренних процессов; применимы к задачам как с числовыми, так и предметными переменными, т.е. позволяют осуществлять поиск в неметризуемых пространствах параметров.

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

Эффективность применения ГА, оцениваемая, прежде всего, степенью приближения результатов решения к оптимальным значениям, не всегда оказывается удовлетворительной. Кроме того, ГА довольно трудоемки, что ограничивает сложность моделей, используемых для расчета целевых функций. Поэтому исследования, направленные на устранение указанных недостатков ГА, сохраняют свою актуальность.

Для повышения эффективности ГА разрабатываются новые алгоритмы выполнения генетических операторов. Разработан ряд алгоритмов кроссовера, селекции и мутации [21,32,36,40,64,65,68].

Другой подход к повышению эффективности ГА основан на применении метода комбинирования эвристик (НСМ) [17], в котором гены представляют не сами искомые проектные параметры, а некоторые эвристические алгоритмы их выбора. Эффективность НСМ зависит от правильности выбора совокупности используемых при поиске эвристических правил.

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

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

В работе показано, что достижение поставленной цели требует решения следующих основных задач:

1. Анализ существующих подходов к решению задач структурного синтеза в проектировании и логистике.

2. Определение параметров, управление которыми позволяет повысить эффективность ГА.

3. Разработка новых генетических методов структурного синтеза проектных решений.

4. Экспериментальная оценка эффективности разработанных методов.

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

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

Диссертация включает введение, четыре главы с выводами, заключение, список литературы и приложения.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Арутюнян, Нарек Микаелович

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

Основные научные теоретические и практические результаты работы состоят в следующем.

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

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

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

4. Автоматический выбор значений параметров и типов генетических операторов в процессе генетического поиска реализован в метагенетическом алгоритме. Как и для определения значений управляемых параметров исходной оптимизационной задачи, для выбора значений параметров и типов операторов использованы генетические алгоритмы. К числу адаптируемых параметров в разработанном алгоритме также относятся длина фрагмента L для смешанного эволюционного метода, а также глубина и частота применения макромутаций в циклическом генетическом методе.

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

6. Экспериментальная оценка эффективности новых генетических методов - смешанного эволюционного метода и метода комбинирования эвристик - показала, что однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА. При этом метод комбинирования эвристик HCM-m(m) превосходит по эффективности метод CGA-w(m) с обычным кодированием хромосом. Смешанный генетический метод HCM-m(m) с многими родителями превосходит по эффективности метод НСМ-т(2), в котором при кроссовере происходит скрещивание генов только двух родителей.

Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГАС «Волна» (г. Москва) и в учебный процесс МГТУ им. Н.Э. Баумана.

113

Список литературы диссертационного исследования кандидат технических наук Арутюнян, Нарек Микаелович, 2007 год

1. Автоматизированный синтез сооружений биохимической очистки сточных вод /ОАО «Пигмент», http://www.gaps.tstu.ru/win-251/lab/sreda/ope/ob ecol html/avtom.html

2. Батищев Д.И., Власов С.Е., Булгаков И.В. Решение задачи «слепого» упорядочения при помощи генетических алгоритмов. М.: Научное издательство «ТВП», 1996. - С. 143-155.

3. Букатова И.Л. Обучающиеся, адаптивные и самоорганизующиеся эволюционные вычисления. М.: Научное издательство «ТВП», 1996. -С. 169-181.

4. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии. 2005. -№10.-С. 36-43.

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционных вычислений. М.: ФИЗМАТЛИТ, 2003. -432с.

6. Ермаченко А. И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя//Принятие решений в условиях неопределенности. Сб. научн. статей. -Уфа: УГАТУ, 2000. С. 35-39.

7. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения /А.С. Мухачева, А. В. Чиглинцев, М. А. Смагин, Э.А. Мухачева //Информационные технологии. -2001. № 9, приложение. - 46с.

8. Кукин В.Д. Эволюционная модель для решения потоковой задачи Штейнера // Методы математического моделирования и информационные технологии. Труды ИПМИ КарНЦ РАН. -Петрозаводск, 2004. С. 200 - 211.

9. Курейчик В.В. Перспективные архитектуры генетического поиска //Программные продукты и системы. 1998. - № 3. - С. 47-48.

10. Курейчик В.М. Зинченко JI.A. Синергетическое эволюционное проектирование// 8 национальная конференция по искусственном интеллекту с международным участием, г.Коломна, 7-12 октября, 2002г. М., 2002. - С.876-884.

11. Курейчик В.М. Курейчик В.В. Фрактальный алгоритм разбиения графов// Теория и системы управления(М.). -2002. № 4. - С. 65-75.

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

13. Ли К. Основы САПР (CAD/CAV/CAE). СПб: Питер, 2006. - 580 с.

14. Мартынов В. В., Валиуллин А.М. Регулярное размещение двумерных геометрических объектов сложной формы/Прикладная геометрия: электронный журнал(М.). -1999. -Вып. 3. -№ 4. -11с.

15. Модели и методы решения задач ортогонального раскроя и упаковки / Э.А. Мухачева, А.Ф. Валеева, В.М. Картак, А.С. Мухачева //Приложение к журналу «Информационные технологии», -2004 № 5. -32 с.

16. Мухачева А. С., Мухачева Э. А. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя //Информационные технологии. 2002. -№ 6. - С. 25-30.

17. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации //Информационные технологии. 1999. -№1. -С. 2-7.

18. Норенков И.П. Основы автоматизированного проектирования. М.: Издательств МГТУ им. Баумана, 2000. - 336 с.

19. Норенков И.П., Арутюнян Н.М. Смешанный эволюционный метод // Информационные технологии. 2007. - № 1. - С. 17-20.

20. Норенков И.П., Арутюнян Н.М. Метагенетический алгоритм оптимизации и структурного синтеза //Информационные технологии. -2007. -№3.- С. 10-13.

21. Норенков И.П., Арутюнян Н.М. Состояние проблемы структурного синтеза в проектировании и логистике //Наука и образование. Инженерное образование: Электронный журнал. 2007. - № 9. -37с.

22. Норенков И.П., Арутюнян Н.М., Бондаренко А.А., Сравнительный анализ эффективности эволюционных методов на примере задачи синтеза расписаний // Информационные технологии. 2006. - № 5. -С.6-11.

23. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. М.: Издательств МГТУ им. Баумана, 2002. - 320 с.

24. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.-288 с.

25. Овчинников В.А. Эволюционно-генетический подход к синтезу передней части кузова легкового автомобиля //Информационные технологии. 2005. - № 9. - С. 36-38.

26. Писаренко Г.К. Алгоритмы частотного планирования в телекоммуникационных системах радиосвязи // Информационные технологии. 2000. - № 7. - С. 14-17.

27. Растригин JI.A. Случайный поиск в эволюционных вычислениях. -М.: Научное издательство «ТВП», 1996. С. 135-142.

28. Скурихин А. Генетические алгоритмы// Новости искусственного интеллекта. 1995. - № 4. - С. 6-17.

29. Системы автоматизированного проектирования в радиоэлектронике: Справочник /Под ред. И.П. Норенкова. М.: Радио и связь, 1986. - 368 с.

30. Стоян Ю. Г. Размещение геометрических объектов. Киев: Наукова думка, 1975.-234 с.

31. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.Брейера. М.: Мир, 1977. -282 с.

32. Baker J. Reducing Bias and Inefficiency in the Selection Algorithm Genetic Algorithms and Their Applications// Proc. Second International Conf. J. Grefenstette /Ed. Lawrence Erlbaum. Massachusetts(MIT),1987. -P. 14-21.

33. Blanton J., Wainwright R. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms// Proc. of 5th Int. Conf. on GA. Massachusetts(MIT), 1993. - P. 452-460.

34. Colorni A., Dorigo M., V. Maniezzo. Distributed Optimization by Ant Colonies //Proceedings of the First European Conference on Artificial Life, Paris, 1992.-P. 134-142.

35. De Jong K. An Analysis of the Behavior of a Class of Genetic Adaptive Systems: PhD thesis. Ann Arbor, 1975. - 126 p.

36. De Jong K.A., Spears W.M. A Formal Analysis of the Role of Multipoint Crossover in Genetic Algorithms //Annals of Mathematics and Artificial Intelligence. -Florida, 1992. -V5. P. 1-26.

37. Deb K. and Agrawal, S. Understanding interactions among genetic algorithm parameters //Foundations of Genetic Algorithms, 1999. V. - P. 265-286.

38. Deneubourg J., Goss S., Pasteels J.M. Self-organization mechanisms in ant societies (II): learning in foraging and division of labor. //From Individual to Collective. Behavior in Social Insects. Basel: Birkhauser, 1987.-267 p.

39. Devis L., Cox A. A genetic algorithm for survivable network designtV»

40. Proc. of 5 International Conference on Genetic Algorithms, San Mateo (California), 1993.-P. 408-415.

41. Dorigo M. Optimization, Learning and Natural Algorithms: PhD thesis. -Milan, 1992.-109 p.

42. Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization //Artificial Life, V.5. Brussels, 1999. -№ 3. -96 p.

43. Dorigo M., Gambardella L. Ant Colony for Traveling Salesman Problem. Bruxelles,1996. - P. 53-66.

44. Eberhart R.C. and Kennedy J. A New Optimizer Using Particles Swarm Theory //Proc. Sixth International Symposium on Micro Machine and Human Science, Piscataway, 1995. -P. 39-43.

45. Eberhart R.C., Dobbins R.W., Simpson P. Computational Intelligence PC Tools. Boston: Academic Press, 1996. - 464 p.

46. Giffler В., Tompson G.L. Algorithms for Solving Production-Scheduling problems // Operational Research. 1964. - № 2. - P. 305-324.

47. Glover F. Future paths for integer programming and links to artificial intelligence// Computers and Operations Research. 1986. - Vol. 13. - P. 533-549.

48. Glover F. Tabu search: Part 1// ORSA Journal on Computing. 1989. -Vol. l.-P.l90-206.

49. Glover F. Tabu search: Part 2 // ORSA Journal on Computing. 1990. -Vol. 2. - P.4-32.

50. Glover F. Tabu search methods for optimization. Feature Issue of Europen J. Oper. Res. -1998. V106, № 2. - P. 4-32

51. Glover F., Laguna. M. Tabu search. -Boston: Kluwer Acad. Publ, 1997. -382 p.

52. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. - 412 p.

53. Goodman E., Punch W. New Technologies to Improve Coarse-Grain Parallel GA Performance // CAD-95 XXII Int. School and Conf. on CAD. Yalta-Gurzuff, 1995. Part 2. - P. 29-40.

54. Holland J. Adaptation in Natural and Artificial Systems. Ann Arbor. Univ. of Michigan Press, 1975.-228 p.

55. Holland J. Some practical aspects of adaptive systems theory// Electronic Information Handling. London, 1965. - P. 209 - 217.

56. Kirkpatrick S. Optimization by simulated annealing: quantitative studies //Statistical Physics. -1984. Vol. 34. - P. 975-986.

57. Kirkpatrick S., Vecchi M. P. Optimization by simulated annealing. //Science. 1983.-Vol. 220.-P. 671-680.

58. Kohonen T. Self-organization and associative memory. New York: Springer-Verlag, 1997, - 428 p.

59. Koza J.R., Riccardo Poli. A Genetic Programming Tutorial. Fairchild, 2004.-819p.

60. Kureichik V.M. Kureichik V.V. Zinchenko L.A. Greedy genetics in memory optimization of reconfigurable computing in wireless //Advances in concurrent engineering. -Lisse, 2002. P. 771-777.

61. Lis J. Parallel Genetic Algorithm with Dynamic Control Parameter. //Proceedings of the 1996 IEEE Conference on Evolutionary Computation. -Piscataway, 1996. -P.324-329.

62. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem //European Journal of Operational Research. -2002. № 141. - P. 410-420.

63. Martynov V. Geometrical objects regular placement onto a stock sheet or strip//Pesquisa Operacional(BRAZIL). -1999. -Vol. 19. № 2. - P. 211222.

64. McClelland J. L., Rumelhart D. E. Parallel distributed processing: explorations in the microstructures of cognition. Volume 2: psychological and biological models. Cambridge(Mass.): MIT Press., - 1986. - 454 p.

65. Muhlenbein J. How genetic algorithms really work: Mutation and Hill climbing, Parallel Problem Solving from Nature -2- R / Manner and B. Manderick eds. Amsterdam, 1994. - P. 15-26.

66. Pinaki Mazumder, Rudnick Elizabeth M. GENETIC ALGORITHMS for VLSI Design, Layout & Test Automation. -Upper Saddle River: Hall PTR, 1999.-335 p.

67. Rumelhart D. E., McClelland J. L. Parallel distributed processing: explorations in the microstructures of cognition. Volume 1: foundations. -Cambridge(Mass.): MIT Press,. 1986. - 516p.

68. Shahookar K.,Mazmunder P. A Genetic Approach to standart Cell Placement Using Meta-Genetic Parameter Optimization //IEEE Trans, on CAD. 1990. - Vol.9, No.5, May. - P. 500 - 511.

69. Spears W., DeJong K. An Analysis of Multipoint Crossover Foundations of Genetic Algorithms. -G. Rawlins, /ed. Morgan-Kaufmann. -Bloomington, 1991.-P. 301-315.

70. Syswerda G. Uniform Crossover in Genetic Algorithms //Proc. 3rd Int. Conf. on Genetic Algorithms. -LA, 1989. P. 2-9.

71. The Radio-link Frequency Assignment Problem: a Case Study Using GA./ A. Kapsalis, P. Chardaire, V. Rayward-Smith, G.Smith //AISB Workshop on Evolutionary Computing. -Washington, 1995. P. 117-131.

72. Tulai A.F. and Oppacher F. Parallel Genetic Algorithm with Strategy Parameters Encoded as Chromosomes //Artificial and Computational Intelligence. Tokyo, 2002. -№ 3. - P 34-47.