tcc_engenharia de software baseada em busca para a otimizao nsga-ii

Prévia do material em texto

UNIVERSIDADE FEDERAL DE RORAIMA 
CENTRO DE CIÊNCIA E TECNOLOGIA 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
CURSO DE CIÊNCIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
Engenharia de Software Baseada em Busca para a Otimização 
Multiobjetivo de Requisitos Utilizando o Algoritmo NSGA-II. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Boa Vista, RR 
2017 
 
 
 
 
 
 
 Dados Internacionais de Catalogação na publicação (CIP) 
 Biblioteca Central da Universidade Federal de Roraima 
 
S237e Santos, Gleysomar Ribeiro dos. 
Engenharia de software baseada em busca para a otimização multiobjectivo 
de requisitos utilizando o algoritmo NSGA-II / Gleysomar Ribeiro dos Santos. – 
Boa Vista, 2017. 
97 f. : il. 
Orientador: Prof. M.e Miguel Raymundo Flores Santibanez. 
Coorientadora: Profa. M.a Delfa Mercedes Huatuco Zuasnábar. 
 
Monografia (graduação) – Universidade Federal de Roraima, Curso de Ciência 
da Computação. 
 
1 – Engenharia de software baseado em busca. 2 – Algoritmos genéticos. 3 – 
Otimização multiobjetivo. 4 – Metaheurística. 5 – Requisitos de software. I – 
Título. II – Santibanez, Miguel Raymundo Flores (orientador). III – Zuasnábar, 
Delfa Mercedes Huatuco (coorientadora). 
 
CDU – 681.3.06 
 
 
GLEYSOMAR RIBEIRO DOS SANTOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Engenharia de Software Baseada em Busca para a Otimização 
Multiobjetivo de Requisitos Utilizando o Algoritmo NSGA-II. 
 
 
 
 
Projeto de pesquisa apresentado ao Curso de 
Bacharelado em Ciência da Computação do 
Departamento de Ciência da Computação da 
Universidade Federal de Roraima. 
 
Orientador: Prof. MSc. Miguel Raymundo 
Flores Santibanez. 
 
Coorientadora: Prof. MSc. Delfa Mercedes 
Huatuco Zuasnábar 
 
 
 
 
 
Boa Vista, RR 
2017
 
 
GLEYSOMAR RIBEIRO DOS SANTOS 
 
 
 
 
Engenharia de Software Baseada em Busca para a Otimização Multiobjetivo de 
Requisitos Utilizando o Algoritmo NSGA-II. 
 
 
 
 
Pesquisa apresentada ao Curso de Bacharelado 
em Ciência da Computação do Departamento 
de Ciência da Computação da Universidade 
Federal de Roraima como pré-requisito à 
obtenção do título de Bacharel em Ciência da 
computação, defendido em 01 de agosto de 
2017 e avaliada pela seguinte banca 
examinadora: 
 
 
______________________________________ 
Profº MSc. Miguel Raymundo Flores Santibanez 
Orientador / Curso de Ciência da Computação - UFRR 
 
 
______________________________________ 
Membro 1 /Profª MSc. Delfa Mercedes Huatuco Zuasnábar 
Curso de Ciência da Computação – UFRR 
 
 
______________________________________ 
Membro 2 /Profº MSc. Acauan Cardoso Ribeiro 
Curso de Ciência da Computação – UFRR 
 
 
 
 
 
 
 
 
 
 
 
AGRADECIMENTOS 
 
 
 
Primeiramente, sem Deus nada é possível, agradeço pela oportunidade de todos os dias 
de minha vida. Segundamente aos meus pais, que se dispuseram a mudar de cidade para me 
acompanhar nessa jornada universitária e que deram todo o suporte, carinho, dedicação, apoio 
existentes neste mundo e vou sentir-me sempre em débito com vocês. 
Ao meu Orientador Miguel Raymundo Flores Santibanez e Coorientadora MSc. Delfa 
Mercedes Huatuco Zuasnábar, por acreditar na minha capacidade e esforço para a elaboração 
desse projeto. 
Ao corpo Docente do Departamento de Ciência da Computação da Universidade Federal 
de Roraima, sem vocês essa formação não teria acontecido. 
A todos meus amigos que muitas vezes resgataram minhas forças e ajudaram a continuar 
a luta, apesar de todas as dificuldades que passei durante a Universidade. Não poderia deixar 
de citar aos meus amigos Alex Medeiros, Liliane Soares, Leandro Sales e Jéssica Ramalho. 
Eles fizeram a diferença em sala de aula e no meu ciclo de amizades, sempre tive apoio deles 
em todos os momentos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Se cheguei até aqui foi porque me 
apoiei no ombro dos gigantes. 
(Issaac Newton)
 
 
RESUMO 
 
Engenharia de Software e Sistema de Busca são áreas promissoras e têm fomentado diversos 
estudos relacionados a estas temáticas. Grande parte das metodologias tradicionais de Software 
não são capazes de resolver problemas no levantamento de requisitos, ou o fazem de modo 
insatisfatório. As problemáticas deste tipo de levantamento, podem ser utilizadas de forma 
automatizadas, com o objetivo de serem resolvidas de maneira eficiente. Neste sentido, uma 
importante área presente no desenvolvimento de software é a Engenharia de Requisitos. Tal 
fase contém alta complexidade, principalmente na definição de quais requisitos devem ser 
implementados para a próxima versão do sistema, considerando a satisfação do cliente, custos 
de implementação e restrições de orçamento. E, para atender tais necessidades, foram 
desenvolvidas técnicas de buscas em 1976, denominadas Search-based Software Engineering 
- SBES e, desde então, têm sido abordadas nas áreas de análise de requisitos, otimização de 
códigos, entre outros. E para a realização da modelagem nesta pesquisa, foram implementadas 
métricas, por ponto de função na aplicação do Repositório Digital de Apoio à Pesquisa, com o 
intuito de obter os custos e, por fim, foi aplicado o Algoritmo Genético NSGA-II, para que estes 
problemas pudessem ser tratados de forma automatizadas, através de algoritmo de busca, 
resultando na otimização destes requisitos. 
 
Palavra-chave: Engenharia de Software Baseado em Busca, Algoritmos Genéticos, Otimização 
Multiobjetivo, Metaheurística e Requisitos de Software. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ABSTRACT 
 
Software Engineering and Search System are promising areas and have promoted several 
studies related to these topics. Most of the traditional software methodologies are not able to 
solve problems in the requirements survey, or they do it in an unsatisfactory way. The problems 
of this type of survey can be used in an automated way, with the objective of being solved in 
an efficient way. In this sense, an important area present in software development is 
Requirements Engineering. Such a phase contains high complexity, especially in defining what 
requirements should be implemented for the next version of the system, considering customer 
satisfaction, implementation costs, and budget constraints. To meet these needs, search 
techniques were developed in 1976, called Search-based Software Engineering (SBES), and 
have since been addressed in the areas of requirements analysis, code optimization, among 
others. In order to perform the modeling in this research, metrics were implemented per function 
point in the application of the Digital Repository of Research Support, in order to obtain the 
costs and, finally, the NSGA-II Genetic Algorithm was applied, so that These problems could 
be treated in an automated way, through a search algorithm, resulting in the optimization of 
these requirements. 
 
Keywords: Software Engineering based on Search, Genetic Algorithms, Multiobjective 
Optimization, Metaheuristics and Software Requirements.Metaheuristics and Software 
Requirements. 
 
 
 
 
 
 
 
 
 
 
LISTA DE SIGLAS 
 
 
 
 
 
