Содержание к диссертации
Введение
1. Анализ проблем, перспектив и методов эволюционного проектирования 10
1.1. Некоторые современные тенденции развития САПР 10
1.2. Эволюционное проектирование 17
1.3. Применение принципов эволюции при построении алгоритмов оптимизации 21
1.3.1, Теории эволюции естественных систем 21
1.3.2. Эволюционное моделирование 33
1.3.3- Генетические алгоритмы на основе не дарвиновских моделей эволюции 41
1.3.4, Гибридные алгоритмы на основе объединения различных теорий эволюции 46
1.4. Создание гибридных моделей на основе различных методик и информационных технологий 48
1.5. Обзор программных средств, использующих генетические алгоритмы 54
1.6. Выводы по главе 1 60
2, Многоэволюционный нечеткий генетический алгоритм 62
2.1. Построение генетических алгоритмов на основе различных моделей эволюции 62
2.1.1. Вид и межвидовая гибридизация в генетических алгоритмах 63
2.1.2, Способы реализации основных моделей эволюции в ГА 69
2.2. Построение гибридной системы на основе различных моделей эволюции 81
2.3. Гибридные модели с использованием ГА и нечеткой логики 83
2.3Л. Нечеткое кодирование 85
2.3.2. Нечеткие генетические операторы 89
2.3.3. Использование баз знаний для подбора параметров 97
2.4. Выводы по главе 2 107
3. Инструментальная среда поддержки эволюционного проектирования «gensearch» 109
3.1 Требования к программным продуктам, реализующим генетические алгоритмы 109
3.2. Основные характеристики инструментальной среды «GenSearch» 111
3.3. Структура инструментальной среды «GENSEARCH» 117
3.4. Выводы по главе 3 126
4. Исследование разработанных алгоритмов и программного обеспечения и оценка их эффективности при решении тестовых и практических задач 127
4.1. Цели и методы проводимых исследований 127
4.2. Исследование эффективности нечеткого генетического 130
4.2.1. Нечеткое кодирование 131
4.2.2. Кроссинговер 132
4.2.3. Мутация 134
4.2.4. Подбор параметров с использованием базы знаний 135
43. Исследование эффективности разработанного алгоритма на практической производственной задаче 139
4.3 Л. Постановка задачи 140
4.3.2. Существующие способы решения 142
4.3.3. Предлагаемый способ решения 146
4.3.4. Программная реализация предлагаемого решения 150
4.4. Выводы по главе 4 153
Заключение 154
Список литературы
- Применение принципов эволюции при построении алгоритмов оптимизации
- Вид и межвидовая гибридизация в генетических алгоритмах
- Основные характеристики инструментальной среды «GenSearch»
- Подбор параметров с использованием базы знаний
Введение к работе
Актуальность темы диссертации. В настоящее время весьма актуальными являются проблемы создания и повышения эффективности работы систем автоматизированного проектирования (САПР), что предполагает дальнейшую разработку и исследование научных основ проектирования, формирование принципиально новых методов и средств реализации проектных процедур, построение интегрированных, интерактивных комплексов синтеза и анализа проектных решений. При этом одной из наиболее важных тенденций развития современных информационных технологий и САПР является активное использование в них бионических принципов, методов и моделей, в частности, создание и применение методов и средств эволюционного проектирования (ЭП). Под эволюционным проектированием искусственной (технической) системы понимается целенаправленное использование компьютерных моделей эволюции на всех стадиях разработки системы. Естественным основанием для классификации концепции и стратегий ЭП может служить анализ причин эволюции системы (внешних или внутренних).
Эволюционное проектирование искусственной системы необходимо рассматривать одновременно как формирование ее наследственной изменчивости (внутренняя причина развития) и эволюционную адаптацию к внешней среде (внешняя причина развития). Тогда ЭП определяется как процесс формирования и развертывания генотипа и фенотипа разрабатываемой системы. Генотип системы соответствует всей наследственной (генетически обусловленной) информации о системе, а фенотип содержит набор ее структур, которые возникают в результате развития генотипа в определенной среде.
Таким образом, включение подсистем ЭП в состав современных интегрированных интерактивных САПР требует построения методологии, теории, методов и моделей эволюционного проектирования технических (производственных) систем, а также разработки теоретических и прикладных аспектов построения неклассических (недарвиновских) и гибридных эволюционных систем, включающих разнородные подсистемы, изменяющиеся во времени- В диссертационной работе предлагается новое решение важной
5 задачи построения гибридных систем в информатике и автоматизированном проектировании, которое опирается на различные модели эволюции, методы нечеткой логики и продукционные базы знаний, что имеет существенное значение для исследования процессов обработки информации, создания и исследования информационных моделей, моделей данных и знаний в САПР. Разработаны методология и методы ЭП в технике, включая постановку, формализацию и типизацию проектных процедур и процессов проектирования, построена инструментальная среда поддержки эволюционного проектирования.
Целью диссертационной работы является повышение эффективности
обработки информации и поиска решений в процессах автоматизированного проектирования за счет построения гибридных систем, использующих эволюционные алгоритмы, аппарат нечеткой логики и продукционные базы знаний.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
Анализ и разработка теоретических вопросов эволюционного проектирования- Реализация эволюционного проектирования с помощью эволюционных алгоритмов.
Исследование способов построения эволюционных алгоритмов на основе недарвиновских моделей эволюции.
3- Исследование существующих гибридных систем. Построение архитектур гибридных интеллектуальных систем, объединяющих методы и средства эволюционных алгоритмов и нечеткой логики.
Разработка способов автоматического подбора параметров и методов самоадаптации эволюционного алгоритма под решаемую задачу.
Разработка алгоритма решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.
Создание программного обеспечения, реализующего разработанные алгоритмы.
7, Применение разработанного программного обеспечения для решения
прикладных оптимизационных задач.
Методы исследования. В диссертационной работе для решения поставленных задач используются методы системного анализа и проектирования, теории множеств и теории алгоритмов, нечеткой логики и теории вероятностей, эволюционного моделирования и инженерии знаний. Результаты экспериментов обрабатывались с использованием методов математической статистики.
Научная новизна диссертации определяется, в первую очередь, разработкой гибридных систем, сочетающих методы эволюционных алгоритмов и нечеткой логики. Новыми являются:
Эволюционный алгоритм на базе недарвиновских моделей эволюции;
Эволюционный алгоритм, использующий аппарат нечеткой логики для кодирования хромосом, а также реализации генетических операторов;
Метод автоматического подбора параметров эволюционного алгоритма на основе баз знаний;
Архитектура инструментальной среды поддержки эволюционного проектирования.
Практическая ценность работы связана с построением комплекса эволюционных алгоритмов и разработкой инструментальной среды поддержки ЭП, реализующей предлагаемые схемы и алгоритмы. В частности, прикладную значимость имеет алгоритм управления запасами при оптимизации раскроя ленточного материала на основе гибридных систем эволюционного моделирования.
Внедрение и реализации результатов. Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении хоздоговорной тематики Отдела «Компьютерные системы автоматизации» НУК РК МГТУ им, Н.Э.Баумана. Результаты диссертации также использованы при выполнении работ по грантам Российского фонда фундаментальных исследований (проекты №02-01-00784, 03-07-90012, 04-01-00306, 05-01-00514).
Результаты исследований, проведенных в диссертационной работе, были внедрены на «ОАО Коломенский завод РТИ», Кроме того, результаты работы нашли применение в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. КЭ.Баумана и кафедры САПР TPTY.
Достоверность научных положений и выводов диссертации подтверждается результатами вычислительных экспериментов на тестовых и практических задачах, а также актами о внедрении- Акты о внедрении и использовании результатов работы, а также копия авторского свидетельства (Роспатент) представлены в Приложении к диссертации.
Апробация работы. Основные результаты работы докладывались на: Пятом международном симпозиуме «Интеллектуальные системы» (INTELSf 2002, Калуга, 2002г.), Научной сессии МИФИ-2003 (Москва, 2003г.), Третьей международной научно-технической конференции «Измерение, контроль, информатизация» (Барнаул, 2003), Региональной студенческой конференции «Применение кибернетических методов в решении проблем общества XXI века» (Обнинск, 2003), Международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике» (КЛИН-2003, Ульяновск, 2003), Девятой Национальной конференции по искусственному интеллекту с международным участием (КИИ-2004, Тверь, 2004г-), Международных научно-технических конференциях IEEE AIS'04 и CAD-2004 (Дивноморское, 2004г.), Научной сессии МИФИ-2005 (Москва, 2005г.), Ш-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005г.), Международных научно-технических конференциях IEEE AIS'05 и CAD-2005 (Дивноморское, 2005г.).
Публикации. По теме диссертации автором опубликовано 16 работ, включается 3 публикации в журналах, рекомендованных ВАК РФ, имеется авторское свидетельство об официальной регистрации программы для ЭВМ (Роспатент). Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений. Объем диссертации составляет 175
8 страниц, в том числе 29 рисунков и 16 таблиц. Список литературы содержит 173 библиографических наименования. На защиту выносятся:
Архитектура эволюционных алгоритмов на основе недарвиновских моделей эволюции,
Архитектуры гибридных систем на основе эволюционных алгоритмов и нечеткой логики.
Метод автоматического подбора параметров и адаптации параметров эволюционного алгоритма на основе баз знаний.
Архитектура инструментальной среды поддержки эволюционного проектирования.
5- Алгоритм решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.
Во введении обоснована актуальность диссертационной работы, сформулированы цель исследования и его основные задачи, указаны научные положения, выносимые на защиту, приведены сведения о практической ценности и внедрении.
В первой главе диссертации приводится постановка задач исследования и обзор методов решения данных задач. Рассматриваются актуальные проблемы информатики и разработки САПР, в том числе инновационные стратегии проектирования. Показано, что эволюционное проектирование является перспективным направлением развития САПР, связанным с применением в них бионических подходов и методов. Отмечаются недостатки классических генетических алгоритмов, являющихся основой эволюционного проектирования. Для устранения предлагаемых недостатков предлагается использование недарвиновских моделей эволюции и гибридных систем с их использованием. Показана перспективность разработки неоднородных гибридных систем с использованием генетических алгоритмов. Описаны существующие программные средства проектирования и реализации генетических алгоритмов (ГА) и показаны их недостатки.
Во второй главе описываются предлагаемые варианты реализации недарвиновских моделей эволюции в генетических алгоритмах, вводится понятие вида. С использованием понятия вида определяется операция межвидового скрещивания (гибридогенез) и предлагаются различные варианты его реализации. Рассматриваются варианты построения гибридного генетического алгоритма на базе различных моделей эволюции. Также во второй главе описывается разработанная автором гибридная система на основе двух разнородных подходов — нечеткой логики и эволюционного моделирования - нечеткий генетический алгоритм. Предлагаются способы реализации основных генетических операторов в нечетком генетическом алгоритме. Описывается способ подбора и адаптации параметров генетического алгоритма под решаемую задачу на основе баз знаний, в том числе на индивидуальном уровне.
В третьей главе описывается разработанная инструментальная среда поддержки эволюционного проектирования - «GenSearch». Рассмотрены ее структура, состав и назначение каждого блока. Приведен возможный способ организации генетического поиска с ее использованием,
В четвертой главе приведены результаты исследований разработанных алгоритмов на тестовых и практических производственных задачах- Показана эффективность нечеткого ГА на тестовых непрерывных функциях. Исследованы различные способы применения базы знаний для подбора и адаптации параметров ГА и показано повышение эффективности ГА при ее использовании. На примере практической производственной задачи управления запасами при раскрое ленточного материала продемонстрирована эффективность разработанных алгоритмов.
В заключении содержатся основные выводы и результаты диссертации.
В приложении 1 приведена копия авторского свидетельства (Роспатент) на инструментальную среду «GenSearch». В приложении 2 приведены копии актов о внедрении и использовании работы.
Применение принципов эволюции при построении алгоритмов оптимизации
Всякая претендующая на полноту и последовательность эволюционная теория должна решить ряд принципиальных проблем, включая [36, 82, 117]: 1) анализ общих причин и движущих сил эволюции организмов; 2) исследование механизмов развития приспособлений (адаптации) организмов к условиям их обитания и изменениям этих условий; 3) определение причин и механизмов возникновения поразительного разнообразия форм организмов, а также причины сходств и различий разных видов и их групп; 4) изучение причины эволюционного прогресса, т.е. нарастающего усложнения и совершенствования организации живых существ в ходе эволюции при одновременном сохранении более примитивных и просто устроенных видов.
С появление первой законченной теории эволюции Ж.-Б. Ламарка прошло почти 200 лет, но до сих пор среди ученых нет однозначного мнения о механизмах эволюции ЕС [24, 35, 79, 82]. Рассмотрим основные классы эволюционных учений.
Ламаркизм
Первая наиболее законченная теория эволюции связывается с именем Ж,-Б. Ламарка [73]. Еще в 1809 г, он предположил, что все живые организмы целесообразно приспосабливаются к условиям среды, а характеристики, приобретенные организмом в течение жизни, наследуются потомками. Причинами эволюции Ж,-Б.Ламарк считал стремление всех живых организмов к прогрессу, развитию от простого к сложному, а также целесообразные изменения организмов, направленные на приспособление к внешним условиям. Эти изменения, как утверждал Ж.-Б. Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков. Отметим также, что для теории Ламарка характерна концентрация внимания на отдельном организме, рассматриваемом вне его связей с другими особями того же вида, т.е., говоря современным языком, отсутствие популяционного подхода, непонимание эволюционной роли биологического вида и составляющих его популяций. В текущий момент теория Ламарка отвергается большинством ученых, но появились ряд учений, успешно использующих ее отдельные части: неоламаркизм, органицизм, психоламаркизм [82].
В свое время Р. Гольдшмидт обратил внимание на удивительный параллелизм между фенотипическими проявлениями модификационной и наследственной изменчивости. Одно и то же состояние фенотипических признаков у разных особей данного вида может формироваться по-разному: у одних особей - как модификационная вариация, проявляющаяся лишь в определенных условиях, у других — как единственно возможный вариант признака. Если в популяции, где данный признак первоначально был одним из модификационных вариантов нормы реакции, появляется мутация, обусловливающая более высокую приспособленность, возникает иллюзия "превращения" ненаследственной модификации в наследственный признак {"эффект Болдуина") [82], т. е. "унаследования приобретенного соматического признака" в духе ламаркизма. Дарвинизм
Теория Чарльза Дарвина (дарвинизм), известная под названием теории естественного отбора, является наиболее законченной теорией эволюции [37]. Согласно этой теории (в изложении И.И,Шмальгаузена [116]), основными условиями эволюции являются: 1) наследственная изменчивость, т.е. мутирование, понимаемое как предпосылка эволюции, ее материал; 2) борьба за сущестеоеание как контролирующий и направляющий фактор эволюции; 3) естественный отбор как преобразующий фактор эволюции, В [79] в качестве одного из главных оснований «универсального эволюционизма» берется дарвиновская триада: изменчивость, наследственность, отбор. Основными факторами естественного отбора являются: механизм отбора; режим размножения; процессы индивидуального развития. Частным случаем естественного отбора является половой отбор, который обеспечивает развитие признаков, связанных с функцией размножения. Мутации являются теми наследственными изменениями, которые либо отдельно, либо совместно определяют изменения свойств, признаков, особенностей или норм реакции организмов, В центре внимания эволюционной теории находятся не отдельные организмы, а биологические виды и внутривидовые группировки (популяции). Основными недостатками дарвинизма являются [49, 82, 116]: 1) признание возможности эволюционных изменений на основе определенной изменчивости и упражнения и неупражиения органов; 2) переоценка роли перенаселения для обоснования борьбы за существование; 3) преувеличенное внимание к внутривидовой борьбе в объяснении дивергенции; 4) недостаточная разработанность концепции биологического вида как формы организации живой материи, принципиально отличающейся от подвидовых и надвидовых таксонов; 5) неучет специфики макроэволюционных преобразований организации и их соотношений с видообразованием. Синтетическая теория эволюции
Синтез дарвинизма и представлений генетиков о случайном возникновении новых признаков и распространении их в популяции привел к возникновению в 40-х годах ХХ-го века синтетической теории микроэволюции, ставшей классической. Основными работами в этой области принято считать работы Р.Фишера, С.Райта, Н.И.Вавилова, Н.П.Дубинина, Д.Холдейна, Д.Хаксли и др. В последующие годы синтетическая теория эволюции (СТЭ) в определенной степени интегрировала также данные эволюционной морфологии (в первую очередь палеонтологии, в которой особо следует выделить работы Д.Симпсона), однако макроэволюционные
Вид и межвидовая гибридизация в генетических алгоритмах
В текущий момент генетический алгоритм оперирует следующими единицами: ген, хромосома, популяция- Введем понятие «вида». В биологии под видом понимается совокупность родственных организмов, способных к скрещиванию с образованием плодовитого потомства, характеризующихся определенными, только им присущими морфофизиологическими и эколого-географическими особенностями [16]. Для всех особей одного вида характерна также общность филогенетического происхождения, одинаковый тип обмена веществ и распространение на определенной территории, называемой ареалом.
В терминах ГА под «видом» будем понимать совокупность хромосом, характеризующуюся определенным способом кодирования и поведения, в частности, образования и выживания новых индивидов [31].
Рассмотрим более подробно взаимосвязь терминов «вид» и «популяция» в биологии и ГА- Для этого дадим определение термина «популяция».
Под популяцией в биологии понимается группа особей, способная к более или менее устойчивому самовоспроизводству (как половому, так и бесполому), относительно обособленная (обычно географически) от других групп, с представителями которых (при половой репродукции) потенциально возможен генетический обмен, С точки зрения популяционной генетики, популяция - это группа особей, в пределах которой вероятность скрещивания во много раз превосходит вероятность скрещивания с представителями других подобных групп [117].
В терминах ГА под популяцией понимается некоторое конечное множество закодированных решений, представленных в виде одной или нескольких хромосом [40].
Как видим в биологии популяция - следующий элемент иерархии после индивида- В генетическом алгоритме популяция рассматривается намного шире, т.е. популяция может иметь хромосомы с разным типом кодирования, разными ГО (см, например [166, 167]), что, по сути, является развитием нескольких видов в рамках одной популяции. Такой интерпретации термина «популяция» в биологии соответствует термин биоценоз, т.е. группа организмов различных видов, совместно обитающих на одной территории и взаимодействующих между собой, но так как термин популяция в ГА устоялся, то в дальнейшем в данной работе будем использовать именно его.
Хромосома при использовании нескольких видов изображена на рис.2Л? где V— идентификатор, указывающей на принадлежность хромосомы к і-му виду; Хь ,..,Хт-гены,
В зависимости от вида хромосомы, мы будем рассматривать гены Xi,...,Xm, как переменные оптимизируемой задачи с вещественным, битовым или нечетким кодированием
Введение понятия вида позволяет рассматривать развитие хромосом с разными способами кодирования и ГО как развитие различных видов. Проводя дальнейшую аналогию с живой природой, рассмотрим взаимоотношения, возникающие между различными индивидами: а) конкуренция за ресурсы; б) скрещивание.
Под ресурсами будем понимать процессорное время, выделяемое каждой популяции для воспроизведения потомков и оценки их эффективности- Сразу отметим, что как и в живой природе, где разные виды потребляют разное количество ресурсов, в ГА различные алгоритмы обладают разной временной сложностью.
Как и в живой природе, в ГА скрещиваться могут особи одного вида. В этом случае идентификатор Vi не участвует в операциях скрещивания и мутации.
С другой стороны, существуют теории эволюции, например симгенез, которые считают скрещивание между различными видами основой эволюции- Выживаемость получаемых в таких случаях гибридов мала, но выжившие обладают намного большей приспособленностью к окружающей среде, чем каждый из видов в отдельности [82]. Скрещивание между разными видами в биологии называется гибридизацией. Точнее под гибридизацией понимается скрещивание разнородных в наследственном отношении организмов (когда в одном организме происходит слияние разнородных наследственных признаков и компонентов).
Рассмотрим способы проведения гибридизации в ГА.
В самом простом случае, если оба вида используют одинаковый способ кодирования и в хромосоме хранятся только значения переменных оптимизируемой задачи, то в результате скрещивания двух хромосом разных видов будет происходить обмен генотипом, без изменения поведения хромосомы- Оператор кроссинговера определяется оператором кроссинговера, соответствующим лучшей из хромосом родителей- Два получаемых потомка будут относиться к разным видам родителей. Таким образом, мы сохраняем видовое разнообразие в популяции. Операции мутации, инверсии и т.д. будут определяться видом данного потомка.
Основные характеристики инструментальной среды «GenSearch»
На основе описанных выше требований была разработана инструментальная среда «GenSeacrh» [33], структура которой изображена на рис, 3.1. Среда реализована на языке высокого уровня Object Pascal в интегрированной среде разработки Delphi 5.0 под операционные системы Windows9 , Windows2000, Windows NT, Windows XP. Программа состоит из выполняемого файла GenSearch.exe, файлов БЗ - .fcs, файлов сохранения результатов работы программы - .rsl Инструментальная среда реализована на основе объектно-ориентированного подхода: каждой сущности среды соответствует некоторый объект. Например, блок, реализующий выполнение ГО — объект TGenetic, блок, реализующий конструктор ГА - TConstruct и т.д. Такой подход к программированию позволяет встраивать разработанные объекты в другие программы на этапе программирования, уменьшая временные затраты на создание новых программ, и использовать сторонние разработки при создании модулей инструментальной среды.
При разработке первой версии среды основная задача состояла в создании программы, реализующей генетический поиск и позволяющей настраивать и управлять всеми его элементами. Одновременно с этим, инструментальная среда должна иметь возможность встраиваться в другие системы как блок оптимизации, показывая эффективный поиск с минимумом настроек для упрощения работы с ней пользователя, не являющегося экспертом по ГА Параметры ГА, устанавливаемые инструментальной средой, можно разделить на 3 группы:
1 Устанавливаемые для всех популяций и не изменяемые во время работы ГА: количество запусков генетического алгоритма. Каждый запуск является независимым от предыдущего и производится с одинаковыми параметрами; функция пригодности;
2. Устанавливаемые для всех популяций, которые могут изменяться Блоком определения и корректировки параметров ГА (БОП): точность представления генотипа и расчета функции пригодности. Поскольку на первом этапе работы ГА задачей является определение перспективных областей поиска, а не поиск точного решения, то можно предположить, что на начальных поколениях работы ГА можно использовать аппарат расчета функции пригодности с некоторой погрешностью, которая может быть заведомо больше погрешности определения функции пригодности на последнем этапе развития популяции. При этом погрешность в определении функции пригодности, скорее всего, не внесет значительных коррективов в правильность стратегии поиска. Тогда мы можем значительно повысить продуктивность такой системы поиска с точки зрения вычислительных ресурсов, поскольку менее точные расчеты требуют меньше времени. Исходя из принципа работы ГА, на втором этапе развития популяции необходимо иметь возможность для более точного расчета функции пригодности.
На последнем этапе развития популяции необходимо производить максимально детализированный расчет. Таким образом, для сокращения времени на поиск решения, инструментальная среда должна позволить производить расчет с различной точностью; количество популяций в многопопуляционном алгоритме [57]. Управление популяциями происходит на основе макроэволюции, а параметры обмена (время обмена, способ обмена) определяются БОП; размер популяции; количество потомков; количество поколений (критерий останова для каждой отдельной популяции может задаваться отдельно); З, Устанавливаемые для каждой популяции в отдельности, которые могут изменяться БОП: способ кодирования (битовое, вещественное, нечеткое); список и параметры ГО; метод локальной оптимизации.
Подбор параметров с использованием базы знаний
Для решения данной задачи предложено использовать генетический алгоритм, реализованный в инструментальной среде «GenSearch» Каждая заготовка получает два идентификационных номера, соответствующих горизонтальному и вертикальному положению заготовки. Хромосома определяет набор заготовок, укладываемых на полотно и порядок укладывания- В данной работе используется мобильный ГА [135], т.е. ГА, имеющий хромосому переменной длины.
В качестве алгоритма декодера используется алгоритм IBL (Improvement Bottom Left) — улучшенный «нижний левый», описанный в [80]. В алгоритмах BL и IBL построение карты раскроя по PL происходит в соответствии с BL-условием, согласно которому каждая размещенная на полосе заготовка не может быть сдвинута дальше вниз и влево.
Алгоритм «нижний левый» удобно представить в виде последовательности шагов. Шаг L Поместить заготовку 1 в левый нижний угол полосы. Шаг і. Последовательно передвинуть заготовку / согласно PL, /=2,..., m, начиная от верхнего правого угла раскраиваемой площади полосы влево настолько, насколько это возможно, затем вниз, снова влево, вниз и т.д. до тех пор, пока заготовка і не сможет быть сдвинута влево или вниз (рис.4.5).
Алгоритм IBL разработан на основе BL, и его стратегия отличается введением преимущественного движения заготовки влево. А именно, размещаемая заготовка движется вниз только до тех пор, пока она может быть сдвинута влево (рис. 4,5).
Легко показать, что шаблон упаковки, созданный IBL-алгоритмом, соответствует BL-условию, так как в противном случае, по крайней мере, одну из заготовок можно сдвинуть дальше вниз или влево. Это противоречит шагу / IBL-алгоритма.
При использовании такой структуры данных для заданных т заготовок число 2тт\ является верхней границей шаблонов упаковки, которые могут быть созданы с помощью IBL-алгоритма (где т!-число последовательностей, 2т - число комбинаций заготовок с учетом поворота на 90 градусов). Следовательно, проблема ортогонального раскроя — это проблема перестановки. На практике IBL-алгоритмом может быть создано меньше, чем 2тт\ шаблонов упаковки. Сложность IBL-алгоритма можно оценить, учитывая, что каждая заготовка / может быть помещена максимум за і перемещений вдоль сторон уже раскроенных заготовок или вдоль границы полосы. Следовательно, сложность размещения заготовки і равна О (і) и общая сложность — О (mz).
Каждый запуск ГА позволяет определить укладку для одного отреза. Количество запусков ГА определяется количеством блоков в заказах или периодом расчета, т.е. расчет ведется до окончания раскроя всех заготовок из всех заказов или пока не будет раскроено все обрабатываемое полотно за период расчета. Каждый запуск использует 50% хромосом из окончательной популяции предыдущей укладки как хромосомы начальной популяции. Остальные 50% создаются случайным образом. В работе используется нечеткое кодирование с точностью представления 1.
Оптимизируемой величиной для ГА является функция пригодности. ФП = а і xSnw + а2 Sxp + а3 xSmmp + а4 xS„np9 где Snot — стоимость отходов полотна; Sxp - затраты на хранение заготовок, размещенных в данной хромосоме; Smmp - штраф за невыполнение заказа в срок; Snnp - штраф за перепроизводство заготовок, размещенных в данной хромосоме; а/, а2, аз, Q4 -весовые коэффициенты, определяющие значимость производственных факторов- Параметры Snmy Sxp, SmmPt Smp необходимо минимизировать. Здесь &пол "" Ь \ 1 -пу ПОЛ Mi где L - длина текущего отреза, Кт - коэффициент использования материала (КИМ), SKMM — стоимость погонного метра полотна. Эмпирически были определены следующие значения весовых коэффициентов: aj = 2, aj — lt аз — 2, а4 = 0.5.
В связи с возможностью отреза полотна различной длины необходимо при расчете ФП определить длину полотна в пределах [lmin, lmaxL что обеспечивает максимальное значение показателя Кт. Для этого после укладки очередной заготовки ее идентификатор и координата конца заготовки на полотне помещаются в отсортированный по указанной координате массив. После окончания укладки всех блоков определяем длину наилучшего отреза по показателю Кт_ Для этого, перемещаясь по массиву, определяем Кті для каждой координаты окончания заготовки по формуле (4-3), если координата превышает 1т[П: кті=Е"г "г ЙА ," (4-3) где ХІ - координата правого нижнего угла і-й заготовки по оси ОХ; z =./,»., т - заготовки с координатами правого нижнего угла заготовки по оси ОХ, большими /(см. рис. 4.5);
Среди всех Кті определяем максимальное значение, причем соответствующая ему длина и будет являться длиной текущего отреза. Все заготовки с координатами правого нижнего угла по оси ОХ, большими длины отреза, удаляются из хромосомы.
Для описания алгоритма расчета 8штр введем следующие обозначения: Датах — дата і-го заказа; LCeo6 І - количество свободного полотна на момент выполнения 1-ГО заказа» т.е. количество полотна, которое будет обработано к дате i-ro заказа и не используемого под другие заказы с более ранней датой, Ісеобі- =Lceo6i_i+ (Датаі-Датаи) Іта Li І — количество полотна, необходимого для выполнения і-го заказа, с учетом уже сделанных заготовок.
