Tabu-förstärkt Simulerad Bifurkation för kombinatorisk optimering

Varför smartare sökande spelar roll

Från att planera rutter för leveransfordon till att para ihop partiklar i en kolliderare—många av dagens svåraste beräkningsuppgifter kokar ner till en utmaning: att hitta det bästa valet bland ett häpnadsväckande antal möjligheter. Dessa så kallade kombinatoriska problem driver logistik, finans, biologi och teknik, men de är så komplexa att även superdatorer kan få svårt. Denna artikel presenterar en ny algoritmisk vinkel, kallad Tabu-förstärkt Simulerad Bifurkation (TESB), som hjälper datorer att undvika att fastna i återvändsgränder och nå bättre svar mycket snabbare.

Svåra val i ett landskap av möjligheter

Forskare föreställer sig ofta kombinatoriska problem som ett skrovligt landskap fullt av kullar och dalar. Varje punkt i detta landskap representerar en möjlig lösning, och höjden motsvarar dess ”energi” eller kostnad; låga dalar är bra lösningar, och den djupaste dalen är den bästa. Många verkliga uppgifter, som att dela en nätverk i två välavskilda delar (Max‑Cut‑problemet) eller att återskapa partikelspår i en detektor, kan översättas till ett sådant energilandskap med en matematisk modell känd som Ising‑modellen. Fångsten är att dessa landskap har astronomiskt många dalar, så en sökprocedur kan lätt slå sig ner i enbart en hygglig grop och aldrig upptäcka att en mycket djupare finns någon annanstans.

Från kvantidéer till klassisk snabbhet

Simulerad Bifurkation (SB) är en relativt ny, fysikinspirerad metod för att utforska dessa skrovliga landskap. Istället för att hoppa från en diskret lösning till en annan föreställer sig SB ett system av partiklar som rör sig i en slät version av landskapet, styrt av ekvationer liknande de i klassisk mekanik. När en styrparameter långsamt ändras, ”bifurkerar” systemet och partiklarnas positioner lutar mot lågenergidalar som kodar bra lösningar. SB har redan visat goda prestanda på stora problem och körs effektivt på grafikprocessorer, men det delar en svaghet med många sökmetoder: det kan bli fångat i lokala minima, särskilt i oregelbundna, tätt sammanlänkade problem där vissa regioner av landskapet är mycket mer trassliga än andra.

Lägga minne till för att undvika gamla fällor

Huvudidén bakom TESB är att ge SB en form av korttidsminne, inspirerad av en välkänd strategi inom optimering kallad tabu‑sökning. I tabu‑sökning håller algoritmen en lista över nyligen undersökta dåliga lösningar och förbjuder tillfälligt drag som skulle återvända till dem. TESB översätter detta koncept till bilden av energilandskapet. Först använder en ”uppvärmnings”-fas den ursprungliga SB‑algoritmen för att snabbt generera många approximativa lösningar. Dessa motsvarar lokala dalar där systemet tenderar att fastna. Därefter modifierar TESB landskapet genom att lägga till ett milt straff runt dessa regioner, vilket i praktiken höjer golvet i dessa dalar. Under den efterföljande ”kontroll”-fasen utvecklas systemet igen i detta omformade landskap, nu uppmuntrat att kringgå de gamla fällorna och söka sig mot djupare, tidigare oupptäckta dalar.

Hålla sökningen livlig med små knuffar

En praktisk utmaning är hur man använder detta minne utan att överdriva. Om TESB straffade varje tidigare dal lika mycket och permanent, skulle det kunna jämna ut landskapet så mycket att användbar vägledning försvinner. För att undvika detta lånar metoden en annan idé från modern maskininlärning: mini‑batches. Vid varje steg i kontrollfasen väljer TESB slumpmässigt endast en liten delmängd av de lagrade suboptimala lösningarna för att bidra till straffet. Detta får landskapet att skifta precis tillräckligt för att driva systemet bort från vältrampade områden, samtidigt som den övergripande strukturen och sökdiversiteten bevaras. Numeriska tester visar att denna strategi gör att TESB fortsätter förbättras långt efter att den ursprungliga SB‑dynamiken i praktiken har stannat av.

Sätta metoden på prov

Författarna benchmarkade TESB på standardtestgrafer för Max‑Cut och på krävande problem från högenergifysik, där återskapandet av laddade partikels banor är både avgörande och beräkningsintensivt. På Max‑Cut‑benchmarks når TESB ofta optimala eller nära‑optimala snitt mycket mer pålitligt än de ursprungliga SB‑varianterna. Mätt i ”tid till lösning” — hur lång tid det i genomsnitt tar att uppnå en målkvalitetslösning — kan TESB vara upp till tusen gånger snabbare på de mest utmanande instanserna. I uppgifter för partikelspårsrekonstruktion som involverar mer än hundratusen variabler hittar TESB konsekvent konfigurationer med lägre energi (vilket betyder bättre anpassning till data) samtidigt som det använder mindre beräkningstid än referensmetoderna, vilket framhäver dess skalbarhet till verkliga, mycket stora system.

Vad detta betyder framöver

Enkelt uttryckt förvandlar TESB en snabb men ibland kortsynt sökare till en mer strategisk upptäckare som minns var den varit och lär sig undvika dåliga grannskap. Genom att omforma energilandskapet kring tidigare misstag istället för att börja om från början ökar chansen avsevärt att nå högkvalitativa lösningar på rimlig tid. Denna blandning av fysikinspirerad dynamik med klassiska tabu‑idéer antyder en bredare väg framåt: många okonventionella optimeringsmotorer, vare sig klassiska eller kvantinspirerade, skulle kunna få ett liknande uppsving genom att införliva smarta, historiekänsliga straff. För tillämpningar som är beroende av att lösa allt större och svårare kombinatoriska pussel erbjuder TESB ett lovande nytt verktyg för att pressa igenom tidigare prestandagränser.

Citering: Tao, XZ., Zeng, QG., Huang, ZJ. et al. Tabu-Enhanced Simulated Bifurcation for combinatorial optimization. Commun Phys 9, 100 (2026). https://doi.org/10.1038/s42005-026-02538-2

Nyckelord: kombinatorisk optimering, simulerad bifurkation, tabu-sökning, Max-Cut, partikelspårsrekonstruktion