A mobile ad hoc network (MANET) is an infrastructure-less multi-hop network where each node communicates with other nodes directly or indirectly through intermediate nodes. Thus, all nodes in a MANET basically function as mobile routers participating in some routing protocol required for deciding and maintaining the routes. Since MANETs are infrastructure-less, self-organizing, rapidly deployable wireless networks, they are highly suitable for applications such as military tactical operations, search and rescue missions, disaster relief operations, and target tracking. Building such ad-hoc networks poses a significant technical challenge because of energy constraints and specifically in relation to the application of wireless network protocols. As a result of its highly dynamic and distributed nature, the routing layer within the wireless network protocol stack, presents one of the key technical challenges in MANETs. In particular, energy efficient routing may be the most important design criterion for MANETs since mobile nodes are powered by batteries with limited capacity and variable recharge frequency, according to application demand. In order to conserve power it is essential that a routing protocol be designed to guarantee data delivery even should most of the nodes be asleep and not forwarding packets to other nodes. Load distribution constitutes another important approach to the optimisation of active communication energy. Load distribution enables the maximisation of the network lifetime by facilitating the avoidance of over-utilised nodes when a route is in the process of being selected. Routing algorithms for mobile networks that attempt to optimise routes while at- tempting to retain a small message overhead and maximise the network lifetime has been put forward. However certain of these routing protocols have proved to have a negative impact on node and network lives by inadvertently over-utilising the energy resources of a small set of nodes in favour of others. The conservation of power and careful sharing of the cost of routing packets would ensure an increase in both node and network lifetimes. This thesis proposes simultaneously, by using an ant colony optimisation (ACO) approach, to optimise five power-aware metrics that do result in energy-efficient routes and also to maximise the MANET's lifetime while taking into consideration a realistic mobility model. By using ACO algorithms a set of optimal solutions - the Pareto-optimal set - is found. This thesis proposes five algorithms to solve the multi-objective problem in the routing domain. The first two algorithms, namely, the energy e±ciency for a mobile network using a multi-objective, ant colony optimisation, multi-pheromone (EEMACOMP) algorithm and the energy efficiency for a mobile network using a multi-objective, ant colony optimisation, multi-heuristic (EEMACOMH) algorithm are both adaptations of multi-objective, ant colony optimisation algorithms (MOACO) which are based on the ant colony system (ACS) algorithm. The new algorithms are constructive which means that in every iteration, every ant builds a complete solution. In order to guide the transition from one state to another, the algorithms use pheromone and heuristic information. The next two algorithms, namely, the energy efficiency for a mobile network using a multi-objective, MAX-MIN ant system optimisation, multi-pheromone (EEMMASMP) algorithm and the energy efficiency for a mobile network using a multi-objective, MAX- MIN ant system optimisation, multi-heuristic (EEMMASMH) algorithm, both solve the above multi-objective problem by using an adaptation of the MAX-MIN ant system optimisation algorithm. The last algorithm implemented, namely, the energy efficiency for a mobile network using a multi-objective, ant colony optimisation, multi-colony (EEMACOMC) algorithm uses a multiple colony ACO algorithm. From the experimental results the final conclusions may be summarised as follows:<ul><li> Ant colony, multi-objective optimisation algorithms are suitable for mobile ad hoc networks. These algorithms allow for high adaptation to frequent changes in the topology of the network. </li><li> All five algorithms yielded substantially better results than the non-dominated sorting genetic algorithm (NSGA-II) in terms of the quality of the solution. </li><li> All the results prove that the EEMACOMP outperforms the other four ACO algorithms as well as the NSGA-II algorithm in terms of the number of solutions, closeness to the true Pareto front and diversity. </li></ul> / Thesis (PhD)--University of Pretoria, 2010. / Computer Science / unrestricted

