OMEGA one multi ethnic genetic approach. (English) Zbl 1343.90105
Summary: The genetic algorithm (GA) is a quite efficient paradigm to solve several optimization problems. It is substantially a search technique that uses an ever-changing neighborhood structure related to a population which evolves according to a number of genetic operators. In the GA framework many techniques have been devised to escape from a local optimum when the algorithm fails in locating the global one. To this aim we present a variant of the GA which we call OMEGA (One Multi Ethnic Genetic Approach). The main difference is that, starting from an initial population, \(k\) different sub-populations are produced at each iteration and they independently evolve in \(k\) different environments. The resulting sub-populations are then recombined and the process is iterated. Our basic algorithmic scheme is tested on a recent and well-studied variant of the classic problem of the minimum spanning tree: the Minimum Labeling Spanning Tree problem. We compare our algorithm with several approaches drawn from the literature. The results are encouraging in view of future application of OMEGA to other classes of problems.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Baker, J.M.: Adaptive speciation: the role of natural selection in mechanisms of geographic and non-geographic speciation. Stud. Hist. Philos. Sci. Part C Stud. Hist. Philos. Biol. Biomed. Sci. 36(2), 303-326 (2005) · doi:10.1016/j.shpsc.2005.03.005 |
| [2] | Barricelli, N.: Numerical testing of evolution theories. Acta Biotheoretica 16(1-2), 69-98 (1962) · doi:10.1007/BF01556771 |
| [3] | Captivo, M., Clímaco, J., Pascoal, M.: A mixed integer linear formulation for the minimum label spanning tree problem. Comput. Oper. Res. 36(11), 3082-3085 (2009) · Zbl 1162.90575 · doi:10.1016/j.cor.2009.02.003 |
| [4] | Carrabs, F., Cerulli, R., Gaudioso, M., Gentili, M.: Lower and upper bounds for the spanning tree with minimum branch vertices. Comput. Optim. Appl. 56(2), 405-438 (2013) · Zbl 1312.90038 · doi:10.1007/s10589-013-9556-5 |
| [5] | Cerrone, C., Cerulli, R., Raiconi, A.: Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur. J. Oper. Res. 232(3), 442-453 (2014) · Zbl 1305.90346 · doi:10.1016/j.ejor.2013.07.029 |
| [6] | Cerulli, R., Fink, A., Gentili, M., Voss, S.: Metaheuristics comparison for the minimum labelling spanning tree problem. In: Golden, B.L., Raghavan, S., Wasil, E.A. (eds.) The next wave on computing, optimization, and decision technologies, pp. 93-106. Springer, Berlin (2005) |
| [7] | Chang, R.S., Shing-Jiuan, L.: The minimum labeling spanning trees. Inf. Process. Lett. 63, 277-282 (1997) · Zbl 0938.90063 · doi:10.1016/S0020-0190(97)00127-0 |
| [8] | Consoli, S., Moreno-Prez, J.A., Mladenovic, N.: Intelligent variable neighbourhood search for the minimum labelling spanning tree problem. Electron. Notes Discrete Math. 41, 399-406 (2013) · doi:10.1016/j.endm.2013.05.118 |
| [9] | Cordeau, J.F., Gaudioso, M., Laporte, G., Moccia, L.: A memetic heuristic for the generalized quadratic assignment problem. INFORMS J. Comput. 18(4), 433-443 (2006) · Zbl 1241.90105 · doi:10.1287/ijoc.1040.0128 |
| [10] | Fraser, A.: Simulation of genetic systems by automatic digital computers. I. Introd. Aust. J. Biol. Sci. 10, 484-491 (1957) |
| [11] | Fraser, A.: Computer models in genetics. McGraw-Hill, New York (1970) |
| [12] | Goldberg, D.E.: Genetic algorithms in search. Optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc., Boston (1989) · Zbl 0721.68056 |
| [13] | Grefenstette, John J. Lamarckian learning in multi-agent environments. Navy Center For Applied Research in Artificial Intelligence Washington DC, (1995) · Zbl 1312.90038 |
| [14] | Holland, J.H.: Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press (1975) · Zbl 0317.68006 |
| [15] | Krumke, S., Wirth, H.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81-85 (1998) · Zbl 0938.90064 · doi:10.1016/S0020-0190(98)00034-9 |
| [16] | Moscato, P., Norman, M.G.: A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems. Parallel Comput. Transput. Appl. 1, 177-186 (1992) |
| [17] | Miettinen, K., Mäkelä, M.M., Neittaanmäki, P., Periaux, J. (eds.): Evolutionary algorithms in engineering and computer science. Wiley, Chichester (1999) · Zbl 0922.00027 |
| [18] | Nummela, J., Julstrom, B.: An effective genetic algorithm for the minimum-label spanning tree problem. In: GECCO ’06 Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 553-558 (2006) |
| [19] | Reed, J., Toombs, R., Barricelli, N.: Simulation of biological evolution and machine learning. I. Selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing. J. Theoret Biol. 17, 319-342 (1967) · doi:10.1016/0022-5193(67)90097-5 |
| [20] | Xiong, Y., Golden, B., Wasil, E.: A one-parameter genetic algorithm for the minimum labeling spanning tree problem. IEEE Trans. Evolut. Comput. 9(1), 55-60 (2005) · doi:10.1109/TEVC.2004.840145 |
| [21] | Xiong, Y., Golden, B., Wasil, E.: Improved heuristics for the minimum label spanning tree problem. IEEE Trans. Evol. Comput. 10(6), 700-703 (2006) · doi:10.1109/TEVC.2006.877147 |
| [22] | Whitley, D., Rana, S., Heckendorn, R.B.: The island model genetic algorithm: on separability, population size and convergence. J. Comput. Inf. Technol. 7, 33-48 (1999) |
| [23] | Latter, B.D.H.: The island model of population differentiation: a general solution. Genetics 73(1), 147-157 (1973) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
