Thesis (MScEng (Industrial Engineering))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: During the 2009 financial year the sawlog production from plantations in South Africa amounted to 4.4 million m 3 and sawn timber of R4.2 billion was produced from these logs. At the current average price for structural timber, a 1% increase in volume recovery at a medium-sized South African sawmill with an annual log intake of 100 000m 3 will result in additional profit of about R2.2 million annually. The purpose of this project was to evaluate the potential of increasing in value recovery at sawmills through optimization of the positioning of a log at the primary workstation by considering the internal knot properties. Although not yet commercially available, a high speed industrial log CT scanner is currently in development and will enable the evaluation of the internal characteristics of a log before processing. The external profiles and the internal knot properties of ten pine logs were measured and the whole log shape was digitally reconstructed. By using the sawmill simulation program Simsaw, explicit enumeration was performed to gather data. This data include the monetary value that can be earned from sawing the log in a specific log position. For every log a total of 808 020 sawing positions were evaluated. In the sawmill production environment only a few seconds are available to make a decision on the positioning of each log. Meta-heuristic optimization algorithms were developed in order to come to a near optimal solution in a much shorter time than that required when simulating all possible log positions. The algorithms used in this study include the Genetic algorithm, Simulated Annealing, Population Based Incremental Learning and the CrossEntropy method. An Alternative algorithm was also developed to incorporate the trends identified through analysis of the sawmill simulation results. The effectiveness of these meta-heuristic algorithms were evaluated using the sawmill simulation data created. Analysis of the simulation data showed that a maximum increase in product value of 8.23% was possible when internal knot data was considered compared to using conventional log positioning rules. When only external shape was considered a maximum increase in product value of 5% was possible compared to using conventional log positioning rules. The efficiency of the meta-heuristic algorithms differed depending on the processing time available. As an example the Genetic algorithm increased the mean product value by 6.43% after 200 iterations. Finally, a method to evaluate the investment decision to purchase an internal scanning and log positioning system is illustrated. / AFRIKAANSE OPSOMMING: Gedurende die 2009 finansiële jaar is daar 4.4 miljoen m 3 rondehout op plantasies in Suid Afrika geproduseer en saaghout ter waarde van R4.2 biljoen is hieruit vervaardig. Met die huidige gemiddelde prys vir strukturele hout, kan ‘n 1% verhoging in volumeherwinning by ‘n gemiddelde grootte saagmeul in Suid Afrika met ‘n jaarlikse rondehout inname van 100 000 m 3 ‘n bykomende wins van R2.2 miljoen lewer. Die doel van hierdie projek was om die potensiële verhoging in waardeherwinning by ‘n saagmeul te evalueer, indien die posisionering van ‘n stomp by die primêre werkstasie geoptimeer word deur interne kwas eienskappe in ag te neem. Kommersiële CTskandeerders word tans nog nie hiervoor aangewend nie, maar ontwikkelinge in tegnologie sal dit moontlik binnekort prakties moontlik maak om die interne karakteristieke van ‘n stomp te evalueer voor prosessering. Die eksterne profiel en interne kwas eienskappe van tien Pinus rondehout stompe is gemeet en die al tien stompe is digitaal geherkonstrueer. Met behulp van die saagmeulsimulasieprogram, Simsaw, is 808 020 verskillende saagsimulasielopies uitgevoer. Elk van hierdie simulasielopies het ‘n ander beginposisie gehad in terme van rotasie, skeefheid en horisontale verskuiwing. Die finansiële waarde wat verdien kan word deur ‘n stomp in ‘n sekere posisie te saag is telkens bepaal. In die saagmeulomgewing is daar slegs ‘n paar sekondes beskikbaar om ‘n besluit te maak oor hoe ‘n stomp geposisioneer moet word. Meta-heuristiese optimisering algoritmes is ontwikkel om ‘n naby optimale oplossing te bepaal in ‘n baie korter tyd as wanneer alle saagposisies geëvalueer word. Vyf verskillende meta-heuristiese algoritmes is teen mekaar opgeweeg. Vier van hierdie algoritmes is bestaande heuristieke wat vir verskeie ander optimeringsprobleme ingespan word. Die vyfde algoritme is spesifiek vir doeleindes van hierdie projek ontwikkel om die neigings wat tydens die data-analise van die saagmeulsimulasie geïdentifiseer is, te inkorporeer. Die effektiwiteit van hierdie meta-heuristiese algoritmes is bepaal deur van die saagmeul simulasiedata wat gegenereer is gebruik te maak. Analise van die simulasiedata toon dat ‘n maksimum toename in produk waarde van 8% moontlik is wanneer interne kwaseienskappe ook geïnkorporeer word tydens besluitneming teenoor die konvensionele stompposisioneringreëls. Wanneer slegs die eksterne stompprofiel in ag geneem word, is ‘n maksimum produkwaardeverhoging van tot 5% moontlik teenoor resultate wat verkry word met konvensionele stompposisioneringsreëls.

