Algoritma sireum

Ti Wikipédia, énsiklopédia bébas
Luncat ka: pituduh, sungsi

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

Sawangan[édit | sunting 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 pendekatan penguatan 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.


Nulis.jpg