Моделирование перемещения бактерий

Одной из наиболее изученных бактерий является бактерия Е. Coli [8], которая живёт в кишечнике большинства млекопитающих (в том числе и в кишечнике человека). Бактерия Е. Coli при соответствующих условиях может самовоспроизводиться (расщепляться) за 20 мин. Движение бактерии Е. Coli обеспечивается шестью или более жгутиками, вращающимися с частотой 100...200 об/с, каждый из которых управляется своим собственным биологи­ческим «мотором».

Примерная схема движения бактерии выглядит следующим образом: ко­гда «мотор» работает в одну сторону, все жгутики у бактерии складываются и вращаются вместе, и бактерия движется прямолинейно. В конце пробега бактерия останавливается, «мотор» переключается и начинает работать в другую сторону. Жгутики растопыриваются и «бултыхаются» независимо друг от друга. Бактерия при этом переориентируется в пространстве случай­ным образом. После этого «мотор» опять переключается и начинает работать в ту сторону, в которую жгутики работают вместе, и возникает следующий отрезок прямолинейного движения.

Хемотаксис - это двигательная реакция бактерии в ответ на появление в среде аттрактанта (аттрактант - вещество, привлекающее бактерий) или ре­пеллента (репеллент - вещество, отпугивающее бактерий). В естественных условиях аттрактантами являются вещества, полезные для бактерий репеллентами - те, которые бактериям вредны.

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

Таким образом, можно выделить следующие хемотаксические действия бактерии Е. Coli:

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

- если бактерия перемещается по градиенту аттрактанта, то перемеще­ние продолжается в этом же направлении. Таким образом, обеспечивается поиск более благоприятной окружающий среды;

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

Таким образом, бактерия может перемещаться в областях с полезным» веществами и в то же время избегать опасных веществ. Сенсоры, используе­мые Е. Coli, - белковые рецепторы, которые являются очень чувствительны­ми (незначительное изменение в концентрации полезных веществ может вы­звать существенное изменение в поведении бактерии).

От рецепторов сигналы поступают на метилакцептирующие белки, ко­торые собирают все сигналы от рецепторов, и результирующий сигнал выхо­дит на «мотор» жгутика, который управляет движением бактерии в зависи­мости от соотношения полезных и опасных веществ в окружающей среде.

Бактерии часто умирают или расстворяются, и это должно учитываться при моделировании их деятельности. Мутации у Е. Coli происходят в нор­мальных условиях приблизительно 10'⁷ ген в поколение.

E.Coli могут формировать сложные устойчивые пространственно- временные структуры в некоторых полутвердых полезных средах. Бактерии могут поглощать питательные вещества по их радиусу, начиная от внешней границы заканчивая серединой, даже в случае, если бактерии были изначаль­но размещены в центре питательных веществ. Кроме того, при определённых I условиях они могут скрывать притягивающие сигналы от клетки к клетке, за счёт чего они группируются и защищают друг друга. Таким образом, эти бактерии могут группироваться в колонии.

Муравьиный алгоритм

Муравья нельзя назвать сообразительным. Отдельный муравей не в со­стоянии принять даже простейшего решения. Дело в том, что он устроен крайне примитивно: все его действия сводятся к элементарным реакциям на окружающую обстановку и своих собратьев. Муравей не способен анализиро­вать, делать выводы и искать решения. Эти факты, однако, никак не согласу­ются с успешностью муравьев как вида. Они существуют на планете более 100 млн лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны.

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

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

Каждый раз, проходя от муравейника до источника пищи и обратно, мура­вьи оставляют за собой дорожку феромонов. Другие муравьи, почувствовав та­кие следы на земле, будут инстинктивно устремляться к источнику пищи. По­скольку эти муравьи тоже оставляют за собой дорожки феромонов, то чем больше муравьев проходит по определённому пути, тем более привлекатель­ным он становится для их сородичей. При этом, чем короче путь до источника пищи, тем меньше времени требуется муравьям на него, а следовательно, тем быстрее оставленные на нем следы становятся заметными.

Имитируя поведение колонии Муравьёв в природе, муравьиные алгоритмы используют многоагентные системы, агенты которых функционируют по край­не простым правилам.

Классический муравьиный алгоритм. Как уже отмечалось, муравьиный алгоритм моделирует много­агентную систему. Её агентов в дальнейшем будем называть муравьями. Как и настоящие муравьи, они устроены довольно просто: для выполнения своих обязанностей они требуют небольшое количество памяти, а на каждом шаге работы выполняют несложные вычисления. Каждый муравей хранит в памя­ти список пройденных им узлов. Этот список называют списком запретов, или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качест- ве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма - т. е. перед тем, как мур_а. вей вновь проходит путь - он опустошается.

Кроме списка запретов при выборе узла для перехода муравей руковод­ствуется «привлекательностью» рёбер, которые он может пройти. Она зави­сит, во-первых, от расстояния между узлами (т. е. от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее му­равьями. Естественно, что в отличие от весов рёбер, которые являются кон­стантными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, на­против, усиливают их.

Жадные алгоритмы

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

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет “самый жирный кусок”, а потом уже пытается сделать наилучший выбор среди оставшихся вариантов, каковы бы они ни были. Алгоритм динамического программирования принимает решение, просчитав заранее последствие всех вариантов.

Оптимальность для подзадач

Решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач: оптимальное решение всей задачи содержит оптимальное решение подзадач.

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