SEMESTRÁLNÍ PRÁCE Z PŘEDMĚTU Matematické modelování (KMA/MM) Téma: Model pohybu mravenců
Zdeněk Hanzal (A08N0182P,
[email protected]) Obor: FAV-AVIN-FIS
2008/2009
1. ÚVOD
Model byl převzat z knihy „Spojité modely v biologii“ viz literatura, jedná se o matematický model z oblasti biologie. Teoretický pohled na model vypadá obecně následovně.
Model vychází z náhodného pohybu mravenců v okolí mraveniště. Mravenec se náhodně pohybuje v okolí mraveniště dokud nenajde větší zdroj potravy a svou cestu si přitom značkuje. V případě, že najde větší zdroj potravy, vrací se podle svých feromonových značek zpět do mraveniště kde vyšle signál ostatním mravencům. Mravenci ho poté jeden po druhém následují, přitom po nějaké době vytvoří řada mravenců přímou cestu spojující mraveniště s místem, kde se zdroj potravy nachází. V semestrální práci ukážeme, že i bez předpokladu hlubší intelektuální schopnosti, pouhým sledováním pohybu předchozího mravence, vyřeší mravenci tímto kolektivním úsilím časem optimalizační úlohu nalezení nejkratší spojnice dvou bodů, tj. vytvoří optimální cestu k cíli (potravě), kterou lze často v přírodě pozorovat.
2/17
2. SESTAVENÍ MODELU Značení a zavedení soustavy souřadné a časové osy Nejprve je nutno zavést soustavu souřadnou a to tak, že mraveniště umístíme do počátku soustavy souřadné tj. [0,0]. Cíl (kořist, potravu) pak umístíme do bodu [L,0]. Dále zavedeme předpoklad konstantní stejné rychlosti pohybu v u všech mravenců. Nechť první mravenec průzkumník, označený jako
M0 , se pohybuje po své
označkované cestě následovně. • V čase τ je v bodě [0,0] , poté vyráží na cestu. • V čase t se nachází kdesi v bodě [x0(t) , y0(t)] (tj. kdesi na křivce kopírující průběh jeho cesty) • V čase T0 se dostává konečně k potravě do cíle, který se nachází v bodě [L,0]. Nákres je zobrazen v následujícím obrázku 1.
Obrázek 1 – pohyb mravenců v zavedené souřadné soustavě
Pro ostatní mravence poté platí: • V čase τ > δ (kde δ > 0 ), vyráží z mraveniště druhý mravenec M1 a zamíří přímo k mravenci M0.
3/17
• V čase τ ≥ τ 1 + δ vyráží z mraveniště třetí mravenec M2 a míří přímo k mravenci M1 . A takto následují i ostatní mravenci.
Odvození modelu pohybu mravenců :
uur Polohový vektor pn každého z mravenců Mn , pro n=0,1,2,… v čase t (1)
uur uur pn = pn (t ) = ( xn (t ) , yn (t ) ) .
Vektor rychlosti p´n (t ) mravence Mn je poté vyjádřen následovně: (2)
dpn (t ) . dt
p´n (t ) =
Vzhledem k předpokladu konstantní stejné rychlosti v u všech mravenců, platí dále: (3)
p´n = v , pro všechna n=1,2,3,….. ,
kde |x| značí velikost vektoru x (tj. eukleidovskou normu
x = x12 + K + xn2 ).
Poněvadž mravenec Mn míří přímo k mravenci Mn-1 platí dále: (4)
p´n = c ( pn −1 − pn ) ,
kde c je kladná konstanta. Z výrazu (3) a (4) plyne ovšem rovnost (5)
p´ n = c ( pn −1 − pn ) = c pn −1 − pn = v .
Po vyjádření konstanty c = v / pn −1 − pn
z předchozího výrazu (5) a její dosazení do
výrazu (4) dostáváme model pohybu mravenců ve tvaru nekonečného systému diferenciálních vektorových rovností: (6)
p´n (t ) =
v ( pn −1 (t ) − pn (t ) ) pn −1 (t ) − pn (t )
4/17
, n=1,2,3,……
Pro řešení tohoto systému rovnic (řešením jsou fce pn(t) při platnosti rovnosti (6) při známém v a p0(t) ) je však nutno dodat, že musí splňovat ještě počáteční podmínky a to konkrétně:
pn (τ n ) = ( 0, 0 ) ,
(7)
n=1,2,3,……
kde {τ n }n =1 je rostoucí posloupnost kladných reálných čísel splňující τ n − τ n −1 = δ + ε n , ∞
kde {ε n }n =1 je ohraničená posloupnost nezáporných čísel. ∞
O vektorové funkci p0 = p0 (t ) předpokládáme, že je definovaná na intervalu 0, ∞ ) , je spojitá (mravenec nedělá skoky, což odpovídá realitě), je diferencovatelná na intervalu ( 0,T0 ) (mravenec se pohybuje konstantní rychlostí v , tj. p´0 existuje a p´0 = v ) a pro t ≥ T0 je p0 (t ) = ( L, 0 ) . Tuto funkci považujeme za známou.
Lze tedy numericky vyřešit počáteční úlohu (6), (7) s n=1 a najít vektorovou funkci p1 = p1 (t ) , pak lze numericky najít funkci p2 = p2 (t ) , atd.
Problém může nastat v případě, že pro nějaké τˆn ≥ τ n platí
pn (τˆn ) = pn −1 (τˆn ) .
V takovém případě není pravá strana rovnosti (6) pro t = τˆn definována, a tedy řešení výše stanovené rovnice pn nelze prodloužit za τˆn . V tomto případě klademe pro
t > τˆn pn (t ) = pn −1 (t ) . Tímto způsobem lze nadefinovat všechny vektorové funkce pn pro n=1,2,3,….. na intervalu τ n , ∞ ) .
5/17
Odvození vlastností systému: Aniž bychom řešili samotný systém (6),(7) lze odvodit několik zásadních vlastností.
1. Nerostoucí vzdálenost dvou mravenců a konečný čas dosažení potravy První vlastností je, že žádný z mravenců neuteče svému následovníku, tj. vzdálenost mezi mravenci Mn-1 a Mn se s časem nezvětšuje. Je tedy nutno ukázat, že funkce
∆ n = ∆ n (t ) = pn −1 (t ) − pn (t ) ,
(8)
značící onu vzdálenost mezi mravenci, je nerostoucí v čase, tedy platí: d d ∆n = ( pn −1 − pn ).( pn −1 − pn ) = dt dt ( p´n −1 − p´n ).( pn −1 − pn ) + ( pn −1 − pn ).( p´n −1 − p´n ) = = 2 ( pn −1 − pn ).( pn −1 − pn ) = ( p´n −1 − p´n ).
pn −1 − pn . pn −1 − pn
Využijeme-li rovnosti (6) dostáváme
p − pn 1 d 1 ∆ n = ( p´n −1 − p´n ). n −1 = ( p´n −1 − p´n ) . p´n = p´n −1. p´n − p´n pn −1 − pn v dt v
(
2
)
Připomeneme-li si, že pro každé dva vektory q, r platí Cauchyova-Bunjakovského nerovnost zapsaná následovně: q . r ≤ q r , kde q.r je skalární součin těchto dvou vektorů. Použitím této nerovnosti, rovnosti (3) a konstantní rychlosti mravence v dostáváme
(
d 1 ∆ n = p´n −1. p´n − p´n dt v
2
) ≤ 1v ( p´
n −1
1 p´n − v 2 ) = (v 2 − v 2 ) = 0 . v
Dokázali jsme tedy, že vzdálenost mezi za sebou jdoucími mravenci se s časem nezvětšuje v námi definovaném modelu.
6/17
Dále lze ukázat, že se každý mravenec dostane do k potravě, tj. do bodu [L,0] v konečném čase. Vycházíme ze skutečnosti, že z výchozí pozice mravence Mn-1 neboli z bodu [0,0] se mravenec Mn-1 dostane nejdále při přímočarém pohybu. To však znamená, že ∆ n (τ n )
(9)
≤
v (τ n − τ n −1 ) = v (δ + ε n ) ,
tj. vzdálenost mravence Mn-1 od mravence Mn, který za ním vyráží z mraveniště v čase τ n je rovna nejvýše vzdálenosti, kterou urazil mravenec Mn-1 při přímočarém pohybu mezi časy τ n −1 a τ n . Zavedeme-li dále vzdálenost D , jakožto vzdálenost uraženou při přímočarém pohybu v nejdelším časovém rozdílu dvou po sobě vycházejících mravenců, tj.
D = v (δ + sup {ε n : n ∈
(10)
},
pak při platnosti již dokázané nerostoucí vzdálenosti mezi mravenci v čase lze psát
∆ n (t ) ≤ D pro t ≥ τ n , n=1,2,3,…..
(11)
Z nerovnosti (11) tedy vyplývá, že každý mravenec se v konečném čase dostane k místu potravy do bodu [L,0] neboť v čase T0, kdy se do tohoto bodu dostal mravenec M0, je vzdálenost mravence M1 od něho ∆1 (T0 ) ≤ D . Mravenec M1 tedy do bodu [L,0] směřuje již přímočaře, takže bodu [L,0] dosáhne v čase T1 = T0 +
∆1 (T0 ) D ≤ T0 + . v v
Analogicky se pak n-tý mravenec dostane do bodu [L,0] v čase Tn = Tn −1 +
∆ n (Tn −1 ) 2D D D D nD ≤ Tn −1 + ≤ Tn − 2 + + = Tn − 2 + ≤ ... ≤ T0 + . v v v v v v
7/17
2. Délka cesty mravenců Dále lze dokázat, že celková dráha, uražená mravenci při cestě k potravě, se s časem a počtem mravenců nezvyšuje. V modelu je rozumné předpokládat, že cíl [L,0] je dostatečně daleko od mraveniště [0,0] a to tak daleko, že n-tý mravenec k němu dorazí později, než jeho následovník (n+1)-ní mravenec vyrazí z mraveniště (předchůdce nedorazí k cíli dřív než následovník vyrazí z mraveniště) tj. (12)
Tn > τ n +1 , pro všechna n=0,1,2,….
Označme ln jako celkovou délku dráhy, kterou urazí mravenec Mn, tj. Tn
(13)
ln =
∫ τ
x´n 2 ( s ) + y´n 2 ( s ) ds = v (Tn − τ n )
n
Poněvadž předpokládáme Tn > τ n a nenulovou v platí ln > 0 pro každé n ∈
.
Vzhledem k tomu, že v okamžiku Tn, kdy předchozí mravenec Mn dorazí k cíli [L,0], zamíří následující mravenec Mn+1 přímočaře k němu je celková délka l n +1 dráhy, kterou urazí mravenec Mn+1 vyjádřena následovně (rekurentně): (14)
ln+1 = v (Tn −τ n+1 ) + ∆n+1 (Tn ) = v (Tn −τ n ) − v (τ n+1 −τ n ) + ∆n+1 (Tn ) = ln − v (δ + ε n+1 ) + ∆n+1 (Tn )
Z rovností (13),(14) a z nerovnosti (12) a současně z faktu, že ∆ n+1 je nerostoucí funkce času (viz výše) dále plyne ln +1 − ln = ∆ n +1 (Tn ) − v(δ + ε n +1 ) = ∆ n +1 (Tn ) − ∆ n +1 (τ n +1 ) ≤ ∆ n +1 (τ n +1 ) − ∆ n +1 (τ n +1 ) = 0 , a je tedy dokázáno, že posloupnost {ln }n =0 je nerostoucí, což rovněž znamená, že ∞
ln ≤ l0 pro všechna n=1,2,3,…..
8/17
Dále dokážeme existenci rostoucí posloupnosti {nk }k =1 přirozených čísel takové, že ∞
∆ nk (Tnk −1 ) ≥
(15)
δv 2
.
Důkaz provedeme sporem. Tedy připustíme existenci n0 ∈ ∆ n (Tn −1 ) <
(16)
δv 2
takového, že
pro všechna n ≥ n0 .
Z rovnosti (14) a z předpokladu (16) plyne, že pro n ≥ n0 je splněna nerovnost ln +1 − ln = −v(δ + ε n +1 ) + ∆ n +1 (Tn )
≤ −vδ + ∆ n+1 (Tn ) < −vδ + vδ 2
= −
vδ 2
Z ní dále úplnou indukcí plyne, že pro n ≥ n0 platí ln < ln0 − (n − n0 )
zejména tedy pro n ≥ n0 +
ln
vδ , 2
2 ln je vδ 0
< ln
0
− (n − n0 )
vδ 2 vδ ≤ ln0 − n0 + ln0 − n0 = 0. vδ 2 2
Zde narážíme na spor s předpokladem ln > 0 , čímž jsme dokázali nerovnost (15).
9/17
3. Optimalizace dráhy mravence Nakonec dokážeme, že při dostatečně velkém počtu mravenců n, se po jisté době všichni mravenci pohybují v úzkém pásu kolem nejkratší spojnice mraveniště a cíle. V limitě by se pak pohybovali po této spojnici. Neboli vzdálenost mravence Mn od úsečky spojující mraveniště a potravu bude po celou dobu jeho pohybu menší než libovolné, předem dané kladné číslo.
Funkce yn ,druhá složka polohového vektoru pn , je řešením výše zmíněné počáteční úlohy
y´n =
(17)
v ( yn−1 − yn ) pn −1 − pn
, yn (τ n ) = 0 .
Jedná se o spojitou funkci na intervalu τ n , Tn a dle 1. Weierstrassovy věty lze tedy tvrdit, že je to funkce omezená. Dále označme
Yn max = max { yn (t ) : t ∈ τ n , Tn
(18)
Yn min = min { yn (t ) : t ∈ τ n , Tn
} }
Dokažme tedy, že platí 0 = yn (τ n ) ≤ Yn max ≤ Yn −1max , tj. že žádný mravenec se od úsečky spojující mraveniště a potravu nevzdálí více, než jeho bezprostřední předchůdce. Kdyby toto tvrzení neplatilo, tj. kdyby existovalo nějaké s ∈ τ n , Tn takové, že yn ( s ) = Yn max > Yn −1max ≥ yn −1 ( s ) ,
nutně by pak y´n ( s ) = 0 a současně dle (17) y´n ( s ) =
v ( yn-1 ( s) − yn ( s) ) < 0 , pn −1 ( s ) − pn ( s )
což by byl evidentně spor. Posloupnost {Yn max }
∞ n =1
je tedy nerostoucí a zdola ohraničená nulou, což znamená, že
je konvergentní.
10/17
Buď nyní k libovolné přirozené číslo. S využitím nerovnosti (15) a faktu, že ∆ nk je
(
)
nerostoucí funkce času, dostaneme, že pro každé t ∈ τ nk , Tnk −1 platí (19)
y´nk (t ) =
(
v yn −1 (t ) − ynk (t ) ∆ nk (t ) k
)≤
(
)
(
)
2v max 2 Ynk −1 − ynk (t ) = Ynmax − y (t ) . δv δ k −1 nk
Řešení počáteční úlohy pro lineární diferenciální rovnici
η´=
(20)
2
δ
(Y
max nk −1
)
− η , η (τ nk ) = 0
pak vypadá následovně
(
η (t ) = Ynmax −1 1 − e
(21)
k
−2( t −τ nk ) / δ
).
S přihlédnutím k nerovnosti (19) dostaneme s použitím srovnávací věty nerovnost
(
ynk (t ) ≤ Ynmax 1− e k −1
(22)
−2( t −τ nk ) / δ
),
platnou pro všechna t ∈ τ nk , Tnk −1 . Dále tedy platí
(
1− e Ynmax ≤ Ynmax k k −1
(23)
−2( t −τ nk ) / δ
) ≤ Y (1 − e max nk −1
−2(Tnk −1 −τ nk ) / δ
).
S využitím (13) tj. ln = v (Tn − τ n ) a skutečnosti, že {ln }n =0 je nerostoucí dostáváme ∞
nerovnost (viz exponent na pravé straně předchozího vztahu (23) )
Tnk −1 − τ nk ≤ Tnk −1 − τ nk −1 =
(24)
lnk −1 v
≤
l0 . v
Po dosazení vztahu (24) do nerovnosti (23) tedy dostáváme
(
)
Ynmax ≤ Ynmax 1 − e−2l0 /(δ v ) , k k −1
(25) neboli při úplné indukci (26)
0 = ynk (τ nk ) ≤ Y
max nk
≤Y
max n1
(1 − e
−2 l0 /(δ v )
)
nk − n1
=
Ynmax 1
(
Poněvadž 1 − e−2l0 /(δ v ) < 1 a současně lim nk = ∞ , platí k →∞
11/17
1 − e −2 l0 /(δ v )
)
n1
(1 − e
−2 l0 /(δ v )
)
nk
.
(
lim 1 − e −2l0 /(δ v ) k →∞
)
nk
= 0.
Z nerovnosti (26) a z věty o třech posloupnostech dostáváme
lim Ynmax =0. k k →∞
{
Jelikož jsme vybrali posloupnost Ynmax k
}
∞
z konvergentní posloupnosti {Ynmax }
∞
k =1
lim Ynmax = 0 . n →∞
Podobně by se dalo dokázat lim Ynmin = 0 . n →∞
12/17
n =1
, platí
3. SESTAVENÍ UPRAVENÉHO MODELU V předchozí kapitole jsem se zabývali modelem pohybu řady mravenců, vycházející z předpokladu, že každý mravenec sleduje svého předchůdce a míří přímo k němu. Nyní se budeme zabývat otázkou, nakolik je tento předpoklad realistický. Budeme přitom předpokládat pouze to, že mravenec umí vnímat každým z tykadel koncentraci nějakého feromonu a podle rozdílu koncentrací feromonu přijímaných jednotlivými tykadly mění směr svého pohybu.
Zpřesnění v soustavě souřadné Nadefinujeme si souřadnice hlavy mravence jako x = x(t ) a y = y (t ) , a dále směrový úhel osy těla mravence ϑ = ϑ (t ) , viz následující obrázek.
Obrázek 2 – mravenec v souřadné soustavě
Stále budeme předpokládat pro jednoduchost konstantní rychlost pohybu mravence v , tj. vektor rychlosti vypadá následovně v=(v cos ϑ ,v sin ϑ ). Za krátký časový interval ∆ t se poloha mravencovy hlavy změní o ∆ x = (v cos ϑ ) ∆t , ∆ y = (v sin ϑ ) ∆t . Dále budeme předpokládat, že mravenec mění směrový úhel osy těla v časovém intervalu ∆ t v závislosti na koncentracích feromonu Cl a Cr přijatých levým a pravým tykadlem, tedy změna směrového úhlu osy těla je funkcí dvou proměnných Cl a Cr tj. 13/17
(27)
∆ ϑ = F ( Cl , Cr ) ∆t ,
Limitním přechodem při ∆t → 0 dostaneme model pohybu jednoho mravence ve tvaru (28)
x´= v cos ϑ , y´= v sin ϑ , ϑ´= F ( Cl , Cr ) .
Pro získání konkrétního modelu, je zapotřebí blíže specifikovat funkci F. Budeme tedy předpokládat existenci nějaké maximální změny směru pohybu θ > 0 , jíž je mravenec schopen, tj. ϑ´ ≤ θ . Změna směru pohybu je přitom tím větší, čím je větší rozdíl ∆C = Cl + Cr koncentrací feromonu na koncích tykadel. V případě nulového rozdílu koncentrací se směr pohybu nemění, je-li na levém tykadle větší koncentrace feromonu než na pravém , tj. když ∆C > 0 , mravenec se otáčí v kladném smyslu, v opačném případě v záporném smyslu.
Příklad funkce F, která splňuje uvedené předpoklady je (29)
F (Cl , Cr ) = θ sgn (∆C ) f ( ∆C ) ,
přičemž funkce f : 0, ∞ ) → 0, ∞ ) je neklesající, spojitá a splňuje podmínky (30)
f (0) = 0 , lim f (ξ ) = 1 . ξ →∞
Nejjednodušší funkce s těmito vlastnostmi je (31)
f (ξ ) =
ξ ξ +ρ
,
kde ρ je kladná konstanta. Pro stanovení ϑ´= F ( Cl , Cr ) tedy zbývá vyjádřit Cl a Cr .
14/17
Budiž se že zdroj feromonu nachází v bodě Z = [ xz , yZ ] odkud se šíří do prostoru všemi směry, přičemž jeho koncentrace v bodě A bude nepřímo úměrná druhé mocnině vzdáleností bodů A a Z. Kladnou konstantu úměrnosti závisející na koncentraci feromonu ve zdroji a na vlastnostech prostředí, označme jako c. Dále označme Rl, resp. Rr , vzdálenost bodu Z od konce levého, resp. pravého, tykadla. Platí tedy (32)
Cl =
c c c , Cr = 2 , ∆C = 2 2 ( Rr2 − Rl2 ) . 2 Rl Rr Rl Rr
Dosazením do (31) dostáváme: (33)
f ( ∆C ) =
c Rr2 − Rl2 c Rr2 − Rl2 + ρ Rl2 Rr2
.
Nechť δ označuje vzdálenost konce tykadla od středu hlavy (tj. délku tykadel) a α úhel svírající tykadlo s osou těla (viz obrázek 2); patrně je δ > 0, 0 < α <
π 2
.
Souřadnice konce levého tykadla jsou potom následující (34)
x + δ cos (ϑ + α ) , y + δ sin (ϑ + α ) ,
resp. souřadnice konce pravého tykadla jsou (35)
x + δ cos (ϑ − α ) , y + δ sin (ϑ − α )
Dále je nutno vyjádřit vzdálenost Rl, resp. Rr, bodu Z = [ xZ , y z ] od levého, resp. pravého, tykadla (36)
Rl2 = ( xZ − x − δ cos (ϑ + α ) ) + ( yZ − y − δ sin (ϑ + α ) ) , 2
2
resp. (37)
Rr2 = ( xZ − x − δ cos (ϑ − α ) ) + ( yZ − y − δ sin (ϑ − α ) ) . 2
Odtud plyne
15/17
2
Rr2 − Rl2 = −2δ ( xZ − x ) ( cos (ϑ − α ) − cos (ϑ + α ) ) − − 2δ ( yZ − y ) ( sin (ϑ − α ) − sin (ϑ + α ) ) + + δ 2 ( cos 2 (ϑ − α ) − cos 2 (ϑ + α ) ) + + δ 2 ( sin 2 (ϑ − α ) − sin 2 (ϑ + α ) ) = = −2δ ( 2 ( xZ − x ) sin ϑ sin α − 2 ( yZ − y ) cos ϑ sin α ) = = 4δ sin α
( (y
Z
− y ) cos ϑ − ( xZ − x ) sin ϑ
)
Při dosazení předchozího rozdílu spolu s Rl2 a Rr2 tj. (36) a (37) do (33) dostáváme výsledný tvar funkce f. Spolu s funkcí f dosadíme do (29) i vztah (38)
sgn ( ∆C ) = sgn ( ( yZ − y ) cos ϑ − ( xZ − x ) sin ϑ )
Dostaneme vyjádření funkce F, které dosadíme do (28) a tím obdržíme výsledný model pohybu jednoho mravence.
Tento model poměrně složitý, takže z něho lze jen obtížně získat nějaké analytické výsledky. Lze ho ovšem řešit numericky a tím dostat tvar mravencovy cesty. To lze udělat v případě, že se bod Z nepohybuje, tedy když xZ, yZ jsou konstanty a řešený systém je autonomní, i v opačném případě, když xZ = xZ (t ) , yZ = yZ (t ) a systém není autonomní. Je-li vzdálenost zdroje feromonu a mravencovi hlavy příliš velká, přesněji řečeno, když c Rr2 − Rl2
ρ Rl2 Rr2 , pak porovnáním s (33) je vidět že f ∆C ≈ 0 . V takovém
případě tedy můžeme model (28) nahradit jednoduchým systémem rovnic (39)
x´= v cos ϑ , y´= v sin ϑ , ϑ´= 0 .
Řešením s počáteční podmínkou (40)
x(0) = x0 , y (0) = y0 , ϑ (0) = ϑ0
x(t ) = x0 + vt cos ϑ0 , y (t ) = y0 sin ϑ0 , ϑ (t ) = ϑ0 .
16/17
je
Mravenec tedy na feromon nereaguje, nezmění směr a pohybuje se po přímce. To samo o sobě není nějak překvapivý závěr. Upozorňuje ale na skutečnost, že může být obtížné experimentálně rozhodnout, zda vzdálený mravenec nereaguje proto, že podnět je natolik slabý, že ho nezachytil, nebo proto, že rozdíl podnětů na koncích jednotlivých tykadel je příliš malý.
LITERATURA [1]
Spojité modely v biologii – Josef Kalas, Zdeněk Pospíšil
17/17
