Mentales habitudes

Aller au contenu | Aller au menu | Aller à la recherche

Anecdotique

Fil des billets

lundi 19 octobre 2015

Paris discret, province continue

La France a une particularité culturelle intéressante liée à la position de sa capitale : Paris est au centre de tout. Il parait que cela fait 4 siècles que ça dure et que ça n'est pas prêt de s'arrêter. Je ne vais pas ici faire un énième édito sur les avantages ou les inconvénients de la métropolisation économico-politico-culturelle française, mais plutôt vous raconter un effet que je trouve intéressant sur la psychologie des français.

Cet effet se résume ainsi : les provinciaux raisonnent de manière continue alors que les parisiens ont un esprit discret (au sens de discontinu). Par « parisien », j'entends quelqu'un habitant depuis plusieurs années dans Paris, temps nécessaire suffisant pour qu'il se soit adapté.

Cette constatation a pris jour dans mon esprit suite au changement de signalétique dans le « pôle RER » de Châtelet-les-Halles (une des plus grosses station de métro de Paris) : la simple mention des points cardinaux à coté de la direction des lignes.

 Ligne (A) : Ouest -- Cergy

Mes amis parisiens ont été unanimes à propos de ce changement : « ça ne sert à rien » alors que nombre de provinciaux on fait part de leur satisfaction. En effet, si vous demandez à un parisien où se trouve la gare de l'Est dans paris, il y a de forte chance qu'il vous réponde « dans le 10e », là où un provincial vous gratifiera d'un « ben, à l'est » narquois. De la même manière, un parisien n'habite pas « au sud-est de Paris », il habite « entre Bastille et Nation », alors qu'un provincial habite « au nord-est d'Angers » et pas « entre Pellouailles-les-Vignes et Écouflant ».

Autre différence notable : la perception de l'espace-temps. Un parisien demandera si votre rendez-vous est loin et s'attendra à ce que vous lui répondiez « 4-5 stations, mais il y a un changement », alors qu'un provincial ne saura de quoi il retourne que si vous lui dites « environ 15 minutes ». S'il doit sortir du réseau de métro, le parisien raisonnera en kilomètres, ce qui laissera le provincial dubitatif, surtout s'il connaît les bouchons parisiens. Ainsi, il sera difficile pour un parisien habitant le quartiers de Montparnasse d'envisager de prendre le train pour aller à Épernon (80 km), alors qu'il ne verra pas trop d'inconvénient à aller à la Villette (9 km), ce qui pourra attrister le provincial, pour qui ces deux trajets font 40 minutes en transports en communs.

Je tiens à préciser que ces deux types de raisonnements sont le fruit d'une adaptation à l'environnement : les attendus provinciaux ne seraient pas adaptés à Paris, tout comme le comportement parisien ne serait pas efficace en province. Par exemple, le provincial comme le parisien aime avoir la liberté de pouvoir rentrer de soirée quand il le souhaite, mais ce simple souhait produit des a priori diamétralement opposés. Un parisien sera réticent à aller passer une soirée en province, car il sait que cela va être pénible de ne pas rater le dernier train et que l'avant-dernier passe une heure plus tôt. De la même façon, le provincial trouve pénible de sortir sur Paris, car y trouver une place de parking est très difficile ou coûte cher. Autre exemple : si un parisien ne vous invite pas chez lui mais toujours dans un bar, c'est parce qu'il n'a simplement pas la place de vous héberger, vous et ses amis. Et si un provincial ne vient jamais boire un coup avec vous, c'est parce qu'il ne peut pas organiser un voyage de deux heures (aller-retour) au dernier moment.

La victoire (toute relative) de l'esprit provincial à Châtelet-les-Halles illustre cette petite différence et met en avant le fait que le cerveau humain est extrêmement capable d'apprendre des modèles généraux et à les appliquer partout où il peut. L'esprit parisien raisonne en terme de lieux relativement séparés alors que l'esprit provincial manipule des directions et des temps plutôt continus.

Garder cette différence à l'esprit peut vous aider à éviter de tomber trop facilement dans les stéréotypes faciles, alors ne vous en privez pas.

lundi 17 novembre 2008

More on "stochastic local search" definition

Petr Pošík let an interesting comment on a previous post : "Metaheuristic" or "Stochastic Local Search"?. As bloggers always love worthwhile comments from insightful readers, I copy it here, as an article, along with my answer.

I would like to present here an idea that will take the "stochastic" and "local" idea even more further than Thomas and Dirk. In that view, even GAs are local search techniques! Why?

It has a lot to do with the definition of neighborhood of the current state of the algorithm. The state may be the position of an algorithm in the search space. In classical local search, the state is given by mere 1 point. In population-based techniques, the state is the whole population. New solutions are usually generated only by local modifications of the state, i.e. the search takes place only in the local neighborhood of the algorithm state.

Yes, of course, the local neighborhood of the population as a whole is very broad and such a local search is much less prone to premature convergence and exhibits a kind of global behaviour. But, IMHO, it is still a local search...

