Abstract Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o ) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.
Hedar and Ismail @cite_10 proposed a hybrid of a genetic algorithm and local search for MDS with a specific fitness function. Another hybrid genetic algorithm was proposed by Potluri and Singh @cite_42 .
@cite_42 @cite_10
2109865546 1539453972 2123497782 1968481105
We propose a hybrid algorithm for finding a set of nondominated solutions of a multi objective optimization problem. In the proposed algorithm, a local search procedure is applied to each solution (i.e., each individual) generated by genetic operations. Our algorithm uses a weighted sum of multiple objectives as a fitness function. The fitness function is utilized when a pair of parent solutions are selected for generating a new solution by crossover and mutation operations. A local search procedure is applied to the new solution to maximize its fitness value. One characteristic feature of our algorithm is to randomly specify weight values whenever a pair of parent solutions are selected. That is, each selection (i.e., the selection of two parent solutions) is performed by a different weight vector. Another characteristic feature of our algorithm is not to examine all neighborhood solutions of a current solution in the local search procedure. Only a small number of neighborhood solutions are examined to prevent the local search procedure from spending almost all available computation time in our algorithm. High performance of our algorithm is demonstrated by applying it to multi objective flowshop scheduling problems. The minimum dominating set (MDS) problem is one of the central problems of algorithmic graph theory and has numerous applications especially in graph mining. In this paper, we propose a new hybrid method based on genetic algorithm (GA) to solve the MDS problem, called shortly HGA-MDS. The proposed method invokes a new fitness function to effectively measure the solution qualities. The search process in HGA-MDS uses local search and intensification schemes beside the GA search methodology in order to achieve faster performance. Finally, the performance of the HGA-MDS is compared with the standard GA. The new invoked design elements in HGA-MDS show its promising performance compared with standard GA. Recently, the hybridization between evolutionary algorithms and other metaheuristics has shown very good performances in many kinds of multiobjective optimization problems (MOPs), and thus has attracted considerable attentions from both academic and industrial communities. In this paper, we propose a novel hybrid multiobjective evolutionary algorithm (HMOEA) for real-valued MOPs by incorporating the concepts of personal best and global best in particle swarm optimization and multiple crossover operators to update the population. One major feature of the HMOEA is that each solution in the population maintains a nondominated archive of personal best and the update of each solution is in fact the exploration of the region between a selected personal best and a selected global best from the external archive. Before the exploration, a selfadaptive selection mechanism is developed to determine an appropriate crossover operator from several candidates so as to improve the robustness of the HMOEA for different instances of MOPs. Besides the selection of global best from the external archive, the quality of the external archive is also considered in the HMOEA through a propagating mechanism. Computational study on the biobjective and three-objective benchmark problems shows that the HMOEA is competitive or superior to previous multiobjective algorithms in the literature. Abstract An efficient hybrid genetic algorithm (HGA) approach for solving the economic dispatch problem (EDP) with valve-point effect is presented in this paper. The proposed method combines the GA algorithm with the differential evolution (DE) and sequential quadratic programming (SQP) technique to improve the performance of the algorithm. GA is the main optimizer, while the DE and SQP are used to fine tune in the solution of the GA run. To improve the performance of the SQP, the cost function of EDP is approximated by using a smooth and differentiable function based on the maximum entropy principle. An initial population obtained by using uniform design exerts optimal performance of the proposed hybrid algorithm. The combined algorithm is validated for two test systems consisting of 13 and 40 thermal units whose incremental fuel cost function takes into account the valve-point loading effects. The proposed combined method outperforms other algorithms reported in literatures (EP, EP–SQP, PSO, PSO–SQP) for EDP considering valve-point effects.