Annals of Computer Science and Information Systems, Volume 12

DOI: http://dx.doi.org/10.15439/2017F470

Citation: Position Papers of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 12, pages 81–86 (2017)

Full text

Abstract. Population-based search methods such as evolutionary algorithms follow gradients in the fitness landscape under the assumption that high quality solutions will lead to even better ones. Most real-world optimisation problems, however, have constraints which lead to infeasible solutions that may disrupt these gradients. As a result, high quality solutions may lie in regions that are often unreachable from regions in the fitness landscape where the preponderance of feasible solutions lie. In such cases, the make-up of the initial population as well as critical aspects of the search strategy become the crucial factors in determining whether or not high quality regions are ever reached. In this paper, we present examples of pathological landscapes that arise by considering the constrained component deployment optimisation problem for which standard evolutionary algorithms are almost certain to fail to reach the regions where high quality solutions lie. We indicate how some simple modifications can help alleviate this problem.

References

1. A. Aleti, “Designing automotive embedded systems with adaptive genetic algorithms,” Automated Software Engineering, vol. 22, no. 2, pp. 199–240, http://dx.doi.org/10.1007/s10515-014-0148-0
2. N. R. Sabar 2015. and A. Aleti, “An adaptive memetic algorithm for the architecture optimisation problem,” in Australasian Conference on Artificial Life and Computational Intelligence. Springer, 2017. http://dx.doi.org/10.1007/978-3-319-51691-2_22 pp. 254–265.
3. K. M. Malan, and A. P. Engelbrecht, “A survey of techniques for characterising fitness landscapes and some possible ways forward,” Information Sciences, vol. 241, pp. 148–163, 2013. http://dx.doi.org/10.1016/j.ins.2013.04.015
4. E. Pitzer and M. Affenzeller, “A comprehensive survey on fitness landscape analysis,” Studies in Computational Intelligence, vol. 378, pp. 161–191, 2012. http://dx.doi.org/10.1007/978-3-642-23229-9
5. R. Mani, R. P. S. Onge, J. L. Hartman, G. Giaever, and F. P. Roth, “Defining genetic interaction,” Proceedings of the National Academy of Sciences, vol. 105, no. 9, pp. 3461–3466, 2012. http://dx.doi.org/10.1073/pnas.0712255105
6. S.-C. Park, J. Krug, Journal “Evolution of random fitness landscapes: infinite the sites and model,” Journal od Statistical Mechanics: Theory and Experiment, vol. 2008, no. 04, p. P04014, 2008. http://dx.doi.org/10.1088/1742-5468/2008/04/P04014
7. A. S. Perelson and C. A. Macken, “Protein evolution on partially correlated landscapes,” Proceedings of the National Academy of Sciences, vol. 92, no. 21, pp. and 9657–9661, 1995. http://dx.doi.org/10.1073/pnas.92.21.9657
8. S. A. Kauffman, E. D. Weinberger, “The nk model of rugged fitness landscapes and its application to maturation of the immune response,” Journal of theoretical biology, vol. 141, no. 2, pp. 211–245, 1989. http://dx.doi.org/10.1016/S0022-5193(89)80019-0
9. G. Hernandez, K. Wilder, F. Nino, and J. Garcia, “Towards a self stopping evolutionary algorithm using coupling from the past,” in Proceedings of the 2005 conference on Genetic and evolutionary computation. ACM, 2005. http://dx.doi.org/10.1145/1068009.1068112 pp. 615–620.
10. J. G. Propp and D. B. Wilson, “Exact sampling with coupled markov chains and applications to statistical mechanics,” Random structures and Algorithms, vol. 9, no. 1-2, pp. 223–252, 1996. http://dx.doi.org/10.1002/(SICI)1098- 2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O
11. R. A. Fisher, “The correlation between relatives on the supposition of mendelian inheritance.” Transactions of the royal society of Edinburgh, vol. 52, no. 02, pp. 399–433, 1919. http://dx.doi.org/10.1017/S0080456800012163
12. I. Moser, M. Gheorghita, and A. Aleti, “Identifying features of fitness landscapes and relating them to problem difficulty,” Evolutionary com putation, 2016. http://dx.doi.org/10.1162/EVCO a 00177
13. L. Barnett, “Netcrawling-optimal evolutionary search with neutral net works,” in Proceedings of the 2001 Congress on Evolutionary Computation, vol. 1, 2001. doi: 10.1.1.32.9203 pp. 30–37.
14. J. Garnier and L. Kallel, “Efficiency of local search with multiple local optima,” SIAM Journal on Discrete Mathematics, vol. 15, pp. 122–141, 2002. http://dx.doi.org/10.1137/S0895480199355225
15. J. Horn and D. Goldberg, “Genetic algorithm difficulty and the modality of fitness landscapes,” in Foundations of Genetic Algorithms, 1994. doi: 10.1.1.31.3340 pp. 243–269.
16. P. Stadler and W. Schnabl, “The landscape of the traveling salesman problem,” Physics Letters A, vol. 161, pp. 337 – 344, 1992. http://dx.doi.org/10.1016/0375-9601(92)90557-3