Разработка и исследование генетических алгоритмов компоновки по критериям числа внешних связей и задержки распространения сигналов

• Автор: Рябец, Михаил Николаевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Таганрог
• Количество страниц: 140 с.

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

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

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

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

1.4. Выводы и рекомендации.

2. Разработка методики поиска при решении задачи

компоновки. ,. .

2.1. Методы генетического поиска и разработка структуры алгоритма

2.2. Кодирование решений в генетическом алгоритме

2.3. Препроцессинг .

2.4. Выводы и рекомендации.

3. Построение и анализ генетических алгоритмов.
3.1. Выбор генетических операторов.
3.2. Расчет целевой функции.и оценка критериев.
3.3. Критерий остановки и анализ сходимости
3.4. Эвристика улучшения решений
3.5. Блок адаптации,, .
3.6. Выводы и рекомендации.
4. Разработка программной подсистемы и анализ
экспериментальных результатов.
4.1. Разработка программного обеспечения.
4.1.1. Структурная схема и принцип построения про1раммного обеспечения .
4.1.2. Краткое описание выполнения программного обеспечения.
. 1 .
4.2. Анализ экспериментальных результатов.
4.2.1. Экспериментальные результаты по разработанному алгоритму.9
4.2.1. Экспериментальные результаты по разработанному алгоритму
4.2.2. Сравнительные оценки работы нескольких алгоритмов.
4.3. Выводы и рекомендации
Список литературы


Комбинаторные методы 1, предназначены для поиска оптимального решения в некотором конечном множестве. В большинстве случаев они используют различные варианты сокращенного перебора, поскольку полный перебор в реальных задачах неосуществим изза слишком большой их размерности. Наиболее распространенный из этих методов метод ветвей и границ , , . Эти методы основаны на идее последовательного разбиения множества на подмножества и формировании оценок , позволяющих рассматривать только те подмножества, которые могут содержать решение задачи т. Основной недостаток этих методов заключается в необходимости корректного выбора оценок, в противном случае при неверном выборе данный метод будет осуществлять полный перебор. Вычислительная сложность алгоритмов данного типа лежит в пределах от О ап2 до 0рп4. Эвристические методы 1, . Для данного класса методов нет четкого математического обоснования, отсутствуют оценки точности решений и условия, гарантирующие получение корректных результатов. В их основе лежат логические соображения. Данные методы не гарантируют нахождение оптимального решения и сильно зависят от класса и описания решаемой задачи. Эвристические методы на практике позволяют получать неплохие результаты, однако предсказать их поведение невозможно. Эвристические методы могут использоваться как самостоятельно, так и в соединении с другими методами, используя найденное с помощью эвристики решение в качестве исходного и дальнейшего улучшения его какимлибо другим, например, комбинаторным методом. Это позволяет значительно сократить время решения задачи.