题名

Generational Model Genetic Algorithm for Real World Set Partitioning Problems

DOI

10.7903/ijecs.1138

作者

Althon Chi-San Lin

关键词

Combinatorial Optimization ； Set Partitioning Problem ； Genetic Algorithm ； Crew Scheduling ； Grouping Crossover

期刊名称

International Journal of Electronic Commerce Studies

卷期/出版年月

4卷1期（2013 / 06 / 01）

页次

33 - 46

内容语文

英文
英文摘要

This paper proposes a generational model genetic algorithm-based system for solving real-world large scale set partitioning problems (SPP). The SPP is an important combinatorial optimization and has many applications like airline crew scheduling. Two improved genetic algorithm (GA) components are introduced and applied to the generational model GA system that can effectively find feasible solutions for difficult and large scale set partitioning problems. The two components are the grouping crossover operator and a modified local optimizer. The experimental results in this research show that the performance of this GA based system is capable of producing optimal or near-optimal solutions for large scale instances of SPP.
主题分类 基礎與應用科學 > 資訊科學
社會科學 > 經濟學
社會科學 > 財金及會計學
社會科學 > 管理學
参考文献
  1. Arabeyre, J.,Fearnley, J.,Steiger, F.,Teather, W.(1969).The airline crew scheduling problem: A survey.Transportation Science,3(2),140-163.
  2. Beasley, J.E.(1990).OR-Library: Distributing test problems by electronic mail.Journal of the Operational Research Society,41(11),1069-1072.
  3. Borndörfer, R.(1998).TU Berlin.
  4. Chen, J.,Lin, Y.,Chen, L.(2007).A relation-based genetic algorithm for partitioning problems with applications.Lecture Notes in Computer Science,4570,217-226.
  5. Chu, P.C.,Beasley, J.E.(1998).Constraint handling in genetic algorithms: The set partitioning problem.Journal of Heuristics,4(4),323-357.
  6. Digalakis, J.G.,Johnson, D.S..Computer and intractability - A guide to the theory of NP-completeness.San Francisco, USA:W.H. Freeman.
  7. Falkenauer, E.(1996).A hybrid grouping genetic algorithm for bin packing.Journal of Heuristics,2(1),5-30.
  8. Garey, M.R.,Margaritis, K.G.(2000).On benchmarking functions for genetic algorithms.International Journal of Computer Mathematics,77(4),481-506.
  9. Goldberg, D.E.(1989).Genetic algorithms in search optimization and machine learning.New York:Addison-Wesley Publishing Co..
  10. Hoffman, K.L.,Padberg, M.(1993).Solving airline crew scheduling problems by branch-and-cut.Management Science,39(6),657-682.
  11. Holland, J.(1975).Adaptation in natural and artificial systems.Ann Arbor:The University of Michigan Press.
  12. Levine, D.(1994).Department of Computer Science, Illinois Institute of Technology.
  13. Lozano, M.,Herrera, F.,Cano, J.R.(2008).Replacement strategies to maintain preserve useful diversity in steady-state genetic algorithms.Inf Sci,178(23),4421-4433.
  14. Nirjon, S.M. Shahriar(2006).Study on GA based solutions to set partitioning problem and proposed new approach.Daffodil International University of Science and Technology,1(1)
  15. Parker, R.,Rardin, R.(1988).Discrete optimization.San Diego:Academic Press.
  16. Syswerda, G.(1989).Uniform crossover in genetic algorithms.Proceeding of the 3rd International Conference on Genetic Algorithms,Fairfax, Virginia, USA:
  17. Van Krieken, M.G.C.,Flueuren, H.A.,Peeters, M.J.P.(1989).CentER DiscussionCentER Discussion,未出版
print cancel