File size: 6,226 Bytes
2facf1f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 | # EVOLVE-BLOCK-START
"""Optimized solver for the AC inequality task using Lp gradient descent."""
import time
import numpy as np
from scipy.signal import fftconvolve
def evaluate_sequence(sequence: list[float]) -> float:
if not isinstance(sequence, list):
return float(np.inf)
if not sequence:
return float(np.inf)
clean: list[float] = []
for x in sequence:
if isinstance(x, bool) or not isinstance(x, (int, float)):
return float(np.inf)
if np.isnan(x) or np.isinf(x):
return float(np.inf)
clean.append(float(x))
clean = [max(0.0, min(1000.0, x)) for x in clean]
n = len(clean)
conv = np.convolve(clean, clean)
max_b = float(np.max(conv))
sum_a = float(np.sum(clean))
if sum_a < 0.01:
return float(np.inf)
return float(2.0 * n * max_b / (sum_a**2))
def run(seed: int = 42, budget_s: float = 10.0, **kwargs) -> list[float]:
del kwargs
rng = np.random.default_rng(seed)
start = time.time()
deadline = start + budget_s * 0.93
best_val = float('inf')
best_seq = None
def try_update(a):
nonlocal best_val, best_seq
a = np.clip(a, 0.0, 1000.0)
val = evaluate_sequence(a.tolist())
if val < best_val:
best_val = val
best_seq = a.copy()
return val
def fast_obj(a):
conv = fftconvolve(a, a)
s = np.sum(a)
if s < 1e-10:
return float('inf')
return 2.0 * len(a) * np.max(conv) / s**2
def lp_gradient_descent(a, time_limit, p_start=4, p_end=32):
"""Projected Lp gradient descent on the convolution peak."""
n = len(a)
a = np.maximum(a, 1e-12).astype(np.float64)
target_sum = np.sum(a)
best_a = a.copy()
best_obj = fast_obj(a)
lr = 0.01
no_improve = 0
t_start = time.time()
t_end = t_start + time_limit
step = 0
while time.time() < t_end:
step += 1
# Adaptive p
progress = min(1.0, step / 2000.0)
p = p_start + (p_end - p_start) * progress
# Compute convolution
conv = fftconvolve(a, a)
conv = np.maximum(conv, 0) # numerical safety
# Lp weights
conv_max = np.max(conv)
if conv_max < 1e-20:
break
# Normalized weights for numerical stability
w = (conv / conv_max) ** (p - 1)
# Gradient: correlate(w, a) gives grad[i] = sum_k w[k]*a[k-i]
a_rev = a[::-1]
grad = fftconvolve(w, a_rev, mode='valid')
if len(grad) != n:
# Adjust if sizes don't match perfectly
grad = grad[:n] if len(grad) > n else np.pad(grad, (0, n - len(grad)))
# Project: remove mean to preserve sum
grad -= np.mean(grad)
# Normalize gradient
gnorm = np.linalg.norm(grad)
if gnorm < 1e-20:
break
grad = grad / gnorm
# Line search with backtracking
step_size = lr
improved = False
for _ in range(5):
a_new = a - step_size * grad * np.sqrt(n)
a_new = np.maximum(a_new, 1e-12)
a_new = a_new / np.sum(a_new) * target_sum
new_obj = fast_obj(a_new)
if new_obj < best_obj:
a = a_new
best_a = a.copy()
best_obj = new_obj
lr = step_size * 1.05
improved = True
no_improve = 0
break
step_size *= 0.5
if not improved:
no_improve += 1
lr *= 0.8
if no_improve > 50:
# Restart with perturbation
a = best_a + rng.normal(0, 0.01 * np.mean(best_a), n)
a = np.maximum(a, 1e-12)
a = a / np.sum(a) * target_sum
lr = 0.01
no_improve = 0
return best_a, best_obj
# Phase 1: Quick evaluation of many starting points
candidates = []
for n in [500, 1000, 2000, 4000]:
j = np.arange(n, dtype=np.float64)
# Best analytical: c + exp(beta * j/n)
for beta in [3.0, 4.0, 5.0, 6.0, 8.0]:
exp_part = np.exp(beta * j / n)
for c_ratio in [0.1, 0.3, 0.5, 0.8, 1.0, 2.0]:
c = c_ratio * np.max(exp_part) / beta
a = c + exp_part
candidates.append(a.copy())
# Exponential only
for beta in [0.8, 1.0, 1.2, 1.5, 2.0]:
a = np.exp(beta * j / n)
candidates.append(a.copy())
# Evaluate all candidates quickly
scored = []
for a in candidates:
val = fast_obj(a)
scored.append((val, a))
scored.sort(key=lambda x: x[0])
# Phase 2: Optimize top candidates
num_to_optimize = min(8, len(scored))
time_per = max(0.3, (deadline - time.time() - 2.0) / num_to_optimize)
for i in range(num_to_optimize):
if time.time() > deadline - 2:
break
val_init, a_init = scored[i]
a_opt, val_opt = lp_gradient_descent(a_init.copy(), time_per)
try_update(a_opt)
# Phase 3: Final refinement of best solution
remaining = deadline - time.time()
if remaining > 1.0 and best_seq is not None:
# Try also changing length (upsample/downsample)
a = best_seq.copy()
for factor in [0.5, 0.75, 1.5, 2.0]:
new_n = max(100, int(len(a) * factor))
a_resized = np.interp(np.linspace(0, 1, new_n), np.linspace(0, 1, len(a)), a)
a_opt, val = lp_gradient_descent(a_resized, min(0.5, remaining / 6))
try_update(a_opt)
if time.time() > deadline - 1:
break
remaining = deadline - time.time()
if remaining > 0.5:
a_opt, val = lp_gradient_descent(best_seq.copy(), remaining - 0.3, p_start=16, p_end=64)
try_update(a_opt)
return [float(x) for x in best_seq.tolist()]
# EVOLVE-BLOCK-END
|