Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Отмечаются следующие основные свойства сложных систем:
- целостность и членимость,
- наличие существенных устойчивых связей (отношений) между элементами,
- организация и структура,
- интегративные качества, функциональность
Сложные системы как объект моделирования имеют следующие характерные особенности: уникальность, слабая структурированность, разнородность подсистем и элементов, составляющих систему, изменчивость во времени, случайность и неопределенность факторов, действующих в системе, многокритериальность оценок процессов, протекающих в системе.
Сложные системы, как правило, уникальны. Следствием этого на практике является необходимость строить новые модели при проектировании таких систем. Поскольку изучаемые системы уникальны, то процесс накопления и систематизации знаний о них затруднен. Слабо изучены сами процессы, протекающие в сложных системах. При идентификации сложных систем присутствует большая доля субъективных экспертных знаний о ней. Такие системы слабопредсказуемы. Для них характерна слабая структурированность теоретических и фактических знаний. Наличие интегративных качеств системы предопределяет важный методологический вывод: сложная система не сводится к простой совокупности элементов и, расчленяя систему на отдельные части, изучая каждую из них в отдельности, нельзя познать свойства системы в целом. Поэтому описание отдельных подсистем необходимо выполнять с учетом их места во всей системе в целом, и наоборот, система в целом исследуется с учетом свойств отдельных подсистем. Одну из основных черт сложных систем составляет взаимодействие выделенных подсистем. Необходимо учитывать результат воздействия одной подсистемы на другую и их взаимодействие с внешней средой. Исследователи отмечают наличие большого числа взаимосвязанных подсистем, многомерность системы, обусловленную большим числом связей между подсистемами, что затрудняет идентификацию моделируемых объектов. Отметим также, что расчленение сложной системы на подсистемы зависит от целей создания системы и взглядов исследователя на нее. Разнородность подсистем и элементов, составляющих систему, определяется и многообразием природы (физической разнородностью подсистем), и разнородностью математических схем, описывающих функционирование различных элементов, а также одних и тех же элементов на различных уровнях изучения. Разнообразие процессов, протекающих в системе, вызывает необходимость исследовать систему в динамике с учетом поведенческих аспектов. Случайность и неопределенность факторов, действующих в изучаемой системе, приводит к резкому усложнению задач и увеличивает трудоемкость исследований (необходимость получения представительного набора данных). Требуется учитывать большое количество действующих в системе факторов. Многокритериальностъ оценок процессов, протекающих в системе, приводит к невозможности однозначной оценки (выбора единого обобщенного критерия оптимальности). Применение многокритериальное™ объясняется следующими обстоятельствами:
- наличием множества подсистем, каждая из которых, вообще говоря, имеет свои цели, оценивается но своим локальным критериям;
- множественностью показателей, характеризующих работу всей системы (показатели, как правило, противоречивы) — в этом случае выбирается компромиссный вариант;
- наличием неформал изуемых критериев, используемых при принятии решений, основанных на практическом опыте лиц, принимающих решение.
При системном подходе процесс исследования системы носит итерационный характер. Исходная модель усложняется с увеличением детализации. Однако создание полной модели системы бесполезно, поскольку она будет столь же сложна в изучении, как и сама система. Следствием этого является необходимость использования при анализе системы комплекса моделей. Различные модели могут отражать как разные стороны функционирования системы, так и разные уровни отображения одних и тех же процессов.
Рассмотренные особенности исследования сложных систем обуславливают потребность в специальных способах построения и анализа их моделей. Традиционные аналитические модели здесь беспомощны - нужны специальные компьютерные технологии.
Методологией исследования сложных систем является системный анализ. Компьютерное моделирование служит одним из важнейших инструментов прикладного системного анализа. Наиболее эффективным и универсальным вариантом компьютерного моделирования в области исследования и управления сложными системами является имитационное моделирование.
Модель представляет собой абстрактное описание системы (объекта, процесса, проблемы, понятия) в некоторой форме, отличной от формы ее реального существования. Итак, в процессе моделирования всегда существуют оригинал (объект) и модель, которая воспроизводит некоторые черты объекта. Моделирование успешно используется при решении большого круга задач: обучение, описание, измерение, оценивание, прогнозирование, планирование, управление, синтез, идентификация и др. Моделирование становится мощным средством в задачах анализа и синтеза сложных технических и экономических систем, а также поиска эффективных решений. Сложные системы необязательно требуют сложных моделей. Надо стремиться создавать простые модели. Моделирование основано на наличии у многообразия естественных и искусственных систем, отличающихся как целевым назначением, так и физическим воплощением, сходства или подобия некоторых свойств: геометрических, структурных, функциональных, поведенческих. Это сходство может быть полным (изоморфизм) и частичным (гомоморфизм).
Исследуя современные сложные системы, человечество придумало различные классы моделей. Развитие информационных технологий можно в известном смысле интерпретировать как возможность реализации моделей различного вида в рамках систем различного назначения: информационные системы, системы автоматизированного проектирования, системы искусственного интеллекта, системы поддержки принятия решений. В основе этих систем лежат модели различных типов: семантические, логические, математические и т. п. Приведем классификацию основных видов моделирования:
- концептуальное моделирование предполагает представление системы с помощью специальных знаков, символов, операций над ними или с помощью естественных или искусственных языков;
- физическое моделирование предполагает, что моделируемый объект или процесс воспроизводится исходя из соотношения подобия, вытекающего из схожести физических явлений;
- в структурно-функциональном моделировании моделями являются схемы (блок-схемы), графики, диаграммы, таблицы, рисунки со специальными правилами их объединения и преобразования;
- математическое (логико-математическое) моделирование предполагает, что построение модели осуществляется средствами математики и логики;
- в имитационном (программном) моделировании логико-математиче ская модель исследуемой системы представляет собой алгоритм функционирования системы, программно реализуемый на компьютере.
Указанные виды моделирования могут применяться по отдельности или одновременно в некоторой комбинации (например, в имитационном моделировании используются практически все перечисленные виды моделирования или их отдельные приемы). Доминирующей тенденцией сегодня является взаимопроникновение всех видов моделирования, симбиоз различных информационных технологий в области моделирования, особенно для сложных приложений и комплексных проектов по моделированию. Так, например, имитационное моделирование включает в себя концептуальное моделирование (на ранних этапах формирования имитационной модели) и логико-математическое (включая методы искусственного интеллекта) — для описания отдельных подсистем модели, а также в процедурах обработки и анализа результатов вычислительного эксперимента и принятия решений. Технология проведения и планирования вычислительного эксперимента с соответствующими математическими методами привнесена в имитационное моделирование из физического (натурного). Наконец, структурно-функциональное моделирование используется как при создании стратифицированного описания многомодельных комплексов, так и для формирования различных диаграммных представлений при создании имитационных моделей.
Под термином «компьютерная модель», чаще всего понимают:
- условный образ объекта либо некоторой системы объектов или процессов, описанный с помощью блок-схем, диаграмм, графиков, рисунков, анимационных фрагментов, гипертекстов и т. д. и отображающий структуру и взаимосвязи между элементами объекта. Компьютерные модели такого вида будем называть структурно-функциональными;
- отдельную программу (совокупность программ, программный комплекс), позволяющую с помощью последовательности вычислений и графического отображения их результатов воспроизводить (имитировать) процессы функционирования объекта, системы объектов при условии воздействия на объект различных, как правило случайных факторов. Такие модели будем называть имитационными.
Суть компьютерного моделирования заключена в получении количественных и качественных результатов на имеющейся модели. Качественные результаты анализа обнаруживают неизвестные ранее свойства сложной системы: ее структуру, динамику развития, устойчивость, целостность. Количественные выводы в основном носят характер анализа существующей системы или прогноза будущих значений некоторых переменных. Кстати, возможность получения не только качественных, но и количественных результатов составляет существенное отличие имитационного моделирования от структурно-функционального.
Схема включает:
1 определение предметной (проблемной) области системы;
2 описание объекта моделирования;
3 определе¬ние цели моделирования;
4 определение требований к моделям;
5 выбор формы представления модели;
6 выбор вида описания модели;
7 определение характера реализации модели;
8 выбор метода исследования модели.
Первые три этапа характеризуют объект и цель исследования и практи¬чески определяют следующие этапы моделирования. Большое значение име¬ет корректное описание объекта и формулировка цели моделирования.
1. Определение предметной области системы. Предметная область ис¬следуемой системы накладывает определенный отпечаток на модель. Физи¬ческие, химические, технические, технологические, информационные, био¬логические, экологические, экономические, социальные и другие особенно¬сти должны быть отражены в модели системы.
2. Описание объекта моделирования. В качестве объекта моделирования в процессе моделирования выступает не вся система, а ее «срез» — элемент, структура, отношение, организация, функция, отдельные процессы поведе¬ния и развития и т. д.
3. Определение цели моделирования. Очень важно правильно обозначить и сформулировать проблему, четко задать цель исследования, проводимого с помощью моделирования. Целенаправленная модель представляет собой за¬мену действительности с той степенью абстракции, которая полезнее для по¬ставленной цели. Иначе говоря, модель прежде всего должна отражать те существенные свойства, те стороны моделируемого объекта, которые опре¬делены практической задачей. Остальными свойствами можно пренебречь.
4. Определение требований к моделям. Моделирование связано с реше¬нием реальных задач, и нужно быть уверенным, что результаты точно отра¬жают истинное положение вещей, т. е. что модель адекватна действительно¬сти. Хорошая модель должна удовлетворять некоторым общепринятым тре¬бованиям: адекватной; надежной в смысле гарантии от абсурдных ответов; простой и понятной пользователю; целенаправленной; удобной в управлении и обращении; функционально полной с точки зрения возможностей решения задачи; адаптивной, позволяющей легко переходить к другим модификациям или обновлять данные.
В зависимости от целевой направленности модели задаются специальные требования к самим моделям. Наиболее характерными требованиями являются целостность; отражение информационных свойств; многоуровневость; множе¬ственность (многомодельностъ); расширяемость; универсальность (абстракт-ность); осуществимость (реальная возможность построения самой модели и ее исследования); реализуемость (возможность материализации модели в виде ре¬альной системы в задачах проектирования); эффективность (затраты времен¬ных, трудовых, материальных и других видов ресурсов на построение моделей и проведение экспериментов находится в допустимых пределах или оправда¬ны). Значимость или приоритетность требований к модели непосредственно вытекают из назначения модели.
5.Выбор формы представления модели. Цель моделирования и задание требований к модели, безусловно, определяют форму представления модели. Любая модель (прежде чем стать объективно существующим предметом) должна быть конструктивно разработана, существовать в мысленной форме, далее - переведена в знаковую форму и, наконец, реализована.
6.Выбор вида описания модели. Например, для знаковых форм такими описаниями являются логические или математические модели. Для логиче¬ских моделей определяются отношения и способы представления знаний (исчисление предикатов, семантические сети, фреймы) [1]. Для математиче¬ских моделей - алгебраические и дифференциальные уравнения.
7.Определение характера реализации модели. Характер реализации зна¬ковых моделей бывает аналитическим, машинным и физическим.
8.Выбор метода исследования модели. Для каждого способа реализации модели в зависимости от ее сложности, цели моделирования, степени неоп¬ределенности характеристик модели могут иметь место различные по харак¬теру способы проведения исследований (экспериментов).
Расчетное моделирование применяется при исследовании математиче¬ских моделей и сводится к их машинной реализации при различных число-вых исходных данных. Результаты этих реализаций (расчетов) выдаются в графической или табличной формах. Под статистическим моделированием понимается машинное воспроизведение функционирования вероятностных моделей. Особенностью статисти¬ческого моделирования является случайное задание исходных данных с из¬вестными законами распределения и, как следствие, вероятностное оценива¬ние характеристик исследуемых процессов. Статистическое моделирование является эффективным методом исследования слабоорганизованных систем с несложной логикой функционирования. Для исследования сложных логиче¬ских и логико-математических моделей с неточным заданием исходных дан¬ных применяется имитационное моделирование. Оно не используется в задачах исследования сложных логико-математических моде¬лей в результате проведения экспериментов на модели. Поэтому в имитаци¬онном моделировании важную роль играет не только проведение, но и пла¬нирование экспериментов. Следующим за имитационным по качественному уровню можно назвать самоорганизующееся моделирование, когда функция построения моделей и ее преобразования в процессе экспериментирования и поиска оптимальных моделей возлагается на ЭВМ
Исследуя современные сложные системы, человечество придумало раз¬личные классы моделей. Приведем классификацию основных видов моделирования:
- концептуальное моделирование предполагает представление системы с помощью специальных знаков, символов, операций над ними или с помощью естественных или искусственных языков;
- физическое моделирование предполагает, что моделируемый объект или процесс воспроизводится исходя из соотношения подобия, вытекающего из схожести физических явлений;
- в структурно-функциональном моделировании моделями являются схемы (блок-схемы), графики, диаграммы, таблицы, рисунки со специальны¬ми правилами их объединения и преобразования;
- математическое (логико-математическое) моделирование предпола¬гает, что построение модели осуществляется средствами математики и логики;
- в имитационном (программном) моделировании логико-математическая модель исследуемой системы представляет собой алгоритм функциони¬рования системы, программно реализуемый на компьютере.
Указанные виды моделирования могут применяться по отдельности или одновременно в некоторой комбинации (например, в имитационном модели¬ровании используются практически все перечисленные виды моделирования или их отдельные приемы). Доминирующей тенденцией сегодня является взаимопроникновение всех видов моделирования, симбиоз различных инфор¬мационных технологий в области моделирования, особенно для сложных приложений и комплексных проектов по моделированию. Так, например, имитационное моделирование включает в себя концептуальное моделирова¬ние (на ранних этапах формирования имитационной модели) и логико-математическое (включая методы искусственного интеллекта) — для описания отдельных подсистем модели, а также в процедурах обработки и анализа ре¬зультатов вычислительного эксперимента и принятия решений. Технология проведения и планирования вычислительного эксперимента с соответствую¬щими математическими методами привнесена в имитационное моделирова¬ние из физического (натурного). Наконец, структурно-функциональное мо¬делирование используется как при создании стратифицированного описания многомодельных комплексов, так и для формирования различных диаграмм¬ных представлений при создании имитационных моделей.
Под термином «компьютерная модель», чаще всего понимают:
- условный образ объекта либо некоторой системы объектов или процес¬сов, описанный с помощью блок-схем, диаграмм, графиков, рисунков, ани¬мационных фрагментов, гипертекстов и т. д. и отображающий структуру и взаимосвязи между элементами объекта. Компьютерные модели такого вида будем называть структурно-функциональными;
- отдельную программу (совокупность программ, программный ком¬плекс), позволяющую с помощью последовательности вычислений и графи¬ческого отображения их результатов воспроизводить (имитировать) процес-сы функционирования объекта, системы объектов при условии воздействия на объект различных, как правило случайных факторов. Такие модели будем называть имитационными.
Суть компьютерного моделирования заключена в получении количест¬венных и качественных результатов на имеющейся модели. Качественные результаты анализа обнаруживают неизвестные ранее свойства сложной сис¬темы: ее структуру, динамику развития, устойчивость, целостность. Количе¬ственные выводы в основном носят характер анализа существующей систе¬мы или прогноза будущих значений некоторых переменных. Кстати, воз¬можность получения не только качественных, но и количественных резуль¬татов составляет существенное отличие имитационного моделирования от структурно-функционального.
Метод имитационного моделирования позволяет решать задачи исключительной сложности, обеспечивает имитацию любых многообразных процессов с большим количеством элементов. Отдельные функциональные зависимости в таких моделях могут описываться весьма громоздкими математическими соотношениями, и поэтому имитационное моделирование эффективно используется в задачах исследования систем со сложной структурой для решения конкретных проблем.
Имитационная модель содержит элементы непрерывного и дискретного действия, поэтому применяется для исследования динамических систем, если требуется анализ узких мест, исследование динамики функционирования системы, если желательно наблюдать на имитационной модели ход процесса в течение определенного периода времени.
Имитационное моделирование - эффективный аппарат исследования стохастических систем, когда исследуемая система может быть подвержена влиянию многочисленных случайных факторов сложной природы. Имеется возможность проводить исследование в условиях неопределенности, при неполных и неточных данных.
Имитационное моделирование является наиболее ценным, системообразующим звеном в системах поддержки принятия решений, поскольку позволяет исследовать большое число альтернатив (вариантов решений), проигрывать различные сценарии при любых входных данных. Главное преимущество имитационного моделирования состоит в том, что исследователь для проверки новых стратегий и принятия решений при изучении возможных ситуаций всегда может получить ответ на вопрос «Что будет, если'?». Имитационная модель позволяет прогнозировать состояние системы, когда речь идет о проектировании системы или исследуются процессы ее развития (т. е. в тех случаях, когда реальной системы не существует).
В имитационной модели может быть обеспечен различный (в том числе и очень высокий) уровень детализации моделируемых процессов. При этом модель создается поэтапно, постепенно, без существенных изменений - эволюционно.
Метод имитационного моделирования - экспериментальный метод исследования реальной системы по ее имитационной модели, который сочетает особенности экспериментального подхода и специфические условия использования вычислительной техники.
В процессе имитационного моделирования исследователь имеет дело с четырьмя основными элементами: реальной системой, логико-математической моделью моделируемого объекта, имитационной моделью и компьютером, на котором осуществляется имитация - направленный вычислительный эксперимент.
Особенностью имитационного моделирования является то, что имитационная модель позволяет воспроизводить моделируемые объекты: с сохранением их логической структуры или с сохранением поведенческих свойств (последовательности чередования во времени событий, происходящих в системе), т. е. динамики взаимодействий.
Построение имитационной модели заключается в описании структуры и процессов функционирования моделируемого объекта или системы. В описании имитационной модели выделяют две составляющие: статическое и динамическое описания системы. Статическое описание является описанием ее структуры. Динамическое описание системы представляет собой описание динамики взаимодействий ее элементов. Отличительной особенностью метода имитационного моделирования является возможность описания и воспроизведения взаимодействия между различными элементами системы.
Ключевым моментом в имитационном моделировании является выделение и описание состояний системы. Система характеризуется набором переменных состояний, каждая комбинация которых описывает конкретное состояние. Следовательно, путем изменения значений этих переменных можно имитировать переход системы из одного состояния в другое. Таким образом, имитационное моделирование - это представление динамического поведения системы посредством продвижения ее от одного состояния к другому в соответствии с хорошо определенными операционными правилами. Эти изменения состояний могут происходить либо непрерывно, либо в дискретные моменты времени. Таким образом, имитационное моделирование - это динамическое отражение изменений состояния системы с течением времени.
При имитационном моделировании структура моделируемой системы адекватно отображается в модели, а процессы её функционирования проигрываются (имитируются) на построенной модели. Поэтому построение имитационной модели заключается в описании структуры и процессов функционирования моделируемого объекта или системы. В описании имитационной модели выделяют две составляющие: статическое и динамическое описание системы. Статическое описание является описанием её структуры. При разработке имитационной модели необходимо выполнить структурный анализ моделируемых процессов. Динамическое описание системы представляет собой описание динамики взаимодействий её элементов. При составлении динамического описания фактически требуется построение функциональной модели моделируемых процессов.
Таким образом, чтобы составить имитационную модель надо:
- представить реальную систему (процесс) как совокупность взаимодействующих элементов.
- алгоритмически описать функционирование отдельных элементов.
- описать процесс взаимодействия различных элементов между собой и с внешней средой.
Ключевым моментом в имитационном моделировании является выделение и описание состояний системы. Система характеризуется набором переменных состояний, каждая комбинация которых описывает конкретное состояние. Следовательно, путем изменения значений этих переменных можно имитировать переход системы из одного состояния в другое. Таким образом, имитационное моделирование - это представление динамического поведения системы посредством продвижения ее от одного состояния к другому в соответствии с хорошо определенными операционными правилами. Эти изменения состояний могут происходить либо непрерывно, либо в дискретные моменты времени. Таким образом, имитационное моделирование - это динамическое отражение изменений состояния системы с течением времени.
Для описания динамики моделируемых процессов в имитационном моделировании реализован механизм задания модельного времени. Эти механизмы встроены в управляющие программы любой системы моделирования. Если бы на ЭВМ имитировалось поведение одного компонента системы, то выполнение действий в имитационной модели можно было бы осуществить последовательно, по пересчёту временной координаты. Чтобы обеспечить имитацию параллельных событий реальной системы, вводят некоторую глобальную переменную t, обеспечивающую синхронизацию всех событий в системе, которую называют модельным(или системным) временем.
Существует два основных способа изменения времени:
1 С помощью фиксированных интервалов времени (метод фиксированного шага) – отсчёт системного времени идёт через интервалы времени определенной длинны.
2 Определение шага до следующего события (метод переменного шага) – состояние системы изменяется с появлением следующего существенного события не зависимо от времени его появления.
Метод переменного шага:
Например, существует последовательность событий ei (event). Происходит приращение времени на один такт и указываются моменты наступления события(ei – событие, а t – время).
Имитационное время приращения при изменении сдвигается вперед точно на момент наступления самого раннего из последующих событий: S1=e1; S2=e2…
Метод переменного шага эффективен при неравномерном распределении событий во времени или при большой величине математического ожидания.
Метод фиксированного шага:
Для метода фиксированного шага необходимо выбрать шаг ∆t. Моменты модельного времени будут кратны ∆t. Событие определяется как S_k=k∆t, а время t_i=i∆t.
Метод фиксированного шага применяется в тех случаях, когда события распределены равномерно и несложно подобрать шаг изменения временной координаты; трудно предсказать появление определенных событий; событий очень много и они появляются группами.
Имитационное моделирование — это экспериментальный метод исследования реальной системы по ее имитационной модели. Суть исследования реальной системы по ее имитационной модели состоит в получении (сборе) данных о функционировании системы в результате проведения эксперимента на имитационной модели.
Имитационные модели - это модели прогонного типа, у которых есть вход и выход, т. е. если подать на вход имитационной модели определенные значения параметров (переменных, структурных взаимосвязей), можно получить результат, который действителен только при этих значениях.
1. Имитационная модель дает результаты, которые действительны только для определенных значений параметров, переменных и структурных взаимосвязей, заложенных в имитационную программу. Изменение параметра или взаимосвязи означает, что имитационная программа должна быть запущена вновь. Поэтому для получения необходимой информации или результатов необходимо осуществлять прогон имитационных моделей, а не решать их.
2. Имитационная модель не способна формировать свое собственное решение в том виде, в каком она формируется в аналитических моделях, а может служить в качестве средства для анализа поведения системы в условиях, определяемых экспериментатором.
Эксперимент на модели содержит несколько реализаций, прогонов и предполагает оценивание по данным совокупности (выборки) (для стохастической системы Стохастические системы - системы, динамика которых зависит от случайных факторов, а входные и выходные переменные стохастической модели, как правило, описываются как случайные величины, функции, процессы, последовательности.). В случае детерминированной системы достаточно провести один прогон - по определенным операционным правилам при конкретном наборе параметров.
В имитационном моделировании важным вопросом является не только проведение, но и планирование имитационного эксперимента в соответствии с поставленной целью исследования.
Таким образом, встает проблема организации эксперимента, т. е. выбора метода сбора информации, который дает требуемый (для достижения поставленной цели исследования) ее объем при наименьших затратах. Основная цель - уменьшить временные затраты на эксплуатацию модели, сократить машинное время на имитацию, отражающее затраты ресурса времени ЭВМ на проведение большого количества имитационных прогонов.
Эта проблема получила название стратегического планирования имитационного исследования. Для ее решения используются методы регрессионного анализа, планирования эксперимента и др. Стратегическое планирование - это разработка эффективного плана эксперимента, в результате которого либо выясняется взаимосвязь между управляемыми переменными, либо находится комбинация значений управляемых переменных, минимизирующая или максимизирующая отклик (выход) имитационной модели.
Тактическое планирование, связано с определением способов проведения имитационных прогонов, намеченных планом эксперимента: как провести каждый прогон в рамках составленного плана эксперимента. Здесь определяется длительность прогона, оценивается точность результатов моделирования и др.
Технологическая схема имитационного моделирования включает следующее:
1 - реальная система;
2 - построение логико-математической модели;
3 - разработка моделирующего алгоритма;
4 - построение имитационной (машинной) модели;
5 - планирование и проведение имитационных экспериментов;
6 - обработка и анализ результатов;
7 - выводы о поведении реальной системы (принятие решений).
Вне зависимости от типа моделей ИМ включает в себя ряд основных этапов.
Этапы ИМ.
На первом этапе формулируется проблема, стоящая перед исследователем, и принимается решение о целесообразности применения метода имитационного моделирования.
Затем определяются цели, которые должны быть достигнуты в результате имитации. На этом этапе определяется и детально изучается объект моделирования, те стороны его функционирования, которые представляют интерес для исследования. Результатом этапа является содержательное описание объекта моделирования с указанием целей имитации и тех аспектов функционирования объекта моделирования, которые необходимо изучить на имитационной модели.
Далее следует: изучение проблемной ситуации - определение диагноза и постановка задачи; уточнение целей моделирования; обоснование необходимости моделирования и выбор его метода. На этом этапе формулируются цели моделирования.
Структурирование и формулирование проблемы. Анализ проблемы необходимо начинать с детального изучения всех аспектов функционирования системы. Важно правильно поставить задачи, общая задача моделирования при этом разбивается на частные. Основное смысловое содержание системного подхода к решению проблем моделирования представлено на рисунке
Первый и самый важный шаг при создании любой модели состоит в определении ее целевого назначения. Может быть применен метод декомпозиции целей, предполагающий разделение целого на части: целей - на подцели, задач - на подзадачи, и т. д. (построение дерева целей).
Категории целей в имитационном исследовании.
Оценка. Определяется, насколько хорошо система предлагаемой структуры будет соответствовать некоторым конкретным критериям.
Сравнение альтернатив. Выполняется сопоставление конкурирующих систем, рассчитанных на выполнение определенной функции, или же выполняется сопоставление нескольких предлагаемых рабочих принципов или методик.
Прогноз. Выполняется оценка поведения системы при некотором предполагаемом сочетании рабочих условий.
Анализ чувствительности. Из большого числа действующих факторов выявляются те, которые в наибольшей степени влияют на общее поведение системы.
Выявление функциональных соотношений. Определяются зависимости между двумя или несколькими действующими факторами, с одной стороны, и откликом системы с другой.
Оптимизация. Находится точное определение такого сочетания действующих факторов и их величин, при котором обеспечивается наилучший отклик всей системы в целом.
Формирование критериев. Четкость и однозначность определения критериев влияет на процесс создания модели и экспериментирования с ней; неправильное определение критерия ведет к неправильным выводам.
Концептуалъная модель - логико-математическое описание моделируемой системы в соответствии с формулировкой проблемы. Основное содержание этого этапа - формулировка общего замысла модели, переход от реальной системы к логической схеме ее функционирования. На этом этапе - документированное концептуальное описание плюс выбранный способ формализации моделируемой системы.
Построение концептуальной модели начинается с того, что на основе цели моделирования устанавливаются границы моделируемой системы, определяются воздействия внешней среды. Выдвигаются гипотезы и фиксируются все допущения (предположения), необходимые для построения имитационной модели. Обсуждается уровень детализации моделируемых процессов.
Система есть совокупность взаимосвязанных элементов. Декомпозиция системы (объекта моделирования) или выделение подсистем есть операция анализа. Элементы модели должны соответствовать реально существующим фрагментам в системе.
Описание внешней среды выполняется, поскольку элементы внешней среды оказывают определенное влияние на элементы системы, однако влияние самой системы на них, как правило, незначительно.
При обсуждении уровня детализации модели важно понимать, что в основании всякой декомпозиции лежат два противоречивых принципа: полнота и простота. Критерии эффективности, параметры, переменные модели.
Параметрами являются величины, которые исследователь может выбирать произвольно, в отличие от переменных модели, которые могут принимать только значения, определяемые видом данной функции. В модели различают переменные двух видов: экзогенные и эндогенные. Экзогенные переменные называются также входными. Это означает, что они порождаются вне системы или являются результатом взаимодействия внешних причин. Эндогенными переменными называются переменные, возникающие в системе в результате воздействия внутренних причин.
На третьем этапе имитационного исследования осуществляется формализация объекта моделирования. Процесс формализации сложной системы включает выбор способа формализации и составление формального описания системы.
Основная задача этапа формализации — дать формальное описание сложной системы, свободное от второстепенной информации, имеющейся в содержательном описании, алгоритмическое представление объекта моделирования. Цель формализации - получить формальное представление логико-математической модели, т. е. алгоритмов поведения компонентов сложной системы, и отразить на уровне моделирующего алгоритма вопросы взаимодействия между собой этих компонентов.
На заключительных этапах имитационного моделирования необходимо проводить стратегическое и тактическое планирование имитационного эксперимента (см. 9 вопрос конец). Организация направленного вычислительного эксперимента на имитационной модели предполагает выбор и применение различных аналитических методов для обработки результатов имитационного исследования.
Можно выделить три основных метода создания имитационных моделей:
1) Системная динамика
2) Дискретно-событийное моделирование
3) Агентное моделирование
Первые два – традиционные, в то время как агентное моделирование стало широко распространяться сравнительно недавно (после 2000 г).
Системная динамика и дискретно-событийное моделирование рассматривают систему сверху вниз, работая на так называемом системном уровне. Агентное моделирование сфокусировано на физическом уровне, где важны отдельные физические объекты , их индивидуальное поведение и физические связи, точные размеры, расстояния, временные промежутки. Системная динамика предполагает наивысший уровень абстракции, когда исследователь абстрагируется от индивидуальных объектов и их поведения. Дискретно событийное моделирование оперирует на среднем уровне, т.е. работает с отдельными обьектами, пренебрегая их физическими размерами. Что касается агентного моделирования, оно может применяться практически на любом уровне абстракции и в любых масштабах.
В том случае, если легче описать поведение каждого обьекта индивидуально, чем пытаться загнать их в один процесс – разумнее использовать агентное моделирование. Напротив, если необходимы только общие оценки процессов, то легче будет использовать метод системной динамики.
В дискретных имитационных системах изменение состава и состояния происходит в дискретные моменты времени, называемые событиями. Под событием понимается мгновенное изменение некоторого элемента системы или состояния в целом, произошедшее в результате осуществления множества взаимодействий между компонентами модели в один и тот же момент имитационного времени( рис 3.1).
Событие Si характеризуется: условиями( или законом) возникновения; типом , определяющим порядок обработки ( дисциплину обслуживания) данного события, и нулевой длительностью. Обычно, события подразделяют на две категории:
- события следования, которые управляют инициализацией процессов ( или отдельных работ внутри процесса);
-события изменения состояний (элементов системы или системы в целом).
Как было отмечено, механизм событий используется в качестве основы построения моделей, предназначенных для исследования причинно-следственных связей в системах при отсутствии временных ограничений. К таким задачам можно отнести, например, некоторые задачи оценки надежности.
Функционирование дискретной системы можно описать, определяя изменения состояния системы, происходящие в моменты свершения событий, а также действия, в которых принимают участие элементы системы, определяя процесс, через который проходят элементы.
Процесс – это ориентированная во времени последовательность событий, которая может состоять из нескольких действий.
Эти представления лежат в основе трех альтернативных методологических подходов к построению дискретных имитационных моделей:
- событийный;
-сканирования активностей;
-процессно-ориентированный.
Это основные концепции структуризации для дискретных имитационных моделей. Их основа закладывается в некоторые языки и системы моделирования.
В 1961 г. Джефри Гордон разработал язык моделирования GPSS (General Purpose Simulating System — моделирующая система общего назначения). Язык GPSS отличает удачно сформированная базовая схема структуризации, поддерживающая блочно-ориентированный подход, в рамках которого моделирующий блок имеет свое функциональное назначение и представлен соответствующими функциональными объектами, имеющими аналоги среди элементов систем массовом обслуживания, а также возможности языка дня описания параллельных процессов. Именно такой взгляд на моделируемый объект позволил реализовать идеографический режим формирования дискретной модели, когда модель конструируется из стандартных функциональных блоков, а связи на этих графических конструкциях интерпретируются как маршруты прохождения подвижных объектов в системе.
В языке GPSS реализована блочно-ориентированная концепция структуризации моделируемого процесса, разработанная с ориентацией на описание систем массового обслуживания (СМО). Структура моделируемого процесса изображается в виде потока, проходящего через обслуживающие устройства (ОУ), очереди, ключи и другие элементы СМО.
Модель имеет блочную структуру. Моделируемый процесс представляется как поток заявок в системе обслуживания. Блок интерпретируется как ОУ. В момент выполнения операции он занят, иначе — свободен. Если ОУ' (канал) свободен, то заявки принимается к обслуживанию.
Заявки (транзакты) конкурируют между собой за место в ОУ', образуют очереди перед ОУ, если те заняты. Дуги на блок-схеме — потенциальные потоки заявок между ОУ. Существуют истоки и стоки этих заявок. В таком случае блок-схема модели описывает маршруты движения заявок в системе. Система массового обслуживания - абстрактный объект, в котором выполняется последовательность операций. СМО включает совокупность приборов обслуживания, которые связаны определенным логическим порядком.
В соответствии с этой логикой происходит движение материальных носителей - заявок на обслуживание от канала к каналу.
Структура систем массового обслуживания
Заявка характеризуется моментом появления на входе системы, статусом по отношению к другим заявкам, некоторыми параметрами, определяющими потребности во временных ресурсах на обслуживание. Постоянно поступающие заявки на обслуживание образуют поток заявок - совокупность заявок, распределенную во времени. Поток заявок может быть однородным (с точки зрения обслуживания все заявки равноправны) и неоднородным.
Основной параметр потока заявок - промежуток времени между моментами поступления 2 соседних заявок. Поток заявок может быть стационарным или нестационарным (например, меняющимся в зависимости от времени суток). Поток заявок рассматривается как случайный процесс, характеризующийся функцией распределения периода поступления заявок.
Обслуживание каждой заявки каналом означает задержку в нем заявки на время, равное периоду обслуживания. После обслуживания заявка покидает прибор обслуживания. Таким образом, ОУ характеризуется временем обслуживания заявки. При случайном характере полпоступления заявок образуются очереди. Заявки принимаются к обслуживанию в порядке очереди (FIFO, очереди с приоритетами и др.), в случайном порядке в соответствии с заданными распределениями, по минимальному времени получения отказа и др. Реальный процесс функционирования СМО следует представлять в виде последовательности фаз обслуживания, выполняемых различными устройствами. Примеры многофазного обслуживания: обслуживание покупателей в магазине (прилавок, касса); производственно-технологический процесс (обработка деталей на станках); выполнение типовых проектных процедур в САПР. Причем эти многофазные системы могут иметь сложную структуру (стохастические сети), например:
.
Обслуженная заявка покидает прибор обслуживания и систему (поглотитель заявок) либо движется дальше в соответствии с технологической схемой работы системы. Различают следующие типы СМО:
- одноканальные и многоканальные (по количеству ОУ);
- с ожиданием и без ожидания (с отказами);
- с ограничением на длину очереди (или с ограниченным ожиданием) и без такого ограничения;
- с упорядоченной и с неупорядоченной очередью;
- с приоритетами и без приоритетов.
Любая модель строится для того, чтобы оценить какие-то показатели качества. Основные показатели качества обслуживания:
- общее количество обслуженных заявок за какой-либо промежуток времени;
- пропускная способность - среднее число заявок, обслуженных в единицу времени;
- доля обслуженных заявок;
- доля заявок, получивших отказ;
- время пребывания заявки в системе (от поступления заявки в систему до завершения ее обслуживания);
- среднее время обслуживания (функция распределения времени обслуживания);
средняя длина очереди;
- среднее время ожидания;
- загрузка каналов - коэффициент использования (как доля времени, в течение которого ОУ было занято) - характеризует степень простоя ОУ.
Классические математические методы исследования СМО предложены
теорией массового обслуживания. Чем аппарат аналитического моделирования СМО отличается от имитационного моделирования? Аналитические методы его весьма ограничены и мало пригодны для решения практических задач. Например, часто используются предположения о простейшем потоке заявок (однако для различных фаз обслуживания он может отличаться), об однотипных устройствах и т.п. В имитационном моделировании подобные ограничения снимаются: могут применяться произвольные законы распределения, различные схемы обслуживания (например, порядок обслуживания заявок из очереди).
Сущность метода имитационного моделирования для СМО состоит в том, что используются специальные алгоритмы, позволяющие вырабатывать случайные реализации потоков событий и моделировать процессы функционирования обслуживающих систем. Далее осуществляется многократное воспроизведение случайных процессов обслуживания и на выходе модели выполняется статистическая обработка полученных статистических данных, оценка показателей качества обслуживании.
GPSS является системой дискретного типа. Система GPSS ориентирована на класс объектов, процесс функционировании которых можно представить в виде множества состояний и правил перехода из одного состояния в другое, определяемых в дискретной пространственно-временной области.
Для регистрации изменений во времени существует таймер модельного времени. Механизм задания модельного времени: пособытийный, с переменным шагом. Изменения в реальной системе приводят к появлению событий. В системе происходят такие события, как поступление заявки; постановка заявки в очередь; начало обслуживания; конец обслуживания и др.
В GPSS рассматриваются два класса событий:
- основные события, которые можно запланировать, т.е. рассчитать момент наступления заранее, до их появления;
- вспомогательные события, которые происходят вследствие основных и осуществляются в результате взаимодействия таких абстрактных элементов, как блоки и транзакты, например смена состояния прибора обслуживания со «свободен» на «занят».
Сети Петри и их обобщения представляют собой математические модели, построенные в рамках определенной концепции структуризации.
Концепция структуризации базируется на возможности представления моделируемых систем в виде совокупности параллельных процессов, взаимодействующих на основе синхронизации событий или распределения общих для нескольких процессов ресурсов. Каждый процесс в рамках этой концепции представляется в виде логически обусловленных не упорядоченных по времени причинно-следственных цепочек условий и событий.
Рассмотрим общие подходы к описанию структур моделируемых проблемных ситуаций в виде сетей Петри. Сети Петри – удобный аппарат моделирования параллельных процессов, т.е. процессов, протекающих независимо один от другого.
При разработке структур моделей дискретных систем в качестве базовой информации можно использовать данные о логической взаимосвязи наблюдаемых в системе событий и условий, предопределяющих наступление этих событий.
В некоторых реальных системах нельзя точно предсказать момент времени наступления событий. Наступление событий предваряет сложная система причин и следствий. Точное знание моментов времени реализации событий в системе часто можно игнорировать, поскольку такие сведения о событиях, происходящих в реальных (или проектируемых) системах, либо просто отсутствуют, либо их нельзя считать достоверными. Это объясняется многообразием предваряющих события условий, невозможностью полного их учета и верного описания, а также действием сложной системы причин и следствий, определение которых на временной шкале часто не представляется возможным.
Вводятся базовые понятия “Условие” и “Событие”, которые могут быть связаны отношением типа “Выполняется после” (рис. 4.4.1).
События выражают действия, реализация которых управляет состояниями системы. Только при достижении определенных состояний (в этом случае соответствующие предикаты принимают истинное значение) обеспечивается возможность действий (наступления событий). Условия, с фактами выполнения которых связана истинность предиката и, следовательно, возможность реализации события, называют “до-условиями” (предпосылками наступления события).
В результате действия, совершившегося при реализации события, объявляются истинными все простые условия, непосредственно связанные с данным событием отношением “Выполняется после”. Эти условия рассматриваются как “пост-условия” (прямые следствия событий).
Только после выполнения всех “до-условий” для некоторого события это событие может быть выполнено. После того как событие имело место, истинными становятся все “пост-условия” данного события, которые затем, в свою очередь, могут быть “до-условиями” каких-либо других событий и т. д. Таким образом, оформляется логическая взаимосвязь событий и условий, предопределяющих эти события в виде логически обусловленных причинно-следственных цепочек условий и событий. Построение полной структуры таких отношений для моделируемой проблемной ситуации составляет цель и задачу формирования структуры модели.
В таблице 4.4 рассматривается фрагмент моделируемой производственной системы, отражающий некоторый процесс обслуживания деталей на станке.
Структуризация производственной системы Таблица 4.4
Формальное и графическое представление сетей Петр
Рассмотренная концепция структуризации моделируемой проблемной ситуации поддерживается формальными средствами, разработанными в теории сетей Петри.
В сетях Петри условия моделируются позициями, а события – переходами.
Формально сеть Петри представляет собой набор:
С = (Р, Т, Е), где
Р - непустое конечное множество позиций сети;
Т - непустое конечное множество переходов;
Е = (РХТ) U (ТХР) – отношение инцидентности позиций и переходов (множество дуг сети) – логически обусловленные причинно-следственные связи между событиями и условиями.
Также могут быть заданы:
W: F->N – функция кратности дуг (каждой дуге ставится в
соответствие n > 0 – кратность дуг);
M: P->N – функция начальной разметки.
В различных расширениях сетей Петри используются графические представления – графы, орграфы, диграфы – в общем виде некоторые сетевые представления.
Графически ординарные сети Петри представляются двудольными орграфами:
С = (Р, Т, Е).
Множество вершин в таких орграфах состоит из непересекающихся подмножеств позиций Р = {рi}, i = 1,…,|P| и переходов Т = {tj}, j = 1,…,| T| , а множество дуг Е разделяется на два подмножества { (рi1, tj) } и { (tj1 , рi) }. Дуги (рi1,tj) ориентированы от позиций к переходам, а дуги (tj1 , рi) – от переходов к позициям.
В изображении графов, представляющих ординарные сети Петри, позиции принято обозначать кружками, а переходы – барьерами (планками) следующим образом:
Рис. 4.4.2. Обозначения основных элементов сетей Петри
Для примера рассмотрим фрагмент сети Петри, моделирующей структуру процессов функционирования производственной системы, соответствующий примеру, приведенному в таблице 4.4.
Динамика поведения моделируемой системы отражается в функционировании сети в виде совокупности действий, называемых срабатыванием переходов.
Динамика сетей Петри обусловлена соглашениями относительно правил срабатывания переходов. Действующие в сетях Петри соглашения о правилах выполнения переходов выражают логические взаимосвязи между условиями и событиями в моделируемой системе. Переход может сработать (срабатывание перехода), если выполнены все условия реализации соответствующего события. Последовательная реализация событий в системе отображается в сети в виде последовательного срабатывания ее переходов.
Механизм маркировки позиций. Изменение состояния сети связано с механизмом изменения маркировок позиций. Начальное состояние сети Петри задается с помощью маркировки ее позиций. Маркировка сети (разметка позиции-места) заключается в присвоении позициям числовых значений (меток, маркеров, фишек). Метки представляют собой набор атрибутов (числа, переменные). Например, начальную разметку можно записать в виде вектора М0 (p) = (00000110100), где 1- соответствует условиям, которые должны быть выполнены.
Когда емкости позиций невелики, в качестве меток на графических изображениях сетей Петри используют не числа, а фишки, маркеры. Выполнение условия изображается разметкой (маркировкой) соответствующего места, а именно помещением числа n или n- фишек (маркеров) в эту позицию. Изменение состояния сети связано с изменением маркировок позиций, в этом случае выполняется возбужденный переход, т.е. переход с ненулевыми метками. Переход может сработать, если выполнены все условия реализации соответствующего события. Для этого задаются специальные правила или процедуры перехода. На рис. 4.4.5 (а, б, в) демонстрируется, как в сетях Петри реализуется механизм маркировки.
Таким образом, срабатывание перехода – это неделимое действие, изменяющее разметку: из каждого входного места (позиции) изымается по одной фишке, а в каждое выходное место (позицию) добавляется по одной фишке. Тем самым реализация события, изображенного переходом, изменяет состояние связанных с ним условий (уменьшается емкость до-условий, увеличивается емкость постусловий).
Применяются следующие правила изменения маркировок:
выполняется только возбужденный переход, т.е. такой переход, во всех входных позициях которого имеются ненулевые метки;
срабатывание перехода может наступить через любой конечный промежуток времени после его возбуждения;
если в некотором состоянии сети возбужденным оказывается сразу несколько переходов, то всегда выполняется только какой-то один (любой) из них;
Рис. 4.4.5. Реализация механизма маркировки в сетях Петри
в результате срабатывания перехода метки в каждой позиции перехода уменьшаются на единицу, а метки во всех его выходных позициях увеличиваются на единицу;
выполнение перехода – неделимый акт, изменение разметки входных и выходных позиций перехода при его выполнении осуществляется мгновенно.
Всякому возможному варианту выполнения сети будет отвечать определенная последовательность срабатываний переходов и последовательность получающих после каждого очередного срабатывания маркировок вида:.
Сети Петри формализуют понятие абстрактной асинхронной системы динамической структуры из событий и условий. В сетях Петри не моделируется ход времени, события упорядочиваются по отношению “Выполняется после”.
Сети Петри моделируют широкий класс систем, но для некоторых распространенных специальных классов систем удобно применять сети Петри не общего вида, а некоторые их подклассы или расширения (иерархические сети, раскрашенные сети Петри, сети событий, временные сети событий, КОМБИ-сети, ЕД-диаграммы), более адекватные рассматриваемым системам.
Регулярные сети. Основным свойством регулярных сетей является наличие определенной алгебры, которая обеспечивает проведение аналитического представления процесса топологического построения и расчленения процесса анализа сетей на совокупность этапов, на каждом из которых достаточно иметь дело с более простыми фрагментами сети.
В свою очередь обобщением регулярных сетей являются иерархические сети, предназначенные для адекватного моделирования иерархических динамических систем. Иерархическая сеть функционирует, переходя от разметки к разметке, с некоторыми отличиями от работы регулярных сетей. Данные отличия связаны с присутствием составных переходов, срабатывание которых является не мгновенным событием, как в традиционных сетях Петри, а составным действием. Поэтому составной переход не срабатывает, а работает, т.е. находится некоторое время в активном состоянии.
При моделировании систем сетями Петри, часто возникают ситуации, при которых фишки позиций (мест) должны быть не “безлики”, а должны соответствовать объектам, передаваемым от компонента к компоненту (от перехода к переходу). Причем, как правило, эти объекты имеют дополнительные атрибуты, которые позволяют различать их и использовать эти различия для управления функционированием системы. Для адекватного описания подобных ситуаций был разработан подкласс раскрашенных сетей Петри. В рассмотренных нами ранее сетях все метки предполагались одинаковыми. Механизм функционирования сетей был связан только лишь с количествами меток во входных позициях переходов и определялся общими для всех меток условиями возбуждения переходов и правилами изменения разметки позиций при выполнении сети. Появление раскрашенных сетей Петри связано с концепцией использования различимых меток. В таких сетях каждая метка получает свой цвет. Условия возбуждения и правила срабатывания переходов для меток каждого цвета задаются независимо. В данных сетях фишкам приписываются некоторые признаки, например различные цвета (переменные), а кратности дуг интерпретируются как функции от этих переменных. Условия срабатывания переходов и правила изменения разметки задаются специальной таблицей, учитывающей цвета фишек.
Дальнейшим расширением раскрашенных сетей явились предикатные сети. Данные сети позволили связывать с переходами сетей логические формулы (предикаты или защиту), представляющие классы возможных разметок во входных и выходных позициях в соответствии с метками дуг. Эти выражения задают условия отбора необходимых цветов для срабатывания переходов.
При разработке практически любой имитационной модели и планировании проведения модельных экспериментов необходимо соотносить между собой три представления времени:
• реальное время, в котором происходит функционирование имитируемой системы;
• модельное (или, как его еще называют, системное) время, в масштабе которого организуется работа модели;
• машинное время, отражающее затраты времени ЭВМ на проведение имитации.
С помощью механизма модельного времени решаются следующие задачи:
1) отображается переход моделируемой системы из одного состояния в другое;
2) производится синхронизация работы компонент модели;
3) изменяется масштаб времени «жизни» (функционирования) исследуемой системы;
4) производится управление ходом модельного эксперимента;
5) моделируется квазипараллельная реализация событий в модели.
Существуют два метода реализации механизма модельного времени — с постоянным шагом и по особым состояниям.
Выбор метода реализации механизма модельного времени зависит от назначения модели, ее сложности, характера исследуемых процессов, требуемой точности результатов и т. д.
При использовании метода постоянного шага отсчет системного времени ведется через фиксированные, выбранные исследователем интервалы времени. События в модели считаются наступившими в момент окончания этого интервала. Погрешность в измерении временных характеристик системы в этом случае зависит от величины шага моделирования .
Метод постоянного шага предпочтительнее, если:
• события появляются регулярно, их распределение во времени достаточно равномерно;
• число событий велико и моменты их появления близки;
• невозможно заранее определить моменты появления событий.
Данный метод управления модельным временем достаточно просто реализовать в том случае, когда условия появления событий всех типов в модели можно представить как функцию времени.
Выбор величины шага моделирования является нелегким и очень важным делом. Универсальной методики решения этой проблемы не существует, но во многих случаях можно использовать один из следующих подходов:
• принимать величину шага равной средней интенсивности возникновения событий различных типов;
• выбирать величину Dt равной среднему интервалу между наиболее частыми (или наиболее важными) событиями.
При моделировании по особым состояниям системное время каждый раз из-меняется на величину, строго соответствующую интервалу времени до момента наступления очередного события. В этом случае события обрабатываются в поряд-ке их наступления, а одновременно наступившими считаются только те, которые являются одновременными в действительности.
Метод моделирования по особым состояниям сложнее в реализации, так как для него требуется разработка специальной процедуры планирования событий (так называемого календаря событий).
Моделирование по особым состояниям целесообразно использовать, если:
• события распределяются во времени неравномерно или интервалы между ними велики;
• предъявляются повышенные требования к точности определения взаимного положения событий во времени;
• необходимо реализовать квазипараллельную обработку одновременных событии.
Дополнительное достоинство метода заключается в том, что он позволяет экономить машинное время, особенно при моделировании систем периодического действия, в которых события длительное время могут не наступать.
Работа (активность) — это единичное действие системы по обработке (преобразованию) входных данных. В зависимости от природы моделируемой системы под входными данными могут пониматься информационные данные или какие-либо материальные ресурсы. Каждая работа характеризуется временем выполнения и потребляемыми ресурсами.
Под процессом понимают логически связанный набор работ. Некоторые процессы могут рассматриваться, в свою очередь, как работы в процессе более высокого уровня. Любой процесс характеризуется совокупностью статических и динамических характеристик.
К статическим характеристикам процесса относятся: длительность, результат, потребляемые ресурсы, условия запуска (активизации), условия останова (прерывания). В общем случае статические характеристики процесса не изменяются в ходе его реализации, однако при необходимости любая из них может быть представлена в модели как случайная величина, распределенная по заданному закону.
Динамической характеристикой процесса является его состояние (активен или находится в состоянии ожидания).
Моделирование в терминах процессов производится в тех случаях, когда система оценивается по каким-либо временным показателям, либо с точки зрения потребляемых ресурсов. Например, при оценке производительности вычислительной сети обработка заданий может быть представлена в модели как совокупность соответствующих процессов, использующих ресурсы сети (оперативную память, пространство на жестких дисках, процессорное время, принтеры и т. д.).
Еще раз отметим, что ИМ позволяет исследовать поведение различных систем с учетом влияния случайных факторов. Эти факторы в зависимости от их природы могут быть отражены в модели как случайные события, случайные величины (дискретные или непрерывные) или как случайные функции (процессы).
В основе всех методов и приемов моделирования случайных факторов лежит использование случайных чисел, имеющих равномерное распределение на интервале [0; 1].
«Истинно» случайные числа формируются с помощью аналого-цифровых преобразователей на основе сигналов физических генераторов, использующих естественные источники случайных шумов (радиоактивный распад, шумы электронных и полупроводниковых устройств и т. п.).
Случайные числа, генерируемые аппаратно или программно на ЭВМ, называются псевдослучайными. Однако их статистические свойства совпадают со статистическими свойствами «истинно» случайных чисел. В состав практически всех современных систем программирования входят специальные функции генерации случайных чисел, которые обычно называют датчиками, или генераторами, случайных чисел.
Наиболее простой метод программной генерации случайных чисел - мультипликативный; в его основе лежит следующее рекуррентное соотношение:
аi = (Aai-l +C)modM, (4.1)
где aj, ai-1 — очередное и предыдущее случайные числа соответственно; А, С - константы; М - достаточно большое целое положительное число (чем больше М, тем длиннее неповторяемая последовательность).
Достоинство метода заключается в том, что при одних и тех же значениях величин, входящих в выражение (4.1), можно полностью воспроизвести эксперимент.
Практика показывает, что результаты имитационного моделирования существенно зависят от качества используемых последовательностей псевдо-случайных чисел. Поэтому применяемые в ИМ генераторы СЧ должны пройти тесты на пригодность.
Основные анализируемые характеристики генерируемых датчиком по-следовательностей: равномерность; стохастичность (случайность); независимость. Рассмотрим методы проведения такого анализа, наиболее часто применяемые на практике.
Проверка равномерности может быть выполнена с помощью гистограммы относительных частот генерируемой СВ. Для ее построения интервал [0; 1] разбивается на т равных частей и подсчитывается относительное число попаданий значений СВ в каждый интервал.
Проверка стохастичности. Рассмотрим один из основных методов проверки - метод комбинаций. Суть его сводится к следующему. Выбирают достаточно большую последовательность случайных чисел х- и для нее определяют вероятность появления в каждом из х(- ровно j единиц. При этом могут анализироваться как все разряды числа, так и только старших.
Проверка независимости проводится на основе вычисления корреляционного момента.
Напомним, что две случайные величины а и Ъ называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая. Для независимых СВ корреляционный момент равен нулю.
Для оценки независимости элементов последовательности поступают следующим образом.
Еще одна важная характеристика датчика СЧ - длина отрезка апериодичности L. Если в основу работы датчика положен мультипликативный метод, то оценить L несложно: она определяется величиной константы М
Моделирование случайных событий. Для моделирования случайного события А, вероятность которого равна Рс, достаточно сформировать одно число г, равномерно распределенное на интервале [0,1].
Моделирование дискретных случайных величин. Наиболее часто используются два метода:
- метод последовательных сравнений;
- метод интерпретации.
Метод последовательных сравнений. Число г последовательно сравнивают со значением суммы Р1 + Р2+ где Р\ — вероятность наименьшего
значения СВ Y, Pj - вероятность второго по величине значения.
Процесс можно ускорить, применяя методы оптимизации перебора: дихотомии, ранжирования В и т. д. Величины Р рассчитывают по функциям распределения вероятности, соответствующим моделируемому закону.
Метод интерпретации основан на физической трактовке моделируемого закона распределения. Например, биномиальное распределение описывает число успехов в п независимых испытаниях с вероятностью успеха в каждом испытании Р и вероятностью неудачи g = l — Р.
При моделировании этого распределения с помощью метода интерпретации выбирают п независимых СЧ, равномерно распределенных на интервале [0, 1], и подсчитывают количество тех из них, которые меньше Р. Это число и является моделируемой СВ.
Моделирование непрерывных СВ. При моделировании непрерывных СВ с заданным законом распределения могут используются три метода:
метод нелинейных преобразований;
метод композиций;
табличный метод.
Первые два метода требуют от разработчика модели весьма серьезной математической подготовки и в данной книге не рассматриваются. Третий метод, условно названный «табличным», основан на замене закона распределения непрерывной СВ специальным расчетным соотношением, которое позволяет вычислять значение СВ по значению случайного числа, равномерно распределенного все на том же интервале [0, 1]. Такие соотношения получены практически для всех наиболее распространенных видов распределений и приведены в справочной литературе.
В одной и той же имитационной модели могут фигурировать различные случайные факторы, одни из них могут быть представлены как случайные события, другие - как случайные величины; более того, если моделируется поведение достаточно сложной системы, то ее функционирование может быть связано с возникновением нескольких типов событий и учетом большого числа случайных величин, распределенных по различным законам. Если же моделирование всех случайных факторов основано на использовании одного датчика, генерирующего одну «общую» последовательность случайных чисел, то с математической точки зрения их нельзя считать независимыми. В связи с этим для моделирования каждого случайного фактора стараются использовать отдельный генератор, или, по крайней мере, обеспечивать создание новой последовательности случайных чисел. Во многих специализированных языках и пакетах моделирования такая возможность предусмотрена.
Асинхронный параллельный процесс (ПП) - процесс, состояние которого не зависит от состояния другого параллельного процесса. Пример АПП в рамках одной системы: работа сборочного конвейера.
Синхронный ПП - процесс, состояние которого зависит от состояния взаимодействующих с ним ПП. Один и тот же процесс может быть синхронным по отношению к одному из активных ПП и асинхронным по отношению к другому. Так при работе вычислительной сети по технологии «клиент-сервер» каждый из узлов сети синхронизирует свою работу с работой сервера, но не зависит от работы других узлов.
Подчиненный ПП - создается и управляется другим процессом (более высокого уровня). Пример: ведение боевых действий подчиненными подразделениями.
Независимый ПП - не является подчиненным ни для одного из процессов. Пример: полет неуправляемой зенитной ракеты, одновременно с которым самолет ведет боевые действия.
Реализация ПП в вычислительных системах (ВС) имеет особенности?
- на уровне задач вычислительные процессы могут быть истинно параллельными только в многопроцессорных ВС или вычислительных сетях
- многие ПП используют одни и те же ресурсы, поэтому даже асинхронные ПП в пределах одной ВС вынуждены согласовывать свои действия при ображении к общим ресурсам
- в ВС дополнительно используются еще 2 вида ПП: родительский и дочерний ПП; особенность их состоит в том, что процесс-родитель не может быть завершен, пока не завершаться все его дочерние процессы
Для организации взаимодействия параллельных процессов в ВС используются 3 основных подхода:
- на основе «взаимного исключения»
- на основе синхронизации посредством сигналов
- на основе обмена информацией (сообщениями)
«Взаимное исключение» - запрет доступа к общим ресурсам для всех ПП, кроме работающего с этими ресурсами в это время.
Синхронизация – обмен сигналами между двумя или более процессами по установленному протоколу.
Обмен сообщениями – когда необходимо передавать от одного ПП другому более подробную информацию, чем просто «сигнал-сообщение»
Перечисленные подходы реализуются на на двух уровнях – системном и прикладном.
На системном уровне взаимодействие между ПП определяется на этапе разработки ВС и реализуется средствами операционной системы. На прикладном уровне взаимодействие реализуется программистом средствами языка, на котором разрабатывается программное обеспечение. Наибольшими возможностями в этом отношении обладают языки моделирования.
Общий механизм реализации ПП в языках моделирования применительно к моделированию на основе транзактов. под событием понимается любое перемещение транзакта по системе, изменение его состояния. Событие ,связанное с данным транзактом, можетхраниться в одном из списков:
Список текущих событий. В нем находятся события, время наступления которых меньше или равно текущему модельному времени.
Список будущих событий. События, время наступления которых больше текущего модельного времени, т.е. которые должны произойти в будущем.
Список прерывний. События, связанные с возобновлением обработки прерванных транзактов. Выбираются в том случе, если сняты условия прерывания.
В списке текущих событий транзакт может находится в активном состоянии, либо в состоянии задержки. Если активно-то транзакт передвигается по системе; если продвижение невозможно, то транзакт переводится в состояние задержки.
После завершения обработки активных транзактов, просматривактся список задержанных и ряд из них переводится в активное состояние. Процедура повторяется, пока не будут обработаны все активные события. После просматривается список будущих событий и модельному времени присваивается значение, равное времени наступления ближайшего. Данное событие переносится в список текущих событий. Затем просматриваются остальные события списка. Просмотр заканчивается, когда в списке остаются события, времена которых больше текущего модельного времени.
Среди задач непрерывной конечномерной оптимизации самым важным с практической точки зрения и одновременно самым сложным является класс задач глобальной условной оптимизации. Методы решения задач этого класса можно разделить на две большие группы:
- методы сведения задачи глобальной условной оптимизации к задаче глобальной безусловной оптимизации с помощью штрафных или барьерных функций;
- методы, специально сконструированные для решения задачи глобальной условной оптимизации.
Метод роя частиц относится к методам первой группы и, таким образом, предназначен для решения задач глобальной безусловной оптимизации.
Методы решения задачи глобальной безусловной оптимизации делятся на детерминированные, стохастические и эвристические .
Эвристические методы. Среди них выделяют эволюционные и поведенческие (имитационные) методы. Поведенческие методы решения задачи глобальной безусловной оптимизации основаны на моделировании коллективного поведения самоорганизующихся живых или неживых систем. Взаимодействующие элементы этих систем, в общем случае, называются агентами.
Поведенческие методы относятся к мультиагентным методам, основанным на моделировании интеллектуального поведения колоний агентов. В природе таким интеллектом обладают группы общественных насекомых, например колонии муравьев. Ключевыми идеями поведенческих методов являются децентрализованность, взаимодействие агентов и простота их поведения.
Известность получили следующие поведенческие методы решения задачи глобальной безусловной оптимизации: метод поведения пчёл; метод роя частиц.
В методе оптимизации роем частиц (particle swarm optimization - PSO) агентами являются частицы в пространстве параметров задачи оптимизации. В каждый момент времени (на каждой итерации) частицы имеют в этом пространстве некоторое положение и вектор скорости. Для каждого положения частицы вычисляется соответствующее значение целевой функции, и на этой основе по определённым правилам частица меняет своё положение и скорость в пространстве поиска.
В основу метода PSO положена социально-психологическая поведенче¬ская модель толпы. Существует несколько разновидностей метода. Например, в каноническом методе роя частиц на каждой итерации при определении следующего положения частицы учитывается информация о наилучшей частице из числа «соседей» данной частицы, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции. Модификация канонической модели FIPS учитывает значения целевой функции, соответствующие всем частицам роя; в некоторых моделях частицы группируются в несколько роёв и т. д.
Метод пчелиного роя представляет собой эвристический итеративный мультиагентный метод случайного поиска, основная идея которого состоит в моделировании поведения пчёл при поиске нектара. Среди недостатков метода пчелиного роя упоминания заслуживает большое число свободных параметров метода, от значений которых, с одной стороны, зачастую сильно зависит эффективность метода, а с другой - отсутствуют какие-либо содержательные основания для выбора этих значений.
Задача многомерной глобальной оптимизации многоэкстремальной целевой функции неразрешима в общем случае, поскольку не гарантируется получение решения за конечное число шагов. Сложность ее численного решения вызвана большой размерностью пространства параметров, отсутствием достаточной априорной информации о характере целевой функции, вероятностным характером критерия оптимальности и дефицитом информации о случайных закономерностях процессов изменения параметров проектируемых технических систем. Экстремум целевой функции приходится искать в условиях нелинейности ее и ограничений на управляемые параметры, недоступности или отсутствия дополнительной информации об объекте исследования. Так, в задачах параметрического синтеза для алгоритмически заданной целевой функции доступными являются лишь ее значения, получение которых требует значительных вычислительных ресурсов.
В методах глобальной оптимизации алгоритмы решения являются итеративным процессом, порождающим последовательность точек в соответствии с предписанным набором правил, включающим критерий окончания счета. Глобальный экстремум ищется среди всех найденных локальных решений, но возможен перебор только части локальных решений, если оставшиеся локальные решения не влияют на окончательный результат. Поэтому все используемые методы сводятся к оценке значения целевой функции на подмножестве точек из допустимого множества и отличаются способами выбора этих точек. При выборе метода решения конкретной задачи основной упор делается на учет свойств целевой функции и допустимого множества оптимизируемых параметров.
Методы оптимизации классифицируют по ряду признаков.
В зависимости от числа управляемых параметров различают:
• методы одномерной оптимизации, в которых управляемый параметр единственный;
• методы многомерной оптимизации, в которых управляемые параметры представляют собой вектор X размером не менее двух.
Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.
По наличию или отсутствию ограничений выделяют:
• методы условной оптимизации;
• методы безусловной оптимизации.
Для реальных задач характерно наличие большого числа ограничений, однако методы безусловной оптимизации также представляют интерес, поскольку задачи условной оптимизации с помощью специальных методов могут быть сведены к задачам без ограничений.
В зависимости от числа экстремумов различают задачи:
• одноэкстремальные (локальные);
• многоэкстремальные (глобальные).
По виду целевой функции и допустимого множества задачи оптимизации и методы их решения можно разделить на следующие классы:
• задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования;
• задачи оптимизации, сводящиеся к задачам нелинейного программирования с соответствующими методами их решения.
Методы оптимизации классифицируют в соответствии с задачами оптимизации:
• локальные методы, сходящиеся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции этот экстремум единственен и будет глобальным максимумом/минимумом;
• глобальные методы, имеющие дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.
Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют, и потому на практике в САПР используют методы поиска локальных экстремумов.
В зависимости от того, используются при поиске производные целевой функции по управляемым параметрам или нет, различают методы нескольких порядков. Если производные не используются, имеем метод нулевого порядка, если используются первые или вторые производные - соответственно метод первого или второго порядка.
Среди алгоритмов оптимизации выделяют детерминированные и вероятностные. При одних и тех же входных данных детерминированный алгоритм всегда будет выдавать один и тот же результат, получаемый после строгого прохождения всех чётко определённых шагов. Таким образом, детерминированный алгоритм эквивалентен конечному автомату или классической машине Тьюринга.
Вероятностные алгоритмы включают в процесс вычисления источник случайности. Благодаря этому им удается сократить (зачастую на порядки) время исполнения. В большинстве случаев, однако, вероятностные алгоритмы не могут гарантировать правильность результата.
Эвристическими называют алгоритмы оптимизации, использующие собственный опыт в процессе поиска. Можно сказать, что в процессе работы эвристические методы обучаются, накапливая знания о качестве всё большего количества оценённых решений. На основании этих знаний они выбирают очередные решения для оценки.
Идея об использовании собственного опыта в процессе вычислений применима не только в области оптимизации. Например, алгоритмы абсолютного большинства современных антивирусных сканеров используют эвристику.
Среди эвристических алгоритмов выделяют подкласс метаэвристических алгоритмов. Такие алгоритмы основываются исключительно на собственном опыте, не делая никаких предположений насчёт структуры области поиска. Таким образом, метаэвристические алгоритмы не зависят (или зависят крайне мало) от специфики решаемой задачи, что позволяет применять их к очень широкому кругу задач.
Метаэвристические алгоритмы рассматривают целевую функцию как «чёрный ящик». Единственное действие, которое они могут совершить с ней - это аппликация, т. е. её вычисление для конкретного решения. Таким образом, для работы метаэвристического алгоритма требуется лишь возможность получения значения целевой функции.
Скорость!!!!!
Эффективность сходящегося метода можно охарактеризовать с помощью понятия скорости сходимости. Пусть при . Говорят, что последовательность сходится к линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы и , что Говорят, что сходится к сверхлинейно (со сверхлинейной скоростью), если
Говорят о квадратичной сходимости, если существуют такие константы
и , что
Иногда, сохраняя ту же терминологию, неравенства (9)-(11) заменяют соответственно на неравенства
Ясно, что из (9) следует (12), а из (10) следует (13). Если предположить, что справедливо (11) и при некотором , то
тогда из (11) следует (14) при C3 = 1/C .
Для характеристики сходимости последовательности k N к в ситуациях, аналогичных (6) или (9), (7) или (10), (8) или (11), используются аналогичные термины: линейная, сверхлинейная и квадратичная скорость сходимости.
Точность!!!!
Остановка может производиться и по достижении заданной точности решения задачи, например, на основе оценок (12)-(14). Однако при решении реальной задачи трудно оценить истинную точность. Так, константы, фигурирующие в оценках (12)-(14), обычно неизвестны. Поэтому о достижении заданной точности приходится судить по косвенным признакам. На практике часто используются следующие условия остановки:
До начала вычислений выбирается одно из условий (15)-(17) и соответствующее ему малое , i = 1,2,3 . Вычисления прекращаются после (k +1)-го шага, если впервые оказывается выполненным выбранное условие остановки. На практике также используются критерии, состоящие в одновременном выполнении двух из условий (15)-(17) или всех трех условий. Ясно, что критерий (17) относится лишь к задачам безусловной оптимизации. Его выполнение означает, что в точке с точностью выполнено условие стационарности. В задаче условной оптимизации критерий (17) следует заменить на критерий «e -стационарности», соответствующий данной задаче.
Метод Дельфи (дельфийский метод) был разработан в 1950—1960 годы в США для прогнозирования влияния будущих научных разработок на методы ведения войны (Olaf Helmer, Norman Dalkey, Nicholas Rescher). Является методом экспертного оценивания. Особенности: заочность, многоуровневость, анонимность, подходит для стратегического, а не операционного планирования. Используется в технике, бизнесе, футурологии.
Суть этого метода в том, чтобы с помощью серии последовательных действий – опросов, интервью, мозговых штурмов – добиться максимального консенсуса при определении правильного решения. Анализ с помощью дельфийского метода проводится в несколько этапов, результаты обрабатываются статистическими методами.
Базовым принципом метода является то, что некоторое количество независимых экспертов (часто несвязанных и не знающих друг о друге) лучше оценивает и предсказывает результат, чем структурированная группа (коллектив) личностей. Позволяет избежать открытых столкновений между носителями противоположенных позиций т.к. исключает непосредственный контакт экспертов между собой и, следовательно, групповое влияние, возникающее при совместной работе и состоящее в приспособлении к мнению большинства, даёт возможность проводить опрос экстерриториально, не собирая экспертов в одном месте (например, посредством электронной почты)
Субъекты:
• группы исследователей, каждый из которых отвечает индивидуально в письменной форме.
• организационная группа — сводит мнения экспертов воедино.
Этапы:
Предварительный: подбор группы экспертов - чем больше, тем дольше будет работать алгоритм.
Основной:
• постановка проблемы — экспертам рассылается вопрос и предлагается его разбить на подвопросы. Организационная группа отбирает наиболее часто встречающиеся. Появляется общий опросник.
• этот опросник рассылается экспертам. Их спрашивают — можно ли добавить ещё что-то; достаточно ли информации; есть ли дополнительная информация по вопросу? В итоге получаем 20 вариантов ответов с дополнительными аспектами и информацией. На основе этого составляется следующий опросник.
• улучшенный опросник вновь рассылается экспертам, которым теперь надо дать свой вариант решения, а также рассмотреть наиболее крайние точки зрения, высказанные другими экспертами. Эксперты должны оценить проблему по аспектам: эффективность, обеспеченность ресурсами, в какой степени соответствует изначальной постановке задачи. Таким образом выявляются преобладающие суждения экспертов, сближаются их точки зрения. Всех экспертов знакомят с доводами тех, чьи суждения сильно выбиваются из общего русла. После этого все эксперты могут менять мнение, а процедура повторяется.
• операции повторяются, пока не будет достигнута согласованность между экспертами, или не будет установлено отсутствие единого мнения по проблеме. Изучение причин расхождений в оценках экспертов позволяет выявить незамеченные ранее аспекты проблемы и зафиксировать внимание на вероятных последствиях развития анализируемой проблемы или ситуации. В соответствии с этим и вырабатывается окончательная оценка и практические рекомендации. Обычно проводится три этапа, но если мнения сильно разнятся - то больше.
Аналитический:
• проверка согласованности мнений экспертов, анализ полученных выводов и разработка конечных рекомендаций
Метод Анализа Иерархий (МАИ) — математический инструмент системного подхода к сложным проблемам принятия решений. МАИ не предписывает лицу, принимающему решение (ЛПР), какого-либо «правильного» решения, а позволяет ему в интерактивном режиме найти такой вариант (альтернативу), который наилучшим образом согласуется с его пониманием сути проблемы и требованиями к ее решению. Этот метод разработан американским математиком Томасом Саати. МАИ широко используется на практике и активно развивается учеными всего мира. В его основе наряду с математикой заложены и психологические аспекты. МАИ позволяет понятным и рациональным образом структурировать сложную проблему принятия решений в виде иерархии, сравнить и выполнить количественную оценку альтернативных вариантов решения. Анализ проблемы принятия решений в МАИ начинается с построения иерархической структуры, которая включает цель, критерии, альтернативы и другие рассматриваемые факторы, влияющие на выбор. Эта структура отражает понимание проблемы лицом, принимающим решение. Каждый элемент иерархии может представлять различные аспекты решаемой задачи, причем во внимание могут быть приняты как материальные, так и нематериальные факторы, измеряемые количественные параметры и качественные характеристики, объективные данные и субъективные экспертные оценки. Иными словами, анализ ситуации выбора решения в МАИ напоминает процедуры и методы аргументации, которые используются на интуитивном уровне. Следующим этапом анализа является определение приоритетов, представляющих относительную важность или предпочтительность элементов построенной иерархической структуры, с помощью процедуры парных сравнений. Безразмерные приоритеты позволяют обоснованно сравнивать разнородные факторы, что является отличительной особенностью МАИ. На заключительном этапе анализа выполняется синтез (линейная свертка) приоритетов на иерархии, в результате которой вычисляются приоритеты альтернативных решений относительно главной цели. Лучшей считается альтернатива с максимальным значением приоритета.
Метод анализа иерархий содержит процедуру синтеза приоритетов, вычисляемых на основе субъективных суждений экспертов. Число суждений может измеряться дюжинами или даже сотнями. Математические вычисления для задач небольшой размерности можно выполнить вручную или с помощью калькулятора, однако гораздо удобнее использовать программное обеспечение (ПО) для ввода и обработки суждений. Самый простой способ компьютерной поддержки - электронные таблицы, самое развитое ПО предусматривает применение специальных устройств для ввода суждений участниками процесса коллективного выбора.
Порядок применения Метода Анализа Иерархий:
1. Построение качественной модели проблемы в виде иерархии, включающей цель, альтернативные варианты достижения цели и критерии для оценки качества альтернатив.
2. Определение приоритетов всех элементов иерархии с использованием метода парных сравнений.
3. Синтез глобальных приоритетов альтернатив путем линейной свертки приоритетов элементов на иерархии.
4. Проверка суждений на согласованность.
5. Принятие решения на основе полученных результатов.
Анкетирование представляет собой опрос экспертов с помощью анкет, на вопросы которых они должны дать ответы в письменной форме, либо с использованием технических средств.
Вопросы, содержащиеся в анкетах, можно классифицировать по содержанию и по типу.
По содержанию вопросы делятся на три группы:
– объективные данные об эксперте (возраст, образование, должность, специальность, стаж работы и т. п.);
– основные вопросы по сути анализируемой проблемы;
– дополнительные вопросы, позволяющие выяснить источники информации, аргументацию ответов, самооценку компетентности эксперта и т. п.
По типу вопросы делятся на открытые, закрытые и с веером ответов.
Открытые вопросы предполагают ответ в произвольной форме. Открытые вопросы целесообразно применять в случае большой неопределенности проблемы. Это позволяет широко охватить рассматриваемую проблему, выявить спектр мнений экспертов. Недостатком открытых вопросов является возможное большое разнообразие и произвольная форма ответов, что существенно затрудняет обработку анкет.
Закрытые вопросы – это вопросы, на которые возможны следующие варианты ответов: «да», «нет», «не знаю». Закрытые вопросы применяются в случае рассмотрения четко определенных двух альтернативных вариантов, когда требуется определить степень большинства мнений по этим альтернативам.
Вопрос с веером ответов
дает возможность эксперту выбрать один из предлагаемых ответов. Их целесообразно использовать при наличии нескольких достаточно четко определенных альтернативных вариантов. Эти варианты формируются для ориентации экспертов по возможному кругу направлений в решении проблемы
В начале 80-х годов в исследованиях по искусственному интеллекту сформировалось самостоятельное направление, получившее название "экспертные системы" (ЭС). Основным назначением ЭС является разработка программных средств, которые при решении задач, трудных для человека, получают результаты, не уступающие по качеству и эффективности решения, решениям получаемым человеком-экспертом. ЭС используются для решения так называемых неформализованных задач, общим для которых является то, что:
• задачи не могут быть заданы в числовой форме;
• цели нельзя выразить в терминах точно определенной целевой функции;
• не существует алгоритмического решения задачи;
• если алгоритмическое решение есть, то его нельзя использовать из-за
• ограниченности ресурсов (время, память).
Кроме того неформализованные задачи обладают ошибочностью, неполнотой, неоднозначностью и противоречивостью как исходных данных, так и знаний о решаемой задаче.
Экспертная система - это программное средство, использующее экспертные знания для обеспечения высокоэффективного решения неформализованных задач в узкой предметной области. Основу ЭС составляет база знаний (БЗ) о предметной области, которая накапливается в процессе построения и эксплуатации ЭС. Накопление и организация знаний - важнейшее свойство всех ЭС.
Знания являются явными и доступными, что отличает ЭС от традиционных программ, и определяет их основные свойства, такие, как:
1) Применение для решения проблем высококачественного опыта, который представляет уровень мышления наиболее квалифицированных экспертов в данной области, что ведёт к решениям творческим, точным и эффективным.
2) Наличие прогностических возможностей, при которых ЭС выдает ответы не только для конкретной ситуации, но и показывает, как изменяются эти ответы в новых ситуациях, с возможностью подробного объяснения каким образом новая ситуация привела к изменениям.
3) Обеспечение такого нового качества, как институциональная память, за счет входящей в состав ЭС базы знаний, которая разработана в ходе взаимодействий со специалистами организации, и представляет собой текущую политику этой группы людей. Этот набор знаний становится сводом квалифицированных мнений и постоянно обновляемым справочником наилучших стратегий и методов, используемых персоналом. Ведущие специалисты уходят, но их опыт остается.
4) Возможность использования ЭС для обучения и тренировки руководящих работников, обеспечивая новых служащих обширным багажом опыта и стратегий, по которым можно изучать рекомендуемую политику и методы.
В зависимости от целей экспертного оценивания и выбранного метода измерения при обработке результатов опроса возникают следующие основные задачи:
1. построение обобщенной оценки объектов на основе индивидуальных оценок экспертов;
2. построение обобщенной оценки на основе парного сравнения объектов каждым экспертом;
3. определение относительных весов объектов;
4. определение согласованности мнений экспертов;
5. определение зависимостей между ранжировками;
6. оценка надежности результатов обработки.
Задача построения обобщенной оценки объектов по индивидуальным оценкам экспертов возникает при групповом экспертном оценивании. Решение этой задачи зависит от использованного экспертами метода измерения. При решении многих задач недостаточно осуществить упорядочение объектов по одному показателю или некоторой совокупности показателей. Желательно иметь численные значения для каждого объекта, определяющие относительную его важность по сравнению с другими объектами. Иными словами, для многих задач необходимо иметь оценки объектов, которые не только осуществляют их упорядочение, но и позволяют определять степень предпочтительности одного объекта перед другим. Для решения этой задачи можно непосредственно применить метод непосредственной оценки. Однако эту же задачу при определенных условиях можно решить путем обработки оценок экспертов.
Определение согласованности мнений экспертов производится путем вычисления числовой меры, характеризующей степень близости индивидуальных мнений. Анализ значения меры согласованности способствует выработке правильного суждения об общем уровне знаний по решаемой проблеме и выявлению группировок мнений экспертов. Качественный анализ причин группировки мнений позволяет установить существование различных взглядов, концепций, выявить научные школы, определить характер профессиональной деятельности и т. п. Все эти факторы дают возможность более глубоко осмыслить результаты опроса экспертов.
Обработкой результатов экспертного оценивания можно определять зависимости между ранжировками различных экспертов и тем самым устанавливать единство и различие в мнениях экспертов. Важную роль
играет также установление зависимости между ранжировками, построенными по различным показателям сравнения объектов. Выявление таких зависимостей позволяет вскрыть связанные показатели сравнения и, может быть, осуществить их группировку по степени связи. Важность задачи определения зависимостей для практики очевидна. Например, если показателями сравнения являются различные цели, а объектами – средства достижения целей, то установление взаимосвязи между ранжировками, упорядочивающими средства с точки зрения достижения целей, позволяет обоснованно ответить на вопрос, в какой степени достижение одной цели при данных средствах способствует достижению других целей.
Оценки, получаемые на основе обработки, представляют собой случайные объекты, поэтому одной из важных задач процедуры обработки является определение их надежности. Решению этой задачи должно уделяться соответствующее внимание.
Обработка результатов экспертизы представляет собой трудоемкий процесс. Выполнение операций вычисления оценок и показателей их надежности вручную связано с большими трудовыми затратами даже в случае решения простых задач упорядочения. В связи с этим целесообразно использовать вычислительную технику и особенно ЭВМ. Применение ЭВМ выдвигает проблему разработки машинных программ, реализующих алгоритмы обработки результатов экспертного оценивания.
Представляет собой рассмотрение исследуемых объектов в зависимости от их важности путём приписывания баллов каждому из них. При этом наиболее важному объекту приписывается, т.е. даётся оценка, в размере наибольшего количества баллов по принятой шкале. Наиболее распространён диапазон шкалы оценок от 0 до 1, от 0 до 10, от 0 до 100. В простейшем случае оценка м.б. 0 или 1.
Иногда оценивание осуществляется в словесной форме. Например, очень важный, важный, маловажный и т.п.
Но часто полученные т.о. оценки переводятся в балльную шкалу, например 3, 2, 1, для большего удобства обработки результатов.
Указанный метод целесообразно использовать только при уверенности в полной информированности экспертов об исследуемых свойствах объекта.
Метод непосредственного оценивания (балльный) представляет собой упорядочение исследуемых объектов в зависимости от их важности путем приписывания баллов каждому из них (табл. 7). Наиболее значимому объекту дается наибольшее количество баллов по принятой шкале. Переход от баллов, соответствующих отдельным показателям к коэффициентам весомости осуществляется по формуле Вi = Ai / Σ Ai, где Вi – коэффициент весомости i–го показателя, Ai – бальная оценка i –го показателя.
Итерационные алгоритмы — алгоритмы улучшения первоначально заданной структуры. По своей сути это алгоритмы перебора, в которых каждый очередной вариант структуры образуется по определенному правилу и перебор заканчивается, когда следование этому правилу, не позволяет добиться дальнейшего улучшения. Количество проб здесь существенно меньше, чем при полном переборе, но нет гарантии получения наилучшего решения.
Рассмотрим алгоритм парных перестановок для решения задачи размещения элементов как пример итерационного алгоритма. В заданной структуре выбирается очередной элемент аiÎА, где А — множество элементов, и далее осуществляется перестановка элемента аi, с элементом аjÎА, i¹j. Получившийся новый вариант и представляет собой новую пробу, для этого варианта подсчитывается значение целевой функции. Следующий вариант структуры будет отличаться от исходного тем, что элемент аi меняется местами с другим элементом аk, k¹i, k¹j. Такие парные перестановки элемента аi осуществляются со всеми остальными элементами множества А, т. е. имеем п-1 пробу.
Из вариантов выбирается один, для которого значение целевой функции оказалось экстремальным. Данный вариант рассматривается как новое исходное размещение; в этом варианте структуры выбирается новый элемент а i+1 Для парных перестановок со всеми остальными элементами, далее производятся аналогичные действия.
Таким образом, перебор всех элементов для осуществления парных перестановок требует выполнения п(п—1) проб и составляет одну итерацию. Очередность выбора элемента А для парных перестановок с остальными элементами может быть произвольной, но лучше начинать перестановки с элементов, имеющих наибольшее число связей с остальными. Если на двух соседних итерациях не достигнуто улучшение целевой функции, то задача размещения считается решенной. Обычно требуется сравнительно малое число итераций, и поэтому общее число проб существенно меньше, чем п!.
Ранжирование представляет собой процедуру упорядочения объектов, выполняемую лицом, принимающим решение, или экспертом. На основе знаний и опыта лицо, принимающее решение, или эксперт располагают объекты в порядке предпочтения, руководствуясь одним или несколькими выбранными показателями сравнения. В зависимости от вида отношений между объектами возможны различные варианты упорядочения объектов.
Например: пусть среди объектов нет одинаковых по сравниваемым показателям, т.е. нет эквивалентных объектов. В этом случае между объектами существует только отношение строгого порядка. В результате сравнения всех объектов по отношению строгого порядка составляется упорядоченная последовательность, где объект с первым номером является наиболее предпочтительным. Объект со вторым номером менее предпочтителен первому объекту, но предпочтительнее всех остальных объектов и т.д.
Для решения задач функциональной оптимизации в последнее время часто используются адаптивные методы поиска. Представителями таких методов являются генетические алгоритмы. Адаптивные методы оптимизации основаны на генетических процессах в биологических организмах: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и принципу «выживает наиболее приспособленный» (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу, генетические алгоритмы способны «развивать» решения реальных задач, если те соответствующим образом закодированы. ГА нашли применение в оптимизации, искусственном интеллекте, инженерии знаний и других областях.
На рис. 2.1 изображена схема работы генетического алгоритма. Вначале генерируется (как правило, случайным образом) начальная популяция особей (индивидуумов), т. е. некоторый набор решений задачи. Затем моделируется размножение внутри данной популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора - чем приспособленное индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Далее моделируются мутации - в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и переходят к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько и начальная, но в силу отбора приспособленность в ней в среднем выше. Затем описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении будут возникать совершенно новые решения задачи. Среди них как плохие, так и хорошие, но благодаря отбору число хороших решений возрастет. Имитируя эволюцию на компьютере, всегда сохраняется жизнь лучшему из индивидуумов текущего поколения - такая методика называется стратегией элитизма.
Генетический алгоритм работает с некоторой целевой функцией Q(u1,u2,…,un) и в результате находит либо ее максимум, либо минимум (в зависимости от задачи). Алгоритм оперирует набором параметров u1,u2,…,un и находит такое решение, при котором достигается оптимальное значение функции Q. Для организации работы алгоритма не требуется находить производную от функции Q и выполнять другие вычисления, подразумевающие наличие какой-либо алгебраической функции. Другими словами генетический алгоритм может работать не только с целевой функцией, но и с каким-либо блоком (набором некоторых действий, операций и вычислений), который на вход получает некоторый набор значений u1,u2,…,un, а на выходе выдаёт результат, напрямую зависящий от входящих значений.
Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнится заданное число поколений или какой-либо иной критерий остановки.
Итак, есть некоторая система Q, зависящая от нескольких входных параметров u1,u2,…,un, и необходимо найти оптимальный набор выходных параметров у1, у2, • • •, Ут Входные параметры задачи являются генетическим материалом - генами. Совокупность генов составляет хромосому. Каждая особь обладает своей хромосомой, а следовательно, своим набором параметров. Подав некоторый набор параметров на вход системы Q, можно получить какое-то значение. То, насколько это значение удовлетворяет поставленным условиям, определяет характеристику особи, называемую приспособленностью. Функция, определяющая приспособленность, должна удовлетворять следующему условию: чем «лучше» особь, тем выше приспособленность.
Генети́ческий алгори́тм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. При описании генетических алгоритмов используются определения, заимствованные из генетики.
Популяция – это конечное множество особей
Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множеством параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организациями.
Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение.
В задачах оптимизации функция приспособленности, как правило оптимизируется и называется целевой функцией. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющая множество потенциальных решений проблемы, например, задачи оптимизации. Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».
Рассмотрим различные стратегии отбора родителей.
Панмиксия. Это самый простой оператор отбора. В соответствии с дан¬ной стратегией каждому члену популяции сопоставляется случайное целое число на отрезке [1; п], где п - количество особей в популяции. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффек¬тивность алгоритма, реализующего такой подход, снижается с ростом чис¬ленности популяции.
Селекция. В данной стратегии родителями могут стать только те особи, значение приспособленности которых не меньше порогового, например среднего значения функции приспособленности. Такой подход обеспечивает более быструю сходимость алгоритма, но не подходит для поиска нескольких экстремумов. Пороговое значение селекции может быть вычислено разными способами, например с применением турнирного и рулеточного (пропорцио¬нальные) отборов.
Ранговый отбор. Для каждой особи её вероятность попасть в промежу¬точную популяцию пропорциональна её порядковому номеру в отсортиро¬ванной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.
Инбридинг. Первый родитель выбирается случайным образом, а вторым родителем является член популяции, ближайший к первому. Близость опре¬деляется, например, как минимальное расстояние Хемминга для бинарных строк или евклидово расстояние между двумя вещественными векторами.
Аутбридинг. Использует понятие схожести особей, однако в этой стра¬тегии брачные пары формируются из максимально далёких особей.
Последние 2 способа по-разному влияют на поведение ГА. Инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что приво¬дит к разбиению популяции на группы вокруг подозрительных на экстремумы участков. Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным решениям, просматривая новые, неисследованные области.
Стратегии формирования нового поколения. Существует 2 основных типа формирования нового поколения после кроссовера и мутации:
- дети замещают родителей;
- новое поколение составляется из совокупности и детей, и их родителей.
Элитарный отбор - в новое поколение включается заданное количество лучших особей предыдущего поколения. Иногда этот метод комбинируют с дру¬гими. Использование стратегии элитизма не допускает потери лучших решений. К примеру, если популяция сошлась в локальном максимуме, а мутация вывела одну из строк в область глобального, то при замещении родителей весьма веро¬ятно, что эта особь в результате скрещивания будет потеряна и решение задачи не будет получено. Если же используется элитизм, то полученное хорошее реше¬ние будет оставаться в популяции до тех пор, пока не будет найдено лучшее.
Отбор вытеснением. В данном типе отбора выбор особи в новую попу¬ляцию зависит не только от степени её пригодности, но и от того, есть ли уже в формируемой популяции особь с аналогичным набором хромосом. Отбор проводится из числа родителей и их потомков. Таким образом, не теряются лучшие решения и постоянно поддерживается разнообразие, что увеличивает привлекательность этого метода в многоэкстремальных задачах.
Метод отжига (Больцмана). Вероятность отбора зависит от управляю¬щего параметра Т. Обычно вероятность попадания в новую популяцию вы¬числяется по следующей формуле: [нераспознанная формула]
где /(г) и /(j) - значения целевой функции г -й и j -й особей. Эти номера выбираются случайно. Если значение р окажется больше случайного числа на интервале (0; 1), то в новую популяцию попадёт особь /((), иначе f(j). Данный метод используется для узкого класса задач.
Генитор (Genitor). В данной модели используется специфичная стратегия отбора. На каждом шаге только одна пара случайных родителей создает только одного потомка. Этот потомок заменяет не родителя, а одну из худших особей популяции.
Таким образом, на каждом шаге в популяции обновляется только одна особь. Процесс продолжается до тех пор, пока пригодности хромосом не станут одинаковыми. В данный алгоритм можно добавить мутацию потомка после его создания. Исследования показали, что сходимость у генитора быстрее, чем у классического ГА.
Метод прерывистого равновесия. Данный метод основан на палеонтологической теории прерывистого равновесия, которая описывает быструю эволюцию за счёт вулканических и других изменений земной коры. Для применения метода предлагается после каждой генерации промежуточного поколения случайным образом перемешивать особи в популяции, а затем применять основной ГА. Для отбора пар используется панмиксия. Потомки, полученные кроссинговером, и наиболее приспособленные родители смешиваются. В новое поколение выбираются только те особи, пригодность которых выше средней. Такая модификация метода может позволить сократить неперспективные популяции и расширить те, в которых находятся лучшие индивидуальности. Используется для эффективного выхода из «локальных ям».
СHС (Eshelman). СПС - это Cross generational elitist selection. Heterogenous recombination. Cataclysmic mutation. Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается. Для скрещивания все особи разбиваются на пары, но скрещиваются только те пары, между которыми расстояние Хемминга больше некоторого порогового (также возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover), разновидность однородного кроссовера - каждому потомку переходит ровно половина бит каждого родителя.
Размер популяции небольшой, что оправдывает использование однородного кроссовера.
Данный алгоритм довольно быстро сходится, так как в нем нет мутаций. 13 этом случае СНС применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети бит). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.
Гибридныи алгоритм (Hybrid algorithm). Использование гибридного алгоритма позволяет объединить преимущества ГА с преимуществами классических методов оптимизации.
Дело в том, что ГА являются робастными алгоритмами, т. е. позволяют быстро находить хорошее решение во всей области поиска, но нахождение оптимального решения зачастую оказывается намного более грудной задачей в силу стохастичности принципов работы алгоритма. Многие классические алгоритмы оптимизации позволяют быстро найти локальный экстремум, но не могут найти глобальный оптимум. В связи с этим возникла идея использовать ГА на начальном этапе для эффективного сужения пространства поиска вокруг глобального экстремума, а затем, взяв лучшую особь, применить один из «классических» методов оптимизации.
Однако можно использовать «классические» методы (hill-climbing, например) и внутри самих ГА. Па каждом поколении каждый полученный потомок оптимизируется этим методом, таким образом, каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации. Такой метод ухудшает способность алгоритма искать решение с помощью отбора гиперплоскостей, но зато возрастает вероятность того, что одна из особей попадёт в область глобального максимума и после оптимизации окажется решением задачи.
ГА с нефиксированным размером популяции (Genetic A Igor ithm with Varying Population Size). В этом алгоритме каждой особи приписывается максимальный возраст, т. е. число поколений, по прошествии которых особь погибает. Введение этого нового параметра позволяет исключить оператор отбора в новую популяцию. Возраст каждой особи индивидуален и зависит от её приспособленности. В каждом поколении t создаётся дополнительная популяция из потомков. Её размер A(t) пропорционален размеру основной популяции S(t):
A(t)=S(t),
где - вероятность воспроизведения.
Для воспроизведения особи выбираются из основной популяции с равной вероятностью. После применения мутации и кроссинговера потомкам приписывается возраст. Возраст является константой на протяжении всей эволюции особи от рождения до гибели. Затем из основной популяции удаляются особи с истекшим сроком жизни и добавляются потомки из промежуточной популяции. Размер популяции после одной итерации алгоритма вычисляется по формуле
S(t+1)=S(t) + A(t) – D(t), где D{t) - число особей, которые умирают в поколении t.
Параллельные генетические алгоритмы. Генетические алгоритмы могут применяться при параллельных вычислениях. При этом формируется несколько отдельных популяций. По некоторому правилу выбираются особи из разных популяций на этапе формирования, таким образом происходит некоторая миграция между популяциями. Модель миграции представляет популяцию как множество подпопуляций. Каждая подпопуляция обрабатывается отдельно на время изоляции (некоторое количество поколений). По истечении этого срока происходит обмен особями. Отбор особей для миграции может происходить следующим образом:
- случайная однообразная выборка из числа особей;
- пропорциональный отбор, т. е. для миграции берутся наиболее пригодные особи.
Островная модель (island model) - модель параллельного генетического алгоритма. Разобьем популяцию на несколько подпопуляций. Каждая их них будет развиваться отдельно с помощью генетического алгоритма. Таким образом, можно сказать, что особи расселены но нескольким изолированным островам. Изредка (например, каждые 5 поколений) происходит миграция - острова обмениваются несколькими хорошими особями. Так как населённость островов невелика, то подпопуляции будут склонны к преждевременной сходимости. Поэтому важно правильно установить частоту миграции: чересчур частая миграция (или миграция слишком большого числа особей) приведет к смешению всех подпопуляций, и тогда островная модель будет несильно отличаться от обычного ГА. Если миграция будет слишком редкой, то она не сможет предотвратить преждевременного схождения подпопуляций.
Генетические алгоритмы стохастичны, поэтому при разных его запусках популяция может сходиться к разным хорошим решениям. Островная модель позволяет запустить алгоритм сразу несколько раз и совместить «достижения» разных островов для получения наилучшего решения.
ГА служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. ГА применяются для решения следующих задач: оптимизации многопараметрических функций и запросов в базах данных; обучения искусственных нейронных сетей; задач компоновки и размещения; игровых стратегий; составления расписаний и др. Генетические и эволюционные алгоритмы оптимизации являются алгоритмами случайно-направленного поиска и применяются в основном там, где сложно или невозможно сформулировать задачу в виде, пригодном для более быстрых алгоритмов локальной оптимизации (например, для градиентных алгоритмов). На сегодняшний день ГА хорошо себя зарекомендовали как универсальные методы глобального поиска, которые позволяют находить квазиоптимальные решения за приемлемое время.
Генетический алгоритм (ГА) позволяет найти удовлетворительное решение аналитически неразрешимых или сложнорешаемых проблем через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.
Генетические алгоритмы являются частью более общей группы методов, называемых эволюционными вычислениями, которые объединяют различные варианты использования эволюционных принципов для достижения поставленной цели. В группе эволюционных вычислений выделяют следующие направления: эволюционные стратегии, генетическое программирование, эволюционное программирование, обучаемые системы классификации.
Эволюционные стратегии – метод оптимизации, основанный на идеях адаптации и эволюции. Степень мутации в данном случае меняется со временем – это приводит к так называемой самоадаптации.
Генетическое программирование – применение эволюционного подхода к популяции программ.
Эволюционное программирование было впервые предложено Л. Дж. Фогелем в 190 г. для моделирования эволюции как процесса обучения с целью создания искусственного интеллекта. Он использовал конечные автоматы, предсказывающие символы в цифровых последовательностях, которые, эволюционируя, становились более приспособленными к решению поставленной задачи.
Обучаемые системы классификации – это обучаемые системы, сопоставляющие выходные результаты входным данным. Внутри они используют генетические алгоритмы при поиске новых правил этого отображения.
Все алгоритмы оптимизации могут быть разделены на 2 класса: детерминированные и вероятностные. Первые чаще всего используются при наличии ясной связи между характеристиками вероятных решений и их полезностью для решаемой задачи. Если эта связь не так очевидна или слишком сложна, или размерность поискового пространства очень велика, используются вероятностные алгоритмы.
Метод ветвей и границ является вариацией полного перебора с отсевом подмножеств решений, заведомо не содержащих оптимальных. Область допустимых решений рекурсивно разбивается на подобласти, образующие дерево поиска, и бесперспективные подобласти отбрасываются.
Поиск в пространстве состояний - это поиск успешных конфигураций (состояний), где конечной целью является нахождение целевого состояния с желаемыми параметрами. Отличительной особенностью этого метода является то, что ветви графа, описывающего пространство состояний, генерируются (и отбрасываются) динамически, по мере их исследования.
Алгоритмы Монте-Карло - это вероятностные алгоритмы с детерминированным временем работы, чей результат, однако, с определенной долей вероятности может быть неверным. Они основываются на повторяющемся случайном семплировании. Наиболее простой пример такого алгоритма - это алгоритм прямого поиска, итеративно перемещающийся в поисковом пространстве от решения к решению.
Важным классом вероятностных алгоритмов Монте-Карло являются эволюционные вычисления. Они включают в себя алгоритмы, основанные на итеративно изменяющемся наборе кандидатов в решения (популяции). )то множество методов оптимизации является подклассом мягких вычислений (алгоритмов, используемых для получения неточных решений вычислительно сложных задач), а также входит в область искусственного интеллекта.
Эволюционные алгоритмы можно разбить на несколько групп:
- генетические алгоритмы работают с пространствами поиска, состоящими из битовых строк;
- эволюционные стратегии исследуют пространство вещественных векторов ;
- генетическое программирование включает в себя эволюционные алгоритмы, автоматически создающие и улучшающие программы, выполняющие целевую задачу;
- обучаемые системы классификации сопоставляют выходные результаты входным данным. Внутри они используют генетические алгоритмы для поиска новых правил для этого отображения;
- эволюционное программирование является эволюционным подходом, который рассматривает экземпляры генома как различные виды, а не различные особи.
Меметические алгоритмы являются модификацией эволюционных алгоритмов с самостоятельным улучшением каждой особи при помощи проблемно-специфичных операторов. Гармонический поиск - это вариация генетического алгоритма, при которой каждая переменная подстраивается под другие так, чтобы получить общую «гармонию» (глобальный оптимум).
Алгоритмы роевого интеллекта имитируют коллективное поведение децентрализованных самоорганизующихся природных систем. Муравьиный алгоритм предназначен для решения задач поиска маршрутов на графе за полиномиальное время. Он использует модель поведения муравьев, которые ищут путь от колонии до источника питания. Метод роя частиц имитирует поведение стаи птиц или косяка рыб. Когда такие группы ищут пищу, каждая особь («частица») действует относительно независимо, имея некоторую степень свободы и случайности поведения. Однако, когда особь найдет источник пищи, она известит об этом других особей в стае, и они последуют за ней.
Алгоритм подъёма - это, в некотором смысле, эволюционный алгоритм с единственной особыо в популяции. Он использует лучшую из полученных особей для создания единственного потомка. Если этот потомок более успешен, чем родительская особь, он ее заменяет и повторяет цикл воспроизводства. В противном случае цикл повторяется со старой особью. Поиск с запретами расширяет алгоритм подъёма, запрещая возврат в уже использованные возможные решения. Такой подход, с одной стороны, уменьшает шанс «застревания» алгоритма в локальном оптимуме, а с другой - усложняет алгоритм и может привести к отказу от очень приспособленных особей. Для решения последней задачи может вводиться дополнительное правило, исключающее отдельные решения из списка запрещённых.
Алгоритм имитации отжига использует модель отжига металлов, при котором в металле уже сформировалась кристаллическая решётка, однако атомы всё еще могут перейти из одной ячейки в другую с некоторой вероятностью. Эта вероятность понижается с уменьшением температуры; кроме того, атом может перейти только в состояние с меньшим уровнем энергии - таким образом, полученная кристаллическая решетка имеет наименьший уровень энергии. Метод стохастического туннелирования семплирует целевую функцию случайными «прыжками» от текущего лучшего решения.
В металлургии отжигом называется термическая обработка металла, заключающаяся в его нагреве до определенной температуры, выдержке и последующем - обычно медленном - охлаждении.
В начале 1950-х гг. группа исследователей под руководством Николаса Метрополиса (Nicholas Metropolis) разработала метод Монте-Карло, позволяющий вычислять свойства субстанций, которые могут быть рассмотрены как системы отдельных взаимодействующих молекул [3]. Этот метод копирует физический процесс, который может быть использован для имитации описанного процесса рекристаллизации в металлах.
Именно работа Метрополиса вдохновила Скотта Киркпатрика (Scott Kirkpatrick) и его коллег на создание вероятностного метаэвристического метода оптимизации, названного ими алгоритмом имитации отжига. Независимо от них, примерно в то же время V. Сеrny применил похожий подход к решению задачи о коммивояжёре.
Вернемся к имитируемому физическому процессу. Каждая конфигурация системы (т. е. множество позиций её атомов) характеризуется вероятностным коэффициентом Больцмана:
где Ej - энергия системы в состоянии i; Т — абсолютная температура;
к = 1,380 • 10 Дж / — постоянная Больцмана.
Алгоритм имитации отжига требует для работы единственного начального решения. На каждом шаге к текущему решению применяется оператор мутации и оно модифицируется случайным образом. Вычисляется энергия полученного состояния, и, если она окажется меньше энергии предыдущего, происходит безусловный переход к новому состоянию. Если энергия нового решения больше, чем энергия предыдущего, переход осуществляется с вероятностью, определяемой коэффициентом Больцмана.
Кроме того, в процессе работы алгоритма снижается значение температуры, что имитирует процесс медленного остывания металла при отжиге. При этом, поскольку температура определяет коэффициент Больцмана, постепенно снижается вероятность перехода системы к новому состоянию. Критерием останова алгоритма является достижение температурой минимального значения - нуля градусов.
Характер изменения температуры оказывает огромное влияние на тщательность исследования пространства поиска и скорость сходимости алгоритма. Наиболее очевидным вариантом является её линейное уменьшение, когда на каждом шаге алгоритма значение температуры уменьшается на некоторую константу, пока не достигнет нуля. Возможны, однако, и более сложные (и, вместе с тем, более эффективные) способы управления температурой. Можно снижать температуру от значения Т до (1-)T’ каждые несколько итераций. Значение Ɛ, очевидно, должно лежать в пределах (0;l). Также можно заранее выбрать число итераций К и уменьшать значение температуры через каждые несколько итераций до значения =T0 (l -к/К)а, где константу а обычно выбирают равной 1, 2 или 4. Чем больше ее значение, тем медленнее будет снижаться температура. Псевдокод алгоритма имитации отжига:
current <- init
iteration <- О
while not terminationCriteria
T <- getTemperatureForlteration(iteration) new <- mutate(current) dE = f(new) - f(current)
if dE > 0 or randomO < exp(-dE/(kB*T)) current <- new iteration <- iteration + 1
В приведенном алгоритме функция getTemperatureForIteration() вычисляет текущую температуру для заданного шага. Конкретная реализация этой функции зависит от выбранной характеристики изменения температуры.
Алгоритм имитации отжига успешно применяется для решения сложных комбинаторных задач и задач оптимизации функций. Он эффективно исследует поисковые пространства со сложной структурой, позволяя находить оптимумы для целевых функций с большой долей нелинейности и стохастичности. Алгоритмическая сложность метода довольно низка, благодаря чему его реализация не представляет больших трудностей. К недостаткам метода следует отнести зачастую слишком низкую скорость сходимости, а также сложность выбора значений настраиваемых параметров. Эти недостатки частично или полностью устранены в его модификациях (например, в адаптивном алгоритме имитации отжига) и являются предметом дальнейших исследований.
Стая птиц представляет собой прекрасный пример коллективного поведения животных. Летая большими группами, они почти никогда не сталкиваются в воздухе. Стая двигается плавно и скоординировано.Как и колония Муравьёв или пчёл, стая представляет собой роевой интеллект. Птицы в ней действуют согласно определенным - довольно простым — правилам. Кружа в небе, каждая из птиц следит за своими сородичами и координирует свое движение согласно их положению, а найдя источник пищи, она оповещает их об этом.
На последнем факте следует остановиться подробнее, поскольку он играет ключевую роль в рассматриваемом методе оптимизации. Причины такого «альтруизма» птиц (и других животных, действующих сходным образом) являлись предметом исследования многих социобиологов. Одним из наиболее популярных объяснений этого феномена является то, что преимущества от такого поведения каждой особи стаи больше, чем такие очевидные недостатки, как необходимость борьбы за найденную пищу с другими особями. Источники пищи обычно расположены случайным образом, поэтому в одиночестве птица вполне может погибнуть, не найдя ни одного из них в течение долгого времени. Однако если все птицы будут «играть по правилам», делясь с сородичами информацией о находках, то шансы каждой из них на выживание резко повышаются. Таким образом, будучи неэффективной для отдельной особи, такая стратегия является залогом эффективности стаи и вида в целом.
Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 г. компьютерной модели, которую он назвал Boids . Для имитации поведения стаи птиц Рейнольдс запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал 3 простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.
Результаты первых же имитаций удивили самого автора: несмотря на простоту лежащих в основе программы алгоритмов, стая на экране выглядела крайне правдоподобно. Птицы сбивались в группы, уходили от столкновений и даже хаотично метались точь-в-точь как настоящие.
Как специалист в области компьютерной графики, Крейг Рейнольдс был в первую очередь заинтересован визуальной стороной результатов созданной им имитации. Однако в посвящённой Boids статье он также отметил, что разработанная им поведенческая модель может быть расширена введением таких дополнительных факторов, как поиск пищи или боязнь хищников.
Классический алгоритм роя частиц . В 1995 г. Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Russel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц. Вдохновением для них послужила имитационная модель Рейнольдса, а также работа Хеппнера (Неррпег) и Гренадера (Grenader) на схожую тему. Кеннеди и Эберхарт отметили, что обе модели основаны на управлении дистанциями между птицами, а следовательно, синхронность стаи является в них функцией от усилий, которые птицы прилагают для сохранения оптимальной дистанции.
Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где аген- ты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями.
Текущее состояние частицы характеризуется координатами в пространстве решений (т. е., собственно, связанным с ними решением), а также вектором скорости перемещения. Оба этих параметра выбираются случайным образом на этапе инициализации. Кроме того, каждая частица хранит координаты лучшего из найденных ею решений, а также лучшее из пройденных всеми частицами решений - этим имитируется мгновенный обмен информацией между птицами.
На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствии со сведениями о найденных оп- тимумах. Значение для i-й компоненты вектора скорости частицы v = (vj, vi,..., vj) определяется по формуле
Vj = Vj + а1rmd() (pbest - Xj) + a2 rmd() (gbest - x), где a1, a2 — постоянные ускорения; функция md() возвращает случайное число от 0 до 1 включительно; pbest- лучшая найденная частицей точка; gbest - лучшая точка из пройденных всеми частицами системы; хi,- - текущее положение частицы. После вычисления направления вектора v частица перемещается в точку Xj = Xj + Vj. При необходимости обновляются значения лучших точек для каждой частицы и для всех частиц в целом. Далее цикл повторяется.
Модификации классического алгоритма роя частиц. Алгоритм роя частиц появился относительно недавно, однако различными исследователями уже был предложен целый ряд его модификаций, и новые работы на эту тему не перестают публиковаться. Можно выделить несколько путей улучшения классического алгоритма, реализованных в большинстве из них. Это соединение алгоритма с другими алгоритмами оптимизации, уменьшение вероятности преждевременной сходимости изменением характеристик движения частиц, а также динамическое изменение параметров алгоритма во время оптимизации. Далее рассмотрены наиболее примечательные из модификаций.
В том же 1995 г. была опубликована статья Кеннеди и Эберхарта, в которой они назвали оригинальный алгоритм «GBEST», поскольку он использует глобальное лучшее решение (global best) для формирования векторов скоростей, а также предложили его модификацию, названную ими «LBEST». При обновлении направления и скорости движения частицы в LBEST используют информацию о решениях соседних с ними частиц:
Vj = Vj + а1rmd() (pbes - Xj) + a2 rmd() (gbest - ),
где lbest - лучший результат среди частицы и ее соседей. Соседними считаются либо частицы, отличающиеся от данной индексом не более чем на некоторое заданное значение, либо частицы, расстояние до которых не превышает заданного порога.
Данный алгоритм тщательнее исследует пространство поиска, однако работает медленнее оригинального. При этом, чем меньшее число соседей учитывается при формировании вектора скорости, тем ниже скорость сходимости алгоритма, но тем эффективнее он избегает субоптимальных решений.
Inertia Weighted PSO. В 1998 г. Юхи Ши (Yuhui Shi) и Рассел Эберхарт предложили модификацию, на первый взгляд совсем незначительно отличающуюся от классического алгоритма. В своей статье Ши и Эберхарт заметили, что одной из главных проблем при решении задач оптимизации является баланс между тщательностью исследования пространства поиска и скоростью сходимости алгоритма. В зависимости от задачи оптимизации и характеристик поискового пространства в ней этот баланс должен быть различным.
С учётом этого Ши и Эберхарт предложили изменить правило обновления векторов скоростей частиц:
Vj = w *, + а1rmd() (pbes - Xj) + a2 rmd() (gbest - ),, где w - коэффициент инерции, определяющий упомянутый баланс между широтой исследования и вниманием к найденным субоптимальным решениям. Если w > 1, скорости частиц увеличиваются, частицы разлетаются в стороны и тщательнее исследуют пространство. В противном случае скорости частиц со временем уменьшаются и, следовательно, скорость сходимости зависит от выбора параметров а.
Time-Varying Inertia Weighted PSO. В своей работе 1998 г. Ши и Эберхарт отметили, что инерция не обязательно должна быть положительной константой: она может изменяться во время работы алгоритма по линейному и даже нелинейному закону. В статье 1999 г. и более поздних работах они чаще всего использовали линейный закон убывания как достаточно эффективный и вместе с тем простой. Тем не менее, разрабатывались и успешно применялись и другие законы изменения инерции.
Значение коэффициента инерции может как убывать, так и расти. При его убывании частицы сначала исследуют область поиска экстенсивно, находя множество субоптимальных решений, и со временем все более концентрируются на исследовании их окрестностей. Возрастание инерции способствует сходимости алгоритма на поздних стадиях его работы.
Canonical PSO. В 2002 г. Марис Клер (Maurice Clerc) и Джеймс Кеннеди предложили свою модификацию алгоритма роя частиц, которая стала настолько популярной, что теперь её принято называть каноническим алгоритмом роя частиц. Он позволяет избавиться от необходимости «угадывать» подходящие значения регулируемых параметров алгоритма, контролируя сходимость частиц.
Муравья нельзя назвать сообразительным. Отдельный муравей не в состоянии принять ни малейшего решения. Дело в том, что он устроен крайне примитивно: все его действия сводятся к элементарным реакциям на окружающую обстановку и своих собратьев. Муравей не способен анализировать, делать выводы и искать решения.
Эти факты, однако, никак не согласуются с успешностью муравьев как вида. Они существуют на планете более 100 миллионов лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны. В сравнении с полной беспомощностью отдельных особей, достижения муравьев кажутся немыслимыми.
Добиться таких успехов муравьи способны благодаря своей социальности. Они живут только в коллективах – колониях. Все муравьи колонии формируют так называемый роевой интеллект. Особи, составляющие колонию, не должны быть умными: они должны лишь взаимодействовать по определенным – крайне простым – правилам, и тогда колония целиком будет эффективна.
В колонии нет доминирующих особей, нет начальников и подчиненных, нет лидеров, которые раздают указания и координируют действия. Колония является полностью самоорганизующейся. Каждый из муравьев обладает информацией только о локальной обстановке, не один из них не имеет представления обо всей ситуации в целом – только о том, что узнал сам или от своих сородичей, явно или неявно. На неявных взаимодействиях муравьев, называемых стигмергией, основаны механизмы поиска кратчайшего пути от муравейника до источника пищи.
Каждый раз проходя от муравейника до пищи и обратно, муравьи оставляют за собой дорожку феромонов. Другие муравьи, почувствовав такие следы на земле, будут инстинктивно устремляться к нему. Поскольку эти муравьи тоже оставляют за собой дорожки феромонов, то чем больше муравьев проходит по определенному пути, тем более привлекательным он становится для их сородичей. При этом, чем короче путь до источника пищи, тем меньше времени требуется муравьям на него – а следовательно, тем быстрее оставленные на нем следы становятся заметными.
В 1992 году в своей диссертации Марко Дориго (Marco Dorigo) предложил заимствовать описанный природный механизм для решения задач оптимизации [1]. Имитируя поведение колонии муравьев в природе, муравьиные алгоритмы используют многоагентные системы, агенты которых функционируют по крайне простым правилам. Они крайне эффективны при решении сложных комбинаторных задач – таких, например, как задача коммивояжера, первая из решенных с использованием данного типа алгоритмов.
Классический муравьиный алгоритм для решения задачи коммивояжера
Как было сказано выше, муравьиный алгоритм моделирует многоагентную систему. Ее агентов в дальнейшем будем называть муравьями. Как и настоящие муравьи, они довольно просто устроены: для выполнения своих обязанностей они требуют небольшое количество памяти, а на каждом шаге работы выполняют несложные вычисления.
Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается.
Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их.
Пусть муравей находится в узле , а узел – это один из узлов, доступных для перехода: . Обозначим вес ребра, соединяющего узлы и , как , а интенсивность феромона на нем – как . Тогда вероятность перехода муравья из в будет равна:
где и – это регулируемые параметры, определяющие важность составляющих (веса ребра и уровня феромонов) при выборе пути. Очевидно, что при алгоритм превращается в классический жадный алгоритм, а при он быстро сойдется к некоторому субоптимальному решению. Выбор правильного соотношения параметров является предметом исследований, и в общем случае производится на основании опыта.
После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути:
,
где – длина пути, а – регулируемый параметр. Кроме этого, следы феромона испаряются, то есть интенсивность феромона на всех ребрах уменьшается на каждой итерации алгоритма. Таким образом, в конце каждой итерации необходимо обновить значения интенсивностей:
Обзор модификаций классического алгоритма
Результаты первых экспериментов с применением муравьиного алгоритма для решения задачи коммивояжера были многообещающими, однако далеко не лучшими по сравнению с уже существовавшими методами. Однако простота классического муравьиного алгоритма (названного «муравьиной системой») оставляла возможности для доработок – и именно алгоритмические усовершенствования стали предметом дальнейших исследований Марко Дориго и других специалистов в области комбинаторной оптимизации. В основном, эти усовершенствования связаны с большим использованием истории поиска и более тщательным исследованием областей вокруг уже найденных удачных решений. Ниже рассмотрены наиболее примечательные из модификаций.
Elitist Ant System
Введение в алгоритм так называемых «элитных муравьев». Опыт показывает, что проходя ребра, входящие в короткие пути, муравьи с большей вероятностью будут находить еще более короткие пути. Таким образом, эффективной стратегией является искусственное увеличение уровня феромонов на самых удачных маршрутах. Для этого на каждой итерации алгоритма каждый из элитных муравьев проходит путь, являющийся самым коротким из найденных на данный момент.
Эксперименты показывают, что, до определенного уровня, увеличение числа элитных муравьев является достаточно эффективным, позволяя значительно сократить число итераций алгоритма. Однако, если число элитных муравьев слишком велико, то алгоритм достаточно быстро находит субоптимальные решение и застревает в нем. Как и другие изменяемые параметры, оптимальное число элитных муравьев следует определять опытным путем.
Ant-Q
Лука Гамбарделла и Марко Дориго опубликовали в 1995 представили муравьиный алгоритм, получивший свое название по аналогии с методом машинного обучения Q-learning. В основе алгоритма лежит идея о том, что муравьиную систему можно интерпретировать как систему обучения с подкреплением. Ant-Q усиливает эту аналогию, заимствуя многие идеи из Q-обучения.
Алгоритм хранит Q-таблицу, сопоставляющую каждому из ребер величину, определяющую «полезность» перехода по этому ребру. Эта таблица изменяется в процессе работы алгоритма – то есть обучения системы. Значение полезности перехода по ребру вычисляется исходя из значений полезностей перехода по следующим ребрам в результате предварительного определения возможных следующих состояний. После каждой итерации полезности обновляются исходя из длин путей, в состав которых были включены соответствующие ребра.
Ant Colony System
В 1997 году те же исследователи опубликовали работу, посвященную еще одному разработанному ими муравьиному алгоритму [5]. Для повышения эффективности по сравнению с классическим алгоритмом, ими были введены три основных изменения.
Во-первых, уровень феромонов на ребрах обновляется не только в конце очередной итерации, но и при каждом переходе муравьев из узла в узел. Во-вторых, в конце итерации уровень феромонов повышается только на кратчайшем из найденных путей. В-третьих, алгоритм использует измененное правило перехода: либо, с определенной долей вероятности, муравей безусловно выбирает лучшее – в соответствие с длиной и уровнем феромонов – ребро, либо производит выбор так же, как и в классическом алгоритме.
Max-min Ant System
В том же году Томас Штютцле (Tomas Stützle) и Хольгер Хоос (Holger Hoos) предложили муравьиный алгоритм, в котором повышение концентрации феромонов происходит только на лучших путях из пройденных муравьями [6]. Такое большое внимание к локальным оптимумам компенсируется вводом ограничений на максимальную и минимальную концентрацию феромонов на ребрах, которые крайне эффективно защищают алгоритм от преждевременной сходимости к субоптимальным решениям.
На этапе инициализации, концентрация феромонов на всех ребрах устанавливается равной максимальной. После каждой итерации алгоритма только один муравей оставляет за собой след – либо наиболее успешный на данной итерации, либо, аналогично алгоритму с элитизмом, элитный. Этим достигается, с одной стороны, более тщательное исследование области поиска, с другой – его ускорение.
ASrank
Бернд Бульнхаймер (Bernd Bullnheimer), Рихард Хартл (Richard F. Hartl) и Кристине Штраусс (Christine Strauß) разработали модификацию классического муравьиного алгоритма, в котором в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей [7]. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции. Кроме того, для более тщательного исследования окрестностей уже найденных удачных решений, алгоритм использует элитных муравьев.
Этот подход нашел применение в решении задачи коммивояжера и многих других комбинаторных проблем, в числе которых задачи о назначениях, задача раскраски графа, задачи маршрутизации, задачи из областей data mining и распознавания образов и другие.
Эффективность муравьиных алгоритмов сравнима с эффективностью общих метаэвристических методами, а в ряде случаев – и с проблемно-ориентированными методами. Наилучшие результаты муравьиные алгоритмы показывают для задач с большими размерностями областей поиска. Муравьиные алгоритмы хорошо подходят для применения вместе с процедурами локального поиска, позволяя быстро находить начальные точки для них.
Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать анализ способа выбора настраиваемых параметров алгоритмов. В последние годы предлагаются различные способы адаптации параметров алгоритмов «на лету». Поскольку от выбора параметров сильно зависит поведение муравьиных алгоритмов, именно к этой проблеме обращено наибольшее внимание исследователей на данный момент.
Описание алгоритма
Метод пчелиной колонии относится к методам оптимизации, заимствовавшим основные принципы работы из живой природы. Этот метод сравнительно молодой, впервые предложен Д. Карбога в 2005 году. Суть метода заключается в моделировании поведения колонии пчел в поисках нектара.
В обычной колонии предполагается, что пчела может выполнять одну из трех ролей: активный (занятый) фуражир, фуражир-разведчик и неактивный фуражир (наблюдатель).
Активные фуражиры летят к источнику нектара, обследуют соседние источники, собирают нектар и возвращаются в улей.
Разведчики обследуют местность вокруг улья в поисках новых источников нектара. Примерно 10% пчел-фуражиров в улье задействованы в качестве разведчиков.
В любой момент некоторое количество пчел-фуражиров неактивно. Они ждут неподалеку от входа в улей. Когда активные фуражиры и разведчики возвращаются в улей, то в зависимости от качества источника нектара, который они только что посетили, они могут исполнять виляющий танец (waggle dance) перед ждущими неактивными пчелами. Есть довольно веские доказательства того, что этот виляющий танец несет информацию неактивным пчелам о местонахождении и качестве источника нектара. Неактивные фуражиры извлекают из виляющего танца эту информацию об источниках нектара и могут становиться активными фуражирами.
В целом, активный фуражир продолжает собирать нектар из конкретного источника до тех пор, пока он не истощится, после чего эта пчела становится неактивным фуражиром.
Сначала из улья в случайном направлении вылетает какое-то количество пчел-разведчиков, которые пытаются отыскать участки, где есть нектар. После того, как они возвращаются в улей, они исполняют «виляющий танец», на основании которого в окрестности посылаются активные фуражиры. После отправки активных фуражиров можно снова отправлять разведчиков в другие случайные точки.
Далее снова находятся лучшие участки, на этот раз не только среди разведчиков, но среди всех отправленных пчел. Запоминается лучший участок местности. Каждая пчела хранит информацию о наилучшем участке, на котором она побывала, и наилучшем участке для всего роя. В соответствии с этим рассчитывается вектор полета пчелы.
Алгоритм повторяется до тех пор, пока не выполнится критерий останова.
Схема пошагового выполнения:
1 Инициализировать популяцию случайными решениями
2 Посчитать фитнесс популяции
3 Запомнить лучшее решение
4 Выбрать участки для исследования их окрестностей
5 Отправить пчел в окрестности выбранных участков (больше пчел на лучшие участки) и посчитать фитнесс
6 Отправить оставшихся пчел на случайный поиск и посчитать их фитнесс
7 Прейти на пункт 3
Многомерная оптимизация на основе метода пчелиной колонии
Использование метода пчелиной колонии для нахождения глобального оптимума функции имеет ряд преимуществ, т.к. для использования этого метода к функции можно не предъявлять ряд требований, таких, как непрерывность, дифференцируемость, унимодальность.
В каждой реализации алгоритма пчелиной колонии должно присутствовать три метода: метод, обеспечивающий генерацию случайного решения, метод, генерирующий смежную область для данного решения и метод, вычисляющий добротность решения (фитнесс функции).
Т.к. реальные пчелы-разведчики при выборе источника нектара пользуются также генетическим материалом, то с помощью процедуры скрещивания можно смоделировать именно этот аспект поведения пчел. Агенты, участвующие в скрещивании, определяются на основе метода имитации отжига.
Работу алгоритма по нахождению минимума функции можно представить в виде следующих шагов:
Шаг 1. Задаются параметры метода
Шаг 2. Создаются начальные агенты разведчики
Шаг 2.1. Для каждого агента-разведчика случайным образом вычисляется решение – координата пчелки
Шаг 2.2. Для полученных решений рассчитывается полезность как значение оптимизируемой функции в найденных координатах
Шаг 2.3. Устанавливается счетчик итераций, количество разведчиков и начальная температура
Шаг 3. Выбираются рабочие агенты
Шаг 3.1. Выбирается лучшая пчелка с наибольшей полезностью
Шаг. 3.2. Выбирается некоторое количество пчел, для которых полезность их решения в определенной степени не хуже, чем наибольшая полезность
Шаг 4. Создание новых агентов на базе отобранных рабочих агентов и лучшего агента (скрещивание)
Шаг 4.1. Создание агентов на базе рабочих агентов. Координата нового агента вычисляется с учетом координаты рабочего агента и лучшей пчелы. Таким образом, новый агент попадает в окрестность решения старого агента.
Шаг 4.2. Создание агентов на базе лучшего агента аналогично.
Шаг 4.3. Корректировка координат новых агентов так, чтобы они не выходили за границы диапазона
Шаг 4.4. Рассчитываем полезность полученных решений для новых агентов
Шаг 4.5. Выбираем нового лучшего агента
Шаг 5. Моделирование «виляющего танца», в результате которого отобранные агенты могут исполнить танец, а неактивные фуражиры наблюдатели могут принять решение последовать за ними.
Преимущества методов пчелиной колонии для решения оптимизационных задач:
– не приводят к зацикливанию в локальных оптимумах, поскольку основаны на случайном поиске;
– поиск лучшего решения основывается на решениях агентов всей колонии пчел;
– применяются в динамических приложениях, поскольку способны адаптироваться к изменениям окружающей среды;
– используются для решения как дискретных, так и непрерывных задач оптимизации.
К недостаткам методов пчелиной колонии можно отнести:
– достаточно высокую итеративность;
– трудности теоретического анализа процесса получения решений, обусловленные тем, что поиск решения имеет стохастическую природу;
– априорную неопределенность времени сходимости, хотя сходимость гарантируется;
– зависимость метода от настройки параметров, подбираемых экспериментально.
Данный метод предназначен для нахождения минимума функции J(Z), X∈R^p, при неизвестном градиенте ∇J(X), где X – позиция бактерии в пространстве поиска Rp, а с помощью J(θ) моделируется полезные и вредные свойства среды, т.е. J(X) характеризует, где находится аттрактанты и репелленты. Таким образом, J<0, J=0, J>0 означает, что бактерия находится в полезной, нейтральной и вредной среде, соответственно.
Пусть P(j,k,l) = {Xi(j,k,l), I =1,2,…,S} описывает позицию каждого члена популяции S бактерий на j-ом хемотаксическом шаге, k-ом шаге воспроизведения и на l-ои событии исключения-рассеивания.
Тогда работу метода оптимизации с помощью моделирования фуражировки бактерий можно представить в виде последовательности выполнения следующих шагов:
Шаг 1 Инициализация. Задаются параметры, влияющие на работу метода: S – количество бактерий, Nre – количество шагов воспроизведения, Nc – количество хемотаксических шагов, Ned – количество событий исключения-рассеивания; Ped – вероятность рассеивания. Случайным образом распределить начальные значения Xi, I = 1,2,…,S по пространству поиска. Рассчитываются начальные значения целевой функции для каждой бактерии Ji.
Шаг 2 Установить: l = l+1.
Шаг 3 Установить: k = k+1.
Шаг 4 Установить: j = j+1.
Шаг 5 Для каждой бактерии моделируются хемотаксис: кувыркание, перемещение и скольжение.
5.1 Установить: i = i+1.
5.2 Кувыркание. Моделирование кувыркания достигается за счёт генерации вектора случайных чисел φ(j)ϵR^p:
φ=∆/√(∆^T ∆), где ∆ - вектор случайных чисел в интервале [-1;1].
Вектор φ представляет собой множество длин для соответствующих измерений.
5.3 Перемещение. Рассчитывается новое положение i-ой бактерии по формуле:
X^i (j+1,k,l)=X^i (j,k,l)+C(i)φ(j) ,где С(i)>0 – размер шага в определённом направлении, позволяющий моделировать процесс кувыркания.
Для новой позиции X^i (j+1,k,l) рассчитывается соответствующее значение целевой функции J(i,j+1,k,l).
5.4 Сложение. Если в позиции X^i (j+1,k,l) значение J(i,j+1,k,l) лучше, чем в позиции X^i (j k,l), то есть выполняется условие: J(i,j+1,k,l)< J(i,j k,l), тогда производится следующий хемотаксический шаг с повторение может повторятся Ns раз. Если условие не выполняется, то переход к шагу 5.5.
5.5 Если i<S, то переход к шагу 5.1, в противном случае – переход к шагу 6.
Шаг 6 Если j<Nc, то переход к шагу 4, в противном случае – переходим к шагу 7.
Шаг 7 Воспроизведение. Менее здоровые бактерии умирают, а остальные разделяются на две бактерии, при этом новые бактерии размещаются в ту же самую точку пространства поиска. За счёт такого подхода обеспечивается неизменность общего количества бактерий. Для этого все агенты сортируются в соответствии с полученными значениями целевой функции, после чего худшая половина(менее здоровые бактерии) отбрасываются, а лучшая(более здоровые бактерии) – дублируются.
Шаг 8 Если k<Nre, тогда выполняется переход к шагу 3, в противном случае – переход к шагу 9.
Шаг 9 Исключение и рассеивание. Жизнь популяции бактерий в окружающей среде может меняться либо постепенно (например, путём потребления полезных веществ), либо внезапно в связи с некоторым другим воздействием. Может произвести так, что все бактерии в области погибнут, или колония бактерий будет рассеяна в другую часть окружающей среды. Данный эффект может помешать возможному хемотаксическому прогрессу, но в то же время этот эффект и помогает, поскольку, в случае рассеивания, бактерии могут разместиться около хороших источников с полезными веществами. Исключение и рассеивание помогают понизить вероятность стагнации, то есть зацикливания в локальном оптимуме, что часто наблюдается в традиционных методах оптимизации(например, метод Коши, Ньютона).
В соответствии с данным подходом каждая бактерия с вероятностью Ped размещается в случайно выбранной точке пространства поиска.
Таким образом, проверяется условие: Ui<Ped, где Ui – случайное число в интервале[0;1] для i-ой бактерии.
Если данное условие выполняется, то бактерия помещается в позицию Xi(j,k,l), полученную случайным образом.
Шаг 10 Если l<Ned, тогда выполняется переход к шагу 2, в противном случае – к шагу 11.
Шаг 11 Выбирается и сохраняется лучшее решение Jbest и соответствующая позиция Xbest, в которой достигается лучшее решение Jbest.
Шаг 12 Проверка на окончание поиска. Если были выполнены все циклы для всех агентов, то выполняется переход к шагу 14, в противном случае выполняется перезапуск – переход к шагу 13
Шаг 13 Перезапуск агентов: выбирается новые случайные позиции для каждого агента Xi, I = 1,2,…,S и рассчитываются соответствующими значения целевой функции Ji, i=1,2,…,S. Счётчики циклов сбрасываются в 0: j=0; k=0; l=0.
Шаг 14 Остановка.
Блок-схема алгоритма:
Является одним из направлений искусственного интеллекта, который основан на моделировании и использовании эволюционных процессов общественных структур. Оп представляет собой совокупность двух пространств, взаимодействие между которыми определяется соответствующим протоколом или набором правил. ( см ниже)
Компонента «общество « состоит из индивидуумов, каждый из которых обладает собственным видением решения проблемы в исследуемой сфере. Лучшие из таких суждений за период существования поколения формируют «общественное мнение». Протокол ( передача-влияние) , в свою очередь, определяет меняющуюся с течением времени зависимость одного компонента от другого: обновление мнений, при появлении нового поколения, и влияние полученных решений на генерацию новых. Описание алгоритма см ниже:
Рассмотрим применение данного алгоритма для решения задачи топологической оптимизации компьютерной сети. Согласно концепции алгоритма ключевым элементом моделируемой системы являются представители популяции. Множество представителей формируют «общество». У каждого из них есть собственное представление об исследуемой области (суждение). Для задачи топологической оптимизации оно может быть представлено следующим выражением {2,0,3,1} ( Т.Е. насколько я понял, в данном случае узел представляется индивидуумом, а совокупность узлов – обществом). Данная запись задает предполагаемую последовательность соединения объектов сети в оптимальную топологию. После выбора первого объекта в сети, обновляется общественное мнение, путем исключения выбранного узла и обновляется общество, путем исключения уже выбранных узлов.
Алгоритм подъёма является одним из старейших алгоритмов оптимизации, относящихся к классу метаэвристических алгоритмов Монте-Карло. Алгоритм относительно прост в реализации, однако во многих случаях он показывает результаты, сопоставимые с результатами работы более сложных алгоритмов имитации отжига и поиска с запретами, выигрывая у них в вычислительной сложности и, следовательно, скорости.
На каждой итерации алгоритм создает единственное новое решение, базирующееся на лучшем из найденных ранее решений. Если новое решение лучше исходного (т. е. значение целевого критерия с использованием нового решения меньше предыдущего), то потомок заменяет родителя и алгоритм переходит к следующей итерации. В противном случае на следующей итерации используется старое решение. Таким образом, алгоритм является жадным - он всегда двигается к лучшему из найденных на данный момент решений.
В определённом смысле алгоритм подъёма можно назвать упрощённой разновидностью генетических алгоритмов со значением размера популяции, равным единице. Опишем работу алгоритма подъёма с помощью псевдокода:
solution <- initSolution while not terminationCriteria do
offspring <- mutate(solution) if cost(offspring) < cost(solution) then solution <- offspring return solution
В качестве критерия останова terminationCriteria могут применяться такие характеристики, как достижение определённого числа шагов алгоритма, ограничение по времени работы алгоритма, отсутствие значительного улучшения значения целевой функции. Могут также использоваться такие характеристики, как улучшение самого решения на шаге или на протяжении определённого числа шагов.
Один из главных недостатков алгоритма подъёма заключается в его преждевременной сходимости. Поскольку он всегда использует для получения нового решения лучшее из найденных ранее, он легко может застрять в локальном оптимуме. Из-за этого алгоритм подъёма в исходном виде представляет собой скорее алгоритм локального поиска, чем глобальной оптимизации. Существует несколько способов, позволяющих избежать данной проблемы. Они будут рассмотрены далее.
Вследствие своей вычислительной простоты алгоритм подъёма применяется особенно часто тогда, когда требуется оптимизация «на лету». Алгоритм широко применяется в задачах, связанных с сетевыми технологиями и связью, робототехникой, интеллектуальным анализом данных и поведением интеллектуальных агентов [3].
Алгоритм стохастического подъёма. Избежать проблемы преждевременной сходимости алгоритма подъёма можно, перезапуская его случайным образом при достижении определённого условия. Перезапуски помогают тщательнее исследовать пространство поиска и увеличивают вероятность нахождения глобального оптимума. Такой подход получил название алгоритма стохастического подъёма. Данный алгоритм требует хранения двух решений: лучшего из решений, полученных при текущем запуске алгоритма, и лучшего решения всех запусков. Кроме того, следует определить критерий перезапуска. Обычно перезапуск выполняют в случае, если на протяжении большого числа итераций результат существенно не улучшился.
Использование такого критерия останова локального поиска гарантирует тщательное исследование области вокруг точки перезапуска. С другой стороны, оно приводит к неопределённой длительности работы алгоритма. Если требуется гарантировать завершение работы алгоритма в заранее известное время, следует производить перезапуск после определённого числа итераций локального поиска. Можно добиться ещё лучших результатов, если при каждом перезапуске программы выбирать исходные точки не случайным образом, а по более сложному алгоритму.
Алгоритм динамического подъёма. В 1993 г. Michael de la Maza и Deniz Yuret предложили свою модификацию алгоритма подъёма, заимствующую идеи из генетических алгоритмов и методов сопряженных градиентов. Алгоритм динамического подъёма использует последние 2 посещённых решения для генерации единичных векторов в пространстве поиска. Направление поиска нового решения, таким образом, подстраивается под структуру пространства поиска. Для работы алгоритма требуется хранение набора ортогональных векторов-решений, образующих базис, а также набора противоположных по знаку первым векторов. Алгоритм включает в себя 2 цикла: внешний и внутренний. Как и в алгоритме стохастического подъёма, внутренний цикл выполняет задачу локального поиска, а внешний отвечает за исследование всей области поиска,
solution <- initSolution best <- solution
while not terminationCriterion do basis <- initBasis do
vector <- basis[vector w/ largest magnitude] if cost (solution + vector) < cost(solution)
then
solution <- solution + vector if vector = oldVector
then vector <- vector * 2 oldVector <- vector
else
vector <- vector / 2 while not basis = minBasis
if cost(solution) < cost(best) then best <- solution solution <- randomSolution
На каждой итерации из набора выбирается вектор с наибольшей длиной и вычисляется сумма исходного вектора-решения и выбранного вектора. Если значение целевой функции в этой точке больше, чем в исходной, происходит перемещение к новому решению и цикл повторяется. В противном случае длина выбранного вектора уменьшается вдвое. Кроме того, если алгоритм 2 раза подряд выбирает один и тот же вектор для перехода, длина этого вектора удваивается. Длины векторов, однако, ограничены как снизу, так и сверху — либо структурой пространства решений, либо явно заданными значениями.
Описанный алгоритм является внутренним циклом. Он напоминает метод циклического покоординатного спуска, однако может применяться и для задач с дискретным пространством поиска. Цикл повторяется до тех пор, пока алгоритм не приходит к точке локального оптимума. Такое решение алгоритм не может улучшить. Это происходит тогда, когда длины всех векторов набора являются минимально возможными. Этот признак можно использовать в качестве критерия останова внутреннего цикла.
Задача внешнего цикла - перезапускать описанную процедуру локального поиска с целью максимально тщательного исследования пространства решений. Наиболее эффективным способом выбора точки перезапуска является её расположение максимально удалённо от всех ранее пройденных алгоритмом точек. Поскольку базис ортогонален, каждая из пройденных точек вместе с базисными векторами делит пространство поиска на области — и-мерные прямоугольные параллелепипеды. Для перезапуска следует выбирать область наибольшего объёма.
Такой подход гарантирует максимально подробное исследование пространства поиска, однако становится слишком сложным для пространств с большим числом измерений: число параллелепипедов растет экспоненциально при увеличении размерности пространства. В таких случаях наиболее простым решением будет случайный выбор точки перезапуска.
Метод дождевой капли. Ещё одной модификацией метода подъёма является метод дождевой капли. Он был разработан Pete Bettinger и Jianping Zhu в 2006 г. для задачи планирования лесов . В оригинальном варианте алгоритма пространство решений и пространство значений целевой функции совпадают. Алгоритм используется в условиях поиска при жестких ограничениях для допустимых решений. На рис. 3.1 представлена укрупненная блок-схема алгоритма дождевой капли.
В качестве критерия останова алгоритм использует ограничение на число итераций без улучшения решения (рис. 3.1). Он изменяет один из компонентов решения и следит за соблюдением ограничений. Если ни одно из них не было нарушено, алгоритм переходит к следующей итерации, вновь изменяя решение. Если же новое решение не соответствует ограничениям, алгоритм пытается изменить другой компонент решения, наиболее близкий к уже изменённому, чтобы вернуть решение в рамки ограничений. Если более далёкие компоненты выходят за рамки ограничений, то процедура повторяется. В итоге каждая подобная итерация приводит к тому, что в обе стороны от измененного изначального состояния компоненты возвращаются в рамки ограничений.
Алгоритм подъёма очень прост алгоритмически и может быть реализован буквально в нескольких строках на любом высокоуровневом языке. Он практически не требует для работы памяти и хорошо подходит для оптимизации «на лету». С учётом сравнительно неплохих показателей эффективности алгоритм подъёма — это идеальный первый выбор при решении несложных задач оптимизации.
Результатом простоты алгоритма, однако, являются его очевидные недостатки, главный из которых — преждевременная сходимость. Алгоритм подъёма очень легко «застревает» в субоптимальных решениях, вследствие чего его можно рассматривать только как быстрый алгоритм локального поиска, но не как метод глобальной оптимизации. Поиск с запретами (Tabu Search), предложенный Фредом Гловером (Fred Glover) в 1986 г. [3], можно считать модификацией алгоритма подъёма, в некоторой степени свободной от этой проблемы.
Как и алгоритм подъёма, алгоритм поиска с запретами является метаэври- стическим алгоритмом Монте-Карло. Основана на использовании информации только о полученных ранее результатах, без учёта каких-либо характеристик поискового пространства и других особенностей задачи. Это уменьшает его эффективность по сравнению со специализированными алгоритмами, однако благодаря этому метод поиска с запретами может быть использован для решения достаточно широкого круга задач, так как позволяет работать с анализируемой системой как с «чёрным ящиком».
Стратегия поиска, положенная в основу рассматриваемого метода, довольно проста. Как и алгоритм подъёма, алгоритм поиска с запретами двигается по пространству решений от точки к точке. Из каждой точки он переходит в наиболее удачную из его окрестности, т. е. из множества точек, которые могут быть получены применением операции мутации к исходной.
Избежать «застревания» в локальных оптимумах удается благодаря тому, что переходы в уже посещенные точки запрещены, т. е. являются «табу». Такое ограничение гарантирует, что алгоритм не зациклится в окрестностях некоторого субоптимального решения, а продолжит исследование пространства поиска. С точки зрения искусственного интеллекта, такое поведение является естественным: отклонение от уже проверенной стратегии поведения, иногда рассматриваемое как ошибка, может привести к получению лучшего результата. Этот механизм является крайне важным - даже фундаментальным - для человека, он представляет собой не что иное, как «изобретательность» и «находчивость».
На каждом шаге работы алгоритм поиска с запретами исследует окрест- . ности текущей точки и выбирает из возможных вариантов для перехода наилучший. Однако, если выбранная точка уже посещалась и находится в списке запретов, алгоритм переходит в наиболее удачную из точек, не включенных в этот список. Перейдя к новому решению, алгоритм заносит предыдущее в список запретов. Список запретов должен хранить пройденные алгоритмом решения, чтобы избежать их повторного посещения. Однако хранить все пройденные точки, естественно, неразумно, а во многих случаях - невозможно. Проще всего решить эту проблему с помощью циклического списка: после накопления порогового числа элементов в списке при добавлении каждого нового элемента из него удаляется первый элемент. Таким образом, список всегда хранит некоторое количество последних посещённых решений.
Простейшим вариантом выбора критерия останова является использование ограничения на число итераций алгоритма. Кроме того, может быть ограничено число итераций без улучшения значения целевой функции либо оста-
новка может происходить при достижении этим значением определённого - заданного заранее - уровня. В более сложных схемах используют комбинацию всех трёх критериев.
Алгоритм поиска с запретами является метаэвристическим, поэтому область его применения крайне широка. К ней относится, в первую очередь, комбинаторная оптимизация. Кроме того, алгоритм применяется в сфере машинного обучения, сетевых технологий и телекоммуникаций, в биохимии, исследовании операций и др. В последние годы наблюдается увеличение числа публикаций, посвящённых применению алгоритма в непривычных для него сферах, например в непрерывных областях, стохастическом программировании и многокритериальной оптимизации.
С учетом алгоритмической простоты метод поиска с запретами является крайне успешным подходом. Он широко применяется для решения сложных комбинаторных проблем. Главной сложностью при его использовании является необходимость детальной информации о предметной области задачи: для применения алгоритма требуется знать характеристики поискового пространства, а также правильно выбрать способ определения окрестностей точки в нём.
Мем – единица культурного обмена, аналог гена в культуре(жест, слово, идея, любая единица культурной информации, которая может быть передана от человека к человеку путем имитации или обучения). Пример мема – форма (набор движений) в кунг фу.
Алгоритм
Он моделирует распространение мемов, вообще похож на генетический, только вместо биологической эволюции – культурная
Этапы:
1 – создание начальной популяции(стартовых особей), либо случайно, либо с помощью процедуры инициализирования .
2 – локальный поиск. Каждая особь популяции ищет локальный минимум своей окрестности
3 – взаимодействие особей. Два способа: кооперация и соревнование. Кооперация – обмен накопленной информацией, соревнование – селекция.
4 – если не достигнут критерий окончания поиска, то опять все по новой, на шаг 1. Иначе – выбор лучшего решения из популяции
Для локального поиска можно использовать имитацию отжига(вычислительно сложно), алгоритм подъема
Кооперация – аналог двухточечного скрещивания в га. Выбирается диапазон в пределах длины решения и соответствующие сегменты двух решений меняются местами . в результате две новых особи.
Критерий окончания – число итераций, оценка улучшения результата, оценка разнообразия особей(для случия вырождения популяции)
Обучение особей – основная проблема – соблюдение баланса между популяционным и локальным поиском, при большом числе особей даже простая процедура локального поиска может занять много времени
Меметические методы обычно проблемно-специфичны, они широко используют всю имеющуюся информацию о решаемой задаче.
Используются в распознавании образов, в обучении нейронных сетей, в экспертных системах и т.д.
Они типа развиваются, создаются более адаптивные (учитывают предысторию) версии алгоритма.
Входные данные алгоритма гармонии:
- целевая функция
- вероятность использования решений из памяти cr;
- вероятность выбора соседнего значения ar.
Рассмотрим псевдокод алгоритма гармонии.
1. Генерация начального состояния памяти .
2. Инициализация нового решения
3. Для каждого элемента xj’ нового решения:
3.1. Если xj’ rand(0...1)<cr, то x’j = xjrand(0..s) , иначе хj' = rand(search_area).
3.2. Если rand(0...1)<ar, то
4. Если (из памяти), то заменить на в памяти.
5. Если достигнут критерий окончания поиска, то вернуть (из памяти) иначе перейти на шаг 2.
Память представляет собой набор векторов , где - найденные решения. На каждой итерации создается одно новое решение, каждый из компонентов которого определяется следующим образом:
• с вероятностью, равной cr (вероятность использования решения из памяти), он становится равен соответствующему компоненту случайного вектора из памяти;
• с вероятностью, равной 1 - cr, он выбирается случайным образом. Далее, с вероятностью, равной ar (вероятность выбора соседнего значения), компонент изменяется на случайное значение из заданного интервала. Если получившееся решение лучше, чем худшее решение в памяти, оно его заменяет, иначе алгоритм либо переходит к следующей итерации, либо завершается при достижении критерия окончания поиска.
Выбор и настройка параметров. В оригинальном варианте алгоритма эти значения являются
фиксированными. В более поздних работах различные исследователи предлагали изменять их в ходе выполнения алгоритма, учитывая текущую ситуацию.
Модификации алгоритма.
Improved Harmony Search. В 2007 г. Мехрдад Махдави (Mehrdad Mahdavi) с коллегами опубликовали статью, в которой предложили изменять параметры алгоритма в процессе его выполнения. В частности, в их модификации вероятность выбора соседнего значения ar линейно возрастает:
где к - номер текущей итерации, К - общее число итераций.
При этом размер диапазона, в пределах которого может измениться решение, экспоненциально уменьшается:
Такая подстройка параметров позволяет контролировать скорость сходимости алгоритма. Вначале, при малом значении параметра ar и большом , алгоритм экстенсивно исследует область поиска. Это ускоряет локализацию областей, содержащих качественные решения, и не позволяет алгоритму «застрять» в субоптимальном решении. На поздних итерациях наблюдается обратная картина: большое ar и малое заставляют алгоритм интенсивно исследовать ближайшие окрестности уже найденных удачных решений.
Standard Deviation. В своем докладе для международной конференции ICDIM 2008 г. Арпан Мукопадхай (Arpan Mukhopadhyay) с соавторами провели анализ некоторых свойств алгоритма и опубликовали результаты ряда экспериментов с изменением его параметров. Авторы пришли к выводу, что оптимальным значением параметра является среднеквадратическое отклонению текущего решения. При этом вероятность использования решения из памяти cr следует устанавливать близкой к единице (конкретно - 0.99).
Оптимальность по Парето. Математические основы этого подхода были изложены Вильфредо Парето в его знаменитой книге «Cours d" Economie Politique» 1896 г. Оптимальность, или эффективность по Парето является одним из центральных понятий экономики, оно также используется в теории игр, общественных и технических науках
Значение понятия оптимальности в контексте концепции Парето основано на понятии доминирования. Говорят, что один из элементов пространства решений доминирует над другим, если он лучше хотя бы по одному критерию и как минимум не хуже по всем остальным.
Определение. Пусть дана целевая функция Тогда решение будет доминировать над решением (записывается как › ), если
Переход из доминированного решения в доминирующее называют Парето-оптималъным переходом. Оптимальность по Парето определяет область в пространстве решений, из которой такой переход невозможен. Таким образом, ни один элемент из области Парето не является доминированным никаким элементом вне её, а, значит, выход за границы этой области неизбежно приведет к ухудшению одного из целевых критериев
На рис. 1.5 показан пример границы оптимальности по Парето в задаче двухкритериальной оптимизации. Ни одно из решений, лежащих на линии, не доминировано ни одним из решений, не лежащих на ней.
Определение. Пусть элементы области допустимых решений являются n-мерными векторами и существует т критериев для их оценки. Пусть дана
целевая функция . Тогда в область Парето X*
будут входить такие элементы х* , что .
Конечный результат оптимизации должен быть выбран из области Парето человеком (экспертом) или алгоритмом на основе каких-то дополнительных критериев.
Если невозможно оценить относительную важность критериев, метод Парето является единственным способом решения многокритериальных оптимизационных задач. Тем не менее, в оригинальном виде он не лишен недостатков. Область Парето зачастую содержит недоминируемые, но абсолютно бесполезные решения. Существуют разные способы обойти этот недостаток. В большинстве случаев используют установку и строгий контроль ограничений.
Интерактивность (от англ. interaction — «взаимодействие») — понятие, которое раскрывает характер и степень взаимодействия между объектами. Используется в областях: теория информации, информатика и программирование, системы телекоммуникаций, социология, промышленный дизайн и других.
В настоящее время среди специалистов перечисленных областей отсутствует конкретное устоявшееся определение значения этого термина. Тем не менее этот термин, обобщенно, можно определить так:
Интерактивность — это принцип организации системы, при котором цель достигается информационным обменом элементов этой системы.
Элементами интерактивности являются все элементы взаимодействующей системы, при помощи которых происходит взаимодействие с другой системой/человеком (пользователем).
Если говорить в контексте использования интерактивного подхода к решению оптимизационных задач, то можно сказать, что любые дополнительные данные от пользователя программы которые помогут ускорить решение задачи - это и есть интерактивность.
Определение. Задачей многокритериальной оптимизации называется задача о нахождении лучшего из элементов x^* из области поиска X в соответствии с заданным набором критериев F={f_1, f_2,…, f_n}. Критерии f_i – это целевые функции, определение которых дано ранее.
При решении задач многокритериальной оптимизации неизбежно возникновение конфликта критериев: при попытках улучшить показатель текущего решения по одному из них показатели по другим зачастую ухудшаются. Существуют 2 основных подхода к решению задачи многокритериальной оптимизации. Первый заключается в сведении её к задаче однокритериальной оптимизации путем свёртки набора критериев. Второй состоит в поиске решений, которые гарантированно лучше остальных, и предоставлении права окончательного выбора эксперту.
Задачи многокритериальной оптимизации возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость и надежность). Требуется найти точку области допустимых решений, которая минимизирует или максимизирует все такие критерии. Если в подобного рода задачах речь идет не о разнородных критериях некоторой системы, а о сопоставлении однородных критериев разных ее подсистем (например, отрасли, группы населения и т.п.), то эти задачи называются задачами векторной оптимизации.
Некоторые частные критерии могут противоречить друг другу, другие действуют в одном направлении, третьи безразличны друг к другу. Поэтому процесс решения многокритериальных задач неизбежно связан с экспертными оценками как самих критериев, так и взаимоотношений между ними. Известен ряд методов решения задач многокритериальной оптимизации:
Критерий оптимальности итальянского экономиста В. Парето применяется при решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались.
Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности (т.е. улучшить хотя бы один из них, не ухудшая остальных), принято называть областью Парето, или областью компромиссов, а принадлежащие ей решения — эффективными, или оптимальными по Парето.
В общем случае эффективные решения не эквивалентны друг другу, так что про два оптимальных по Парето решения нельзя сказать, какое из них лучше. Поэтому при решении многокритериальных задач необходимо дополнительное изучение эффективных решений. Для этого можно было бы сформулировать некоторый критерий и оптимизировать его на множестве эффективных решений. Обычный подход заключается в стремлении «свернуть» частные критерии в один обобщенный скалярный критерий, оптимизация которого приводит к оптимальному решению задачи в целом. Формулировка подходящего обобщенного критерия в зависимости от конкретных условий как раз и является основным вопросом, который изучается в многокритериальной оптимизации.