SOURCE-ALIGNED TUTORIAL · STEP-BY-STEP SNAPSHOTS

ROSE
ทีละขั้น

ติดตามหนึ่ง generation ตั้งแต่ population ดิบ การเลือก elite การสร้างสถิติ relative order การสุ่มตำแหน่งทีละสมาชิก ไปจนถึงคำตอบรุ่นใหม่ พร้อม snapshot ตัวเลขที่ตรวจสอบย้อนกลับกับ Python implementation ได้

01 · GENERATION LOOP

ROSE เรียนอะไรในหนึ่งรอบ

ประเมิน

ส่ง permutation ทุกตัวเข้า evaluator เดียวกัน ได้ fitness หนึ่งค่าหรือ Pareto selection score

เลือก

เรียงตามทิศทางของ objective แล้วเก็บ elite ตาม selection ratio

ประมาณค่า

แปลง elite เป็น inverse positions แล้วคำนวณ exact-position และ signed-distance statistics

สุ่ม

สุ่ม item และ locus ที่ยังว่าง โดยผสมหลักฐาน node กับ relative order

ทำซ้ำ

ประเมิน population ใหม่ เก็บ diagnostics และเรียน estimator รอบถัดไป

หน่วยของเวลา: การเปรียบเทียบที่ยุติธรรมควรใช้จำนวน objective evaluations ไม่ใช่จำนวน generation เพียงอย่างเดียว เพราะ population ต่างกันทำให้ต้นทุนต่อ generation ต่างกัน

02 · SELECTION SNAPSHOT

เริ่มจาก population ที่มองเห็นได้

ตัวอย่าง minimization ขนาด n=6, population=5 และ selection ratio=40% จึงเลือก max(1, round(5×0.40)) = 2 ตัวแรกหลังเรียง fitness

P0 · f=18[1, 4, 0, 3, 5, 2]

P1 · f=11 · ELITE[1, 3, 5, 0, 4, 2]

P2 · f=15[3, 1, 0, 5, 2, 4]

P3 · f=9 · ELITE[1, 5, 3, 0, 2, 4]

P4 · f=21[4, 0, 2, 1, 5, 3]

order = argsort(fitness)                  # minimization
k = max(1, round(population × ratio/100))
selected = population[order[:k]]         # P3, P1

Minimization

argsort(fitness) น้อยไปมาก

Maximization

argsort(fitness)[::-1] มากไปน้อย

03 · FIT SNAPSHOT

จาก permutation เป็นเมทริกซ์สถิติ

3.1 กลับมุมมองเป็นตำแหน่งของ item

permutation ตอบว่า “ตำแหน่ง p มี item ใด” แต่ estimator ต้องถามกลับว่า “item j อยู่ตำแหน่งใด” จึงสร้าง inverse array หนึ่งครั้ง แล้วอ่านทุกคู่ได้ O(1)

Elite	Permutation	pos[0..5]
P3	`1 5 3 0 2 4`	`3 0 4 2 5 1`
P1	`1 3 5 0 4 2`	`3 0 5 1 4 2`

positions[row, item] = locus

P3: pos(1)=0, pos(3)=2
P1: pos(1)=0, pos(3)=1

Δ(1,3) = pos(3)-pos(1)
P3 → +2
P1 → +1

NODE / EXACT POSITION

N[j,p]

นับว่า item j ปรากฏที่ locus p กี่ครั้ง เติม smoothing α ทุกช่อง แล้ว normalize แต่ละแถวให้รวมเป็น 1

N[j,p] = (count(j at p)+α)/(k+nα)
α=1, k=2
item 1 observed at p=0 twice
N[1] = [3,1,1,1,1,1] / 8

RELATIVE ORDER

Δπ(i,j)

ระยะมีเครื่องหมาย: บวกหมายถึง j อยู่หลัง i, ลบหมายถึง j อยู่ก่อน i จึงเก็บทั้งทิศและระยะในค่าเดียว

Δπ(i,j)=posπ(j)-posπ(i)
M[i,j]=mean Δ
L[i,j]=min Δ
U[i,j]=max Δ
S[i,j]=population SD of Δ

Snapshot ของคู่ reference=1, target=3

observations+2, +1

count2

mean M1.5

min L1

max U2

SD S0.5

implementation ใช้ population standard deviation (หารด้วย k) ไม่ใช่ sample SD (หารด้วย k−1) และกำหนด diagonal i=j เป็น count=0 เพราะระยะศูนย์ไม่ให้ข้อมูล

04 · THREE ESTIMATORS

สามรุ่นเก็บและสุ่มไม่เหมือนกัน

ROSE · MULTI-REFERENCE

เฉลี่ยตำแหน่งที่หลาย reference ทำนาย