ACO Ant Colony Optimization 
AEs Algoritmos Evolutivos 
AG Algoritmo Genético 
AM Algoritmo Multiobjetivo 
APF Análise por Pontos de Funções 
ER Engenharia de Requisitos 
ES Engenharia de Software 
IFPUG International Funtion Point User Group 
NSGA-II Non-dominated Sorting Genetic Algorithm 
PCU Pontos por Caso de Usos 
PF Ponto de Fução 
SBSE Search-based Software Engineering 
SPEA-II Strength Pareto Evolutionary Algorithm II 
VEGA Vector Evaluated Genetic Algorithm 
XP Extreme Programming 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LISTA FIGURA 
 
 
Figura 1 - Exemplo de um processo de engenharia de requisitos ............................................19 
Figura 2 - Custo para corrigir um defeito dependendo de quando é descoberto ...................... 22 
Figura 3 - Representação matemática ....................................................................................... 25 
Figura 4 - Esbouço da região admissível. ................................................................................. 25 
Figura 5 - Função de Otimização. ............................................................................................ 28 
Figura 6 - Exemplo que ilustra várias opções de compra de carro (1-5), considerando o 
seu custo e conforto. ................................................................................................................. 29 
Figura 7 - Distribuição de Soluções na Fronteira de Pareto. .................................................... 30 
Figura 8 - Diagrama de Sequência do Algoritmo Genético. .................................................... 35 
Figura 9 - Exemplificação do Algoritmo Genético. ................................................................. 36 
Figura 10 - Procedimento NSGA-II. ........................................................................................ 43 
Figura 11 - Algoritmo NSGA-II - Classificação Não Dominada. ............................................ 44 
Figura 12 - Algoritmo do NSGA-II (CrowdingDistance). ....................................................... 45 
Figura 13 - Algoritmo do NSGA-II (main loop). .................................................................... 46 
Figura 14 - Tempo de execução em milissegundos e desvio padrão........................................ 51 
Figura 15 - Possível propagação de otimização requisitos ideais. ........................................... 55 
Figura 16 - Primeira Interface do Repositório Digital. ............................................................. 60 
Figura 17 - Segunda Interface do Repositório Digital. ............................................................. 60 
Figura 18 - Arquitetura do Repositório Digital. ....................................................................... 62 
Figura 19 -Diagrama de Caso de Uso do Repositório Digital. ................................................ 63 
Figura 20- Diagrama de Classe do Repositório Digital. ........................................................... 63 
Figura 21 -Representa os objetivos a serem otimizado em relação a F1 e F2 .......................... 76 
Figura 22 - Representação dos cromossomos para cada função. ............................................. 77 
Figura 23 - Exemplo de Distância Euclidiana ......................................................................... 77 
Figura 24 - Simulação do NSGA-II. ......................................................................................... 82 
Figura 25 - Simulação do NSGA-II Requisitos Versus Custos. ............................................... 83 
Figura 26 - Resultado com uma População 100 e 50 Iterações. ............................................... 84 
Figura 27 - Resultado com População 100 e 100 Iterações. ..................................................... 85 
Figura 28 - Resultado com uma População 100 e 200 Iterações. ............................................. 85 
Figura 29 - Comparando os Resultados da Tabela 22. ............................................................. 87 
Figura 30 - Simulação do Algoritmo Randômico. ................................................................... 88 
file:///C:/Users/Gleysson%20Ribeiro/Dropbox/TCC%202%20-%20Gleysomar/TCC2%20GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS/GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS_TCC02_FINAL.docx%23_Toc492928635
file:///C:/Users/Gleysson%20Ribeiro/Dropbox/TCC%202%20-%20Gleysomar/TCC2%20GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS/GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS_TCC02_FINAL.docx%23_Toc492928647
file:///C:/Users/Gleysson%20Ribeiro/Dropbox/TCC%202%20-%20Gleysomar/TCC2%20GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS/GLEYSOMAR%20RIBEIRO%20DOS%20SANTOS_TCC02_FINAL.docx%23_Toc492928648
 
 
Figura 31 - Caso A. .................................................................................................................. 89 
Figura 32 - Caso B. ................................................................................................................... 89 
Figura 33 - Caso C. ................................................................................................................... 90 
Figura 34 - Comparação (X) NSGA-II e (Y) – Randômico. ................................................. 90 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LISTA DE TABELAS 
 
 
Tabela 1 - SBSE em diversas áreas da Engenharia de Software .............................................. 49 
Tabela 2 - Requisitos Funcionais (RF) do Repositório Digital ................................................ 61 
Tabela 3 - Requisitos Não Funcionais (RNF) do Repositório .................................................. 61 
Tabela 4 – Complexidade Funcional de Entrada Externa ........................................................ 66 
Tabela 5 - Complexidade Funciona Saída e Consultas .......................................................... 66 
Tabela 6 - complexidade Funcional de Arquivo interno e externo .......................................... 66 
Tabela 7 - Ponto de Função Não Ajustados por Tipo e Complexidade de Função .................. 67 
Tabela 8 - Identificação das funções a partir dos requisitos ..................................................... 67 
Tabela 9- Técnica de pontos de função sugere 14 fatores ........................................................ 68 
Tabela 10 - Complexidade dos atores....................................................................................... 69 
Tabela 11 - Tipo de Ator Complexidade .................................................................................. 69 
Tabela 12 - Cálculo da complexidade do caso de uso - UUCW ............................................. 70 
Tabela 13 - Fatores técnicos de ajuste de pontos de caso de uso ............................................. 70 
Tabela 14 - Fatores ambientais de ajuste de pontos de caso de uso ......................................... 71 
Tabela 15 - Comparativo de Ponto de Função Ajustado e Pontos de Caso de Uso. ................ 72 
Tabela 16 - Valores de custo .................................................................................................... 73 
Tabela 17 - Matriz clientes versus importância de requisitos .................................................. 75 
Tabela 18 - Matriz custos dos requisitos .................................................................................. 75 
Tabela 19 Parâmetros do NSGA-II .......................................................................................... 79 
Tabela 20 Parâmetro do Randômico ........................................................................................ 81 
Tabela 21 - Testes de Parâmetros no NSGA-II – Cenário 1 .................................................... 83 
Tabela 22 - Testes de Parâmetros no NSGA-II – Cenário 2 .................................................... 86 
Tabela 23 - Testes do Tamanho da População do Randômico ................................................. 88 
 
 
 
13 
 
 
SUMÁRIO 
 
1 INTRODUÇÃO ......................................................................................................... 15 
1.1 MOTIVAÇÃO ............................................................................................................. 15 
1.2 OBJETIVOS ................................................................................................................ 16 
1.2.1 Objetivo Geral ........................................................................................................... 16 
1.2.2 Objetivos Específicos .................................................................................................17 
1. 3 ORGANIZAÇÃO DO DOCUMENTO ...................................................................... 17 
2. FUNDAMENTAÇÃO TEÓRICA ............................................................................ 18 
2.1 ENGENHARIA DE REQUISITOS ............................................................................ 18 
2.1.1 Elicitação de Requisitos ............................................................................................ 19 
2.2 MÉTRICAS ................................................................................................................. 22 
2.3 OTIMIZAÇÃO MATEMÁTICA ................................................................................ 24 
2.3.1 Otimização MonoObjetivo ........................................................................................ 25 
2.3.2 Otimização Multiobjetivo ......................................................................................... 26 
2.3.3 Avaliação Multiobjetivo ............................................................................................ 27 
2.3.3.1 Formulação ................................................................................................................ 27 
2.3.3.2 Soluções Pareto Ótimo .............................................................................................. 28 
2.4 ALGORITMOS EVOLUTIVOS ................................................................................. 31 
2.4.1 Algoritmos Genéticos ................................................................................................ 33 
2.4.1.1 Vantagens e Desvantagens dos Algoritmos Genéticos ........................................... 38 
2.4.2 SPEA II ou Algoritmo Evolutivo da Força do Pareto ............................................ 39 
2.4.3 Vega .............................................................................................................................40 
2.4.4 Otimização por Colônia de Formiga ........................................................................ 40 
2.4.5 NSGA II ou Algoritmo Genético de Classificação por Não Dominância II ........ 41 
2.5 ENGENHARIA DE SOFTWARE BASEADA EM BUSCAS ................................... 48 
2.6 CONSIDERAÇÕES FINAIS DO CAPÍTULO ........................................................... 49 
3 TRABALHOS RELACIONADOS ........................................................................... 50 
3.1 SELEÇÃO DE ELEMENTOS DE ELICITAÇÃO DE REQUISITOS UTILIZANDO 
ALGORITMOS EVOLUTIVOS MULTIOBJETIVOS ............................................... 50 
3.2 .....UMA ABORDAGEM BASEADA EM OTIMIZAÇÃO PARA A PRIORIZAÇÃO DE 
............REQUISITOS DE SOFTWARE CONSIDERANDO A ESTABILIDADE DO 
............REQUISITO. ................................................................................................................ 52 
3.3 SELEÇÃO E OTIMIZAÇÃO DE REQUISITOS BASEADO EM BUSCA 
MULTIOBJETIVO ....................................................................................................... 54 
3.4 CONSIDERAÇÕES FINAIS DO CAPÍTULO ............................................................ 58 
14 
 
 
4 ENGENHARIA DE SOFTWARE BASEADA EM BUSCA PARA A 
OTIMIZAÇÃO MULTIOBJETIVO DE REQUISITOS UTILIZANDO O 
ALGORITMO NSGA-II. ........................................................................................... 59 
4.1 IDENTIFICAÇÃO E MODELAGEM DOS REQUISITOS ....................................... 59 
4.2 METRICAS DO REPOSITÓRIO DIGITAL ............................................................... 64 
4.2.1 Análise por Pontos de Funções (APF) ...................................................................... 65 
4.2.2 Pontos Por Caso de Usos ............................................................................................ 69 
4.3 FERRAMENTA COMPUTACIONAL E AMBIENTE .............................................. 73 
4.4 MODELAGEM DO PROBLEMA PARA O ALGORITMO NSGAII ....................... 74 
4.4.1 Representação do Algoritmo no Matlab ................................................................... 78 
4.4.1.1 Parâmetros do Algoritmo NSGA-II ......................................................................... 78 
4.4.1.2 Parâmetros do Algoritmo Randômico ..................................................................... 80 
4.5 RESULTADOS ........................................................................................................... 81 
4.5.1 Simulação NSGA-II ................................................................................................... 82 
4.5.2 Simulação Randômica ............................................................................................... 87 
5 CONCLUSÃO ............................................................................................................ 92 
5.1 CONSIDERAÇÕES FINAIS ...................................................................................... 92 
5.2 TRABALHOS FUTUROS .......................................................................................... 93 
REFERÊNCIAS ..................................................................................................................... 95 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
15 
 
 
1 INTRODUÇÃO 
1.1 MOTIVAÇÃO 
A medida que o software vem evoluindo mais complexo tende a ficar. Uma 
consequência é um crescimento na complexidade de extensão dos sistemas de software 
modernos, e um concomitante aumento do esforço de desenvolvimento considerando tempo e 
custo. Empresas de desenvolvimento de software têm de satisfazer de forma eficiente grandes 
conjuntos de requisitos, minimizando os custos de produção de projetos de software. Na maioria 
dos casos, não é possível desenvolver todas as novas características originalmente sugeridas. 
A ER é um fator primordial na elaboração de um projeto de software, principalmente a 
elicitação de requisitos. Freitas et al (2009) explica que o objetivo da ER é entender as 
necessidades dos clientes e possibilitar a implementação dessas necessidades no software 
desenvolvido. 
 A partir do momento em que se inicia o desenvolvimento de um produto de software, 
