Solving Large Location-Allocation problems by Clustering and Simulated Annealing

Globalization involves several facility location problems that need to be handled at large scale. Location Allocation (LA) is a combinatorial problem in which the distance among points in the data space matter. Precisely, taking advantage of the distance property of the domain we exploit the capability of clustering techniques to partition the data space in order to convert an initial large LA problem into several simpler LA problems. Particularly, our motivation problem involves a huge geographical area that can be partitioned under overall conditions. We present different types of clustering techniques and then we perform a cluster analysis over our dataset in order to partition it. After that, we solve the LA problem applying simulated annealing algorithm to the clustered and non-clustered data in order to work out how profitable is the clustering and which of the presented methods is the most suitable

Neural networks complemented with genetic algorithms and fuzzy systems for predicting nitrogenous effluent variables in wastewater treatment plants

This work focuses on the prediction of the two main nitrogenous variables that describe the water quality at the effluent of a Wastewater Treatment Plant. We have developed two kind of Neural Networks architectures based on considering only one output or, in the other hand, the usual five effluent variables that define the water quality: suspended solids, biochemical organic matter, chemical organic matter, total nitrogen and total Kjedhal nitrogen. Two learning techniques based on a classical adaptative gradient and a Kalman filter have been implemented. In order to try to improve generalization and performance we have selected variables by means genetic algorithms and fuzzy systems. The training, testing and validation sets show that the final networks are able to learn enough well the simulated available data specially for the total nitrogen

Simulated Annealing, High-Order Statistics and Mutual Information for Separation of Sources

In this article, the fusion of a stochastic metaheuristic as Simulated Annealing (SA) with classical criteria for convergence of Blind Separation of Sources (BSS), is shown. Although the topic of BSS, by means of various techniques, including ICA, PCA, and neural networks, has been amply discussed in the literature, to date the possibility of using simulated annealing algorithms has not been seriously explored. From experimental results, this paper demonstrates the possible benefits offered by SA in combination with high order statistical and mutual information criteria for BSS, such as robustness against local minima and a high degree of flexibility in the energy function.

Can genetic algorithms explain experimental anomalies? An application to common property resources

It is common to find in experimental data persistent oscillations in the aggregate outcomes and high levels of heterogeneity in individual behavior. Furthermore, it is not unusual to find significant deviations from aggregate Nash equilibrium predictions. In this paper, we employ an evolutionary model with boundedly rational agents to explain these findings. We use data from common property resource experiments (Casari and Plott, 2003). Instead of positing individual-specific utility functions, we model decision makers as selfish and identical. Agent interaction is simulated using an individual learning genetic algorithm, where agents have constraints in their working memory, a limited ability to maximize, and experiment with new strategies. We show that the model replicates most of the patterns that can be found in common property resource experiments.

A Model-to-model analysis of the repeated Prisoners' Dilemma: genetic algorithms vs. evolutionary dynamics

We study the properties of the well known Replicator Dynamics when applied to a finitely repeated version of the Prisoners' Dilemma game. We characterize the behavior of such dynamics under strongly simplifying assumptions (i.e. only 3 strategies are available) and show that the basin of attraction of defection shrinks as the number of repetitions increases. After discussing the difficulties involved in trying to relax the 'strongly simplifying assumptions' above, we approach the same model by means of simulations based on genetic algorithms. The resulting simulations describe a behavior of the system very close to the one predicted by the replicator dynamics without imposing any of the assumptions of the analytical model. Our main conclusion is that analytical and computational models are good complements for research in social sciences. Indeed, while on the one hand computational models are extremely useful to extend the scope of the analysis to complex scenar

Clustering algorithms for anti-money laundering using graph theory and social network analysis

