Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» (СПбГЭТУ)

Факультет компьютерных технологий и информатики

Кафедра систем автоматизированного проектирования

РЕФЕРАТ

НА ТЕМУ: «Алгоритмы интеллектуальных систем»

по учебной дисциплине «Интеллектуальные системы»

Выполнил: Торопов Д.А.

Группа: 8302

Проверила:

Новакова Н.Е.

Санкт-Петербург. 2012г.

1. Меметический алгоритм

Теория эволюции всегда интересовала широкую публику больше, чем какая-либо другая сфера биологии. Однако даже с учетом этого успех изданной в 1976 г. книги британского этолога Ричарда Докинза (Richard Dawkins) «Эгоистичный ген» можно назвать поистине феноменальным. Ни один труд об эволюции со времен «Происхождения видов» Дарвина не продавался таким тиражом, не был переведен на столько я лаков и не вызывал таких споров.

В своем труде убежденный дарвинист Докинз изложил геноцентрический взгляд на эволюцию. Стремление генов к «эгоистичной» репликации определяет развитие популяций, сходящихся к эволюционно стабильным стратегиям. Любой самый сложный эволюционный процесс особей и видов может рассматриваться как совокупность эволюции их генов. Естественный отбор на уровне отдельных организмов и групп почти никогда не одерживает верх над отбором на уровне генов.

Более того, для пользы дела гены могут даже вредить организму-хозяину. Например, теория объясняет такой феномен, как альтруизм. Поведение живого существа, при котором оно жертвует собственными интересами во благо других, проигрышно с точки зрения выживания. Однако с точки зрения геноцентризма, помощь существу с такими же генами приводит к увеличению числа копий этих генов - а это и есть их главная цель.

Мемы. Одной из революционных идей, высказанных в книге, является схожесть эволюции генов и эволюции человеческой культуры. Докинз назвал единицу культурного обмена, т. е. аналог гена в культуре, мемом. Мемом можно назвать жест, слово или идею; любая единица культурной информации, которая может быть передана от человека к человеку путём имитации или обучения - это мем.

Сторонники меметики считают, что мемы ведут себя лак же, как и гены. Мемы передаются между поколениями, мутируют и проходят отбор. Как и гены, меты стремятся к саморепликации. Неудачные мемы постепенно исчезают, удачные надолго закрепляются в хозяевах, разносторонне влияя на их поведение.

Пабло Москато (Pablo Moscato), о котором будет сказано далее, пользовался аналогией с китайскими боевыми искусствами. Наборы движений кунг-фу, называемые формами, передаются от учителей к ученикам, от поколений к поколениям. За время существования они были доведены до совершенства, и лишь лучшие мастера могут вносить в них изменения. В этом смысле, формы являются прекрасным примером мемов.

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

Меметические алгоритмы. Идеи, высказанные Докинзом, вдохновили австралийского исследователя Пабло Москато на создание алгоритма оптимизации, моделирующего распространение мемов. В то время как генетические алгоритмы имитируют процесс биологической эволюции, разработанный Москато подход использует аналогию с эволюцией мемов, т. е. культурной эволюцией.

В общих чертах меметический алгоритм состоит из следующих этапов:

Шаг 1. Создание начальной популяции. Особи в популяции могут быть сгенерированы случайным образом, либо при помощи специальной процедуры инициализации.

Шаг 2. Локальный поиск. Каждая из особей в популяции осуществляет поиск локального оптимума в своей окрестности.

Шаг З. Взаимодействие особей. Особи могут взаимодействовать двумя способами: путём кооперации или соревнования. Кооперация предполагает обмен накопленной информацией, соревнование - селекцию.

Шаг 4. Если не достигнут критерий окончания поиска, переход на шаг 1, иначе выбор лучшего решения из популяции.

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

Компоненты алгоритма:

Локальный поиск. Для осуществления локального поиска Москато использовал алгоритм имитации отжига. В более поздних работах предлагались менее сложные в вычислительном отношении алгоритмы, такие, как алгоритм подъёма. Оптимальным же является применение детерминированных алгоритмов, использующих информацию о структуре области поиска.

