книги / Основы САПР. CAD CAM CAE

Рис. 9.7. Решение задачи коммивояжера для 100 городов

Рис. 9.8. Решение задачи коммивояжера для 400 городов, полученное с nомощью метода модельной закалки

Оптимальная компоновка

Задача опти.малыюй компоновки (optimal nesting) состоит в минимизаци11 ис­

пользования исходных листоn (заготовок) при производстве деталей разЛii'-fной

формы. Типичные ограничения задачи состоят· в том, что формы не должнь1 пе­

рекрываться, но при этом должны целиком располагаться внутри границ 1II1cтa.

Если на листе имеются дефекты, эти дефекты должны исключаться из полезной площади в процессе комПоновки. Таким образом, функция стоимости может

быть записана в следующем виде:

F(5) =отходы+ w х перекрытие.

Здесь 5 - текущая конфигурация компоновки, отходы - количество отходов

с одного листа (или листов), то есть разность площади исходного листа и площа­ ди уместившихся на нем деталей. Перекрытие - суммарная площадь перекры­ вающихся частей деталей, а w - весовой коэффициент. В процессе оптимизации

перскрытия не запрещаются, но большой весовой коэффициент исключает их в

конечной конфигурации. Заметьте, что здесь мы, по сути, используем внутрен­ нюю штрафную функцию из раздела 9.2.

Конфигурация 5', соседняя с текущей конфигурацией 5, может быть построена небольшим возмущением текущей конфигурации. Например, можно случайным

образом выбрать одну деталь из всех размещенных на листе и немного изменить ее

положение и ориентацию. Изменение конфигурации с 5 на 5' называется пере­ мещением и выполняется в соответствии с алгоритмом Метрополиса (листинг 9.2).

Результаты размещения деталей на стальном листе для последовательного их из­

готовления демонстрирует рис. 9.9. Примеры размещения 36 выкроек на отрезе

постоянной ширины и на отрезе неправилыюй формы с внутренним дефектом

приведены на рис. 9.10 и рис. 9.11. Дефектная область показана на рис. 9.11 чер­

ным цветом, в данном случае это тонкая вертикальная полоска. Дефекты такого

типа часто возникают при отрезании заготовок для пошива одежды из кожи.

7

Доля отходов= 17,5%

ДОЛЯ ОТХОДОВ = 28,4%

Рис. 9.9. Оптимальное размещение деталей для последовательной вырубки

Рис. 9.1 О. Размещение 36 выкроек на пр~щоугольном отрезе

Рис. 9. 11. Размещение 36 выкроек на отрезе неправильной формы с внутренним дефектом

9.5. Генетические алгоритмы

Генетическими алzоритмам.и (genetic algorithms) называется группа адаптивных

методов, которые могут использоваться для решения задач поиска и оптимиза­

ции. Они происходят от тех же основ, что и естественная эволюция и генетика.

Популяции живых существ развиваются в течение многих поколений в соответ­

ствии с принципами естественного отбора и 4Выживания наиболее приспособ­

ленных>>. Имитируя этот процесс, генетические алгоритмы способны решать ре­ альные задачи, при условии, что те будут правильно закодированы [13].

Сила генетических алгоритмов в их устойчивости и в способности решать зада­

чи самых разных типов, в том числе и трудноразрешимые другими методами.

Хотя генетические алгоритмы не обязательно находят глобально-оптимальное

решение, они обычно 4достаточно быстро~ находят •достаточно хорошие~ реше­

ния. Разумеется, специализированные методы, ориентированные на конкретные

задачи, по сравнению с генетическими алгоритмами почти наверняка дадут луч·

шую скорость и точность конечного результата. Превосходство генетических

алгоритмов проявляется в таких областях, где специализированных методов не

существует. Однако даже имеющиеся методы можно в некоторых случаях усо­

вершенствовать, сскрестив• их с генетическими алгоритмами [56].

Основные принципы генетических алгоритмов были заложены Холландам [71],

им посвящено достаточно много трудов. Эти алгоритмы имитируют то, чем обу­

словливается эволюция в живых популяциях. В природе выживают те, кто луч­

ше приспособлен к конкуренции за ограниченные ресурсы, поэтому адаптация к

изменяющейся конкурентной среде принципиально важна для выживания инди­

видуумов любого вида. Уникальные особенности индивидуума определяют его жизнеспособность, но сами они, в сnою очередь, определяются генаr.w индиви­ дуума. Каждой особенности сопоставляется элемент наследственной информа­

ции - ген. Наборы генов, определяющих особенности организма, объединяются

вхромосомы. Процесс воспроизводства создает разнообразие в генофонде, а на·

чинается оно с рекомбинации хромосом родительских особей в момент объеди­

нения их половых клеток. Из исходных комбинаций генов создаются новые,

врезультате чего получается новый генотип. Происходит обмен генами между

хромосомами, что дает хромосомы с новыми свойствами. Этот процесс называется

101 10111100101 101101

t

101011110010101101

Рис. 9. 12. Процесс кодирования переменных в хромосоме

В терминах генетики набор переменных, описываемых хромосомами, называется геиотипом. Генотип содержит информацию, по которой строится организм, обла­

дающий определенным набором свойств (фенотипо.м). Те же термины приме­

няются и в теории генетических алгоритмов. Например, в задаче конструирования

моста набор переменных, описывающих конкретный проект, является генотипом, а готовая конструкция - фенотипом. Жизнеспособность индивидуума определяет­

ся характеристиками фенотипа, которые могут быть определены по генотипу (вы­

числены по имеющимся хромосомам при помощи функции приспособленности).

