Генетические методы структурного синтеза проектных решений

• Автор: Арутюнян, Нарек Микаелович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 120 с. : ил.

Оглавление
ВВЕДЕНИЕ

ГЛАВА 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. Предотвращение преждевременной стагнации.
ВЫВОДЫ И ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


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