Tagging Game Simulation

After several months of absence due to huge changes in my environment, I've finally spared some time and enthusiasm to invest into my blog! So please be glad dear reader.

Today, I'll take you out for a little and hopefully enjoyable trip into the concept of assigning names to things. This seemingly innocent task is at the center of several contemporary issues surrounding information in the human context. Of course, our long lasting friend Probability Theory comes along with us.

For the purpose of the argument, let's consider the non iterated following game:

Two players are given a common evidence. An evidence is anything the players can identify with good certainty, ranging from single words, to complete works, pictures, etc. The players must then independently come up with an unique word. If the words are the same, then they win the round.

We require the game to be one time because we don't want the players to figure out a cheating strategy, like always returning the same word (although non-matching words can be kept secret to diminish the feasibility of this strategy). Does this game reminds you of something? Actually it is a minimalist version of the ESP game by Luis Von Ahn, which seems to be a pretty efficient way to get good tags on pictures using human minds. His presentation of the work is a must see.

Anyway, we're going to focus on another aspect of the game, namely what is the probability of winning a round? And this should by design also be the probability of the description given by any two players of the evidence being the same, which is in essence the naming problem.

Heuristically, this probability must be pretty low on random evidences. Try something like "sick pigeons fall on people's heads". Candidate 1-word descriptions are for instance: umbrella, stroke, disgusting, absurd, crazy. Then we can try to guess what could be the most "popular" answer for this evidence, and return this one, as it would intuitively increase our chances of winning.

Let's now dive further into a bayesian probabilistic model of the naming game. Let $n$ be a positive integer representing the underlying vocabulary size, $e$ be the random variable representing the evidence (we're not interested in its density function though), and $x$ be the chosen candidate word. For commodity reasons, we'll represent $x$ as an $n$-dimensional vector having one 1 on the coordinate corresponding to the word and 0s everywhere else. The goal is to model the distribution $p(x|e)$, which is in our case a mass function of the form:

$$p(x|e) = \prod_{i=1}^n{\theta_i^{x_i}}$$

where the parameters of the model $\theta_i$ are positive and sum to 1. Notice that each evidence $e$ gets its own set of $\theta$ s. Now, what do the $\theta$ s look like?

A reasonable guess would suppose that they follow something called a Zipf's law. This particular kind of distribution is actually very common in the context of human language (and language in general as a communication protocol) and requires its own post for a decent coverage. In any case, there are both theoretical and practical evidence to support such a choice.

Under this assumption, and for the simplest possible form of a Zipf-like distribution (which is good enough for this back-of-the-envelop model), we can derive our parameters quite simply by:

$\theta_i \propto i^{-s}$

where our words "i" are ordered by decreasing popularity and $1 \leq s$.

We'll fix $n=100,000$ (reasonable for the English language, see AskOxford). $s$ can be seen as a measure of the difficulty of the problem. A low $s$ means a difficult problem where people don't come up with "hit words", and a high $s$ makes the distribution very sharp around the few first words, meaning that some consensus is emerging. As a reference level, $s \sim 1.1$ for the distribution of words in a standard English text.

The model is simple in its outset, but obtaining a nice closed form for $p(x^{(1)}=x^{(2)}|e)$ (namely the probability of 2 independent names being the same) is another challenge. Without loss of generality, given the various independence assumptions, it is straightforward to show that this probability is nothing else than:

$$p=\sum_{i=1}^n{\theta_i^2}$$

And there is no further simplification. In the improbable configuration $n \rightarrow \infty$ and $s>1$ (this condition is not $s>0.5$ because $p(x|e)$ would be otherwise not defined), we have $p \propto \zeta (2s)$, where $\zeta$ is the elusive Riemann's Zeta function.

A sensible range for the values of $s$ is $[1;1.5]$ . Usually, $s=1$ is accepted as a good choice for words frequencies in documents. However, the asymptotic properties of a Zipf distribution having $s=1$ are unpleasant. Because $\sum_{i=1}^n{\frac{1}{i}} \rightarrow \infty$ as $n \rightarrow \infty$, we would have $p \rightarrow 0$ as the vocabulary size grows...

