Биоинспирированные методы в оптимизации

Муравьиные методы и алгоритмы

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

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

Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива – колонии. Основу «социального» поведения муравьев составляет самоорганизация – множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. При этом исключается любое централизованное управление и обращение к глобальному образу, репрезентирующему систему во внешнем мире. Самоорганизация является результатом взаимодействия следующих четырех компонентов: случайность; многократность; положительная обратная связь; отрицательная обратная связь.

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

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

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

Важным свойством муравьиных алгоритмов является неконвергентность: даже после большого числа итераций одновременно исследуется множество вариантов решения, вследствие чего, не происходит длительных временных задержек в локальных экстремумах. Перспективными путями улучшения муравьиных алгоритмов являются on-line адаптация параметров с помощью базы нечетких правил, а также их гибридизация с другими методами природных вычислений, например генетическими алгоритмами. Гибридизация может осуществляться по островной схеме, когда различные алгоритмы решают задачу параллельно и автономно, или по принципу «мастер-подмастерье», когда основной алгоритм − «мастер» передает решение типовых подзадач «подмастерью».

Пчелиные методы и алгоритмы

Пчелиный алгоритм − это оптимизационный алгоритм, в основе которого лежит поведение пчёл в живой природе.

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

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

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

В обычной колонии пчел, например Apis mellifera (медоносная пчела домашняя), предполагается, что пчелы со временем выполняют разные роли. В типичном улье может быть от 5000 до 20 000 особей. Взрослые особи (в возрасте от 20 до 40 дней), как правило, становятся фуражирами. Фуражиры обычно выполняют одну из трех ролей: активные фуражиры, фуражиры-разведчики и неактивные фуражиры.

Активные фуражиры летят к источнику нектара, обследуют соседние источники, собирают нектар и возвращаются в улей.

Разведчики обследуют местность вокруг улья (площадью до 130 км²) в поисках новых источников нектара. Примерно 10% пчел-фуражиров в улье задействованы в качестве разведчиков.

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

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

Работа пчелиного алгоритма зависит от следующих основных параметров: общего числа пчёл-разведчиков (N); общего числа участков (m); числа элитных участков (е); числа пчёл-разведчиков на элитных участках (n); числа пчёл (l) на остальных (m− е) участках; начального размера участков, т.е. размера участков вместе с их окрестностями (S); максимального числа итераций (I).

Основная идея пчелиного алгоритма заключается в том, что все пчёлы на каждом шаге будут выбирать как элитные участки для исследования, так и участки в окрестности элитных, что позволит, во-первых, разнообразить популяцию решений на последующих итерациях, во-вторых, увеличить вероятность обнаружения, близких к оптимальным решения. После чего в окрестности остальных участков (m− е), в зависимости от значения их целевой функции, отправляются рабочие пчёлы (l = N− n).

Приведём словесное описание алгоритма пчёл. Сначала создается популяция пчёл и производится оценка значений их целевых функций, затем выбор участков для поиска в их окрестностях и отправка пчёл-разведчиков, далее производится выбор пчёл с лучшими значениями целевой функции с каждого участка и отправка рабочих пчёл, осуществляющих случайный поиск с оценкой их целевой функции. Затем формируется новая популяция и производится проверка условия окончания работы алгоритма. Таким образом, ключевой операцией алгоритма пчёл является совместное исследование перспективных областей и их окрестностей. В конце работы алгоритма популяция решений будет состоять из двух частей: пчёлы с лучшими значениями целевой функции элитных участков, а также группы рабочих пчёл со случайными значениями функции. Отличительной особенностью алгоритма является способность динамически разбивать поисковое пространство на области, что уменьшает время работы алгоритма. Данный алгоритм иллюстрирует стратегию поиска «Разделяй и властвуй». Главным преимуществом является тот факт, что резко снижается вероятность попадания в локальный оптимум, а за счет распараллеливания уменьшается время.

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

Заключение

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

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

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

При написании пособия авторами ставилась цель рассмотреть модели, методы и алгоритмы конструкторского этапа проектирования, которые используются в САПР ЭВМ.

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

