Otimização é o ato de obter o melhor resultado sob determinadas circunstâncias [12]. No projeto, construção e manutenção de qualquer sistema o engenheiro deve tomar decisões em várias etapas. O objetivo principal dessas decisões é minimizar o esforço e maximizar o beneficio. Devido a que o esforço ou o beneficio, em qualquer situação prática, pode ser expresso como uma função de determinadas variáveis de decisão, a otimização pode ser definida como o processo realizado para obter as condições que dão o valor máximo (ou mínimo de uma função), chamada de função objetivo ou função custo.
Na Figura 3.1 pode ser visto que, se um ponto x∗corresponde ao valor mínimo de uma função
f (x), o mesmo ponto corresponde também ao valor máximo do negativo da função, −f(x) [12]. No contexto deste trabalho, todos os problemas de otimização são considerados de minimi- zação, os quais podem ser definidos da seguinte maneira: seja f : ℜn → ℜ, encontrar x∗
∈ ℜn,
para o qual f (x∗) < f (x), i.e., x = (x
1, . . . , xn).
Figura 3.1. Mínimo de f (x) igual ao máximo de −f(x) [12].
plexas entre as variáveis do projeto x e as restrições do sistema, formando um espaço de busca S, e contendo em alguns casos várias soluções ótimas. Dessa forma, surge uma subdivisão das técnicas para a solução de problemas de otimização: otimização local e otimização global. Um ponto x∗ é um ótimo local de f se existe uma vizinhança V = x : |x∗
− x| < ǫ em torno de x∗ tal que f(x∗
) < f (x), ∀x ∈ V ⊂ S ⊆ ℜn. Um ponto x∗ é um ótimo global de f se
f (x∗
) < f (x), ∀x ∈ V ⊂ S ⊆ ℜn, sendo S o espaço de busca [13].
3.1.1 Elementos de um Modelo de Otimização
A solução de um problema de otimização requer como primeira instância uma formulação matemática de um modelo que preserve uma equivalência coerente com o problema real. A abstração de um modelo de otimização envolve múltiplas etapas de tentativa e erro, comumente dependendo de critérios subjetivos, tais como experiência, criatividade e poder de síntese, que não podem ser regulados pelo estabelecimento de regras fixas [13]. Os elementos básicos de um modelo de otimização são descritos a seguir (as definições foram tomadas de [12], [13]):
1. Variáveis de decisão: as variáveis de decisão são as incógnitas que definem a solução do modelo.
2. Espaço de busca: o espaço de busca é o conjunto de pontos que representam as soluções factíveis e infactíveis ao problema de otimização. Esse espaço é determinado pelo limite superior e inferior das variáveis de decisão.
3. Função objetivo: a função objetivo é aquela função matemática que deve ser maximizada ou minimizada e que representa o problema de otimização e as interações entre as variáveis de decisão. Também é referenciada como função custo. O valor da função objetivo avaliada em uma possível solução é conhecido como valor de aptidão.
4. Restrições: as restrições são funções matemáticas que limitam o espaço de soluções factíveis do problema de otimização. São determinadas pelas limitações físicas de sistema.
5. Ótimo local: um ótimo local é um ponto máximo ou mínimo que ocorre em um subespaço do espaço de busca.
6. Ótimo global: o ótimo global é o ponto do espaço de busca onde a função objetivo alcança o valor máximo ou mínimo.
Problemas que envolvem muitos ótimos locais são chamados de multimodais. Entretanto, problemas com um único ótimo global são chamados de unimodais ou problemas convexos [13].
3.1.2 Classificação dos Métodos de Otimização
Segundo S. S. Rao [12], os algoritmos de otimização podem ser classificados de muitas manei- ras: com base na existência de restrições, na natureza das variáveis de projeto, na estrutura física do problema, na natureza das equações envolvidas, no número de funções objetivo, etc. Porém, neste trabalho, estes algoritmos serão classificados em três categorias: (a) métodos exatos, (b) métodos heurísticos e (c) métodos meta-heurísticos.
3.1.2.1
Métodos Exatos
Os métodos exatos geralmente utilizam algoritmos determinísticos para realizar uma busca do espaço de soluções no intuito de encontrar o ótimo global da função objetivo. Técnicas de programação matemática tais como o algoritmo Simplex para programação linear, métodos baseados em derivadas para programação não linear, ou algoritmos de programação dinâmica fazem parte dos métodos exatos. Em muitos problemas de otimização a relação entre as soluções candidatas e o valor de aptidão é complexa, fazendo com que o problema seja difícil de resolver de forma determinística. Adicionalmente, problemas de alta dimensionalidade conduzem a tempos de execução elevados (horas ou dias) e, portanto, algoritmos não determinísticos devem ser considerados [12].
3.1.2.2
Métodos Heurísticos
São métodos que utilizam uma ou mais informações referentes ao problema para guiar o processo de busca de uma solução ótima [31]. Os métodos heurísticos não garantem encontrar a solução ótima de um problema, porém, podem encontrar soluções aceitáveis (sub-ótimas) em um tempo polinomial. A principal desvantagem dos métodos heurísticos é que são desenvolvidos para resolver classes específicas de problemas, carecendo de generalidade [13].
3.1.2.3
Métodos Meta-heurísticos
São métodos de generalização de heurísticas que permitem resolver diversos tipos de pro- blemas sem precisar grandes mudanças nos algoritmos [13]. Estes métodos geralmente utilizam estatísticas obtidas de amostras do espaço de busca que permitem resolver uma ampla gama de problemas, sendo comum a utilização de modelos baseados em fenômenos naturais ou pro- cessos físicos no intuito de aplicar uma filosofia que permita o desenvolvimento de algoritmos heurísticos. Entre as técnicas de otimização meta-heurísticas mais utilizadas podem-se mencio- nar algoritmos bio-inspirados tais como os algoritmos genéticos [32], otimização por colônia de formigas [33], otimização por enxame de partículas [34], entre outros. Os métodos de otimização meta-heurísticos são o foco do presente trabalho.
Neste trabalho, serão considerados os algoritmos de otimização bio-inspirados baseados em populações, já que estes apresentam resultados satisfatórios para problemas de otimização com- plexos, onde as funções objetivo apresentem não linearidades [12], [13]. Na seção 3.1.3, será feita uma descrição mais detalhada dos algoritmos bio-inspirados.
3.1.3 Algoritmos de Otimização Bio-inspirados
Nas últimas décadas tem surgido uma nova ciência computacional baseada em meta-heurísticas inspiradas na natureza, na biologia e em processos físicos denominada computação natural. Esta ciência compreende áreas de atuação em processos de otimização, inteligência artificial (redes neurais artificiais, lógica nebulosa, etc.), biocomputação para análise de DNA, fractais, entre outros.
Algoritmos de otimização bio-inspirados (baseados em populações), dentre os quais se desta- cam os algoritmos evolutivos e os algoritmos de enxames, fazem parte dos métodos de computação natural. Estes algoritmos utilizam técnicas computacionais baseadas nos princípios biológicos evolutivos encontrados na natureza, tais como a seleção natural e herança genética, mutação e comportamentos coletivos para intercâmbio de informação [13].
Os algoritmos bio-inspirados baseados em populações podem ser classificados em dois grupos (vide Figura 3.2): (a) os algoritmos evolutivos e (b) os algoritmos de de enxames. Os algoritmos evolutivos incluem os algoritmos genéticos, a programação evolutiva, estratégias evolutivas e a programação genética. Estas técnicas estão baseadas no princípio de sobrevivência dos mais for- tes, reproduzindo apenas as soluções que mais se aproximam à solução ótima [13]. Além disso, os algoritmos de enxames consideram um conjunto de técnicas baseadas no comportamento co- letivos de algumas espécies naturais, permitindo um intercâmbio eficiente de informação entre os indivíduos de uma colônia. Este conjunto de técnicas é chamado de Inteligência de Enxames. Assim, a estrutura organizacional das abelhas, o caminho ótimo percorrido por uma colônia de formigas e o agrupamento de cardumes de peixes e bandos de aves, na procura de alimento, são somente alguns exemplos do sucesso deste tipo de comportamento social.
Figura 3.2. Classificação dos algoritmos bio-inspirados baseados em popu- lações [13].
Além disso, os algoritmos de otimização bio-inspirados baseados em populações são uma excelente alternativa para a otimização de processos de restauração de imagens em meios suba- quáticos, já que os modelos de degradação de imagens considerados neste trabalho são altamente não-lineares devido aos processos físicos de propagação da luz (vide capítulo 2). Assim, os algo- ritmos de otimização bio-inspirados serão o foco deste trabalho.