Recent work in metaheuristic algorithms has shown that solution quality may be improved by composing algorithms with orthogonal characteristics. In this thesis, I study multi-population particle swarm optimization (MPSO) and genetic algorithm (GA) hybrid strategies. I begin by investigating the behaviour of MPSO with crossover, mutation, swapping, and all three, and show that the latter is able to solve the most difficult benchmark functions. Because GAs converge slowly and MPSO provides a large degree of parallelism, I also develop several parallel hybrid algorithms. A composite approach executes PSO and GAs simultaneously in different swarms, and shows advantages when arranged in a star topology, particularly with a central GA. A static scheme executes in series, with a GA performing the exploration followed by MPSO for exploitation. Finally, the last approach dynamically alternates between algorithms. Hybrid algorithms are well-suited for parallelization, but exhibit tradeoffs between performance and solution quality.

In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. (authors' abstract)

A portfolio optimisation problem involves allocation of investment to a number of different assets to maximize return and minimize risk in a given investment period. The selected assets in a portfolio not only collectively contribute to its return but also interactively define its risk as usually measured by a portfolio variance. This presents a combinatorial optimisation problem that involves selection of both a number of assets as well as its quantity (weight or proportion or units). The problem is extremely complex due to a large number of selectable assets. Furthermore, the problem is dynamic and stochastic in nature with a number of constraints presenting a complex model which is difficult to solve for exact solution. In the last decade research publications have reported the applications of metaheuristic-based optimisation methods with some success., This paper presents a review of these reported models, optimisation problem formulations and metaheuristic approaches for portfolio optimisation.

Combinatorial optimisation problems (COPs) have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms, classical local search methods, metaheuristics, and hyperheuristics. This thesis proposes a refined generic and parametrised infeasible local search (GPILS) algorithm for solving COPs and customises it to solve the traveling salesman problem (TSP), for illustration purposes. In addition, a rule-based heuristic is proposed to initialise infeasible local search, referred to as the parameterised infeasible heuristic (PIH), which allows the analyst to have some control over the features of the infeasible solution he/she might want to start the infeasible search with. A recursive infeasible neighbourhood search (RINS) as well as a generic patching procedure to search the infeasible space are also proposed. These procedures are designed in a generic manner, so they can be adapted to any choice of parameters of the GPILS, where the set of parameters, in fact for simplicity, refers to set of parameters, components, criteria and rules. Furthermore, a hyperheuristic framework is proposed for optimizing the parameters of GPILS referred to as HH-GPILS. Experiments have been run for both sequential (i.e. simulated annealing, variable neighbourhood search, and tabu search) and parallel hyperheuristics (i.e., genetic algorithms / GAs) to empirically assess the performance of the proposed HH-GPILS in solving TSP using instances from the TSPLIB. Empirical results suggest that HH-GPILS delivers an outstanding performance. Finally, an offline learning mechanism is proposed as a seeding technique to improve the performance and speed of the proposed parallel HH-GPILS. The proposed offline learning mechanism makes use of a knowledge-base to keep track of the best performing chromosomes and their scores. Empirical results suggest that this learning mechanism is a promising technique to initialise the GA's population.

<p>The ability to tackle NP-hard problems has been greatly extended by the introduction of Metaheuristics (see Blum & Roli (2003)) for a summary of most Metaheuristics, general problem-independent optimisation algorithms extending the hill-climbing local search approach to escape local minima. One of these algorithms is Iterated Local Search (ILS) (Lourenco et al., 2002; Stützle, 1999a, p. 25ff), a recent easy to implement but powerful algorithm with results comparable or superior to other state-of-the-art methods for many combinatorial optimisation problems, among them the Traveling Salesman (TSP) and Quadratic Assignment Problem (QAP). ILS iteratively samples local minima by modifying the current local minimum and restarting</p><p>a local search porcedure on this modified solution. This thesis will show how ILS can be implemented for MSA. After that, ILS will be evaluated and compared to other MSA algorithms by BAliBASE (Thomson et al., 1999), a set of manually refined alignments used in most recent publications of algorithms and in at least two MSA algorithm surveys. The runtime-behaviour will be evaluated using runtime-distributions.</p><p>The quality of alignments produced by ILS is at least as good as the best algorithms available and significantly superiour to previously published Metaheuristics for MSA, Tabu Search and Genetic Algorithm (SAGA). On the average, ILS performed best in five out of eight test cases, second for one test set and third for the remaining two. A drawback of all iterative methods for MSA is the long runtime needed to produce good alignments. ILS needs considerably less runtime than Tabu Search and SAGA, but can not compete with progressive or consistency based methods, e. g. ClustalW or T-COFFEE.</p>

Optimization problems are common throughout science, engineering and commerce. The desire to continually improve solutions and resolve larger, complex problems has given prominence to this field of research for several decades and has led to the development of a range of optimization algorithms for different class of problems. The Estimation of Distribution Algorithms (EDAs) are a relatively recent class of metaheuristic optimization algorithms based on using probabilistic modeling techniques to control the search process. Within the general EDA framework, a number of different probabilistic models have been previously proposed for both discrete and continuous optimization problems. This thesis focuses on GMMEDAs; continuous EDAs based on the Gaussian Mixture Models (GMM) with parameter estimation performed using the Expectation Maximization (EM) algorithm. To date, this type of model has only received limited attention in the literature. There are few previous experimental studies of the algorithms. Furthermore, a number of implementation details of Continuous Iterated Density Estimation Algorithm based on Gaussian Mixture Model have not been previously documented. This thesis intends to provide a clear description of the GMMEDAs, discuss the implementation decisions and details and provides experimental study to evaluate the performance of the algorithms. The effectiveness of the GMMEDAs with varying model complexity (structure of covariance matrices and number of components) was tested against five benchmark functions (Sphere, Rastrigin, Griewank, Ackley and Rosenbrock) with varying dimensionality (2−, 10− and 30−D). The effect of the selection pressure parameters is also studied in this experiment. The results of the 2D experiments show that a variant of the GMMEDA with moderate complexity (Diagonal GMMEDA) was able to optimize both unimodal and multimodal functions. Further, experimental analysis of the 10 and 30D functions optimized results indicates that the simpler variant of the GMMEDA (Spherical GMMEDA) was most effective of all three variants of the algorithm. However, a greater consistency in the results of these functions is achieved when the most complex variant of the algorithm (Full GMMEDA) is used. The comparison of the results for four artificial test functions - Sphere, Griewank, Ackley and Rosenbrock - showed that the GMMEDA variants optimized most of complex functions better than existing continuous EDAs. This was achieved because of the ability of the GMM components to model the functions effectively. The analysis of the results evaluated by variants of the GMMEDA showed that number of the components and the selection pressure does affect the optimum value of artificial test function. The convergence of the GMMEDA variants to the respective functions best local optimum has been caused more by the complexity in the GMM components. The complexity of GMMEDA because of the number of components increases as the complexity owing to the structure of the covariance matrices increase. However, while finding optimum value of complex functions the increased complexity in GMMEDA due to complex covariance structure overrides the complexity due to increase in number of components. Additionally, the affect on the convergence due to the number of components decreases for most functions when the selection pressure increased. These affects have been noticed in the results in the form of stability of the results related to the functions. Other factors that affect the convergence of the model to the local optima are the initialization of the GMM parameters, the number of the EM components, and the reset condition. The initialization of the GMM components, though not visible graphically in the 10D optimization has shown: for different initialization of the GMM parameters in 2D, the optimum value of the functions is affected. The initialization of the population in the Evolutionary Algorithms has shown to affect the convergence of the algorithm to the functions global optimum. The observation of similar affects due to initialization of GMM parameters on the optimization of the 2D functions indicates that the convergence of the GMM in the 10D could be affected, which in turn, could affect the optimum value of respective functions. The estimated values related to the covariance and mean over the EM iteration in the 2D indicated that some functions needed a greater number of EM iterations while finding their optimum value. This indicates that lesser number of EM iterations could affect the fitting of the components to the selected population in the 10D and the fitting can affect the effective modeling of functions with varying complexity. Finally, the reset condition has shown as resetting the covariance and the best fitness value of individual in each generation in 2D. This condition is certain to affect the convergence of the GMMEDA variants to the respective functions best local optimum. The rate at which the reset condition was invoked could certainly have caused the GMM components covariance values to reset to their initials values and thus the model fitting the percentage of the selected population could have been affected. Considering all the affects caused by the different factors, the results indicates that a smaller number of the components and percentage of the selected population with a simpler S-GMMEDA modeled most functions with a varying complexity.

The ability to tackle NP-hard problems has been greatly extended by the introduction of Metaheuristics (see Blum &amp; Roli (2003)) for a summary of most Metaheuristics, general problem-independent optimisation algorithms extending the hill-climbing local search approach to escape local minima. One of these algorithms is Iterated Local Search (ILS) (Lourenco et al., 2002; Stützle, 1999a, p. 25ff), a recent easy to implement but powerful algorithm with results comparable or superior to other state-of-the-art methods for many combinatorial optimisation problems, among them the Traveling Salesman (TSP) and Quadratic Assignment Problem (QAP). ILS iteratively samples local minima by modifying the current local minimum and restarting a local search porcedure on this modified solution. This thesis will show how ILS can be implemented for MSA. After that, ILS will be evaluated and compared to other MSA algorithms by BAliBASE (Thomson et al., 1999), a set of manually refined alignments used in most recent publications of algorithms and in at least two MSA algorithm surveys. The runtime-behaviour will be evaluated using runtime-distributions. The quality of alignments produced by ILS is at least as good as the best algorithms available and significantly superiour to previously published Metaheuristics for MSA, Tabu Search and Genetic Algorithm (SAGA). On the average, ILS performed best in five out of eight test cases, second for one test set and third for the remaining two. A drawback of all iterative methods for MSA is the long runtime needed to produce good alignments. ILS needs considerably less runtime than Tabu Search and SAGA, but can not compete with progressive or consistency based methods, e. g. ClustalW or T-COFFEE.

Actuellement, les équipements employés dans les milieux industriels sont de plus en plus complexes. Ils exigent une maintenance accrue afin de garantir un niveau de service optimal en termes de fiabilité et de disponibilité. Par ailleurs, souvent cette garantie d'optimalité a un coût très élevé, ce qui est contraignant. Face à ces exigences la gestion de la maintenance des équipements est désormais un enjeu de taille : rechercher une politique de maintenance réalisant un compromis acceptable entre la disponibilité et les coûts associés à l'entretien du système. Les travaux de cette thèse partent par ailleurs du constat que dans plusieurs applications de l'industrie, le besoin de stratégies de maintenance assurant à la fois une sécurité optimale et une rentabilité maximale demeure de plus en plus croissant conduisant à se référer non seulement à l'expérience des experts, mais aussi aux résultats numériques obtenus via la résolution des problèmes d'optimisation. La résolution de cette problématique nécessite au préalable la modélisation de l'évolution des comportements des états des composants constituant le système, i.e, connaître les mécanismes de dégradation des composants. Disposant d'un tel modèle, une stratégie de maintenance est appliquée au système. Néanmoins, l'élaboration d'une telle stratégie réalisant un compromis entre toutes ces exigences représente un verrou scientifique et technique majeur. Dans ce contexte, l'optimisation de la maintenance s'impose pour atteindre les objectifs prescrits avec des coûts optimaux. Dans les applications industrielles réelles, les problèmes d'optimisation sont souvent de grande dimension faisant intervenir plusieurs paramètres. Par conséquent, les métaheuristiques s’avèrent une approche intéressante dans la mesure où d'une part, elles sacrifient la complétude de la résolution au profit de l'efficacité et du temps de calcul et d'autre part elles s'appliquent à un très large panel de problèmes.Dans son objectif de proposer une démarche de résolution d'un problème d'optimisation de la maintenance préventive, cette thèse fournit une méthodologie de résolution du problème d'optimisation des politiques de maintenance préventive systématique appliquée dans le domaine ferroviaire à la prévention des ruptures de rails. Le raisonnement de cette méthodologie s'organise autour de trois étapes principales : 1. Modélisation de l'évolution des comportements des états des composants constituant le système, i.e, connaître les mécanismes de dégradation des composants et formalisation des opérations de maintenance. 2. Formalisation d'un modèle d'évaluation de politiques de maintenance tenant compte aussi bien du facteur sûreté de fonctionnement du système que du facteur économique conséquent aux procédures de gestion de la maintenance (coûts de réparation, de diagnostic, d'indisponibilité). 3. Optimisation des paramètres de configuration des politiques de maintenance préventive systématique afin d'optimiser un ou plusieurs critères. Ces critères sont définis sur la base du modèle d'évaluation des politiques de maintenance proposé dans l'étape précédente / At present, equipments used on the industrial circles are more and more complex. They require a maintenance increased to guarantee a level of optimal service in terms of reliability and availability. Besides, often this guarantee of optimalité has a very high cost, what is binding. In the face of these requirements the management of the maintenance of equipments is from now on a stake in size: look for a politics of maintenance realizing an acceptable compromise between the availability and the costs associated to the maintenance of the system. The works of this thesis leave besides the report that in several applications of the industry, the need for strategies of maintenance assuring(insuring) at the same time an optimal safety and a maximal profitability lives furthermore there

