Генетические методы структурного синтеза проектных решений
Диссертация
Генетические алгоритмы отличаются тем, что в процессе поиска рассматривается несколько решений параллельно. При оптимизации ГА также допускаются значительные и недетерминированные изменения (оператор мутации), что уменьшает вероятность «застревания» текущей точки в локальных экстремумах или на дне узких «оврагов». В ГА с помощью комбинирования двух проектных решений (оператор кроссовера… Читать ещё >
Содержание
- ГЛАВА 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. Тестовые задачи
- 1. 1. Задачи структурного синтеза проектных решений
- Выводы
- ГЛАВА 2. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
- 2. 1. Разновидности генетических операторов
- 2. 2. Многоточечный и однородный кроссовер
- 2. 3. Параллельные и гибридные генетические методы
- 2. 4. Метод комбинирования эвристик
- Выводы
- ГЛАВА 3. НОВЫЕ ГЕНЕТИЧЕСКИЕ МЕТОДЫ
- 3. 1. Смешанный эволюционный метод
- 3. 1. 1. Обоснование предпочтительности многоточечного кроссовера
- 3. 1. 2. Варианты смешанного эволюционного метода
- 3. 2. Метагенетический метод
- 3. 3. Циклический генетический метод
- 3. 1. Смешанный эволюционный метод
- Выводы
- ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ НОВЫХ ГЕНЕТИЧЕСКИХ МЕТОДОВ
- Программное обеспечение генетического поиска
- 4. 2. Многоточечность и полигамность
- 4. 2. 1. Оценка эффективности смешанного эволюционного метода
- 4. 2. 2. Оценка эффективности метода комбинирования эвристик
- 4. 3. Адаптивность
- 4. 4. Предотвращение преждевременной стагнации
- 4. 2. Многоточечность и полигамность
- Выводы
Список литературы
- Автоматизированный синтез сооружений биохимической очистки сточных вод /ОАО «Пигмент», http://www.gaps.tstu.ru/win-251/lab/sreda/ope/ob ecol html/avtom.html
- Батищев Д.И., Власов С. Е., Булгаков И. В. Решение задачи «слепого» упорядочения при помощи генетических алгоритмов. М.: Научное издательство «ТВП», 1996. — С. 143−155.
- Букатова И.Л. Обучающиеся, адаптивные и самоорганизующиеся эволюционные вычисления. М.: Научное издательство «ТВП», 1996. -С. 169−181.
- Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии. 2005. -№ 10.-С. 36−43.
- Емельянов В.В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционных вычислений. М.: ФИЗМАТЛИТ, 2003. -432с.
- Ермаченко А. И., Сиразетдинов Т. М. Рекурсивный метод для решения задачи гильотинного раскроя//Принятие решений в условиях неопределенности. Сб. научн. статей. -Уфа: УГАТУ, 2000. С. 35−39.
- Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения /А.С. Мухачева, А. В. Чиглинцев, М. А. Смагин, Э. А. Мухачева //Информационные технологии. -2001. № 9, приложение. — 46с.
- Кукин В.Д. Эволюционная модель для решения потоковой задачи Штейнера // Методы математического моделирования и информационные технологии. Труды ИПМИ КарНЦ РАН. -Петрозаводск, 2004. С. 200 — 211.
- Курейчик В.В. Перспективные архитектуры генетического поиска //Программные продукты и системы. 1998. — № 3. — С. 47−48.
- Курейчик В. М. Зинченко JI.A. Синергетическое эволюционное проектирование// 8 национальная конференция по искусственном интеллекту с международным участием, г. Коломна, 7−12 октября, 2002 г. М., 2002. — С.876−884.
- Курейчик В. М. Курейчик В.В. Фрактальный алгоритм разбиения графов// Теория и системы управления (М.). -2002. № 4. — С. 65−75.
- Ли К. Основы САПР (CAD/CAV/CAE). СПб: Питер, 2006. — 580 с.
- Мартынов В. В., Валиуллин А. М. Регулярное размещение двумерных геометрических объектов сложной формы/Прикладная геометрия: электронный журнал (М.). -1999. -Вып. 3. -№ 4. -11с.
- Модели и методы решения задач ортогонального раскроя и упаковки / Э. А. Мухачева, А. Ф. Валеева, В. М. Картак, А. С. Мухачева //Приложение к журналу «Информационные технологии», -2004 № 5. -32 с.
- Мухачева А. С., Мухачева Э. А. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя //Информационные технологии. 2002. -№ 6. — С. 25−30.
- Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации //Информационные технологии. 1999. -№ 1. -С. 2−7.
- Норенков И.П. Основы автоматизированного проектирования. М.: Издательств МГТУ им. Баумана, 2000. — 336 с.
- Норенков И.П., Арутюнян Н. М. Смешанный эволюционный метод // Информационные технологии. 2007. — № 1. — С. 17−20.
- Норенков И.П., Арутюнян Н. М. Метагенетический алгоритм оптимизации и структурного синтеза //Информационные технологии. -2007. -№ 3.- С. 10−13.
- Норенков И.П., Арутюнян Н. М. Состояние проблемы структурного синтеза в проектировании и логистике //Наука и образование. Инженерное образование: Электронный журнал. 2007. — № 9. -37с.
- Норенков И.П., Арутюнян Н. М., Бондаренко А. А., Сравнительный анализ эффективности эволюционных методов на примере задачи синтеза расписаний // Информационные технологии. 2006. — № 5. -С.6−11.
- Норенков И.П., Кузьмик П. К. Информационная поддержка наукоемких изделий. М.: Издательств МГТУ им. Баумана, 2002. — 320 с.
- Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.-288 с.
- Овчинников В.А. Эволюционно-генетический подход к синтезу передней части кузова легкового автомобиля //Информационные технологии. 2005. — № 9. — С. 36−38.
- Писаренко Г. К. Алгоритмы частотного планирования в телекоммуникационных системах радиосвязи // Информационные технологии. 2000. — № 7. — С. 14−17.
- Растригин JI.A. Случайный поиск в эволюционных вычислениях. -М.: Научное издательство «ТВП», 1996. С. 135−142.
- Скурихин А. Генетические алгоритмы// Новости искусственного интеллекта. 1995. — № 4. — С. 6−17.
- Системы автоматизированного проектирования в радиоэлектронике: Справочник /Под ред. И. П. Норенкова. М.: Радио и связь, 1986. — 368 с.
- Стоян Ю. Г. Размещение геометрических объектов. Киев: Наукова думка, 1975.-234 с.
- Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.Брейера. М.: Мир, 1977. -282 с.
- 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.
- 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.
- 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.
- De Jong K. An Analysis of the Behavior of a Class of Genetic Adaptive Systems: PhD thesis. Ann Arbor, 1975. — 126 p.
- 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.
- Deb K. and Agrawal, S. Understanding interactions among genetic algorithm parameters //Foundations of Genetic Algorithms, 1999. V. — P. 265−286.
- 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.
- Devis L., Cox A. A genetic algorithm for survivable network designtV"
- Proc. of 5 International Conference on Genetic Algorithms, San Mateo (California), 1993.-P. 408−415.
- Dorigo M. Optimization, Learning and Natural Algorithms: PhD thesis. -Milan, 1992.-109 p.
- Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization //Artificial Life, V.5. Brussels, 1999. -№ 3. -96 p.
- Dorigo M., Gambardella L. Ant Colony for Traveling Salesman Problem. Bruxelles, 1996. — P. 53−66.
- 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.
- Eberhart R.C., Dobbins R.W., Simpson P. Computational Intelligence PC Tools. Boston: Academic Press, 1996. — 464 p.
- Giffler В., Tompson G.L. Algorithms for Solving Production-Scheduling problems // Operational Research. 1964. — № 2. — P. 305−324.
- Glover F. Future paths for integer programming and links to artificial intelligence// Computers and Operations Research. 1986. — Vol. 13. — P. 533−549.
- Glover F. Tabu search: Part 1// ORSA Journal on Computing. 1989. -Vol. l.-P.l90−206.
- Glover F. Tabu search: Part 2 // ORSA Journal on Computing. 1990. -Vol. 2. — P.4−32.
- Glover F. Tabu search methods for optimization. Feature Issue of Europen J. Oper. Res. -1998. V106, № 2. — P. 4−32
- Glover F., Laguna. M. Tabu search. -Boston: Kluwer Acad. Publ, 1997. -382 p.
- Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. — 412 p.
- 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.
- Holland J. Adaptation in Natural and Artificial Systems. Ann Arbor. Univ. of Michigan Press, 1975.-228 p.
- Holland J. Some practical aspects of adaptive systems theory// Electronic Information Handling. London, 1965. — P. 209 — 217.
- Kirkpatrick S. Optimization by simulated annealing: quantitative studies //Statistical Physics. -1984. Vol. 34. — P. 975−986.
- Kirkpatrick S., Vecchi M. P. Optimization by simulated annealing. //Science. 1983.-Vol. 220.-P. 671−680.
- Kohonen T. Self-organization and associative memory. New York: Springer-Verlag, 1997, — 428 p.
- Koza J.R., Riccardo Poli. A Genetic Programming Tutorial. Fairchild, 2004.-819p.
- 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.
- Lis J. Parallel Genetic Algorithm with Dynamic Control Parameter. //Proceedings of the 1996 IEEE Conference on Evolutionary Computation. -Piscataway, 1996. -P.324−329.
- 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.
- Martynov V. Geometrical objects regular placement onto a stock sheet or strip//Pesquisa Operacional (BRAZIL). -1999. -Vol. 19. № 2. — P. 211 222.
- 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.
- 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.
- Pinaki Mazumder, Rudnick Elizabeth M. GENETIC ALGORITHMS for VLSI Design, Layout & Test Automation. -Upper Saddle River: Hall PTR, 1999.-335 p.
- Rumelhart D. E., McClelland J. L. Parallel distributed processing: explorations in the microstructures of cognition. Volume 1: foundations. -Cambridge (Mass.): MIT Press,. 1986. — 516p.
- 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.
- Spears W., DeJong K. An Analysis of Multipoint Crossover Foundations of Genetic Algorithms. -G. Rawlins, /ed. Morgan-Kaufmann. -Bloomington, 1991.-P. 301−315.
- Syswerda G. Uniform Crossover in Genetic Algorithms //Proc. 3rd Int. Conf. on Genetic Algorithms. -LA, 1989. P. 2−9.
- 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.
- 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.