×

zbMATH — the first resource for mathematics

An algebraic approach to population-based evolutionary algorithm generation. (English) Zbl 1351.68258
Xue, Jinyun (ed.) et al., Proceedings of the 6th international workshop on harnessing theories for tool support in software (TTSS 2013), Nanchang, China, October 27, 2013. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 309, 95-107, electronic only (2014).
Summary: Evolutionary algorithms (EAs) are popular in solving a diversity of problems, but current algorithm design approaches typically require formulating an algorithmic structure for each individual problem. The paper presents an algebraic framework for high-level specification of general-purpose metaheuristic methods, which cover a wide range of population-based EAs. Based on specification composition and refinement, the framework support mechanical program generation for concrete problem solving. We illustrate the applications of the framework in two typical optimization problems, which show that the proposed approach can achieve a high level of abstraction and mechanization without losing performance.
For the entire collection see [Zbl 1310.68021].
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q65 Abstract data types; algebraic specification
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beyer, H.-G.; Schwefel, H.-P., Evolution strategies - a comprehensive introduction, Natural Comput., 1, 3-52, (2002) · Zbl 1014.68134
[2] E. Bonabeau, M. Dorigo, G. Theraulaz, 4, Oxford University Press, New York, 1999.
[3] Claszen, I.; Ehrig, H.; Wolz, D., Algebraic specification techniques and tools for software development: the ACT approach, (1993), World Scientific
[4] Fogel, L. J.; Owens, A. J.; Walsh, M. J., Artificial intelligence through simulated evolution, (1967), John Wiley & Sons Chichester · Zbl 0148.40701
[5] Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence, (1992), MIT Press Cambridge, MA, USA
[6] Lowry, M., Algorithm synthesis through problem reformulation, (1989), Stanford University, Ph.D. thesis
[7] Partsch, H., Specification and transformation of programs: a formal approach to software development, (1990), Springer · Zbl 0751.68036
[8] Sannella, D.; Tarlecki, A., Essential concepts of algebraic specification and program development, Formal Aspects of Computing, 9, 229-269, (1997) · Zbl 0887.68070
[9] Simon, D., Biogeography-based optimization, IEEE Trans. Evol. Comput., 12, 702-713, (2008)
[10] Xue, J., A unified approach for developing efficient algorithmic programs, Journal of Computer Science and Technology, 12, 314-329, (1997)
[11] Xue, J., Formal derivation of graph algorithmic programs using partition-and-recur, Journal of Computer Science and Technology, 13, 553-561, (1998) · Zbl 0910.68090
[12] Xue, J., Par method and its supporting platform, (Proc. 1st Intl Workshop of Asian Working Conf. Verified Software, Macao, China, (2006)), 11-20
[13] Zheng, Y.; Shi, H.; Xue, J., Toward a unified implementation for dynamic programming, High Technology Letters, 12, 31-34, (2006)
[14] Zheng, Y.; Shi, H.; Xue, J., An algebraic approach to mechanical tabu search algorithm generation, (IEEE International Conference on Progress in Informatics and Computing, (2010)), 988-992
[15] Zheng, Y.; Xue, J., A problem reduction based approach to discrete optimization algorithm design, Computing, 88, 31-54, (2010) · Zbl 1192.68437
[16] Zheng, Y.; Xue, J.; Liu, W., Object-oriented specification composition and refinement via category theoretic computations, (Cai, J.-Y.; Cooper, S.; Li, A., Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 3959, (2006), Springer Berlin, Heidelberg), 601-610 · Zbl 1178.68145
[17] Zheng, Y.; Xue, J.; Shi, H., A category theoretic approach to search algorithms: towards a unified implementation for branch-and-bound and backtracking, (4th International Conference on Computer Science Education, (2009)), 845-850
[18] Zheng, Y.; Xue, J.; Zuo, Z., Toward an automatic approach to greedy algorithms, (Deng, X.; Hopcroft, J.; Xue, J., Frontiers in Algorithmics, Lecture Notes in Computer Science, vol. 5598, (2009), Springer Berlin, Heidelberg), 302-313 · Zbl 1248.68466
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.