V Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
«Алгоритмы роя частиц»
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
Технологии развиваются с умопомрачительной скоростью. Абсолютно во все сферы деятельности проникает электроника, даже в те, где ее присутствие раньше нельзя было представить. Технологии упрощают нашу жизнь и позволяют подняться на те высоты, мысли о которых еще недавно были уделом фантастов. Но всем нужно управлять, ведь как сказал Пабло Пикассо: «Компьютеры глупы. Все, что они могут, – это давать ответы». А управлять компьютером может только человек, посредством написанной им же программы. Как всем нам известно, компьютер может выдавать только что-то точное, без малейшего отклонения от заданного алгоритма. Но как же можно в компьютер внести некоторую долю вероятности? С помощью специального алгоритма генерации псевдослучайных чисел, который может помочь в решении задач, на которые трудно дать точный ответ. Возможности его применения и разные направления использования я и рассмотрю в своей работе.
- Модуль «Random»
Даже человек не очень хорошо знающий английский может догадаться, что в модуле, имеющем название «Random» будет вестись работа с некоторыми случайными единицами, ну или же словами которые будут выставлены в случайном порядке. Но прежде чем перейти непосредственно к модулю, нужно понять, что это такое.
Наверное, все мы знаем, что модули это некие части чего-либо, при помощи которых можно собрать готовое изделие. В программировании это примерно то же самое. Модуль в программировании это своего рода алгоритм позволяющий выполнять базовую задачу. Обычно, в таких новых языках как «Python» библиотеки (тот же модуль) берутся из других, более ранних, языков программирования, таких как «Pascal», ну или языков семейства «С». Это нужно для того, чтобы программисты по многу раз не писали одни и те же ко̀ды по многу раз. Для этого и были созданы стандартные наборы функций, в основном математических, которые проверены и испытаны по многу раз.
Одной из таких функций и является модуль «Random». Он работает на основе алгоритма генерации псевдослучайных чисел. Почему же не по настоящему случайных, спросите вы. Все дело в том, что создать реальную случайность на данный момент не возможно, источниками настоящей случайности являются такие вещи как физические шумы, дробовой шум в резисторе или космическое излучение. В различных генераторах используются специальные алгоритмы. А поскольку алгоритм это вещь предопределенная, генерацию называют псевдослучайной.
Очень хорошим примером генератора случайных чисел является «Генератор Макларена-Марсальи», он работает при помощи двух массивов псевдослучайных чисел и матрицы, которая случайно заполняется из этих 2Xмассивов. При помощи этого метода удается немного приблизиться к настоящей случайности.
Практические возможности использования генератора
Самый явный способ использования генератора случайных чисел – это примерное нахождение числа π. способ приближенного подсчета числа p заключается в бросании стрелок в мишень, представляющую собой квадрат, в который вписан круг (рисунок 1).
Рисунок 1 – Подготовка к исследованию
Мы выбираем точки в квадрате случайным образом и подсчитываем, какая их часть попала в круг. Если радиус круга равен r, то его площадь равна pr2, а площадь квадрата равна(2r)2 =4r2. Отношение площади круга к площади квадрата равно p/4. Если мы выбираем точки в квадрате действительно случайно, то стрелки распределятся по квадрату более или менее равномерно (рисунок 2, 3). Для случайного бросания стрелок в мишень число p приблизительно равно 4 * c/s, где с – число стрелок, попавших в круг, a s – общее число брошенных стрелок. Чем больше стрелок брошено, тем более точное приближение к числу p мы получаем.
Рисунок 2 – 20 точек мишени
Рисунок 3 – 1000 точек мишени
С помощью этой техники можно подсчитать площадь произвольной неправильной фигуры, для которой мы умеем проверять, принадлежит ли ей заданная точка (х,у). Для этого мы просто генерируем случайные точки в объемлющем фигуру квадрате и подсчитываем отношение числа тех из них, которые попали внутрь фигуры, к общему числу сгенерированных точек. Отношение число стрелок, попавших внутрь фигуры, и общее число брошенных стрелок совпадает с отношением площадь фигуры площадь квадрата.
Для чего можно использовать генератор в повседневной жизни
Исследования показывают, что около 40 % всех пользователей выбирают пароли, которые легко угадать автоматически. Легко угадываемые пароли (123, admin) считаются слабыми и уязвимыми. Пароли, которые очень трудно или невозможно угадать, считаются более стойкими. Как раз такие пароли и можно создать при помощи генератора. Пароль, созданный таким образом будет считаться надежным, поскольку его будет невозможно угадать, только подобрать.
Так же, данный метод может помочь в предсказании примерных результатов соц. опросов, в которых нет однозначного ответа на вопрос.
- Алгоритмы роя частиц
Сам роевой интеллект – это, прежде всего, саморегулирующаяся независимая система, состоящая из множества частей, никак не связанных друг с другом. Если проще, это система, состоящая из множества объектов, которые каждый по своему пути приходит к единственно правильному решению какой-то задачи. Так, точка максимального скопления так называемых агентов является ответом на поставленную цель. Изначально этот метод использовался для предсказания социального поведения, ведь один человек точно так же ищет правильный путь к решению задачи, как и единственно взятый «агент». Так же данный принцип позаимствован у природы, а, значит, проверен миллионами лет эволюции. Для примера можно взять представителя царства насекомых, такого как обыкновенная муха. Ведь мухи не собираются в стаи, у них нет своего «командования», но при этом в том месте, где есть что-то полезное для них, находится большое количество особей. Это является самым явным примером роевого интеллекта в природе. Теперь возьмем единственного агента «роя», так называемого биода. Каждый биод следует простому набору команд, заранее заведенному в алгоритм. Таким образом, они не управляются чем-то одним, но набор случайных взаимодействий приводит к определенному роду сознанию, которое и называется разумом роя.
Есть несколько основных типов алгоритмов, рассмотрим их.
Метод роя частиц
Метод, предназначенный для численной оптимизации. Первая версия алгоритма была представлена Марко Дориго, а был доказан Кеннеди, Эберхартом и Шии, а создан для имитации социального поведения. Каждый бион перемещается в пространстве согласно простой формуле в поисках наилучшего положения удовлетворяющей условию. Пример – это программа для поиска глобального минимума функции (рисунок 4).
Рисунок 4 – Программа для поиска глобального минимума функции
Муравьиный алгоритм
Создан для нахождения решений задачи коммивояжёра, а так же аналогичных задач на поиск оптимального маршрута на графах. В основе лежит поведения муравьиной колонии в моменты поиска еды. Так, они ищут более оптимальный маршрут до еды, и обратно. Этот принцип и заложен в основу алгоритма. Принцип его работы показан на рисунке 5.
Рисунок 5 – Принцип работы муравьиного алгоритма
Пчелиный алгоритм
Был составлен Д. Карабога в 2005 году. За основу он взял стратегию пчел по поиску нектара. Где сначала на местность вылетают пчелы разведчики, и выбирают наиболее удачные районы. Потом в наиболее удачные районы вылетают пчелы рабочие и собирают непосредственно нектар. То есть алгоритм основан на выборе наиболее оптимальных точек и обработке их. Работает он по следующему принципу. На рисунке 6 толстые линии – это траектории полета «разведчиков», а окружности – это области исследования «рабочих».
Рисунок 6 – Пчелиный алгоритм
Практические возможности применения
Метод роя частиц: одна из возможностей его применения была, как это было ранее указано, раскрыта в эссе Станислава Лема. В нем была очень хорошо раскрыта тема использования роя дронов, управляемых этим самым роевым интеллектом в военных целям. Во времена написания это фантастического размышления Лем и не мог предположить, что в 21 веке дроны будут так хорошо развиваться, ведь за последние два-три года произошел огромный прорыв в этой области, да и вообще в области робототехники и искусственного интеллекта. Но автор не дожил до этого момента (Станислав Лем 1921-2006). Почему же Лем отдал предпочтение именно роевому интеллекту, ведь по сути это даже не интеллект, в привычном понимании этого слова? Все объясняется в цитате: «...лишь около 2040 года информатики, специалисты по цифровой технике и прочие эксперты стали задаваться вопросом, почему, собственно, их предшественники так долго оставались слепыми настолько, что per fas et nefas (правдами и неправдами (лат.)) и при помощи brute force (грубой силы (англ.)) пытались создать искусственный интеллект. Ведь для огромного большинства задач, которые выполняют люди, интеллект вообще не нужен». Так множество боевых дронов, каждый из которых выполняет определенную задачу, доберутся до места по отдельности, а уже непосредственно перед местом соберутся в единое целое и нанесут удар. И такому оружию нельзя будет ничего противопоставить из имеющихся средств защиты, разве что кроме импульсной гранаты, которая выключает всю электронику в зоне деятельности, но она находится все еще на стадии разработки во многих КБ мира. А от остальных факторов они полностью защищены, ведь они каждый сам управляет собой и «глушилки» будут бесполезны. Так же поскольку они состоят из органики, то им не страшна радиация и до определенного момента тепловое излучение. Каждый из них представляет собой простейший механизм, что уменьшает вероятность поломки, и наконец они все взаимозаменяемы, поскольку будут дублироваться по многу раз. Но если уйти от военного применения и перенестись из возможно недалекого будущего в настоящее, то уже эту технологию можно использовать например для поиска очагов заражения воды или воздуха, с помощью нано-дронов. Их можно будет выбрасывать в море или реку, и дальше они будут по своему алгоритму искать место наибольшего заражения и рано или поздно найдут его источник.
Муравьиный алгоритм: тут все намного проще и понятнее, с помощью этого алгоритма можно найти наиболее оптимальные пути для прокладывания дорог, связывающих несколько городов. Таких как, например, скоростные магистрали. Так же можно моделировать наиболее оптимальные способы пожарной эвакуации, ведь примерно так же люди будут искать верный путь для эвакуации, так почему не сделать путь там, где это удобно.
- ЗАКЛЮЧЕНИЕ
Во время работы я открыл для себя крайне интересную тему, которая крепко засела в моей памяти, и вероятно в скором будущем я к ней еще вернусь в рамках других работ. Но непосредственно к теме. Моей целью было понять принцип работы алгоритмов, и расширить свои знания относительно модуля «Random». Так же мне удалось найти несколько вариантов использования данного метода в, пусть и не повседневной, но достаточно близких к простому обывателю сферах деятельности. Данный подход является очень хорошим, поскольку в условиях постоянно меняющегося мира, он позволяет подстраиваться под реальность. А военный потенциал практически безграничен. Работы была крайне интересная, хоть я и работал с самой «верхушкой айсберга».
- СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Лемм С. Системы оружия 21 века или эволюция вверх ногами: эссе.
Маконнелл Дж. Анализ алгоритмов. Вводный курс. Москва: Техносфера, 2013. 304 с.
Нагел К. С# 2005 для профессионалов. Москва: Вильямс, 2014. 1376 с.
Метод роя частиц [Электронный ресурс] // Википедия. Свободная энциклопедия: [сайт]. URL: https://ru.wikipedia.org/Метод_роя_частиц (дата обращения: 05.03.2018).
Муравьиный алгоритм [Электронный ресурс] // Википедия. Свободная энциклопедия: [сайт]. URL: https://ru.wikipedia.org/wiki/Муравьиный_алгоритм (дата обращения: 06.03.2018).
Роевой интеллект [Электронный ресурс] // Википедия. Свободная энциклопедия: [сайт]. URL: https://ru.wikipedia.org/wiki/Роевой_интеллект (дата обращения: 02.03.2018).