Manufactural activity is the basis of every sound economy. The risk for today's industrial establishments in our let us say european conditions is to hold competitiveness in the terms of global economy. This diploma thesis is focusing on solving problems of manufacturing scheduling with the view of theory and practice. It is impeach of real-life production. Scheduling belongs to hard combinatorial problems and therefore are usually solved by various heuristic or metaheuristic methods. For application of mentioned metaheuristic methods is important to use suitable choice of representative data.

Cette thèse s'inscrit dans le cadre d'un projet pluridisciplinaire, le projet DRAMA, qui consiste à générer des scènes virtuelles 3D à partir des descriptions contenues dans les textes théâtraux. L'un des objectifs de ce projet consiste à simplifier au maximum la tâche des utilisateurs finaux en leur offrant un outil simple, rapide, et efficace. Ainsi, la technique adoptée dans cette étude est axée sur la modélisation déclarative d'environnements virtuels qui s'appuie sur trois phases (description, génération et prise de connaissances). La phase de description permet au concepteur de décrire l'environnement à partir d'un ensemble de propriétés, interprétées en un ensemble de contraintes destinées à un système de génération qui produit un ou plusieurs environnements virtuels solutions.Dans le cadre de ce projet DRAMA, des nouvelles méthodes de balisage ont été proposées afin de détecter les éléments essentiels pour la création d'une pièce théâtrale, notamment les informations sur les placements d'objets. Par ailleurs, les utilisateurs peuvent, aussi, lancer des requêtes au niveau du texte à partir de ces balises. Les propriétés sur les placements seront traduites en contraintes spatiales grâce aux données initialement stockées dans une base de connaissance qui utilise le langage XML. Une technique adoptant la méthode des métaheuristiques est ensuite utilisée pour la résolution des contraintes de placements obtenues précédemment. La gestion des propriétés physiques des objets (collision, gravité, friction) a été aussi gérée à partir d'un moteur physique. À la fin, les scènes solutions finales seront proposées à l'utilisateur, en utilisant un moteur de rendu 3D. / This thesis is part of a multidisciplinary project, the DRAMA project, which attempts to generate 3D virtual scenes from the descriptions which are obtained from theatrical text. This project aims to simplify, as soon as possible, the tasks of the end-users by providing simple, fast, and effective tools. Thus, the technique used in this study is focused on the declarative modeling of virtual environments that is based on three phases (description, generation and management of knowledge). The description phase allows the designer to describe the environment from a set of properties, interpreted as a set of constraints for a generation system which produces one or several virtual environments solutions. This project, new tagging methods have been proposed to detect essential for the creation of scene, including information on the placement of objects. In addition, users can also run queries in the text from these tags. Placement properties are translated into spatial constraints with the data originally stored in a knowledge base that uses XML. A technique adopting the method of metaheuristics is then used for solving constraints. The object physical properties (collision, gravity, friction) were also managed from a physics engine. At the end, the finals scenes solutions were be proposed to the user, using a 3D rendering engine.