existe um processo manual de interação entre o cliente e o analista, onde o analista tenta 
absorver o máximo possível de informação. Porém, nem sempre essas informações são de fato 
assimiladas. Portanto, há detalhes que acabam fazendo uma grande diferença no processo de 
desenvolvimento do software. E isto acaba impactando no projeto de forma sucinta, gerando 
tempo para identificar o erro, o custo acaba se elevando e deixando os clientes insatisfeitos. 
Muitos problemas dentro da engenharia apresentam uma coleção de objetivos a serem 
otimizados que são, na maioria das vezes, conflitantes entre si, ou seja, é impossível melhorar 
um objetivo sem deteriorar algum outro (VITA, 2008). Estes problemas são conhecidos como 
Multiobjetivo ou multicritério e distinguem-se dos problemas clássicos de otimização 
Monoobjetivo quanto ao sentido que o conceito de solução do problema. Por se tratar de 
objetivos conflitantes, na otimização multiobjetivo cada objetivo corresponde a uma solução 
ótima. Isso faz com que esses problemas apresentem um conjuntos de soluções ótimas 
(AMORIM, 2006). 
Visando nisso, surgiram técnicas automatizadas para resolver esse tipo de problema na 
área de Engenharia de Requisitos (RE). A Engenharia de Software Baseado em Busca, 
conhecida por Search Based Software Engineering - SBSE. A SBSE se tornou fortemente a 
partir de 2010, onde vários trabalhos científicos foram publicados afim de solucionar esse 
problema da Engenharia de Software (ES). 
A otimização de requisitos de software é uma tarefa importante em Engenharia de 
Software, e é especialmenterelevante na gestão de abordagens de desenvolvimento de software 
16 
 
 
incrementais, como os métodos ágeis. Nestes métodos, o produto de software é desenvolvido 
através da geração de versões que são produzidas em ciclos iterativos curtos. Em cada iteração, 
um novo conjunto de requisitos é proposto, sob medida para atender às necessidades dos 
clientes e os custos de desenvolvimento. Neste contexto, o desafio consiste em definir quais 
requisitos devem ser desenvolvidas levando em consideração vários fatores complexos 
(prioridades dadas a diferentes clientes, que têm diferentes níveis de importância para a 
empresa, os esforços de desenvolvimento, restrições de custo, as interações entre diferentes 
requisitos, etc.). 
Existem técnicas que podem ser aplicadas dentro da área de ER, como o Algoritmos 
Genéticos- AGs e as técnicas de Computação Evolucionária. A dificuldade de obtenção de 
soluções ótimas pelos métodos convencionais de otimizações faz dos Algoritmos 
Evolucionários (AEs) umas das técnicas mais eficientes para a otimização multiobjetivo. 
Entretanto, a tomada de decisões implica num processo que consiste em vários fatores, com o 
objetivo de encontrar a melhor solução (FERNANDES, 2005). 
Neste contexto, esse trabalho tem como objetivo principal utilizar esses métodos e 
técnicas de buscas, em especial as metaheurísticas, aplicando algoritmo evolutivos NSGAII -
Non-dominated Sorting Genetic Algorithm, onde será aplicado na elicitação de requisitos na 
fase dos requisitos funcionais na engenharia de software, trabalhando com técnicas de 
otimização. Ou seja, temos como problemática maximizar o grau de satisfação do cliente e 
minimizar o custo o máximo possível. 
Utilizamos a abordagem de otimização aplicado aos dados obtidos do trabalho de 
conclusão de curso TCC “Protótipo de um Repositório Digital de Apoio à Pesquisa Usando XP 
em Software com Serviço” (Matos 2017). Extraímos os requisitos do repositório para a 
realização dos testes de otimização utilizando algoritmo genético que é a proposta deste TCC. 
Assim, demostrando e analisando esses resultados da otimização. 
 
1.2 OBJETIVOS 
1.2.1 Objetivo Geral 
Aplicar o algoritmo de busca Metaheurística Multiobjetivo para a Otimização na 
Elicitação de Requisitos Funcionais do Repositório Digital de apoio à pesquisa 
utilizando algoritmo genético NSGAII. 
17 
 
 
1.2.2 Objetivos Específicos 
Para alcançar o objetivo geral, alguns objetivos específicos são requeridos, entre 
eles: 
1 analisar o panorama atual da área de Engenharia de Software Baseado em Busca, 
detalhando as fases dos Requisitos, Métricas e Algoritmos de Busca 
Multiobjetivo; 
2 modelar os requisitos Funcionais e não Funcionais do Repositório Digital de 
Apoio à Pesquisa; 
3 utilizar as Métricas de Pontos por Função e Caso de Uso para dimensionar a 
modelagem; 
4 aplicar o algoritmo NSGA-II e Randômico para a Otimização de Requisitos; 
5 avaliar os resultados obtidos através de testes realizados com Algoritmo 
Genético NSGAII e Randômico. 
1.3 ORGANIZAÇÃO DO DOCUMENTO 
 No primeiro capítulo apresentou a introdução, a motivação e os objetivos para o 
desenvolvimento do trabalho. O segundo capítulo traz a fundamentação teórica para a 
contextualização do leitor. O terceiro capítulo descreve os trabalhos desenvolvidos por outros 
pesquisadores que se relacionam a esta pesquisa. O quarto capítulo aborda a modelagem da 
pesquisa com os requisitos e analise dos resultados. O quinto capítulo a conclusão do trabalho 
exposto e trabalhos futuros. 
18 
 
 
 2. FUNDAMENTAÇÃO TEÓRICA 
 
Para levantar as informações necessárias ao desenvolvimento do projeto, foram realizados 
pesquisas e estudos em livros, periódicos, artigos e sites de Internet, focando nos objetivos desta 
pesquisa. Entre as informações levantadas destacam-se conceitos da área de Engenharia de 
Software e Inteligência Artificial com ênfase em Algoritmo Genético NSGAII. 
2.1 ENGENHARIA DE REQUISITOS 
 A Engenharia de Requisitos estabelece uma base sólida para construção do software. 
Sem ela, o software resultante tem a grande probabilidade de não atender às necessidades do 
cliente, afirma Pressman (2011). 
Segundo Pohl (2001) o impacto da Engenharia de Requisitos (ER) no desenvolvimento 
de sistemas de sucesso e focado no cliente não pode mais ser ignorado. Tornou-se prática 
comum destinar recursos à engenharia de requisitos. Além disso, é cada vez maior a 
compreensão o papel do engenheiro de requisitos é claramente diferenciado e abrangente uma 
série de atividades complexas. 
Moraes (2008) afirma que o termo requisito como uma declaração que identifica uma 
capacidade, característica física, ou fator de qualidade que ressalta uma necessidade de um 
produto ou processo para o qual uma solução será adotada. Esta definição traz um aspecto 
interessante, pois fala das necessidades não só de um produto, mas também de processo, além 
de mencionar que um requisito pode, também, ser um fator de qualidade. 
 Entretanto, Pressman (2011) diz que projetar e construir software é desafiador, criativo 
e pura diversão. Na realidade, construir software é tão cativante que muitos desenvolvedores 
desejam iniciar logo, antes de terem um claro entendimento daquilo que é necessário. 
Argumentam que as coisas ficarão mais claras à medida que forem construindo o software, que 
os interessados no projeto serão capazes de entender a necessidade apenas depois de examinar 
as primeiras iterações do software, que as coisas mudam tão rápido que qualquer tentativa de 
entender os requisitos de forma detalhada será uma perda de tempo, que o primordial é produzir 
um programa que funcione e que todo o resto é secundário. 
Segundo Bezerra (2015) o produto do levantamento de requisitos é o documento de 
requisitos, que declara os diversos tipos de requisitos do sistema. Esse documento deve ser 
escrito em uma notação informal (em linguagem natural). 
 
 
 
19 
 
 
A Figura 1 apresenta o processo de levantamento de requisitos. 
Figura 1 - Exemplo de um processo de engenharia de requisitos 
 
Fonte: Tsui; Karam (2013) 
 
Durante o processo de desenvolvimento e implementação de um software, são muitos os 
problemas que podem acontecer relacionados à base da construção do software, ou seja, os 
requisitos desse software podem gerar um impacto negativo no final da construção. Requisitos 
incompletos ou defeituosos podem causar problemas no produto final (BARBOSA, 2013). E 
isso acontece devido à má elicitação de requisitos durante o processo de identificação desses 
requisitos do software. 
2.1.1 Elicitação de Requisitos 
O termo elicitar, de acordo com Leite (1994) pode ser definido como: definir, tornar 
explícito, obter o máximo de informação sobre o objeto em questão. Também no Dicionário 
Aurélio (Aurélio, 1999), encontra-se dentre outras as seguintes definições do termo: fazer sair; 
extrair uma resposta ou reação de um informante, extrair enunciados ou julgamentos 
linguísticos de um informante. 
Barbosa (2013) diz que a elicitação de requisitos geralmente executada por uma 
metodologia ou uma série de técnicas, com o objetivo comum de dar aos analistas o 
entendimento necessário sobre o problema. Embora alguns analistas acreditem que uma única 
metodologia ou técnica possa ser aplicada em todas as situações, vários pesquisadores afirmam 
que não existe uma única capaz de suportar a resolução de todas as dificuldades das várias 
situações de um problema. 
 Os requisitos podem ser classificados de várias formas, a finalidade desta classificação é 
