有物混成，先天地生。寂兮寥兮，獨立不改，周行而不殆，可以為天下母。吾不知其名，字之曰道，強為之名曰大。大曰逝，逝曰遠，遠曰反。故道大，天大，地大，王亦大。域中有四大，而王居其一焉。人法地，地法天，天法道，道法自然。

子虛先生據《烏有傳》講︰

小海龜法『地□』深得其術。

具體數學：計算機科學之基石

An ant starts to crawl along a taut rubber rope 1 km long at a speed of 1 cm per second (relative to the rubber it is crawling on). At the same time, the rope starts to stretch uniformly by 1 km per second, so that after 1 second it is 2 km long, after 2 seconds it is 3 km long, etc. Will the ant ever reach the end of the rope?

在『具體數學』這本書中提到了另一個『違反直覺』的例子 ── 橡膠繩上的螞蟻 ──，一隻螞蟻以每秒鐘一公分的速度，在一根長一公里拉緊了的橡膠繩上爬行【螞蟻的爬行速度相對橡膠繩】，就在螞蟻爬行的同時，橡膠繩也以每秒一公里的速度伸長，也就是說一秒後，它有兩公里長，兩秒後有三公里長等等。試問螞蟻果真到的了繩子之另一端的嗎？

假設 $t$ 時刻時，螞蟻在 $x(t), x_0 = x(0)$ 的『位置』，以 $\alpha$ 的速度朝另一端爬行，同時橡膠繩用 $v$ 的速度同向均勻伸長，因此橡膠繩上的某點 $X$ 的伸長速度將是 $\frac{X}{c + v t} v$ ，此處 $c$ 就是橡膠繩的『原長』，由於起點是『固定』不動的，因此繩上各點的速度與『端點的速度』 $v = \frac{c + v t}{c + v t} v$ 成比例，於是對於一個靜止的觀察者而言，螞蟻的速度將是

$\frac{dx(t)}{dt} = x'(t) = \alpha+\frac{x(t)}{c+vt} v$

。如果我們設想要是橡膠繩並不與時伸展，那麼這隻螞蟻是一定到的了彼端，假使一個相對於繩子靜止的觀察者將看到什麼現象的呢？或許他將用 $\Phi (t) = \frac{x(t)}{c + v t}$ 來描述這隻螞蟻的行進的吧！它從 $t=0, \Phi(0) = 0$ 開始爬行，它將會在 $t=T, \Phi(T)=1$ 時刻到達了另一端。由於

$\frac{d\Phi}{dt} = \frac{d}{dt} \left[ {(c + v t)}^{-1} \cdot x(t) \right]$
$= {(c + v t)}^{-1} \cdot \frac{dx(t)}{dt} - {(c + v t)}^{-2} \cdot v x(t)$
$= {(c + v t)}^{-1} \cdot \left[ \alpha + {(c + v t)}^{-1} \cdot v x(t) \right] - {(c + v t)}^{-2} \cdot v x(t)$
$= \frac{\alpha}{c + v t}$ ，因此我們就可以得到

$\Phi(t)=\int{\frac{\alpha}{c+vt}\,dt}=\frac{\alpha}{v}\log(c+vt)+\kappa$

此處 $\kappa$ 積分常數。從 $\Phi(0)=0$ ，可以得到 $\kappa=-\frac{\alpha}{v}\log{c}$ ，所以 $\Phi(t)=\frac{\alpha}{v}\log{\left(\frac{c+vt}{c}\right)}$ 。再從 $\Phi(T)=1$ ，就得到了 $T=\frac{c}{v}\left(e^{v/\alpha}-1\right)$ 。

假使將 $c = 1 km, v = 1 km/sec, \alpha = 1 cm/sec$ 代入後，求得 $T=(e^{100,000}-1) \ \mathrm{s}\ \approx2.8\times10^{43,429}\,\mathrm{s}$ ，這隻小螞蟻果真到的了彼端，雖然它得經過千千萬萬個三千大劫的吧！！

那麼為什麼︰某點 $X$ 的伸長速度會是 $\frac{X}{c + v t} v$ 的呢？假使考慮一根『有刻度』 $p_i, i = 0 \cdots n$ 的尺，它的一端固定，另一端向外延伸，這樣每個『刻度點』也都相對的向外伸長 ${\delta}_i$ ，於是『固定端』 ${\delta}_0 =0$ ，『第一個刻度』在 $p_1 + {\delta}_1$ 的位置，『第二個刻度』在 $p_2 + {\delta}_1+ {\delta}_2$ 的位置，這樣『第 $k$ 個刻度』將在 $p_k + \sum \limits_{j=1}^{j=k} {\delta}_j$ 的位置。假設『橡膠繩』的『彈性』是『均勻』的，這樣所有的 ${\delta}_i = \delta x$ 都相等，因此 $p_k + \sum \limits_{j=1}^{j=k} {\delta}_j = p_k + k \delta x$ ，如此當『另一端』用『定速』 $v$ 移動時，此時 $n \delta x = v \delta t$ ，於是『第 $k$ 個刻度』就用 $\frac{k}{n} v$ 的速度在移動的啊！

─── 《【Sonic π】電路學之補充《四》無窮小算術‧中下中‧中》

觀蟻感悟天○︰

Ant colony optimization algorithms

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis,^[1]^[2] the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. From a broader perspective, ACO performs a model-based search ^[3] and share some similarities with Estimation of Distribution Algorithms.

Ant behavior was the inspiration for the metaheuristic optimization technique

Overview

In the natural world, ants of some species (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but instead to follow the trail, returning and reinforcing it if they eventually find food (see Ant communication).

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over more frequently, and thus the pheromone density becomes higher on shorter paths than longer ones. Pheromone evaporation also has the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained. The influence of pheromone evaporation in real ant systems is unclear, but it is very important in artificial systems.^[4]

The overall result is that when one ant finds a good (i.e., short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads to all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve.

Example pseudo-code and formula

  procedure ACO_MetaHeuristic
    while(not_termination)
       generateSolutions()
       daemonActions()
       pheromoneUpdate()
    end while
  end procedure

ant-colony-optimization

Implementation of the Ant Colony Optimization algorithm (python)

Usage:

import ant_colony

//given some nodes, and some locations...
test_nodes = {0: (0, 7), 1: (3, 9), 2: (12, 4), 3: (14, 11), 4: (8, 11)
    5: (15, 6), 6: (6, 15), 7: (15, 9), 8: (12, 10), 9: (10, 7)}

//...and a function to get distance between nodes...
def distance(start, end):
    x_distance = abs(start[0] - end[0])
    y_distance = abs(start[1] - end[1])

    //c = sqrt(a^2 + b^2)
    import math
    return math.sqrt(pow(x_distance, 2) + pow(y_distance, 2))

//...we can make a colony of ants...
colony = ant_colony(test_nodes, distance)

//...that will find the optimal solution with ACO
answer = colony.mainloop()

於是能放下包袱，自然惜時精進︰

背包問題

假使有 $n$ 種物品，物品 $k$ 的重量是 $w_k$ ，價格為 $p_k$ 。如果我們有個背包，最大能載重 $W$ ，要是各種物品只能選或者不選，那麼『最高價』的裝法是什麼？數學上來講，就是在『滿足』
$\qquad \sum_{k=1}^n w_k\,x_k \ \leqslant \ W, \quad \quad x_k \ \in \ \{0,1\}$ 的『條件』下，求
$\qquad \sum_{k=1}^n p_k\,x_k$ 之『最大化』的問題。