We see how difficult it is to independently give the same name for the same evidence. The naming problem is in general tough stuff, and there are some nice empirical articles in the field of human computer interaction which study how to name the functionalities of a software so that people can easily find what they need.

Agressivité passive à 300km/h

Prendre le TGV, c’est un peu vivre une expérience sociale inattendue à chaque reprise. Non, je ne parle pas des retards et autres incidents qui bien que malvenus n’ont rien d’extraordinaires. Je parle des gens, de mes congénères voyageurs, dont la personnalité semble se réaliser pleinement dans cet espace fermé mais néanmoins public.

Mise en situation : quelqu’un a pris votre place. Que faites-vous?

• Solution 1 : Vous changez de place sans rien dire puisque peu importe, vous êtes seul et vous n’êtes pas un fétichiste des places numérotés.

• Solution 2 : Vous prenez vos précautions et faites remarquer à la personne son mauvais placement et qu’au moindre pépin vous regagnerez votre place.

• Solution 3 : Vous changez de place sans rien dire et vous n’arrêtez pas de répéter à votre fille à très haute voix que « le vilain monsieur a pris nos places ».

• Solution 4 : Horreur ! Vous faites dégager sans ménagement le fraudeur trop baba-cool à votre goût avant que le contrôleur n’ait eu le temps de valider son méfait.

