Enabling and Measuring Complexity in Evolving Designs using Generative Representations for Artificial Architecture

As the complexity of evolutionary design problems grow, so too must the quality of solutions scale to that complexity. In this research, we develop a genetic programming system with individuals encoded as tree-based generative representations to address scalability. This system is capable of multi-objective evaluation using a ranked sum scoring strategy. We examine Hornby's features and measures of modularity, reuse and hierarchy in evolutionary design problems. Experiments are carried out, using the system to generate three-dimensional forms, and analyses of feature characteristics such as modularity, reuse and hierarchy were performed. This work expands on that of Hornby's, by examining a new and more difficult problem domain. The results from these experiments show that individuals encoded with those three features performed best overall. It is also seen, that the measures of complexity conform to the results of Hornby. Moving forward with only this best performing encoding, the system was applied to the generation of three-dimensional external building architecture. One objective considered was passive solar performance, in which the system was challenged with generating forms that optimize exposure to the Sun. The results from these and other experiments satisfied the requirements. The system was shown to scale well to the architectural problems studied.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Choix d'un associateur 2-D pour le balayage multiple et optimisation de l'estimation des pistes

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

La résolution du problème de formation de cellules dans un contexte multicritère

Les techniques de groupement technologique sont aujourd’hui utilisées dans de nombreux ateliers de fabrication; elles consistent à décomposer les systèmes industriels en sous-systèmes ou cellules constitués de pièces et de machines. Trouver le groupement technologique le plus efficace est formulé en recherche opérationnelle comme un problème de formation de cellules. La résolution de ce problème permet de tirer plusieurs avantages tels que la réduction des stocks et la simplification de la programmation. Plusieurs critères peuvent être définis au niveau des contraintes du problème tel que le flot intercellulaire,l’équilibrage de charges intracellulaires, les coûts de sous-traitance, les coûts de duplication des machines, etc. Le problème de formation de cellules est un problème d'optimisation NP-difficile. Par conséquent les méthodes exactes ne peuvent être utilisées pour résoudre des problèmes de grande dimension dans un délai raisonnable. Par contre des méthodes heuristiques peuvent générer des solutions de qualité inférieure, mais dans un temps d’exécution raisonnable. Dans ce mémoire, nous considérons ce problème dans un contexte bi-objectif spécifié en termes d’un facteur d’autonomie et de l’équilibre de charge entre les cellules. Nous présentons trois types de méthodes métaheuristiques pour sa résolution et nous comparons numériquement ces métaheuristiques. De plus, pour des problèmes de petite dimension qui peuvent être résolus de façon exacte avec CPLEX, nous vérifions que ces métaheuristiques génèrent des solutions optimales.

Contribution à l’élaboration d’un guide alimentaire béninois : approche par la programmation linéaire et validation sur le terrain

Contexte: Le Bénin est atteint par le double fardeau nutritionnel : dans le même pays, et parfois dans le même ménage, il y a des personnes malnutries et d’autres aux prises avec des maladies chroniques. Ces conditions, au moins pour partie, peuvent être prévenues si la population est sensibilisée à de bonnes habitudes alimentaires. Pour ce faire, les professionnels de la santé ont besoin d’outils comme un guide alimentaire (GA) pour faciliter l’apprentissage de bonnes pratiques alimentaires. Ce dernier nécessite plusieurs étapes à son élaboration, dont la définition des groupes alimentaires, la présentation visuelle et la quantification des portions d'aliments. Objectif : Ce travail a eu pour but de proposer et d’homologuer des portions quotidiennes d’aliments dans chaque groupe alimentaire pour différents groupes d’âge de Béninois. Méthode : Elle consiste à : 1) Caractériser la consommation alimentaire locale; 2) Optimiser le profil moyen de consommation alimentaire quotidienne à l’aide de la programmation linéaire (PL); 3) Traduire les résultats en termes de nombre et taille de portions d’aliments de chaque groupe à consommer quotidiennement; 4) Illustrer les recommandations au moyen d’exemples de menus journaliers; 5) Homologuer le prototype du GA avec des experts béninois. La PL a permis de déterminer les choix d’aliments et quantités optimales à recommander à partir des enquêtes transversales récentes et des recommandations nutritionnelles de l’OMS. Résultats : Les quantités et portions d'aliments recommandées à la consommation ont été déterminées. Les résultats ont été partagés avec les personnes-ressources en nutrition au Bénin. Le premier prototype du GA a été développé pour restitution subséquente aux autorités du Bénin.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Operational Cost Reduction in WDM Networks using Lighttours

