Algoritmo memético com infecção viral: uma aplicação ao problema do caixeiro viajante assimétrico

The Combinatorial Optimization is a basic area to companies who look for competitive advantages in the diverse productive sectors and the Assimetric Travelling Salesman Problem, which one classifies as one of the most important problems of this area, for being a problem of the NP-hard class and for possessing diverse practical applications, has increased interest of researchers in the development of metaheuristics each more efficient to assist in its resolution, as it is the case of Memetic Algorithms, which is a evolutionary algorithms that it is used of the genetic operation in combination with a local search procedure. This work explores the technique of Viral Infection in one Memetic Algorithms where the infection substitutes the mutation operator for obtaining a fast evolution or extinguishing of species (KANOH et al, 1996) providing a form of acceleration and improvement of the solution . For this it developed four variants of Viral Infection applied in the Memetic Algorithms for resolution of the Assimetric Travelling Salesman Problem where the agent and the virus pass for a symbiosis process which favored the attainment of a hybrid evolutionary algorithms and computational viable

Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process

O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante

Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure

Algorítmo evolucionário para a distribuição de produtos de petróleo por redes de polidutos

The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated

Multicast packing problem: abordagem multiobjetivo

This work presents a algorithmic study of Multicast Packing Problem considering a multiobjective approach. The first step realized was an extensive review about the problem. This review serverd as a reference point for the definition of the multiobjective mathematical model. Then, the instances used in the experimentation process were defined, this instances were created based on the main caracteristics from literature. Since both mathematical model and the instances were definined, then several algoritms were created. The algorithms were based on the classical approaches to multiobjective optimization: NSGA2 (3 versions), SPEA2 (3 versions). In addition, the GRASP procedures were adapted to work with multiples objectives, two vesions were created. These algorithms were composed by three recombination operators(C1, C2 e C3), two operator for build solution, a mutation operator and a local search procedure. Finally, a long experimentation process was performed. This process has three stages: the first consisted of adjusting the parameters; the second was perfomed to indentify the best version for each algorithm. After, the best versions for each algorithm were compared in order to identify the best algorithm among all. The algorithms were evaluated based on quality indicators and Hypervolume Multiplicative Epsilon

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Uma prática educativa ambiental na construção de agenda 21 local.

This proposal is to search, investigate practical experience in environmental education for the construction of Local Agenda 21, in the municipality of Maxaranguape-RN, attended that brought together various subject and collective social actors of civil society organizations, among them, the Center for Education and Advice Herbert de Souza - CEAHS (NGOs who serves on the council since 1999), associations of farmers and farmers in areas of settlements, teachers / as, groups of women and young people, entrepreneurs, public power, the German partner entities IBAMA. INCRA, BNB in the project of Agenda 21. They are members and participants, constituents of the Permanent Forum of Agenda 21, the main actor privileged in the search. As an object of study to identify the limits and scope of this practice, with regard to aspects of awareness / participation and awaken to an awareness of critical social subjects in the collective social and environmental perspective. The study seeks to investigate if this experience has allowed the individual and collective social subjects, understand and act in their daily life, as the changes in attitudes postures, and expand their interests to participate in various public spaces this intention, is considered the educational activities made with the principles of environmental education in the construction of Agenda 21 that have contributed in raising awareness / participation of social actors of the Permanent Forum of Agenda 21. While reference methodology, the research focuses on theoretical design Freireana with relevance on the dimensions of dialogue, critical thinking and the human dimension comprising the act as educational practice of freedom, the prospect of human emancipation and social transformation of reality, and bring other thinkers as, Carvalho (2004), Trigueiro (2003), Days (2004), among others. The investigation of this practice points to the subject of education, which ECOCIENCIA to install the Agenda 21 and its effect on demand under municipal, German, providing a change of attitudes and postures and certainly, generating a new look and act in the world, broadening their interests and desires of inserting themselves, to participate in public spheres, particularly in establishing relations with dialogical criticality with the authorities and face the demands socio-environmental locations.

A participação popular na elaboração de políticas públicas de desenvolvimento local: um estudo no Município de Serrinha/RN (1997-2004)

