TECNALIA Publications Repository :: Browsing by Keyword "Multi-objective optimization"

Browsing by Keyword "Multi-objective optimization"

Now showing 1 - 15 of 15

Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem
(2020) Murua, Maialen; Galar, Diego; Santana, Roberto; FACTORY; Tecnalia Research & Innovation
The Hamiltonian cycle problem (HCP) consists of finding a cycle of length N in an N-vertices graph. In this investigation, a graph G is considered with an associated set of matrices, in which each cell in the matrix corresponds to the weight of an arc. Thus, a multi-objective variant of the HCP is addressed and a Pareto set of solutions that minimizes the weights of the arcs for each objective is computed. To solve the HCP problem, the Branch-and-Fix algorithm is employed, a specific branching algorithm that uses the embedding of the problem in a particular stochastic process. To address the multi-objective HCP, the Branch-and-Fix algorithm is extended by computing different Hamiltonian cycles and fathoming the branches of the tree at earlier stages. The introduced anytime algorithm can produce a valid solution at any time of the execution, improving the quality of the Pareto Set as time increases.
Bio-inspired computation: Where we stand and what's next
(2019-08) Del Ser, Javier; Osaba, Eneko; Molina, Daniel; Yang, Xin She; Salcedo-Sanz, Sancho; Camacho, David; Das, Swagatam; Suganthan, Ponnuthurai N.; Coello Coello, Carlos A.; Herrera, Francisco; IA; Quantum
In recent years, the research community has witnessed an explosion of literature dealing with the mimicking of behavioral patterns and social phenomena observed in nature towards efficiently solving complex computational tasks. This trend has been especially dramatic in what relates to optimization problems, mainly due to the unprecedented complexity of problem instances, arising from a diverse spectrum of domains such as transportation, logistics, energy, climate, social networks, health and industry 4.0, among many others. Notwithstanding this upsurge of activity, research in this vibrant topic should be steered towards certain areas that, despite their eventual value and impact on the field of bio-inspired computation, still remain insufficiently explored to date. The main purpose of this paper is to outline the state of the art and to identify open challenges concerning the most relevant areas within bio-inspired optimization. An analysis and discussion are also carried out over the general trajectory followed in recent years by the community working in this field, thereby highlighting the need for reaching a consensus and joining forces towards achieving valuable insights into the understanding of this family of optimization techniques.
Cost-efficient deployment of multi-hop wireless networks over disaster areas using multi-objective meta-heuristics
(2018-01-03) Bilbao, M. N.; Del Ser, Javier; Perfecto, C.; Salcedo-Sanz, S.; Portilla-Figueras, J. A.; IA
Nowadays there is a global concern with the growing frequency and magnitude of natural disasters, many of them associated with climate change at a global scale. When tackled during a stringent economic era, the allocation of resources to efficiently deal with such disaster situations (e.g., brigades, vehicles and other support equipment for fire events) undergoes severe budgetary limitations which, in several proven cases, have lead to personal casualties due to a reduced support equipment. As such, the lack of enough communication resources to cover the disaster area at hand may cause a risky radio isolation of the deployed teams and ultimately fatal implications, as occurred in different recent episodes in Spain and USA during the last decade. This issue becomes even more dramatic when understood jointly with the strong budget cuts lately imposed by national authorities. In this context, this article postulates cost-efficient multi-hop communications as a technological solution to provide extended radio coverage to the deployed teams over disaster areas. Specifically, a Harmony Search (HS) based scheme is proposed to determine the optimal number, position and model of a set of wireless relays that must be deployed over a large-scale disaster area. The approach presented in this paper operates under a Pareto-optimal strategy, so a number of different deployments is then produced by balancing between redundant coverage and economical cost of the deployment. This information can assist authorities in their resource provisioning and/or operation duties. The performance of different heuristic operators to enhance the proposed HS algorithm are assessed and discussed by means of extensive simulations over synthetically generated scenarios, as well as over a more realistic, orography-aware setup constructed with LIDAR (Laser Imaging Detection and Ranging) data captured in the city center of Bilbao (Spain).
Energy-Aware Multi-Objective Job Shop Scheduling Optimization with Metaheuristics in Manufacturing Industries: A Critical Survey, Results, and Perspectives: A Critical Survey, Results, and Perspectives
(2022-01-29) Para, Jesus; Del Ser, Javier; Nebro, Antonio J.; IA
In recent years, the application of artificial intelligence has been revolutionizing the manufacturing industry, becoming one of the key pillars of what has been called Industry 4.0. In this context, we focus on the job shop scheduling problem (JSP), which aims at productions orders to be carried out, but considering the reduction of energy consumption as a key objective to fulfill. Finding the best combination of machines and jobs to be performed is not a trivial problem and becomes even more involved when several objectives are taken into account. Among them, the improvement of energy savings may conflict with other objectives, such as the minimization of the makespan. In this paper, we provide an in-depth review of the existing literature on multi-objective job shop scheduling optimization with metaheuristics, in which one of the objectives is the minimization of energy consumption. We systematically reviewed and critically analyzed the most relevant features of both problem formulations and algorithms to solve them effectively. The manuscript also informs with empirical results the main findings of our bibliographic critique with a performance comparison among representative multi-objective evolutionary solvers applied to a diversity of synthetic test instances. The ultimate goal of this article is to carry out a critical analysis, finding good practices and opportunities for further improvement that stem from current knowledge in this vibrant research area.
Extending the speed-constrained multi-objective PSO (SMPSO) with reference point based preference articulation
(Springer Verlag, 2018) Nebro, Antonio J.; Durillo, Juan J.; García-Nieto, José; Barba-González, Cristóbal; Del Ser, Javier; Coello Coello, Carlos A.; Benítez-Hidalgo, Antonio; Aldana-Montes, José F.; Fonseca, Carlos M.; Lourenco, Nuno; Machado, Penousal; Paquete, Luis; Whitley, Darrell; Auger, Anne; IA
The Speed-constrained Multi-objective PSO (SMPSO) is an approach featuring an external bounded archive to store non-dominated solutions found during the search and out of which leaders that guide the particles are chosen. Here, we introduce SMPSO/RP, an extension of SMPSO based on the idea of reference point archives. These are external archives with an associated reference point so that only solutions that are dominated by the reference point or that dominate it are considered for their possible addition. SMPSO/RP can manage several reference point archives, so it can effectively be used to focus the search on one or more regions of interest. Furthermore, the algorithm allows interactively changing the reference points during its execution. Additionally, the particles of the swarm can be evaluated in parallel. We compare SMPSO/RP with respect to three other reference point based algorithms. Our results indicate that our proposed approach outperforms the other techniques with respect to which it was compared when solving a variety of problems by selecting both achievable and unachievable reference points. A real-world application related to civil engineering is also included to show up the real applicability of SMPSO/RP.
A framework to improve urban accessibility and environmental conditions in age-friendly cities using graph modeling and multi-objective optimization
(2023-06) Delgado-Enales, Iñigo; Del Ser, Javier; Molina, Patricia; IA
The rapid growth of cities in recent decades has unleashed several challenges for urban planning, which have been exacerbated by their aging population. Among the most pressing problems in cities are those related to mobility and environmental quality, by which a global concern has flourished around enhancing pedestrian accessibility for both environmental and health-related reasons. To tackle this issue, this paper presents a new framework that combines multi-objective optimization with a graph model that aims to support urban planning and management to enhance age-friendly cities. The framework allows designing urban projects that improve accessibility and reduce noise and/or air pollution through the installation of urban elements (ramps and escalators, elevators, acoustic and vegetation panels), while considering the overall economic cost of the installation. To explore the trade-off between these objectives, we resort to multi-objective evolutionary algorithms, which permit to compute near Pareto-optimal interventions over the graph model of the urban area under study. We showcase the applicability of the proposed framework over two use cases in the city of Barcelona (Spain), both quantitatively and qualitatively. Results evince that the framework can help urban planners make informed decisions towards enhancing urban accessibility and the environmental quality of age-friendly cities.
jMetalPy: A Python framework for multi-objective optimization with metaheuristics: A Python framework for multi-objective optimization with metaheuristics
(2019-12) Benítez-Hidalgo, Antonio; Nebro, Antonio J.; García-Nieto, José; Oregi, Izaskun; Del Ser, Javier; Quantum; IA
This paper describes jMetalPy, an object-oriented Python-based framework for multi-objective optimization with metaheuristic techniques. Building upon our experiences with the well-known jMetal framework, we have developed a new multi-objective optimization software platform aiming not only at replicating the former one in a different programming language, but also at taking advantage of the full feature set of Python, including its facilities for fast prototyping and the large amount of available libraries for data processing, data analysis, data visualization, and high-performance computing. As a result, jMetalPy provides an environment for solving multi-objective optimization problems focused not only on traditional metaheuristics, but also on techniques supporting preference articulation, constrained and dynamic problems, along with a rich set of features related to the automatic generation of statistical data from the results generated, as well as the real-time and interactive visualization of the Pareto front approximations produced by the algorithms. jMetalPy offers additionally support for parallel computing in multicore and cluster systems. We include some use cases to explore the main features of jMetalPy and to illustrate how to work with it.
Multi-objective design of time-constrained bike routes using bio-inspired meta-heuristics
(Springer Verlag, 2018) Osaba, Eneko; Del Ser, Javier; Bilbao, Miren Nekane; Lopez-Garcia, Pedro; Nebro, Antonio J.; Melab, Nouredine; Korosec, Peter; Talbi, El-Ghazali; Quantum; IA
This paper focuses on the design and implementation of a bike route optimization approach based on multi-objective bio-inspired heuristic solvers. The objective of this approach is to produce a set of Pareto-optimal bike routes that balance the trade-off between the length of the route and its safety level, the latter blending together the slope of the different street segments encompassing the route and their average road velocity. Additionally, an upper and lower restriction is imposed on the time taken to traverse the route, so that the overall system can be utilized for planning bike rides during free leisure time gaps. Instead of designing a discrete route encoding strategy suitable for heuristic operators, this work leverages a proxy software – Open Trip Planner, OTP – capable of computing routes based on three user-level preference factors (i.e. safety, inclination and duration), which eases the adoption of off-the-shelf multi-objective solvers. The system has been assessed in a realistic simulation environments over the city of Bilbao (Spain) using multi-objective bio-inspired approaches. The obtained results are promising, with route sets trading differently distance for safety of utmost utility for bike users to exploit fully their leisure time.
A multi-objective grouping Harmony Search algorithm for the optimal distribution of 24-hour medical emergency units
(2013-05) Landa-Torres, I.; Manjarres, D.; Salcedo-Sanz, S.; Del Ser, J.; Gil-Lopez, S.; Tecnalia Research & Innovation; IA
This paper presents a novel multi-objective heuristic approach for the efficient distribution of 24-h emergency units. This paradigm is essentially a facility location problem that involves determining the optimum locations, within the existing health care centers, where to deploy 24-h emergency resources, as well as an efficient assignment of patients to such newly placed resources through the existing medical care infrastructure. The formulation of the underlying NP-complete problem is based on a bi-objective distance and cost metric, which is tackled in our approach by combining a Harmony Search algorithm with a grouping encoding and a non-dominated solution sorting strategy. Additionally, the nominal grouping encoding procedure has been redefined in order to reduce the dimension of the search space, thus allowing for a higher efficiency of the searching process. Extensive simulations in a real scenario-based on the geographic location of medical centers over the provinces of Guadalajara and Cuenca (Spain)-show that the proposed algorithm is statistically robust and provides a wide range of feasible solutions, hence offering multiple alternatives for the distribution of emergency units.
A novel multi-objective algorithm for the optimal placement of wind turbines with cost and yield production criteria
(IEEE Computer Society, 2014) Manjarres, Diana; Sanchez, Valentin; Del Ser, Javier; Landa-Torres, Itziar; Gil-Lopez, Sergio; Vande Walle, Naima; Guidon, Nicolaz; IA; HPA; Tecnalia Research & Innovation
During the last years wind energy has experimented a significant growth in comparison with other types of renewable energy sources. Accordingly, the number of wind farms has increased sharply to become one of the most developed worldwide infrastructures. Unfortunately, the high number of constraints and restrictions that must be considered nowadays when designing a wind farm deployment (e.g. protected environmental areas or geographical unfeasibility) calls for tools aimed at the cost-effective optimal placement of wind farms, along with an optimized micro-siting of their compounding wind turbines. In this paper a novel multi-objective adaptation of the Harmony Search meta-heuristic algorithm is developed and tested for efficiently solving the problem of optimally deploying wind turbines in wind farms, which is accomplished by simultaneously addressing two conflicting objectives: the yield production and the capital cost of the deployment. Experimental simulation results over a certain region of the Basque Country (northern Spain) will be presented and discussed so as to shed light on the practical applicability of the derived solver.
One-way urban traffic reconfiguration using a multi-objective harmony search approach
(2013-07) Salcedo-Sanz, S.; Manjarrés, D.; Pastor-Sánchez, Á; Del Ser, J.; Portilla-Figueras, J. A.; Gil-López, S.; IA
The use of intelligent optimization systems has been a major topic of research in the last few years for improving the existing urban infrastructure, the traffic optimization and the mobility of citizens. These techniques are of great importance in the analysis and optimization of transportation networks, as well as their re-organization to improve users' mobility. In this paper we focus on the reconfiguration of one-way roads in a city after the occurrence of a major problem (e.g. a long-term road cut) in order to provide alternative routes that guarantee the mobility of citizens. In this manuscript a novel definition of this problem is formulated, for whose efficient resolution a novel two-objective approach based on the harmony search (HS) algorithm is proposed. The effectiveness of this proposal is tested in several synthetic instances, along with a real scenario in a city near Madrid, Spain. Extensive simulation results have been analyzed to verify that our proposal obtains excellent results in all the considered scenarios.
Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm
(2022-04) Murua, M.; Galar, D.; Santana, R.; FACTORY; Tecnalia Research & Innovation
The Hamiltonian cycle problem consists of finding a cycle in a given graph that passes through every single vertex exactly once, or determining that this cannot be achieved. In this investigation, a graph is considered with an associated set of matrices. The entries of each of the matrix correspond to a different weight of an arc. A multi-objective Hamiltonian cycle problem is addressed here by computing a Pareto set of solutions that minimize the sum of the weights of the arcs for each objective. Our heuristic approach extends the Branch-and-Fix algorithm, an exact method that embeds the problem in a stochastic process. To measure the efficiency of the proposed algorithm, we compare it with a multi-objective genetic algorithm in graphs of a different number of vertices and density. The results show that the density of the graphs is critical when solving the problem. The multi-objective genetic algorithm performs better (quality of the Pareto sets) than the proposed approach in random graphs with high density; however, in these graphs it is easier to find Hamiltonian cycles, and they are closer to the multi-objective traveling salesman problem. The results reveal that, in a challenging benchmark of Hamiltonian graphs with low density, the proposed approach significantly outperforms the multi-objective genetic algorithm.
Some investigations into the optimal dimensional synthesis of parallel robots
(2016-04-01) Kelaiaia, Ridha; Zaatri, Abdelouahab; Company, Olivier; Chikh, Lotfi; Tecnalia Research & Innovation
In this paper, we will perform a comparison between two approaches of dimensional synthesis of parallel robots. The first one concerns the single-objective optimization approach; in this case, the dimensional synthesis is expressed by taking into account only one performance criterion but enables to get a final solution if it exists. The second one concerns the multi-objective optimization approach; it enables to simultaneously take into account several performance criteria. However, this approach appears to provide a set of solutions instead of a single expected final solution which should directly enable to carry out the structural synthesis. In fact, the search of a single final solution is postponed to a further step where the designers have to impose and/or restrict certain parameters. And we will establish if it is really necessary to make a multi-objective optimization approach or if a single-objective is sufficient to reach the objectives set in the specifications (user requirements). A discussion is proposed concerning the arising questions related to each approach and leading to the optimal dimensional synthesis. The PAR2 robot with two degree-of-freedom is used to exemplify the analysis and the comparison of the two approaches. The proposed comparison can be applied to any classes of parallel robots.
Tool-Path Problem in Direct Energy Deposition Metal-Additive Manufacturing: Sequence Strategy Generation: Sequence Strategy Generation
(2020-05) Murua, Maialen; Suarez, Alfredo; Galar, Diego; Santana, Roberto; FACTORY; FABRIC_INTEL; Tecnalia Research & Innovation
The tool-path problem has been extensively studied in manufacturing technologies, as it has a considerable impact on production time. Additive manufacturing is one of these technologies; it takes time to fabricate parts, so the selection of optimal tool-paths is critical. This research analyzes the tool-path problem in the direct energy deposition technology; it introduces the main processes, and analyzes the characteristics of tool-path problem. It explains the approaches applied in the literature to solve the problem; as these are mainly geometric approximations, they are far from optimal. Based on this analysis, this paper introduces a mathematical framework for direct energy deposition and a novel problem called sequence strategy generation. Finally, it solves the problem using a benchmark for several different parts. The results reveal that the approach can be applied to parts with different characteristics, and the solution to the sequence strategy problem can be used to generate tool-paths.
Underwater Robot Task Planning Using Multi-Objective Meta-Heuristics
(2017-04-04) Landa-Torres, Itziar; Manjarres, Diana; Bilbao, Sonia; Del Ser, Javier; Tecnalia Research & Innovation; IA; BIGDATA
Robotics deployed in the underwater medium are subject to stringent operational conditions that impose a high degree of criticality on the allocation of resources and the schedule of operations in mission planning. In this context the so-called cost of a mission must be considered as an additional criterion when designing optimal task schedules within the mission at hand. Such a cost can be conceived as the impact of the mission on the robotic resources themselves, which range from the consumption of battery to other negative effects such as mechanic erosion. This manuscript focuses on this issue by devising three heuristic solvers aimed at efficiently scheduling tasks in robotic swarms, which collaborate together to accomplish a mission, and by presenting experimental results obtained over realistic scenarios in the underwater environment. The heuristic techniques resort to a Random-Keys encoding strategy to represent the allocation of robots to tasks and the relative execution order of such tasks within the schedule of certain robots. The obtained results reveal interesting differences in terms of Pareto optimality and spread between the algorithms considered in the benchmark, which are insightful for the selection of a proper task scheduler in real underwater campaigns.

Browsing by Keyword "Multi-objective optimization"

Results Per Page

Sort Options