Wavelength division multiplexing (WDM) networks have been adopted as a near-future solution for the broadband Internet. In previous work we proposed a new architecture, named enhanced grooming (G+), that extends the capabilities of traditional optical routes (lightpaths). In this paper, we compare the operational expenditures incurred by routing a set of demands using lightpaths with that of lighttours. The comparison is done by solving an integer linear programming (ILP) problem based on a path formulation. Results show that, under the assumption of single-hop routing, almost 15% of the operational cost can be reduced with our architecture. In multi-hop routing the operation cost is reduced in 7.1% and at the same time the ratio of operational cost to number of optical-electro-optical conversions is reduced for our architecture. This means that ISPs could provide the same satisfaction in terms of delay to the end-user with a lower investment in the network architecture

Mapping sub-flows to p2mp LSPs

In previous work we proposed a multi-objective traffic engineering scheme (MHDB-S model) using different distribution trees to multicast several flows. In this paper, we propose a heuristic algorithm to create multiple point-to-multipoint (p2mp) LSPs based on the optimum sub-flow values obtained with our MHDB-S model. Moreover, a general problem for supporting multicasting in MPLS networks is the lack of labels. To reduce the number of labels used, a label space reduction algorithm solution is also considered

Aplicació d'algoritmes genètics en l'optimització dels processos de fabricació del paper

La creciente preocupación y concienciación de la sociedad respecto el medio ambiente, y en consecuencia la legislación y regulaciones generadas inducen a la modificación de los procesos productivos existentes en la industria química. Las configuraciones iniciales deben modificarse para conseguir una mayor integración de procesos. Para este fin se han creado y desarrollado diferentes metodologías que deben facilitar la tarea a los responsables del rediseño. El desarrollo de una metodología y herramientas complementarias es el principal objetivo de la investigación aquí presentada, especialmente centrada en el desarrollo y la aplicación de una metodología de optimización de procesos. Esta metodología de optimización se aplica sobre configuraciones de proceso existentes y pretende encontrar nuevas configuraciones viables según los objetivos de optimización fijados. La metodología tiene dos partes diferenciadas: la primera se basa en un simulador de procesos comercial y la segunda es la técnica de optimización propiamente dicha. La metodología se inicia con la elaboración de una simulación convenientemente validada que reproduzca el proceso existente, en este caso una papelera no integrada que produce papel estucado de calidad, para impresión. A continuación la técnica de optimización realiza una búsqueda dentro del dominio de los posibles resultados, en busca de los mejores resultados que satisfazcan plenamente los objetivos planteados. Dicha técnica de optimización está basada en los algoritmos genéticos como herramienta de búsqueda, junto a un subprograma basado en técnicas de programación matemática para el cálculo de resultados. Un número reducido de resultados son finalmente escogidos y utilizados para modificar la simulación existente fijando la redistribución de los flujos del proceso. Los resultados de la simulación del proceso determinan en último caso la viabilidad técnica de cada reconfiguración planteada. En el proceso de optimización, los objetivos están definidos en una función objetivo dentro de la técnica de optimización. Dicha función rige la búsqueda de resultados. La función objetivo puede ser individual o una combinación de objetivos. En el presente caso, la función persigue una minimización del consumo de agua y una minimización de la pérdida de materia prima. La optimización se realiza bajo restricciones para alcanzar este objetivo combinado en forma de una solución de compromiso. Producto de la aplicación de esta metodología se han obtenido resultados interesantes que significan una mejora del cierre de circuitos y un ahorro de materia prima, sin comprometer al mismo tiempo la operabilidad del proceso producto ni la calidad del papel.

Potential cost and environmental impact of feeding high-oil corn to poultry in Brazil