melhor compreender a relação entre objetos, tarefas e as próprias funções do sistema. Uma 
forma bastante aceitável entre analista é que a classificação seja entre requisitos funcionais e 
não funcionais. Os Requisitos Funcionais são especificações do sistema deve ser completa e 
consistente. Ou seja, esses requisitos funcionaisé uma interação entre o sistema e o seu 
ambiente com algumas funcionalidades especificas do sistema, já os Requisitos Não Funcionais 
20 
 
 
estão relacionados ao uso da aplicação em termos de desempenho, usabilidade, confiabilidade, 
disponibilidade, segurança e tecnologias envolvidas. São também conhecidos como requisitos 
de qualidade, que impõem restrições sobre o projeto ou execução (SOMMERVILLE, 2011). 
Para Barbosa (2013), o principal objetivo da Engenharia de Requisitos é criar e manter 
documentos de requisitos de sistemas. O processo de ER, como o todo, contém quatro grandes 
sub-processos que são: a) utilidade do software ao negócio (viabilidade), b) descoberta de 
requisitos (elicitação), c) conversão de tais requisitos em um formato padrão (especificação) e 
d) descoberta de quais requisitos realmente definem o sistema tal como usuário deseja 
(validação). 
Segundo Silva e Silva (2011), os requisitos gerados de acordo com técnicas de obtenção 
de requisitos devem refletir as reais necessidades do usuário, sendo consistentes, completos e 
compreensíveis a ele estabelecendo um elo entre o desenvolvedor e o usuário do sistema, de 
forma que as informações sejam captadas corretamente. As informações bem entendidas evitam 
retrabalhos, atrasos de cronogramas, custos mais altos, insatisfações do cliente, entre outros 
prejuízos. 
O mesmo descreve que no processo da Engenharia de Requisitos, há uma variedade de 
técnicas de elicitação utilizadas para se identificar os fatos que compõem os requisitos de um 
sistema. Sendo destacadas as seguintes: 
➢ Realização de entrevistas (fechadas e abertas) com diferentes stakeholders para 
se obter um entendimento preciso sobre os requisitos do sistema; 
➢ O uso de cenários é usado como uma técnica de representação de situações 
durante a análise de um sistema de informação, a fim de expressar os objetivos 
dos usuários desse sistema; 
➢ O uso de Protótipos como uma versão inicial do sistema para experimentação. 
Os esboços das telas serviram como uma linguagem mais informal e acessível aos 
futuros usuários. Este é o modo mais concreto de exibir ao cliente como suas 
informações se transformarão no sistema desejado. 
➢ O uso de Diagramas de Caso de Uso servindo como referência para as atividades 
de implementação. 
Durante o levantamento nem sempre esses requisitos são identificados de forma bem 
detalhada e acabam passando por despercebido os requisitos que deveriam ser priorizados na 
fase de desenvolvimento. E isso acaba impactando no custo total do projeto, demando um tempo 
a mais e a insatisfação do cliente. 
21 
 
 
Em Sommerville (2003) os problemas que os engenheiros de Software têm para 
solucionar são, muitas vezes, imensamente complexos. Compreender a natureza dos problemas 
pode ser muito difícil, especialmente se o sistema for novo. 
Segundo Barbosa (2013), raramente, durante o desenvolvimento de um software, é 
dedicado tempo para coletar dados, tais como indicadores de qualidades ou cumprimento de 
prazos, que estimam sobre o processo de desenvolvimento em si. Devido à pouca qualidade 
deste tipo de informação, as tentativas de estimar a duração/custo de produção de um software 
têm conduzido resultados bastante insatisfatórios como atraso na entrega ou orçamento acima 
do estimado; além disso, a falta destas informações impede uma avaliação eficientes das 
técnicas e metodologias implementadas no desenvolvimento. 
Um grande problema enfrentado pelas empresas de desenvolvimentos e manutenção de 
grandes e complexos sistemas desenvolvidos para grandes e diversificados clientes é o 
determinar quais requisitos vão ser implementados na próxima release do software 
(BEGNALL, 2001). 
Já para Zowghi (2002 apud BARBOSA, 2013) define que os requisitos são fundamentais 
no processo de desenvolvimento de software. São eles que proporcionam as bases para estimar 
custo e esforço, além de permitir a elaboração das estimativas do desenvolvimento e 
especificações de teste. Embora um conjunto inicial possa ser bem documentado, requisitos 
mudarão durante o ciclo de vida de desenvolvimento do software. Essas constantes mudanças 
(adições, exclusões e modificações) nos requisitos durante o ciclo de desenvolvimento 
impactarão nas estimativas dos custos, tempo e qualidade do produto resultante. 
Idealmente, os requisitos aprovados pelo cliente devem ficar estabilizados ou com um 
conjunto mínimo de mudanças. Mudanças de requisitos devem declinar de 3% no início do 
projeto para 1% na fase de codificação e, idealmente, para 0% durante os testes. No entanto, os 
requisitos sempre mudam e isso pode ter um efeito negativo durante o estágio de 
desenvolvimento do software. Requisitos que mudam durante a fase de codificação tendem 
aumentar a quantidade de erros encontrados na fase de teste (CAPERS, 1997 apud BARBOSA 
2013). 
O mesmo autor diz em um estudo realizado demonstraram as taxas de erros associados 
com as novas características adicionadas durante a fase de codificação que é aproximadamente 
50% maior do que aqueles dos erros associados com os requisitos originais. 
A Figura 2, mostra como acaba tornando impactante ao descobrir os erros na fase de 
desenvolvimento, principalmente quando estão na fase final. Isso acaba tornando prejudicial 
para o cliente. Pois a medida que tentam encontrar os erros, a demanda do custo aumenta e 
principalmente o tempo de entrega. 
22 
 
 
 
Figura 2 - Custo para corrigir um defeito dependendo de quando é descoberto 
 
 Fonte: Barbosa, 2013 
 
Esse resultado inevitável de erros de requisitos é o tempo dispendioso de retrabalho. O 
retrabalho pode consumir de 30 a 40 por cento do esforço total exercido sobre o projeto de 
desenvolvimento de software. A Figura acima demostra que pode custar até 110 vezes mais 
para corrigir erros decorrentes da mudança de requisitos do que se estes fossem definidos ainda 
na fase de elicitação de requisitos (SMITH, 2006 apud BARBOSA, 2013). 
O mesmo autor afirma que, a priorização de requisitos, segunda a sua estabilidade, 
contribui para um melhor cumprimento de prazo de entrega, pois garante que serão 
implementados primeiro requisitos mais estáveis. Aplicação de técnicas de otimização mostra-
se um meio promissor para a realização desta priorização. O uso de metaheurísticas na 
Engenharia de Software deu a origem a uma área de pesquisa chamada Search Based Software 
Engineering (SBSE) que objetiva automatizar a construções de soluções e tem a Engenharia de 
Requisitos como uma aplicação. 
A técnica de Engenharia de Software Baseado em Busca SBSE, será explicado com mais 
detalhes na seção 2.4. 
2.2 MÉTRICAS 
 
Pressman (2011) explica essas métricas como um fator importante que na maioria dos 
empreendimentos técnicos, as medições ajudam-nos a entender o processo técnico usado para 
se desenvolver um produto, como também o próprio. O processo é medido, num esforço para 
melhorá-lo. O produto é medido, num esforço para aumentar sua qualidade. 
Mas antes disso, existe todo um processo envolvido que a gestão de projeto. Pressman 
(2011) a gerencia de projeto é a primeira camada do processo da engenharia de software. Logo 
a gestão de projeto de software é a fase onde se tem todo um levantamento de questões na fase 
inicial do projeto. Wazlawick (2013) diz que o desenvolvimento de software e as atividades 
23 
 
 
relacionadas estruturam-se a partir de um modelo de ciclo de vida, escolhido pelo engenheiro 
de software para servir à empresa. A partir desse modelo de ciclo de vida, a empresa deve 
instanciar um processo próprio de desenvolvimento a ser seguido e constantemente aprimorado 
pela equipe de desenvolvimento, sob supervisão ou orientação do engenheiro de software. 
E a partir dessa gestão de projeto, estimamos a duração, o esforço, número de iterações, 
definição das entregas, cronograma e o planejamento.Ou seja, é um processo que faz parte do 
ciclo de vida do software. Assim, determinando essa gestão, pois nada adianta se não forem 
levadas a sério pelos desenvolvedores e pelo próprio gerente. 
 Por isso, temos as métricas que é muito importante na fase de levantamento de 
requisitos. Pois elas, estimam o esforço do projeto através de cálculos. Assim, nos dando uma 
estimativa de duração do projeto e custo associados. O próximo tópico explica um pouco mais 
sobre as métricas existentes. 
 O planejamento, em software, necessita de estimativa de esforço que são muito 
particulares dessa área. Existem várias técnicas para que um planejador consiga calcular, antes 
de iniciar um projeto, quanto tempo vai levar para ele ser concluído e quanto vai custar. Dessa 
forma, minimizará um dos maiores problemas nessa indústria, que é a imprevisibilidade, já que 
em geral os projetos atrasam e custam mais do que o previsto (WAZLAWICK, 2013). 
 O mesmo autor afirma que uma das questões fundamentais em um projeto de software 
é saber antes de executá-lo, quanto esforço, em que horas de trabalho, será necessário para leva-
lo a termo. Essa área é chamada de estimativa de esforço, conta com algumas técnicas que têm 
apresentado resultados interessante ao longo dos últimos anos. 
 Assim, existem várias técnicas que conseguimos medir o esforço de um projeto. Entre 
elas temos (SLOC, COCOMO, PF e PCU). O autor Wazlawick (2013), explica cada uma delas, 
como será demostrado nos próximos parágrafos. 
 A técnica conhecida como LOC (Lines of Code) ou SLOC (Source Lines of Code) foi 
possivelmente a primeira a surgir e consistir em estimar o número de linhas que um programa 
deverá ter, normalmente com base na opinião de especialistas e no histórico de projetos 
passados. 
 O COCOMO ou Constructive Cost Model (Também conhecido como COCOMO 81) é 