The question of participation has been debated in Brazil since the 1980 decade in search a better way to take care of poulation s demand. More specificaly after the democratic open (1985) begins to be thought ways to make population participates of decisions related to alocation of public resources. The characteristic of participates actualy doesn t exist, population to be carried through is, at top, consulted, and the fact population participates stays restrict to some technics interests at the projects, mainly of public politics of local development. Observe that this implementation happens through a process and that has its limits (pass) that could be surpassed through strategies made to that. This dissertation shows results of a research about participative practices in city of Serrinha between 1997 and 2004, showing through a study of the case of Serrinha what was the process used to carry through these pratices in a moment and local considered model of this application. The analyses were developed through a model of research elaborated by the author based on large literature respects the ideal process to implant a participative public politics. The present research had a qualitative boarding, being explorative and descritive nature. The researcher (author of this dissertation) carried through all the research phases, including the transcriptions of interviews that were recorded with a digital voice recorder. Before the analysis of these data was verified that despite the public manager (former-mayor) had had a real interest in implant a process of local development in city, he was not able to forsee the correct process to do it. Two high faults were made. The first was the intention to have as tool a development plan, what locked up to make this plan was the booster of supossed participative pratice and no the ideal model that would be a plan generate by popular initiative. The second one was absence of a critical education project for the population that should be the fisrt step to carry through a politc like that

As condições e o sentido do trabalho doméstico realizado por adolescentes que residem no local de emprego

The house work is a reality for girls of humble class and one of the most found forms of work among adolescent workers. Moreover, it is a mean of work which reproduces poverty and gender relations within the society. The purpose of this essay in to understand the house work in the life of adolescent workers, emphasizing the meaning produced by these teenagers concerning the job they perform. In order to achieve such goal, questionnaires were applied to 332 adolescents, under 18 years old from public schools (from EJA-supletivo) in Natal, with the purpose of mapping the registration of this activity among young students. Next, 14 adolescents were interviewed in order to recognize the meaning of this work and its repercussions over the teenagery, such as school education, socialization, relations with employers and adolescent s self-image. Later we have noticed most workers among the students from public schools are housemaids. Furthermore, this work is used as a form of social ascension and it contributes for the search for better opportunities in the state capital for adolescents who leave the countryside trying to agree to education and remuneration. This work plays an important role, which is to reproduce gender relations, as a woman works to maintain the private space as a female space and maintains the man out of this relation. Besides it reproduces class relations, ethny and generation conflicts, in which the employer replaces the control the parents have in the adolescent s life. Summing up, this study about house work have negative aspects, related to exploitation, humiliation and mistreat, as well as positive ones, for it permits the adolescent to improve his life conditions. The most important thing is to look for a mean of work in which human and workers rights are respected

Políticas públicas, desenvolvimento local e participação social nas instâncias de governança associadas ao turismo no Rio Grande do Norte

In contemporary dynamics, a change is observed in the institutional structure of the state, culminating in several policies for the tourist sector which promote a new management format. The from this view, the Tourism Regionalization Macro Program (TRP), considered a significant program to Ministry of Tourism, arose as an answer to this new reality, having as strategy a joint working of structuring and promotion turned at decentralization of actions, valuing the residents participation in the search of the permanent dialogue between peers and revaluation of places and territories, based in the regionalization process. Based on this bias, this study aims to examine the role of the Tourism State Council of Rio Grande do Norte, with regard to the tourism planning, trying to understand it and solve it as governance Instance, through the Tourism Regionalization Program interventions, given the participation context of its actors and agents. For purposes of this study is delimited as time frame the year 2007 at 2014, understanding that it was this time, there was greater council members accession, as well as different types of sectors representation of civil society, as a result of a tourism public policy based on principles of innovation and participation. In relation to the research problem, this study is conceptualized as a qualitative and the chosen method is the materialist dialectic. Still on the methodological options, utilize the Content Analysis. The results show that the institutionalization of governance instance as the Conetur does not contributes, ideally, in the planning and management process of participatory and integrated tourist activity, facing a fair direction of your space production. The research indicates that there are debates, discussions and guidelines (still in a timely and targeted form), but not reverberates practical effects, by act in a conjuncture that Is strategically designed for political and economic power game, setting the hegemonic actors performance, which uses this arena to instill personal desires and wishes, that are decided in absentia to the council.