The objective of the study was to evaluate the cost and environmental impact of replacing traditional corn, which is the main ingredient in poultry diets, with a high-oil corn (HOC) variety. Using linear programming, diets were formulated with either traditional corn or HOC. The results indicate that HOC-based diets cost up to $11.38/tonne less than traditional corn-based diets. Using HOC rather than traditional corn in diets has the potential to reduce the annual nitrogen excreted to the environment from broilers and broiler breeders in Brazil by 6.44 Mtonnes. In addition, there is the potential to reduce P excretion by 4.52 Mtonnes/yr, because the need to supplement diets with inorganic P sources, such as dicalcium phosphate, is much lower with HOC-based diets. We estimate that 28.5 Mtonnes of dicalcium phosphate can be saved annually using HOC in Brazilian poultry diets. The literature suggests that replacing traditional corn with HOC does not affect bird metabolism, while positive impacts on growth rate have been recorded. Therefore, substituting traditional corn with HOC has cost and environmental benefits for the Brazilian poultry industry without compromising productivity.

A robust controller design method for feedback substitution schemes using genetic algorithms

Controllers for feedback substitution schemes demonstrate a trade-off between noise power gain and normalized response time. Using as an example the design of a controller for a radiometric transduction process subjected to arbitrary noise power gain and robustness constraints, a Pareto-front of optimal controller solutions fulfilling a range of time-domain design objectives can be derived. In this work, we consider designs using a loop shaping design procedure (LSDP). The approach uses linear matrix inequalities to specify a range of objectives and a genetic algorithm (GA) to perform a multi-objective optimization for the controller weights (MOGA). A clonal selection algorithm is used to further provide a directed search of the GA towards the Pareto front. We demonstrate that with the proposed methodology, it is possible to design higher order controllers with superior performance in terms of response time, noise power gain and robustness.

Does increased hydrochemical model complexity decrease robustness?

The aim of this study was, within a sensitivity analysis framework, to determine if additional model complexity gives a better capability to model the hydrology and nitrogen dynamics of a small Mediterranean forested catchment or if the additional parameters cause over-fitting. Three nitrogen-models of varying hydrological complexity were considered. For each model, general sensitivity analysis (GSA) and Generalized Likelihood Uncertainty Estimation (GLUE) were applied, each based on 100,000 Monte Carlo simulations. The results highlighted the most complex structure as the most appropriate, providing the best representation of the non-linear patterns observed in the flow and streamwater nitrate concentrations between 1999 and 2002. Its 5% and 95% GLUE bounds, obtained considering a multi-objective approach, provide the narrowest band for streamwater nitrogen, which suggests increased model robustness, though all models exhibit periods of inconsistent good and poor fits between simulated outcomes and observed data. The results confirm the importance of the riparian zone in controlling the short-term (daily) streamwater nitrogen dynamics in this catchment but not the overall flux of nitrogen from the catchment. It was also shown that as the complexity of a hydrological model increases over-parameterisation occurs, but the converse is true for a water quality model where additional process representation leads to additional acceptable model simulations. Water quality data help constrain the hydrological representation in process-based models. Increased complexity was justifiable for modelling river-system hydrochemistry. Increased complexity was justifiable for modelling river-system hydrochemistry.

Evaluating the sustainable intensification of arable farms

Sustainable Intensification (SI) of agriculture has recently received widespread political attention, in both the UK and internationally. The concept recognises the need to simultaneously raise yields, increase input use efficiency and reduce the negative environmental impacts of farming systems to secure future food production and to sustainably use the limited resources for agriculture. The objective of this paper is to outline a policy-making tool to assess SI at a farm level. Based on the method introduced by Kuosmanen and Kortelainen (2005), we use an adapted Data Envelopment Analysis (DEA) to consider the substitution possibilities between economic value and environmental pressures generated by farming systems in an aggregated index of Eco-Efficiency. Farm level data, specifically General Cropping Farms (GCFs) from the East Anglian River Basin Catchment (EARBC), UK were used as the basis for this analysis. The assignment of weights to environmental pressures through linear programming techniques, when optimising the relative Eco-Efficiency score, allows the identification of appropriate production technologies and practices (integrating pest management, conservation farming, precision agriculture, etc.) for each farm and therefore indicates specific improvements that can be undertaken towards SI. Results are used to suggest strategies for the integration of farming practices and environmental policies in the framework of SI of agriculture. Paths for improving the index of Eco-Efficiency and therefore reducing environmental pressures are also outlined.