A hybrid multi-objective bayesian estimation of distribution algorithm
Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. Estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decision variable space to construct probabilistic models from promising solutions. The...
| Autor principal: | Martins, Marcella Scoczynski Ribeiro |
|---|---|
| Formato: | Tese |
| Idioma: | Inglês |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2017
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/2806 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
riut-1-2806 |
|---|---|
| recordtype |
dspace |
| spelling |
riut-1-28062017-12-21T18:35:20Z A hybrid multi-objective bayesian estimation of distribution algorithm Um algoritmo de estimação de distribuição híbrido multiobjetivo com modelo probabilístico bayesiano Martins, Marcella Scoczynski Ribeiro Delgado, Myriam Regattieri De Biase da Silva http://lattes.cnpq.br/4166922845507601 Lüders, Ricardo http://lattes.cnpq.br/5158617067991861 Delgado, Myriam Regattieri De Biase da Silva Hermida, Roberto Santana Meza, Gilberto Reynoso Pozo, Aurora Trinidad Ramirez Algorítmos computacionais Probabilidades Teoria bayesiana de decisão estatística Algorítmos Otimização matemática Engenharia elétrica Computer algorithms Probabilities Bayesian statistical decision theory Algorithms Mathematical optimization Electric engineering CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. Estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decision variable space to construct probabilistic models from promising solutions. The probabilistic model used in EDA captures statistics of decision variables and their interdependencies with the optimization problem. Moreover, the aggregation of local search methods can notably improve the results of multi-objective evolutionary algorithms. Therefore, these hybrid approaches have been jointly applied to multi-objective problems. In this work, a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA), which is based on a Bayesian network, is proposed to multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and configuration parameters of an embedded local search (LS). We tested different versions of HMOBEDA using instances of the multi-objective knapsack problem for two to five and eight objectives. HMOBEDA is also compared with five cutting edge evolutionary algorithms (including a modified version of NSGA-III, for combinatorial optimization) applied to the same knapsack instances, as well to a set of MNK-landscape instances for two, three, five and eight objectives. An analysis of the resulting Bayesian network structures and parameters has also been carried to evaluate the approximated Pareto front from a probabilistic point of view, and also to evaluate how the interactions among variables, objectives and local search parameters are captured by the Bayesian networks. Results show that HMOBEDA outperforms the other approaches. It not only provides the best values for hypervolume, capacity and inverted generational distance indicators in most of the experiments, but it also presents a high diversity solution set close to the estimated Pareto front. Atualmente, diversas metaheurísticas têm sido desenvolvidas para tratarem problemas de otimização multiobjetivo. Os Algoritmos de Estimação de Distribuição são uma classe específica de metaheurísticas que exploram o espaço de variáveis de decisão para construir modelos de distribuição de probabilidade a partir das soluções promissoras. O modelo probabilístico destes algoritmos captura estatísticas das variáveis de decisão e suas interdependências com o problema de otimização. Além do modelo probabilístico, a incorporação de métodos de busca local em Algoritmos Evolutivos Multiobjetivo pode melhorar consideravelmente os resultados. Estas duas técnicas têm sido aplicadas em conjunto na resolução de problemas de otimização multiobjetivo. Nesta tese, um algoritmo de estimação de distribuição híbrido, denominado HMOBEDA (Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm ), o qual é baseado em redes bayesianas e busca local é proposto no contexto de otimização multi e com muitos objetivos a fim de estruturar, no mesmo modelo probabilístico, as variáveis, objetivos e as configurações dos parâmetros da busca local. Diferentes versões do HMOBEDA foram testadas utilizando instâncias do problema da mochila multiobjetivo com dois a cinco e oito objetivos. O HMOBEDA também é comparado com outros cinco métodos evolucionários (incluindo uma versão modificada do NSGA-III, adaptada para otimização combinatória) nas mesmas instâncias do problema da mochila, bem como, em um conjunto de instâncias do modelo MNK-landscape para dois, três, cinco e oito objetivos. As fronteiras de Pareto aproximadas também foram avaliadas utilizando as probabilidades estimadas pelas estruturas das redes resultantes, bem como, foram analisadas as interações entre variáveis, objetivos e parâmetros de busca local a partir da representação da rede bayesiana. Os resultados mostram que a melhor versão do HMOBEDA apresenta um desempenho superior em relação às abordagens comparadas. O algoritmo não só fornece os melhores valores para os indicadores de hipervolume, capacidade e distância invertida geracional, como também apresenta um conjunto de soluções com alta diversidade próximo à fronteira de Pareto estimada. 2017-12-21T18:35:20Z 2017-12-21T18:35:20Z 2017-12-11 doctoralThesis MARTINS, Marcella Scoczynski Ribeiro. A hybrid multi-objective bayesian estimation of distribution algorithm. 2017. 124 f. Tese (Doutorado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2017. http://repositorio.utfpr.edu.br/jspui/handle/1/2806 eng openAccess application/pdf Universidade Tecnológica Federal do Paraná Curitiba Brasil Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial UTFPR |
| institution |
Universidade Tecnológica Federal do Paraná |
| collection |
RIUT |
| language |
Inglês |
| topic |
Algorítmos computacionais Probabilidades Teoria bayesiana de decisão estatística Algorítmos Otimização matemática Engenharia elétrica Computer algorithms Probabilities Bayesian statistical decision theory Algorithms Mathematical optimization Electric engineering CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica |
| spellingShingle |
Algorítmos computacionais Probabilidades Teoria bayesiana de decisão estatística Algorítmos Otimização matemática Engenharia elétrica Computer algorithms Probabilities Bayesian statistical decision theory Algorithms Mathematical optimization Electric engineering CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica Martins, Marcella Scoczynski Ribeiro A hybrid multi-objective bayesian estimation of distribution algorithm |
| description |
Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. Estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decision variable space to construct probabilistic models from promising solutions. The probabilistic model used in EDA captures statistics of decision variables and their interdependencies with the optimization problem. Moreover, the aggregation of local search methods can notably improve the results of multi-objective evolutionary algorithms. Therefore, these hybrid approaches have been jointly applied to multi-objective problems. In this work, a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA), which is based on a Bayesian network, is proposed to multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and configuration parameters of an embedded local search (LS). We tested different versions of HMOBEDA using instances of the multi-objective knapsack problem for two to five and eight objectives. HMOBEDA is also compared with five cutting edge evolutionary algorithms (including a modified version of NSGA-III, for combinatorial optimization) applied to the same knapsack instances, as well to a set of MNK-landscape instances for two, three, five and eight objectives. An analysis of the resulting Bayesian network structures and parameters has also been carried to evaluate the approximated Pareto front from a probabilistic point of view, and also to evaluate how the interactions among variables, objectives and local search parameters are captured by the Bayesian networks. Results show that HMOBEDA outperforms the other approaches. It not only provides the best values for hypervolume, capacity and inverted generational distance indicators in most of the experiments, but it also presents a high diversity solution set close to the estimated Pareto front. |
| format |
Tese |
| author |
Martins, Marcella Scoczynski Ribeiro |
| author_sort |
Martins, Marcella Scoczynski Ribeiro |
| title |
A hybrid multi-objective bayesian estimation of distribution algorithm |
| title_short |
A hybrid multi-objective bayesian estimation of distribution algorithm |
| title_full |
A hybrid multi-objective bayesian estimation of distribution algorithm |
| title_fullStr |
A hybrid multi-objective bayesian estimation of distribution algorithm |
| title_full_unstemmed |
A hybrid multi-objective bayesian estimation of distribution algorithm |
| title_sort |
hybrid multi-objective bayesian estimation of distribution algorithm |
| publisher |
Universidade Tecnológica Federal do Paraná |
| publishDate |
2017 |
| citation |
MARTINS, Marcella Scoczynski Ribeiro. A hybrid multi-objective bayesian estimation of distribution algorithm. 2017. 124 f. Tese (Doutorado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2017. |
| url |
http://repositorio.utfpr.edu.br/jspui/handle/1/2806 |
| _version_ |
1805320558964899840 |
| score |
10,814766 |