um modelo de estimativa de esforço baseado em KSLOC. Esse modelo já é obsoleto e foi 
substituído por COCOMO II em aplicações reais, nas técnicas. Além disso, pode ser usado 
como uma ferramenta de estimativa grosseira, caso pouquíssima informação sobre o sistema 
disponível (WAZLAWICK, 2013). 
 Já a técnica de Análise por Pontos de Funções (APF), ou Function Point Analysis, é 
também a técnica paramétrica para estimativa de esforço para desenvolvimento de software. 
24 
 
 
Porém, ao contrário de COCOMO, ela não se baseia em linhas de código, mas em requisitos.
 E por fim, temos a técnica de Pontos de Caso de Uso surgiu em 1992, a partir da Tese 
de Gustav Karner (1993). O método é baseado em Análise de Pontos de Função, 
especificamente MK II, que é o modelo relativamente mais simples do que o International 
Funtion Point User Group - IFPUG. 
 Portanto, entre as técnicas demonstradas acima, foi escolhido o uso das técnicas: Análise 
por Pontos de Funções (APF) e Pontos de Caso de Uso (PCU). Para ter uma estimativa do 
esforço no projeto do Repositório Digital. Essas técnicas serão apresentadas com mais detalhes 
nos próximos capítulos. 
2.3 OTIMIZAÇÃO MATEMÁTICA 
 
Como abordamos nesse trabalho a otimização, não poderíamos deixar de mostrar 
algumas funções matemática, cujo o objetivo é maximizar e minimizar os requisitos modelados 
para essa pesquisa. 
A palavra otimizar tem o sentido de melhorar o que já existe, ou então, projetar o novo 
com mais eficiência e menor custo. A otimização visa determinar a melhor configuração do 
projeto sem ter que testar todas as possibilidades. Otimização pode também ser definida como 
a necessidade de eficiência, que pode ser dividida nas etapas de reconhecimento das alternativas 
e a decisão. Primeiramente, é reconhecido numa tarefa ou problema a possibilidade de optar 
entre várias hipóteses e, em seguida, é decidida por aquela que se considera a melhor opção 
(ZINI, 2009). 
Otimizar é melhorar o que já existe, projetar o novo com mais eficiência e menor custo. 
A otimização visa determinar a melhor configuração de projeto sem ter que testar todas as 
possibilidades envolvidas (SARAMAGO 2012 apud SOUZA, 2014 ). 
A decisão pode ser qualitativa quando a escolha é feita através do bom senso, ou 
quantitativa quando a decisão é baseada em métodos matemáticos. No entanto, no processo de 
tomada de decisões é de grande auxílio o uso de alguns métodos ou técnicas para realizar tarefas 
ou resolver problemas (ZANI, 2009). 
Já Barbosa (2013) explica que matematicamente, comumente a chamada de 
programação matemática, possui uma história relativamente curta. Essencialmente, possui a 
característica de procurar minimizantes ou maximizantes, de certa função num certo conjunto, 
geralmente definida por equações e inequações. Como mostra a Figura abaixo. 
 
25 
 
 
Figura 3 - Representação matemática 
 
 Fonte: BARBORSA (2013) 
 
Na Figura 12, x1 + x2 representa a função objetivo a ser otimizada, nesse caso 
maximizada, respeitando as restrições x1 - x2 ≤ 1, -2 x1 - x2 ≤ -5 + 2x2 ≤ 7. A Figura 4 
mostra uma representação geométrica para a modelagem apresentada. 
 
Figura 4 - Esbouço da região admissível. 
 
 Fonte: Barbosa (2013) 
 
 Barbosa (2013), explica que de acordo com suas características, podemos classificar os 
problemas de otimização. A classificação interessa ao contexto desta pesquisa é a classificação 
em que os problemas são divididos de acordo com a quantidade de funções objetivos. Portanto, 
podemos definir a função objetivo como o ponto formando pelas variáveis de projeto que 
extremizam uma função e satisfazem as restrições. 
2.3.1 Otimização MonoObjetivo 
 Os problemas onde exista apenas uma função objetivo caracterizam a otimização mono-
objetivo possuem algumas limitações quando aplicadas a problemas de otimização 
multiobjeito, tais como a composição de funções e a repetição do processo de busca (JUNIOR 
2015 apud BARBOSA 2013). 
 Nos problemas de otimização monoobjetivo tem-se como objetivo encontrar solução 
ótima global. (Máximo e Mínimo) enquanto nos problemas de otimização multiobjetivo pode 
existir um ponto ótimo global. Portanto, o que diferencia o multiobjetivo do monoobjetivo é o 
fato de a otimização multiobjetivo encontrar um conjunto de soluções da fronteira do Pareto é 
tão importante quanto preservar a diversidade neste conjunto. Desta forma, um algoritmo 
eficiente para otimização multiobjetivo deve considerar os dois aspectos. 
26 
 
 
2.3.2 Otimização Multiobjetivo 
 
Ticona (2003) um problema de Otimização Multiobjetivo, trabalha com mais de uma 
função objetivo. Muitos problemas de tomada de decisões implicam em vários critérios que 
devem ser balanceados. Também explica que as técnicas tradicionais de otimização têm sido 
usadas para solucionar estes problemas no passado. Está técnica originalmente foram 
formuladas para trabalhar com uma função objetivo e encontrar uma solução ótima. Assim, 
vários objetivos são combinados em uma função. 
Os métodos de otimização multiobjetivo têm dois objetivos principais: minimizar a 
distância entre a frente não dominada e a frente do Pareto ótimo e encontrar um conjunto de 
soluções diversificadas. Em contrapartida, os AEs buscam solucionar dois problemas: o 
procedimento de avaliação e seleção dos algoritmos de forma a garantir uma busca eficiente 
para um conjunto Pareto ótimo e uma forma de manter a diversidade da população evitando a 
convergência prematura (Barbosa 2010). 
No entanto, quando otimização de conceber modelos para um problema, é 
frequentemente o caso que não há uma, mas vários objetivos que queremos otimizar. É 
normalmente o caso que estes objetivos estão em conflito entre si. Por exemplo, ao projetar 
uma ponte, gostaríamos de minimizar seu custo, maximizando a sua segurança. Estes problemas 
com duas ou mais funções objetivos são chamadas de 'multiobjetivos' e exigem diferentes 
ferramentas matemáticase algorítmicas do que as adaptadas para resolver problemas de 
otimização de Monoobjetivo. Até mesmo a noção de mudanças 'Otimalidade ' quando se lida 
com problemas de otimização multiobjetivo (COELLO, 2006). 
Vários problemas reais são formulados por uma coleção de objetivos a serem 
extremizados, os quais são muitas vezes conflitantes entre si. Porém, em muitas destas 
aplicações são realizadas simplificações no problema original de forma a combinar vários 
objetivos numa única função. Ou ainda escolhendo-se aquele que dentre os objetivos do 
problema requer prioridade de extremização, normalmente o custo (CASTRO, 2001). 
Também afirma que nos últimos anos vêm aumentando os estudos na área da otimização 
multiobjetivos, trazendo como consequência o desenvolvimento de métodos matemáticos para 
tal tarefa, bem como seus estudos e conhecimentos pelo meio técnico. 
Otimização multiobjetivo esteve disponível para cerca de duas décadas e sua aplicação 
em problemas do mundo real está aumentando continuamente. Uma importante tarefa na 
otimização multiobjetivo é identificar o conjunto de soluções de Pareto Ótimo. Um algoritmo 
evolutivo é caracterizado por uma população de candidatos de solução e o operador de 
reprodução permite que o processo de combinar soluções existentes para gerar novas soluções. 
27 
 
 
Como resultado, a computação encontra que vários membros de Pareto Ótimo definida em uma 
única corrida em vez de realizar uma série de pistas separadas, que é o caso de alguns dos 
convencionais processos estocásticos (ABRAHAM, 2005). 
O mesmo autor ainda afirma que o principal desafio em uma otimização multiobjetivo 
ambiente é minimizar a distância das soluções geradas para o Conjunto de Pareto e para 
maximizar a diversidade do conjunto de Pareto desenvolvido. Um bom conjunto de Pareto pode 
ser obtido, orientando adequado do processo de pesquisa através de um design cuidadoso dos 
operadores de reprodução e atribuição de aptidão estratégias. Para obter a diversificação 
especial tem que ser tomado na seleção processo. Cuidados especiais também é para ser tomado 
para evitar soluções não-dominadas se perca. 
2.3.3 Avaliação Multiobjetivo 
Na maioria dos problemas do mundo real requerem a otimização simultânea de 
múltiplos, frequentemente competitivos, critérios (ou objetivos), a solução para tais problemas 
é usualmente computada através da combinação dos objetivos em um único critério a ser 
otimizado, de acordo com alguma função. E vários casos, porém, a melhor forma de efetuar a 
combinação de objetivos não é conhecida antes do processo de otimização. Então o problema 
deve ser tratado como um Problema de Otimização Multiobjetivo com objetivos não 
comensuráveis (Guimarães, 2005). 
O mesmo autor explica que um problema de otimização Multiobjetivo trabalha com 
mais de uma função objetivo. Técnicas tradicionais de otimização têm sido usadas para 
solucionar estes problemas no passado. Estas técnicas originalmente foram formuladas para 
trabalhar com uma única função objetivo e encontrar uma solução ótima. Mas novas técnicas 
para considerar os objetivos separadamente estão sendo aplicadas. Assim, os vários objetivos 
não são combinados em uma única função. 
2.3.3.1 Formulação 
Para a formulação Multiobjetiva devemos seguir algumas regras matemática que define 
essa estratégia. É o que Guimarães (2005) descreve que um problema de otimização 
multiobjetivo possui um número de funções objetivo a serem otimizadas (maximizar ou 
minimizar). Além disso, possui restrições que devem ser satisfeitas por qualquer solução 
factível. O enunciado otimização multiobjetivo é o seguinte: 
 
