Основы САПР (CAD,CAM,CAE) - (Кунву Ли)(2004) (951262), страница 57
Текст из файла (страница 57)
Если иа листе имеются дефекты, эти дефекты должны исключаться из полезной плошади в процессе компоновки. Таким образом, функция стоимости может быть записана в следующем виде: Г(5) = оптходьг+ то к перекрьилие. Здесь 5 — текушая конфигурация компоновки, отходы — количество отходов ';.': с одного листа (или листов), то есть разность площади исходного листа и площа::-' ди уместившихся иа ием деталей. Перекрытие — суммариая плоШадь перекры';, ваюшихся частей деталей, а ю — весовой коэффициент. В процессе оптимизации ",.'. перекрытия ие запрещаются, ио большой весовой коэффициент исключает их в т конечной конфигурации.
Заметьте, что здесь мы, по сути, используем внутрениюю штрафную функцию из раздела 9.2. ,;!., Конфигурация 5', соседняя с текущей конфигурацией 5, может быть построена '„.",.;:: иебольшим возмущением текушей конфигурации. Например, можно случайным ':;:.. образом выбрать одну деталь из всех размещеииых ва листе и немного изменить ее ',"г положение и ориентацию. Изменение коифигурацити с 5 иа 5' называется пере.';.гмешеиием и выполняется в соответствии с алгоритмом Метрополиса (листииг 9.2), ,,:.,Результаты размещения деталей иа стальном листе для последовательного их из.:-".готовлеиия демонстрирует рис. 9.9.
Примеры размещения 36 выкроек иа отрезе ,:::,постояииой ширииы и иа отрезе неправильной формтз с впутреииим дефектом ; Приведены иа рис. 9.10 и рис. 9.11. Дефектная область показана иа рис. 9.11 черт'мым цветом, в данном случае это тонкая вертикальная полоска.
Дефекты такого - хипа часто возникают при отрезаиии заготовок для пошива одежды из кожи. Доля отходов = 2В,4% Рис. 9.9. Оптимальное размещение деталей для последовательной вырубки я Рно. 9.10. Размещение Зб выкроек на прямоугольном отрезе $З»В. 9,11. Размещение 36 выкровк на отрезе неправильной формы о внутренним дефектом ',.;:; ~-,'$. Тенатические алгоритмы ческиии аазоритмами (йеяейс а[йопйтз) называется группа адаптивных в, которые могут использоваться для решеиия задач поиска и оптимизави происходят от тех же основ, что и естественная эволюция и генетика.
ляции живых существ развиваются в течение миоп1х поколений в соответс принципами естественного отбора и «выживашия наиболее приспособх». Имитируя этот процесс, геиегические алгоритмы способны решать ре:;;";4Дй[зые задачи, при условии, что те будут правильно закодированы [131. ~ф геиетических алгоритмов в их устойчивости и в способности решать задаф~~~ймых разных типов, в том числе и трудноразрешимые другими методами. :,'~~$к генетические алгоритмы ие обязательно находят глобально-оптимальное ~агнце, оии обычно «досгаточио быстров находят «достаточио хорошие» реше- .4:,~р~;.;:;Разумеется, специализированные методы„ориеитироваииые на конкретные :.',-.;~йачи, по сравнению с генетическими алгоритмами почти иаверияка дадут луч";.":-:1[Е«Ч1н СКОрОСть И тОЧНОСтЬ КОНЕЧНОГО рЕЗуЛЬтата.
ПрЕВОСХОдетВО ГЕНЕТИЧЕСКИХ ~!.$~6фитмов проявляется в таких областях, где специализироваиных методов не А:;"'4~[цествует. Однако даже имеющиеся методы можно в некоторых случаях усо-'::,",' ~йфаеиствовать„«скрестив» их с генетическими алгоритмами [5б]. 9сиовиые принципы генетических алгоритмов были заложены Холлапдом [711, 'яы посвяшеио достаточно много трудов. Эти алгоритмы имитируют то, чем обу"' еьяовливается эволюция в живых популяциях.
В природе выживают те, кто луч;ше приспособлен к конкуренции за ограниченные 1жсурсы, поэтому адаптация к и»меияюшейся конкурентной среде принципиально вюкна для выживания иидпвидуумов любого вида. Уникальные особенности индивидуума определяют его жизиеспособиость, но саьщ они, в свою очередь, определяются генами иидиви'-'- : дуума. Каждой особенности сопоставляется элемент наследственной ииформа;:'-' .ции — ген. Наборы генов, определяющих особенности организма, объединяются 'в хромосомы. Процесс воспроизводства создает разнообразие в гегюфоиде, а иачииается оио с рекомбииации хромосом родительских особей в момент объедииеиия их половых клеток. Из исходных комбинаций генов создаются новые, в результате чего получается новый генотип. Происходит обмен генами между хромосомами, что.джт хромосомы с новыми свойствами. Этот процесс называется кроссоеером (стозгооег).
Таким. образом осуществляется поиск наиболее правильиой комбинации генов, по которой был бы построен более совершевиый организм. Отбор и кроссовер обеспечивают постоянную эволюцию генотипа и приводят к рождеиию организмов, лучше приспособленных к выживанию. В начале 70-х гг. Холланд предложил обозначать термином «геиетические алгоритмы» программы, имитирующие природный эволюционный процесс. Генетические алгоритмы работают с популяцией потенциальных решений задачи оптимизации (или поиска). Решения представляются в закодированном виде, подобно тому как в генетическом материале кодируется информация об особенностях иидиви- 1:-'' дуума.
В генетических алгоритмах Холланда решения кодировались в виде по":,!::::. следовательиостей битов двоичного алфавита. Как и в природе, механизмы отбора обеспечивали выживание наиболее совершенных решений. Каждому решеиию ::.;": сопоставляется определеииое значение «приспособлеииости», отражающее каче:„:-' 'ство данного решения по сравиеиию с другими решеииями той же популяш1и.
"!- Чем больше значение приспособлеиности, тем больше шансы иа вьокиваиие и воспроизводство, и тем больший вклад вносит данный индивидуум в последую- '::~:, а(ее поколение. Рекомбииация геиетического материала в генетических апгорит',;:, ашк имитируется механизмом кроссовера, осуществляющим обмен участками '-'::,''".строк. Дополвительиая операция, называемая мутацией, вызывает споралические случайиые изменения битов строк. Мутация тоже существует в природе, ",',:::, Зде оиа обеспечивает восстановление утраченного генетического материала [561. '; 9.%.1. Основные принципы В литературе генетический алгоритм Холланда обычно называется простым ге;-', 'уетическим алгоритмам (к[гор[с йелебс о[йонгйт — ЮА).
В основе 5ОА лежит ;;.'.;., з)рпуляция двоичных строк. Каждая такая строка, состоящая из нулей и единиц, ,кодирует решение задачи оптимизации. По сути, оиа эквивалентна коифигурагцпг в методе модельиой закалки. Алгоритм начинает работу с определенного коли- ~ '.'чества строк, которые называются популяцией первого поколения. При помощи ' .
'.Геиетических операторов (мутации и кроссовера) алгоритм создает следующее .;"„':,'цоколеиие из строк текущей популяции. Преимушеспю в воспроизводстве име":,:,::ют более совершеииые строки, так что в следующем поколении преобладает их ! '"«потомство».
Цикл воспроизводства повторяется до тех пор, пока ие выполнится ':,:;; задаииый критерий завершения. Общую схему генетического алгоритма демон'.: .стрирует рис. 9.12. Подробное описаиие важных составляющих этой схемы дает,.:: ся в последующих разделах. 1чеханизи кгщирования Структура генетического алгоритма во многом определяется механизмом кодиРования, используемым для представления переменных задачи оптимизации. :.~". Эти переменные (иазываемые генами) объединяются вместе и образуют строку значений (иазываемую хромосомой). Например, если мы должны найти максимум функции трех переменных г(х, у, з)„мы можем представить каждую переменную 10-разрядиым двоичным числом (при условии правильного выбора масштаба).
При этом хромосома будет содержать три гена, а ее длина будет равна 30 двоичиым разрядам (битам) 5 4.65 тз Параметр Ит Парю етр Их Параметр ЯЗ 10110Ш100101101101 101011110010101101 рию. 9.12. Процесс копировании переменных а кромосомю 'хечермиидх генетики набор переменных, описываемых хромосомами, называется .' 'дбвйдигтном. Генотип содержит информацию, по которой строится организм, обла': 'лй)тттщий определенным набором свойств (фенотипом).
Те же термины приме-; ~ф~~$тся и в теории генетических алгоритмов. Например, в задаче конструирования 'ха набор переменных, описывающих конкретный проект, является генотипом, '''«~~)давая конструкция — фенотипом. Жизнеспособность индивидуума определяет'"::,''-",:; "«~дрйктериспдками фенотипа, которые могут быть определены по генотипу (вы- ло имеющимся хромосомам при помощи функции приспособленности). Нные оптимизации представляются строкой или хромосомой, несмотря '~дз'что они могут принимать непрерывный ряд вещественных значений. Шн- -и!ййдддьиспользуется метод кодирования через целочисленное представление.
Снап;'~ЕЕ«)11',к переменным применяется линейное отображеште на подмножество целых ~дрййьпосяе чего целое число кодируется фиксированным числом битов. Пред)явг11(яййм, например, что непрерывная переменная оптимизации определена на йдг«вв«$Ш 1 — 1,28; 1,28). Мы можем закодировать такую переменную с точностью до ;, дй~тМаков после запятой, умножив ее вещественное значение на 100 и отбро- ую часть результата. Таким образом, значение переменной будет ото- :чГд)тггйтзао на целые числа от -128 до +128.
Двоичное представление целого числа '",:ф11(яяд10пить очень легко (листиш 9.3) 133]. ;,йюя)йгяиг 0.3. Общий вид генетического алгоритма ' а."'!тюят1И 1» Генетический алгоритн»Г Опадать начальную популяцию Рассчитать приспособленность каядого индивидууна. И11ЕЕ ИОТ расчет закончен 00 ВЕ61И /» порокдение нового поколения »/ Рбд разнер популяции/2 00 ВЕВЕИ /» Цикл воспроизводства »I тюьк „ ВибратЬ дВуХ ИидняндууНОВ ИЗ ПрвдидуЮЕГО ПОНОЛЕНня дпя равикпяюиня: «» Ореинуюество у более приспособпенних »I Реконбинировать хроносони индивидуунов: Рассчитать присгюсобгенность погонна: Добавить потомка в новую погуляцию: ЕИО !Е популяция конвертировала ТНЕИ расчет закончен :- ТЙОЕ: ЕИО ЕИО Функция приспособлаииости ;' Для оценки приспособленности строк лолжна использоваться целевая (оптими-.,; зируемая) функция.
Однако диапазон значений этой функции зависит от кон:-'- кретной задачи. Для обеспечения однородности алгоритма по отношению к раз: личным задачам мы выбираем функцию пригодности, нормируюшую целевую функцию на удобный отрезок 10, 1). Нормированное значение целевой функции ;:;, считается коэффициентом пригодности строки, который используется механиз- мом отбора для сравнения строк, составляющих популяцию ~33).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
