Abstract
This paper presents a novel approach for the integration of constraint programming techniques and evolution programs. In this approach the genetic operators implementation is based on a constraint solver, and chromosomes are arc-consistent solutions to the problem, represented as arrays of finite integer domains. This method allows to tackle efficiently constrained optimisation problems over finite integer domains with a large search space. The paper describes the main issues arising in this integration: chromosome representation and evaluation, selection and replacement strategies, and genetic operators design. The implemented system has been applied to the channel routing problem, a particular kind of the interconnection routing problem, one of the major tasks in the physical design of very large scale integration circuits.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brouwer, R.J., Banerjee, P.: Simulated annealing algorithm for channel routing on a hypercube multiprocessor. IEEE Int. Conf. on Computing Design. (1988) 4–7.
Burnstein, M.: Channel routing. Layout design and verification. North-Holland (1986) 133–167.
Carlson, B.: Compiling and Executing Finite Domain Constraints. PhD Thesis, Computer Science Department, Uppsala Unv. (1995).
Dincbas,M., Van Henteryck,P., Simmons,H., Aggoun,A.: The Constraint Programming Language CHIP. Proc. of the 2nd Int. Conf. on 5th Generation Computer Systems. (1988), 249–264.
Fang,S.C., Feng,W.S., Lee,S.L.: A new efficient approach to multilayer channel routing problem. 29th ACM-IEEE Design Automation Conf. (1992), 579–584.
Homaifar, A., Lai, S.H., Qi, X.: Constrained optimisation by genetic algorithms. Simulation, 62(4) (1994) 242–254.
ILOG. ILOG Solver C++. Reference Manual, ILOG S.A. (1993).
Joines, J., Houck C.: On the use of non-stationary penalty functions to solve nonlinear constrained optimisation problems with gas. Proc. of the 1st IEEE Int. Conf. on Evolutionary Computation. Piscatway N.Y. IEEE Press (1994) 579–584.
LaPaugh, A.S.: Algorithms for integrated circuits layouts: an analytical approach. PhD Dissertation, MIT Lab. of Computer Science (1980).
Liu, X., Sakamoto, A., Shimamoto, T.: Genetic channel routing. IEICE Trans. Fundamentals (1994) 492–501.
Michalewicz, Z.: Genetic algorithms + Data Structures = Evolution Programs. 2nd Edition, Springer-Verlag (1994).
Michalewicz, Z., Nazhiyath, G.: Genocop III. A co-evolutionary algorithm for numerial optimisation problems with non-linear constraints. Proc. of the 2nd IEEE Int. Conf. on Evolutionary Computation. NY. IEEE Press (1995) 647–651.
Minton, D., Johnston, M.D., Philips, A.B., Laird, P.: Minimising conflicts: a Heuristic Repair Method for constraint satisfaction and scheduling problems. Artificial Intelligence 58 (1992).
Mohr, R., Henderson, T.C.: Arc and path consistency revisited. Artificial Intelligence 28 (1996) 225–233.
Paredis, J.: Genetic State-Search for constrained Optimisation Problems. 13th Int. Joint Conf. on Artificial Intelligence (1993).
Takefuji: Neural network parallel computing. Kluwer Academic Press (1992).
Van Hentenryck P., Deville, Y., Teng C.M.: A generic Arc-consistency Algorithm and its Specialisations. Artificial Intelligence 57 (1992) 291–321.
Van Hentenryck, P, Saraswat, V., Deville, Y.: Design, Implementation and Evaluation of the Constraint Language cc(FD). Draft (1993).
Wallace, M.: Constraints in Planing, Scheduling and Placement Problems. Constraint Programming, Springer-Verlag (1994).
Yoshimura, T., Kuh, E.S.: Efficient algorithms for channel routing. IEEE Trans. on CAD. (1982) 25–35.
Zhou, N.F.: Channel Routing with Constraint Logic Programming and Delay. 9th I.C. on Industrial Applications of AI. Gordon and Breach. (1996) 217–231.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Ruiz-Andino, A., Ruz, J.J. (1998). Integration of constraint programming and evolution programs: Application to channel routing. In: Mira, J., del Pobil, A.P., Ali, M. (eds) Methodology and Tools in Knowledge-Based Systems. IEA/AIE 1998. Lecture Notes in Computer Science, vol 1415. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-64582-9_775
Download citation
DOI: https://doi.org/10.1007/3-540-64582-9_775
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64582-5
Online ISBN: 978-3-540-69348-2
eBook Packages: Springer Book Archive