Kapittel 2. Teoretisk grunnlag
2.2 Arbeidsgivers kompetansebehov, holdninger og kategorisering
Os métodos de definição da frente Pareto podem ser classificados como:
multiobjetivos clássicos e multiobjetivos evolucionários. Os primeiros utilizam na sua
estrutura técnicas que buscam otimizar apenas uma função objetivo por vez, empregando, para determinar a frente das soluções não dominadas, um conjunto de vetores, de peso ou restrições. Vale salientar que o emprego de técnica de otimização evolucionária para determinação da frente Pareto, não implica que a mesma é
multiobjetivo evolucionária. Para ela ser classificada dessa forma é preciso que, na
estrutura do método, exista uma mudança no modo de se trabalhar com mais de um objetivo simultaneamente. Na maioria dos métodos isso é feito empregando-se diretamente na estrutura do algoritmo de otimização o conceito de dominância. Nos itens seguintes serão comentadas algumas técnicas clássicas de geração de frentes Pareto, bem como alguns dos principais métodos evolucionários desenvolvidos nos últimos anos.
3.2.2
Métodos Clássicos
Embora existam numerosos métodos multiobjetivos clássicos para a geração da região Pareto ótima, a maioria desses são ramificações de duas metodologias principais: método dos pesos e método das restrições-ε . Existe, ainda, uma outra linha de métodos que são os baseados no algoritmo Simplex da Programação Linear, como os propostos por Philip (1972) e Zeleny (1971). Entretanto, estas metodologias não podem ser aplicadas a problemas de natureza não-linear, como é o caso desse trabalho.
3.2.2.1 Método dos Pesos
O método dos pesos foi apresentado por Gass e Saaty (1955), sendo posteriormente aperfeiçoado por Zadeh (1963), que lhe deu a forma pela qual é conhecido atualmente. O método dos pesos agrega, através da multiplicação de ponderadores, os diversos objetivos em uma única função, e, devido a sua simplicidade, é um dos mais utilizados (GOICOECHEA, HANSEN e DUCKSTEIN, 1982).
Originalmente, o método dos pesos foi empregado como uma metodologia multiobjetivo a priori, em que o decisor antecipadamente definia os pesos de cada critério utilizado. Entretanto, o emprego efetivo dessa metodologia fica prejudicado dificultando a determinação dos pesos, pela falta de conhecimento antecipado das relações entre os objetivos. Como pequenas alterações nos pesos geram resultados diferentes, essa metodologia passou a ser utilizada como um meio de geração da região Pareto ótima.
O método dos pesos considera a otimização de uma combinação linear dos objetivos expressa da seguinte forma:
Minimize Z(x) = w1Z1(x) + w2Z2(x) + w3Z3(x) + ... + wMZM(x) (3.3)
sujeito a: x ∈ Xf
sendo wi os pesos positivos e normalizados de modo que Σwi =1.
No caso de, um problema com dois objetivos, que tem dois valores para os pesos fixados w1 e w2 e dado que Z(x) é a combinação linear dos desses pesos, a Equação (3.3) representa uma reta no espaço dos objetivos que possui inclinação
2 1
w w
− (Figura 3.3). O ponto em que a reta tangencia a fronteira Pareto, corresponde a
solução ótima para aquela configuração de pesos. A região Pareto completa seria então determinada a partir da resolução do problema de minimização para uma série de combinações dos pesos (Figura 3.3).
Por sua simplicidade, o método dos pesos é de fácil implementação. Entretanto, essa metodologia apresenta um número muito grande de desvantagens, a saber (COHON, 1974; GOICOECHEA, HANSEN e DUCKSTEIN, 1982 e DEB 2001): • pode-se encontrar uma mesma solução para diferentes conjuntos de pesos
• para problemas não-lineares, um conjunto de pesos uniformemente distribuído, não retorna um conjunto Pareto ótimo também distribuído de forma igual;
Z Z 1 2 Frente Pareto w w 2 1
Figura 3.3 Método dos pesos para um problema de dois objetivos
• para problemas multiobjetivos que apresentarem mais de uma solução ótima para um determinado conjunto de pesos (o que é frequente quando se trabalha com funções multimodais), deve-se utilizar um algoritmo de otimização global – que requer um tempo computacional elevado para encontrar uma solução – caso seja empregado um método de busca que produza como respostas soluções locais, algumas faixas de soluções do conjunto não dominado podem não ser encontradas
• a complexidade computacional do método dos pesos aumenta exponencialmente com o número de objetivos do problema, sendo o número de otimizações necessárias para se determinar a frente Pareto determinado pela equação: 1 − = K M ns (3.4)
em que ns é o número de problemas a ser otimizado, K é a quantidade de pontos da frente não dominada que se quer determinar;
• o método dos pesos também é incapaz de trabalhar com problemas envolvendo regiões não convexas, visto que não se consegue determinar os pontos pertencentes a tais regiões (Figura 3.4).
Para se superar a última dificuldade, desenvolveram-se metodologias em que o problema é resolvido utilizando distâncias métricas. Dois desses métodos são:
método dos pesos com métricas (BOWMAN 1976 apud MIETTINEN, 1999) e o método de Benson (BENSON, 1978). Essas metodologias embora superem o problema de se
lidar com regiões não convexas, ainda apresentam todos as outras dificuldades citadas, acarretando uma complexidade computacional ainda maior (MIETTINEN, 1999). Z Z 1 2 Frente Pareto w w 2 1 Frente Encontrada
Figura 3.4 Representação do método dos pesos em um problema não convexo
3.2.2.2 Método das Restrições-ε
Um outro método que pode ser empregado para a solução de problemas envolvendo regiões não convexas, é o método das restrições-ε. Proposto por Himes et al. (1971), sugere a resolução do problema de otimização simples considerando um objetivo por vez. Os outros objetivos seriam então colocados nas restrições do problema. A representação gráfica do método das restrições-ε é mostrada na Figura 3.5. Matematicamente , o método consiste em se resolver o seguinte problema:
Minimizar: Z (x) = Zµ(x) (3)
sujeito a: Zi(x) >εik i = 1,2,...,M e i≠µ; k=1, 2, ..., K. x ∈ Xf
O método das restrições-ε apresenta vantagens sobre o método dos pesos como a possibilidade de se poder trabalhar com problemas que têm regiões não- convexas (Figura 3.5) . Outra vantagem está no fato de que na maioria dos problemas, uma única solução é encontrada para cada conjunto de vetores ε = (ε1, ε2, ...,εµ- 1, ε µ+1,...,εM) No entanto, as outras desvantagens inerentes ao método dos pesos ainda
persistem (MIETTINEN, 1999). Z Z 1 2 ε1 ε1 ε1 ε1 ε1 1 2 2 k k+1 K
Figura 3.5 Representação do método das restrições-ε
De um modo geral, observa-se que a implementação dos métodos tradicionais acima apresenta problemas na obtenção da região Pareto ótima. Estas dificuldades são (ZITZLER, 1998 e DEB, 2001):
• apenas uma solução da região Pareto ótima pode ser encontrada a cada otimização;
• alguns métodos são incapazes de trabalhar com problemas apresentando regiões não convexas;
• essas metodologias requerem, de alguma forma, um conhecimento prévio, seja para a determinação dos pesos, seja para determinar as restrições-ε. A primeira desvantagem é, sem dúvida, a que mais restringe a aplicação desses métodos a problemas práticos. A utilização destes processos de otimização aumenta consideravelmente o esforço computacional quando está se trabalhando com problemas com mais de 2 objetivos.
Por exemplo, caso se deseje uma discretização por objetivo de 20 pontos em um problema com 5 objetivos, o número de vezes que seria necessário empregar uma rotina de otimização seria igual a 160.000 (205).
Este foi o principal motivo para o desenvolvimento dos métodos interativos, que, embora também empreguem algoritmos de otimização, requerem uma quantidade muito menor de simulações.
Na última década ocorreu o desenvolvimento de uma forma de algoritmos evolucionários aplicados na determinação de frentes não dominadas. Os métodos desenvolvidos utilizam uma vantagem desse tipo de formulação, que é trabalhar com um número grande de soluções ao mesmo tempo na busca do conjunto de soluções Pareto. O desenvolvimento desses métodos tem ocorrido de modo rápido, já tendo sido produzidos centenas de trabalhos que procuram refinar metodologias existentes e/ou criar novos métodos. No item a seguir será feito um breve apanhado sobre as principais metodologias baseadas em algoritmos evolucionários aplicadas aos problemas multiobjetivos.