The long-term evolution (LTE) network has been proposed to provide better network capacity than the earlier 3G network. Driven by the market, the conventional LTE (3G) network standard could not achieve the expectations of the international mobile telecommunications advanced (IMT-Advanced) standard. To satisfy this gap, the LTE-Advanced was introduced with additional network functionalities to meet up with the IMT-Advanced Standard. In addition, due to the need to minimize operational expenditure (OPEX) and reduce human interventions, the wireless cellular networks are required to be self-aware, self-reconfigurable, self-adaptive and smart. An example of such network involves transceiver base stations (BTSs) within a self-organizing network (SON). Besides these great breakthroughs, the conventional LTE and LTE-Advanced networks have not been designed with the intelligence of scalable capacity output especially in sudden demographic changes, namely during events of football, malls, worship centres or during religious and cultural festivals. Since most of these events cannot be predicted, modern cellular networks must be scalable in terms of capacity and coverage in such unpredictable demographic surge. Thus, the use of dynamic BTSs is proposed to be used in modern and future cellular networks for crowd and demographic change managements. Dynamic BTSs are complements of the capability of SONs to search, determine and deploy less crowded/idle BTSs to densely crowded cells for scalable capacity management. The mobile BTSs will discover areas of dark coverages and fill-up the gap in terms of providing cellular services. The proposed network relieves the LTE network from overloading thus reducing packet loss, delay and improves fair load sharing. In order to trail the best (least) path, a bio-inspired optimization algorithm based on swarm-particle optimization is proposed over the dynamic BTS network. It uses the ant-colony optimization algorithm (ACOA) to find the least path. A comparison between an optimized path and the un-optimized path showed huge gain in terms of delay, fair load sharing and the percentage of packet loss.

No description available.

Bayesian network (BN) structure learning from data has been an active research area in the machine learning field in recent decades. Much of the research has considered BN structure learning as an optimization problem. However, the finding of optimal BN from data is NP-hard. This fact has driven the use of heuristic algorithms for solving this kind of problem. Amajor recent focus in BN structure learning is on search and score algorithms. In these algorithms, a scoring function is introduced and a heuristic search algorithm is used to evaluate each network with respect to the training data. The optimal network is produced according to the best score evaluated. This thesis investigates a range of search and score algorithms to understand the relationship between technique performance and structure features of the problems. The main contributions of this thesis include (a) Two novel Ant Colony Optimization based search and score algorithms for BN structure learning; (b) Node juxtaposition distribution for studying the relationship between the best node ordering and the optimal BN structure; (c) Fitness landscape analysis for investigating the di erent performances of both chain score function and the CH score function; (d) A classifier method is constructed by utilizing receiver operating characteristic curve with the results on fitness landscape analysis; and finally (e) a selective o -line hyperheuristic algorithm is built for unseen BN structure learning with search and score algorithms. In this thesis, we also construct a new algorithm for producing BN benchmark structures and apply our novel approaches to a range of benchmark problems and real world problem.

The global competitive environment and the growing demand for personalised products have increased the interest of companies in producing similar product models on the same assembly line. Companies are forced to make significant structural changes to rapidly respond to diversified demands and convert their existing single-model lines into mixed-model lines in order to avoid unnecessary new line construction cost for each new product model. Mixed-model assembly lines play a key role in increasing productivity without compromising quality for manufacturing enterprises. The literature is extensive on assembling small-sized products in an intermixed sequence and assembling large-sized products in large volumes on single-model lines. However, a mixed-model parallel two-sided line system, where two or more similar products or similar models of a large-sized product are assembled on each of the parallel two-sided lines in an intermixed sequence, has not been of interest to academia so far. Moreover, taking model sequencing problem into consideration on a mixed-model parallel two-sided line system is a novel research topic in this domain. Within this context, the problem of simultaneous balancing and sequencing of mixed-model parallel two-sided lines is defined and described using illustrative examples for the first time in the literature. The mathematical model of the problem is also developed to exhibit the main characteristics of the problem and to explore the logic underlying the algorithms developed. The benefits of utilising multi-line stations between two adjacent lines are discussed and numerical examples are provided. An agent-based ant colony optimisation algorithm (called ABACO) is developed to obtain a generic solution that conforms to any model sequence and it is enhanced step-by-step to increase the quality of the solutions obtained. Then, the algorithm is modified with the integration of a model sequencing procedure (where the modified version is called ABACO/S) to balance lines by tracking the product model changes on each workstation in a complex production environment where each of the parallel lines may a have different cycle time. Finally, a genetic algorithm based model sequencing mechanism is integrated to the algorithm to increase the robustness of the obtained solutions. Computational tests are performed using test cases to observe the performances of the developed algorithms. Statistical tests are conducted through obtained results and test results establish that balancing mixed-model parallel two-sided lines together has a significant effect on the sought performance measures (a weighted summation of line length and the number of workstations) in comparison with balancing those lines separately. Another important finding of the research is that considering model sequencing problem along with the line balancing problem helps algorithm find better line balances with better performance measures. The results also indicate that the developed ABACO and ABACO/S algorithms outperform other test heuristics commonly used in the literature in solving various line balancing problems; and integrating a genetic algorithm based model sequencing mechanism into ABACO/S helps the algorithm find better solutions with less amount of computational effort.

