Lompat ke isi

Algoritma sireum

Ti Wikipédia Sunda, énsiklopédi bébas

Algoritma sireum dikenalkeun ku Moyson jeung Manderick [MoMa88] anu saterusna dikembangkeun ku Marco Dorigo [CMD91,Dor92,DoSt04], mangrupa hiji téhnik probabilistik pikeun méréskeun masalah komputasi ku jalan manggihan jalur panghadéna maké grafik. Algoritma ieu ningali kana kalakuan sireum dina manggihan jalur ti kolonina nuju kana dahareun.

Sawangan

[édit | édit sumber]

Dina alam nyata, sireum nguriling kalayan acak, tur lamun pinanggih kadaharan, maranéhannana bakal balik ka kolonina bari jeung nandaan ku tapak féromon. Lamun sireum-sireum séjén manggihan éta jalur, maranéhannana moal nyungsi kadaharan kalayan acak deui, tapi bakal miturut éta tapak jeung bakal nguatkeunnana lamun dina ahirna maranéhannana ogé manggihan kadaharan.

Lamun diingkeun tapak feromon bakal nguap tur ngurangan kakuatan daya tarikna. Leuwih lila hiji sireum bulak balik ngaliwatan jalur eta, leuwih lila deui feromon nguap. Minangka babandingan, hiji jalur nu pondok bakal diliwatan ku barisan leuwih gancang, ku kituna feromon bakal tetep rapet sabab aya dina jalur sagancang nguapna. Nguapna feromon mibanda kauntungan keur nyegah konvergensi dina penyelesaian optimal sacara lokal. Lamun taya penguapan sama sakali, jalur nu dipilih ku sireum mimiti bakal narik sacara kaleuleuwihi ka sireum-sireum lian nu nuturkeunnana. Dina kasus kieu, eksplorasi ruang penyelesaian bakal kawates.

Ku alatan éta, nalika hiji sireum manggihan jalur anu alus (jalur anu pondok) ti koloni ka asal kadaharan, sireum séjénna baris miluan jalur kasebut, sarta ahirna kabéh sireum baris miluan hiji jalur tunggal. Ideu algoritma koloni sireum nyaéta pikeun nurutan laku-lampah ieu ngaliwatan 'sireum tiruan' nu leumpang dina sabudeureun grafik anu némbongkeun masalah anu kudu dipungkas.

Algoritma optimisasi koloni sireum geus dipaké pikeun ngahasilkeun jalan kaluar anu ngadeukeutan optimal dina masalah salesman anu ngalakonan lalampahan. Algoritma sireum leuwih nguntungkeun batan pamarekanpenguatan tiruan (simulaten annealing) sarta algoritma genetik nalika grafik aya kamungkinan robah sacara dinamis; algoritma koloni sireum bisa jalan sacara kontinyu sarta nyocogkeun jeung parobahan sacara waktu téla (real time). Hal ieu pikaresepeun dina routing raramat sarta sistem transportasi urban.