China
Africa
Explore chapters and articles related to this topic
Introduction
Published in A Vasuki, Nature-Inspired Optimization Algorithms, 2020
Optimizing a cost function that is defined on a set of independent variables is a combinatorial optimization problem since it involves finding the right set of independent variables that maximizes or minimizes the function. The problems which generally fall into this category can be divided into two classes – those which are easy to solve and take up less time (can be solved in polynomial time) and those which take up a large amount of time and are practically infeasible to solve, called NP-hard problems. The most famous problem in computer science under the category of NP-hard is the traveling salesman problem (TSP), and other similar problems in this category are the graph partitioning (coloring) problem, job scheduling problem, and network routing problem, to name a few. These combinatorial optimization problems could be solved by the classical optimization algorithms in an infinitely long time or by the heuristic/metaheuristic optimization algorithms in finite short time that produces an optimum solution that closely approximates the actual solution.
Ant Colony Optimization
Published in Bogdan M. Wilamowski, J. David Irwin, Intelligent Systems, 2018
Christian Blum, Manuel López-Ibáñez
When dealing with optimization problems, algorithms that guarantee to find an optimal solution within bounded time are called complete algorithms. Nonetheless, some optimization problems may be too large or complex for complete algorithms to solve. In particular, there exists a class of problems, known as NP-hard, for which it is generally assumed that no complete algorithm with polynomial running time will ever be found. However, many practical situations only require to find a solution that, despite not being the optimal, is “good enough,” specially if such solution is found within a reasonable computation time. This compromise explains the interest in the development of approximate (incomplete) algorithms, which aim to find a solution with objective cost close to the optimal within a computation time much shorter than any complete algorithm.
*
Published in Fadi Al-Turjman, Wireless Sensor Networks, 2018
This node placement problem has been shown in Reference [7] to be NP-hard. Finding near optimal approximate solutions is also NP-hard in some cases. To address this complexity, we propose an Optimized two-phase Relay Placement (ORP) approach. The first phase sets up a connected network backbone using a reasonably small number of relays, which we call First Phase Relay Nodes (FPRNs). The first phase also finds a set of candidate locations for relays that are deployed in the second phase, which we call Second Phase Relay Nodes (SPRNs). The second phase aims at deploying the available number of SPRNs in the candidate positions obtained from the first phase in such a way that maximizes the WSN connectivity. The two schemes we present in this chapter differ in the first phase. The first scheme is the Grid-based Optimized Relay Placement (GORP) in which all relays are assumed to be deployed on grid vertices as shown in Figure 4.3. The second scheme is a general Optimized Relay Placement (ORP) scheme where relays may be placed at any point in the field. The general ORP scheme utilizes some interesting geometrical structures to connect the disjointed sectors and to find candidate positions for the SPRNs. Once the candidate positions for SPRNs are found, selecting the locations of the SPRNs is done by formulating the problem as a relaxed Semi-Definite Program (SDP) and solving it using a standard SDP solver.
Research on reducing fuzzy test sample set based on heuristic genetic algorithm
Published in Systems Science & Control Engineering, 2021
Zhihua Wang, Manman Cheng, Yongjian Wang
Approximation algorithms are algorithms used to find approximation methods to solve optimization problems. Approximation algorithms are usually related to NP-hard problems. Since it is impossible to solve the NP-hard problem by an effective polynomial time exact calculation, a polynomial time suboptimal solution is obtained. Unlike heuristic algorithms, only reasonable solutions are usually found fairly quickly, requiring a provable solution quality and a provable run time range, even if the approximation algorithm usually yields a quality-assured solution. The approximation algorithm refers to the scenario or accuracy of using the relevant algorithm to solve some practical problems, and the solution given is the theoretical optimal solution. In the reduction of the sample set, the approximation algorithm refers to giving the smallest sample set of samples as accurately as possible, and obtaining high-quality samples is the only standard of the approximation algorithm (Liu et al., 2020).
Medical diagnosis and treatment is NP-complete
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2021
Jeffrey. E. Arle, Kristen W. Carlson
Problems that are NP and NP-hard are NP-complete (NPC), a remarkable class in that all NPC problems, while often appearing very different from each other, have a related underlying structure, since they can be mapped to each other in PTIME (Arora & Barak, 2009; Sipser, 2006). Thousands of important mathematical and real-world problems have been shown to be NPC. The P class can be thought of as including those problems for which programmers have found efficient algorithms to solve them, while NPC contains those for which even the greatest programmers have not yet succeeded in finding a solution algorithm (Garey & Johnson, 1979). The great P = NP mystery is whether, with more cleverness and perseverance, we can find an algorithm to solve any NPC problem in PTIME – recall they appear to require computational resources that grow in super-polynomial time. If such an algorithm can be found, even in one single case, then all NPC problems would be solvable in PTIME, saving inestimable computational resources (Arora & Barak, 2009; Hopcroft & Ullman, 1979; Sipser, 2006). To wit, recently a problem tackled by leading mathematicians and computer science for decades, suspected of being intrinsically intractable, was shown to be polynomial-time tractable with a simple 2-page proof (Huang, 2019). No one knows whether showing that P = NP may be close at hand, impossible to prove, or false.
A comprehensive review of moth-flame optimisation: variants, hybrids, and applications
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2020
Abdelazim G. Hussien, Mohamed Amin, Mohamed Abd El Aziz
Optimisation research is a very active and promising area since it is applied to several applications such as energy, medical, economics, engineering, and computer (Hassanien & Emary, 2016; Yang, 2014). The goal of the optimisation problem is finding the best values of its variables, these problems can be classified to single or multi-objective, discrete or continuous, constrained or unconstrained and static or dynamic. Almost all real-world applications are NP-hard, however, the classical mathematical methods and techniques fail in addressing them due to their complexity. There are many metaheuristics algorithms inspired from nature which can be classified into the following categories: Evolutionary AlgorithmChemistry & Physics-basedSwarm-basedMusic-basedMaths-basedSport-basedPlant-basedHuman-based