霍爾頓序列（Halton sequence）是一種基於確定性方法生成的低差異序列，常用於蒙特卡洛模擬等數值方法中，其微小偏差特性使其歸類於擬隨機序列。該算法通過兩個質數基數分別在(0,1)區間內生成坐標分量，例如基數2和3對應的X軸序列為1/2、1/4、3/4，Y軸序列為1/3、2/3、1/9，組合後形成多維空間分布點。Halton序列在高維空間中存在投影分布不均勻的問題，後續改進方法包括引入隨機化、置亂化技術，以提高數值積分和模擬的精度。該方法被套用於克隆選擇算法初始化種群、大跨橋樑構件可靠度分析中，以增強解空間搜尋效率。該序列由Halton於1960年提出，後續衍生出基於整數與無理數的廣義van der Corput序列構建版本，並首次針對無理數基底序列提出置亂算法。
基本介紹
- 中文名：霍爾頓序列
- 外文名：Halton squence
生成Halton 序列的基本思想是給定兩個質數 a 和 b，分別對應 X 軸和 Y 軸的基數。每個軸根據基數分別在（0，1）之間迂迴取值，迂迴的策略參考下面的示例以及實現代碼。
以a = 2 和 b = 3 為例，其隨機點選取過程如圖1所示：
其中：
x的取值順序為： 1⁄2,1⁄4,3⁄4,1⁄8,5⁄8,3⁄8,7⁄8,1⁄16,9⁄16
y的取值順序為： 1⁄3,2⁄3,1⁄9,4⁄9,7⁄9,2⁄9,5⁄9,8⁄9,1⁄27
按順序組成頂點T1-T8： (1⁄2,1⁄3), (1⁄4,2⁄3), (3⁄4,1⁄9), (1⁄8,4⁄9), (5⁄8,7⁄9), (3⁄8,2⁄9), (7⁄8,5⁄9), (1⁄16,8⁄9), (9⁄16,1⁄27).
Halton sequence的一個實現代碼如下：
// Class for generating the Halton low-discrepancy series for Quasi Monte Carlo integration.
class Halton {
double value, inv_base;
public :
void number(int i, int base) {
double f = inv_base = 1.0 / base;
value = 0.0;
while (i > 0) {
value += f * ( double )(i%base);
i /= base;
f *= inv_base;
}
}
void next() {
double r = 1.0 - value - 0.0000001;
if (inv_base<r) value += inv_base;
else {
double h = inv_base, hh;
do {hh = h; h *= inv_base;} while(h >=r);
value += hh + h - 1.0;
}
}
double get() { return value; }
};
