Navegando por Palavras-chave "Metaheuristic"
Agora exibindo 1 - 5 de 5
Resultados por página
Opções de Ordenação
- ItemAcesso aberto (Open Access)Formulações e heurísticas para o problema de localização de coberturas com sobreposições(Universidade Federal de São Paulo (UNIFESP), 2020-02-19) Araujo, Eliseu Junio [UNIFESP]; Chaves, Antonio Augusto [UNIFESP]; Universidade Federal de São PauloCoverage location problems and its variations aim to locate facilities strategically to meet the maximum number of demand points that require attendance, meeting different criteria, for example, meeting service capacity constraints. We observe that in many contexts, there are regions that need different priorities for their population concentration, since a region may have different population concentrations. Thus, the priorities are represented by the amount and the organization of coverage zones that must offer as adequate support according to the number of demands covered, avoiding overload of service. Due to the literature have gaps of efficient approaches about this theme, this thesis proposes the overlaps control between coverage zones to meet different prioritization criteria. Thus, a constraint that enables this control is adapted to classical coverage problems. Basically, this constraint quantifies the proportion of overlaps between coverage zones and, depending on the user’s choice, maximizes or minimizes them. Therefore, the control is integrated into the Maximal Coverage Location Problem (MCLP), to the Probabilistic Maximal Coverage location-allocation Problem (PMCLP), and to the Coverage Location Problem (CLP). In instances that optimal solution was not found by CPLEX, the method Density Clustering Search (DCS) was chose to give good solutions to the classical problems due to having re- turned good solutions to problems related to coverage. Results show that overlaps control combination with coverage location problems was efficient, giving the expected solutions. DCS results also show that the method is efficient in terms of objective function value and computational time.
- ItemSomente MetadadadosIntelligent-guided adaptive search for the maximum covering location problem(Pergamon-Elsevier Science Ltd, 2017) Maximo, Vinicius R. [UNIFESP]; Nascimento, Maria C. V. [UNIFESP]; Carvalho, Andre C. P. L. F.Computational intelligence techniques are part of the search process in several recent heuristics. One of their main benefits is the use of an adaptive memory to guide the search towards regions with promising solutions. This paper follows this approach proposing a variation of a well-known iteration independent metaheuristic. This variation adds a learning stage to the search process, which can improve the quality of the solutions found. The proposed metaheuristic, named Intelligent-Guided Adaptive Search (IGAS), provides an efficient solution to the maximum covering facility location problem. Computational experiments conducted by the authors showed that the solutions found by IGAS were better than the solutions obtained by popular methods found in the literature. (C) 2016 Elsevier Ltd. All rights reserved.
- ItemSomente MetadadadosInvestigating Smart Sampling as a population initialization method for Differential Evolution in continuous problems(Elsevier B.V., 2012-06-15) Melo, Vinicius Veloso de [UNIFESP]; Botazzo Delbem, Alexandre Claudio; Universidade Federal de São Paulo (UNIFESP); Universidade de São Paulo (USP)Recently, researches have shown that the performance of metaheuristics can be affected by population initialization. Opposition-based Differential Evolution (ODE), Quasi-Oppositional Differential Evolution (QODE), and Uniform-Quasi-Opposition Differential Evolution (UQODE) are three state-of-the-art methods that improve the performance of the Differential Evolution algorithm based on population initialization and different search strategies. in a different approach to achieve similar results, this paper presents a technique to discover promising regions in a continuous search-space of an optimization problem. Using machine-learning techniques, the algorithm named Smart Sampling (SS) finds regions with high possibility of containing a global optimum. Next, a metaheuristic can be initialized inside each region to find that optimum. SS and de were combined (originating the SSDE algorithm) to evaluate our approach, and experiments were conducted in the same set of benchmark functions used by ODE, QODE and UQODE authors. Results have shown that the total number of function evaluations required by de to reach the global optimum can be significantly reduced and that the success rate improves if SS is employed first. Such results are also in consonance with results from the literature, stating the importance of an adequate starting population. Moreover, SS presents better efficacy to find initial populations of superior quality when compared to the other three algorithms that employ oppositional learning. Finally and most important, the SS performance in finding promising regions is independent of the employed metaheuristic with which SS is combined, making SS suitable to improve the performance of a large variety of optimization techniques. (C) 2012 Elsevier Inc. All rights reserved.
- ItemAcesso aberto (Open Access)Uma nova heurística para o problema de minimização de trocas de ferramentas(Universidade Federal de São Carlos, 2012-01-01) Chaves, Antonio Augusto [UNIFESP]; Senne, Edson Luiz França; Yanasse, Horacio Hideki [UNIFESP]; Universidade Federal de São Paulo (UNIFESP); Universidade Estadual Paulista (UNESP); Instituto Nacional de Pesquisas EspaciaisThe minimization of tool switches problem (MTSP) seeks a sequence to process a set of jobs so that the number of tool switches required is minimized. This study presents a new heuristic for the MTSP. This heuristic has two phases: a constructive phase, based on a graph where the vertices correspond to tools and there is an arc k = (i, j) linking vertices i and j if and only if the tools i and j are required to execute some job; and an improvement phase, based on an Iterated Local Search. Computational results show that the proposed heuristic has a good performance on the instances tested contributing to a significant reduction in the number of nodes generated by an enumerative algorithm.
- ItemAcesso aberto (Open Access)Traveling Backpacker Problem with priorities: mono-objective and multi-objective formulations(Universidade Federal de São Paulo, 2023-04-28) Costa, Calvin Rodrigues da [UNIFESP]; Rosset, Mariá Cristina Vasconcelos Nascimento; http://lattes.cnpq.br/1010810293243435; http://lattes.cnpq.br/2681751274592304The Traveling Backpacker Problem (TBP) is a combinatorial optimization problem whose goal is to define a minimum-cost route in low-cost airlines. In the TBP, a limited travel time is imposed, as well as the number of stay days associated with each destination and time-varying air ticket costs. Furthermore, the traveler must visit all predefined locations and a length of stay at each destination. The cost to move from one specific location to another varies according to the moment the travel occurs. The literature on the TBP is still scarce and lacks investigation in considering new particularities of the application and heuristic methods. In line with this, the contributions of this Ph.D. thesis are: (i) a heuristic method for the TBP; (ii) the investigation of the TBP in scenarios where the traveler has a limited budget and subjective scores linked to the destinations of interest. In the second contribution, we approach the problem of deciding, besides the route, which places to visit considering the involved costs, preferences, and other constraints (available air tickets and the number of stay days, for example). For such, first, we present a study on the Prize Collecting Traveling Backpacker Problem (PCTBP). In the PCTBP, prizes are assigned to the places according to the user's preferences for the destinations. Two PCTBP models were introduced: (i) one that minimizes the air ticket costs plus the penalties for unvisited destinations (PCTBP-I); (ii) another that maximizes the prizes associated with the destinations but limits the budget according to a predefined value (PCTBP-II). To evaluate the first problem an exact solver to solve several diverse real instances was considered. The results of this experiment indicated that, depending on how the user assigns the prizes, the pattern of the routes differs significantly. Based on our observations of the PCTBP, we also propose the bi-objective PCTBP (BO-PCTBP). The goal of BO-PCTBP is to maximize priorities while minimizing air ticket costs. To solve this problem, two adaptations of the evolutionary multi-objective optimization algorithm, Nondominated Sorting Genetic Algorithm II (NSGA-II), were presented. Furthermore, we introduced a new set of instances based on real-world data and conducted experiments using both the instances used in the PCTBP experiments. The results suggest that the proposed NSGA-II obtains, in general, a diversified approximate Pareto frontier. To further improve the results, however, a more robust parameter tuning is needed as indicated by the analysis of the results.