Содержание к диссертации
Введение
1. Проблемы, перспективы и анализ задач размещения при конструкторском проектировании 8
1.1. Анализ задач размещения компонентов СБИС 8
1.2. Постановка задачи размещения 20
1.3. Выводы 35
2. Использование квантового и генетического поиска для решения задач размещения 36
2.1. Модель задачи размещения 36
2.2. Анализ квантового и генетического поиска при размещении элементов 44
2.3. Модифицированная архитектура генетического поиска для размещения элементов 61
2.4. Алгоритмы анализа квантовых алгоритмов при исследовании графовых моделей 68
2.5. Выводы 76
Размещения на основе моделирования отжига, квантового и генетического поиска 77
3.1. Модифицированный алгоритм размещения на основе моделирования отжига 77
3.3. Модифицированные генетические операторы для размещения 1 1 I
3.4. Выводы 119
4. Анализ результатов вычислительного эксперимента при размещении элементов 120
4.1. Экспериментальные исследования квантового и генетического алгоритма размещения 120
4.2. Анализ вычислительных экспериментов алгоритма размещения на основе моделирования отжига 130
4.3. Описание программного комплекса для размещения разногабаритных элементов 140
4.4 Выводы 148
Заключение 149
Список литературы , 150
Приложение 160
Акты использования и внедрения результатов работы
- Анализ задач размещения компонентов СБИС
- Анализ квантового и генетического поиска при размещении элементов
- Модифицированные генетические операторы для размещения
- Анализ вычислительных экспериментов алгоритма размещения на основе моделирования отжига
Введение к работе
Развитие современной науки и техники тесно связано с развитием САПР, чья роль во всех областях человеческой деятельности непрерывно возрастает. Проектирование все более сложных, требующих больших временных и людских ресурсов, объектов, невозможно без автоматизированного проектирования. При этом ЭВМ является и инструментом, и объектом проектирования, и, таким образом, автоматизация проектирования зависит от совершенствования вычислительной техники и ее элементной базы. В современных, высокопроизводительных ЭВМ элементной базой являются сверхбольшие и сверхскоростные интегральные схемы (СБИС и ССБИС).
Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики практически недоступны для САПР предыдущих поколений и достигаются лишь программами, использующими совершенные и сложные интегрированные комплексы и алгоритмы. Количественный рост сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли математического обеспечения САПР. Это позволяет в области синтеза топологии СБИС выйти па следующий уровень в программном обеспечении САПР. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и верификация, синтез топологии. Исходными для проектирования являются спецификация прибора и технические требования к нему. Спецификация определяет логическую цель проектирования, технические требования - физические ограничения. Логическое проектирование — это процесс создания структурного описания проектируемого устройства в соответствии с требованиями, предъявляемыми к его функционированию с последующей детализацией проекта по уровням. Синтез топологии является одним из важнейших этапов в общей проблеме проектирования СБИС. В этой связи разработка алгорит.мов проектирования топологии является актуальной для новых поколений радиоэлектронной и электронно-вычислительной аппаратуры. В работе рассмотрена одна из важных задач конструкторского проектирования СБИС - задача размещения. Она относится к классу NP (неопределенно распознаваемых за полиномиальное время), или является NP-полной, и для нее не известен алгоритм, растущий в полиномиальной степени. В этой связи разработка эффективных полиномиальных алгоритмов является актуальной и важной задачей.
Цель диссертационной работы состоит в разработке и исследовании интегрированных поисковых, квантовых и генетических алгоритмов размещении компонентов СБИС.
Достижение указанной цели предполагает решение следующих основных задач: построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства; разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области ЧИПа; построение архитектур бионического и квантового поиска ориентированных на задачи размещения графовых моделей компонентов СБИС; разработка интегрированных квантовых, генетических и алгоритмов моделирования отжига.
Для решения поставленных задач в диссертационной работе используются следующие методы: теория графов, множеств, алгоритмов и методология эволюционного моделирования и квантового поиска. Научная новизна работы заключается в решении задачи размещения компонентов СБИС, имеющей существенное значение в интеллектуальных САПР для синтеза топологии.
Разработана архитектура квантового и генетического поиска применительно к размещению компонентов СБИС. Построены новые модифицированные операторы квантового и генетического поиска, ориентированные на задачи размещения в САПР. Разработаны интегрированные квантовые, генетические и алгоритмы моделирования отжига, позволяющие получать множество локальных оптимумов при размещении.
Решение поставленных задач позволяет автору защищать следующие новые научные результаты: генетические алгоритмы совместного размещения на основе квантового, генетического поиска и моделирования отжига; модифицированные квантовые алгоритмы построения клик графа и паросочетаний, как строительных блоков интегрированных алгоритмов размещения; схемы квантового и генетического поиска, основанные на «жадных» стратегиях и эвристиках, позволяющие в отличие от существующих методов синтеза топологий находить не одно, а некоторое множество эффективных решений.
Практическая ценность результатов диссертационной работы определяется созданием программного комплекса алгоритмов размещения компонентов СБИС, позволяющих использовать разработанные математические модели, методы и эвристики, отвечающие конкретным задачам синтеза топологий. Разработана специальная программная среда для моделирования при решении задач размещения. Программы реализованы на языке C++ под WINDOWS. Проведенные результаты вычислительного эксперимента, показали преимущество комбинированных поисковых и генетических алгоритмов для решения задач размещения графовых моделей, по сравнению с существующими методами. Разработанные алгоритмы размещения позволяют получать не одно, а набор оптимальных, или квазиоптимальных результатов. Время получения лучших результатов размещения соответствует полиномиальному времени, которое требуют итерационные алгоритмы.
Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Таганрогского государственного радиотехнического университета (ТРТУ), по гранту Министерства образования и науки РФ, а также научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12353, 12388, 12380). Результаты этих работ внедрены и используются в учебном процессе в ТРТУ (г. Таганрог). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.
Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные САПР" (г.Геленджик, 1998г.- 2005г.), третьей и четвертой всероссийских научных конференциях молодых ученых «Новые информационные технологии» (г.Таганрог, 2000г., 2001г.). По материалам диссертационной работы опубликовано 14 печатных работ, материалы вошли в три отчета по НИР.
Структура и объем диссертационной работы. Диссертация состоит из введения, четырех разделов, заключения, изложенных на 149 страницах, 72 рисунков, 10 таблиц, списка литературы из 126 наименований и приложения.
Во ведении обоснована актуальность диссертационной работы, приведена цель работы, основные научные положения выносимые на защиту, приведены сведения о практической ценности, реализации и внедрения, апробации диссертационной работы, дано краткое содержание основных разделов диссертации.
В нервом разделе рассмотрены модели компонентов СБИС. Отмечено, что при решении задач размещения компонентов СБИС необходимо использовать модели, учитывающие предварительные знания о решаемых задачах. Приведена постановка задачи размещения коммутационных схем компонентов СБИС. Рассмотрена классификация методов размещения графовых и гиперграфовых моделей с оптимизацией заданных критериев качества. Проведен краткий обзор существующих методов размешени.
Отмечено, что перспективными исследованиями являются разработка совместных квантовых, генетических и алгоритмов моделирования отжига, позволяющих решать проблемы предварительной сходимости и получать наборы квазиоптимальных и оптимальных решений.
Во втором разделе приведена классификация оптимизационных задач размещения компонентов СБИС. Рассмотрен модифицированный нечеткий алгоритм построения математических моделей задач размещения. Проанализированы различные методы поиска при решении задач размещения. Построены квантовые и генетические алгоритмы размещения. Временная сложность этих алгоритмов не выходит за пределы полиномиальной области. Сформулированы стратегии комбинированного поиска решений при размещении. Разработаны новые архитектуры' квантового и генетического поиска. Это дает возможность распараллеливать процесс оптимизации, эффективно управлять поиском, получать оптимальные и квазиоптимальные решения в задачах размещения.
В третьем разделе разработаны модифицированные операторы отжига, кроссинговера, мутации, инверсии, транслокации, сегрегации, удаления и вставки, основанные на методах квантового и генетического, имеющие полиномиальную временную сложность. Разработаны модифицированные алгоритмы квантового поиска для определения паросочетапий и клик графа, позволяющие решать задачи размещения компонентов СБИС. Временная сложность алгоритмов (ВСА) ориентировочно равна 0(n logn), где п - число элементов СБИС.
В четвертом разделе описаны результаты вычислительного эксперимента при анализе разработанных алгоритмов. Произведено сравнение разработанных алгоритмов с существующими аналогами. Описаны структурные схемы алгоритмов, даны компоненты разработанного программного обеспечения.
В заключении изложены основные выводы и результаты диссертационной работы.
В приложении даны копии актов внедрения.
Анализ задач размещения компонентов СБИС
Этап автоматизированного конструкторского проектирования компонентов СБИС является одним из важнейших в общей проблеме разработки узлов РЭА и ЭВА с помощью САПР. На этом этапе происходит выбор оптимальных конструктивных параметров компонентов, определяющих расположение с учетом заданных конструкторско-технологических ограничений и требований оптимизации задержек сигнала электромагнитной и тепловой совместимости. Все это позволяет обеспечивать высокую функциональную работоспособность спроектированных систем. Оптимальный выбор характеристик при синтезе конструкций является затруднительным в связи со сложной системой начальных условий и ограничений, а также в связи с экспоненциальным ростом сложности алгоритмов. Поэтому при решении задач конструкторского синтеза топологий для снижения размерности выполняются различные способы декомпозиции задачи на более простые подзадачи [1-20]. Функциональные характеристики каждого компонента СБИС можно условно описать системой коммутационных, электрических, конструктивных и внешних параметров [5-8]. F=F(A,B,C,D) (1.1)
Система А коммутационных параметров определяет число элементов и соединений компонентов СБИС. Система В электрических параметров в основном не зависит от коммутационных параметров. Здесь необходимо решать проблемы задержки, электрической совместимости, емкостного баланса и т.п. Система С конструктивных параметров определяет размеры компонентов, внутренних элементов, толщину и длину соединений. Система D определяется ЛПР (лицом, принимающим решение), т.е. конструктором и представляет собой набор расплывчатых множеств и инструкций [21-23]. В первом делается попытка максимального сокращения объема перебора при поиске оптимальных и квазиоптимальных решений. Во втором строятся эвристики нахождения локального решения за приемлемое время (детерминированные эвристические алгоритмы). К сожалению, данные подходы вследствие применения жестких правил поиска не способны преодолевать барьеры локальных оптимумов .
Для большинства задач размещения применимы комбинированные алгоритмы случайного и направленного поиска. К ним можно отнести метод моделирования отжига, метод силовой релаксации, метод групповых, парных перестановок и т.д. [21,24,25].
Комплексное решение задачи синтеза топологий при совместном разбиении, размещении и трассировки соединений может вызвать ухудшение качественных показателей. Особенно это касается этапов размещения и планирования кристаллов. В этой связи задачу оптимального или квазиоптимального размещения компонентов СБИС предлагается разбивать на этапы или подэтапы, которые должны реализовываться параллельными, последовательными или комплексными методами. Эффективным методом уменьшения размерности задачи размещения является выбор нечетких подсистем топологических параметров. Это целесообразно для получения первоначального решения, которое может стать как бы прообразом будущих популяций альтернативных решений. Использование топологических параметров позволяет в первую очередь анализировать взаимное расположение элементов в топологическом пространстве. Конкретизацию размещения элементов, заключающуюся в определении их физических координат на поле кристалла, предлагается выполнять на заключительном этапе размещения.
Размещением компонентов СБИС на монтажпо-коммутационном пространстве (поле кристалла) называется процесс распределения элементов в одном конструктивном уровне в соответствии с заданными критериями. Основным комплексным критерием является мера оценки электромагнитотешювой совместимости при размещении компонентов СНИС [14,21]. Данный критерий определяет область допустимых размещений элементов на плоскости, на которой могут быть заданы другие критерии. Такими критериями могут быть: длина критических связей, число изгибов, толщина проводящих соединений, число конструктивно законченных блоков, длина задержки сигнала, число соединений между конструктивными блоками, количество связей внутри блоков, функциональная полнота блоков. Распространенным критерием при размещении является суммарная длина внутренних соединений. Выполнение этого критерия обеспечивает минимизацию задержки сигнала, эффективную трассировку схемы, повышение надежности монтажа и т. д. В связи с этим анализ и исследование методов размещения компонентов СБИС и блоков ЭВА проводится, в основном, на основе критерия суммарной длины соединений, суммарного числа изгибов проводников и суммарного числа пересечений связей [8,11,12,14,16,18-25].
Известно, что алгоритмизация задач размещения производится путем перехода построения математических моделей схем соединений и монтажного пространства. Для этой цели используются четкие и нечеткие множества, графы, гиперграфы и их матричные, фреймовые и списковые эквиваленты [15-26].
Анализ квантового и генетического поиска при размещении элементов
При решении задач САПР эффективно используются стратегии, концепции, методы, механизмы эволюционного моделирования и бионического поиска [89-95]. Бионика — решение инженерных и технических задач на основе изучения структуры и жизнедеятельности живых организмов. Бионический поиск с точки зрения преобразования информации при решении задач размещения - это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое. В основе ГА лежит случайный, направленный или комбинированный поиск. Такие алгоритмы эффективно используют информацию, накопленную в процессе эволюции, для получения квазиоптимальных и оптимальных решений [80-91].
Основной трудностью решения задач компоновки в САПР с большим количеством локальных оптимумов является предварительная сходимость алгоритмов. Другими словами, попадание решения в один, далеко не самый лучший, локальный оптимум.
Различные методы селекции и их модификации как раз и позволяют в некоторых случаях решать проблему предварительной сходимости алгоритмов. Следует отметить, что исследователи ГА при решении комбинаторно-логических задач САПР все более склоняются к мысли применять комбинированные методы селекции с использованием предварительных знаний о решаемых задачах и предварительных результатах [86-90]. Выделяют три особенности алгоритма эволюции: каждая новая популяция состоит только из «жизнеспособных» хромосом; каждая новая популяция «лучше» (в смысле ЦФ) предыдущей; в процессе эволюции последующая популяция зависит только от предыдущей.
Эволюционный поиск основан на схеме эволюционной стратегии (ЭС). В [83-87], основная схема ЭС описывается следующим образом. Индивидуум состоящий из произвольного элемента мутирует, добавлением нормально распределенного случайного вектора. Новая точка выбирается если она лучше или эквивалентна предыдущей, иначе предыдущая точка переходит к следующей итерации. Решение о выборе основано на простом сравнении значений целевой функции предыдущих и новых точек. При условии, что целевая функция должна быть минимизирована, простая ЭС, начинается в некоторой точке.
В этой схеме, общее количество индивидуумов составляет популяцию Р. Далее (3 новых индивидуумов выбраны среди первоначальных m индивидуумов, с вероятностью р7Р. Новая совокупность индивидуумов подвергается процессу мутации, а также процессу рекомбинации, являющимся новым и важным свойством. В процессе рекомбинации, содержимое двух индивидуумов объединяется в многоточечном пересечении.
Моделирование эволюции в задачах САПР может осуществляться в результате взаимодействия трех основных факторов, а именно изменчивости, наследственности и естественного отбора. В [666,70,79,83,89] дана классификация существующих форм отбора: методический, бессознательный, естественный и искусственный отбор. Эти формы отбора тесно связаны с процессом селекции.
Для эффективного использования положительных свойств существующих алгоритмов в [66-91] предложено использовать ГА и эвристику предварительной обработки (препроцессинга) для обеспечения хороших начальных решений.
Использование идей квантовой механики позволяет при поиске решений в задачах САПР использовать подходы параллельных вычислений. Согласно известному принципу суперпозиции система (графовая модель) может, как бы одновременно находиться во всех возможных состояниях. Производя над одним состоянием графа произвольные действия, мы производим это одновременно над заданным множеством состояний [89,90,91]. При решении оптимизационных задач на графах предлагается новая технология па основе совместного бионического и квантового поиска. Описаны новые архитектуры и принципы такого поиска. Это позволяет расширить область поиска решений без увеличения времени работы и сократить преждевременную сходимость алгоритмов, повысить эффективность и качество получаемых решений.
В последнее время появились новые подходы решения NP - полных проблем, основанные на методах квантового поиска [72,92-98]. Квантовый поиск анализирует неструктурированные проблемы, которым в общем виде формулируются следующим образом [94-98]. Задана функция f(x), аргументы х - целые числа х = 1,2,....,N, причем f(x) принимает значение ноль во всех случаях, кроме x=w. Необходимо найти значение w, используя наименьшее число запросов к f(x). Задачи такого типа при небольшом х 100 решаются на основе полного перебора (исчерпывающего поиска) или методом проб и ошибок.
Идею и структуру квантового алгоритма предложил Л.Гровер [94,95]. Согласно [94] при решении неструктурированной проблемы поиска существует "оракул", определяющий является ли рассматриваемое решение искомым. Л.Гровер рассматривает N целых чисел индекса х=1,2,..., N как набор ортогональных векторов х = 1,2, ... к в N - размерном пространстве Хильберта. Этот шаг алгоритма как бы на языке вычисления кванта, ставит в соответствие каждому возможному индексу уникальный собственный вектор. Первоначально готовится пространство,
Модифицированные генетические операторы для размещения
Преимуществом генетических и эволюционных алгоритмов от рассмотренных является тот факт, что они могут работать в любом классе задач САПР. Здесь важно правильно представить постановку задачи в закодированной форме, чтобы полнее отобразить поисковое пространство ЦФ. Кратко рассмотрим основные операторы (ГО и КО) генетических и квантовых алгоритмов.
Селекция- это процесс, посредством которого хромосомы, имеющие более высокое функциональное значение, получают большую возможность для репродукции, чем "слабые" хромосомы. Элементы, выбранные для селекции, обмениваются генетическим материалом, создавая аналогичные или различные потомки. Существует несколько основных видов селекции [66,101].
Основным итогом анализа ГА стало выбор триады генетических операторов (ГО) "кроссинговер - мутация - инверсия". Воздействуя с некоторой вероятностью на генотипы родительских особей, каждый из них, с одной стороны, обеспечивает передачу потомству важных признаков, а с другой - поддерживает на протяжении эволюционно значимого периода достаточно высокий уровень его изменчивости. Определение в потомстве новых, отличных от родительских, фенотипических (совокупность всех внешних и внутренних признаков) признаков открывает для популяции дополнительные возможности для адаптации.
В эволюционном моделировании под к р о с с и н г о в е р о м понимают оператор, который формирует хромосому потомка, собирая ее из фрагментов родительских хромосом [66, 102]. Основная функция оператора кроссинговера (ОК) - создавать хромосомы потомков на основе различного скрещивания родителей.
Мутация - генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Таким образом, мутации представляют собой изменения генов, хромосом.
Двухточечный ОМ. Две точки мутации выбираются случайно, а затем ген, соответствующий второй точке мутации, размещается в позицию перед геном, соответствующим первой точке мутации. Например: Р3 : 5 3 9 I 1 4 8 0 2 6 7 до ОМ, Рп :5390148267 после ОМ.
Важным понятием в ОМ является шкала мутации, которая определяет, какой процент от общего числа генов в популяции мутирует в каждой генерации. Это число находится в пределах Рт = 0.1 и ниже [2]. Оператор инверсии (ОИ) - это поворот участка гена или хромосомы на 180 градусов. Одноточечный ОИ. Случайным образом определяется точка инверсии и элементы по обе стороны от этой точки инвертируются.
Многоточечный ОИ. Для задач оптимизации вероятность ОИ принимают равной в пределах/1/= (0.05 -0.01) [66,102].
Иногда, говоря о триаде генетических операторов, подчеркивают способность кроссинговера и инверсии к глобальному поиску, в то время как мутацию отождествляют со средствами локальной настройки решения.
Оператор транслокации (ОТ) - перенос части одной хромосомы на другую. В процессе транслокации случайным образом производится один разрыв в каждой хромосоме. При формировании потомка Р/2 берется левая часть до разрыва из родителя Р, и инверсия правой части до разрыва из Р2 . При создании Р21 берется левая часть Р2 и инверсия правой части Р;, Например: Pi А В С D Е F Р2 : G К Н I J Q JJl : ABQJ IH P21 : G К F E D С. Приведем пример оператора сегрегации (ОС). Пусть имеется популяция Р, состоящая из четырех хромосом: Л= 123 4,/ =2 43 \,Р3= 3 1 42, =43 2 1.
Тогда потомка Р12 можно сформировать случайным образом, взяв первый элемент из Р/, второй из Р2, третий из Р3 и четвертый из Р4. При этом должны быть отброшены повторяющиеся решения, или решения, содержащие одинаковые элементы. Так, вариант Р12 =4121 должен быть отброшен, а вариант Р2\ = 2143 является "легальным". Очевидно, что оператор селекции можно реализовать различными способами в зависимости от выборки генов из хромосом Pj- Р4. Кроме описанных генетических операторов существуют и некоторые другие, например оператор удаления и т.п.
Опишем принцип кодирования-декодирования хромосом на конкретном примере размещения. Пусть имеется начальное размещение, представленное на рис. 3.1. Данному размещению соответствует хромосома решения Р/: 12 3 4 5. Значения генов в хромосоме - это номера вершин графовой модели, которые необходимо разместить в графе-решетке (координатная сетка) с требуемым критерием оптимизации.
Анализ вычислительных экспериментов алгоритма размещения на основе моделирования отжига
Разработанная программа, решающая задачу размещения методом моделирования отжига, условно состоит из трех основных частей:
1) ввод исходных данных и перевод их из вида, понятного пользователю (графа размещения, визуально отраженный на экране монитора), во внутренний формат (матрицу смежности);
2) выполнение алгоритма и вывод результатов на экран в виде отображения начального значения целевой функции, конечного значения целевой функции и графического отображения решения в виде графа на коммутационном поле, а также графика зависимости качества решения от температуры;
3) проведение экспериментальных исследований, целью которых является определение оптимальных параметров работы алгоритма (начальная температура, конечная температура, шаг изменения температуры, размер серии при данной температуре и т. д.) и исследование временной сложности алгоритма.
Исходными данными для данной программы являются размеры коммутационного поля и граф начального размещения. После создания начального размещения происходит разблокировка пункта меню «Запуск» и алгоритм готов к выполнению. Перед запуском алгоритма на выполнение необходимо задать параметры работы алгоритма, к которым относятся начальная температура, конечная температура, шаг изменения температуры, размер серии при данной температуре и т. д.
Для проведения экспериментальных исследований программой предусмотрено создание файла статистики «report.txt» на жестком диске, в котором указываются исходные данные решаемой задачи размещения (размеры коммутационного поля и сведения о графе начального размещения) и параметры алгоритма.
Опции позволяют настраивать параметры алгоритма такие, как (начальная температура, конечная температура, размер серии при данной температуре, шаг изменения температуры). Диалоговое окно вид, представленный на рис. 4.7.
График зависимости качества размещения от температуры показан па рис. 4.8.
На панели инструментов находятся пиктограммы: создание нового размещения; открытие уже имеющегося на диске размещения; сохранение созданного размещения; изменение имени файла с размещением; выход из программы; сведения о разработчике и версии программы.
Объектами исследований в работе являются параметры работы алгоритма размещения методом моделирования отжига, к которым относятся начальная температура, конечная температура, шаг изменения температуры, размер серии при данной температуре. Чем дольше работает алгоритм, в основе которого лежит метод моделирования отжига, тем больше решений он оценивает, тем выше вероятность нахождения оптимального решения.
Экспериментальные исследования алгоритма состоят из следующих этапов:
1) Проведение серии экспериментов для исследования влияния параметров алгоритма (начальная температура, конечная температура, шаг изменения температуры, размер серии при данной температуре) на получаемые решения;
2) Обработка экспериментальных данных и выявление оптимального режима работы алгоритма.
Обработка полученных результатов заключается в определении следующих характеристик:
Влияние размера начальной температуры на качество решения. На основе экспериментальных исследований подберем такие значения начальной температуры, которые приводят к наилучшему решению задачи размещения, т.е. достигается наименьшее значение целевой функции.
В таблице 4.8. приведены результаты экспериментальных исследований (значение начальной температуры Тнач., значение получаемой ЦФ, среднее значение ЦФ), полученные в результате проведения 3 испытаний для каждого значения температуры.
Постоянные параметры эксперимента следующие: конечная температура 0; размер серии при данной температуре 5; шаг изменения температуры 1.
Как видно из таблицы, близкое к оптимальному значение целевой функции получено при максимальной начальной температуре равной 1000. Близкое к оптимальному среднее значение целевой функции получено при температуре близкой к максимальной и составляющей 800..По приведенным в таблице данным построим график зависимости значения ЦФ от начальной температуры (рис 4.8).
Влияние размера конечной температуры па качество решения. На основе экспериментальных исследований подберем такие значения конечной температуры, которые приводят к наилучшему решению задачи размещения, т.е. достигается наименьшее значение целевой функции,
В таблице 4.9 приведены результаты экспериментальных исследований (значение конечной температуры Ткон., значение получаемой ЦФ, среднее значение ЦФ), полученные в результате проведения 3 испытаний для каждого значения температуры.
Постоянные параметры эксперимента: начальная температура 1000; размер серии при данной температуре 5; шаг изменения температуры 1.
Как видно из таблицы близкое к оптимальному значение целевой функции получено при минимальной конечной температуре равной 0. Близкое к оптимальному среднее значение целевой функции за серию экспериментов получено при температуре близкой к минимальной и составляющей 100.
