Содержание к диссертации
Введение
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.1. Нечеткое кодирование 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
4.3. Исследование эффективности разработанного алгоритма на
практической производственной задаче 139
4.3.1. Постановка задачи 140
4.3.2. Существующие способы решения 142
4.3.3. Предлагаемый способ решения 146
4.3.4. Программная реализация предлагаемого решения 150
4.4. Выводы по главе 4 153
Заключение 154
Список литературы
- Применение принципов эволюции при построении алгоритмов оптимизации
- Вид и межвидовая гибридизация в генетических алгоритмах
- Основные характеристики инструментальной среды «GenSearch»
- Исследование эффективности нечеткого генетического
Введение к работе
Актуальность темы диссертации. В настоящее время весьма актуальными являются проблемы создания и повышения эффективности работы систем автоматизированного проектирования (САПР), что
предполагает дальнейшую разработку и исследование научных основ проектирования, формирование принципиально новых методов и средств реализации проектных процедур, построение интегрированных, интерактивных комплексов синтеза и анализа проектных решений. При этом одной из наиболее важных тенденций развития современных информационных технологий и САПР является активное использование в них бионических принципов, методов и моделей, в частности, создание и применение методов и средств эволюционного проектирования (ЭП). Под эволюционным проектированием искусственной (технической) системы понимается целенаправленное использование компьютерных моделей эволюции на всех стадиях разработки системы. Естественным основанием для классификации концепции и стратегий ЭП может служить анализ причин эволюции системы (внешних или внутренних).
Эволюционное проектирование искусственной системы необходимо рассматривать одновременно как формирование ее наследственной изменчивости (внутренняя причина развития) и эволюционную адаптацию к внешней среде (внешняя причина развития). Тогда ЭП определяется как процесс формирования и развертывания генотипа и фенотипа разрабатываемой системы. Генотип системы соответствует всей наследственной (генетически обусловленной) информации о системе, а фенотип содержит набор ее структур, которые возникают в результате развития генотипа в определенной среде.
Таким образом, включение подсистем ЭП в состав современных интегрированных интерактивных САПР требует построения методологии, теории, методов и моделей эволюционного проектирования технических (производственных) систем, а также разработки теоретических и прикладных аспектов построения неклассических (недарвиновских) и гибридных эволюционных систем, включающих разнородные подсистемы, изменяющиеся во времени. В диссертационной работе предлагается новое решение важной
5 задачи построения гибридных систем в информатике и автоматизированном проектировании, которое опирается на различные модели эволюции, методы нечеткой логики и продукционные базы знаний, что имеет существенное значение для исследования процессов обработки информации, создания и исследования информационных моделей, моделей данных и знаний в САПР. Разработаны методология и методы ЭП в технике, включая постановку, формализацию и типизацию проектных процедур и процессов проектирования, построена инструментальная среда поддержки эволюционного проектирования.
Целью диссертационной работы является повышение эффективности обработки информации и поиска решений в процессах автоматизированного проектирования за счет построения гибридных систем, использующих эволюционные алгоритмы, аппарат нечеткой логики и продукционные базы знаний.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
Анализ и разработка теоретических вопросов эволюционного проектирования. Реализация эволюционного проектирования с помощью эволюционных алгоритмов.
Исследование способов построения эволюционных алгоритмов на основе недарвиновских моделей эволюции.
Исследование существующих гибридных систем. Построение архитектур гибридных интеллектуальных систем, объединяющих методы и средства эволюционных алгоритмов и нечеткой логики.
Разработка способов автоматического подбора параметров и методов самоадаптации эволюционного алгоритма под решаемую задачу.
Разработка алгоритма решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.
Создание программного обеспечения, реализующего разработанные алгоритмы.
7. Применение разработанного программного обеспечения для решения
прикладных оптимизационных задач.
Методы исследования. В диссертационной работе для решения поставленных задач используются методы системного анализа и проектирования, теории множеств и теории алгоритмов, нечеткой логики и теории вероятностей, эволюционного моделирования и инженерии знаний. Результаты экспериментов обрабатывались с использованием методов математической статистики.
Научная новизна диссертации определяется, в первую очередь, разработкой гибридных систем, сочетающих методы эволюционных алгоритмов и нечеткой логики. Новыми являются:
Эволюционный алгоритм на базе недарвиновских моделей эволюции;
Эволюционный алгоритм, использующий аппарат нечеткой логики для кодирования хромосом, а также реализации генетических операторов;
Метод автоматического подбора параметров эволюционного алгоритма на основе баз знаний;
Архитектура инструментальной среды поддержки эволюционного проектирования.
Практическая ценность работы связана с построением комплекса эволюционных алгоритмов и разработкой инструментальной среды поддержки ЭП, реализующей предлагаемые схемы и алгоритмы. В частности, прикладную значимость имеет алгоритм управления запасами при оптимизации раскроя ленточного материала на основе гибридных систем эволюционного моделирования.
Внедрение и реализация результатов. Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении хоздоговорной тематики Отдела «Компьютерные системы автоматизации» НУК РК МГТУ им. Н.Э.Баумана. Результаты диссертации также использованы при выполнении работ по грантам Российского фонда фундаментальных исследований (проекты №02-01-00784, 03-07-90012, 04-01-00306, 05-01-00514).
Результаты исследований, проведенных в диссертационной работе, были внедрены на «ОАО Коломенский завод РТИ». Кроме того, результаты работы нашли применение в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана и кафедры САПР ТРТУ.
Достоверность научных положений и выводов диссертации подтверждается результатами вычислительных экспериментов на тестовых и практических задачах, а также актами о внедрении. Акты о внедрении и использовании результатов работы, а также копия авторского свидетельства (Роспатент) представлены в Приложении к диссертации.
Апробация работы. Основные результаты работы докладывались на: Пятом международном симпозиуме «Интеллектуальные системы» (INTELS' 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 библиографических наименования. На защиту выносятся:
Архитектура эволюционных алгоритмов на основе недарвиновских моделей эволюции.
Архитектуры гибридных систем на основе эволюционных алгоритмов и нечеткой логики.
Метод автоматического подбора параметров и адаптации параметров эволюционного алгоритма на основе баз знаний.
Архитектура инструментальной среды поддержки эволюционного проектирования.
Алгоритм решения задачи комплексной организации управления запасами при оптимизации раскроя ленточного материала.
Во введении обоснована актуальность диссертационной работы, сформулированы цель исследования и его основные задачи, указаны научные положения, выносимые на защиту, приведены сведения о практической ценности и внедрении.
В первой главе диссертации приводится постановка задач исследования и обзор методов решения данных задач. Рассматриваются актуальные проблемы информатики и разработки САПР, в том числе инновационные стратегии проектирования. Показано, что эволюционное проектирование является перспективным направлением развития САПР, связанным с применением в них бионических подходов и методов. Отмечаются недостатки классических генетических алгоритмов, являющихся основой эволюционного проектирования. Для устранения предлагаемых недостатков предлагается использование недарвиновских моделей эволюции и гибридных систем с их использованием. Показана перспективность разработки неоднородных гибридных систем с использованием генетических алгоритмов. Описаны существующие программные средства проектирования и реализации генетических алгоритмов (ГА) и показаны их недостатки.
Во второй главе описываются предлагаемые варианты реализации недарвиновских моделей эволюции в генетических алгоритмах, вводится понятие вида. С использованием понятия вида определяется операция межвидового скрещивания (гибридогенез) и предлагаются различные варианты его реализации. Рассматриваются варианты построения гибридного генетического алгоритма на базе различных моделей эволюции. Также во второй главе описывается разработанная автором гибридная система на основе двух разнородных подходов - нечеткой логики и эволюционного моделирования - нечеткий генетический алгоритм. Предлагаются способы реализации основных генетических операторов в нечетком генетическом алгоритме. Описывается способ подбора и адаптации параметров генетического алгоритма под решаемую задачу на основе баз знаний, в том числе на индивидуальном уровне.
В третьей главе описывается разработанная инструментальная среда поддержки эволюционного проектирования - «GenSearch». Рассмотрены ее структура, состав и назначение каждого блока. Приведен возможный способ организации генетического поиска с ее использованием.
В четвертой главе приведены результаты исследований разработанных алгоритмов на тестовых и практических производственных задачах. Показана эффективность нечеткого ГА на тестовых непрерывных функциях. Исследованы различные способы применения базы знаний для подбора и адаптации параметров ГА и показано повышение эффективности ГА при ее использовании. На примере практической производственной задачи управления запасами при раскрое ленточного материала продемонстрирована эффективность разработанных алгоритмов.
В заключении содержатся основные выводы и результаты диссертации.
В приложении 1 приведена копия авторского свидетельства (Роспатент) на инструментальную среду «GenSearch». В приложении 2 приведены копии актов о внедрении и использовании работы.
Применение принципов эволюции при построении алгоритмов оптимизации
Как было сказано выше, эволюционное проектирование лежит на стыке теории и методологии автоматизированного проектирования, разработки теоретических основ информатики и биологических учений об эволюции. Рассмотрим подробнее биологические учения об эволюции.
В биологии и ряде других научных дисциплин принято считать, что эволюция (от лат. Evolutio - развертывание, развитие) есть необратимое историческое развитие естественных и искусственных систем [17]. Ранее эволюцию противопоставляли революции - быстрым и значительным по масштабу изменениям. В настоящее время стало ясно, что процесс развития естественных систем (ЕС) и искусственных систем (ИС) слагается из изменений как постепенных, так и резких, как быстрых, так и длящихся на протяжении жизни многих поколений [21, 40, 59, 62].
Всякая претендующая на полноту и последовательность эволюционная теория должна решить ряд принципиальных проблем, включая [36, 82, 117]: 1) анализ общих причин и движущих сил эволюции организмов; 2) исследование механизмов развития приспособлений (адаптации) организмов к условиям их обитания и изменениям этих условий; 3) определение причин и механизмов возникновения поразительного разнообразия форм организмов, а также причины сходств и различий разных видов и их групп; 4) изучение причины эволюционного прогресса, т.е. нарастающего усложнения и совершенствования организации живых существ в ходе эволюции при одновременном сохранении более примитивных и просто устроенных видов.
С появление первой законченной теории эволюции Ж.-Б. Ламарка прошло почти 200 лет, но до сих пор среди ученых нет однозначного мнения о механизмах эволюции ЕС [24, 35, 79, 82]. Рассмотрим основные классы эволюционных учений.
Ламаркизм
Первая наиболее законченная теория эволюции связывается с именем Ж.-Б. Ламарка [73]. Еще в 1809 г. он предположил, что все живые организмы целесообразно приспосабливаются к условиям среды, а характеристики, приобретенные организмом в течение жизни, наследуются потомками. Причинами эволюции Ж.-Б.Ламарк считал стремление всех живых организмов к прогрессу, развитию от простого к сложному, а также целесообразные изменения организмов, направленные на приспособление к внешним условиям. Эти изменения, как утверждал Ж.-Б. Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков. Отметим также, что для теории Ламарка характерна концентрация внимания на отдельном организме, рассматриваемом вне его связей с другими особями того же вида, т.е., говоря современным языком, отсутствие популяционного подхода, непонимание эволюционной роли биологического вида и составляющих его популяций. В текущий момент теория Ламарка отвергается большинством ученых, но появились ряд учений, успешно использующих ее отдельные части: неоламаркизм, органицизм, психоламаркизм [82].
В свое время Р. Гольдшмидт обратил внимание на удивительный параллелизм между фенотипическими проявлениями модификационной и наследственной изменчивости. Одно и то же состояние фенотипических признаков у разных особей данного вида может формироваться по-разному: у одних особей - как модификационная вариация, проявляющаяся лишь в определенных условиях, у других - как единственно возможный вариант признака. Если в популяции, где данный признак первоначально был одним из модификационных вариантов нормы реакции, появляется мутация, обусловливающая более высокую приспособленность, возникает иллюзия "превращения" ненаследственной модификации в наследственный признак {"эффект Болдуина") [82], т. е. "унаследования приобретенного соматического признака" в духе ламаркизма. Дарвинизм
Теория Чарльза Дарвина (дарвинизм), известная под названием теории естественного отбора, является наиболее законченной теорией эволюции [37]. Согласно этой теории (в изложении И.И.Шмальгаузена [116]), основными условиями эволюции являются: 1) наследственная изменчивость, т.е. мутирование, понимаемое как предпосылка эволюции, ее материал; 2) борьба за существование как контролирующий и направляющий фактор эволюции; 3) естественный отбор как преобразующий фактор эволюции. В [79] в качестве одного из главных оснований «универсального эволюционизма» берется дарвиновская триада: изменчивость, наследственность, отбор.
Вид и межвидовая гибридизация в генетических алгоритмах
Рассмотрим способы проведения гибридизации в ГА.
В самом простом случае, если оба вида используют одинаковый способ кодирования и в хромосоме хранятся только значения переменных оптимизируемой задачи, то в результате скрещивания двух хромосом разных видов будет происходить обмен генотипом, без изменения поведения хромосомы. Оператор кроссинговера определяется оператором кроссинговера, соответствующим лучшей из хромосом родителей. Два получаемых потомка будут относиться к разным видам родителей. Таким образом, мы сохраняем видовое разнообразие в популяции. Операции мутации, инверсии и т.д. будут определяться видом данного потомка.
При использовании в родителях разных типов кодирования может стать невозможным проведение операции скрещивания между родителями. В природе в таком случае скрещивание либо не происходит, либо появившийся потомок не выживает. В ГА нереализуемость оператора кроссинговера к обоим родителям приводит к необходимости использования гибридизации только между родственными видами, что противоречит самой идее межвидового скрещивания.
Для проведения гибридизации между любыми двумя видами предлагается два способа. В первом случае хромосома на всем протяжении жизненного цикла относится к определенному виду, во втором случае в хромосоме хранится непосредственно генотип, а вид хромосомы определяется на каждом поколении.
Структура генетического поиска в первом случае может быть описана следующим образом:
1. В начальный момент случайным образом создаем популяцию. Хромосомы закодированы вещественным кодированием. Каждая хромосома относится к определенному виду. Количество видов и размер каждого вида определяется БЗ или экспертом.
2. Вычисляем функцию пригодности каждой хромосомы.
3. Выбираем случайным образом хромосому R\. В соответствии со способом выбора родительской пары, определяемым видом хромосомы Rb выбираем второго родителя R2.
4. Пусть хромосома Rj обладает большей функцией пригодности. Определяем тип оператора кроссинговера, соответствующего виду хромосомы Ri. В зависимости от типа оператора кроссинговера производим перекодирование хромосом R) и R2 в битовое или другое кодирование, соответствующее выбранному оператору кроссинговера. Производим оператор кроссинговера и получаем хромосомы R j и R 2. Будем считать, что хромосома R i принадлежит виду хромосомы Ri, a R — R2.
5. Для хромосом R i( R 2 выполняем мутацию, инверсию и другие ГО, определяемые их видами. 6. Производим перекодирование хромосом R\ R2 в вещественное кодирование и вычисляем функцию пригодности. 7. Выполняем оператор отбора, определенный для всей популяции. 8. Продолжаем цикл генетического поиска (пункты 3-7) до выполнения условия останова.
За счет хранения переменных в вещественном формате данный способ позволяет проводить гибридизацию между любыми видами. Временные затраты на проведения дополнительной операции кодирования/ декодирования являются незначительными по сравнению с затратами на вычисление функции пригодности в прикладных задачах.
Второй способ проведения гибридизации подразумевает использование не гаплоидных, а диплоидных хромосом [23]. В одной из хромосом будут храниться переменные оптимизируемой задачи (популяция Рі), а в другой -набор признаков, характеризующих данный вид (популяция Р2). Количество хромосом в обеих популяциях одинаково.
Здесь Xi, ...,Хт - действительные переменные оптимизируемой задачи, m - количество переменных оптимизируемой задачи, Qb ..., Qk — признаки, характеризующие поведение данного вида, а именно способ кодирования, ГО, дополнительные методы, которые будут применяться при создании и селекции потомка, к — общее количество признаков.
При диплоидном представлении хромосом возможно эволюционное развитие либо двух популяций (Pi и Р2), либо только популяции Рі. В первом случае каждый индивид будет принадлежать отдельному виду, во втором случае число видов остается неизменным на всем протяжении генетического поиска.
Алгоритм генетического поиска в этом случае может быть представлен следующим образом:
1. В начальный момент случайным образом создаем популяцию хромосом переменных (Pi). Хромосомы закодированы вещественным кодированием. Вычисляем функцию пригодности каждой хромосомы.
В соответствии с количеством видов и размером каждого вида создаем хромосомы популяции Рг- Причем количество хромосом i-го вида в популяции Рг будет определять количество хромосом і-го вида в популяции Pj. Функцию пригодности хромосом популяции Р2 устанавливаем равной 0.
Случайным образом выбираем хромосому из популяции Pi — Rn и популяции Р2 — R.12- Эта пара хромосом будет определять первого родителя. В соответствии со способом выбора родительской пары, закодированным в хромосоме Ri2, выбираем хромосомы из популяций Pi (R21) И P2(R22).
Пусть хромосома Rn обладает большей функцией пригодности. Тогда из хромосомы Rj2 определяем тип оператора кроссинговера. В зависимости от типа оператора кроссинговера производим перекодирование хромосом Rn, R21 в битовое или другое кодирование, соответствующее выбранному оператору кроссинговера. Выполняем операцию кроссинговера над парами хромосом Ru, R12 и R21, R22 (если популяция Рг эволюционирует) и получаем хромосомы R n,R i2, R 21, R 22 Для каждой из хромосом R n, R n, R 2i R 22 выполняем мутацию, инверсию и другие ГО, определяемые хромосомами R21, R22 соответственно.
Производим перекодирование хромосом R n, R 12 в вещественное кодирование и вычисляем функцию пригодности. Значение функции пригодности хромосом R 2i, R 22 будет равно значению функции пригодности хромосом R n, R n соответственно. Помещаем полученные хромосомы в популяции Р і и Р г соответственно. Выполняем оператор отбора. Продолжаем цикл генетического поиска (пункты 3-8) до выполнения условия останова.
Основные характеристики инструментальной среды «GenSearch»
Для реализации различных стратегий и методов эволюционного проектирования необходима разработка инструментальной среды поддержки ЭП, обеспечивающей возможность рационального выбора конкретных моделей эволюции, их подбора под решаемую задачу, позволяющей осуществлять быстрое построение и настройку параметров генетических алгоритмов и эволюционных стратегий, средств генетического и эволюционного программирования. Так в настоящее время предложено большое количество различных реализаций ГО и схем ГА, способов построения гибридных систем с использованием генетического поиска и т.д. В то же время, многие предлагаемые схемы поиска являются чисто теоретическими разработками, не подтвержденными тестированием. Другие предлагаемые модели поиска опробованы на тестовых задачах, но их применение в решении практических задач затруднено ввиду отсутствия или недостаточной гибкости соответствующих программных систем. Как было описано в разделе 1.4, существующие на текущий момент программные средства, реализующие генетический поиск, обладают рядом существенных недостатков. Среди них необходимо отметить [68]: жесткую привязку разработанного ПО к задаче на этапах кодирования и декодирования ее решений в виде генов и хромосом; осуществление программной реализации ГА практически с нуля; закрытость разработанных программ как для доработки, так и для интеграции с другими программами; слабую реализацию идеи сохранения результатов поиска и промежуточных состояний популяции и, следовательно, невозможность анализа этой информации в дальнейшем; малое количество реализованных ГО.
В [68] предложена общая архитектура среды поддержки ГА (СПГА), состоящая из двух частей: общесистемная (управляющая) среда, которая включает управляющую программу (монитор), базу данных и знаний СПГА, представляющую собой базу данных (БД) и знаний (БЗ) о ГО, процедурах генетического поиска и ГА (со своими системами управления БД и БЗ), а также среду сборки рабочих программ, формируемых ГА; среда поддержки действий пользователя, включающая интерфейсы и среды поддержки четырех основных групп действий пользователя при построении новых ГА: среда выбора варианта реализации искомого элемента ГА с использованием соответствующего конструктора элемента; среда описания функции элемента ГА с использованием конструктора описания программы его работы на выбранном языке программирования процедурного или сценарного типа; среда настройки параметров разработанных (выбранных) ГО и ГА с помощью соответствующих диалоговых окон; среда потоков ввода-вывода рабочих программ ГА, обеспечивающая подготовку определенных форматов исходных данных для решения конкретных задач, а также графическую или иную интерпретацию результатов генетического поиска (на основе типовых вариантов декодирования хромосом).
С теоретической точки зрения предлагаемая структура позволяет устранить практически все описанные выше недостатки, но сложность ее практической реализации является ее существенным недостатком. Кроме того, практическое осуществление ЭП требует поддержки различных методов эволюционного моделирования.
Исходя из вышеописанного, представляется перспективной разработка инструментальной среды поддержки ЭП, удовлетворяющей следующим требованиям: возможность встраивания инструментальной среды в различные системы САПР как блока проектирования и/ или оптимизации; простота настройки генетического поиска, доступная для не специалиста; наличие блока подбора и адаптации параметров ГА (ЭА, ЭС) и ГО под решаемую задачу; возможность использования внешних функций, реализующих ГО, способы кодирования, расчет функций пригодности; наличие встроенных библиотек ГО, типов кодирования, тестовых функций с возможностью гибкой настройки ГО и использованием внешних, по отношению к инструментальной среде, функций по проверке и коррекции результата применения встроенных ГО; возможность запуска ГА с созданной внешними средствами или ранее сохраненной начальной популяцией; наличие блока анализа исходных данных, сохранения, обработки и анализа результатов с расчетом основных статистических данных; простота разработка ИС.
Исследование эффективности нечеткого генетического
Исследование нечеткого генетического алгоритма проводилось на непрерывных тестовых функциях F1-F3. Исследовались 3 основные характеристики НГА: 1. Нечеткое кодирование; 2. Нечеткие ГО: мутация и кроссинговер; 3. Адаптация параметров на индивидуальном и популяционном уровне с использованием БЗ.
Параметры ГА при исследовании были следующими: количество популяций - 1; размер популяции - 250 хромосом; количество поколений - 250 или при достижении критерия останова, определяемого БЗ; точность решения -0.001; выбор родительской пары - дальнее родство на фенотипе; отбор - «с вытеснением», количество повторяющихся хромосом — не более 25; количество запусков - 20; вероятность кроссинговера — 1 (может изменяться при использовании БЗ); вероятность мутации- 0.1 (может изменяться при использовании БЗ); «встряхивание» популяции каждые 5 поколений с замещением 10% хромосом. При использовании БЗ частота «встряхивания» определяется БЗ.
Отсутствие в данном списке классических реализаций кроссинговера (одноточечный и двухточечный) обусловлено проведенными ранее исследованиями [58], доказавшими, что оператор рекомбинация показывает лучшие результаты по сравнению с классическими схемами. Результаты исследования представлены в таблицах 4.2-4.4 и на рис.4.2. Для всех случаев мутация - вещественная.
Исследование эффективности подбора параметров ГА с помощью базы знаний на популяционном и индивидуальном уровне проводилось в двух режимах: при начале работы ГА с параметрами, являющимися наиболее подходящими для оптимизации данной функции на основе ранее проведенных исследований (см. [32, 58]); при начале работы ГА с параметрами, являющимися наименее подходящими для оптимизации данной функции на основе ранее проведенных исследований (см. [32, 58]). Сравнение полученных результатов позволит сделать вывод о возможности базы знаний подобрать наиболее близкие к оптимальным параметрам. Результаты исследований приведены в таблицах 4.6-4.8 и на рис.4.4 (для функции F3 на гистограмме при работе без ГА с худшими начальными параметрами значение ФП показано «-3», вместо «-53» для увеличения масштаба и улучшения читаемости диаграммы). Для оценки эффективности работы критерия останова приводится среднее количество вычислений функции пригодности за один запуск. Для оценки временных затрат на работу БЗ на популяционном и индивидуальном уровне приводится время работы ГА.
Для функций F1 и F2 при начале работы с наиболее подходящими параметрами результаты во всех режимах практически одинаковы, но за счет наличия в БЗ правил по определению критерия останова количество вычислений функций сократилось почти в 2 раза, а время работы -практически на 40%. При начале работы с наименее подходящими параметрами отсутствие БЗ приводит к неудовлетворительным результатам. Использование БЗ с подбором параметров на индивидуальном уровне результаты значительно лучше, чем при использовании адаптации только на популяционном уровне. Следует отметить, что при различных начальных условиях при использовании БЗ практически не произошло увеличения времени работы ГА, но ухудшились результаты работы ГА, что говорит о том, что БЗ подобрала параметры, не являющиеся наиболее подходящими, но сделала это довольно быстро.
Для функции F3 ситуация немного отличается. Во всех режимах работы результаты работы ГА были практически одинаковыми за исключением режима без БЗ с началом работы при наименее подходящих параметрах. Но использование БЗ позволило сократить почти в 3 раза количество вычислений функций при подходящих начальных параметрах. При наименее подходящих параметрах БЗ смогла найти практически лучшие параметры, но на это пришлось потратить почти в 2 раза больше времени.
С целью оценки эффективности разработанных алгоритмов в условиях реальной жизни рассмотрим практическую задачу оптимизации в рамках проектирования производства - управление запасами при оптимизации раскроя ленточного материала. Следует отметить, что для решения данной задачи необходимо реализовывать поиск в больших многомерных пространствах, что делает невозможным использование точных математических методов оптимизации.
Управление запасами — это балансирование между двумя целями, взаимоисключающими друг друга в своих полярных точках: сокращение совокупных затрат, направленных на содержание запасов, и обеспечение максимальной надежности производственного процесса. В настоящее время разработано большое количество систем управления материальными запасами, позволяющими сократить затраты на создание и поддержание запасов, однако эти системы не всегда соответствуют специфическим условиям функционирования конкретного предприятия.
Для предприятия, имеющего в своем составе цех штамповки, такой специфичной задачей является задача раскроя. Управление запасами и решение задачи раскроя на таких производствах осложняется следующими обстоятельствами: большое количество типоразмеров заготовок и, следовательно, большая размерность задачи управления запасами (десятки и сотни типоразмеров заготовок); случайный график поставок, обусловленный случайностью вырубки заготовок из полосы, что приводит к сложности расчета издержек производства и хранения; требовательность к вычислительным ресурсам, как в задаче управления запасами, так и в задаче раскроя.
Сегодня существующие алгоритмы управления запасами и алгоритмы раскроя — это слабосвязанные между собой методы, что, затрудняя их интеграцию в единую систему, не позволяет устранить описанные выше сложности.
Таким образом, разработка алгоритмов, позволяющих обеспечить эффективное управление запасами при одновременной оптимизации ленточного раскроя, является актуальной теоретической и важной прикладной проблемой.