I completely understand your view: if there is a non-zero probability of generating any solution in the search space, then the search must eventually find the global optimum, and thus performs a global search.

This is the case for many stochastic local search algorithm in continuous domain which use e.g. normal distribution. But if you set the variance too high, you will get very slow convergence to that global optimum which is in practice not desirable. If you set variance too low, you will quickly find local optimum, but you will have to wait for the global one virtually infinitely long - again undesirable. Or, put it in another way, would you call a "global optimization" technique still "global" if it takes zilions of years to find that global solution?

In practice, I think, for continuous spaces we have to resort to algorithms that exhibit local behavior since we always have some hard constraints on the length of the optimization run. In my eyes, this perfectly justifies the name "stochastic local search".

In fact, as far as I comprehend them, both Dick Thierens and Thomas Stützle shares your point of view. For them, GA are a kind of stochastic local search.

I find the classification in "descent" algorithm and "population" ones quite artificial. For example, simulated annealing is implemented as a descent algorithm, but does actually perform a sampling of the objective function, which is commonly seen as a population algorithm characteristic.

More rigourously, I think that every stochastic metaheuristic does try to avoid local optima. Stochastic processes are always here to do so[1].

Maybe the problem is the definition of local search. In my humble opinion, a local search is a method that search for a local optimum. This can be opposed to global search, where one want to find a global optimum.

You are right when you point out that this is related to ergodicity, as only an ergodic[2] algorithm may converge[3], and thus be able to reliably find a global optimum. Thus, yes, I will say that a true and rigorous optimization method is global if, and only if, it is at least quasi-ergodic[4]. A pure random search is the basic global optimization method, that a good metaheuristic should at least outperforms.

Here, it is the stochastic operators that manipulates the solutions that permits the global behaviour. This is not related to the encoding of the solutions/the neighbourhood structure, even if it is a really crucial part of the algorithm.

Thus, a "stochastic local search" may be defined as a local search seeking a global optimum, which is a paradoxical definition. I'd rather prefer that we keep the implementation and the mathematical bases separated, and thus talk of "stochastic search", or "stochastic metaheuristic".

Or else, one may want to use a paradoxical definition, as a matter of fun, which is also a good reason to do so :-)

Notes

[1] There may be probabilistic choices that are not related to such tasks, but they are not linked to the iterative aspects of the search algorithms, thus not being stochastics

[2] i.e. that can evaluate any solution

[3] i.e. that have a non-null probability of finding the global optimum in a finite time, or to say it differently, that can find the global optimum after a time that may tends towards infinity (for continuous problems, for discrete ones it is bounded by the size of the instance)

[4] i.e. that can reach any solution in a finite number of iterations

vendredi 7 novembre 2008

"Metaheuristic" or "Stochastic Local Search"?

During their excellent tutorials at META 2008, both Thomas and Dick talked about "stochastic local search" and seems to be rather uncomfortable with the "metaheuristic" term. They seems to reserve it for very high level well known algorithms.

I'm not sure that using the term "stochastic" along with "local" is a good idea. In all the algorithms, the use of probabilistic processes aims at avoiding local optima. Thus, stochastic algorithms are not "local search" anymore, but "global search". While I agree that it is a very good approach to start with local search techniques, I would say that when you introduce stochastic processes, then you enter the field of metaheuristics. On the other hand, the paradoxal use of "stochastic" along with "local" may be interesting from a marketing point of vue... but I like paradoxes.

Anyway, despite the fact that there would be a lot more to say about the problem of nomenclature in our field (who says "everything is evolutionary"?), this is not very important, I tink I will continue using "metaheuristics", until a common term establish itself in the litterature.

dimanche 10 septembre 2006

Confirmation of the biological foundations of particle swarm optimization

Particle swarm optimization (PSO) is based on biological (and theorical physic) work concerning self-organizaton in animals groups. Up to now, theory explained that animals must adjust their direction in order to set up a group. PSO use this concept to build a set of vectors that will exlpore the search space of an optimization problem, while converging on an optimum.

One key prediction of the theory is a transition between the recruitment of the individuals and the collective motion. This transition "from disorder to order" has been proved in situ by biologists, while studying locusts. They have filmed during 8 hours a group of 5 to 120 desert locusts, in a circular cockpit, and analysed the motions datas. The study shows that, at low density (under 25 individuals/m2), the animals moves independently. When reaching 25 to 60 locusts/m2, they form collective groups, which direction can vary abruptly. Beyond 75 locusts/m2, the coordinated marching is homogen.

While this should not change the use of PSO, which is a simplified model, it is always interesting to consider works talking about this transition between order and chaos, in self-organized systems. Indeed, this transition can also occurs in metaheuristics, and is perhaps interesting for further research, like in dynamical optimization.

From Disorder to Order in Marching Locusts, Buhl et al., Science, Vol. 312. no. 5778, pp. 1402 - 1406, 2 june 2006.