Special Issue Evolutionary Optimization: Theory and ApplicationsNo Access

HYBRID EVOLUTIONARY AND ANNEALING ALGORITHMS FOR NONLINEAR DISCRETE CONSTRAINED OPTIMIZATION

Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Urbana, IL 61801, USA

Search for more papers by this author

and

YIXIN CHEN

Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Urbana, IL 61801, USA

Search for more papers by this author

https://doi.org/10.1142/S1469026803001063Cited by:7 (Source: Crossref)

Abstract

This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

E. Aarts and J. Korst , Simulated Annealing and Boltzmann Machines ( John Wiley and Sons , 1989 ) . Google Scholar
D. P. Bertsekas , Constrained Optimization and Lagrange Multiplier Methods ( Academic Press , 1982 ) . Google Scholar
A. Coranaet al., ACM Trans. Math. Software 13(3), 262 (1987), DOI: 10.1145/29380.29864. Crossref, Google Scholar
A. E. Eiben and Z. Ruttkay, Self-adaptivity for constraint satisfaction: Learning penalty functions, Proc. 3rd IEEE Conf. Evol. Comput. (1996) pp. 258–261. Google Scholar
C. A. Floudas and P. M. Pardalos , A Collection of Test Problems for Constrained Global Optimization Algorithms , Lecture Notes in Computer Science 455 ( Springer-Verlag , 1990 ) . Crossref, Google Scholar
J. Joines and C. Houck, On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems, Proc. 1st IEEE Int. Conf. Evol. Comput. (1994) pp. 579–584. Google Scholar
R. E. Korf, Artif. Intell. 27, 97 (1985), DOI: 10.1016/0004-3702(85)90084-0. Crossref, Google Scholar
S. Koziel and Z. Michalewics, Evol. Comput. 7(1), 19 (1999), DOI: 10.1162/evco.1999.7.1.19. Crossref, Google Scholar
S. Leyffer, Mixed integer nonlinear programming solver [http://www-unix.mcs.anl.gov/~leyffer/solvers.html, 2002] . Google Scholar
S. Leyffer, MacMINLP: AMPL collection of MINLP problems [http://www-unix.mcs.anl.gov/~leyffer/MacMINLP/, 2003] . Google Scholar
Z. Michalewicz and G. Nazhiyath, Genocop III: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints, Proc. IEEE Int. Conf. Evol. Comput.2 (1995) pp. 647–651. Google Scholar
Z. Michalewicz and M. Schoenauer, Evol. Comput. 4(1), 1 (1996), DOI: 10.1162/evco.1996.4.1.1. Crossref, Google Scholar
R. Vanderbei, Nonlinear optimization models. [http://www.sor. princeton.edu/~rvdb/ampl/nlmodels/, 2003] . Google Scholar
B. W. Wah and Y. X. Chen, Optimal anytime constrained simulated annealing for constrained global optimization, 6th Int. Conf. Principles Practice Constraint Program (2000) pp. 425–439. Google Scholar
B. W. Wah and Y. X. Chen, Partitioning of temporal planning problems in mixed space using the theory of extended saddle points, Proc. IEEE Int. Conf. Tools Artif. Intell. (2003) pp. 266–273. Google Scholar
B. W. Wah and T. Wang, Simulated annealing with asymptotic convergence for nonlinear constrained global optimization, Principles Practice Constraint Program (1999) pp. 461–475, DOI: 10.1007/978-3-540-48085-3_33. Google Scholar
B. W. Wah and Z. Wu, The theory of discrete Lagrange multipliers for nonlinear discrete optimization, Principles Practice Constraint Program (1999) pp. 28–42, DOI: 10.1007/978-3-540-48085-3_3. Google Scholar
Z. Wu, The Theory and Applications of Nonlinear Constrained Optimization using Lagrange Multipliers, PhD Thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 2001 . Google Scholar