Так, и с алгоритмами: нельзя придумать ни одного стоящего алгоритма, если ты, не знаешь ни одного эффективного алгоритма.

Надеемся, что данное пособие стимулирует обучаемых на разработку эффективных алгоритмов конструкторского этапа проектирования ЭВМ и, в частности, задач теории графов.

Список литературы

1. Абрайтис, Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем / Л.Б. Абрайтис. - М.: Радио и связь, 1985. – 198 с.2. Алексеев, О.В. Автоматизация проектирования радиоэлектронных средств: учеб. пособие для студентов радиотехнических специальностей вузов / О.В. Алексеев. – М.: Высшая школа, 2000. – 430 с.

3. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие.– 2-е изд.–М.: Физматлит, 2006. –320 с.

4. Гладков Л.А, Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010. – 366 с

5. Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. – М.: Физматлит, 2009. –384 с.

6. Гладков Л. А., Курейчик В. В, Курейчик В. М. Дискретная математика. Учебник/ Таганрог: Изд-во ТТИ ЮФУ, 2011. –312 с.

7. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. / Изд.2, испр. М.: УРСС, 2009. –392 с.

8. Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004. – 664 с. - ISBN: 5-9502-0057-8

9. Иванова Н.Ю., Петров А.С., Поляков В.И., Романова Е.Б. Технология проектирования печатных плат в САПР P-CAD-2006 / СПб: СПбГУ ИТМО, 2009 – 168 с.

10. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. – 3-е изд. – М.: «Вильямс», 2013. –1324 с.11. Корячко, В.П. Теоретические основы САПР / В.П. Корячко, В.М. Курейчик, И.П. Норенков. – М.: Энергоиздат, 1987. – 400 с.12. Кристофидес Н, Теория графов: Алгоритмический подход: пер. с англ. / Н. Кристофидес. – М.: Мир, 1978. – 432 с. 13. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств - М.: Наука, 1974. –304 с.14. Муромцев, Д. Ю. Математическое обеспечение САПР: учебное пособие / Д. Ю. Муромцев, И. В. Тюрин. – 2-е изд., перераб. и доп. – СПб.: Лань, 2014. – 464 с.15. Муромцев, Ю.Л. Задачи компоновки радиоэлектронной аппаратуры: лабораторные работы / Ю.Л. Муромцев, В.Н. Грошев, В.В. Трейгер. – Тамбов: ТИХМ, 1987. – 36 с.16. Муромцев, Ю.Л. Задачи размещения радиоэлектронной аппаратуры: лабораторные работы / Ю.Л. Муромцев, В.В. Трейгер, В.Н. Грошев. – Тамбов: ТИХМ, 1988. – 32 с.17. Муромцев, Ю.Л. Задачи трассировки печатных плат: лабораторные работы / Ю.Л. Муромцев, В.В. Трейгер, В.Н. Грошев. – Тамбов: ТИХМ, 1990. – 32 с.18. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3- е изд. — СПб.: Питер, 2009. – 384 с.19. Норенков, И.П. Основы автоматизированного проектирования: учебник для вузов / И.П. Норенков. – – 3-е изд., перераб. и доп. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. – 448 с. 20. Петухов, Г.А. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом / Г.А. Петухов, Г.Г. Смолич, Б.И. Юлин. – М.: Радио и связь, 1987. – 152 с.21. Разевиг, В.Д. Применение программ PCAD и Pspice для схемотехнического моделирования на ПЭВМ / В.Д. Разевиг. – М.: Радио и связь, 1992. – Вып. 4. 71 с.

22. Селютин, В. А. Машинное конструирование электронных устройств / В. А. Селютин. – М.: Советское радио, 1977. – 384 с.

23. Советов, Б.Я. Информационные технологии: учебник для вузов / Б.Я. Советов. – М.: Высшая школа, 2003. – 352 с.24. Харари Ф. Теория графов (3-е издание). М.: КомКнига, УРСС, 2006. – 259 с.

25. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. – 400 с.

Приложение

⇐ Предыдущая 10 11 12 13 14 15 16 171819 Следующая ⇒