Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 43
Текст из файла (страница 43)
Так как пространство D метризовано,то можно использовать понятие а-окрестности So(Xt) текущей точки поискаXk. Вместо перебора точек во всем пространстве D осуществляется перебортолько в Sa(Xt). Если F(X ) > F (Х^) для всех Х^ € So(Xt), то считается, что найден локальный минимум целевой функции в точке Хг В противном случае точку X , в которой достигается минимум F(X) в So(Xt), принимают в качественовой текущей точки поиска.Недостатком метода является его явно выраженная локальность — «застревание» в окрестностях локальных экстремумов. Повысить эффективностьпоиска можно с помощью метода оптимизации с запретами (tabu search).
Дляэтого в 8я(Х4) вводят запреты на попадание в некоторые точки. Обычно этозапреты на повторное исследование точек, пройденных на нескольких последних шагах оптимизации. Запрет распространяется и на лучшую точку Х^ предыдущего шага, которая может оказаться точкой локального минимума. Тогдана данном шаге перемещение происходит в лучшую незапрещенную точку Xt+1,несмотря на то что /r(X;t+]) > /*XXt). Тем самым появляется тенденция к выходу из области притяжения локального экстремума.Системы искусственного интеллектаВ теории интеллектуальных систем синтез реализуется с помощью экспертных системЭС = <БД,БЗ,И>,где БД — база данных, включающая сведения о базовых элементах; БЗ — базазнаний, содержащая правила конструирования вариантов структуры; И — ин-1824.4.
Методы структурного синтеза в системах автоматизированного проектированиятерпретатор, устанавливающий последовательность применения правил из базызнаний. Системы искусственного интеллекта основаны на знаниях, отделенных от процедурной части программ и представленных в одной из характерныхформ. Такими формами могут быть продукции, фреймы, семантические сети.Реально функционирующие в современных САПР системы с базами знанийчаще всего относятся к классу экспертных систем.Продукция представляет собой правило типа «если А, то 5», где А — условие, а В — действие или следствие, активизируемое при истинности А.
Продукционная база знаний содержит совокупность правил, описывающих определенную предметную область.Фрейм — структура данных, в которой в определенном порядке представлены сведения о свойствах описываемого объекта. Типичный вид фрейма:< имя фрейма; *, =/?,; х2 = р2; ... ; xN = pN; qv qv ..., qM >,где х — имя /-го атрибута; pi — его значение; q — ссылка на другой фрейм илинекоторую обслуживающую процедуру.
В качествеpt можно использовать имядругого (вложенного) фрейма, описывая тем самым иерархические структурыфреймов.Семантическая сеть — форма представления знаний в виде совокупностипонятий и явно выраженных отношений между ними в некоторой предметнойобласти. Семантическую сеть удобно изображать в виде графа, в котором вершины отображают понятия, а ребра или дуги — отношения между ними. Вкачестве вершин сети можно использовать фреймы или продукции.Экспертная система является типичной системой искусственного интеллекта, в которой база знаний содержит сведения, полученные от людей-экспертов в конкретной предметной области. Трудности формализации процедур структурного синтеза привели к популярности применения экспертных систем в САПР,поскольку в них вместо выполнения синтеза на базе формальных математических методов осуществляется синтез на основе опыта и неформальных рекомендаций, полученных от экспертов.Методы распространения ограниченийВо многих задачах структурного синтеза множество D допустимых вариантов, задаваемое ограничениями W(X) > 0 и (или) Z(X) = 0, включает сравнительно малое число элементов, и в качестве результатов синтеза принимаетсялюбой из этих вариантов.
Такое решение задачи часто выполняют с помощьюметода распространения ограничений (constraints propagation).Сущность этого метода заключается в сужении допустимых интерваловуправляемых переменных X с помощью учета (распространения) исходныхограничений на выходные параметры W и Z.Для пояснения метода рассмотрим простой пример. Пусть в задаче фигурируют триуправляемые целочисленные переменные х, у, z, заданы исходные интервалы допустимых значений этих переменных х е [1: 100], у е [1: 100], z e [10:100], а область Dопределена ограничениямиx+y>5z,(4.31)1834. Математическое обеспечение синтеза проектных решенийх>у+5.(4.32)Распространение ограничения (4.31) на интервал переменного z приводит к уменьшению его верхней границы, так как z < (хтх1+утгк)/5 = 40, а с учетом ограничения (4.32)- к его новой корректировке z < 39, поскольку jmax= 95, а также к увеличению нижнихграниц переменных х ну, так как решение неравенств х + у > 50 и (4.32) дает х>2В,у>22.Таким образом, получено сужение допустимой области х е [28:100],^ е [22:95],ze [10:39].Метод легко распространяется на задачи с нечисловыми параметрами.
Вэтом случае вместо сокращения числовых интервалов уменьшают мощностидопустимых подмножеств значений параметров.Одним из практических приложений метода распространения ограниченийявляется поиск допустимых вариантов в множестве синтезируемых структурпри ограничениях типа (4.29) на совместимость элементов структуры.Пример.
Рассмотрим фрагмент структуры, состоящий из трех компонентов А, ВиС,причем Л е {а,, а2, ау а4, а;}, В е {&,, Ь2, Ъу Ь4}, С е {с,, с2, с}}. Заданы списки допустимыхсочетаний компонентов в синтезируемой структуре:L1: а,, Ь{; ау Ъ^ а4,Ь2, а5, Ь3; о5, £4;L2: Ь}, с,; Ъу су й4, с,; Ь4, с2;L3:a 2 , с3;а3, с2;а4, С3;а5,с2.Сокращение первого списка выполняется путем поочередного выбора в нем а(, фиксации в L3 соответствующих значений ck, а затем в L2 сопряженных с ck значений b'. Еслив L1 имеется элемент a,, bj, то он сохраняется в сокращенном списке, остальные сочетания с а из L1 удаляются. В нашем примере, поскольку значения я, в L3 нет, то сочетаниеа,, и, недопустимо и из L1 удаляется.
Далее для символа аг фиксируем в L3 значение суему в L2 соответствует только значение Ьу Поэтому а2, Ь, -также недопустимое сочетание. Обработав подобным образом все списки, получаем результат распространенияограничений в виде LI: a5,i>4;L2: 64,c2;L3: a},c2.Следовательно, решение состоит из единственной допустимой структуры, включающей компоненты ау 64, с3.В общем случае сокращение списков выполняется в итерационном процессе до совпадения их содержимого на двух последних итерациях.На базе метода распространения ограничений компанией ILOG создан программный комплекс оптимизации и синтеза проектных решений, состоящий изподсистем Solver, Configurator, Scheduler и др.Эволюционные методыЭволюционные методы (ЭМ) предназначены для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуацийи итерационном приближении к искомому состоянию систем.В отличие от точных методов математического программирования ЭМ позволяют находить решения, близкие к оптимальным, за приемлемое время, а вотличие от известных эвристических методов оптимизации характеризуютсясущественно меньшей зависимостью от особенностей приложения (т.
е. болееуниверсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оптимальному решению. Универсальность ЭМ определяется так1844 4 Методы структурного синтеза в системах автоматизированного проектированияже применимостью к задачам с неметризуемым пространством управляемыхпеременных (т. е. среди управляемых переменных могут быть и лингвистические).Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы.
Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.Свойства объектов представлены значениями параметров, объединяемыми в запись, называемую в ЭМ хромосомой. В ГА оперируют хромосомами,относящимися к множеству объектов — популяции. Имитация генетическихпринципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшениюзначений целевой функции (функции полезности) от поколения к поколению.Среди ЭМ находят применение также методы, которые в отличие от ГАоперируют не множеством хромосом, а единственной хромосомой.
Так, методдискретного локального поиска (его англоязычное название hillclimbing) основан на случайном изменении отдельных параметров (т. е. значений полей взаписи или, другими словами, значений генов в хромосоме). Такие измененияназывают мутациями. После очередной мутации оценивают значение функции полезности F (fitness function) и результат мутации сохраняется в хромосоме, только если F улучшилась. В другом ЭМ под названием «Моделирование отжига» (Simulated Annealing) результат мутации сохраняется с некоторойвероятностью, зависящей от полученного значения F.Постановка задачи поиска оптимальных решенийс помощью генетических алгоритмовДля применения генетических алгоритмов необходимо:1) выделить совокупность свойств объекта, характеризуемых внутреннимипараметрами и влияющих на его полезность, т.
е. выделить множество управляемых параметров X = (г,, х2, ..., хп); среди * могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин(enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;2) сформулировать количественную оценку полезности вариантов объекта— функцию полезности F. Если в исходном виде задача многокритериальна, тотакая формулировка означает выбор скалярного (обобщенного) критерия;3) разработать математическую модель объекта, представляющую собойалгоритм вычисления F для заданного вектора X;4) представить вектор X в форме хромосомы — записи следующего вида:х\Х2XT,хп1854. Математическое обеспечение синтеза проектных решенийВ генетических алгоритмах используется такая терминология:ген — управляемый параметр xt;аллель — значение гена;локус (позиция) — позиция, занимаемая геном в хромосоме;генотип — экземпляр хромосомы, генотип представляет собой совокупность внутренних параметров проектируемого с помощью алгоритма объекта;генофонд — множество всех возможных генотипов;функция полезности (приспособленности) F — целевая функция;фенотип — совокупность генотипа и соответствующего значения F, подфенотипом часто понимают совокупность выходных параметров синтезируемого с помощью ГА объекта.Простой генетический алгоритмВычислительный процесс начинается с генерации исходного поколения —множества, включающего N хромосом (N- размер популяции).
Генерация выполняется случайным выбором аллелей каждого гена.Далее организуется циклический процесс смены поколений:for (&=0; k<G;{for(j=0;j<N;j++){Выбор родительской пары хромосом;Кроссовер;Мутации;Оценка функции полезности F потомков;Селекция;}Замена текущего поколения новым;Для каждого витка внешнего цикла генетического алгоритма выполняетсявнутренний цикл, на котором формируются экземпляры нового (следующего затекущим) поколения. Во внутреннем цикле повторяются операторы выборародителей, кроссовера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение.Рассмотрим алгоритмы выполнения операторов в простом генетическомалгоритме.Выбор родителей. Этот оператор имитирует естественный отбор, еслиотбор в родительскую пару хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F требуется минимизировать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
