Abstract
Seeding is a technique used to leverage population diversity in genetic algorithms. This paper presents a quick survey of different seeding approaches, and evaluates one of the promising ones called the Seeding Genetic Algorithm. The Seeding GA does not include mutation, and it has been shown to work well on some GA-hard problems with binary representation, such as the Hierarchical If-and-Only-If or Deceptive Trap. This paper investigates the effectiveness of the Seeding GA on two problems with more complex non-binary representations: capacitated lot-sizing and single-machine scheduling. The results show, with statistical significance, that the new GA is consistently outperformed by the conventional GA, and that not including mutation is the main reason why. A detailed analysis of the results is presented and suggestions are made to enhance and improve the method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The “labor cost” here entails regular and overtime labor costs, plus sub-contracting costs.
The data sets are available online and can also be provided upon request.
IBM ILOG Optimization Studio Version 12.6 was used, and unless otherwise stated, all runs were on default setting.
The flow time of a job is the amount of time it spends in the system after its readiness until its completion.
The data sets are available upon request and they might be published in a future separate work
References
Ahuja, R. K., & Orlin, J. B. (1997). Developing fitter genetic algorithms. INFORMS Journal on Computing, 9(3), 251–253.
Baker, K. R. (1974). Introduction to sequence and scheduling. New York: Wiley.
Bentley, J. L. (1990). Experiments on traveling salesman heuristics. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (SODA ’90), pp. 91–99.
Chang, P. C., Hsieh, J. C., & Liu, C. H. (2006). A case-injected genetic algorithm for single machine scheduling problems with release time. International Journal of Production Economics, 103(2), 551–564.
Eshelman, L., & Schaffer, J. J. D. (1993). Crossover’s niche. In Proceedings of 5th international conference on genetic algorithms (ICGA), pp. 9–14.
Forrest, S., & Mitchell, M. (1993). Relative building-block fitness and the building-block hypothesis. In Foundations of genetic algorithms 2 (pp. 109–126).
Gicquel, C., Minoux, M., & Dallery, Y. (2008). Capacitated lot sizing models: A literature review., Open Access Article hal-00255830.
Goldberg, D.E. (1987). Simple genetic algorithms and the minimal deceptive problem. In Genetic algorithms and simulated annealing (Chap. 6, pp. 74–88).
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison Wesley Publication Co.
Goren, H. G., Tunali, S., & Jans, R. (2010). A review of applications of genetic algorithms in lot sizing. Journal of Intelligent Manufacturing, 21(4), 575–590.
Grefenstette, J. J. (1987). Incorporating problem specific knowledge into genetic algorithms. In Genetic algorithms and simulated annealing (pp. 42–60).
Holland, J. H. (1975). Adaptation in natural and artificial systems. ann arbor: University of Michigan Press.
Jones, T. (1995). Crossover, macromutation, and population based search. In Proceedings of 6th international conference on genetic algorithms (ICGA), pp. 73–80.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Liu, J., & McCarthy, B. L. (1991). Effective heuristic for the single machine scheduling problem with ready times. International Journal of Production Research, 29, 1521–1533.
Louis, S. J., McGraw, G., & Wyckoff, R. (1993). Case-based reasoning assisted explanation of genetic algorithm results. Journal of Experimental and Theoretical Artificial Intelligence, 5, 21–37.
Meadows, B., Riddle, P., Skinner, C., & Barley, M. (2013). Evaluating the seeding genetic algorithm. Advances in Artificial Intelligence, Lecture Notes in Computer Science, 8272, 221–227.
Oman, S., & Cunningham, P. (2001). Using case retrieval to seed genetic algorithms. International Journal of Computational Intelligence and Applications, 1, 71–82.
Ramsey, C., & Grefensttete, J. (1993). Case-based initialization of genetic algorithms. In Proceedings of the fifth international conference on genetic algorithms.
Skinner, C., & Riddle, P. J. (2007). Random search can outperform mutation. In 2007 IEEE Congress on Evolutionary Computation. CEC, 2007, pp. 2584–2590.
Skinner, C. (2009). On the discovery, selection and combination of building-blocks in evolutionary algorithms. PhD thesis, Department of Computer Science, University of Auckland.
Süer, G. A., Badurdeen, F., & Dissanayake, N. (2008). Capacitated lot sizing by using multi-chromosome crossover strategy. Journal of Intelligent Manufacturing, 19, 273–282.
Süer, G. A., Vazquez, R., & Santos, J. (2003). Evolutionary programming for minimizing the average flow time in the presence of non-zero ready times. Computers and Industrial Engineering, 45, 331–344.
Watson, R.A., & Pollack, J.B. (2000). Recombination without respect: Schema combination and disruption in genetic algorithm crossover. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 112–119.
Wu, A.S., Lindsay, R.K., & Riolo, R.L. (1997). Empirical observations on the roles of crossover and mutation. In: Proceedings of 7th international conference on genetic algorithms, pp. 362–369.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mirshekarian, S., Süer, G.A. Experimental study of seeding in genetic algorithms with non-binary genetic representation. J Intell Manuf 29, 1637–1646 (2018). https://doi.org/10.1007/s10845-016-1204-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-016-1204-3