ADans cette thède, nous traitons le problème de stockage de conteneurs dans un terminal portuaire. Dans un premier temps, noux présentons une étude bibliographique dans laquelle sont analysés les travaux qui ont déhà été rélisé dans ce domaine. Ensuite, nous présentons une étude analytique, puis une modélisation mathématique et des méthodes de résolution numérique qui englobent des algorithmes efficaces. Nous proposons une démonstration de la compexité du problème de stockage de conteneurs en considérant différents cas de stockage. Ce problème étant "Np_difficile" peut être difficilement résolu avec le logiciel d'optimisation "ILOG CPLEX". », raison pour laquelle nous proposons un algorithme de banch-and-cut, qui est une méthode de résolution exacte et qui nous a permis de repousser les limites de "ILOG CPLEX". Nous avons aussi proposé des algorithmes métatheuristiques et des hybridations qui procurent des résultats très satisfaisants et qui sont très avantageux en temps de calcul. / AIn this thesis, we trait the container storage problem at port terminal. Initially, we present a state of the art in which the work that have been previously made in this filed are analyzed. After that, we present an analytical study. Thed we propose a mathematical modelling and some methods of resolution including effective algorithms. We propose a demonstration of the complexity of the problem by considering different cases of storage. This problme is "Np_difficult, so not always easy to solve by using the optimization software "ILOG CPLEX”. This is why we propose a branch-and-cut algorithm, wich is an optimal resolution algorithm and wich enables to go beyong the limits of "ILOG CPLEX". We also proposed meta-heuristic algorithms and hybridizations wich provide satisfactory resulys and wich required less calculation times.

Millimeter wave technologies present an appealing solution for increasing data throughputs as they provide abundant contiguous channel bandwidths as compared to conventional microwave networks. However, millimeter wave technologies suffer from severe propagation limitations and channel impairments such as atmospheric attenuation and absorption, path and penetration losses, and blockage sensitivity. Therefore, phased arrays and beamforming technologies are necessary to compensate for the degraded signal levels due to the aforementioned factors. Namely, base stations and mobile stations utilize directional transmission in the control- and data- plane for an enhanced channel capacity, which results in initial access challenges due to the absence of omni-directional transmission. Here the base station and mobile station are compelled to exhaustively search the entire spatial domain, i.e., in order to determine the best beamforming and combining vectors that yield the highest received signal level. Overall, a wide range of studies have looked at the initial beam access challenges in millimeter wave networks, with most efforts focusing on iterative and exhaustive search procedures, as well as subarrays schemes and out-of-band beam access. However, these studies suffer from significant signaling overhead attributed to the prolonged beam scanning cycle. In particular, access times here are excessively high that exceed control plane latencies and coherence times. Furthermore, existing work suffer from high computational complexity, power consumption, energy inefficiency, as well as low directivities and high outage probabilities. In light of the above, the contributions in this dissertation propose fast initial beam access schemes based upon novel meta-heuristic search schemes and beamforming architectures. These contributions include modified search procedures inspired by Nelder Mead, Luss-Jaakola, divide-and-conquer with Tabu search, generalized pattern search, and Hooke Jeeves methods. Furthermore, efficient and highly-directive access schemes are also developed in this dissertation levering sidelobe emissions, grating lobes and Hamming codes. The overall performance of the proposed solutions here is extensively evaluated versus traditional access schemes and incorporating different channel and path loss models. Finally, this dissertation addresses the problem of link sensitivity and blockage effects in millimeter wave networks, a subsequent stage to beam access and link association. Nevertheless, a novel link recovery procedure is proposed here that features instantaneous link-recovery and high signal levels.

