Basque Center for Applied Mathematics (BCAM) and University of the Basque Country, Spain
Follow the talks in the SPECIES Society youtube channel.
The goal of this talk is to provide new views on combinatorial optimization problems. Particularly we consider two different scenarios which produce different rich information about the problems. In a first scenario we consider instances of combinatorial optimization problems as ranking of the elements of the search space. This allows us to compute those instances that are in the intersection between different combinatorial optimization problems. In a second scenario we use the Fourier transform. After calculating the Fourier coefficients of several problems we manage to discover their intrinsic dimensionalities, i.e. the minimum number of parameters required to define an instance of the problem.Furthermore, the Fourier coefficients equip us with the possibility to exactly compute the dimension of the intersection between different problems. This can give the base for transferring algorithms designed for one problem to a different problem.
Jose A. Lozano received his M.Sc. degree in mathematics and PhD in computer science from the University of the Basque Country UPV/EHU, in Spain, in 1992 and 1998 respectively. He has been a full professor at the University of the Basque Country since 2008 where he leads the Intelligent Systems Group. Since January 2019 he is the scientific director of the Basque Center for Applied Mathematics (Spain). Prof. Lozano has authored more than 110 ISI journal papers, some of them have become highly cited papers. His current research interests include combinatorial optimization, machine learning and its synergies with optimization in general and supervised classification, time series analysis and Bayesian inference in particular. Prof. Lozano has served on the organizing and program committee of over 60 international conferences being the general chair of IEEE Congress on Evolutionary Computation (IEEE CEC 2017) and the editor-in-chief of the Genetic and Evolutionary Computation Conference (GECCO 2020). He also serves as Associate Editor of top journals such as IEEE Trans. on Evolutionary Computation, Evolutionary Computation and IEEE Trans. on Neural Network and Learning Systems, to name but a few.
The importance of data is undisputable in science, and it is often believed that more, and more accurate, data always lead to a better understanding of the phenomena. However, the great times in science are those where data and theories grow hand-in-hand, while progress is slow when there is an imbalance between the richness of data and that of theories. Nowadays, data seem to lag behind theories in fundamental physics, while the opposite happens in biology, where there is a huge and ever-growing amount of available data, with very few general principles to interpret them.
Due to their scarcity, these principles are particularly valuable and an interesting candidate is the “criticality principle” (CP for short), which claims that dynamical states, which are neither fully ordered nor fully disordered, are advantaged with respect either to chaotic states, since they are more stable and controllable, or to ordered ones, since they can better change in response to different conditions. If this is indeed the case, evolution should have driven living beings towards critical states: this means that the values of the parameters of the corresponding dynamical systems should be critical, or close to criticality.
In the importante case gene regulatory networks (GRNs), it is possible to draw inferences about their dynamical regimes from available data, with the support of mathematical models, most notably Boolean networks. Although the cases which have been analyzed so far do not allow one to draw definitive conclusions, it seems that GRNs in different biological organisms are often found to be critical or close to criticality. These evidences will be discussed, emphasizing the interesting interplay between experimental data, dynamical models and general principles.
It is interesting to ascertain whether the CP might apply also to artificial evolving systems, like those studied in evolutionary computation. One can consider for example the evolution of Boolean models of GRNs, which are required to reach a state with some peculiar features or to perform some task, under the action of a Genetic Algorithm (GA). Starting from purely random Boolean networks (RBNs) the GA leads to networks which are no longer completely random. In several interesting cases the desired performance level can indeed be achieved, although the evolved artificial networks are not always critical. The reasons why this happens will be discussed.
On the other hand, biological systems, which live in changing environments, seem indeed critical or close to criticality. This might be explained by the higher evolvability of critical systems, which is confirmed by numerical experiments on Boolean networks which will be reviewed. It will also be shown that it is possible to evolve “always-critical” Boolean networks, by constraining the networks generated by the GA to stay on a critical boundary, without compromising the possibility of solving some non-trivial tasks with interesting biological significance.
The above results are based on the usual definition of dynamical criticality. In the case of strongly non-ergodic systems like RBNs some interesting alternatives have been proposed, and they will be reviewed and discussed at the end of the talk.
Roberto Serra graduated in Physics at the University of Bologna, where he was awarded the Guglielmo Marconi prize as the best graduate of his academic year. He later performed research activities for more than 20 years in different industrial groups (including the multinational groups Eni and Montedison) where he led various research groups; he served as director of the Montedison Environmental Research Centre for almost 10 years (1995-2004).In 2004 he moved to academia and became full professor of Complex Systems at the University of Modena and Reggio Emilia. He is also a Fellow and a Member of the Science Board of the European Centre for Living Technologies (an international research organization in Venice) and a Fellow of the Institute for Advanced Study of the University of Amsterdam. Roberto Serra has also been president of AI*IA (Associazione Italiana per l’ Intelligenza Artificiale) and chairman of the Science Board of the European Centre for Living Technologies. His research interests concern several aspects of the dynamics of complex systems, paying particular attention to biological systems. The most relevant recent works concern models of genetic networks and of protocells, and methods based on information theory to identify relevant sets of integrated variables in complex systems.