Структурное моделирование в классе задач о назначении и исследование генетического метода решения

• Автор: Минаков, Сергей Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Воронеж
• Количество страниц: 122 с. : ил.

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

1. МОДЕЛИРОВАНИЕ СТРУКТУР В ЗАДАЧАХ НАЗНАЧЕНИЯ

1.1. Постановка задачи о назначении как задачи структурного моделирования.

1.2. Анализ частных случаев формализованных постановок задач

1.2.1. Транспортная задача

1.2.2. Задача о размещении и раскрое

1.2.3. Двухуровневая задача о назначении

1.2.4. Конечные автоматы

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.2. Синтез и исследование алгоритма решения квадратичной задачи о назначениях.
3.3. Преимущества и недостатки метода.
4. ПРИМЕРЫ РЕАЛИЗАЦИИ ЗАДАЧ СТРУКТУРНОГО МОДЕЛИРОВАНИЯ
4.1. Задача о раскрое с произвольным видом границ.
4.2. Задача составления расписания занятий
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Поэтому вводится понятие показателя сложности структуры. Каждому отношению между элементами на множестве сопоставляется булевая матрица. Переменной в математической модели также является многомерная булевая матрица. Задается целевая функцию задачи. Она учитывает матрицу отношений п взаимозависимость элементов. Поэтому в целевой функции проверяются поэлементно назначения из каждого множества, если отношения соблюдаются, то произведение равняется 1, в противном случае - 0. Таким образом, целевая функция стремиться к максимуму, чтобы увеличить количество выполненных отношений. Из целевой функции и ограничений видно, что квадратичная задача о назначении является частным случаем предлагаемой модели. Полученная математическая модель интерпретируется на графах как задача поиска наибольшего клика. Но при больших размерностях задач, требуется поиск решения за приемлемое время, что не могут обеспечивать алгоритмы, реализованные на графах. Также метод ветвей и границ, различные способы линеаризации целевой функции вызывают ряд сложностей при реализации вычислительной схемы. Итак, во второй главе, построена общая модель задач о структурном назначении. В третьей главе предлагается генетический алгоритм и исследование его эффективности. Задается функция кроссовера скрещивания двух индивидуумов. Скрещивание происходит нохромосомно, т. Т.к. X определяется позицией ненулевого гена. Чтобы приблизить генетический алгоритм к более реальному биологическому процессу, в кроссовере используется функция рандомизации. Работа операции кроссовера заключается в последовательном скрещивании позиций ненулевых генов хромосом индивидуумов. При вычислении новой хромосомы необходимо учитывать ограничения модели, т. Для соблюдения этого ограничения, после вычисления позиции единичного гена, достаточно корректировать ее сдвигая поочередно вправо и влево. Данная коррекция позиции называется случайной Л/ - мутацией хромосомы. Согласно введенного понятия мутации последняя хромосома индивидуума будет предопределяется предыдущими. Доказано утверждение, что предлагаемый алгоритм представим в каноническом виде. Канонический вид генетического алгоритма оперирует двоичными векторами-хромосомами, в нем используется одноточечный кроссовер, эффективность канонического вида алгоритма доказана в теореме о шимах Д. Холлапдом в . Численные эксперименты тестирования предлагаемого генетического алгоритма подтверждают достоверность теоретических заключений. В четвертой главе рассматривается разработанный в рамках специальности программный комплекс, состоящий из нескольких подсистем. Всероссийском научно-техническом информационном центре. Задачи о раскрое и составлении расписаний рассматриваются как примеры задач структурного моделирования. В задаче о раскрое предлагается способ описания произвольных нелинейных форм изделий и заготовок. Согласно материалу изделия и точности, которую необходимо обеспечить, на заготовки изделия наносится сетка требуемого размера ячейки. На множествах элементов сетки задаются отношения представимые булевыми матрицами. Целевая функция максимизирует количество корректно назначенных ячеек, т. Т.к. В результате получается частный случай квадратичной задачи о назначении с единичными коэффициентами в целевой функции. В приложениях приводятся результаты вычислительных экспериментов генетического алгоритма для квадратичной задачи о назначении. В процессе тестирования генетический алгоритм показал хорошие результаты за приемлемое время. Результаты вычислений оформлены в виде соответствующих графиков и таблиц. Проведен теоретико-множественный анализ задач, обеспечивший унифицированный подход к построению математических моделей из класса задача о назначении. Разработан метод структурного моделирования для построения моделей на основе введения отношений на множествах обеспечивающий формализацию широкого класса задач о назначении. Проведен анализ известных подходов и методов решения из класса задач о назначении, что обосновало применение генетического алгоритма при условиях большой размерности.