O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação. / The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region\'s vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.

O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação. / The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region\'s vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.

<p>Detta examensarbete har utförts på och i samarbete med ITN, Institutionen för Teknik och Naturvetenskap, vid Linköpings Universitet. Problemställningen härrör från tidigare projektsamarbete mellan Linköpings Universitet, Telia AB och Ericsson. Uppgiften består i att ta fram en optimeringsalgoritm som använder sig av ett nytt angreppssätt genom att försöka minska osäkerheten på indata.</p>

<p>This thesis investigates the possibilities to extend a tactical air combat simulator, named TACSI, with support for team behavior in fight and attack scenarios. A model for describing teamwork has been developed. The model uses plans and primitive team actions to achieve goals. A social structure is used to transfer the responsibility for making decisions from the team to a single agent within the team. Special care have been taken to allow an effctive distribution of targets within the team. In order to test the concepts of the model and to evaluate the applicability in TACSI, a limited implementation of the team behavior model have been made. The results show that the concepts of the model works and that the model is applicable in TACSI, but some things is left to be specified in order to make a complete implementation.</p>

Modifiable Boltzmann selective pressure is investigated as a tool to control variability in optimizations using genetic algorithms. An implementation of variable selective pressure, modeled after the use of temperature as a parameter in simulated annealing approaches, is described. The convergence behavior of optimization runs is illustrated as a function of selective pressure; the method is compared to a genetic algorithm lacking this control feature and is shown to exhibit superior convergence properties on a small set of test problems. An analysis is presented that compares the selective pressure of this algorithm to a standard selection procedure.

Human exposure to reduced weightbearing results in bone loss. The rate of bone loss during microgravity exposure is similar to that of a post-menopausal women. In fact, the maintenance of bone mass is intimately dependent on exercise. Therefore, exercise associated mechanical loads to bone tissue are an important countermeasure to prevent disuse-induced bone loss. However, the types of exercise modalities required to prevent such bone loss are unclear. Moreover, how mechanical loading to bone translates into molecular osteogenic signals in bone cells is unknown. Radiation exposure is another potent inducer of bone loss, namely observed on Earth in the clinical setting following radiotherapy procedures. It is expected that long duration space missions outside the protection of Earth’s magnetosphere will result in significant galactic cosmic radiation exposure. However, the magnitude of bone loss resulting from this galactic cosmic radiation exposure is unclear. Moreover, it is unknown if radiation exposure will exacerbate disuse-induced bone loss. Therefore, a series of experiments were designed to determine: 1) Will simulated galactic cosmic radiation exacerbate reduced weightbearing-induced bone loss? 2) Will pharmacological activation of the putative mechanosensing Wnt pathway enhance exercise-induced bone mass gain? To address these questions the experimental study series employed two animal models of reduced weightbearing, hindlimb unloading and partial weightbearing. These model test-beds enabled the evaluation of two novel countermeasures (simulated resistance exercise and glycogen synthase kinase-3 (GSK-3) therapeutic) and simulated exposure to space radiation environments. To test the impact of simulated space radiation (28Si) one study of the series was conducted at Brookhaven National Laboratory. To quantify the impact of the abovementioned countermeasures and space radiation on bone, mechanical testing, peripheral quantitative computed tomography, micro-computed tomography, histomorphometry, and immunohistochemistry served as primary outcome measures. The primary findings are: 1) Low-dose high-LET radiation negativity impacts maintenance of bone mass by lowering bone formation and increasing bone resorption. This impaired bone formation response is in part due to sclerostin induced suppression of Wnt signaling. 2) Combining GSK-3 inhibition with high intensity exercise mitigates cancellous bone loss and restores cortical periosteal growth during disuse.