Кооперация. Для обмена информацией между особями может служить процедура, аналогичная применению оператора двухточечного скрещивания в генетических алгоритмах. Технически, при этом выбирается некоторый диапазон в пределах длины решения, и соответствующие сегменты двух решений меняются местами. В результате получаются две новые особи, к которым впоследствии применяется процедура локальной оптимизации.

Соревнование. Процедура селекции в целом аналогична таковой в генетических алгоритмах и обычно заключается в отборе наиболее приспособленных особей и популяции и исключении из неё менее приспособленных.

Критерий окончания поиска. Наряду с подсчётом числа итераций и оценкой улучшения результата определение целесообразности окончания поиска в меметических алгоритмах может включать оценку разнообразия особей. Обычно в случае вырождения популяции бессмысленно продолжать поиск.

Меметическим называют довольно широкий класс алгоритмов, объединённых общей идеей: включением в генетический алгоритм индивидуального обучения особей и использованием информации о структуре пространства возможных решений.

Обучение особей. Одной из главных трудностей, возникающих при проектировании алгоритма, сочетающего популяционный и локальный поиск, является соблюдение баланса между ними. Можно говорить о ней как о более общей проблеме соблюдения баланса между экстенсивным и интенсивным исследованиями пространства поиска. Кроме того, следует учитывать тот факт, что при большом числе особей даже простая процедура локального поиска может занять непозволительно много времени. Разные исследователи по-разному оценивали важность локального поиска, и объём времени, который ему нужно уделять. В целом, не существует универсальных рекомендаций на этот счет.

Использование информации об области поиска. В отличие от большинства эволюционных методов меметические алгоритмы обычно проблемно-специфичны. Они широко используют всю имеющуюся информацию о решаемой задаче. Это несколько усложняет их проектирование, однако значительно улучшает показываемые ими результаты.

Известно множество примеров применения меметических алгоритмов для решения NP-полных задач, в задачах распознавания образов и обучения нейронных сетей, и экспертных системах, при проектировании электронных устройств, в задачах составления расписаний и многих других областях. Зачастую они показывали значительно лучший результат, чем традиционные генетические и другие метаэвристические алгоритмы.

Меметические алгоритмы - одна из наиболее активно развивающихся областей эволюционных вычислений и методов оптимизации в целом. Подход предполагает большую степень свободы в добавлении нововведений, чем пользуются различные исследователи, создавая всё новые его модификации. На данный момент наиболее перспективным следует считать создание адаптивных версий алгоритма, учитывающих предысторию поиска и негативную информацию о6 области поиска, т. е. решения плохого качества.

2. Жадный алгоритм

алгоритм оптимизация программирование

Жадный алгоритм (англ. Greedy algorithm) -- алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование. [3]

УСЛОВИЯ ПРИМЕНИМОСТИ

Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами, характерны две особенности: во-первых, к ним применим “Принцип жадного выбора”, а во-вторых, они обладают свойством “Оптимальности для подзадач”.

Алгоритмы, которые предназначены для задач оптимизации, обычно представляют собой методичность шагов, на каждом из которых предоставляется некое количество выборов. В жадном алгоритме всегда делается выбор, который кажется самым лучшим в данный момент -- т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. Мы рассмотрим задачи оптимизации, пригодные для решения с помощью жадных алгоритмов.

Не всегда жадные алгоритмы приводят к оптимальному решению, но во многих задачах они дают нужный результат. Чтобы рассмотреть жадный алгоритм, сначала будет рассмотрено решение, основанно на динамическом программировании, после чего будет показано, что оптимальное решение можно получить, исходя из принципов жадных алгоритмов. Жадный метод подходит для довольно широкого класса задач. Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода. [3],[2]

СВОЙСТВО ЖАДНОГО ВЫБОРА