[pt] A interpretação de falhas sísmicas é uma tarefa complexa e trabalhosa, que está sujeita à experiência do geólogo. Normalmente ela é auxiliada pela análise de atributos sísmicos, que podem não ser suficientes para uma clara visualização das falhas. Este trabalho realiza uma análise dos métodos atuais que utilizam ACO para o realce de atributos de falha, de forma a entender a contribuição de cada etapa para o resultado. Com base nessa análise, um novo método é proposto, o qual elimina as fraquezas encontradas de forma a buscar uma convergência mais estável e rápida ao resultado. / [en] The interpretation of seismic faults is a complex and labourious task, which is dependent on the experience of the geologist. The interpretation is normally aided by seismic attributes. However, they may not be enough for a clear visualization nor to be used in automatic extraction methods. This dissertation accomplishes an examination of the state of the art ACO algorithms for fault enhancement. This study reveals the importance, contributions and weaknesses of each step of these methods. From there, a new method is proposed, which eliminates some of the problems found, acquiring a more stable and quick convergence of the end result.

Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif / In this thesis, we investigate the capabilities of Ant Colony Optimization (ACO) metaheuristic to solve combinatorial and multi-objective optimization problems. First, we propose a taxonomy of ACO algorithms proposed in the literature to solve multi-objective problems. Then, we studydifferent pheromonal strategies for the case of mono-objective multidimensional knapsackproblem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. Thisalgorithm is parameterised by the number of ant colonies and the number of pheromonestructures. This algorithm allows us to evaluate and compare new and existing approaches in thesame framework. We compare six variants of this generic algorithm on the multi-objectivemultidimensional knapsack problem