Otimização estrutural é uma área relativamente nova que vem sendo cada vez mais explorada. Existem muitos métodos clássicos, e outros mais recentes vem surgindo para disputar em eficiência, confiabilidade e rapidez na obtenção de um resultado ótimo. Os algoritmos são classificados em algoritmos determinísticos, que utilizam a informação do gradiente, ou seja, usam os valores das funções e suas derivadas, e os meta-heurísticos, algoritmos de otimização aleatórios que são métodos probabilísticos não baseados em gradiente, ou seja, usam somente a avaliação da função objetivo. São apresentados dois algoritmos meta-heurísticos relativamente recentes: o Harmony Search, baseado na improvisação musical em busca da harmonia perfeita, e o Firefly Algorithm, que é inspirado no comportamento da luz dos vagalumes. Vários exemplos clássicos de treliças 2-D e 3-D considerando otimização paramétrica e de forma, com restrições de tensão, deslocamento, flambagem e frequência natural, são apresentados para demonstrar a eficiência dos métodos. Os resultados são comparados aos de outros autores usando diferentes métodos encontrados na literatura. Os resultados indicam que os algoritmos de otimização estudados neste trabalho são melhores ou tão eficientes quanto os demais. Por fim, os métodos são aplicados à estrutura de um projeto de engenharia adaptado. / Structural optimization is a relatively new area that has been increasingly exploited. There are many classical methods, and newer are emerging to compete on efficiency, reliability and speed in obtaining an optimal result. The algorithms are classified into deterministic algorithms, which use the gradient information, i.e., use the values of the functions and their derivatives, and meta-heuristic algorithms, random optimization methods which are probabilistic methods not based on gradient, i.e., they use only objective function evaluation. Two relatively recent meta-heuristics algorithms are presented, Harmony Search, based on musical improvisation in search of the perfect harmony, and Firefly Algorithm, which is inspired by the behavior of the light of fireflies. Several benchmarks of 2-D and 3-D trusses considering size and shape optimization, with stress, displacement, buckling and natural frequency constraints, are presented to demonstrate the effectiveness of the methods. The results are compared to the others authors using different methods found in the literature. The results indicate that optimization algorithms studied in this work are better than or as efficient as others. Finally, the methods are applied to the structure of an adapted engineering design.

O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Otimização estrutural é uma área relativamente nova que vem sendo cada vez mais explorada. Existem muitos métodos clássicos, e outros mais recentes vem surgindo para disputar em eficiência, confiabilidade e rapidez na obtenção de um resultado ótimo. Os algoritmos são classificados em algoritmos determinísticos, que utilizam a informação do gradiente, ou seja, usam os valores das funções e suas derivadas, e os meta-heurísticos, algoritmos de otimização aleatórios que são métodos probabilísticos não baseados em gradiente, ou seja, usam somente a avaliação da função objetivo. São apresentados dois algoritmos meta-heurísticos relativamente recentes: o Harmony Search, baseado na improvisação musical em busca da harmonia perfeita, e o Firefly Algorithm, que é inspirado no comportamento da luz dos vagalumes. Vários exemplos clássicos de treliças 2-D e 3-D considerando otimização paramétrica e de forma, com restrições de tensão, deslocamento, flambagem e frequência natural, são apresentados para demonstrar a eficiência dos métodos. Os resultados são comparados aos de outros autores usando diferentes métodos encontrados na literatura. Os resultados indicam que os algoritmos de otimização estudados neste trabalho são melhores ou tão eficientes quanto os demais. Por fim, os métodos são aplicados à estrutura de um projeto de engenharia adaptado. / Structural optimization is a relatively new area that has been increasingly exploited. There are many classical methods, and newer are emerging to compete on efficiency, reliability and speed in obtaining an optimal result. The algorithms are classified into deterministic algorithms, which use the gradient information, i.e., use the values of the functions and their derivatives, and meta-heuristic algorithms, random optimization methods which are probabilistic methods not based on gradient, i.e., they use only objective function evaluation. Two relatively recent meta-heuristics algorithms are presented, Harmony Search, based on musical improvisation in search of the perfect harmony, and Firefly Algorithm, which is inspired by the behavior of the light of fireflies. Several benchmarks of 2-D and 3-D trusses considering size and shape optimization, with stress, displacement, buckling and natural frequency constraints, are presented to demonstrate the effectiveness of the methods. The results are compared to the others authors using different methods found in the literature. The results indicate that optimization algorithms studied in this work are better than or as efficient as others. Finally, the methods are applied to the structure of an adapted engineering design.

