Iterated local search
ઇટરેટેડ લોકલ સર્ચ (આઇ. એલ. એસ.) એ લાગુ કરેલ ગણિત અને કોમ્પ્યુટર વિજ્ઞાનમાં એક શબ્દ છે જે અલગ ઓપ્ટિમાઇઝેશન સમસ્યાઓ ઉકેલવા માટે સ્થાનિક શોધ અથવા હિલ ક્લાઇમ્બિંગ પદ્ધતિઓમાં ફેરફારને વ્યાખ્યાયિત કરે છે. સ્થાનિક શોધ પદ્ધતિઓ સ્થાનિક લઘુત્તમમાં અટવાઇ શકે છે, જ્યાં કોઈ સુધારાત્મક પડોશીઓ ઉપલબ્ધ નથી. એક સરળ ફેરફારમાં સ્થાનિક શોધ દિનચર્યામાં કૉલ્સને પુનરાવર્તિત કરવાનો સમાવેશ થાય છે, દરેક વખતે અલગ પ્રારંભિક રૂપરેખાંકનથી શરૂ થાય છે. આને પુનરાવર્તિત સ્થાનિક શોધ કહેવામાં આવે છે, અને તે સૂચવે છે કે અગાઉના સ્થાનિક શોધ તબક્કાઓ દરમિયાન મેળવેલ જ્ઞાનનો ઉપયોગ થતો નથી. શિક્ષણ સૂચવે છે કે અગાઉનો ઇતિહાસ, ઉદાહરણ તરીકે અગાઉ મળેલા સ્થાનિક મિનિમા વિશેની યાદશક્તિ, સ્થાનિક શોધ માટે વધુ સારા અને વધુ સારા પ્રારંભિક બિંદુઓ ઉત્પન્ન કરવા માટે ખોદવામાં આવે છે. સ્થાનિક મિનિમાના સમૂહબદ્ધ વિતરણની ગર્ભિત ધારણા છેઃ જ્યારે કાર્યને ન્યૂનતમ કરવામાં આવે છે, ત્યારે સ્થાનિક લઘુત્તમથી ઓછા મૂલ્ય સાથે શરૂ કરતી વખતે સારા સ્થાનિક મિનિમાનું નિર્ધારણ કરવું સરળ હોય છે, જ્યારે તે અવ્યવસ્થિત બિંદુથી શરૂ થાય છે. એકમાત્ર ચેતવણી એ છે કે આપેલ આકર્ષણ બેસિનમાં કેદ ટાળવી, જેથી સ્થાનિક મિનિમાઇઝરને આગામી દોડ માટે પ્રારંભિક બિંદુમાં રૂપાંતરિત કરવાની કિક યોગ્ય રીતે મજબૂત હોવી જોઈએ, પરંતુ મેમરી-ઓછી રેન્ડમ પુનઃપ્રારંભમાં પાછા ફરવાનું ટાળવા માટે ખૂબ મજબૂત ન હોવી જોઈએ. પુનરાવર્તિત સ્થાનિક શોધ સ્થાનિક રીતે શ્રેષ્ઠ ઉકેલોનો ક્રમ બનાવવા પર આધારિત છેઃ વર્તમાન સ્થાનિક લઘુત્તમમાં ખલેલ પહોંચાડવી; સુધારેલા ઉકેલથી શરૂ કર્યા પછી સ્થાનિક શોધ લાગુ કરવી. વિક્ષેપની તાકાત એક અલગ સ્થાનિક મહત્તમ તરફ દોરી જતા એક અલગ આકર્ષણ તટપ્રદેશ તરફ દોરી જવા માટે પૂરતી હોવી જોઈએ. પેર્ટર્બેશન અલ્ગોરિધમ આઈ. એલ. એસ. માટે પેર્ટર્બેશન અલ્ગોરિધમ શોધવું એ સરળ કાર્ય નથી. મુખ્ય ઉદ્દેશ એ જ સ્થાનિક લઘુત્તમ પર અટવાઇ ન જવાનો છે અને આ મિલકતની ખાતરી કરવા માટે, પૂર્વવત્ કામગીરી પ્રતિબંધિત છે. આમ છતાં, સારા ક્રમચયને ઘણા બધા મૂલ્યો ધ્યાનમાં લેવા પડે છે, કારણ કે ત્યાં બે પ્રકારના ખરાબ ક્રમચયો અસ્તિત્વ ધરાવે છેઃ ખૂબ નબળાઃ સમાન સ્થાનિક લઘુત્તમ ખૂબ મજબૂત પર પાછા ફરોઃ રેન્ડમ રીસ્ટાર્ટ બેન્ચમાર્ક પર્ટર્બેશન આ પ્રક્રિયામાં વિક્ષેપ માટે સંખ્યાબંધ મૂલ્યો નક્કી કરવામાં આવે છે જેથી આ મૂલ્યો ઉદાહરણ તરીકે નોંધપાત્ર હોયઃ સરેરાશ સંભાવના પર અને દુર્લભ નહીં. તે પછી, રનટાઇમ પર પાસ થયેલા ઉદાહરણો પર સરેરાશ વિચાર મેળવવા માટે બેન્ચમાર્ક પ્લોટને તપાસવું શક્ય બનશે. અનુકૂલનશીલ વિક્ષેપ કારણ કે ત્યાં કોઈ પ્રાથમિક કાર્ય નથી જે જણાવે છે કે આપેલ વિક્ષેપ માટે કયું સૌથી યોગ્ય મૂલ્ય છે, તેને અનુકૂલનશીલ બનાવવું એ શ્રેષ્ઠ માપદંડ છે. દાખલા તરીકે બટ્ટીતી અને પ્રોતાસીએ મેક્સ-સેટ માટે પ્રતિક્રિયાશીલ શોધ અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો જે આઇએલએસ માળખામાં સંપૂર્ણપણે બંધબેસે છે. તેઓ "નિર્દેશિત" વિક્ષેપ યોજના કરે છે જે તબુ શોધ અલ્ગોરિધમ દ્વારા લાગુ કરવામાં આવે છે અને દરેક વિક્ષેપ પછી તેઓ પ્રમાણભૂત સ્થાનિક વંશના અલ્ગોરિધમનો લાગુ કરે છે. વિક્ષેપને અનુકૂળ થવાની બીજી રીત એ છે કે શોધ દરમિયાન તેની તાકાતને નિર્ધારિત રીતે બદલવી. અવ્યવસ્થાને અનુકૂળ બનાવવી બીજી પ્રક્રિયા એ છે કે સમસ્યાના પેટા ભાગને અનુકૂળ બનાવવી જ્યારે બિન-નિષ્ક્રિય મિલકતને સક્રિય રાખવી. જો આ પ્રક્રિયા શક્ય હોય, તો વિક્ષેપ પછી પેદા થતા તમામ ઉકેલો ખૂબ સારા હોય છે. વધુમાં નવા ભાગો પણ ઓપ્ટિમાઇઝ કરવામાં આવ્યા છે. આ પદ્ધતિ જોબ શોપ શેડ્યુલિંગ સમસ્યાઓ, ફ્લો-શોપ સમસ્યાઓ, વાહન રૂટીંગ સમસ્યાઓ તેમજ અન્ય ઘણી બધી સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓ પર લાગુ કરવામાં આવી છે. સંદર્ભો ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