28 
 
 
Figura 5 - Função de Otimização. 
 
 Fonte: Guimarães 2005. 
 
Onde x é o vetor de n variáveis de decisão x = (x1, x2,..., xn )T . Os valores (L) xi(L) e 
xi(U), representam o mínimo e o máximo valor respectivamente para a variável xi. Estes limites 
definem o espaço de variáveis de decisão ou espaço de decisão D. O vetor x será referido 
também como solução. 
As J desigualdades (gj) e as K igualdades (hk) são chamadas de funções de restrição. 
Uma solução x factível será aquela que satisfaça as J + K funções de restrição e os 2n limites. 
Caso contrário a solução será não factível. O conjunto de todas as soluções factíveis formam a 
região factível ou espaço de busca S. 
Cada uma das M funções objetivo f1(x), f2(x),...,fM(x) pode ser maximizada ou 
minimizada. Porém, para trabalhar com os algoritmos de otimização, é necessário converter 
todas para serem maximizadas ou minimizadas. O vetor função objetivo f(x) conforma um 
espaço multidimensional chamado espaço de objetivos Z. Esta é uma diferença fundamental 
em relação à otimização de objetivos simples, cujo espaço de objetivos é unidimensional. O 
mapeamento acontece, então, entre um vetor x (n-dimencional) e um vetor f(x) (M-
dimensional). Por exemplo, se cada elemento de x e f(x) são números reais, então f(x) estaria 
mapeada como f(x) : ℜn →ℜM (GUIMARÃES, 2005). 
 
2.3.3.2 Solução Pareto Ótimo 
 
A tomada de decisões implica num processo que consiste em vários fatores, com o 
objetivo de encontrar a melhor solução. Em alguns casos, podem aparecer várias soluções boas, 
das quais nenhuma é quantitativamente melhor que a outra. Por exemplo, na hora de comprar 
um carro suponha-se que se está procurando o preço e conforto (TICONA, 2003). 
O autor explica que em um problema de multiobjetivo onde temos mais de dois 
objetivos, como a compra de um carro. Onde queremos otimizar o valor de custo e ao mesmo 
tempo maximizar o conforto. A Figura 6 representa uma opção de compra de um carro. 
29 
 
 
 Figura 6 - Exemplo que ilustra várias opções de compra de carro (1-5), 
considerando o seu custo e conforto. 
 
 Fonte: Ticona, 2003. 
O mesmo autor explica que o objetivo é minimizar o custo e maximizar o conforto. 
Neste caso tem-se cinco possíveis opções de compra. Intuitivamente, descarta-se a solução 1, 
já que a solução 5 fornece mais conforto por igual preço. A solução 2 é descartada pela mesma 
razão. Tem-se então três soluções: 3,4,5, que são boas alternativas de compra. Em termos 
quantitativos nenhuma é melhor que a outra, pois uma é mais confortável, mas menos barata, e 
vice-versa. Existe então um compromisso entre os objetivos. Quanto maior o conforto, maior o 
preço caro e vice-versa. 
 Diz-se que uma solução domina uma outra se seus valores são melhores em todos os 
objetivos. Por exemplo, a solução 5 domina a solução 1. Já a solução 5 é não dominada por 
nenhuma outra. O mesmo acontece com as soluções 3 e 4. Se não se conhece a priori a 
importância relativa de cada objetivo, pode-se dizer que as soluções 3, 4, e 5 são igualmente 
boas. Portanto, existe um conjunto de soluções ótimas; este conjunto é chamado de conjunto 
não dominado.(TICONA, 2003). As outras soluções (1, e 2) formam o conjunto dominado. 
Estes conjuntos têm as seguintes propriedades: 
 
1. Qualquer par de soluções do conjunto não dominado deve ser não dominado um em 
relação ao outro. 
2. Quaisquer das soluções não pertencentes ao conjunto não-dominado, devem ser 
dominadas por no mínimo uma solução no conjunto não dominado. 
 
Se os pontos não dominados estão em um espaço contínuo, pode-se desenhar uma curva. 
Todos os pontos contidos na curva formam a Frente de Pareto ou Fronteira de Pareto. Quando 
a informação adicional sobre importância dos objetivos é desconhecida, todas as soluções 
Pareto-ótimas são igualmente importantes. Deb assinala duas importantes metas em Otimização 
Multi-Objetivo (DEB, 2001): 
 
30 
 
 
1. Encontrar um conjunto de soluções o mais próximo possível da 
Fronteira de Pareto. 
2. Encontrar um conjunto de soluções com a maior diversidade possível. 
 
 
A primeira meta é comum para qualquer processo de otimização. Soluções muito 
distantes da Fronteira de Pareto não são desejáveis. Porém, encontrara maior diversidade dentro 
das soluções é uma meta específica para Otimização Multiobjetivo (TICONA, 2003). 
O mesmo autor explica na Figura 7a mostra-se uma boa distribuição de soluções na 
fronteira de Pareto, enquanto que na Figura 7b as soluções estão distribuídas apenas em algumas 
regiões. É necessário assegurar a maior cobertura possível da fronteira, já que isso implica em 
ter um bom conjunto de soluções comprometidas com os objetivos desejados. Como em 
Problemas de Otimização Multiobjetivo trabalha-se com o espaço de decisões e o espaço de 
objetivos, é desejável que as soluções tenham uma boa diversidade nestes espaços. 
Normalmente, uma boa diversidade em um destes espaços garante também a diversidade no 
outro. Entretanto, em alguns problemas isto não acontece. 
 
Figura 7 - Distribuição de Soluções na Fronteira de Pareto. 
 
 
 Fonte: Ticona, 2003 
 
Guimarães (2005) explica que como as soluções do problema de otimização 
multiobjetivo trabalham com espaços das decisões e dos objetivos, a diversidade das soluções 
na Fronteira de Pareto Ótimo implica que o conjunto de soluções comprometidas é de qualidade 
em relação aos objetivos desejados. 
Geralmente, é necessário um critério adicional para diferenciar as soluções encontradas 
no conjunto Pareto-Ótimo, de modo que se tenha uma única solução ótima. Isso pode ser feito 
por algum especialista, após o processo de otimização ter descoberto um conjunto de soluções 
31 
 
 
não-dominadas, ou pode-se adotar algum critério que diferencie as soluções do conjunto Pareto-
Ótimo durante o processo de otimização. 
 
2.4 ALGORITMOS EVOLUTIVOS 
Algoritmos evolutivos são os mais adequados para resolver problemas de otimização 
multiobjetivo, porque lidam ao mesmo tempo com um conjunto de soluções possíveis (o 
chamado população). Isso nos permite encontrar vários membros de conjunto de Pareto ótimo 
em uma única execução do algoritmo, em vez de realizar uma série de pistas separadas como é 
o caso da tradicional técnicas de programação matemáticas. 
Além disso, Algoritmos Evolutivos são menos suscetíveis a forma ou a continuidade do 
Frente de Pareto (por exemplo, podem facilmente lidar com descontínuos ou côncavo frentes 
de Pareto), considerando que estas duas questões são uma preocupação real para técnicas de 
programação matemáticas. 
A maioria dos problemas do mundo real apresenta, em sua formulação, restrições de 
igualdade e desigualdade. Na resolução destes problemas os Algoritmos Evolucionários, em 
especial os Algoritmos Genéticos, têm sido amplamente utilizados. Estas técnicas, ao serem 
comparadas com os métodos tradicionais de programação, possuem a vantagem de trabalhar 
com uma menor quantidade de informações não precisando, por exemplo, calcular gradientes, 
derivadas, hessianas entre outras. Além disso, estas técnicas são de fácil implementação e são 
ferramentas de busca global. (ZANI, 2009). 
Sendo assim, existem diferentes tipos de Algoritmos Evolucionários e a ideia envolvida 
na teoria destes algoritmos está relacionada em utilizar conceitos e princípios da evolução 
natural das espécies como estratégia de otimização de problemas. Apesar do presente capítulo 
tratar de Algoritmos Evolucionários, aqui será apresentado somente um desses algoritmos: o 
Algoritmo Genético. O intuito de dar ênfase somente a este algoritmo se deve ao fato que a base 
principal do desenvolvimento deste trabalho se apoia nesta técnica. Desta forma, neste capítulo 
são apresentados os principais fundamentos da técnica da qual se denomina Algoritmos 
Genéticos. 
Inicialmente, apresenta-se uma estrutura básica e mais usual da forma com que esta 
técnica foi ou vem sendo originalmente empregada, visto que, novas estratégias podem ser 
adicionadas em conjunto com a técnica mais básica dos Algoritmos Genéticos com o intuito de 
promover novas melhorias e dar origem a Algoritmos Genéticos mais elaborados. No decorrer 
deste capítulo, são explicitados de forma sucinta as origens, definições, procedimentos, forma 
de codificação de uma configuração, vantagens, desvantagens e outros tópicos importantes 
relacionados a esta técnica. 
32 
 
 
Do mesmo modo que Santos (2009), explica que os métodos de otimização e busca 
estocástica têm recebido crescente interesse nas últimas décadas, principalmente os baseados 
em princípios da teoria da evolução. O desenvolvimento de modelos computacionais inspirados 
nos mecanismos evolutivos caracteriza-se pela configuração de algoritmos de otimização 
robustos e sistemas adaptativos. AEs são algoritmos computacionais pertencentes a uma classe 
de métodos regidos por princípios evolutivos. Tais princípios são oriundos do mundo biológico 
e baseados na teoria da evolução Darwiniana. Os AEs tentam abstrair e imitar mecanismos 
evolutivos para resolução de problemas que requerem adaptação, busca e otimização. 
Durante os últimos anos, vários algoritmos evolucionários foram propostos para 
resolver problemas de otimização restrita. Considerando a otimização restrita, pode-se dizer 
que obter uma solução factível, ou seja, uma solução que seja útil na formulação do problema 
e satisfaça todas as restrições, prevalece, em determinado estágio do algoritmo, sobre otimizar 
a função objetivo. Existem problemas bastante complexos que são altamente restritos e, neste 
caso, encontrar uma única solução factível pode ser considerado uma tarefa extremamente 
difícil. Muitas vezes, impor que a obtenção de soluções factíveis seja sempre satisfeita, pode 
ser uma exigência um tanto exagerada. (ZANI, 2009). 
O mesmo autor também explica que objetivou-se elaborar um algoritmo que, em seu 
primeiro estágio, visa exclusivamente obter, pelo menos, uma única solução factível. Após 
alcançar com sucesso o primeiro estágio, o algoritmo transfere-se para um segundo estágio que 
visa realizar a otimização simultânea da função objetivo e da violação das restrições. Neste 
estágio um problema monoobjetivo de otimização restrita é tratado como um problema 
biobjetivo e, desta forma, além de buscar a solução ótima global factível do problema, procura-
se também obter soluções que violam de forma aceitável as restrições impostas na tentativa de 
obter um ganho importante nos valores da função objetivo. 
Neste algoritmo pode-se perceber que, na busca da solução ótima do problema, uma 
população de soluções é processada em cada iteração ou geração. Esta característica do 
Algoritmo Genético ou de outra técnica evolucionária faz com que estes algoritmos sejam 
naturalmente adequados para a determinação de várias soluções. Sendo assim, pode-se afirmar 
que na resolução de problemas de otimização multiobjetivo, os Algoritmos Evolucionários são 
mais vantajosos em relação, por exemplo, aos métodos clássicos que não foram projetados para 
trabalharem com múltiplas soluções (ZANI, 2009). 
Na próxima seção explicaremos o algoritmo genético de forma como funciona 
utilizando técnica de busca utilizada na Ciência da Computação para achar soluções 
aproximadas em problemas de otimização e busca. 
 
