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

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

1

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

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