O objetivo deste trabalho é apresentar uma nova abordagem para obtenção de configurações para sistemas de distribuição de energia elétrica com o intuito de minimizar o valor de perdas ativas sem violar as restrições operacionais. Para isso, considera-se que os sistemas de distribuição estão operando em regime permanente e que suas fases estão equilibradas e simétricas, podendo o sistema ser representado por um diagrama unifilar. A reconfiguração é feita de forma a redistribuir os fluxos de corrente nas linhas, transferindo cargas entre os alimentadores e melhorando o perfil de tensão ao longo do sistema. O problema de reconfiguração do sistema pode ser formulado como um problema de programação não-linear inteiro misto. Devido à explosão combinatorial inerente a este tipo de problema, a resolução do mesmo por técnicas de otimização clássicas torna-se pouco atraente, dando espaço para técnicas heurísticas e metaheurísticas. Essas outras, mesmo não garantindo o ótimo global, são capazes de encontrar boas soluções em um espaço de tempo relativamente curto. Para a resolução do problema de reconfiguração, utilizou-se uma nova metodologia baseada no comportamento de colônias de formigas em busca de alimento na natureza. Nesta, formigas artificiais (agentes) exploram o meio ambiente (sistema de distribuição) e trocam informações para tentar encontrar a topologia que apresente os menores valores de perdas ativas. Para o cálculo das perdas, este trabalho também apresenta uma nova abordagem para resolução do problema de fluxo de potência (FP) em sistemas de distribuição radial. O fluxo de potência é uma ferramenta básica utilizada pelos centros de controle para determinar os estados e condições operacionais desses sistemas de potência. Basicamente, as metodologias empregadas para o cálculo do fluxo de potência são baseadas nos métodos clássicos de Newton ou Gauss. Mas em sistemas de distribuição de energia, devido a particularidades inerentes a estes, como a alta relação entre resistência e reatância das linhas (r/x) e a operação radial, estes métodos apresentam problemas de convergência e se tornam ineficientes na maioria das vezes. A abordagem consiste na associação dos métodos da função penalidade e de Newton. O mal-condicionamento da matriz Jacobiana de Newton é resolvido pela associação com o método da função penalidade. São apresentados testes realizados em sistemas de 5 barras, 16 barras, 33 barras, 69 barras e 136 barras para avaliar a potencialidade das técnicas propostas. Os resultados são considerados bons ou muito bons quando comparado com as técnicas existentes atualmente. / The objective of this work is to present a novel methodology for obtaining new configurations of the distribution system in order to minimize the active power losses without violating operational constraints. For this, it is considered that any distribution system is operating in a steady state and that it is balanced, therefore it can be represented by a one-line diagram. The reconfiguration is done in order to redistribute de current flows on the distribution power lines, transferring loads among the feeders and improving the voltage profile along the system. Such problem can be formulated as a mixed integer nonlinear programming problem. Due to its inherent combinatorial characteristic and since its solution by classic optimization techniques is not appealing, heuristic and metaheuristic techniques are thus better suited for its solution. Although these latter do not guarantee a global optimum, they are able to find good solutions in a relatively short time. The solution of the reconfiguration problem in this approach makes use of a novel methodology based on ant colony behavior, when these search for victuals in nature. In this technique, the artificial ants (agents) explore the environment (distribution system) and exchange information among them in order to find the topology that provides the smallest active losses. For the active losses calculation, this work also presents a novel approach for the solution of the power flow problem for radial distribution systems. The solution of the power flow problem is used by system operators in order to determine the state and operational conditions of power systems. Basically, the most common techniques used in the power flow solution are based on either Newton\'s or Gauss\' approaches. However, due to particular characteristics of distribution systems such as the high ratio of r/x and the radial topology, these methods present convergence problems and are not efficient in most of the cases. Thus, this novel technique consists in associating Newton\'s and the penalty function approaches. The matter of the ill-conditioned Jacobian matrix in Newton\'s method is overcome with the penalty function method. Some tests performed in different systems are then presented in order to assess the effectiveness of both proposed techniques.

A tarefa de planejamento de trajetórias de robôs móveis autônomos consiste em determinar objetivos intermediários para que um robô seja capaz de partir de sua localização inicial e alcançar seu objetivo final. Além do planejamento, é importante definir um método de controle da navegação (seguimento da trajetória) do robô para que ele seja capaz de realizar seu trajeto de forma segura. Este projeto propõe uma abordagem híbrida para planejamento exploratório e execução de trajetórias de robôs móveis autônomos em ambientes indoor. Para o planejamento de trajetória, foram investigados algoritmos de busca em espaço de estados, dando ênfase ao uso de algoritmos evolutivos e algoritmos de otimização por colônia de formigas para a descoberta e otimização da trajetória. O controle da navegação é realizado por meio de comportamentos locais reativos, baseado na exploração e uso de mapas topológicos, os quais permitem uma maior flexibilidade em termos de definição da localização da posição do robô móvel e sobre os detalhes do mapa do ambiente (mapas com informações aproximadas e não métricos). Assim, foi proposto e desenvolvido um método robusto capaz de planejar, mapear e explorar um caminho ótimo ou quase ótimo para que o robô possa navegar e alcançar seu objetivo de forma segura, com pouca informação prévia do ambiente ou mesmo sobre sua localização. Além disso, o robô pode reagir a ambientes com alterações dinâmicas em sua estrutura, considerando por exemplo, elementos dinâmicos como portas que possam ser abertas ou fechadas e passagens que são obstruídas. Por fim, foram realizados diversos testes e simulações a fim de validar o método proposto, com a avaliação da qualidade das soluções encontradas e comparação com outras abordagens tradicionais de planejamento de trajetórias (algoritmos A* e D*). / The task of planning path for autonomous mobile robots consists in determine intermediary goals in order to allow a robot be able to leave its initial location and reach its final goal. Besides the planning, it is important to define a method of navigation control (the trajectory following) of the robot for it be able to do its path safely. This project proposes a hybrid approach to path planning and execution of an autonomous mobile robot in indoor environments. For the path planning, search algorithms in state space have been investigated, with emphasis in evolutionary algorithms and ant colony optimization algorithms for the trajectory search and optimization. The navigation control is done by local reactive behaviors, based on topological maps, which allow more flexibility concerning localization definition of position of the mobile robot and about the details of the environment map (maps with approximate information and not metric). Thus, a robust method able to plan an optimum or almost optimum path for the robot to reach its goal safely has been proposed, with little previous information of the environment. Furthermore, the robot can react to dynamic elements in the environment structure, concerning, for example, dynamic elements such as doors that can be opened or closed and ways that are blocked. Finally, several tests and simulations has been carried out to validate the proposed method, with evaluation of the solutions quality and comparison with others traditional approaches for the path planning task (A* and D* algorithms).

