Генетические алгоритмы
Зарегистрируйся в два клика и получи неограниченный доступ к материалам,а также
промокод
на новый заказ в Автор24. Это бесплатно.
Введение
Наука возникает из непосредственного человеческого желания понимать и контролировать мир. На протяжении истории люди постепенно строили грандиозное здание знаний, которое позволяет в различной степени прогнозировать погоду, движения планет, солнечные и лунные затмения, течение болезней, подъем и падение экономического роста, этапов развития у детей и обширной панорамы других природных, социальных и культурных явлений. Совсем недавно человечество пришло к пониманию некоторых фундаментальных ограничений способности предсказывать. За прошедшие годы были разработаны все более сложные средства для контроля многих аспектов жизни и взаимодействий с природой, и была также обнаружена та степень, в которой другие аспекты неконтролируемы. Появление электронных компьютеров, возможно, было самым революционным событием в истории науки и техники. Эта продолжающаяся революция глубоко увеличивает человеческую способность предсказывать и контролировать природу способами, которые едва ли были задуманы даже полвека назад. Для многих венчающими достижениями этой революции станет создание – в форме компьютерных программ – новых видов разумных существ и даже новых форм жизни. Цели создания искусственного интеллекта и искусственной жизни можно проследить до самого начала компьютерного века. Самые ранние ученые компьютерных наук – Алан Тьюринг, Джон фон Нейман, Норберт Винер и другие – были в значительной степени мотивированы видениями наполнения компьютерных программ интеллектом, жизненной способностью к самовоспроизведению и адаптивной способностью к обучению и контроля своей сред. Эти первые пионеры информатики интересовались биологией и психологией так же, как и электроникой, и они рассматривали природные системы как метафору в отношении того, как достичь своего видения. Поэтому неудивительно, что с первых дней компьютеры применялись не только для расчета траекторий ракет и расшифровки военных кодов, но и для моделирования мозга, имитации обучения людей и моделирования биологической эволюции. Эта биологически мотивированная компьютерная деятельность с годами как усиливалась, так и ослабевала, но с начала 1980-х годов все эти области пережили возрождение в сообществе исследователей вычислительной техники. Первая выросла в область нейронных сетей, вторая – в машинное обучение, а третья – в то, что сейчас называется «эволюционными вычислениями», из которых генетические алгоритмы являются наиболее ярким примером. Зачем использовать эволюцию как источник вдохновения для решения вычислительных задач? Для исследователей эволюционных вычислений механизмы эволюции кажутся хорошо подходящими для некоторых из наиболее актуальных вычислительных задач во многих областях. Многие вычислительные проблемы требуют поиска огромного количества возможностей для решения. Одним из примеров является проблема белковой инженерии с искомым алгоритмом, который будет находить среди огромного числа возможных аминокислотных последовательностей белок с заданными свойствами. Другой пример – поиск набора правил или уравнений, которые будут предсказывать взлеты и падения финансового рынка, например, для иностранной валюты. Такие проблемы поиска часто могут выиграть от эффективного использования параллелизма, при котором многие различные возможности рассматриваются одновременно эффективным образом. Например, при поиске белков с заданными свойствами вместо того, чтобы оценивать одну аминокислотную последовательность за раз, было бы намного быстрее оценивать множество одновременно. Необходим как вычислительный параллелизм (т.е. несколько процессоров оценивают последовательности одновременно), так и разумная стратегия выбора следующего набора последовательностей для оценки. Важнейшим частным случаем эволюционных механизмов являются генетические методы и алгоритмы. Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции. Цель работы – изучить особенности генетических алгоритмов, их ключевые приложения и применения в задачах оптимизации.
Биологические основы
Многие вычислительные проблемы требуют, чтобы компьютерная программа была адаптивной и продолжала хорошо работать в изменяющейся среде. Другие требуют, чтобы компьютерные программы были новаторскими – для создания чего-то действительно нового и ориги...
Открыть главуСравнение с другими методами оптимизации
Итак, принцип любого генетического алгоритма прост: имитировать генетику и естественный отбор с помощью компьютерной программы. Параметры решаемой задачи наиболее естественно кодируются как ДНК-подобная линейная структура данных, вектор или строка. И...
Открыть главуЗадачи нечеткой оптимизации
Нечеткая оптимизация описывает проблему оптимизации с нечеткой целевой функцией и нечеткими ограничениями. Результаты, полученные с помощью классических методов оптимизации с использованием детерминированных переменных, имеют различные недостатки. В ...
Открыть главуЗадача комбинаторной оптимизации
Комбинаторная оптимизация – это отрасль оптимизации в прикладной математике и информатике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности, которая находится на пересечении нескольких областей, включая искусс...
Открыть главуЗаключение
Генетические алгоритмы – это оригинальные системы, основанные на предполагаемом функционировании живого организма. Этот метод сильно отличается от классических алгоритмов оптимизации. Важно понимать, что работа такого алгоритма не гарантирует успеха. Проблема заключается в стохастической системе, и генофонд может быть слишком далек от решения, или, например, слишком быстрая конвергенция может остановить процесс эволюции. Тем не менее, генетические алгоритмы чрезвычайно эффективны и используются в самых разных областях, таких как фондовая биржа, планирование производства или программирование сборочных роботов в автомобильной промышленности. Генетические алгоритмы могут даже быстрее находить глобальные максимумы, чем обычные методы, в частности, когда производные предоставляют вводящую в заблуждение информацию. Следует отметить, что в большинстве случаев, когда могут применяться обычные методы, генетические алгоритмы намного медленнее, потому что они не принимают во внимание вспомогательную информацию, такую как производные. В этих задачах оптимизации нет необходимости применять генетические алгоритмы, которые дают менее точные решения после гораздо большего времени вычислений. Огромный потенциал генетических алгоритмов заключается в другом – в оптимизации недифференцируемых или даже разрывных функций, дискретной оптимизации и индукции программ. Было заявлено, что посредством операций отбора, скрещивания и мутации генетические алгоритмы будут сближаться через последовательные поколения к глобальному (или почти глобальному) оптимуму. Эта простая операция должна создать быструю, полезную и надежную технику, в основном из-за того, что генетические алгоритмы объединяют направление и случайность в поиске эффективным и действенным образом. Поскольку популяция неявно содержит гораздо больше информации, чем просто индивидуальные оценки пригодности, генетические алгоритмы объединяют полезную информацию, скрытую в решении, с полезной информацией из другого решения, чтобы создавать новые решения с полезной информацией, унаследованной от обоих родителей, что неизбежно (как предполагается) ведет к оптимальности. Способность алгоритма одновременно исследовать и использовать информацию в своих интересах одновременно, растущее количество теоретических обоснований и успешное применение к реальным задачам укрепляет вывод о том, что генетический алгоритм является мощным и надежным методом оптимизации.
Список литературы
Вирт Н. Алгоритмы и структуры данных; [не указано] - М., 1995. - 365 c. Вирт Н. Алгоритмы+структуры данных=программы; [не указано] - М., 2003. - 609 c. Захарова Л.Е. Алгоритмы дискретной математики; [не указано] - М., 2002. - 308 c. Майника Э. Алгоритмы оптимизации на сетях и графах; [не указано] - М., 2008. - 893 c. Мальцев А.И. Алгоритмы и рекурсивные функции; [не указано] - М., 2011. - 985 c. Павлидис Т. Алгоритмы машинной графики и обработки изображений; [не указано] - М., 1994. - 247 c. Рассел Джесси Генетический алгоритм; VSD - М., 2012. - 664 c. Свами М., Тхуласираман К. Графы, сети и алгоритмы: моногр. ; [не указано] - М., 2001. - 297 c. Серпик Игорь Нафтольевич Генетические Алгоритмы Оптимизации Металлических Строительных Конструкций; ИЛ - Москва, 2010. - 188 c. Хуанг Т.С. (ред.) Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры; [не указано] - М., 2007. - 444 c.