Deep packet inspection (DPI) is useful as a tool for analyzing internet traffic. Regular expressions (regexps) can be used to detect the network traffic patterns that the DPI is able to identify. These regexps can be represented as state-machines, and sometimes combining smaller state-machines into larger state-machines can result in more efficient processing. This thesis looks at how to decide which state-machines used in DPI-classes should be combined with which other state-machines in an efficient manner using genetic algorithms. The goal being to create as few resulting state-machines from the combination while still maintaining a upper limit on the size of the resulting state-machines. The problem is modelled as an assignment problem for which an emulated surrogate problem is used in order to make experimental evaluations. Several genetic algorithms are suggested in an attempt to explore a wide range of parameters. It is also evaluated if different genetic algorithms perform differently depending on if the state-machines represent DPI-classes used to parse UDP or TCP traffic. A 2-dimensional representation is used that allows for a better capture of the underlying assignment problem. Different approaches to fitness are explored and found to have different efficacy in different situations. Several genetic algorithm operators are suggested for different situations and a difference is found between what works for UDP and for TCP. / Deep packet inspection (DPI) ̈ar användbart som ett verktyg f ̈or att analysera internettrafik. Regular expressions (regexps) kan användas för att detektera trafik mönster somDPI:n kan identifiera. De här regexps kan representeras som state-machines, och ibland så kan kombinationen av mindre state-machines till större state-machines resultera i mer effektiv bearbetning. Den här tesen undersöker hur man kan bestämma vilka state-machines som används iDPI-klassen bör bli kombinerade på ett effektivt sätt med genetiska algoritmer. Målet är att skapa så fǻ resulterande state-machines från kombineringen på ett sådant sätt att storleken på alla resulterande state-machines håller sig under en övre gräns. Problemet är modellerat som ett assignment problem för vilket ett emulerat surrogatproblem används för att tillåta experiment att utföras. Ett flertal genetiska algoritmer är föreslagna i ett försök att undersöka en bred räckvidd av parametrar. Det är också undersökt om olika genetiska algoritmer har olika prestanda beroende på om state-machines representerar DPI-klasser använda för UDP eller TCP trafik. En 2-dimensionell representation som fångar det underliggande problemet på ett bras sätt är använd. Olika tillvägagångssätt för att representera fitness är undersökta och är upptäckta att ha olika effektivitet i olika situationer. Ett flertal genetiska algoritm operatorer är föreslagna för olika situationer och en skillnad är hittad mellan vad som fungerar för UDP och vad som fungerar för TCP.

El texto completo de este trabajo no está disponible en el Repositorio Académico UPC por restricciones de la casa editorial donde ha sido publicado. / Online social media has made the process of disseminating news so quick that people have shifted their way of accessing news from traditional journalism and press to online social media sources. The rapid rotation of news on social media makes it challenging to evaluate its reliability. Fake news not only erodes public trust but also subverts their opinions. An intelligent automated system is required to detect fake news as there is a tenuous difference between fake and real news. This paper proposes an intelligent gravitational search random forest (IGSRF) algorithm to be employed to detect fake news. The IGSRF algorithm amalgamates the Intelligent Gravitational Search Algorithm (IGSA) and the Random Forest (RF) algorithm. The IGSA is an improved intelligent variant of the classical gravitational search algorithm (GSA) that adds information about the best and worst gravitational mass agents in order to retain the exploitation ability of agents at later iterations and thus avoid the trapping of the classical GSA in local optimum. In the proposed IGSRF algorithm, all the intelligent mass agents determine the solution by generating decision trees (DT) with a random subset of attributes following the hypothesis of random forest. The mass agents generate the collection of solutions from solution space using random proportional rules. The comprehensive prediction to decide the class of news (fake or real) is determined by all the agents following the attributes of random forest. The performance of the proposed algorithm is determined for the FakeNewsNet dataset, which has sub-categories of BuzzFeed and PolitiFact news categories. To analyze the effectiveness of the proposed algorithm, the results are also evaluated with decision tree and random forest algorithms. The proposed IGSRF algorithm has attained superlative results compared to the DT, RF and state-of-the-art techniques. / Revisión por pares

No description available.

In this dissertation, the vehicle routing problem and one of its variants, the vehicle routing problem with simultaneous pick up and deliveries (VRPSPD) are studied. The traditional vehicle routing problem (VRP) consists of constructing minimum cost routes for the vehicles to follow so that the set of customers are visited only once. A lot of effort has been devoted to research on developing fast and effective solution methods for many different versions of this problem by different majors of engineering profession. Thus, a structuring effort is needed to organize and document the vast literature so far has accumulated in this field. Over its lifespan the VRP literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this dissertation begins with defining VRP's domain in its entirety, accomplishes an allencompassing taxonomy for the VRP literature, and delineates all of VRP's facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Next, a more detailed version of the original problem, the VRPSPD is examined and a more abstract taxonomy is proposed. Additionally, two other existing classification methodologies are used to distinguish all published VRPSPD papers on their respective research strategies and solution methods. By using well-organized methods this study provides a solid multidimensional identification of all VRPSPD studies? attributes thus synthesizing knowledge in the filed. Finally, a hybrid metaheuristic solution algorithm for the VRPSPD problem is presented. To solve this NP-hard vehicle routing problem a GRASP initiated hybrid genetic algorithm is developed. The algorithm is tested on two sets of benchmark problems from the literature with respect to computational efficiency and solution quality. The effect of starting with a better initial population for the genetic algorithm is further investigated by comparing the current results with previously generated ones. The experimental results indicate that the proposed algorithm produces relatively good quality solutions and a better initial population yields a reduction in processing cycles.