Станислав Лем: Генетические алгоритмы

Здесь есть возможность читать онлайн «Станислав Лем: Генетические алгоритмы» весь текст электронной книги совершенно бесплатно (целиком полную версию). В некоторых случаях присутствует краткое содержание. категория: Фантастика и фэнтези / на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале. Библиотека «Либ Кат» — LibCat.ru создана для любителей полистать хорошую книжку и предлагает широкий выбор жанров:

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

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

libcat.ru: книга без обложки
  • Название:
    Генетические алгоритмы
  • Автор:
  • Жанр:
    Фантастика и фэнтези / на русском языке
  • Язык:
    Русский
  • Рейтинг книги:
    3 / 5
  • Избранное:
    Добавить книгу в избранное
  • Ваша оценка:
    • 60
    • 1
    • 2
    • 3
    • 4
    • 5

Генетические алгоритмы: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Генетические алгоритмы»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Станислав Лем: другие книги автора


Кто написал Генетические алгоритмы? Узнайте фамилию, как зовут автора книги и список всех его произведений по сериям.

Генетические алгоритмы — читать онлайн бесплатно полную книгу (весь текст) целиком

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

Шрифт:

Интервал:

Закладка:

Сделать

Лем Станислав

Генетические алгоритмы

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

При десяти городах для решения задачи компьютеру требуется около пяти секунд, но для двадцати городов требуется уже около 100 000 лет, так как это так называемая «NP-проблема» (не полиномиальная, по-английски «nopolynomial»), и решение требует N! шагов. Время, необходимое для решения проблем типа «P», растет вместе с размерами проблем приблизительно в том же самом темпе (10 единиц времени для 10 элементов проблемы и т. д.). А решения проблем типа «NP» растут по времени, как сказано выше, быстро, и вскоре уже возможно ожидание у компьютера МИЛЛИОНОВ лет на их решение. Те худшие NP-проблемы математики называют «твердыми», так как даже при наибольшей вычислительной мощности проблема компьютером практически не берется, ибо здесь любая «brute force» [«грубая сила» — здесь и далее в квадратных скобках примечания переводчика], особенно как в давних алгоритмах игры в шахматы, ничем не поможет. На сцену выходят более новые алгоритмы, называемые генетическими потому, что подобные использует Мать Природа в сфере биологии и биологической эволюции. Sensu stricto atque proprio [в строгом смысле и собственно] не являются они такими же, как классические алгоритмы, так как не заключают в себе рецепт на единственное оптимальное решение, такое, лучше которого уже быть не может. Оно скорее не тождественно оптимальному, а является хорошей аппроксимацией оптимального решения. Как такие алгоритмы функционируют, не очень просто представить, и особенно для действительно «твердых» NP-проблем, так как принципиально представление этого процесса выходит за границы человеческого воображения. Но можно осуществить своего рода упрощение такого представления, причем разными способами. Что-то подобное происходит, когда для получения какого-либо наглядного представления грани многомерного пространства проецируем в пространство меньшего количества измерений. Манфред Эйген (Manfred Eigen) изобразил это элементарное эволюционное движение генетических систем на модели, в качестве которой выступает так называемый «измеряемый пейзаж» («Wertlandschaft» — «Stufen zum Leben», Piper, 1987). «Пейзаж» выглядит как заполненная холмистыми возвышенностями равнина, при этом «псевдоорганизмы», которые борются за выживание по правилам естественного отбора, окружая их вершины, могут с низких перескакивать на более высокие. В этом также заключен их «биологический прогресс» как «survival of the fittest» [выживание при прохождении теста]. Те, которые так перемещаться не могут, погибают, так как процесс осуществляется во время их репликации [от replication — копирование], а если репликация плохо происходит, то наступает что-то, что очень напоминает фазовый переход (как, например, вода превращается в лед, или НАОБОРОТ: происходит изменение состояния).

Здесь нить рассказа, позаимствованного у Манфреда Эйгена, прерываю, а вспомнил о нем прежде всего затем, чтобы показать, какой в наше время дорогой идет и движется вперед мысль исследователя, чтобы как-то жизненные процессы выбора и отбора смоделировать, так как в слишком сложном «оригинале» представлять их пока не умеем («организмы», кружащие над измеряемым пейзажем Эйгена, даже с точки зрения бактерий или простейших вирусов, являются примитивными моделями, НО ОСНОВЫ ИХ ДИНАМИКИ можно уже распознать и на модели).

Для решения проблем «NP», или тех, которые полиномиально попробовать или разгрызть не удается, эксперты организовали другой «пейзаж». «Пейзаж» (landscape) по сути как бы взят у Эйгена, но перевернут, ибо где у Эйгена возвышенности — здесь долины. Он «измерим», хотя ценности, которые приписываются глубине этих «долин», радикально отличаются от величин Эйгена. Зато для решения таких проблем, как уже упоминавшееся путешествие коммивояжера по кратчайшему пути между городами (или для установления, какое количество самолетов на заданном количестве аэродромов нужно держать в готовности для минимизации затрат, вызванных произвольным действием, которое какое-то количество самолетов, готовых к старту, задержит на земле; количество таких заданий может быть разнообразно большим), глубина «долины» устанавливается ценой (затратами), которую нужно заплатить для покрытия затрат, связанных с путешествиями (или поддержанием самолетов в стартовой готовности: как видно, эти «генетические ландшафты» при своей стереометрической тождественности могут служить для решения абсолютно различных задач). Чем глубже долина, тем МЕНЬШЕ затраты (внимание: между затратами и «глубиной» обратная зависимость!). Ищется тогда долина поглубже, потому что она обозначает минимум затрат, и именно это является плодом реализации квази-генетического алгоритма для решения проблемы поиска, который, проведенный вслепую, или непосредственными («человеческими») действиями, или при помощи «brute force» компьютера, продолжаться может миллионы лет. В какого вида отношении то, что здесь кратко представлено, стоит с реальными «алгоритмически генетическими проблемами» в биологии (в биологической эволюции), точно не известно, что видно хотя бы из того, что позиции «истинных» генетиков, т. е. действующих в области биологии, принципиально взаимно различаются. Нужно сказать, что на этом поле скрыты мощные загадки. Применяя методики, основанные на эволюционной мысли Дарвина и других, Д. Эпплгейт (D. Applegate) из лаборатории Bell в прошлом году поставил рекорд в поиске оптимальной дороги для коммивояжера между 7 397 городами: этот вдохновленный генетикой поиск продолжался 3,5 года, но действие вслепую (brute force) требовало бы анализа 102547 дорог, что продолжалось бы дольше, чем СУЩЕСТВОВАНИЕ ВСЕЛЕННОЙ!

Читать дальше

Шрифт:

Интервал:

Закладка:

Сделать

Похожие книги на «Генетические алгоритмы»

Представляем Вашему вниманию похожие книги на «Генетические алгоритмы» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё не прочитанные произведения.


Отзывы о книге «Генетические алгоритмы»

Обсуждение, отзывы о книге «Генетические алгоритмы» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.