17:
130:
The procedure consists in fixing a number of values for the perturbation such that these values are significant for the instance: on average probability and not rare. After that, on runtime it will be possible to check the benchmark plot in order to get an average idea on the instances passed.
113:
Finding the perturbation algorithm for ILS is not an easy task. The main aim is not to get stuck at the same local minimum and in order to ensure this property, the undo operation is forbidden. Despite this, a good permutation has to consider a lot of values, since there exist two kind of bad
69:, and implies that the knowledge obtained during the previous local search phases is not used. Learning implies that the previous history, for example the memory about the previously found local minima, is mined to produce better and better starting points for local search.
159:
Another procedure is to optimize a sub-part of the problem while keeping the not-undo property active. If this procedure is possible, all solutions generated after the perturbations tend to be very good. Furthermore the
143:
that tells which one is the most suitable value for a given perturbation, the best criterion is to get it adaptive. For instance
Battiti and Protasi proposed a reactive search algorithm for
151:
algorithm and after each perturbation they apply a standard local descent algorithm. Another way of adapting the perturbation is to change deterministically its strength during the search.
87:
to transform a local minimizer into the starting point for the next run has to be appropriately strong, but not too strong to avoid reverting to memory-less random restarts.
484:
431:
Penna, Puca H.V.; Satori Ochi, L.; Subramanian, A. (2013). "An
Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem".
330:
Lourenço, H.R.; Zwijnenburg M. (1996). "Combining the Large-Step
Optimization with Tabu-Search: Application to the Job-Shop Scheduling Problem".
230:
83:
with a low value than when starting from a random point. The only caveat is to avoid confinement in a given attraction basin, so that the
207:. Kluwer Academic Publishers, International Series in Operations Research & Management Science. Vol. 146. pp. 363–397.
349:
331:
202:
101:
The perturbation strength has to be sufficient to lead the trajectory to a different attraction basin leading to a different
414:"Using Iterated Local Search for solving the Flow-Shop Problem: parametrization, randomization and parallelization issues"
385:
Lourenço, H.R. (1995). "Job-Shop
Scheduling: computational study of local search and large-step optimization methods".
44:
147:
which fits perfectly into the ILS framework. They perform a "directed" perturbation scheme which is implemented by a
173:
65:
calls to the local search routine, each time starting from a different initial configuration. This is called
181:
208:
274:. Kluwer Academic Publishers, International Series in Operations Research & Management Science.
213:
201:
Lourenço, H.R.; Martin O.; Stützle T. (2010). "Iterated Local Search: Framework and
Applications".
177:
36:
465:
359:
240:
413:
345:
312:
267:
226:
80:
440:
394:
337:
302:
218:
40:
79:: when minimizing a function, determining good local minima is easier when starting from a
371:
252:
90:
Iterated Local Search is based on building a sequence of locally optimal solutions by:
16:
478:
398:
102:
75:
55:
48:
341:
222:
148:
444:
316:
307:
290:
144:
412:
Juan, A.A.; Lourenço, H.; Mateo, M.; Luo, R.; Castella, Q. (2013).
15:
97:
applying local search after starting from the modified solution.
466:"Roberto Cordone - Corsi - Algoritmi euristici (A.A. 2016/17)"
291:"Reactive search, a history-sensitive heuristic for MAX-SAT"
336:. Kluwer Academic Publishers. Springer. pp. 219–236.
51:
methods for solving discrete optimization problems.
418:International Transactions in Operational Research
289:Battiti, Roberto; Protasi, Marco (1997-01-01).
266:Lourenço, H.R.; Martin O.; Stützle T. (2003).
58:, where no improving neighbors are available.
118:too weak: fall back to the same local minimum
8:
306:
212:
387:European Journal of Operational Research
295:ACM Journal of Experimental Algorithmics
54:Local search methods can get stuck in a
457:
193:
172:The method has been applied to several
367:
357:
248:
238:
94:perturbing the current local minimum;
72:The implicit assumption is that of a
7:
485:Optimization algorithms and methods
24:a solution out from a local optimum
61:A simple modification consists of
14:
180:problems, Flow-Shop Problems,
1:
399:10.1016/0377-2217(95)00012-F
342:10.1007/978-1-4613-1361-8_14
223:10.1007/978-1-4419-1665-5_12
139:Since there is no function
43:defining a modification of
501:
272:Handbook of Metaheuristics
204:Handbook of Metaheuristics
174:combinatorial optimization
121:too strong: random restart
74:clustered distribution of
445:10.1007/s10732-011-9186-y
164:parts are optimized too.
184:as well as many others.
182:Vehicle Routing Problems
268:"Iterated Local Search"
176:problems including the
155:Optimizing Perturbation
126:Benchmark Perturbation
109:Perturbation Algorithm
25:
20:Iterated local search
433:Journal of Heuristics
308:10.1145/264216.264220
135:Adaptive Perturbation
67:repeated local search
29:Iterated Local Search
19:
178:Job Shop Scheduling
37:applied mathematics
26:
232:978-1-4419-1663-1
492:
470:
469:
462:
449:
448:
428:
422:
421:
409:
403:
402:
382:
376:
375:
369:
365:
363:
355:
327:
321:
320:
310:
286:
280:
279:
263:
257:
256:
250:
246:
244:
236:
216:
198:
41:computer science
500:
499:
495:
494:
493:
491:
490:
489:
475:
474:
473:
464:
463:
459:
453:
452:
430:
429:
425:
411:
410:
406:
384:
383:
379:
366:
356:
352:
333:Meta-Heuristics
329:
328:
324:
288:
287:
283:
265:
264:
260:
247:
237:
233:
214:10.1.1.187.2089
200:
199:
195:
190:
170:
157:
137:
128:
111:
35:) is a term in
12:
11:
5:
498:
496:
488:
487:
477:
476:
472:
471:
456:
451:
450:
439:(2): 201–232.
423:
404:
393:(2): 347–364.
377:
368:|journal=
350:
322:
281:
258:
249:|journal=
231:
192:
191:
189:
186:
169:
166:
156:
153:
136:
133:
127:
124:
123:
122:
119:
114:permutations:
110:
107:
99:
98:
95:
13:
10:
9:
6:
4:
3:
2:
497:
486:
483:
482:
480:
467:
461:
458:
455:
446:
442:
438:
434:
427:
424:
419:
415:
408:
405:
400:
396:
392:
388:
381:
378:
373:
361:
353:
351:9780792397007
347:
343:
339:
335:
334:
326:
323:
318:
314:
309:
304:
300:
296:
292:
285:
282:
277:
273:
269:
262:
259:
254:
242:
234:
228:
224:
220:
215:
210:
206:
205:
197:
194:
187:
185:
183:
179:
175:
167:
165:
163:
154:
152:
150:
146:
142:
134:
132:
125:
120:
117:
116:
115:
108:
106:
104:
103:local optimum
96:
93:
92:
91:
88:
86:
82:
81:local minimum
78:
77:
70:
68:
64:
59:
57:
56:local minimum
52:
50:
49:hill climbing
46:
42:
38:
34:
30:
23:
18:
460:
454:
436:
432:
426:
417:
407:
390:
386:
380:
332:
325:
298:
294:
284:
275:
271:
261:
203:
196:
171:
168:Applications
161:
158:
140:
138:
129:
112:
100:
89:
84:
76:local minima
73:
71:
66:
62:
60:
53:
45:local search
32:
28:
27:
21:
149:tabu search
278:: 321–353.
188:References
370:ignored (
360:cite book
317:1084-6654
251:ignored (
241:cite book
209:CiteSeerX
63:iterating
479:Category
301:: 2–es.
141:a priori
145:MAX-SAT
348:
315:
229:
211:
22:kicks
372:help
346:ISBN
313:ISSN
253:help
227:ISBN
85:kick
39:and
441:doi
395:doi
338:doi
303:doi
219:doi
162:new
47:or
33:ILS
481::
437:19
435:.
416:.
391:83
389:.
364::
362:}}
358:{{
344:.
311:.
297:.
293:.
276:57
270:.
245::
243:}}
239:{{
225:.
217:.
105:.
468:.
447:.
443::
420:.
401:.
397::
374:)
354:.
340::
319:.
305::
299:2
255:)
235:.
221::
31:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
