Presentation of Some Metaheuristics for the Optimization of Complex Systems
LARA, École Nationale d’Ingénieurs de Tunis
BP 37, Le Belvédère 1002 Tunis, Tunisie
LAGIS, École Centrale de Lille, Cité scientifique
BP 48, 59651 Villeneuve d’Ascq Cedex, France
Abstract: Some metaheuristics for the optimization of complex systems are proposed in this paper. The metaheuristic approaches can be separate in two classes: the local search techniques and the global ones. An important difficulty which appears in complex optimization problems is the existence of constraints which can be strict and inviolable or soft. To resolve these problems, some hybrid approaches are considered.
Keywords: Optimization, complex systems, metaheuristics, tabu search, simulated annealing, genetic algorithms, ant colony optimization, particle swarm optimization, tunneling Algorithms.
Fatma Tangour graduated from Ecole Normale Superieure de l’Enseignement Technique of Tunis, received the Master degree of automatic and signal treatment in 2004 and Doctoral degree from the Ecole Nationale d’Ingénieur de Tunis and the Ecole Centrale de Lille in 2007. She is currently researcher in LARA Automatique at the Ecole Nationale d’Ingénieur de Tunis and working with the higher institute of sciences applied and technology of Kairouan, Tunisia. Her research interests are in the area of optimization methods for discrete events systems, computer science and operational research.
Pierre Borne received the Master degree of Physics in 1967, the Masters of Electronics, of Mechanics and of Applied Mathematics in 1968. The same year he obtained the Diploma of “Ingénieur IDN” (French “Grande Ecole”). He obtained the PhD in Automatic Control of the University of Lille in 1970 and the DSc of the same University in 1976. He became Doctor Honoris Causa of the Moscow Institute of Electronics and Mathematics (Russia) in 1999, of the University of Waterloo (Canada) in 2006 and of the Polytechnic University of Bucarest (Romania). He is author or co-author of about 200 Journal articles and book chapters, and of 34 plenary lectures and of more than 250 communications in international conferences. He has been the supervisor of 68 PhD thesis and is author of 20 books. He is Fellow of IEEE and has been President of the IEEE/SMC society in 2000 and 2001. He is presently Professor “de classe exceptionnelle” at the Ecole Centrale de Lille and director of the french pluriformations national group of research in Automatic Control
CITE THIS PAPER AS:
Fatma TANGOUR, Pierre BORNE, Presentation of Some Metaheuristics for the Optimization of Complex Systems, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (2), pp. 169-180, 2008.
Many optimization problems such as combinatorial optimization [3, 31] ones are usually N-P hard problems which prevent the implementation of exact used solving methodologies. It is the reason why engineers prefer to use metaheuristics which are able to produce good solutions in a reasonable computation time. The metaheuristic approaches can be separate in two classes: the local search techniques and the global ones. Among the local search techniques the Tabu search  is the more known. The other methods usually involve a part of stochastic approach, like the Simulated Annealing [1, 6, 27], the Genetic or Evolutionary Algorithms [28, 29, 36], the Ant Colony Optimization  or the Particle Swarm Optimisation [4, 8].An important difficulty which appears in complex optimization problems is the existence of constraints which can be strict and inviolable or soft but with penalization which increase strongly with the degree of violation.
A possible acceleration of the convergence can be obtained by using tunnelling algorithms.
The muliobjective optimization is considered at the end of this paper with presentation of the OWA approach, of the Choquet integral and the Pareto optimality.
The various metaheuristics which have been presented here have been implemented in various applications such as the optimization manufacturing problems but in each case the formulation of the problem have to be adapting to the chosen algorithm.
Very often hybrid approaches are implemented using simultaneously several metaheuristics and usual local search like the hill climbing methods.
- Aarts, E.H.L., Van Laarhoven P.J.M., Simulated Annealing: Theory and Applications, D. Reidel Publishing Company, 1987.
- Bäck, T., Hammel U., Schwefel H.P., Evolutionary Computation, Comments on the History and Current State, IEEE Transactions on Evolutionary Computation, Vol. 1, 1997, pp. 3-17.
- Blum, C., Roli A., Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison, ACM Computing Surveys, Vol. 35, No. 3, September 2003, pp. 268-308.
- Bonabeau, E., Dorigo M., Theraulaz G., Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999.
- Borne, P., TANGOUR F., Metaheuristics for the Optimization in Planning and Scheduling, the Fourth Conference on Management and Control of Production and Logistics MCPL 2007, Sibiu, ROMANIA, September 27- 30, 2007.
- Chaisemartin, P., Dreyfus G., Fontet M., Kouka E., Loubières P., Siarry P., Placement and Channel Routing by Simulated Annealing: Some Recent Developments, Computer Systems Science and engineering, Vol. 41, 1989.
- Choquet, G., Theory of Capacities, Annales de l’Institut Fourier, No 5, 1993, pp. 131-295.
- Clerc, M., Kennedy J., The Particle Swarm. Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 58-73, 2002.
- Dejong, K.A., Spears W.M., Using Genetic Algorithms to Solve NP- Complete Problems, George Mason University, Fairfax, VA, 1989.
- Deneubourg, J.L., Goss S., Verhaeghe J.C., Probabilistic Behaviour in Ants, Journal of Theorical Biology, Vol. 105, 1983, pp. 259-271.
- Dorigo, M., Colorni A., Maniezzo V. ,The Ant System: Optimization By a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No 1, pp.1-13, 1996.
- Ennigrou, M., Ghédira K., Flexible Job-Shop scheduling with Multi-agent System and Tabu Search, Journal Européen des Systèmes Automatisés, JESA, Vol. 38, No. 7-8, 2004.
- Ghédira, K., Jlifi B., A Distributed Guided Genetic Algorithm for Max-CSPs, Revue d’Intelligence Artificielle, 2002, pp. 1-16.
- Glover, F., Laguna M., Tabu Search, Kluwer, Norwell, MA, 1997.
- Glover F., Tabu Search, Part I – ORSA Journal on Computing 1, 1989, pp. 190-206.
- Glover F., Tabu Search, Part II , ORSA Journal on Computing 2, 1990, pp. 4-32.
- Goldberg, D.E., Genetic Algorithms in Search, Optimisation, and Machine Learning, Reading, Mass, Addison-Wesley, 1989.
- Holland, J.H., Genetic Algorithms and the Optimal Allocations of Trials, In SIAM Journal of computing, Vol. 2, 1973, pp. 88-105.
- Kacem, I., Hammadi S., Borne P., Fuzzy Evolutionary Approach for Multiobjective Combinatorial Optimization: Application to Scheduling Problems, Studies in fuzziness and soft computing, Vol. 126, 2003, pp. 197-219.
- Kacem, I., Hammadi S., Borne P., Pareto-optimality Approach for Flexible Job-shop Scheduling Problem: Hybridization of Genetic Algorithms with Fuzzy Logic, Mathematics and Computers in Simulation, Vol. 60, 2002, pp. 245-276.
- Kennedy, J, Eberhart R., Shi Y., Swarm Intelligence, Morgan Kaufmann Academic Press, 2001.
- Kennedy, J., Eberhart R., Particle Swarm Optimization, IEEE International Conference on Neural Networks, Piscataway, NJ, Proc., 1995, pp. 1942-1948.
- Kirkpatrick, S., Gelatt C.D., VECCHI M.P., Optimization by Simulated Annealing, Science, Vol. 220, No. 4598, 1983, pp. 671-680.
- Levy, A.V., Gomez S., The Tunneling Method Applied to Global Optimization, In: Boggs PT, Byrd R.H., Schnabel RB (eds), Numerical Optimization, SIAM, 1985, pp. 213-244.
- Liouane, N., Saad I., Hammadi S., Borne P., Ants System and Local Search Optimisation for Flexible Job-shop scheduling Production, International Journal of Computers, Communication and Control, Vol. 11, No. 2, 2007, pp. 66-75.
- Mesghouni, K., Borne P., Hammadi S., Evolutionary Algorithms for Job-shop scheduling, Applied Mathematics and Computer, Vol. 14, No. 1, 2004, pp. 91-103.
- Metropolis, N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E., Simulated Annealing, J. Chem. Phys. 21, 1953.
- Patnaik, S., Genetic Algorithms: A Survey, IEEE computer society, Vol. 27, No. 6, pp.17-26, 1994.
- Renders, J.M., Algorithmes génétiques et réseaux de neurones, Paris: Hermès, 1995.
- Richardson, J.T., Palmer M.R. Liepins G., Hilliard M., Some Guidelines for Genetic Algorithms with Penalty Functions, Proceedings of the Third International Conference on Genetic Algorithms, pp. 191-197, 1989.
- Schwefel, H.P., Numerical Optimization of Computer Models, Chichester Wiley, 1981.
- Siarry, P., Berthiau G., Durbin F., Haussy J., Enhanced Simulated Annealing for Globally Minimizing Functions of Many Continuous Variables, ACM Transactions on Mathematical Software, Vol. 23, No. 2, pp. 209-228, 1997.
- Tangour, F., I. Saad, Multiobjective Optimization Scheduling Problems by Pareto-optimality in Agro-alimentary Workshop, International Journal of Computers Communications & Control, IJCCC, Vol. 1, No. 3, 2006, pp. 71-83.
- Wenzel, W., Hamacher K., Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes, Phys. Rev. Lett., Vol. 82, No. 15, 1999, pp. 3003-3007.
- Yager, R.R., On Weighted Medium Aggregation Operators in Multicriteria Decision Making, IEEE Trans. On Systems, Man and Cybernetics, Vol. 18, 1988, pp. 183-190.
- Zomaya, P.F., Parallel Genetic Algorithms, Parallel & Distributed Computing, Handbook, McGraw Hul, 1996.
- Zribi, N., Borne P., Hybrid Genetic Algorithm for the Flexible Job-shop Problem under Maintenance Constraints, Lecture Notes in Computer Science, Vol. 3612, 2005, pp. 259-268.