| Echegoyen C, Mendiburu A, Santana R and Lozano JA (2013), "On the Taxonomy of Optimization Problems under Estimation of Distribution Algorithms", Evolutionary Computation. Vol. 21(3), pp. 471-495. |
| Abstract: Understanding the relationship between a search algorithm and the space of problems is a fundamental issue in the optimization field. In this paper, we lay the foundations to elaborate taxonomies of problems under estimation of distribution algorithms (EDAs). By using an infinite population model and assuming that the selection operator is based on the rank of the solutions, we group optimization problems according to the behavior of the EDA. Throughout the definition of an equivalence relation between functions it is possible to partition the space of problems in equivalence classes in which the algorithm has the same behavior. We show that only the probabilistic model is able to generate different partitions of the set of possible problems and hence, it predetermines the number of different behaviors that the algorithm can exhibit. As a natural consequence of our definitions, all the objective functions are in the same equivalence class when the algorithm does not impose restrictions to the probabilistic model. The taxonomy of problems, which is also valid for finite populations, is studied in depth for a simple EDA that considers independence among the variables of the problem. We provide the sufficient and necessary condition to decide the equivalence between functions and then we develop the operators to describe and count the members of a class. In addition, we show the intrinsic relation between univariate EDAs and the neighborhood system induced by the Hamming distance by proving that all the functions in the same class have the same number of local optima and that they are in the same ranking positions. Finally, we carry out numerical simulations in order to analyze the different behaviors that the algorithm can exhibit for the functions defined over the search space 0,13. |
BibTeX:
@article{Echegoyen_et_al:2013,
author = {C. Echegoyen and A. Mendiburu and R. Santana and J. A. Lozano},
title = {On the Taxonomy of Optimization Problems under Estimation of Distribution Algorithms},
journal = {Evolutionary Computation},
year = {2013},
volume = {21},
number = {3},
pages = {471-495},
url = {http://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00095}
}
|
| Karshenas H, Santana R, Bielza C and Larrañaga P (2013), "Regularized Continuous Estimation of Distribution Algorithms", Applied Soft Computing. Vol. 13(5), pp. 2412-2432. |
| Abstract: Regularization is a well-known technique in statistics for model estimation which is used to improve the generalization ability of the estimated model. Some of the regularization methods can also be used for variable selection that is especially useful in high-dimensional problems. This paper studies the use of regularized model learning in estimation of distribution algorithms (EDAs) for continuous optimization based on Gaussian distributions. We introduce two approaches to the regularized model estimation and analyze their effect on the accuracy and computational complexity of model learning in EDAs. We then apply the proposed algorithms to a number of continuous optimization functions and compare their results with other Gaussian distribution-based EDAs. The results show that the optimization performance of the proposed RegEDAs is less affected by the increase in the problem size than other EDAs, and they are able to obtain significantly better optimization values for many of the functions in high-dimensional settings. |
BibTeX:
@article{Karshenas_et_al:2013,
author = {H. Karshenas and R. Santana and C. Bielza and P. Larrañaga},
title = {Regularized Continuous Estimation of Distribution Algorithms},
journal = {Applied Soft Computing},
year = {2013},
volume = {13},
number = {5},
pages = {2412--2432},
url = {https://www.sciencedirect.com/science/article/pii/S1568494612005376}
}
|
| Larrañaga P, Karshenas H, Bielza C and Santana R (2013), "A Review on Evolutionary Algorithms in Bayesian Network Learning and Inference Tasks", Information Sciences. Vol. 233(1), pp. 109-125. |
| Abstract: Thanks to their inherent properties, probabilistic graphical models are one of the prime candidates for machine learning and decision making tasks especially in uncertain domains. Their capabilities, like representation, inference and learning, if used effectively, can greatly help to build intelligent systems that are able to act accordingly in different problem domains. Bayesian networks are one of the most widely used class of these models. Some of the inference and learning tasks in Bayesian networks involve complex optimization problems that require the use of meta-heuristic algorithms. Evolutionary algorithms, as successful problem solvers, are promising candidates for this purpose. This paper reviews the application of evolutionary algorithms for solving some NP-hard optimization tasks in Bayesian network inference and learning. |
BibTeX:
@article{Larranaga_et_al:2013,
author = {P. Larrañaga and H. Karshenas and C. Bielza and R. Santana},
title = {A Review on Evolutionary Algorithms in Bayesian Network Learning and Inference Tasks},
journal = {Information Sciences},
year = {2013},
volume = {233},
number = {1},
pages = {109-125},
url = {https://www.sciencedirect.com/science/article/pii/S0020025513000443}
}
|
| Santana R and Mendiburu A (2013), "Model-based template-recombination in Markov network estimation of distribution algorithms for problems with discrete representation", In 2013 Third World Congress on Information and Communication Technologies (WICT 2013). , pp. 170-175. |
| Abstract: While estimation of distribution algorithms (EDAs) based on Markov networks usually incorporate efficient methods to learn undirected probabilistic graphical models (PGMs) from data, the methods they use for sampling the PGMs are computationally costly. In addition, methods for generating solutions in Markov network based EDA frequently discard information contained in the model to gain in efficiency. In this paper we propose a new method for generating solutions that uses the Markov network structure as a template for crossover. The new algorithm is evaluated on discrete deceptive functions of various degrees of difficulty and Ising instances. |
BibTeX:
@inproceedings{Santana_and_Mendiburu:2013,
author = {Santana, Roberto and Mendiburu, Alexander},
title = {Model-based template-recombination in Markov network estimation of distribution algorithms for problems with discrete representation},
booktitle = {2013 Third World Congress on Information and Communication Technologies (WICT 2013)},
year = {2013},
pages = {170--175},
url = {https://ieeexplore.ieee.org/document/7113130?signout=success}
}
|
| Santana R, Armañanzas R, Bielza C and Larrañaga P (2013), "Network measures for information extraction in evolutionary algorithms", International Journal of Computational Intelligence Systems. Vol. 6(6), pp. 1163-1188. |
| Abstract: Problem domain information extraction is a critical issue in many real-world optimization problems. Increasing the repertoire of techniques available in evolutionary algorithms with this purpose is fundamental for extending the applicability of these algorithms. In this paper we introduce a unifying information mining approach for evolutionary algorithms. Our proposal is based on a division of the stages where structural modelling of the variables interactions is applied. Particular topological characteristics induced from different stages of the modelling process are identified. Network theory is used to harvest problem structural information from the learned probabilistic graphical models (PGMs). We show how different statistical measures, previously studied for networks from different domains, can be applied to mine the graphical component of PGMs. We provide evidence that the computed measures can be employed for studying problem difficulty, classifying different problem instances and predicting the algorithm behavior. |
BibTeX:
@article{Santana_et_al:2013,
author = {R. Santana and R. Armañanzas and C. Bielza and P. Larrañaga},
title = {Network measures for information extraction in evolutionary algorithms},
journal = {International Journal of Computational Intelligence Systems},
year = {2013},
volume = {6},
number = {6},
pages = {1163-1188},
url = {https://www.atlantis-press.com/article/25868449.pdf}
}
|
| Santana R, McKay RI and Lozano JA (2013), "Symmetry in evolutionary and estimation of distribution algorithms", In Proceedings of the 2013 Congress on Evolutionary Computation CEC-2013. Cancun, Mexico , pp. 2053-2060. IEEE Press. |
| Abstract: Symmetry has hitherto been studied piecemeal in a variety of evolutionary computation domains, with little consistency between the definitions. Here we provide formal definitions of symmetry that are consistent across the field of evolutionary computation. We propose a number of evolutionary and estimation of distribution algorithms suitable for variable symmetries in Cartesian power domains, and compare their utility, integration of the symmetry knowledge with the probabilistic model of an EDA yielding the best outcomes. We test the robustness of the algorithm to inexact symmetry, finding adequate performance up to about 1% noise. Finally, we present evidence that such symmetries, if not known a priori, may be learnt during evolution. |
BibTeX:
@inproceedings{Santana_et_al:2013a,
author = {R. Santana and R. I. McKay and J. A. Lozano},
title = {Symmetry in evolutionary and estimation of distribution algorithms},
booktitle = {Proceedings of the 2013 Congress on Evolutionary Computation CEC-2013},
publisher = {IEEE Press},
year = {2013},
pages = {2053-2060},
url = {https://ieeexplore.ieee.org/document/6557811}
}
|
| Santana R, Mendiburu A and Lozano JA (2013), "Message passing methods for estimation of distribution algorithms based on Markov networks", In Proceedings of the 4th Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO-2013). Chennai, India , pp. 419-430. Springer. |
| Abstract: Sampling methods are a fundamental component of estimation of distribution algorithms (EDAs). In this paper we propose new methods for generating solutions in EDAs based on Markov networks. These methods are based on the combination of message passing algorithms with decimation techniques for computing the maximum a posteriori solution of a probabilistic graphical model. The performance of the EDAs on a family of non-binary deceptive functions shows that the introduced approach improves results achieved with the sampling methods traditionally used by EDAs based on Markov networks. |
BibTeX:
@inproceedings{Santana_et_al:2013b,
author = {R. Santana and A. Mendiburu and J. A. Lozano},
title = {Message passing methods for estimation of distribution algorithms based on Markov networks},
booktitle = {Proceedings of the 4th Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO-2013)},
publisher = {Springer},
year = {2013},
pages = {419-430},
url = {https://link.springer.com/chapter/10.1007/978-3-319-03756-1_38}
}
|
| Santana R, Mendiburu A and Lozano JA (2013), "Critical issues in model-based surrogate functions in estimation of distribution algorithms", In Proceedings of the 4th Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO-2013). Chennai, India , pp. 1-13. Springer. |
| Abstract: In many optimization domains the solution of the problem can be made more efficient by the construction of a surrogate fitness model. Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms particularly suitable for the conception of model-based surrogate techniques. Since EDAs generate probabilistic models, it is natural to use these models as surrogates. However, there exist many types of models and methods to learn them. The issues involved in the conception of model-based surrogates for EDAs are various and some of them have received scarce attention in the literature. In this position paper, we propose a unified view for model-based surrogates in EDAs and identify a number of critical issues that should be dealt with in order to advance the research in this area. |
BibTeX:
@inproceedings{Santana_et_al:2013c,
author = {R. Santana and A. Mendiburu and J. A. Lozano},
title = {Critical issues in model-based surrogate functions in estimation of distribution algorithms},
booktitle = {Proceedings of the 4th Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO-2013)},
publisher = {Springer},
year = {2013},
pages = {1-13},
url = {https://link.springer.com/chapter/10.1007/978-3-319-03756-1_1}
}
|
| Santana R, McGarry L, Bielza C, Larrañaga P and Yuste R (2013), "Classification of neocortical interneurons using affinity propagation", Frontiers in Neural Circuits. Vol. 7, pp. 1-13. |
| Abstract: In spite of over a century of research on cortical circuits, it is still unknown how many classes of cortical neurons exist. In fact, neuronal classification is a difficult problem because it is unclear how to designate a neuronal cell class and what are the best characteristics to define them. Recently, unsupervised classifications using cluster analysis based on morphological, physiological, or molecular characteristics, have provided quantitative and unbiased identification of distinct neuronal subtypes, when applied to selected datasets. However, better and more robust classification methods are needed for increasingly complex and larger datasets. Here, we explored the use of affinity propagation, a recently developed unsupervised classification algorithm imported from machine learning, which gives a representative example or exemplar for each cluster. As a case study, we applied affinity propagation to a test dataset of 337 interneurons belonging to four subtypes, previously identified based on morphological and physiological characteristics. We found that affinity propagation correctly classified most of the neurons in a blind, non-supervised manner. Affinity propagation outperformed Ward's method, a current standard clustering approach, in classifying the neurons into 4 subtypes. Affinity propagation could therefore be used in future studies to validly classify neurons, as a first step to help reverse engineer neural circuits. |
BibTeX:
@article{Santana_et_al:2013d,
author = {R. Santana and L. McGarry and C. Bielza and P. Larrañaga and R. Yuste},
title = {Classification of neocortical interneurons using affinity propagation},
journal = {Frontiers in Neural Circuits},
year = {2013},
volume = {7},
pages = {1-13},
url = {https://www.frontiersin.org/articles/10.3389/fncir.2013.00185/full}
}
|
| Santana R, Bielza C and Larrañaga P (2013), "Changing conduction delays to maximize the number of polychronous groups with an estimation of distribution algorithm". Research Report at: Department of Artificial Intelligence, Faculty of Informatics, Technical University of Madrid. (UPM-FI/DIA/2013-1) |
| Abstract: Spiking network polychronization refers to reproducible time-locked but not synchronous firing patterns with millisecond precision. There are many factors that influence the number of polychronous groups in spiking networks. In this paper we address the question of maximizing the number of polychronous groups by biasing the axonal conduction delay values of the spiking network. An estimation of distribution algorithm (EDA) that learns tree models to search for spiking networks with optimal delay configurations is used. An analysis of the evolved networks show a higher number of polychronous groups with respect to networks with random delay values. We evaluate to what extent the spiking network structure is reflected in the probabilistic models learned by the EDA. Finally, we introduce the informative edge ranking measure r that quantifies how much of the original spiking network structure is captured in the tree models. |
BibTeX:
@techreport{Santana_et_al:2013e,
author = {R. Santana and C. Bielza and P. Larrañaga},
title = {Changing conduction delays to maximize the number of polychronous groups with an estimation of distribution algorithm},
school = {Department of Artificial Intelligence, Faculty of Informatics, Technical University of Madrid},
year = {2013},
number = {UPM-FI/DIA/2013-1},
url = {https://www.researchgate.net/publication/275408208_Changing_conduction_delays_to_maximize_the_number_of_polychronous_groups_with_an_estimation_of_distribution_algorithm}
}
|
| Santana R, Mendiburu A and Lozano JA (2013), "Extending the use of message passing algorithms to problems with unknown structure", In 2013 NIPS Workshop on Bayesian Optimization. , pp. 1-8. |
| Abstract: We investigate the behavior of message passing algorithms (MPAs) on approximate probabilistic graphical models (PGMs) learned in the context of optimization. We use the framework of estimation of distribution algorithms (EDAs), a class of optimization algorithms that learn in each iteration a PGM and sample new solutions from it. The impact that including the most probable configuration of the model has for EDAs is evaluated using a variety of MPAs on different instances of the Ising problem. |
BibTeX:
@inproceedings{Santana_et_al:2013f,
author = {Santana, Roberto and Mendiburu, Alexander and Lozano, Jose A},
title = {Extending the use of message passing algorithms to problems with unknown structure},
booktitle = {2013 NIPS Workshop on Bayesian Optimization},
year = {2013},
pages = {1--8},
url = {https://www.researchgate.net/profile/Roberto-Santana/publication/275408229_Extending_the_use_of_message_passing_algorithms_to_problems_with_unknown_structure/links/553bb6120cf29b5ee4b87c0b/Extending-the-use-of-message-passing-algorithms-to-problems-with-unknown-structure.pdf}
}
|
| Santana R (2013), "Multi-objective optimization approach to detecting extremal patterns in social networks", In 2013 Third World Congress on Information and Communication Technologies (WICT 2013). , pp. 196-201. |
| Abstract: This paper introduces the use of extremal patterns as a way to characterize social networks. The concepts of Pareto-dominance, multi-objective optimization, and estimation of distribution algorithms are integrated in a general strategy to compute the multiple extremal patterns. The algorithm is applied to the identification of sets of subjects that have the broadest direct network reachability in a social network extracted from the Reality mining dataset. |
BibTeX:
@inproceedings{Santana:2013,
author = {R. Santana},
title = {Multi-objective optimization approach to detecting extremal patterns in social networks},
booktitle = {2013 Third World Congress on Information and Communication Technologies (WICT 2013)},
year = {2013},
pages = {196--201},
url = {https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7113134}
}
|
| Santana R (2013), "A detailed investigation of classification methods for vowel speech imagery recognition". Research Report at: Department of Computer Science and Artificial Intelligence, University of the Basque Country., December, 2013. (hdl.handle.net/10810/4562) |
| Abstract: Accurate and fast decoding of speech imagery from electroencephalographic (EEG) data could serve as a basis for a new generation of brain computer interfaces (BCIs), more portable and easier to use. However, decoding of speech imagery from EEG is a hard problem due to many factors. In this paper we focus on the analysis of the classification step of speech imagery decoding for a three-class vowel speech imagery recognition problem. We empirically show that different classification subtasks may require different classifiers for accurately decoding and obtain a classification accuracy that improves the best results previously published. We further investigate the relationship between the classifiers and different sets of features selected by the common spatial patterns method. Our results indicate that further improvement on BCIs based on speech imagery could be achieved by carefully selecting an appropriate combination of classifiers for the subtasks involved. |
BibTeX:
@techreport{Santana:2013a,
author = {R. Santana},
title = {A detailed investigation of classification methods for vowel speech imagery recognition},
school = {Department of Computer Science and Artificial Intelligence, University of the Basque Country},
year = {2013},
number = {hdl.handle.net/10810/4562},
url = {https://addi.ehu.es/bitstream/handle/10810/11154/tr13-2.pdf?sequence=1}
}
|