No és difícil trobar exemples que mostrin la inqüestionable importància de la estereoquímica en temes com la salut o l'economia: D'una banda, la quiralitat és tristament ben coneguda a causa del desastre de la Talidomida. Per altra banda, varem trobar recentment un altre exemple no menys important dins el camp de les conformacions de macromolècules: La Malaltia de Creutzfeld-Jacob. Per això, creiem que és rellevant examinar amb més detall aquells temes relacionats amb els estudis conformacionals.A la present Tesi Doctoral es proposa un procés en dues etapes per a estudiar espais conformacionals de macromolècules mitjançant Simulated Annealing (SA) i Dinàmica Molecular (DM). Ambdues metodologies són ben conegudes dins el camp de la Modelització Molecular; no obstant això, la principal contribució aportada per aquest treball és el desenvolupament d'eines metodològiques millorades -descriptors moleculars adequats, anàlisi de saturació de conformacions i grau de solapament de trajectòries- per mesurar quantitativament l'evolució i convergència dels càlculs SA i MD. / No es difícil encontrar ejemplos que muestren la incuestionable importacia de la estereoquímica en temas como la salud o la economía: Por una parte, la quiralidad es tristemente bien conocida debido al desastre de la Talidomida. Por otra parte, encontramos recientemente otro ejemplo no menos importante dentro del campo de las conformaciones de macromoléculas: La Enfermedad de Creutzfeld-Jacob. Por ello, creemos que es relevante examinar más detenidamente aquellos temas relacionados con los estudios conformacionales.En la presente Tesis Doctoral se propone un proceso en 2 etapas para estudiar espacios conformacionales de macromoléculas mediante Simulated Annealing (SA) y Dinámica Molecular (DM). Ambas metodologías son bien conocidas dentro del campo de la Modelización Molecular; sin embargo la principal contribución aportada por este trabajo es el desarrollo de herramientas metodológicas mejoradas -descriptores moleculares adecuados, análisis de saturación de conformaciones y grado de solapamiento de trayectorias- para medir cuantitativamente la evolución y convergencia de los cálculos SA y MD. / It is not difficult to find examples that show the unquestionable importance of stereochemistry in human life and economy: On the one hand, chirality is unfortunately the most well known one due to the Thalidomide Disaster. On the other hand, there is a no less important example in recent years in the field of molecular conformations: the Creutzfeldt-Jakob Disease. In this sense, we think that it is worth paying more attention to conformational studies due to their indisputable relevance.A 2-stage process for studying Conformational Spaces of large macromolecules involving Simulated Annealing (SA) Conformational Search followed by series of Molecular Dynamics (MD) calculations is proposed in this PhD Thesis. Both methodologies are well-known ones in the Molecular Modelling area of knowledge; nevertheless, the main contribution made by this research work is the development of enhanced methodological techniques -suitable molecular descriptors, saturation analysis and trajectory overlapping ratio- for monitoring quantitatively how SA and MD calculations evolve.

Search-based placement methods have long been used for placing integrated circuits targeting the field programmable gate array (FPGA) and standard cell design styles. Such methods offer the potential for high-quality solutions but often come at the cost of long run-times compared to alternative methods. This dissertation examines strategies for enhancing local search heuristics---and in particular, simulated annealing---through the application of directed moves. These moves help to guide a search-based optimizer by focusing efforts on states which are most likely to yield productive improvement, effectively pruning the size of the search space. The engineering theory and implementation details of directed moves are discussed in the context of both field programmable gate array and standard cell designs. This work explores the ways in which such moves can be used to improve the quality of FPGA placements, improve the robustness of floorplan repair and legalization methods for mixed-size standard cell designs, and enhance the quality of detailed placement for standard cell circuits. The analysis presented herein confirms the validity and efficacy of directed moves, and supports the use of such heuristics within various optimization frameworks.

Detta examensarbete har utförts på och i samarbete med ITN, Institutionen för Teknik och Naturvetenskap, vid Linköpings Universitet. Problemställningen härrör från tidigare projektsamarbete mellan Linköpings Universitet, Telia AB och Ericsson. Uppgiften består i att ta fram en optimeringsalgoritm som använder sig av ett nytt angreppssätt genom att försöka minska osäkerheten på indata.

Search-based placement methods have long been used for placing integrated circuits targeting the field programmable gate array (FPGA) and standard cell design styles. Such methods offer the potential for high-quality solutions but often come at the cost of long run-times compared to alternative methods. This dissertation examines strategies for enhancing local search heuristics---and in particular, simulated annealing---through the application of directed moves. These moves help to guide a search-based optimizer by focusing efforts on states which are most likely to yield productive improvement, effectively pruning the size of the search space. The engineering theory and implementation details of directed moves are discussed in the context of both field programmable gate array and standard cell designs. This work explores the ways in which such moves can be used to improve the quality of FPGA placements, improve the robustness of floorplan repair and legalization methods for mixed-size standard cell designs, and enhance the quality of detailed placement for standard cell circuits. The analysis presented herein confirms the validity and efficacy of directed moves, and supports the use of such heuristics within various optimization frameworks.