China
Africa
Explore chapters and articles related to this topic
Brain Storm Optimization (BSO) for Coverage and Connectivity Problems in Wireless Sensor Networks
Published in Ibrahiem M. M. El Emary, Anna Brzozowska, Shaping the Future of ICT, 2017
Solutions to these problems also could be classified into centralized algorithms such as in Cardei and Du (2005), Cardei and Wu (2006), and Slijepcevic and Potkonjak (2001), and distributed algorithms such as in Yardibi and Karasan (2010). In Cardei and Du (2005), the authors proposed an algorithm to monitor an object in the monitored field. The main idea behind their algorithm is to divide the sensor nodes into sets where each set can track/cover the target in the whole monitored area. This problem is well known under the title of maximum set cover problem. Cardei and Wu (2006) extended this work and proved that the maximum set cover problem is NP-complete problem. Slijepcevic and Potkonjak (2001) took another approach where they divided the monitored area into fields that can be covered by the same set of nodes. The linear programming techniques were not far from targeting the coverage problem solution. For instance, Pyun and Cho (2009) proposed integer linear programming (ILP) for multiple target tracking with network lifetime extension. In Yardibi and Karasan (2010), a distributed algorithm was proposed for partial target coverage. In other words, they assume that the full coverage of the monitored field or the target is not required; only the coverage is required with certain percentage. Sensors’ residual energy is utilized to check on the performance of the proposed algorithm.
Introduction to Coverage Optimization in Wireless Sensor Networks
Published in Huynh Thi Thanh Binh, Nilanjan Dey, Soft Computing in Wireless Sensor Networks, 2018
Huynh Thi Thanh Binh, Nguyen Hai Nam
In phase one, the goal is to find SSCAT (sensor set covering all targets) that uses the minimum number of sensor to cover each target by at least one sensor. To simplify the problem, it is assumed that the sensors’ coordinates are integers. Since this is an NP-complete set cover problem, the greedy set cover algorithm is used to solve this problem in polynomial time. After covering each target with one or more sensor(s), SSCAT set is doubled (now denoted SSCAT’) to let at least two sensors covering on each target, enhancing the fault-tolerance of the target monitoring.
Nature-Inspired Approaches to Test Suite Minimization for Regression Testing
Published in Ankita Bansal, Abha Jain, Sarika Jain, Vishal Jain, Ankur Choudhary, Computational Intelligence Techniques and Their Applications to Software Engineering Problems, 2020
Nowadays, software industries use continuous integration and continuous development models, with new requirements being added along with their updates. Regression testing plays a crucial role in retaining quality and reliability (Yamuç, Cingiz, Biricik, and Kalıpsız 2017). Regression testing is performed to check whether the changes introduced any faults or vulnerabilities. The extensive collection of test cases takes more time ranging from days to weeks to run (Zheng, Hierons, Li, Liu, and Vinciotti 2016). In addition, new and updated requirements need more test cases to be designed for complete testing, which creates a broad set of redundant test cases (Zhang, Liu, Cui, Hei, and Zhang 2011). Consequently, the regression test suite reduction came into practice. This approach tries to remove redundancy, which thereby reduces the cost of execution. The competitive market strives for small budgets and quick solutions (Yamuç, Cingiz, Biricik, and Kalıpsız 2017), which require a representative set as efficient as the original set. Computational intelligence algorithms are capable of solving such complex problems. This problem is equivalent to a minimal set cover problem, that is, NP-complete problem. Nature-inspired algorithms have the potential to solve NP-complete problems efficiently and effectively (Haider, Nadeem, and Akram 2016). In this chapter, we focus on test suite minimization approaches that use nature-inspired algorithms. We formulated the following research questions to assess the potential of nature-inspired algorithms in solving the problem: RQ1: Which nature-inspired optimization algorithms are used in the field of regression test suite minimization?RQ2: Whether the optimization algorithms are used for a single objective or multi-objective test suite minimization?RQ3: Which testing criteria are used for designing fitness function?RQ4: Which performance metrics and datasets are used for validation of the results?
A primer on the application of neural networks to covering array generation
Published in Optimization Methods and Software, 2022
Ludwig Kampel, Michael Wagner, Ilias S. Kotsireas, Dimitris E. Simos
A typical optimization problem for set covers is the minimal set cover problem. That is, for given , to find a subset of minimal cardinality, such that . We call also an SC instance.
Efficient network algorithms for two special cases of the weighted set cover problem
Published in International Journal of Management Science and Engineering Management, 2018
Javad Tayyebi, Abumoslem Mohammadi
Problem (1) is one of the 21 problems whose NP-hardness was first established by Karp (1972). Thus, due to its inherent complexity, problem (1) cannot be solved efficiently in an exact way unless it is NP-hard. There exist four different remedies to this problem:to apply implicit enumeration methods;to design heuristic and metaheuristic methods;to present polynomial-time approximation algorithms with guaranteed performance;to propose polynomial-time exact algorithms for some special cases of the problem.Since the weighted set cover problem can be formulated as a binary linear programming one, the branch and bound and the branch and cut methods and Benders decomposition are used to solve it (for more details, see Gendron, Lucena, da Cunha, & Simonetti, 2014, and Haddadi, 2017). Heuristic and metaheuristic methods such as the artificial bee colony algorithm (Crawford et al., 2014a; Cuesta, Crawford, Soto, & Paredes, 2014), the cultural algorithm (Crawford, Soto, & Monfroy, 2013), ant colony optimization (Jovanovic & Tuba, 2011; Ren, Feng, Ke, & Zhang, 2010), tabu search (Bilal, Galinier, & Guibault, 2014; Zhou, Lu, Wang, Ding, & Peng, 2015), local search (Soto et al., 2015; Wang, Belhassena, Zhang, & Yin, 2017), and the binary firefly algorithm (Crawford et al., 2014a) are also applied to solve it. All these methods run in exponential times in the worst case. Hence, it is worthwhile to design polynomial-time algorithms to obtain satisfactory solutions for large-scale instances in a reasonable time. Among approximation techniques, the greedy algorithm was shown to give an ( ln n ln ln n + O(1))-approximation for the set cover problem (Slavík, 1997). The problem also has a linear programming based algorithm that gives an approximation to within the same factor (Srinivasan, 1999).