Neutral but a Winner! How Neutrality Helps Multiobjective Local Search Algorithms

详细信息    查看全文

• 作者：Aymeric Blot (16) (17)
  Hern谩n Aguirre (19)
  Clarisse Dhaenens (17) (18)
  Laetitia Jourdan (17) (18)
  Marie-El茅onore Marmion (17) (18)
  Kiyoshi Tanaka (19)
  
  16. ENS Rennes ; Ker Lann ; Universit茅 Rennes 1 ; Rennes ; France
  17. Inria Lille - Nord Europe ; DOLPHIN Project-team ; Lille ; France
  19. Faculty of Engineering ; Shinshu University ; Nagano ; Japan
  18. Universit茅 Lille 1 ; LIFL ; UMR CNRS 8022 ; Villeneuve-d鈥橝scq ; France
  
• 关键词：Neutrality ; Multi ; objective optimization ; Local search ; Permutation flowshop scheduling
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9018
• 期：1
• 页码：34-47
• 全文大小：483 KB
• 参考文献：1. Barnett, L.: Netcrawling - optimal evolutionary search with neutral networks. In: Proceedings of the 2001 Congress on Evolutionary Computation, CEC 2001, pp. 30鈥?7. IEEE Press (2001)
  2. Bleuler, S, Laumanns, M, Thiele, L, Zitzler, E PISA 鈥?a platform and programming language independent interface for search algorithms. In: ditors">Fonseca, CM, Fleming, PJ, Zitzler, E, Deb, K, Thiele, L eds. (2003) Evolutionary Multi-Criterion Optimization. Springer, Heidelberg, pp. 494-508 dx.doi.org/10.1007/3-540-36970-8_35" target="_blank" title="It opens in new window">CrossRef
  3. Knowles, J., Thiele, L., Zitzler, E.: A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich (February 2006)
  4. Liefooghe, A, Humeau, J, Mesmoudi, S, Jourdan, L, Talbi, EG (2012) On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. J. Heuristics 18: pp. 317-352 dx.doi.org/10.1007/s10732-011-9181-3" target="_blank" title="It opens in new window">CrossRef
  5. Liefooghe, A, Jourdan, L, Talbi, EG (2011) A software framework based on a conceptual unified model for evolutionary multiobjective optimization: Paradiseo-moeo. European Journal of Operational Research 209: pp. 104-112 dx.doi.org/10.1016/j.ejor.2010.07.023" target="_blank" title="It opens in new window">CrossRef
  6. Lourenco, H, Martin, O, Stutzle, T Iterated local search. In: ditors">Glover, F, Kochenberger, G eds. (2002) Handbook of Metaheuristics, International Series in Operations Research & Management Science. Kluwer Academic Publishers, Norwell, pp. 321-353
  7. Marmion, M-E, Dhaenens, C, Jourdan, L, Liefooghe, A, Verel, S NILS: a neutrality-based iterated local search and its application to flowshop scheduling. In: ditors">Merz, P, Hao, J-K eds. (2011) Evolutionary Computation in Combinatorial Optimization. Springer, Heidelberg, pp. 191-202 dx.doi.org/10.1007/978-3-642-20364-0_17" target="_blank" title="It opens in new window">CrossRef
  8. Minella, G, Ruiz, R, Ciavotta, M (2008) A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing 20: pp. 451-471 dx.doi.org/10.1287/ijoc.1070.0258" target="_blank" title="It opens in new window">CrossRef
  9. Taillard, E (1993) Benchmarks for basic scheduling problems. European Journal of Operational Research 64: pp. 278-285 dx.doi.org/10.1016/0377-2217(93)90182-M" target="_blank" title="It opens in new window">CrossRef
  10. Verel, S., Collard, P., Clergue, M.: Scuba search : when selection meets innovation. In: Evolutionary Computation, 2004. CEC2004 Evolutionary Computation, 2004. CEC2004., pp. 924鈥?31. IEEE Press, Portland (Oregon) United States (2004)
  
• 作者单位：Evolutionary Multi-Criterion Optimization
• 丛书名：978-3-319-15933-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

This work extends the concept of neutrality used in single-objective optimization to the multi-objective context and investigates its effects on the performance of multi-objective dominance-based local search methods. We discuss neutrality in single-objective optimization and fitness assignment in multi-objective algorithms to provide a general definition for neutrality applicable to multi-objective landscapes. We also put forward a definition of neutrality when Pareto dominance is used to compute fitness of solutions. Then, we focus on dedicated local search approaches that have shown good results in multi-objective combinatorial optimization. In such methods, particular attention is paid to the set of solutions selected for exploration, the way the neighborhood is explored, and how the candidate set to update the archive is defined. We investigate the last two of these three important steps from the perspective of neutrality in multi-objective landscapes, propose new strategies that take into account neutrality, and show that exploiting neutrality allows to improve the performance of dominance-based local search methods on bi-objective permutation flowshop scheduling problems.