Курсовая работа: Программная реализация генетического алгоритма для задачи размещения элементов на кристалле

Содержание
Введение......................................................................................................................... 3
1. Теоретическая часть........................................................................................... 4
1.1. Основные определения................................................................................. 4
1.2. Принцип действия генетического алгоритма.......................................... 4
1.3. Способы кодирования................................................................................... 6
1.4. Оператор оценки (селекции)........................................................................ 6
1.5. Оператор кроссинговера (скрещивания).................................................. 8
1.6. Оператор мутации........................................................................................ 10
1.7. Преимущества и недостатки генетических алгоритмов..................... 11
1.8. Сравнение с другими алгоритмами размещения.................................. 11
1.8.1. Силовой алгоритм................................................................................... 11
1.8.2. Алгоритм отжига..................................................................................... 13
2. Практическая часть........................................................................................ 15
2.1. Ход работ программы................................................................................. 15
2.2. Выбор реализации основных операторов............................................... 22
2.2.1. Реализация оператора кроссинговера................................................. 23
2.2.2. Реализация оператора мутации............................................................ 25
2.2.3. Реализация оператора оценки............................................................... 27
2.3. Размещение.................................................................................................... 30
Заключение.................................................................................................................. 34
Список литературы.................................................................................................... 35









Введение
В наши дни в повседневной жизни мы постоянно используем различные электронные устройства, которые создаются на основе сверхбольших интегральных схем (СБИС). В таких схемах на кристалле размещают боле 10000 элементов.
С каждым годом повышается степень интеграции элементов при практически неизменной или уменьшающейся площади кристалла, что приводит к проблеме размещения элементов. Это является одной из фундаментальных задач физического проектирования, так как помогает определить структуру микросхемы. Также, качественное размещение может частично решить проблему трассировки.
Для решения этой задачи необходимо создавать новые, более эффективные алгоритмы, и дорабатывать и оптимизировать уже существующие.
Для решения проблемы размещения используются различные алгоритмы: силовой, алгоритм отжига, генетический алгоритм. Данные алгоритмы используют физические или биологический модели для решения задач размещения элементов на кристалле, что позволяет каждому разработчику подстроить и оптимизировать алгоритм под определенную задачу.
Для данного дипломного проекта выбрана тема "Программная реализация генетического алгоритма для задачи размещения элементов на кристалле".
Для достижения цели необходимо ре