HEMOLIA (a project under European community’s 7th framework programme) is a new generation Anti-Money Laundering (AML) intelligent multi-agent alert and investigation system which in addition to the traditional financial data makes extensive use of modern society’s huge telecom data source, thereby opening up a new dimension of capabilities to all Money Laundering fighters (FIUs, LEAs) and Financial Institutes (Banks, Insurance Companies, etc.). This Master-Thesis project is done at AIA, one of the partners for the HEMOLIA project in Barcelona. The objective of this thesis is to find the clusters in a network drawn by using the financial data. An extensive literature survey has been carried out and several standard algorithms related to networks have been studied and implemented. The clustering problem is a NP-hard problem and several algorithms like K-Means and Hierarchical clustering are being implemented for studying several problems relating to sociology, evolution, anthropology etc. However, these algorithms have certain drawbacks which make them very difficult to implement. The thesis suggests (a) a possible improvement to the K-Means algorithm, (b) a novel approach to the clustering problem using the Genetic Algorithms and (c) a new algorithm for finding the cluster of a node using the Genetic Algorithm.

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A is a manufacturing company dedicated to produce prefabricatedconcrete parts to several industries as rail transportation andagricultural industries.Recently, PRECON signed a contract with RENFE,the Spanish Nnational Rail Transportation Company to manufacturepre-stressed concrete sleepers for siding of the new railways of the highspeed train AVE. The scheduling problem associated with the manufacturingprocess of the sleepers is very complex since it involves severalconstraints and objectives. The constraints are related with productioncapacity, the quantity of available moulds, satisfying demand and otheroperational constraints. The two main objectives are related withmaximizing the usage of the manufacturing resources and minimizing themoulds movements. We developed a deterministic crowding genetic algorithmfor this multiobjective problem. The algorithm has proved to be a powerfuland flexible tool to solve the large-scale instance of this complex realscheduling problem.

Unconstrained optimization with MINTOOLKIT for GNU octave

The paper documents MINTOOLKIT for GNU Octave. MINTOOLKIT provides functions for minimization and numeric differentiation. The main algorithms are BFGS, LBFGS, and simulated annealing. Examples are given.

Hard instances of algorithms and proof systems

"Vegeu el resum a l'inici del document del fitxer adjunt."

Population genetic structure and demography analysis in palinurus elephas populations from atlantic and mediterranean waters

Report for the scientific sojourn at the University of Reading, United Kingdom, from January until May 2008. The main objectives have been firstly to infer population structure and parameters in demographic models using a total of 13 microsatellite loci for genotyping approximately 30 individuals per population in 10 Palinurus elephas populations both from Mediterranean and Atlantic waters. Secondly, developing statistical methods to identify discrepant loci, possibly under selection and implement those methods using the R software environment. It is important to consider that the calculation of the probability distribution of the demographic and mutational parameters for a full genetic data set is numerically difficult for complex demographic history (Stephens 2003). The Approximate Bayesian Computation (ABC), based on summary statistics to infer posterior distributions of variable parameters without explicit likelihood calculations, can surmount this difficulty. This would allow to gather information on different demographic prior values (i.e. effective population sizes, migration rate, microsatellite mutation rate, mutational processes) and assay the sensitivity of inferences to demographic priors by assuming different priors.

Algorithms and cryptographic protocols using elliptic curves

En els darrers anys, la criptografia amb corbes el.líptiques ha adquirit una importància creixent, fins a arribar a formar part en la actualitat de diferents estàndards industrials. Tot i que s'han dissenyat variants amb corbes el.líptiques de criptosistemes clàssics, com el RSA, el seu màxim interès rau en la seva aplicació en criptosistemes basats en el Problema del Logaritme Discret, com els de tipus ElGamal. En aquest cas, els criptosistemes el.líptics garanteixen la mateixa seguretat que els construïts sobre el grup multiplicatiu d'un cos finit primer, però amb longituds de clau molt menor. Mostrarem, doncs, les bones propietats d'aquests criptosistemes, així com els requeriments bàsics per a que una corba sigui criptogràficament útil, estretament relacionat amb la seva cardinalitat. Revisarem alguns mètodes que permetin descartar corbes no criptogràficament útils, així com altres que permetin obtenir corbes bones a partir d'una de donada. Finalment, descriurem algunes aplicacions, com són el seu ús en Targes Intel.ligents i sistemes RFID, per concloure amb alguns avenços recents en aquest camp.

