A memetic algorithm for the delineation of local labour markets

Given a territory composed of basic geographical units, the delineation of local labour market areas (LLMAs) can be seen as a problem in which those units are grouped subject to multiple constraints. In previous research, standard genetic algorithms were not able to find valid solutions, and a specific evolutionary algorithm was developed. The inclusion of multiple ad hoc operators allowed the algorithm to find better solutions than those of a widely-used greedy method. However, the percentage of invalid solutions was still very high. In this paper we improve that evolutionary algorithm through the inclusion of (i) a reparation process, that allows every invalid individual to fulfil the constraints and contribute to the evolution, and (ii) a hillclimbing optimisation procedure for each generated individual by means of an appropriate reassignment of some of its constituent units. We compare the results of both techniques against the previous results and a greedy method.

Grouping genetic operators for the delineation of functional areas based on spatial interaction

The delineation of functional economic areas, or market areas, is a problem of high practical relevance, since the delineation of functional sets such as economic areas in the US, Travel-to-Work Areas in the United Kingdom, and their counterparts in other OECD countries are the basis of many statistical operations and policy making decisions at local level. This is a combinatorial optimisation problem defined as the partition of a given set of indivisible spatial units (covering a territory) into regions characterised by being (a) self-contained and (b) cohesive, in terms of spatial interaction data (flows, relationships). Usually, each region must reach a minimum size and self-containment level, and must be continuous. Although these optimisation problems have been typically solved through greedy methods, a recent strand of the literature in this field has been concerned with the use of evolutionary algorithms with ad hoc operators. Although these algorithms have proved to be successful in improving the results of some of the more widely applied official procedures, they are so time consuming that cannot be applied directly to solve real-world problems. In this paper we propose a new set of group-based mutation operators, featuring general operations over disjoint groups, tailored to ensure that all the constraints are respected during the operation to improve efficiency. A comparative analysis of our results with those from previous approaches shows that the proposed algorithm systematically improves them in terms of both quality and processing time, something of crucial relevance since it allows dealing with most large, real-world problems in reasonable time.

Multi-objective adaptive evolutionary strategy for tuning compilations

Tuning compilations is the process of adjusting the values of a compiler options to improve some features of the final application. In this paper, a strategy based on the use of a genetic algorithm and a multi-objective scheme is proposed to deal with this task. Unlike previous works, we try to take advantage of the knowledge of this domain to provide a problem-specific genetic operation that improves both the speed of convergence and the quality of the results. The evaluation of the strategy is carried out by means of a case of study aimed to improve the performance of the well-known web server Apache. Experimental results show that a 7.5% of overall improvement can be achieved. Furthermore, the adaptive approach has shown an ability to markedly speed-up the convergence of the original strategy.