Переменные оптимизации представляются строкой или хромосомой, несмотря

на то что они могут принимать непрерывный ряд вещественных значений. Ши­

роко используется метод кодирования через целочисленное представление. Сна­

чала к переменным применяется линейное отображение на подмножество uелых чисел, после чего целое число кодируется фиксированным числом битов. Пред­

положим, например, что непрерывная переменная оптимизации определена на

отрезке [-1,28; 1,28]. Мы можем закодировать такую переменную с точностью до двух знаков после запятой, умножив ее вещественное значение на 100 и отбро­

сив дробную часть результата. Таким образом, значение переменной будет ото­ бражено на целые числа от -128 до +128. Двоичное представление целого числа вычислить очень легко (листинг 9.3) [33].

Лисrинг 9.3. Общий вид генетического алгоритма

BEGIN /* Генетический алгоритм */

Создать начальную популяцию:

Рассчитать приспособленность каждого индивидуума:

WHILE NOT расчет закончен 00

BEGIN /* порождение нового поколения */ FOR размер популяции/2 DO

BEGIN /* Цикл воспроизводства */

Выбрать двух индивидуумов из предыдущего поколения для размножения: /* Преимущества у более приспособленных */ Рекомбинировать хромосомы индивидуумов:

Рассчитать приспособленность потомка: Добавить потомка в новую популяцию:

END

IF популяция конвергировала THEN

расчет закончен := TRUE:

END

END

Функция приспособленности

Для оценки приспособленности строк должна использоваться целевая (оптими­ зируемая) функция. Однако диапазон значений этой функции зависит от кон­

кретной задачи. Для обеспечения однородности алгоритма по отношению к раз­

личным задачам мы выбираем функцию пригодности, нормирующую целевую функцию на удобный отрезок fO, 1]. Нормированное значение целевой функции

считается коэффициентом пригодности строки, который используется механиз­

мом отбора для сравнения строк, составляющих популяцию [33]. Целевая функ­ ция нормируется таким образом, что максимальная пригодность соответствует

оптимальной ситуации.

Механизм отбора

Процесс отбора является имитацией естественного отбора, имеющего место в при­

роде. Более приспособленные решения выживают, тогда как худшие исчезают.

В генетических алгоритмах более приспособленная строка получает большее ко­

личество потомков, в точности подобных ей самой, и потому получает больше

шансов на выживание в следующем поколении. В схеме пропорционального от­

бора строка, значение приспособленности которой совпадает со средним по по­

пуляции, получает одного потомка и участвует в процессе воспроизводства сле­

дующего поколения. Строка с большим значением приспособленности получает больше одного потомка, тогда как строка с меньшим значением приспособлен­ ности получает меньше одного потомка. Поэтому более совершенные строки бо­

лее активно участвуют в воспроизводстве, тогда как вклад менее совершенных

оказывается меньшим. Рассмотрим, например, популяцию из четырех строк

(табл. 9.2).

Таблица 9.2. Параметры популяции

В нашем примере вторая строка получит одного потомка, а вероятность полу­

чить второго будет равна 0,99. Четвертая строка также получит одного потомка,

а с вероятностью 0,22- и второго. Итак, вторая и четвертая строки точно полу­

чают по одному потомку. Остается выбрать, какая именно получит двух остав­ шихся потомков. Мы выбираем первую строку (0,58) и вторую строку (0,99), по­ тому что вероятности у них больше, чем у третьей и четвертой строк (0,22 и 0,21

соответственно). Заметьте, что для второй и четвертой строк вероятности были

уменьшены на 1, потому что эти строки уже получили по одному потомку. Та­

ким путем создается новая популяция, в которой среднее значение приспособ­

ленности оказывается выше.

Воспроизводство

На этапе воспроизводства из популяции выбираются индивидуумы, генетический

материал которых рекомбинируется, в результате чего получаются потомки, со­

ставляющие следующее поколение. Родительские особи выбираются из популя­ ции случайным образом. Поскольку более приспособленные особи имеют шанс получить несколько потомков, у них больше шансов и на то, чтобы быть выбран­ ными для воспроизводства несколько раз, тогда как менее приспособленные мо­

гут не участвовать в воспроизводстве ни одного раза.

Хромосомы двух выбранных родитеЛьских особей рекомбинируются. Обычно

это осуществляется механизмами кроссовера и мутации. При кроссовере берут­

ся два индивидуума, хромосомы которых разрезаются на части в случайных мес­

тах, в результате чего получаются два «головных» сегмента и два <<хвостовых>>

сегмента. Затем «хвостовые» сегменты меняются местами, в результате чего по­ лучается две хромосомы нормальной длины (рис. 9.13). Это называется кроссо­

вером в одной точке (single-point crossover) [33]. В каждой из двух хромосом ока­

зьшаются гены обоих родителей.

Родитель N

Рис. 9.13. Кроссавер

Кроссавер не всегда применяется ко всем парам размножающихся индиви­

дуумов. Пары выбираются случайно, причем вероятность кроссовера полагается равной какому-либо числу от 0,6 до 1,0. Все случайные операции осуществля­

ются при помощи генератора случайных чисел. Кроссавер разрешается, если

выпавшее случайное число от О до 1 оказывается меньшим, чем выбранная веро­

ятность (имеющая значение от 0,6 до 1). Если кроссовера не происходит, по­ томство в точности копирует родителей. Это дает каждому индивидууму шанс

передать свои гены в последующие поколения без нарушений, вызванных крос­

совером.

Мутация применяется индивидуально к каждому потомку после кроссовера.

Оператор мутации случайным образом изменяет каждый ген с малой вероятно-