Первый из названных выше основных составляющих жадного алгоритма - свойство жадного выбора: глобальное оптимальное решение можно получить, делая локальный оптимальный (жадный) выбор. Другими словами, рассуждая по поводу того, какой выбор следует сделать, мы делаем выбор, который кажется самым лучшим в текущей задаче; результаты возникающих подзадач при этом не рассматриваются.

Рассмотрим отличие жадных алгоритмов от динамического программирования. В динамическом программировании на каждом этапе делается выбор, однако обычно этот выбор зависит от решений подзадач. Следовательно, методом динамического программирования задачи обычно решаются в восходящем направлении, т.е. сначала обрабатываются более простые подзадачи, а затем -- более сложные. В жадном алгоритме делается выбор, который выглядит в данный момент наилучшим, после чего решается подзадача, возникающая в результате этого выбора. Выбор, сделанный в жадном алгоритме, может зависеть от сделанных ранее выборов, но он не может зависеть от каких бы то ни было выборов или решений последующих подзадач. Таким образом, в отличие от динамического программирования, где подзадачи решаются в восходящем порядке, жадная стратегия обычно разворачивается в нисходящем порядке, когда жадный выбор делается один за другим, в результате чего каждый экземпляр текущей задачи сводится к более простому. Конечно же, необходимо доказать, что жадный выбор на каждом этапе приводит к глобальному оптимальному решению, и здесь потребуются определенные интеллектуальные усилия. Обычно, в таком доказательстве исследуется глобальное оптимальное решение некоторой подзадачи. Затем демонстрируется, что решение можно преобразовать так, чтобы в нем использовался жадный выбор, в результате чего получится аналогичная, но более простая подзадача. Свойство жадного выбора часто дает определенное преимущество, позволяющее повысить эффективность выбора в подзадаче. Например, в задаче о выборе заявок, предварительная сортировка заявок в порядке возрастания времени окончания, позволяет рассмотреть заявку всего один раз. Зачастую оказывается, что благодаря предварительной обработке входных данных или применению подходящей структуры данных (нередко это очередь с приоритетами) можно ускорить процесс жадного выбора, что приведет к повышению эффективности алгоритма.

3. Пчелиный алгоритм

Данный алгоритм моделирует поведение пчел в естественной среде. Идея пчелиного алгоритма заключается в том, что все пчелы на каждом шаге будут выбирать как элитные участки для исследования, так и участки в окрестности элитных, что позволит, во-первых, разнообразить популяцию решении? на последующих итерациях, во-вторых, увеличить вероятность обнаружения близких к оптимальным решении? [5]. Приведем основные понятия пчелиного алгоритма:

1. Источник нектара (цветок, участок).

2. Фуражиры (рабочие пчелы).

3. Пчелы-разведчики. Источник нектара характеризуется значимостью, определяемой различными параметрами. Фуражиры закреплены за источниками нектара. Количество всех пчел в этих участках больше, чем на остальных. Среднее количество разведчиков в рое составляет 5 - 10%. Вернувшись в улей, пчелы обмениваются информацией посредством танцев на так называемой закрытой площадке для танцев.

Пусть решение представляет собой, как и в ГА, вектор H. Областью поиска нектара для пчел будет являться пространство поиска решении?, размерностью n! (количество всех возможных перестановок вектора H). Расположение источника нектара характеризуется конкретной перестановкой H, решением. Таким образом, координатами источника является решение H. Количество нектара на источнике обратно пропорционально ЦФ. Участок имеет размеры, где размер - количество решении?, «близких» к H. Близость между векторами определяется значением расстояния Хемминга между ними. К примеру, решения {5,2,7,3,4,1,6} и {5,4,7,3,2,1,6} являются «близкими», т.е. в пространстве поиска они располагаются рядом, находятся на одном «участке».

Приведем словесное описание алгоритма пчел.

1. Генерация участков для поиска нектара.

2. Оценка полезности участков.

3. Выбор участков для поиска в их окрестности.

4. Отправка фуражиров.

5. Поиск в окрестностях источников нектара.

