Memetic Algorithms for the MinLA Problem

1. Bäck, T., Hammel, U., Schwefel, H.P.: Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation 1(1), 3–17 (1997)

   Article  Google Scholar 

2. Bar-Yehuda, R., Even, G., Feldman, J., Naor, S.: Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. Journal of Graph Algorithms and Applications 5(4), 1–27 (1996)

   Article  MathSciNet  MATH  Google Scholar 

3. Corne, D., Dorigo, M., Glover, F., Dasgupta, D., Moscato, P., Poli, R., Price, K.V. (eds.): New Ideas in Optimization (Part 4: Memetic Algorithms). McGraw-Hill, New York (1999)

   Google Scholar 

4. Davis, L.: Handbook of Genetic Algorithms. Van Nostrad, New York (1991)

   Google Scholar 

5. Diaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002)

   Article  Google Scholar 

6. Even, S., Shiloah, Y.: NP-completeness of several arrangement problems. Technical Report CS0043, Computer Science Department, Technion, Israel Institute of Technology, Haifa, Israel (January 1975)

   Google Scholar 

7. Freisleben, B., Merz, P.: A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pp. 616–621. IEEE Computer Society Press, Los Alamitos (1996)

   Chapter  Google Scholar 

8. Galinier, P., Hao, J.: Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3(4), 379–397 (1999)

   Article  MathSciNet  MATH  Google Scholar 

9. Garey, M., Johnson, D.: Computers and Intractability: A guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)

   MATH  Google Scholar 

10. Grefenstette, J.J.: Incorporating problem specific knowledge into genetic algorithms. In: Davis, L. (ed.) Genetic Algorithms and Simulated Annealing, London, pp. 42–60. Morgan Kaufmann Publishers, San Francisco (1987)

    Google Scholar 

11. Harper, L.: Optimal assignment of numbers to vertices. Journal of SIAM 12(1), 131–135 (1964)

    MathSciNet  MATH  Google Scholar 

12. Hart, W.E., Krasnogor, N., Smith, J.E. (eds.): Recent Advances in Memetic Algorithms and Related Search Technologies. Springer, Heidelberg (2004)

    Google Scholar 

13. Juvan, M., Mohar, B.: Optimal linear labelings and eigenvalues of graphs. Discrete Applied Mathematics 36(2), 153–168 (1992)

    Article  MathSciNet  MATH  Google Scholar 

14. Koren, Y., Harel, D.: A multi-scale algorithm for the linear arrangement problem. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 293–306. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

15. McAllister, A.J.: A new heuristic algorithm for the linear arrangement problem. Technical Report TR-99-126a, Faculty of Computer Science, University of New Brunswick (1999)

    Google Scholar 

16. Merz, P., Freisleben, B.: Fitness landscapes, memetic algorithms and greedy operators for graph bi-partitioning. Evolutionary Computation 8(1), 61–91 (2000)

    Article  Google Scholar 

17. Petit, J.: Approximation heuristics and benchmarkings for the MinLA problem. In: Alex 1998 – Building Bridges Between Theory and Applications, pp. 112–128 (1998)

    Google Scholar 

18. Petit, J.: Layout Problems. PhD thesis, Universitat Politécnica de Catalunya (2001)

    Google Scholar 

19. Petit, J.: Combining spectral sequencing and parallel simulated annealing for the MinLA problem. Parallel Processing Letters 13(1), 71–91 (2003)

    Article  MathSciNet  Google Scholar 

20. Poranen, T.: A genetic hillclimbing algorithm for the optimal linear arrangement problem. Technical report, University of Tampere, Finland (June 2002)

    Google Scholar 

21. Safro, I., Ron, D., Brandt, A.: Graph minimum linear arrangement by multilevel weighted edge contractions. In: Journal of Algorithms (in press 2004)

    Google Scholar 

22. Tomassini, M.: A survey of genetic algorithms. Annual Reviews of Computational Physics III, 87–118 (1995)

    Article  MathSciNet  Google Scholar 

23. Yao, X., Wang, F., Padmanabhan, K., Salcedo-Sanz, S.: Hybrid evolutionary approaches to terminal assignment in communications networks. In: Hart, W.E., Krasnogor, N., Smith, J.E. (eds.) Recent Advances in Memetic Algorithms and Related Search Technologies, pp. 129–160. Springer, Heidelberg (2004)

    Google Scholar 

Download references