เลือก active roll จาก item ที่วางแล้ว ทุก reference i ทำนาย target_i = pos(i)+M[i,j] แล้วเฉลี่ย target ทั้งหมด ไม่สุ่ม Δ จากช่วง [L,U]

targets = [pos(i)+M[i,j]]
target = mean(targets)
scale = max(mean(S[i,j]),1)

SR-ROSE · COMPACT RANGE

เลือก reference เดียวแล้วสุ่มระยะ

เลือก reference แบบ uniform หรือ confidence=1/SD แล้วสุ่ม integer Δ จาก Normal(M,S) ที่ตัดให้อยู่ใน [L,U] และห้ามศูนย์

i ~ reference policy
Δ ~ TruncNormal(M[i,j],S[i,j],L,U)
target = pos(i)+Δ

SH-ROSE · HISTOGRAM

อ่าน probability ของระยะจริง

เก็บ H[i,j,d] จำนวน 2n−1 bins แล้วให้คะแนน free locus p จาก d=p−pos(i) จึงรักษา distribution หลายยอดได้ แต่ใช้หน่วยความจำ O(n³)

d = p-pos(i)
relative_score(p)=log H[i,j,d]
confidence(i)=1/entropy(H[i,j,:])

รุ่น	Reference	ข้อมูลระยะ	หน่วยความจำ	จุดแข็ง
ROSE	หลายตัวใน roll	M, S; average targets	O(n²)	ต้องการ consensus ที่นิ่ง
SR-ROSE	หนึ่งตัว	M, L, U, S; truncated draw	O(n²)	ต้องการ diversity โดยยัง compact
SH-ROSE	หนึ่งตัว	full empirical histogram	O(n³)	distribution มีหลายยอด

05 · SAMPLING SNAPSHOT

หนึ่ง item ถูกวางลงช่องว่างอย่างไร

สมมุติกำลังวาง item j=3, วาง reference i=1 ที่ locus 0 แล้ว และเหลือ free loci {1,2,4,5} จาก snapshot ก่อนหน้า SR-ROSE เรียน M=1.5, L=1, U=2, S=0.5

เลือก construction order

shuffle jobs ด้วย deterministic SplitMix64 seed เพื่อลดอคติจากเลข item

กำหนด active roll

all, fixed หรือ random 1..max_roll

สร้าง node score

node(p)=log(max(N[3,p],ε))

สร้าง relative score

ตัวอย่างสุ่มได้ Δ=2 จึง target=0+2=2

ผสมคะแนน

score=λ·node+(1−λ)·relative

Masked softmax

คำนวณเฉพาะ free loci; ช่องที่ใช้แล้วไม่มีสิทธิ์ถูกสุ่ม

Weighted choice

สะสม weight จนผ่าน random threshold แล้ว commit item ลง locus

อัปเดต state

เขียน result, pos(j), history และลบ locus ออกจาก free

ตัวอย่างการคำนวณλ=0.25 · temperature=1.0 · target=2 · scale=max(S,1)=1

free = [1, 2, 4, 5]

p	N[3,p]	node=log N	relative=−\|p−2\|/1	mixed score	softmax P
1	.125	−2.079	−1	−1.270	23.7%
2	.250	−1.386	0	−0.347	59.7%
4	.125	−2.079	−2	−2.020	11.2%
5	.125	−2.079	−3	−2.770	5.3%

ตัวเลข probability ปัดเพื่อการสอน; implementation ลบ max(score) ก่อน exp เพื่อป้องกัน overflow และ fallback เป็น uniform เมื่อ weight ไม่ finite หรือผลรวมไม่เป็นบวก

Truncated-normal fallback ของ SR-ROSE

ใช้ Box–Muller สร้าง normal draw ปัดเป็น integer และยอมรับเมื่ออยู่ใน [L,U] และไม่เป็นศูนย์ ทดลองสูงสุด 32 ครั้ง ถ้ายังไม่ได้จึงสุ่ม uniform จาก integer ที่ legal ในช่วง ไม่ใช่ขยายช่วงเอง

repeat at most 32 times:
    z = BoxMuller(U₁,U₂)
    Δ = round(M + S·z)
    accept if L ≤ Δ ≤ U and Δ ≠ 0
fallback: uniform({L..U} \ {0})

06 · WITH TEMPLATE (WT)

เจาะบางตำแหน่ง แล้วสร้างเฉพาะส่วนที่หาย

PARENT

153024

↓ sample ratio 50%: ตำแหน่ง 1,3,5 ถูกเจาะ

PUNCHED TEMPLATE

1_3_2_

↓ free={1,3,5}, jobs={5,0,4}; fixed items ใช้เป็น reference ได้

CHILD

143520

Template ไม่ใช่ mutation ธรรมดา

ตำแหน่งที่คงไว้กำหนดทั้ง item ที่ถูก reserve และ reference context ส่วนช่องที่เจาะเท่านั้นที่ sampler ของ ROSE เติมกลับ