Dans cette thèse nous proposons un outil d’aide à la décision multicritère qui permet aux décideurs de sélectionner un scénario optimal dans un graphe de projet qui contient toutes les alternatives de choix de conception et de réalisation d’un nouveau système, tout en tenant compte des risques inhérents aux choix réalisés. Le modèle du graphe est construit en considérant toutes les décisions collaboratives des différents acteurs impliqués dans le projet. Cet outil d’aide à la décision est basé principalement sur les techniques de l’optimisation combinatoire. En effet, nous avons choisi de travailler avec la métaheuristique ACO (algorithme d’optimisation par colonies de fourmis) vu sa capacité à fournir des solutions optimales dans un temps raisonnable. Les objectifs à minimiser sont le coût global du projet, sa durée totale de réalisation et l’incertitude sur ces critères (coût, durée). La modélisation des incertitudes a été abordée suivant deux approches différentes. La première approche consiste à modéliser l’incertitude en utilisant des intervalles simples et en la considérant comme un objectif à part entière à optimiser avec le coût et la durée. Quant à la deuxième approche, elle permet de modéliser l’incertitude sur les objectifs du projet (coût, durée) sous formes de distributions de probabilités. L’outil d’optimisation proposé dans la thèse fait partie d’un processus intégré et plus global qui se base sur les standards industriels (processus d’ingénierie système et de management de projet) qui sont largement connus et utilisés dans les entreprises. Ainsi, le travail développé dans cette thèse constitue un vrai guide pour les industriels dans leurs processus de conception et de réalisation des systèmes complexes innovants dans le domaine d’ingénierie système. / In this thesis, we propose a multi-criteria decision making tool that allows decision-makers to select an optimal scenario in a project graph that includes all the alternative choices of a new system’s conception and realization, while taking into account the risks inherent to these choices. The model of the graph is constructed by considering all the collaborative decisions of the different actors involved in the project. This decision making tool is based mainly on the techniques of combinatorial optimization. Indeed, we have decided to work with the metaheuristic ACO (Ant Colony Optimization algorithm) for its ability to provide optimal solutions in a reasonable amount of time. The objectives to be minimized are the total cost of the project, its global duration and the uncertainties about these criteria (cost, duration). The uncertainties modeling is performed according to two different approaches. The first approach consists in using single intervals to model the uncertainty and it is considered as a third objective to optimize besides cost and duration. As for the second approach, the uncertainty about project objectives (cost, duration) is performed by using probabilities distributions. The optimization tool proposed in this thesis is a part of an integrated and more global process, based on industrial standards (the systems engineering process and the project management one) that are widely known and used in companies. Thus, the work developed in this thesis is a real guide for companies in their process of design and realization of innovative complex systems in the systems engineering field.