Разработка и исследование интегрированной инструментальной подсистемы генетического поиска

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К МОДЕЛИРОВАНИЮ ЭВОЛЮЦИОННОГО ПОИСКА

1.1. МЕТОДЫ ГЕНЕТИЧЕСКОГО ПОИСКА

1.2. ОПИСАНИЕ МОДЕЛЕЙ ЭВОЛЮЦИИ

1.3. СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА СУЩЕСТВУЮЩИХ ПРОГРАММ ГЕЕТИЧЕСКОГО ПОИСКА

1.4. ПОСТАНОВКА ЗАДАЧИ РАЗМЕЩЕНИЯ.

1.5. ВЫВОДЫ.

2. АРХИТЕКТУРА ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

2.1. СТРУКТУРА И ОРГАНИЗАЦИЯ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

Подсистема пользовательского интерфейса

Ядро подсистемы генетического поиска.
2.2. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ РЕШЕНИЯ ЗАДАЧИ
Варианты представления различных типов данных, их кодирование и
декодирование в виде хромосом
Представление решения задачи размещения
2.3. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА.
2.4. ВЫВОДЫ.
3. РАЗРАБОТКА БЛОКОВ ИНТЕРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И АЛГОРИТМОФ ЕЕ ФУНКЦИОНИРОВАНИЯ
3.1. КОМПОНЕНТНАЯ МОДЕЛЬ ОРГАНИЗАЦИИ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА
3.2. ВНУТРЕННЯЯ СТРУКТУРА ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА
3.3. ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА ОПИСАНИЯ ПРОЦЕДУР ГЕНЕТИЧЕСКОГО ПОИСКА ПРОЕКТНЫХ РЕШЕНИЙ.
3.4. РАЗРАБОТКА АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА
3.5. РАЗРАБО ТКА МОДИФИЦИРОВАННЫХ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.
3.6. РАЗРАБОТКА АЛГОРИТМА ДВУМЕРНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СХЕМ.
3.7. ВЫВОДЫ
4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И НА ПРИМЕРЕ ЗАДАЧИ РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ ЭЛЕМЕНТОВ СХЕМЫ
4.1. ЦЕЛЬ ЭКСПЕРИМЕНТА.
4.2. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВРЕМЕННОЙ И ПРОСТРАНСТВЕННОЙ СЛОЖНОСТИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗМЕЩЕНИЯ
4.3. ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА.
4.4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА.
4.5. ВЫВОДЫ
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Правило сопоставления особи (решения) и такой оценки называют целевой функцией (ЦФ), которая в литературе иногда называется функцией полезности, приспособленности или пригодности. Эта функция используется в ГА для сравнения альтернативных решений между собой и выбора лучших []. Следовательно, основная задача генетических алгоритмов состоит в оптимизации целевой функции. Традиционные оптимизационные алгоритмы для нахождения лучшего решения используют большое количество допущений при оценке ЦФ. Эволюционный подход не требует таких допущений. Это расширяет класс задач, которые можно решать с помощью генетических алгоритмов. Результаты существующих исследований позволяют сделать вывод, что ГА способны решать те проблемы, решение которых традиционными алгоритмами затруднительно []. Генетический алгоритм дает преимущества при решении практических задач. Одно из них - это адаптация к изменяющейся окружающей среде. В реальной жизни постановка задачи, может претерпеть некоторые изменения в процессе решения. При использовании традиционных методов все вычисления приходится начинать заново, что приводит к большим затратам машинного времени. Эволюционный подход позволяет анализировать, дополнять и видоизменять популяцию альтернативных решений применительно к изменяющимся условиям. Для этого не требуется полный перебор. Другое преимущество ГА для решения задач состоит в способности быстрой генерации достаточно хороших решений [ - ]. Рассмотрим некоторые особенности выполнения этих этапов. На первом этапе решается следующая задача: необходимо выбрать такое формальное представление решения задачи, т. Иначе говоря, необходимо определить морфологическую и генетическую структуру особи. Математически доказано, что не существует идеальной структуры представления решения [], так что для создания хорошей структуры требуется анализ предметной области, перебор и эвристические подходы. Возможный вариант представления должен позволять проведение различных перестановок в альтернативных решениях. Па втором этапе производится выбор оператора (или операторов) для формирования новых альтернативных решений. Существует огромное число таких операторов. Следует отметить, что существуют два основных типа размножения: половое и бесполое [6, ]. При половом размножении фрагменты строк кодов исходных решений комбинируются, в результате чего конструируется одно или несколько новых решений. При бесполом размножении потомок формируется путем копирования строки кодов исходного решения с незначительными изменениями значений некоторых генов. Модели этих типов размножения играют важную роль в генетических алгоритмах. В общем случае можно применить модели размножения, которые не существуют в природе. Например, использовать материал от трех или более родителей, проводить голосование при выборе родителей и т. Успех генетических алгоритмов во многом зависит от того, как взаимодействуют между собой структура, кодирующая решение, методы формирования новых решений (операторы) и способ определения целевой функции. На третьем этапе задаются правила выживания решений. Существует множество способов проведения селекции альтернативных решений. Простейшее правило - это «выживание сильнейших», согласно которому только лучшие решения с точки зрения заданной целевой функцией остаются, а все остальные устраняются. Такое правило часто оказывается малоэффективным при решении сложных технических проблем. На последнем предварительном этапе создается начальная популяция. При создании начальной популяции рекомендуется использовать знания о решаемой задаче. Отметим, что популяция обязательно является конечным множеством. В настоящее время методы генетического поиска и генетические алгоритмы в частности нашли широкое применение при решении различных оптимизационных задач. Генетические алгоритмы позволяют найти баланс между эффективностью поиска и качеством получаемых решений за счет «выживания сильнейших альтернативных решений», в неопределенных и нечетких условиях []. Это позволяет в некоторых случаях увеличить эффективность обработки данных, т. Эта особенность позволяет синтезировать новые квазиоптимальные решения на основе старых квазиоптимальных решений.