Incorporação de Técnicas de Tratamento de Restrição Baseadas em Penalidade na Meta-heurística de Nuvem de Partículas no contexto do Problema do Escalonamento e Atribuição de Tarefas em Projetos de Software
Resumo
O Problema do Escalonamento e Atribuição de Tarefas em Projetos de Software consiste na alocação de empregados a tarefas de forma a minimizar a duração e o custo do projeto. Para solucionar o problema algoritmos metaheurísticos têm sido aplicados, dentre eles a versão multiobjetivo do algoritmo Otimização por Nuvem de Partículas, SMPSO. No entanto, o algoritmo gera muitas soluções que violam alguma restrição, chamadas de soluções inválidas. Este trabalho investiga o impacto da incorporação ao SMPSO de técnicas de tratamento de restrição baseadas em penalidade, com objetivo de aumentar o número de soluções válidas geradas. Os resultados sugerem que a incorporação do tratamento de restrição melhora a qualidade das soluções geradas.
Palavras-chave:
Evolutionary Computation and Metaheuristics, Computational Intelligence
Referências
Afzal, W., Torkar, R., e Feldt, R. (2009). A systematic review of search-based testing for non-functional system properties. Information and Software Technology, 51(6):957 – 976.
Alba, E. e Chicano, J. F. (2007). Software project management with gas. Information Sciences, 177(11):2380 – 2401.
Andrade, J., Silva, L., Britto, A., e Amaral, R. (2019). Solving the Software Project Scheduling Problem with Hyper-heuristics, páginas 399–411.
Biju, A., Victoire, T., e Mohanasundaram, K. (2015). An improved differential evolution solution for software project scheduling problem. The Scientific World Journal, 2015.
Coello, C. A. C., Lamont, G. B., e Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems, volume 5. Springer.
Fonseca, C. M., Paquete, L., e López-Ibáñez, M. (2006). An improved dimension-sweep algorithm for the hypervolume indicator. In Proceedings of the Evolutionary Computation on 2006. CEC ’06. Proceedings of the 2006 Congress, CEC ’06, páginas 1157–1163.
Harman, M., McMinn, P., de Souza, J. T., e Yoo, S. (2012). Search Based Software Engineering: Techniques, Taxonomy, Tutorial, páginas 1–59. Springer Berlin Heidelberg, Berlin, Heidelberg.
Homaifar, A., X. Qi, C., e Lai, H.-Y. (1994). Constrained optimization via genetic algorithms. Transactions of The Society for Modeling and Simulation InternationalSIMULATION, 62:242–253.
Michalewicz, Z. e Schoenauer, M. (1996). Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 4(1):1–32.
Nebro, A., Durillo, J., García-Nieto, J., Coello Coello, C., Luna, F., e Alba, E. (2009). Smpso: A new pso-based metaheuristic for multi-objective optimization. páginas 66 – 73.
Rezende, A. V., Silva, L., Britto, A., e Amaral, R. (2019). Software project scheduling problem in the context of search-based software engineering: A systematic review. Journal of Systems and Software, 155:43 – 56.
Sievi-Korte, O. (2010). A survey on search-based software design. Computer Science Review, 4:203–249.
Standish Group (2014). Chaos report.
Tapia, M. G. C. e Coello, C. A. C. (2007). Applications of multi-objective evolutionary algorithms in economics and finance: A survey. In 2007 IEEE Congress on Evolutionary Computation, páginas 532–539.
Woldesenbet, Y. G., Yen, G. G., e Tessema, B. G. (2009). Constraint handling in multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation, 13(3):514–525.
Xiao, J., Ao, X.-T., e Tang, Y. (2013). Solving software project scheduling problems with ant colony optimization. Computers Operations Research, 40(1):33 – 46.
Zhang, Y., Finkelstein, A., e Harman, M. (2008). Search based requirements optimisation: Existing work and challenges. In Paech, B. e Rolland, C., editors, Requirements Engineering: Foundation for Software Quality, páginas 88–94, Berlin, Heidelberg. Springer Berlin Heidelberg.
Özgür, Y. (2005). Penalty function methods for constrained optimization with genetic algorithms. Mathematical and Computational Applications, 10:45–56.
Alba, E. e Chicano, J. F. (2007). Software project management with gas. Information Sciences, 177(11):2380 – 2401.
Andrade, J., Silva, L., Britto, A., e Amaral, R. (2019). Solving the Software Project Scheduling Problem with Hyper-heuristics, páginas 399–411.
Biju, A., Victoire, T., e Mohanasundaram, K. (2015). An improved differential evolution solution for software project scheduling problem. The Scientific World Journal, 2015.
Coello, C. A. C., Lamont, G. B., e Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems, volume 5. Springer.
Fonseca, C. M., Paquete, L., e López-Ibáñez, M. (2006). An improved dimension-sweep algorithm for the hypervolume indicator. In Proceedings of the Evolutionary Computation on 2006. CEC ’06. Proceedings of the 2006 Congress, CEC ’06, páginas 1157–1163.
Harman, M., McMinn, P., de Souza, J. T., e Yoo, S. (2012). Search Based Software Engineering: Techniques, Taxonomy, Tutorial, páginas 1–59. Springer Berlin Heidelberg, Berlin, Heidelberg.
Homaifar, A., X. Qi, C., e Lai, H.-Y. (1994). Constrained optimization via genetic algorithms. Transactions of The Society for Modeling and Simulation InternationalSIMULATION, 62:242–253.
Michalewicz, Z. e Schoenauer, M. (1996). Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 4(1):1–32.
Nebro, A., Durillo, J., García-Nieto, J., Coello Coello, C., Luna, F., e Alba, E. (2009). Smpso: A new pso-based metaheuristic for multi-objective optimization. páginas 66 – 73.
Rezende, A. V., Silva, L., Britto, A., e Amaral, R. (2019). Software project scheduling problem in the context of search-based software engineering: A systematic review. Journal of Systems and Software, 155:43 – 56.
Sievi-Korte, O. (2010). A survey on search-based software design. Computer Science Review, 4:203–249.
Standish Group (2014). Chaos report.
Tapia, M. G. C. e Coello, C. A. C. (2007). Applications of multi-objective evolutionary algorithms in economics and finance: A survey. In 2007 IEEE Congress on Evolutionary Computation, páginas 532–539.
Woldesenbet, Y. G., Yen, G. G., e Tessema, B. G. (2009). Constraint handling in multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation, 13(3):514–525.
Xiao, J., Ao, X.-T., e Tang, Y. (2013). Solving software project scheduling problems with ant colony optimization. Computers Operations Research, 40(1):33 – 46.
Zhang, Y., Finkelstein, A., e Harman, M. (2008). Search based requirements optimisation: Existing work and challenges. In Paech, B. e Rolland, C., editors, Requirements Engineering: Foundation for Software Quality, páginas 88–94, Berlin, Heidelberg. Springer Berlin Heidelberg.
Özgür, Y. (2005). Penalty function methods for constrained optimization with genetic algorithms. Mathematical and Computational Applications, 10:45–56.
Publicado
15/10/2019
Como Citar
SANTOS, Werthen; SILVA, Leila; BRITTO, André.
Incorporação de Técnicas de Tratamento de Restrição Baseadas em Penalidade na Meta-heurística de Nuvem de Partículas no contexto do Problema do Escalonamento e Atribuição de Tarefas em Projetos de Software. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 503-514.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9310.