33 
 
 
 
2.4.1 Algoritmos Genéticos 
 
Segundo Lucas (2002), os Algoritmos Genéticos (AGs) utilizam conceitos provenientes 
do princípio de seleção natural para abordar uma série ampla de problemas, em especial de 
otimização. Robustos, genéricos e facilmente adaptáveis, consistem de uma técnica 
amplamente estudada e utilizada em diversas áreas. 
AG é um método que simula o processo de evolução natural (biológica), destinando-se 
a solucionar problemas de otimização. O AG pode ser entendido como uma interpretação 
matemática e algorítmica das teorias de Darwin, no qual as hipóteses podem ser resumidas: a 
evolução é maneira que age sobre os cromossomos do organismo, e não sobre o organismo que 
os transporta. Logo o que ocorrer durante a vida do organismo não altera os seus cromossomos, 
no entanto, os cromossomosrefletem diretamente nas características do organismo. 
A seleção natural faz com que os cromossomos que criam organismos mais bem 
adaptado ao ambiente, sobrevivam e reproduzam mais que outros organismos com 
cromossomos menos adaptados. A reprodução é o ponto no qual a evolução se define. O 
processo de recombinação dos cromossomos (entre dois pais) podem gerar cromossomos dos 
filhos bem diferente dos pais (SOUZA, 2014). 
Também diz que, os AGs é uma técnica heurística de otimização global utilizada para 
encontrar soluções aproximadas em problemas de otimização. Este algoritmo utiliza técnicas 
que foram inspiradas pela biologia evolutiva como seleção natural, hereditariedade, mutação e 
recombinação. AG não é um algoritmo de busca de solução ótima, mas sim uma heurística que 
encontrar boas soluções, já que o mesmo utiliza da aleatoriedade, pode encontra soluções 
diferentes a cada execução, podendo esses serem ótimo locais ou globais. 
No entanto, explica que o AG utiliza população de indivíduos, sendo que um indivíduo 
é uma representação abstrata de uma solução para o problema. Realizando uma analogia com a 
biologia, o gene é a parte indivisível da representação, e todos os genes compõem um 
cromossomo. A representação cromossômica deve ser adequada para cada problema, deve 
poder representar o problema de modo que tenha uma precisão desejada e outras 
particularidades da arquitetura da máquina ou da linguagem de programação utilizada. A 
representação deve ser o mais simples possível e que preferencialmente não represente soluções 
ilegais ao problema. 
Em analogia com a natureza, a informação é codificada em cromossomos e a reprodução 
(sexuada) e a mutação se encarregará de fazer a população evoluir. A reprodução (crossover) é 
o processo que irá criar filhos baseado na mistura entre os cromossomos de dois ou mais pais. 
34 
 
 
Ha vários modos de efetuar a reprodução, e o mesmo é dependente de como foi codificado o 
cromossomo. 
Mutações são alterações nos genes, que podem ser causadas por erros de cópia do 
material genético durante a divisão celular. Na natureza ocorrem com uma baixa probabilidade. 
Essa mesma pode ser benéfica, gerando um indivíduo com uma melhor aptidão, ou maléfica 
reduzindo a aptidão do indivíduo. No AG as mutações são importantes para aumentar a 
diversidade de soluções na população, e evitar uma convergência genética muito rápida, ela é 
importante para evitar máximos locais. 
E explica que para que a população possa evoluir para uma boa solução, deve-se 
selecionar os melhores indivíduos da população para gerarem novos indivíduos. Sendo que os 
pais mais aptos tende a gerar mais filhos, e pais menos aptos gerarem menos descendentes. 
Como funciona na seleção natural onde as características favoráveis que são hereditárias se 
tornaram mais comum nas gerações sucessivas, e as características desfavoráveis que são 
hereditárias se tornam mais raras, ou até mesmo extintas. Essas características são preservadas 
em consequência da vantagem seletiva que concedem a seus portadores, permitindo que um 
indivíduo deixe mais descendentes que outros sem essas características. 
Nos AGs, a adaptabilidade do indivíduo é calculada pela função de avaliação, essa 
função tem como entrada o cromossomo e gera a avaliação do indivíduo. Na seleção, os 
indivíduos que tiverem uma avaliação alta devem ser privilegiados em detrimento aos que 
tiverem uma avaliação ruim. É importante que todos os indivíduos possam ser selecionados, 
pois indivíduos com uma baixa avaliação pode ter alguma característica que seja propícia a 
melhor solução do problema. Caso apenas os melhores indivíduos evoluírem, em cada geração 
a população tenderá a ser constituída por indivíduos cada vez mais semelhantes, 
consequentemente reduzindo a diversidade da população, gerando o efeito da convergência 
genética (LINDEN 2012 apud SOUZA 2014). 
Mostra em seu trabalho que o primeiro AG proposto por Holland é conhecido como 
Standart Genetic Algorithm ou Simple Genetic Algorithm é descrito em 6 passos. 
 
1. Inicie uma população com os cromossomos gerados aleatoriamente, de tamanho N. 
2. Avalie cada cromossomo da população utilizando a função de avaliação. 
3. Gere uma nova população de tamanho N a partir do cruzamento de cromossomos 
selecionados da população anterior. Aplique mutação nestes cromossomos. 
4. Remova a população anterior, trocando pela nova população criada. 
5. Avalie cada cromossomo da população utilizando a função de avaliação. 
35 
 
 
6. Caso a solução ideal seja encontrado, ou o tempo do algoritmo se esgote (número 
máximo de gerações, ou avaliações, ou algum outro critério de parada), retorna o 
cromossomo com a melhor avaliação. Caso contrário retorne para o passo 3. 
Figura 8 - Diagrama de Sequência do Algoritmo Genético. 
 
 Fonte: Souza 2014 
 
Se tudo ocorrer bem, esta simulação do processo evolutivo produzirá, conforme a 
população for evoluindo, os cromossomos melhor adaptados (com uma melhor avaliação), irão 
obter uma boa solução para o problema tratado (SOUZA 2014). 
A figura 9 mostra a representação do Algoritmo Genético elaborado por Branquinho 
(2013). 
1 - Nessa esquematização detalhada do algoritmo genético, demostra o seu 
funcionamento de acordo com seus padrões. Portanto, nesse fluxograma nós temos o início que 
vai gerar uma população de indivíduos Tp esses indivíduos vão fazer parte da nossa população. 
De acordo com o tamanho da nossa população, o nosso genético pode achar melhores soluções 
ou piores soluções. E essa população inicial é gerada de forma aleatória. 
 
 
 
36 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Fonte: Branquinho, 2013. 
 
2 - Após gerar essa população inicial, o AG avalia cada indivíduo da população inicial 
e esse processo de avalição corresponde a associar uma aptidão de cada indivíduo, ou seja, essa 
avaliação vai dizer o quão bom é esse indivíduo para resolver um dado problema. 
3 - Uma vez que já tem a população e todos indivíduos avaliados, o AG tem que verificar 
se o critério de parada foi atingido. O que significa esse critério de parada? Normalmente são 
Início 
2. Avaliam-se os indivíduos da População Inicial 
1. Gera-se a População Inicial com T
p
 indivíduos 