Genetic diversity and species richness patterns in Baetidae (Ephemeroptera) in the Montseny Mountain range (North-East Iberian Peninsula)

This study aimed to describe patterns of diversity of Baetidae (Ephemeroptera) at the ommunity and population levels within the Montseny Mountain range (North-East Iberian Peninsula). We studied both the distribution of 4 species of baetids in 20 sites among three catchments along the altitudinal gradient (350-1700 masl); and the genetic diversity of the mtDNA cytochrome c oxidase subunit I (cox1) gene of the two common species Baetis alpinus and Baetis rhodani. We found a gradual replacement of the dominant species along the altitudinal gradient. Baetis alpinus inhabited sites at high-altitudes, and this species was replaced by B. rhodani when the altitude decreased. Baetis melanonyx and Alainites muticus attained low abundance at all river sections, and no clear altitudinal trend appeared. Our hypothesis at the population level was that genetic structuring is associated with geographic distance and limited by drainage boundaries among the three studied catchments because of the short-time dispersion of adults. Unexpectedly, analyses of molecular variance (AMOVA) and isolation-bydistance (IBD) showed genetic diversity was unstructured by distance for both species, which may be explained by the relatively short spatial scale studied and small topographic barriers among the three catchments. The Generalized Mixed Yule-Coalescent (GMYC) model showed that B. rhodani had two differentiated genetic lineages that co-occurred in all sites. Overall, diversity of baetids was structured at the community level along the altitudinal gradient, whereas it was unstructured at the population level within the Montseny Mountain range.

Genetic diversity and species richness patterns in Baetidae (Ephemeroptera) in the Montseny Mountain range (North-East Iberian Peninsula)

This study aimed to describe patterns of diversity of Baetidae (Ephemeroptera) at the ommunity and population levels within the Montseny Mountain range (North-East Iberian Peninsula). We studied both the distribution of 4 species of baetids in 20 sites among three catchments along the altitudinal gradient (350-1700 masl); and the genetic diversity of the mtDNA cytochrome c oxidase subunit I (cox1) gene of the two common species Baetis alpinus and Baetis rhodani. We found a gradual replacement of the dominant species along the altitudinal gradient. Baetis alpinus inhabited sites at high-altitudes, and this species was replaced by B. rhodani when the altitude decreased. Baetis melanonyx and Alainites muticus attained low abundance at all river sections, and no clear altitudinal trend appeared. Our hypothesis at the population level was that genetic structuring is associated with geographic distance and limited by drainage boundaries among the three studied catchments because of the short-time dispersion of adults. Unexpectedly, analyses of molecular variance (AMOVA) and isolation-bydistance (IBD) showed genetic diversity was unstructured by distance for both species, which may be explained by the relatively short spatial scale studied and small topographic barriers among the three catchments. The Generalized Mixed Yule-Coalescent (GMYC) model showed that B. rhodani had two differentiated genetic lineages that co-occurred in all sites. Overall, diversity of baetids was structured at the community level along the altitudinal gradient, whereas it was unstructured at the population level within the Montseny Mountain range.

Decision Support Methods for Global Optomization

Immobile location-allocation (LA) problems is a type of LA problem that consists in determining the service each facility should offer in order to optimize some criterion (like the global demand), given the positions of the facilities and the customers. Due to the complexity of the problem, i.e. it is a combinatorial problem (where is the number of possible services and the number of facilities) with a non-convex search space with several sub-optimums, traditional methods cannot be applied directly to optimize this problem. Thus we proposed the use of clustering analysis to convert the initial problem into several smaller sub-problems. By this way, we presented and analyzed the suitability of some clustering methods to partition the commented LA problem. Then we explored the use of some metaheuristic techniques such as genetic algorithms, simulated annealing or cuckoo search in order to solve the sub-problems after the clustering analysis