Annals of Computer Science and Information Systems, Volume 15

DOI: http://dx.doi.org/10.15439/2018F331

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 57–65 (2018)

Full text

Abstract. The usual assumption in the Evolutionary Computation field is that a cost of computing single fitness function evaluation is at last similar for all cases. Such assumption does not have to be true. In this paper we consider the recently proposed Problem Encoding Allowing Cheap Fitness Computation of Mutated Individuals (PEACh) effect that allows to significantly reduce the computation load of some of the fitness computations that occur during the evolutionary method run. To the best of our knowledge, it is the first experimental analysis that investigates the results of PEACh application to methods solving NP-hard practical problems.

References

1. L. Fratta M. Gerla, L. Kleinrock, “The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design,” Networks, vol. 3, no. 2, 1973, pp. 97-133.
2. D.E. Goldberg, B. Korb, K. Deb, “Messy genetic algorithms: Motivation, analysis, and first results,” Complex Systems, vol. 3, 1989, pp. 493-530.
3. B. W. Goldman, W. F. Punch, “Parameter-less Population Pyramid,” Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO ’14), ACM, 2014, pp. 785-792.
4. W. D. Grover, “Mesh-based Survivable Transport Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking,” Prentice Hall PTR, New Jersey, 2004.
5. S.-H. Hsu, T.-L. Yu, “Optimization by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II,” Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO ’15), ACM, 2015, pp. 519-526.
6. D.R. Jones, “A taxonomy of global optimization methods based on response surfaces,” Journal of Global Optimization, vol. 21, 2001, pp.345-383.
7. M. M. Komarnicki, M. W. Przewozniczek, “The influence of fitness caching on modern evolutionary methods and fair computation load measurement,” Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ’18), ACM, 2018, (in press).
8. H. Kwasnicka, M. Przewozniczek, “Multi Population Pattern Searching Algorithm: a new evolutionary method based on the idea of messy Genetic Algorithm,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 5, pp. 715-734, 2011.
9. P.B. Myszkowski, M. Przewozniczek, M. Skowronski, “Constructive heuristics for technology-driven Resource Constrained Scheduling Problem,” Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, 2015.
10. P.B. Myszkowski, M. Skowronski, L. Olech, K. Oslizlo, “Hybrid Ant Colony Optimization in solving Multi-Skill Resource-Constrained Project Scheduling Problem,” Soft Computing, vol. 19, issue 12, 2015, pp 3599-3619.
11. M. Pioro, D. Medhi, “Routing, Flow, and Capacity Design in Communication and Computer Networks,” Morgan Kaufmann Publishers, 2004.
12. R. J. Povinelli, X. Feng, “Improving Genetic Algorithms Performance By Hashing Fitness Values,” Artificial Neural Networks in Engineering, 1999, 399-404.
13. M. Przewozniczek, K. Walkowiak, “Quasi-hierarchical Evolutionary Algorithm for Flow Optimization in Survivable MPLS Networks ,” Lecture Notes in Computer Science, vol. 4707, Springer Verlag, 2007, pp. 330-342.
14. M. Przewozniczek, R. Goscien, K. Walkowiak, M. Klinkowski, “Towards Solving Practical Problems of Large Solution Space Using a Novel Pattern Searching Hybrid Evolutionary Algorithm - An Elastic Optical Network Optimization Case Study” in Expert Systems with Applications,” vol. 42, 2015, pp. 7781-7796.
15. M. Przewozniczek, “Active Multi Population Pattern Searching Algorithm for Flow Optimization in Computer Networks - the novel coevolution schema combined with linkage learning,” Information Sciences, vol. 355-356, 2016, pp. 15-36.
16. M. W. Przewozniczek, K. Walkowiak, M. Aibin, “The evolutionary cost of Baldwin effect in the routing and spectrum allocation problem in elastic optical networks,” Applied Soft Computing, vol. 52, 2017, pp. 843-862.
17. M. W. Przewozniczek, “Problem Encoding Allowing Cheap Fitness Computation of Mutated Individuals,” Proceedings of 2017 Congress on Evolutionary Computation (CEC 2017), 2017, pp. 308-316.
18. D. Thierens, P.A.N. Bosman, “Hierarchical Problem Solving with the Linkage Tree Genetic Algorithm,” Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO âĂŹ13), 2013, pp. 877-884.
19. F. Zhang , X. Zheng, H. Zhang, Y. Guo, “A kind of topology aggregation algorithm in hierarchical wavelength-routed optical networks,” Photonic Network Communications, vol. 9, 2005, pp. 167-180.