Максим Шапиро - Гуманитарная помощь

- Напротив, - возразил Поллит, - Это будет очень трудно. Почти невозможно.

- Гм, - Семченко потер подбородок и взглянул на Графа, - Так в чем там дело? – спросил он у него, - Что не так с этими ребятами на Сарасте?

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

- Институты? – недоуменно спросил генетик.

- Это долгая история, - предупредил экономист.

- А я никуда и не тороплюсь, - заявил Семченко, закинув ногу на ногу и всем своим видом демонстрируя, что он не уйдет пока не получит исчерпывающий ответ.

- Хорошо, - вздохнул экономист, - Но начать придется очень издалека.

Семченко сделал приглашающий жест.

- Представьте, что вы коммивояжер и перед вами стоит простая с виду задача – вы должны объехать сто деревенек, продавая различный товар 107 107 Gutin, G., & Punnen, A. P. (Eds.). (2002). The traveling salesman problem and its variations (Vol. 12). Springer. . Для простоты допустим, что из каждого населенного пункта вы можете двигаться в другой по прямой. Казалось бы, собрался и в путь. Но вы не просто коммивояжер. Вы очень рациональный коммивояжер. Поэтому вы решаете посетить все деревеньки и вернуться домой по кратчайшему из возможных маршрутов. Но как найти самый кратчайший маршрут соответствующий подобных условиям? Может перебрать все возможные варианты маршрутов, сравнить их и выбрать самый оптимальный? – Поллит достал из кармана найзер, включил голографический проектор и продолжил, - Тем более, что формула расчета количества всех возможных маршрутов для проблемы коммивояжера при числе городов равных n уже давно выведена. Вот она.

(n-1)!/2

- При n равном 100 мы получим

(100-1)!/2≈4,666*10 155

- Это достаточно много, - ухмыльнулся Поллит, - Намного, намного больше чем число всех существующих частиц в видимой части вселенной. Но может с помощью компьютера мы посчитаем быстрее? Есть, однако, как мне подсказывает мой искин, фундаментальные ограничения на вычислительную мощность материи, следующие из уравнения эквивалентности массы и энергии Эйнштейна и принципа неопределенности Гейзенберга. Так максимальная теоретически достижимая скорость вычислений на килограмм вещества равна 108 108 Bremermann, H. J. (1962). Optimization through evolution and recombination. Self-organizing systems, 93-106.

1.36×10 50бит в секунду на килограмм

- Допустим нам удалось всю видимую нам вселенную превратить в компьютер работающий на теоретическом пределе мощности, - продолжил экономист, - Масса нашей вселенной, если брать обычную материю, а не темную, будет приблизительно равна 1053 килограмм 109 109 Paul Davies (2006). The Goldilocks Enigma. First Mariner Books. p. 43–. ISBN 978-0-618-59226-5. Retrieved 1 July 2013. . Соответственно наш гигантский

компьютер будет обладать вычислительной мощностью

(1.36×10 50)×10 53=1.36×10 103бит в секунду

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

4,666*10 155/1,36*10 103=3,43*10 52секунд

- Это опять-таки намного порядков больше чем возраст нашей вселенной. Ждать в общем придется долго. Мораль проста. При решении с помощью перебора многих с виду простых проблем число возможных вариантов растет экспоненциально. Даже при относительно небольшом количестве составляющих частей мы очень быстро приходим к границам вычислительных возможностей 110 110 Krippendorff, Klaus. "Combinatorial Explosion". Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Retrieved 29 November 2010. . Но что такое любая информация как не комбинация составляющих ее частей? Частей, которых может быть гораздо больше ста. Фактически любая информация — это комбинация чего-либо. Но как нужную дверь открывает далеко не любой ключ, так и не любая информация полезна. В задаче коммивояжера нас интересует не первый попавшийся путь, а именно кратчайший. Однако найти его, как мы видим, может быть очень непросто.

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

- О том и речь, - согласился Поллит, - Поскольку перепробовать все возможные способы решения таких задач невозможно, то приходится действовать наугад и многое зависит от банального везения. Но не только от него. Та же задача коммивояжера приближенно неплохо решается с помощью имитации естественного отбора или строго говоря «генетического алгоритма» 111 111 Davis, L. (Ed.). (1991). Handbook of genetic algorithms (Vol. 115). New York: Van Nostrand Reinhold. . Да и эволюция живых существ вполне себе идет вперед.

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

Потомки получают ее и добавляют к ней что-то свое. Так миллиардами лет в ДНК накапливаются знания.

Фактически это обучение из поколения в поколение, делающее организмы чуть более приспособленными к текущей среде. И поскольку число возможных комбинаций генов чудовищно – эволюция никогда не заканчивается 112 112 Wiser, M. J., Ribeck, N., & Lenski, R. E. (2013). Long-term dynamics of adaptation in asexual populations. Science, 342(6164), 1364-1367. хоть и замедляется. Собственно, так в ее процессе и создается информация – делается случайный выбор и его результаты подвергаются естественному отбору 113 113 Quastler, H. (1964). The emergence of biological organization. New Haven: Yale University Press. . Если брать ваш пример с коммивояжером, то очевидно, что разные коммивояжеры будут пробовать разные способы объехать все города. И те, у которых при прочих равных суммарный путь будет короче – будут преуспевать и постепенно вытеснят с рынка остальных.

- Если только эти остальные не скопируют маршрут самого успешного коммивояжера, по которому тот объезжает населенные пункты, и не начнут использовать его сами, - вставил Граф.

- И с чего бы такому успешному коммивояжеру делиться с конкурентами своим маршрутом? – скептически спросил Семченко.

- Недавно проводили детский конкурс по созданию наиболее успешных животных, соревнующихся в виртуальном террариуме 114 114 http://news.microsoft.com/2002/02/25/microsoft-terrarium-game-demonstrates-continuing-developer-enthusiasm-for-net-platform/ , - ответил советник, - Никакого искусственного интеллекта, разумеется. Никаких сложных алгоритмов. Все очень примитивно. Дети ведь. Прямой обмен данными между животными по условиям задачи запрещен. Но школьная команда создавшая лучшее травоядное сумела его обойти. Они придумали очень простое правило – «Если видишь животное твоего вида, которое бежит в какую-либо сторону – беги туда же» 115 115 http://habrahabr.ru/company/microsoft/blog/130755/ .