4 research outputs found
A Modified Firefly Algorithm with Support Vector Machine for Medical Data Classification
No full textDensity based problem space search for the capacitated clustering p-median problem
No full textIn the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction-deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency.AHMAD I, 1995, CONCURRENCY-PRACT EX, V7, P411, DOI 10.1002-cpe.4330070506; AHMADI S, 2004, EUROPEAN J OPERA JAN; AHMADI S, 1998, THESIS U KENT CANTER; Baldacci R, 2002, COMPUT OPER RES, V29, P365, DOI 10.1016-S0305-0548(00)00072-1; BAXTER J, 1981, J OPER RES SOC, V32, P815, DOI 10.2307-2581397; BECK MP, 1982, EES821 PRINC U; Brucker P, 1977, OPTIMIZATION OPERATI, P45; CAPTIVO ME, 1991, EUR J OPER RES, V52, P65; CHHAJED D, 1993, LOCATION SCI, V1, P263; DHODHI MK, 1995, IEEE T COMPUT AID D, V14, P934, DOI 10.1109-43.402494; DONGARRA JJ, 2001, PERFORMANCE VARIOUS; Franca P. M., 1999, International Transactions in Operational Research, V6, DOI 10.1016-S0969-6016(99)00017-9; Franco J, 1997, CROP SCI, V37, P972; GENDREAU M, 1992, OPER RES, V40, P1086, DOI 10.1287-opre.40.6.1086; Glover F, 2000, CONTROL CYBERN, V29, P653; Hansen P, 1997, MATH PROGRAM, V79, P191, DOI 10.1007-BF02614317; HANSEN P, 1994, EUR J OPER RES, V72, P602, DOI 10.1016-0377-2217(94)90427-8; HANSEN P, 1993, G9338; Karimi J., 1986, Journal of Management Information Systems, V3; KLEIN G, 1991, NAV RES LOG, V38, P447, DOI 10.1002-1520-6750(199106)38:3447::AID-NAV32203803123.0.CO;2-0; KOSKOSIDIS YA, 1992, TRANSPORT RES B-METH, V26, P365, DOI 10.1016-0191-2615(92)90032-R; Leon VJ, 1997, IIE TRANS, V29, P115, DOI 10.1023-A:1018550624429; LEON VJ, 1995, OR SPEKTRUM, V17, P173; Liu G., 1968, INTRO COMBINATORIAL; Maniezzo V, 1998, J HEURISTICS, V4, P263, DOI 10.1023-A:1009665717611; MIRZAIAN A, 1985, NETWORKS, V15, P1, DOI 10.1002-net.3230150102; MULVEY JM, 1984, EUR J OPER RES, V18, P339, DOI 10.1016-0377-2217(84)90155-3; MURALIDHAR K, 1995, COMPUT OPER RES, V22, P701, DOI 10.1016-0305-0548(94)00063-E; Naphade KS, 1997, ANN OPER RES, V70, P307, DOI 10.1023-A:1018982423325; NEMHAUSER GL, 1988, WILEYINTERSCIENCE SE; Osman I. H., 1994, INT T OPER RES, V11, P317, DOI 10.1111-1475-3995.d01-43; Osman Ibrahim H, 1996, METAHEURISTICS THEOR; OSMAN IH, 2002, GUIDED CONSTRUCTION; Osman IH, 1995, OPERATIONAL RES TUTO, P92; OSMAN IH, 1995, OR SPEKTRUM, V17, P211; Osman IH, 1996, ANN OPER RES, V63, P513; OSMAN IH, 2003, JOINT EURO INFORMS M; Ribeiro CC, 2002, ESSAYS SURVEYS METAH; RUSSELL RA, 1995, TRANSPORT SCI, V29, P156, DOI 10.1287-trsc.29.2.156; Steiglitz K., 1968, Proceedings sixth Allerton conference on circuit and system theory; STORER RH, 1993, OPERATIONS RES PRODU; STORER RH, 1992, MANAGE SCI, V38, P1495, DOI 10.1287-mnsc.38.10.1495; Vakharia AJ, 2000, EUR J OPER RES, V123, P640, DOI 10.1016-S0377-2217(99)00103-4; VOSS S, 1998, METAHEURISTICS ADV T; WONG MA, 1982, J AM STAT ASSOC, V77, P841, DOI 10.2307-228731693
Greedy random adaptive memory programming search for the capacitated clustering problem
No full textIn the capacitated clustering problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises the total scatter of points allocated to these centers. In this paper, we propose a merger of Greedy Random Adaptive Search Procedure (GRASP) and Adaptive Memory Programming (AMP) into a new GRAMPS framework for the CCP. A learning process is kept in charge of tracking information on the best components in an elite set of GRAMPS solutions. The information are strategically combined with problem-domain data to restart the construction search phase. At early stage of constructions, priorities are given to problem-domain data and progressively shifted towards generated information as the learning increases. GRAMPS is implemented with an efficient local search descent based on a restricted λ-interchange neighbourhood. Extensive experiments are reported on on a standard set of bench-marks from the literature and on a new set of large instances. The results show that GRAMPS has an efficient learning mechanism and is competitive with the existing methods in the literature. © 2003 Elsevier B.V. All rights reserved.AHMADI S, 2004, ANN OPERATIONS RES M; AHMADI S, 1998, THESIS U KENT CANTER; AIEX RM, 2003, INFORMS J COMPUTING; Baldacci R, 2002, COMPUT OPER RES, V29, P365, DOI 10.1016-S0305-0548(00)00072-1; BECK MP, 1982, EES821 PRINC U; Brucker P, 1977, OPTIMIZATION OPERATI, P45; CHHAJED D, 1993, LOCATION SCI, V1, P263; DONGARRA JJ, 2001, PERFORMANCE VARIOUS; Dorigo M, 1996, IEEE T SYST MAN CY B, V26, P29, DOI 10.1109-3477.484436; FEO TA, 1989, OPER RES LETT, V8, P67, DOI 10.1016-0167-6377(89)90002-3; Fleurent C, 1999, INFORMS J COMPUT, V11, P198, DOI 10.1287-ijoc.11.2.198; Franca P. M., 1999, International Transactions in Operational Research, V6, DOI 10.1016-S0969-6016(99)00017-9; Glover F, 2000, CONTROL CYBERN, V29, P653; Glover F., 1977, DECISION SCI, V8, P156, DOI DOI 10.1111-J.1540-5915.1977.TB01074.X; Glover F., 1997, ADV METAHEURISTICS O, P1; Golden BL, 1997, COMPUT OPER RES, V24, P445, DOI 10.1016-S0305-0548(96)00065-2; Hansen P, 1997, MATH PROGRAM, V79, P191, DOI 10.1007-BF02614317; HANSEN P, 1994, EUR J OPER RES, V72, P602, DOI 10.1016-0377-2217(94)90427-8; HANSEN P, 1993, G9338; HANSEN P, 2002, ESSAYS SURVEYS METAH; Karimi J., 1986, Journal of Management Information Systems, V3; KLEIN G, 1991, NAV RES LOG, V38, P447, DOI 10.1002-1520-6750(199106)38:3447::AID-NAV32203803123.0.CO;2-0; KOSKOSIDIS YA, 1992, TRANSPORT RES B-METH, V26, P365, DOI 10.1016-0191-2615(92)90032-R; Laguna M, 1999, INFORMS J COMPUT, V11, P44, DOI 10.1287-ijoc.11.1.44; Maniezzo V, 1998, J HEURISTICS, V4, P263, DOI 10.1023-A:1009665717611; MIRZAIAN A, 1985, NETWORKS, V15, P1, DOI 10.1002-net.3230150102; MULVEY JM, 1984, EUR J OPER RES, V18, P339, DOI 10.1016-0377-2217(84)90155-3; Osman I. H., 1994, INT T OPER RES, V11, P317, DOI 10.1111-1475-3995.d01-43; Osman Ibrahim H, 1996, METAHEURISTICS THEOR; OSMAN IH, 2002, GUIDED CONSTRUCTION; Osman IH, 1999, LECT NOTES ARTIF INT, V1611, P11; Osman IH, 1995, OPERATIONAL RES TUTO, P92; Osman IH, 1996, ANN OPER RES, V63, P513; OSMAN IH, 2003, JOINT EURO INFORMS M; PITSOULIS LS, 2001, HDB APPL OPTIMIZATIO; Resende Festa P., 2001, ESSAYS SURVEYS METAH; Rochat Y., 1995, Journal of Heuristics, V1, DOI 10.1007-BF02430370; Vakharia AJ, 2000, EUR J OPER RES, V123, P640, DOI 10.1016-S0377-2217(99)00103-4; VOSS S, 1998, METAHEURISTICS ADV T30252