Replacement เป็นราย parent

child เทียบกับ parent ของตนเอง ถ้าไม่ดีกว่า จะคืน parent ก่อน fit generation ถัดไป จึงเป็น local elitism ที่ชัดเจน

survivor = child  if f(child) < f(parent)   # minimization
           parent otherwise

# strict improvement: equal fitness does not replace the parent

07 · UPDATE AND SNAPSHOT

snapshot หนึ่งรุ่นกลายเป็น prior ของรุ่นถัดไป

ยังไม่มี estimator

สร้าง random permutations ด้วย seed เดียวกันแล้วได้ reproducible initial population

G0 FIT

N₀, M₀, L₀, U₀, S₀

สถิติสร้างจาก elite ของ G0 เท่านั้น ไม่ใช่ population ทั้งหมด

G1 SAMPLE

ใช้ snapshot แบบ read-only

สร้าง offspring ทั้งรุ่นจาก estimator ชุดเดียว ทำให้ลำดับ candidate ไม่แอบเปลี่ยน model

G1 FIT

N₁, M₁, L₁, U₁, S₁

หลัง evaluate และ selection จึงแทน estimator พร้อมกันสำหรับ G2

สิ่งที่ควรเก็บใน experiment snapshot

seedgenerationevaluationsselected indicesbest / mean / worstexact-position entropyrelative SD meanduplicate ratefallback countsroll-size distributionreference frequencyWT improvement rate

08 · COMPLEXITY AND PARAMETERS

ต้นทุนและความหมายของทุก knob

Parameter	ทำหน้าที่	ผลเมื่อเพิ่ม
`selection_ratio`	สัดส่วน survivor ที่ใช้ fit	model นุ่มและหลากหลายขึ้น แต่อาจเรียนช้าลง
`smoothing α`	pseudocount ของ N และ H	ลด zero probability แต่เพิ่ม exploration
`node_weight λ`	น้ำหนัก exact-position เทียบ relative	พึ่ง locus frequency มากขึ้น
`temperature T`	หาร score ก่อน softmax	distribution แบนขึ้นและสุ่มมากขึ้น
`roll_mode / roll size`	จำนวน reference ล่าสุดที่พิจารณา	บริบทกว้างขึ้น แต่ consensus อาจเฉลี่ยสัญญาณขัดกัน
`template_sample_ratio`	เปอร์เซ็นต์ locus ที่เจาะและสร้างใหม่	ก้าวไกลจาก parent มากขึ้น

ROSE / SR-ROSE

O(n²) memory

เก็บ N, M, L, U, S และ count เป็น n×n ไม่มี tensor ต่อสมาชิก elite

SH-ROSE

O(n³) memory

เพิ่ม H ขนาด n×n×(2n−1) ทั้ง counts และ probabilities

การสร้างหนึ่ง permutation

≈ O(n²)

ทำ n commits และให้คะแนน free loci ที่ลดลงทีละหนึ่ง

Numba acceleration: ส่วน fit ที่วนทุก elite×pair ใช้ fixed-size NumPy arrays และ Numba kernel ส่วน sampling ยังต้องรักษา state ของ free loci, history และ deterministic RNG

09 · IMPLEMENTATION MAP

เอกสารนี้ผูกกับ class และไฟล์ใด

ชื่อเผยแพร่	Python class	หน้าที่หลัก	Source
ROSE / ROSE-WT	`ROSE` `TemplateROSE`	multi-reference mean + optional punched template	`models/rose.py`
SR-ROSE / SR-ROSE-WT	`ROSESingleRef` `TemplateROSESingleRef`	single-reference compact range sampling	`models/rose.py`
SH-ROSE / SH-ROSE-WT	`ROSESingleRefHistogram` `TemplateROSESingleRefHistogram`	single-reference empirical histogram	`models/rose_histogram.py`
ตัวประมาณแบบเร็ว	`fit_rose_estimators_numba`	สร้าง N, M, L, U, S, count จาก elite	`models/rose_numba.py`

Invariant ที่ทดสอบได้

ทุก offspring เป็น permutation ของ 0..n−1
N แต่ละแถวรวมเป็น 1
M[j,i] = −M[i,j]
L[j,i] = −U[i,j]
ผลซ้ำได้เมื่อ config และ seed เหมือนกัน

อย่าอ่านผลเกินกว่าที่ model บอก

M เป็นค่าเฉลี่ยของ elite ไม่ใช่ข้อบังคับ
[L,U] เป็นช่วงที่เคยพบ ไม่ใช่ confidence interval
SD ต่ำอาจเกิดจาก elite น้อย จึงต้องรายงาน count
fitness ที่ดีไม่ได้พิสูจน์ว่า estimator family ดีในทุก objective

GitHub repository ↗ROSE.md ↗rose.py ↗หน้าการสุ่มเชิงลึก →