1, 2 ou 4 : vous faites ce que vous voulez tant que vous restez en accord avec vous même, mais par pitié fuyez la 3. D’une part parce que l’on apprend ainsi à sa fille à éviter tout conflit direct sans pour autant se résoudre à accepter son sort et à attendre l’intervention de quelqu’un d’autre que soi-même. Et surtout parce que l’on emmerde tous les autres passagers mal placés (c'est-à-dire tous les non-fétichistes des places numérotées) qui se demandent si les ineptes gesticulations de la pauvre victime lui sont destinés. Si un jour vous êtes le spectateur de ce petit manège, deux choix s’offrent à vous, selon que vous vous sentez l’âme joyeuse ou plutôt sombre. Dans le dernier cas, mettez ostensiblement vos écouteurs et ouvrez un livre, ou mieux, votre ordinateur portable. N’y pensez pas, c’est son problème, pas le votre.

En revanche, dans le premier, il faudra franchement mettre les pieds dans le plat. Demandez-lui suffisamment fort pour que vos voisins l’entendent, qui est le gredin qui a osé le/la léser de ses places. Allez-y franchement, ne faites pas les choses à moitié, sinon vous allez vous retrouver à lui faire la conversation durant tout le trajet (alors que le but de la manœuvre est seulement de contribuer à la sérénité des non-fétichistes de la rame, c'est-à-dire de vous même). Affirmez-lui toute votre indignation face à ces attitudes si peu respectueuses des autres. Rajoutez en des couches tant que la personne ne se décidera pas à prendre une décision. Si elle décide de rester là ou elle est, elle arrêtera à coup sûr de râler, en tout cas elle le gardera pour elle. Sinon elle s’en ira d’elle-même récupérer les places si chères à son cœur, ce qui sera un spectacle des plus divertissants pour tous les voyageurs du wagon!

La prochaine fois je tente cette dernière stratégie, promis. En attendant, une bonne lecture sur ce qu'est le comportement passif agressif ici. A bientôt pour une nouvelle tranche de vie sur les rails!

Démographie de l'au-delà

D'aucuns se sont préoccupés de connaître le statut thermodynamique de l'enfer. En attendant de s'y rendre et de savoir si Theresa a eu raison de rembarrer Tim ainsi, je vous propose aujourd'hui une autre interrogation de prime importance.

En une phrase: Y a t'il plus de personnes vivantes actuellement qu'il n'y a eu de morts jusqu'à présent?

Tout d'abord, la question est de prime importance. Imaginez, demain c'est la guerre entre l'au-delà et ici-bas. La première des choses qu'on aimerait savoir, c'est le camp qui a la supériorité numérique. De plus, il serait fort agaçant d'être pris au dépourvu par un ami qui voudrait parier contre vous sur l'issue de ce combat improbable. Et la question n'est pas si triviale qu'on pourrait passer dessus comme on roulerait sur un joli poussin jaune au milieu de l'autoroute sans même tenter de l'éviter.

En effet, prenons un modèle très grossier pour s'en convaincre. Considérons la démographie humaine comme une suite de générations de tailles exponentielles $(2^i)_i$. À la $n$-ième génération, on se retrouve avec $\sum_0^{n-1}{2^i}=2^n$ décès en tout et pour tout, soit exactement la taille de la génération $n$ en cours. Maintenant que vous êtes convaincus que le problème en est effectivement un, aventurons nous dans un modèle un tantinet plus réaliste, tout en restant très simple.

Soit $p(t)$ la population à un instant $t$. Son évolution est régie par le nombre de naissances $n(t)$ moins le nombre de décès $d(t)$ à ce même instant $t$. Parce que nous préférons travailler avec des taux, on note $\alpha=\frac{n}{p}$ le taux de natalité et $\beta=\frac{d}{p}$ le taux de mortalité. On se trouve donc avec l'équation différentielle suivante:

$\dot{p}=(\alpha_t-\beta_t)p$

Bien sûr, si nous avions toutes les statistiques de la mortalité et la natalité depuis le "début" (c'est quand ça?) de l'humanité, il ne serait pas très coûteux de faire une petite résolution numérique de cette équation. À défaut d'avoir ces données, on peut néanmoins montrer une proprieté basique de ce système. Notons $\Delta(t)$ la différence entre la population à un temps $t$ et le nombre total de morts à ce même temps. On a par définition:

$\Delta(t)=p(t)-\int_0^t{\beta p}$

Tous calculs faits, $\Delta$ varie comme:

$\dot{\Delta}=(\alpha-2\beta)p$

Voici donc le résultat. Si on a pendant une période "suffisante" $\alpha > 2\beta$, alors on finira par avoir plus de vivants que de morts. Inversement, si $\alpha < 2\beta$, les morts seront toujours en supériorité numérique (exponentielle avec le temps). Concrètement parlant, dans un modèle de familles/générations, 4 enfants par couple bi-parental est un minimum pour maintenir l'écart de population entre les vivants et les morts constant. Au dessus: on est plus nombreux que les morts, en dessous, on est écrasé numériquement. Mais il n'y a guère que dans certaines transitions démographiques que l'on observe un tel écart entre natalité et mortalité.

En France, on n'a pas non plus de tels écarts. Conclusion 1: l'au-delà a indéniablement la supériorité numérique. Mais à quoi bon pour une guerre s'il n'est peuplé que de nourrissons et de vieillards? Conclusion 2: la réincarnation n'existe pas en tant que telle, sauf si vous supposez que les âmes se diluent au cours du temps.

Le mystère des cadavres de pigeons manquants

Vous êtes vous déjà demandés où pouvaient bien aller mourir tous ces pigeons des villes, et comment se fait-il qu'on ne croise que si rarement leurs cadavres? Serait-il possible que ces volatiles préfèrent finir leurs jours dans des endroits inaccessibles, comme les gouttières et les recoins des monuments publics par exemple?

En réalité il n'en est rien, et l'explication est quelque peu décevante pour les esprits fantasques qui s'imaginaient déjà les toits de Paris comme un cimetière de pigeons géant. C'est plutôt du côté de la théorie des files d'attente et plus précisément de la loi de Little qu'il faut attendre la solution.

Prenons un cas concret: la ville de Paris. Vous savez qu'il existe environ 80,000 pigeons à Paris. Pour les biens de la cause, vous supposez que cette population est relativement stable, à savoir qu'il y a autant de naissances que de morts, sans vous préoccuper de la mortalité infantile chez les pigeons... Vous savez aussi, ou plutôt vous allez apprendre, que la durée de vie moyenne d'un pigeon est de l'ordre de 7 ans en ville (chiffres de la mairie de Paris - profitez-en pour apprendre à différencier le roucoulement des pigeons ramier et biset!).

En déduire le nombre de décès par jour est alors chose facile, pour peu que vous pensiez le système comme une file d'attente: les naissances correspondent à une arrivée de pigeons dans la file, leur vie comme l'attente dans la file et leur mort comme la sortie de celle-ci. Nous sommes parfaitement dans les conditions d'application de la loi de Little (on ne nous en demande pas trop de ce côté là). On trouve un taux de mortalité $\lambda$ de :

$\lambda=\frac{80000}{7 \times 365} \simeq 30$ pigeons/jour

Ouf! Les services de propreté de la ville de Paris pourront faire face à cette charge de travail et nous ne succomberons pas sous le poids des cadavres de si tôt.

Pour finir de se convaincre qu'il n'existe pas de mystère pigeon, on peut estimer le nombre de cadavres de pigeons croisés du regard en un an de vie parisienne. On suppose que l'on regarde assez attentivement pour y repérer un pigeon mort l'équivalent de la surface de la place de grève ($6.10^3 m^2$) tous les jours. L'approximation est justifiée étant donné notre capacité d'attention limitée et l'efficacité relative du service de propreté. La superficie de Paris étant de $105 km^2$, on a :

$N=365 \times 30 \times \frac{6.10^3 }{105.10^6} \simeq 1$

On tombe en moyenne sur 1 cadavre de pigeon par an, à moins de passer son temps à les chercher. Le mystère étant désormais résolu, nous pouvons dormir sur nos deux oreilles.

Web, Ruptures et Faux-semblants

Facebook, Twitter, gmail, Skype, etc: que signifie à l'heure actuelle dire que l'on effectue une rupture dans sa vie? Est-il possible de parler encore de rupture lorsque l'on continue de recevoir de manière régulièrement sure des nouvelles de tous ceux que l'on a connu un jour, qu'ils aient comptés ou non dans notre vie? Lorsque nous savons qu'à tout moment, il nous est possible de les joindre et de les voir en direct sur notre écran, quel sens donner à l'éloignement physique?

Cette question devient réellement préoccupante lorsqu'il s'agit d'une rupture amoureuse, car dès lors, le risque de manquer de l'espace nécessaire à une reconstruction saine et indépendante est grand. C'est sans doute un des motifs d'abandon soudain d'activité dans les systèmes de type réseaux sociaux, tel Facebook. Qui ne connaît pas d'exemple parmi sa liste de contacts d'un "ami" naguère prolixe en publications mais désormais muet comme un cadavre de carpe au fond d'un rift océanique?

Mais mon propos va plus loin que la rupture amoureuse. Il est des situations où nous sommes au contraire bien aises de disposer de tels outils. C'est en premier lieu le cas lorsque l'on change brusquement d'environnement physique après une longue période d'acclimatation. Cette période nous a vu tisser des liens importants avec certaines personnes, et parfois même très profonds avec un petit nombre d'entre elles. Quitter cet environnement de confort et de certitudes, où nous savions que nous pouvions d'un simple coup de fil partir déjeuner/faire les magasins/dîner/sortir en soirée ou autres avec ses amis, voilà qui est difficile à admettre.

Ce n'est pas tant le fait d'avoir à se faire une place ailleurs qui nous effraye (quoique?). La question obsédante est bien plutôt: "Que restera-t-il de mes amitiés, de toutes celles qui ont fait de moi ce que je suis maintenant?". Nous savons que les choses seront nécessairement différentes après, mais jusqu'à quel point? Si l'on considère l'ensemble de la situation comme un système dynamique décrit par je-ne-sais-quelle équation différentielle vraisemblablement chaotique, dès lors que je ne serais plus en interaction avec quelqu'un, nos deux trajectoires respectives divergeront exponentiellement (sous certaines conditions néanmoins très faibles). Autrement dit, nous n'auront plus rien en commun en quelques années.

Certes, nous ne sommes pas si bêtement déterministes. Nous disposons d'une volonté que l'on aime à croire propre, et qui nous permet de dire, en toutes circonstances "un tel est mon ami, je l'estime et je l'apprécie, etc". Mais la question se pose toujours. Dans ce cadre là, garder des liens grâce au web est une chance. Sans doute pas par les réseaux sociaux, qui ne fonctionnent en dernière analyse que parce qu'il existe une réalité physique réunissant les protagonistes (pensez à toutes ces conversations -creuses- à propos de Facebook à table!), mais bien plutôt grâce aux Skype et autres joyeusetés algorithmiques de traitement des signaux. Malheureusement, même la meilleure des webcams, le meilleur des micros, et la meilleure des connections internet ne remplacera pas une chose aussi triviale qu'un déjeuner entre amis.

Non, internet n'est pas ce lieu qui abolit les distances entre les gens. Il ne saurait l'être, puisque nous avons tous besoin de cette distance, si difficile soit-elle à accepter. En revanche, et pour finir sur une note positive, je ne sais quel écrivain/physicien faisait la comparaison romanesque entre deux cœurs amoureux et deux particules quantiques intriqués. La non-localité du comportement de la paire fera que si grande soit la distance entre les deux cœurs, aucun des deux n'oubliera jamais l'autre...

Structure Learning in Markovian Random Fields: the wrong approach

Here is a map of the problematic. Let $X = (X_1,…,X_l)$ be a composite random variable made of a set of random variables $(X_i)_{1 \leq i \leq l}$. Each $X_i$ takes its values over an alphabet of finite cardinality $m$. We have a sample $(x)$ of $X$ values, of cardinality $n$. The goal is to evaluate the probability distribution of X. This data-mining problem is particularly interesting in the EDAs' context.
So we want to approximate $p(X)$ by analyzing the sample. The following is by definition always true (conditional probability):

$p(X=x)=\prod_{1 \leq i \leq l} p(X_i=x_i|(X_k=x_k)_{i < k \leq l})$

Because of the finite cardinality of the sample, computing directly $p(X)$ or the conditional probabilities above is not feasible by simply counting the occurrence of the events. To put it in a nutshell, Markovian Random Field (MRF) is a distribution probability model which is closed to Bayesian Network. Similarly to BN, MRF natively provides a graphical comprehension of the variable dependencies. However, where BN works by identifying implications between variables, thus resulting in an acyclic directed implication graph, MRF focuses on the notion of clique of variables.

A clique is a subset of $(X_1,…,X_l)$, and each clique $c_i$ has an associated clique function $\psi_i$, called a potential. Cliques are chosen so that $p(X=x)$ factorizes over the $(\psi_i)$. We write:

$p(X=x)=\frac{1}{Z}\prod{\psi_i(\pi_i(x))}$

where $Z$ is (a rather problematic) normalization constant, and $\pi_i$ is the projection operator returning the variables in the clique $c_i$.

Of course, choosing the right cliques from the initial sample, and then learning the clique functions is a complex task.

A good choice for the cliques would be to isolate the strongly coupled variables, i.e. the variables for which the joint probability is very different from the product of the independent probabilities. This is exactly the idea of the Chi-2 test. We will now try to briefly evaluate the efficiency of this technique.

Let’s say we want to find the pairs of strongly coupled variables. The following computes the correlation indicator between variables $X_1$ and $X_2$.

$ I_{1,2} = \sum_{x_1,x_2}\frac{(p_1(x_1)p_2(x_2)-p_{1,2}(x_1,x_2))^2}{p_1(x_1)p_2(x_2)} $

where $p_1(x_1)$ denotes $p(X_1=x_1)$, and so on. We approximate those probabilities by counting the occurrences in the sample. The approximation done this way is good if and only if $m^2 \ll n$ in this case.

Evaluating both $p_1$ and $p_{1,2}$ this way costs at least $O(n)$ ($O(m)$ and $O(m^2)$ in space respectively). Computing $I_{1,2}$ is of complexity $O(n+m^2)$.

So, computing all the $I_{i,j}$ this way would take $O((n+m^2)l^2)$, and $O(l^2)$ of space.
But we notice that in computing the upper triangular part of the $(I_{i,j})$ matrix, we perform several times the same computations. Can we do better?

The trouble is not the $p_i$ computation. It takes $O(nl)$ for computing them all (space complexity: $O(ml)$). The real issue is the joint probabilities. There is no way we can compute them all in linear time as above, because we still have $O(l^2)$ of them to compute, and it doesn't seem that dynamic programming techniques are of any help. So $O(nl^2)$, and we are still left with this ugly $l^2$.

Nevertheless, computation could be parallelized by preparing packets of data. This is an interesting problem, which would require a separate topic.

So, finding 2-cliques in the data is quadratic in the number of variables. What about 3-variable dependencies? Chi-2 test for 3 variables costs $O(n+m^3)$. Thus, computing the 3-dimensional $(I_{i,j,k})$ takes something like $O((n+m^3)l^3)$. Computing the k-variable dependencies would take $O((n+m^k)l^k)$ if $k \leq \frac{n}{2}$.

Let’s say the approximation of $p$ done by counting is correct if $n>10m^k$. Thus $k$ is such as $k \leq [\log_m \frac{n}{10}]$. For $m=4$ (ATGC – genetic code) and $n=10000$, we get $k \leq 6$.

When $n$ is very high (data-mining context), and $m$ very low, the chi-2 method costs $O(nl^k)$, were $k$ is the size of the biggest interaction to be computed. Space complexity is neither lovely! This is one big reason why the problem of finding cliques, i.e. the structure of MRFs, is currently addressed by heuristic methods, such as greedy hill climbing. Your favorite search engine will probably return some interesting results on the title of this article (careful though, only the first part of it)!

Pourquoi ce blog?

Vague étonnement et un peu d'incompréhension de la part d'un proche cette après-midi :

Qu'est ce qu'il te prend de faire un blog tout d'un coup? Ça ne te dérange pas de montrer qui tu es au premier venu du web? Cela répond-il à un besoin quelconque?

Pas de doutes, j'ai mis les deux pieds dans le plat avec ce blog! Ces interrogations bien légitimes, ce sont aussi les miennes. Ce sont celles que tout blogueur se pose depuis le tout début. Car le web, ce n'est pas la place du village où circulent des gens avec lesquels vous pourrez toujours faire plus ample connaissance si l'envie vous en prend. Le web est un espace unidirectionnel dans lequel toutes sortes d'individus et d'organisations peuvent récolter ce que vous y avez semé, et de manière beaucoup plus efficace que ce que le commun des mortels s'imagine. Les techniques de datamining existent depuis des dizaines d'années, et l'explosion des données disponibles à la volée constitue un mets de choix. Et lorsque l'on connaît un peu la nature humaine, il est contradictoire de prétendre que l'on n'a jamais rien à cacher sur Internet! Ce n'est pas une question de honte, c'est une exigence de rationalité. Il est par conséquent nécessaire de se fixer des limites à ne pas franchir. En ce qui me concerne, bloguer n'est pas parler à un confident, à un ami, ni même à un parfait inconnu. L'anonymat du web et l'anonymat de l'inconnu sont incommensurables. Ainsi, il ne sera jamais question sur ce blog de détails dits "personnels" de la vie de quiconque, et a fortiori de tous ceux que je connais.

Bloguer, c'est d'abord laisser une trace pour les autres de ce que l'on juge important, beau, nécessaire ou simplement drôle. Cela est peut-être une façon détournée d'exposer sa vie, car ces choses sont constitutives de notre existence même. Mais c'est aussi la raison pour laquelle il y a tant d'écrivains et tant de livres. Nous espérons confusément être un jour utile à quelqu'un, éveiller en cette personne des pensées semblables aux nôtres, partager l'expérience de la condition humaine pour emprunter les termes d'Hannah Arendt.

Le blog est avant tout une création (plus ou moins "artistique"). Il est le résultat d'une production humaine, qui in fine ne possède pas de réponse à la question du pourquoi. Pour ma part, bloguer est une nouvelle expérience. Je verrai bien où elle me mènera. Carpe diem!

Evolutionary metaheuristics: what is a suitable fitness function?

Evolutionary metaheuristic methods such as Genetic Algorithms, or more recently Estimation of Distribution Algorithms are useful when the optimization problem to solve presents no apparent structure.

In other words, when you have to find an $x_0$ living in a domain $D$ such as

$f(x_0)=\max_{x \in D} f(x)$

you have either:

1. A messy domain $D$, for example a huge discret domain
   
2. A messy function $f$, for example a non-convex or discontinuous one

you may reasonably invoke these metaheuristics. In the evolutionary metaheuristics, $f$ is called the fitness function, and a population $P \subset D$ is evolved towards the high values of $f$. Finally, you can pick your $x_0$ in $P$ if all went well.

However, as exciting as evolutionary computing may sound, this tool will perform poorly, and even fail to evolve any population when applied on ill designed fitness functions. The existence of such unfriendly functions is given by the famous no free lunch theorem(s). It states that for static optimization tasks such as ours, when benchmarking any algorithm over all the possible $f$ functions, it performs as well as a random search over $D$. Or in other words, any given algorithm can't be better than any other one on all possible fitness functions. Again: for each and every optimization algorithm, there is a disastrous class of $f$ functions on which it fails computing a good solution. This result holds independently of the type of algorithm. They are all included, even the ones we don't know yet! There is no static optimization algorithm performing well on every $f$, just like there is no hotel serving free lunches everyday.

This is a theoretical result: it may seem the space where the $f$ functions are living is so huge, we won't even be capable of exhibiting such disastrous functions for evolutionary algorithms. As a matter of fact, we can!

Disclaimer: the following part is solely based on my previous experience with evolutionary algorithms. It doesn't rely on a truly scientific evidence, just on my own intuition.

Genetic Algorithms and Estimation of Distribution Algorithms rely implicitly on a minimal local stability of the fitness function.

Let $\delta$ be a distance over $D$. For convenience, we assume that $f(D) \subset \mathbb{R}$. Minimal local stability means that for almost any $x$ in $D$, slightly changing $x$ will only reasonably affect $f(x)$. This is (a little bit more) formalized by:

$\exists e, C > 0; e \sim \min_{x \neq y} {\delta(x,y)}; C \ll \max{f} - \min{f}$
for almost any $x,y \in D$
$\delta(x,y) \leq e \Rightarrow \mid f(x) - f(y) \mid < C$

The local discontinuities of the fitness don't matter, because they are soon assimilated by the population in GA or the distribution model for EDA. Everywhere else, the behavior of the fitness is kind of predictable, and we can rely on this stability to carry out the evolution process. In EDA, local stability plays a major role, because it ultimately legitimates the approximations done during the learning of the model parameters.

In GA, when we are crossing-over (notation $\otimes$) $x$ and $y$, we hope that, most of the time, $f(x \otimes y)$ will be comparable to $\max(f(x),f(y))$. On the early stages of evolving $P$, we can say that the algorithm is searching for a stability zone in $D$, where this assumption can be made. The existence of this stability zone in $D$ is to my mind related to the propriety of local stability of $f$. One heuristic argument in favor of this assumption, is that GA will fail when $f$ is discontinuous everywhere, because of the induced randomness. There is no direction to go for the algorithm with such a messy fitness function.

The moral of the story is to always check if the fitness function has some kind of regularity. If $f$ is locally stable, we can hope that the algorithms will perform honorably. However, this is probably only a necessary condition for good results...