6. Отправка пчел-разведчиков.

7. Случайный поиск.

8. Оценка полезности новых участков.

9. Если условие останова не выполняется, то п. 2. 10. Конец работы алгоритма. Таким образом, ключевой операцией алгоритма пчел является совместное исследование перспективных областей и их окрестностей. В конце работы алгоритма популяция решении? будет состоять из двух частей: пчелы с лучшими значениями ЦФ элитных участков, а также группы рабочих пчел со случайными значениями ЦФ. Зависимость временной сложности пчелиного алгоритма от числа вершин - O(n2).

4. Классический генетический алгоритм

Генетический алгоритм был предложен Джоном Холландом в 1975 году в работе [5] и является первым из эволюционных алгоритмов. Особи в генетическом алгоритме представляются в виде строк фиксированной длины (обычно используются битовые строки). Рассмотрим работу генетического алгоритма более детально.

* Инициализация. Создается случайная начальная популяция. Способ создания случайной строки может быть специфичным для задачи, однако обычно применяется случайная генерация строк с равномерным распределением над каждым символом строки.

* Отбор. Существует несколько стратегии? при выборе особеи? для проведения генетических операторов и при формировании нового поколения. При отбор по рулетке вероятность выбора особи i ? P t прямо пропорциональна значению f tћiџ . При пропорциональном отборе находят значение f '=?f tћiџ/#Pt# . Затем для каждой особи i?Pt вычисляется отношение ftћiџ/f ' , которое показывает сколько раз должна быть отобрана данная особь. Также в число часто используемых методов отбора входят турнирный отбор, отбор усечением и т. д.

