Environnement de programmation generique pour la recherche locale: Metalab

This dissertation is concerned with local search programming environments. We show, in this thesis, how programming environments may answer to the challenges of local search computing. We follow two goals on the theoritical level. We first give an outlook of the different computing paradigms on which can be engineered the local search programming tasks. For those used to procedurial langages, it should help to assimilate and compare the declarative, object-oriented or generic features of the different programming environments proposed in the literature. Second, we propose an original computing model of local search. This model, which profiles the design of our software, is based on generic programming. In practical, the thesis presents the software METALAB which has been developped during our work. Some case studies illustrate the different features of the langage. On one side, we show how to use METALAB to solve new problems on the basis of algorithms distributed by the programming environment. On the other side, we show how to use METALAB to express new metaheuristics.;Like the frameworks reported in the literature, METALAB relies on the paradigm of generic programming. In this model, the kernel of the software computes the skeleton of a local search according to some peripherical data structures to be given by the user. So as to keep the scope of the environment as general as possible, those periphericals are just described on a formal level independently of any application. The generic definition of a type, which concentrates on its interface, gives the set of services it must yield. For instance, METALAB defines an Attribute as a type with an operation, called scan(), that allows to measure a given property related to a movement. For a given problem, the user is commited to compute those functionalities according to the METALAB specifications.;Otherwise, METALAB distinguishes with the frameworks given in the literature as it does not rely on a set of patterns of well-known algorithms. As well as the representation of a problem has been decomposed by the computing of movements and solutions in the framework approach, our software also proposes to decompose the computing of the search process. This approach introduces three families of peripherical data structures: Representation types, Variable types and Control types. Representations are concerned with those structures related to the problem. Solutions and Movements, for instance, are forms of Representation. Variables are concerned with observations done on some Representation states encountered during the search process. Variables may be temporal or memorized. The cost of a Solution, of a Movement, a tabu list, or any Attribute of a Movement are examples of Variables. Finally, Control types are those ones that contribute to the search process. A Server, that enumerates some Movements according to the neighborhoods of the curent Solution, an Explorer, that selects one of those Movements to be applied are some examples of Control types. The syntax of METALAB, which is used to coordinate all the different pieces, allows to generate, modulate and experiment the final local search program.;As illustrated, the model of METALAB offers a great potential of expressivity, reusability and efficiency. First, let us point out that, along with the computing of simple Variables directly connected to some Representation types, it is possible to compose Variables together so as to express complex observations. This first feature gives the environment a great expressivity . Also, let us notice that our model minimizes the communication between Representation types and Control types which is done via Variables. It is the case in local search where the decision of the search path (cf. Control types) relies on some observations (cf. Variable types) made in turn on the Solutions and Movements (cf. Representation types). On a software engineering level, this second feature allows to warrant an optimal reusability of each piece of program. We finally argue that the decomposition into elementary pieces of code promotes the adaptation of metaheuristics as one can concentrate its work on the code truly concerned. Notice that the very polymorphic feature of METALAB, which allows to conceive efficient algorithms, has no cost at run-time. As METALAB only relies on static polymorphism, all the factors that shape the final algorithm are in fact taken into account at compile-time. Executables are then exclusively processed toward the run of the local search. (Abstract shortened by UMI.).;The main contribution of the thesis is to propose a new type of programming environment. The software we present, called METALAB, can be viewed as an extension to the framework approach.