A new evolutionary approach to cutting stock problems with and without contiguity

被引:84
作者
Liang, KH [1 ]
Yao, X
Newton, C
Hoffman, D
机构
[1] Univ New S Wales Coll, Sch Comp Sci, Australian Def Force Acad, Canberra, ACT 2600, Australia
[2] Univ Birmingham, Sch Comp Sci, Birmingham B15 2TT, W Midlands, England
关键词
evolutionary algorithm; cutting stock problems; combinatorial optimization;
D O I
10.1016/S0305-0548(01)00039-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 [计算机应用技术]; 0835 [软件工程];
摘要
Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.
引用
收藏
页码:1641 / 1659
页数:19
相关论文
共 29 条
[1]
[Anonymous], 1989, GENETIC ALGORITHM SE
[2]
[Anonymous], 1991, Handbook of genetic algorithms
[3]
Back T, 1996, EVOLUTIONARY ALGORIT
[4]
Bilchev G., 1996, Evolutionary Programming V. Proceedings of the Fifth Annual Conference on Evolutionary Programming, P333
[5]
CHELLAPILLA K, 1997, LECT NOTES COMPUTER, V1213, P361
[6]
A TYPOLOGY OF CUTTING AND PACKING PROBLEMS [J].
DYCKHOFF, H .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 44 (02) :145-159
[7]
Dyckhoff H., 1992, CUTTING PACKING PROD
[8]
Falkenauer E., 1996, Journal of Heuristics, V2, P5, DOI 10.1007/BF00226291
[9]
Fogel D.B., 1995, EVOLUTIONARY COMPUTA
[10]
APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS [J].
FOGEL, DB .
CYBERNETICS AND SYSTEMS, 1993, 24 (01) :27-36