3. População atingiu o 
critério de término? 
4/9. Melhor indivíduo da 
população é apresentado 
como a solução 
sim 
Fim 
não 
4. Selecionam-se p
sel
 indivíduos que formarão os pares de crossover 
6. Submetem-se os novos indivíduos a uma mutação com probabilidade p
mut
 
5. Para cada par, sorteia-se um Ponto de crossover e 2 novos indivíduos são gerados por crossover 
7. Avalia-se o desempenho dos novos indivíduos formados após os processos de crossover e mutação 
8. Selecionam-se os T
p
 melhores indivíduos dentre a população original e os novos indivíduos 
N 
 Figura 9 - Exemplificação do Algoritmo Genético. 
37 
 
 
duas coisas, primeiro de acordo com a aptidão encontramos ótimas soluções ou o número de 
evoluções alcançou um certo limite. Ou seja, temos a população e ela foi evoluindo uma certa 
quantidade de período e atingiu o máximo especificado pelo usuário e assim o AG pega as 
melhores soluções das populações. Se o algoritmo encontrar as melhores soluções ele retorna 
para esse melhor indivíduo e assim finaliza o AG. 
4 - Senão tiver encontrado as melhores soluções, o AG entra no processo de crossover. 
Ou seja, crossover pega a população inicial de acordo com certo método de seleção, ele 
seleciona alguns indivíduos em dois. 
5 - A ideia dele utilizar dois indivíduos selecionados e que eles serão parte desse 
processo do crossover. A partir desses dois indivíduos ele gera mais dois novos indivíduos, ou 
seja, eles vão conter partes das informações de seus pais da população inicial. 
6 - Após ter processado o crossover com os novosindivíduos, o AG pega esses 
indivíduos e aplica o processo de mutação. Ou seja, pega essa solução e de forma aleatória 
alterar essa solução. 
7 - Uma vez feito isso o AG ter os novos indivíduos, avaliamos esses dois novos 
indivíduos e este processo de avaliação é a aptidão. 
8 – Desta forma depois de serem avaliados, eles são colocados na população e estes 
quando são colocados na nova população o AG faz o processo de seleção natural, a ideia é 
eliminar os indivíduos que não são tão bons da população para serem selecionados. Por 
exemplo, se tivemos uma população inicial de 100 indivíduos e fez o processo de crossover, 
mutação, e foram avaliados e vamos supor que gerou 50 novos indivíduos, então temos 100 de 
uma certa geração e mais 50 mais novos indivíduos, portanto juntando esses dois vamos ter 150 
população de indivíduos. Agora temos que aplicar o processo de Seleção Natural, ou seja, temos 
que eliminar uma certa quantidade de indivíduos para que mantenhamos exatamente a mesma 
quantidade de 100 indivíduo da população inicial. Eliminando os 50 e mantendo os 100 
melhores. 
Após essa etapa o AG verificar se a população inicial atingiu o critério de parada, que é 
exatamente, se achou a melhor solução ou a quantidade de evoluções atingiu o limite. O N 
representado no fluxograma representa a quantidade de evolução se atingiu o limite ou não. 
Basicamente, os AGs tratam problemas de otimização como um processo iterativo de 
busca da melhor solução dentro do espaço de possíveis respostas para o problema. Inicia com 
um conjunto aleatório de soluções iniciais, que constituem a população inicial. Combinando os 
melhores representantes dessa população, obtém uma nova, que possa substituir a anterior, 
caracterizando-se como a próxima geração. O mecanismo é repetido. Cada nova iteração a 
38 
 
 
população é refinada gerando novas e melhores soluções para o problema em questão, 
culminando com a sua convergência (FERNANDES, 2005). 
Portanto, podemos perceber que dentro desse ciclo do AG, Guimarães (2005), explica 
que os cromossomos, ou indivíduos, são então submetidos a um processo evolucionário que 
envolve avaliação, seleção, recombinação (crossover) e mutação. Após vários ciclos de 
evolução a população deverá conter indivíduos mais aptos. Os algoritmos utilizam uma 
analogia direta deste fenômeno de evolução da natureza, onde cada indivíduo representa uma 
possível solução para um problema dado. A cada indivíduo atribui-se um valor de avaliação: 
sua aptidão, que indica quanto a solução representada por este indivíduo é boa em relação às 
outras soluções da população. Desta maneira, o termo população refere-se ao conjunto de todas 
as soluções com as quais trabalha o sistema. O indivíduo mais apto é dado uma probabilidade 
maior de se reproduzirem mediante cruzamento com outros indivíduos da população, 
produzindo descendentes com características de ambas as partes. A mutação também tem um 
papel significativo, ao introduzir na população novos indivíduos gerados de maneira aleatória. 
Assim, o processo de evolução começa com a criação aleatória dos indivíduos que 
formarão a população inicial. A partir de um processo de seleção baseado na aptidão de cada 
indivíduo, são escolhidos indivíduos para a fase de reprodução que cria novas soluções 
utilizando-se, para isto, um conjunto de operadores genéticos. Deste modo, a aptidão do 
indivíduo determina o seu grau de sobrevivência e, assim, a possibilidade de que o cromossomo 
possa fazer parte das seguintes gerações. 
Para determinar o final da evolução pode-se fixar o número de gerações, o número de 
indivíduos criados, ou ainda condicionar o algoritmo à obtenção de uma solução satisfatória, 
isto é, quando atingir um ponto ótimo. Outras condições para a parada incluem o tempo de 
processamento e o grau de similaridade entre os elementos numa população (convergência) 
(GUIMARÃES, 2005). 
2.4.1.1 Vantagens e Desvantagens dos Algoritmos Genéticos 
 Como todos algoritmos, o AG também tem suas vantagens e desvantagens. Castro 
(2001), afirma que: 
 
Vantagens dos AGs 
• São robustos e aplicáveis a uma grande variedade de problemas. 
• Não requerem conhecimentos ou informações dos gradientes da superfície 
definida pela função objetivo. 
39 
 
 
• Descontinuidades ou complexidades presentes na superfície acarretam pouco ou 
nenhum efeito no desempenho da busca. 
• São mais resistentes a se prenderem a ótimos locais. 
• Apresentam um bom desempenho para uma grande escala de problemas. 
• São de implementação fácil e proporcionam maior flexibilidade no tratamento do 
problema a ser resolvido. 
Desvantagens dos AGs 
• Dificuldade para achar o ótimo global exato. 
• Requerem um grande número de avaliações de funções de aptidão. 
• Grandes possibilidades de configurações que podem complicar a resolução do 
problema tratado. 
Na literatura especializada, encontram-se uma variedade de algoritmos evolucionários 
multiobjetivos. No entanto, analisar em detalhes todas as técnicas existentes é considerado uma 
tarefa inviável neste trabalho. Sendo assim, serão citados alguns algoritmos evolucionários 
multiobjetivos que podem ser encontrados em (DEB, 2004). Entre os principais algoritmos 
evolucionários multiobjetivos estão: SPEA II, VEGA, RANDÔMICO, NSGA-II e etc. 
Existem vários outros tipos de Algoritmos Genéticos Multiobjetivos e dentre eles 
destacamos alguns principais. 
 
2.4.2 SPEA II ou Algoritmo Evolutivo da Força do Pareto 
 
Baseado no envelope de Pareto Seleção Algoritmo II (Pesa-II) é um algoritmo de 
optimização evolutiva de multiobjetivo, que utiliza o mecanismo de AG juntamente com a 
seleção com base no envelope de Pareto. PESA-II utiliza um arquivo externo para armazenar 
as soluções aproximadas de Pareto. Os pais e os mutantes são selecionados a partir deste 
arquivo externo, com base nas redes criadas com base na distribuição geográfica dos membros 
de arquivo. Isto é muito semelhante ao mecanismo usado em MOPSO algoritmo. Na verdade o 
PESA-II é um algoritmo genético multiobjetivo, que utiliza as redes para fazer seleções, e criar 
a próxima geração. 
O algoritmo funciona com a manutenção de uma população externa a cada geração que 
armazena um conjunto de soluções não dominadas determinado desde a população inicial e que 
participa nas operações genéticas. (CASTRO, 2001). 
40 
 
 
Também afirma que a aptidão de cada indivíduo na população corrente e na população 
externa é decidida com base no número de soluções dominadas pelo seguinte procedimento. 
Inicialmente, uma população combinada pela população corrente e a externa é construída. A 
seguir, todas as soluções não dominadas nesta população recebem um valor de aptidão baseado 
no número de soluções que elas dominam, mantendo a diversidade. Toma-se o cuidado de não 
atribuir para as soluções não dominadas uma aptidão pior que o das melhores soluções 
dominadas, para garantir que a busca caminhe na direção da fronteira não dominada e 
simultaneamente a diversidade entre os indivíduos dominados e não dominados. 
 
2.4.3 Vega 
 
O primeiro algoritmo genético, para o tratamento de problemas multiobjetivos (Vector 
Evaluated Genetic Algorithm, VEGA), foi apresentado por Schaffer [Schaffer, 1984]. 
Atualmente existem inúmeras trabalhos publicados envolvendo os Algoritmos Evolutivos 
Multiobjetivos-MOEA (AMORIM, 2006). 
Também explica que foi o pioneiro na implementação de algoritmos evolutivos para 
solução de problemas multiobjetivo, Schaffer desenvolveu o chamado “Vector Evaluated 
Genetic Algorithms”, mais conhecido como VEGA. Schaffer modificou o software de domínio 
público GENESIS através da criação de melhorias no procedimento de seleção original que faz 
com que o procedimento seja repetido para cada objetivo separadamente, contemplando desta 
forma a natureza multiobjetivo do problema, até atingir-se um determinado número predefinido 
de indivíduos