* Кроссовер. На строках фиксированной длины скрещивание реализуют следующим образом: часть символов копируется из одной строки, остальные символы копируются из другой строки. Будем говорить, что результатом кроссовера двух строк {a1...an} и {b1...bn} с маской {m1 ...mn}, где mi?{0,1}, является строка {c1 ...cn}, для которой ci={ai , mi=0; bi, mi=1.

Таким образом, методы кроссовера отличаются методом создания маски. Наиболее распространены методы одноточечного кроссовера, двухточечного кроссовера и однородного кроссовера. Более сложные операторы кроссовера можно рассмотреть на примере скрещивания строк вещественных чисел -- это «Flat crossover» [7], ``Simple crossover'' [8],[9], ``Arithmetical crossover'' [9], ``BLX- · crossover" [10], ``Linear crossover'' [8], ``Discrete crossover'' [11], ``Extended line crossover'' [11] и пр.

* Мутация. Наиболее распространен следующии? метод мутации -- выбирается случайная позиция в строке и символ в этой позиции заменяется на случайный.

5. Алгоритм культурного обмена

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

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

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

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

Алгоритм уменьшает необходимость для незрелых людей тратить энергию в обход проб и ошибок итераций, как правило, требуется получить информацию об окружающей среде. Он позволяет передачу больше информации, чем любые недостатки индивидуального генома мая реально содержит коммуникационный протокол алгоритма и культуры населения, дает общие черты культурной информации может передаваться быстрее, чем генетические материалы. Стабильность - культура способна упорно за жизнь одного человека протоколов.

Культурные связи протокола взаимодействия между населением и убеждений пространстве культурного алгоритма - лучших людей из населения может обновить веру пространства алгоритмов. Связанные с помощью функции обновления техники знания категорий убеждений пространстве может повлиять на население путем изменения генома или действия отдельных лиц Преимущества и недостатки протокола и алгоритма общие черты

С эволюционной точки зрения культурного алгоритма в микроэволюционной перспективе - передаче поведение между индивидуумами в области народонаселения и с макроэволюционной точки зрения (формирование обобщенных Преимущества и убеждений на основе индивидуального опыта) Недостатки коммуникации каждый человек может быть описан: алгоритм набора признаков. Общие черты лица опыта прошлого и прогнозы относительно будущего коммуникационные протоколы или обобщенного описания своего опыта вложение.

Основные культурные алгоритма инициализировать народонаселения космической POP (т), а также справочную и инициализировать убеждений космической BLF и повторяется до тех пор, пока прекращение состояния достигнуто. Преимущества и недостатки выполнять действия отдельных лиц в POP (т); протокола и связи оценки каждого отдельного используя функции; Алгоритм выбирает лучших людей стать родителями; Общие черты создать новое поколение потомков путем мутации и кроссовер; Другие лучшие люди могут обновить BLF (т) - признание функции.

Двойного наследования (по крайней населения и уровня знаний) соответствующие знания по методам руководства эволюции населения англ. Поддерживает иерархическую структуру населения и убеждений. Преимущества и области знаний, отделяется от лиц Недостатки Сообщение поддерживает себя адаптации на различных уровнях протокола и алгоритма эволюции может происходить с разной скоростью на разных уровнях общие черты (В алгоритме развивается 10 раз быстрее, чем биологические коммуникационные протоколы поддерживает гибридные подходы к решению проблем вложении Другие методы вычислительной в рамках которой многие все будущие направления различных моделей культурные изменения могут быть выражены.

Алгоритм может поддержать возникновение иерархических структур в обоих алгоритмов. Похожие убеждений и населения методам нахождения количество доменных знаний (например, сдерживается смежным методам оптимизации проблем сложных систем, в которых адаптация может происходить на различных уровнях Справочная информация и на различных курсов в области народонаселения и убеждений пространстве и знания в различных формах и должна быть мотивированным минусы, по-разному коммуникационный протокол и гибридных систем, которые требуется сочетание Алгоритм поиска и базы знаний, основанные общие черты Подходит Проблемы проблема требует решения многочисленных групп населения и многочисленных коммуникационных пространств убеждений и их взаимодействие протоколов вложении Другие иерархически структурированной среде, где проблема Методы иерархическую структуру населения и знание элементов

Признание Функция культуры Алгоритм - все люди используются для обновления ограничений знаний культурных алгоритмов. Похожие рейтинг 20% (видный человек) являются использование используются методы обновления от нормативного знания использовать помехи для корректировки правил активных клеток. Недостатки Сообщение осуществимо протокола и невозможно Алгоритм полу-возможные общие черты Подходит Проблемы адаптации иерархическая структура, основанная на вышеупомянутое сообщение Протоколы сплит полу-возможно клеток на более мелкие ячейки, когда число вложении Другие лица становится слишком высокой Будущие направления слиянии невозможно детей в первоначальном родителей;

Похожие методы руководства миграции людей из менее продуктивными клеток , чтобы те, которые являются более продуктивными-это возможно и практически осуществимо клеток с видными Преимущества и недостатки отдельных лиц и коммуникационный протокол свидетельствует миграция из обычной клетки для выдающихся Алгоритм клеток общие черты как мало видных клеток коммуникационные протоколы перемещения лиц в невозможно клетки для них осуществимо вложении перехода от обычных людей на видных клеток

Население культурных моделей, используемых алгоритмов - генетических алгоритмов. Похожие методы англ. Недостатки Сообщение Эволюция стратегий (Робот играет в футбол) и Протокол Алгоритм Memetic моделей (Развитие сельского хозяйства ) Общие черты агент на основе моделирования (Эволюция состояния окружающей среды Подходит Проблемы коммуникации воздействия)

Вариации культуры Алгоритм - генетических алгоритмов. Похожие методы англ. и космической руководствуясь генетические алгоритмы (VGA)

Микро-эволюционный процесс моделируетсяс использованием генетических алгоритмов.Недостатки протокола и убеждений пространство представляет схемы и обобщения отдельных хромосом, основанных на их поведении. Подходят будущие направления культуры Алгоритм - генетических алгоритмов. Похожие методы нескольких представлениях и народонаселения Преимущества и недостатки убеждений космической эволюции протокола Проектирование и культурных систем Алгоритм общие черты и структуры и решении проблем окружающей среды.

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

Размещено на Allbest.ru